Pondération des violations dans une fonction d'aptitude

Question

Je travaille sur mon projet de fin d'études en développant un algorithme génétique pour l'optimisation des horaires. Cela se passe assez bien pour l'instant car je produis des chromosomes aléatoires représentant l'emploi du temps de mes classes. J'ai conçu ma fonction de remise en forme ainsi que des contraintes potentielles, mais je suis actuellement bloqué sur la pondération de mes contraintes.

J'utilise la fonction suivante comme fonction d'aptitude :

1/1 + (Ci*Wci)

Ci étant le nombre de violations pour la contrainte i et Wci étant la pondération pour la contrainte i.

Il est évident que je dois donner plus de poids aux contraintes fortes qu'aux contraintes faibles.

Je me demandais si quelqu'un avait déjà utilisé cette technique et s'il existait une fourchette recommandée pour ces valeurs de poids.

Answer 1

Si l'on se contente d'ajouter la pénalité à la valeur d'aptitude actuelle d'un individu, il y a un problème car l'algorithme peut optimiser la solution sans minimiser les pénalités. Si l'algorithme peut réduire la valeur d'aptitude à un degré supérieur à la pénalité, la solution devient meilleure. En utilisant les pénalités, vous devez orienter la recherche vers la région réalisable en plus d'optimiser la qualité.

Je suggérerais de supposer une valeur d'aptitude constante, mais très mauvaise, pour toutes les solutions irréalisables auxquelles vous ajoutez le degré de violation des contraintes. Par exemple, l'individu ayant le plus mauvais objectif dans votre population actuelle pourrait être une valeur de base suffisante. Cette méthode présente l'avantage de rassembler toutes les solutions dans un même ordre : Les solutions irréalisables seraient comparées les unes aux autres uniquement en fonction de leur degré de violation des contraintes, toutes les solutions réalisables seraient comparées en fonction de leur efficacité et, à l'échelle globale, il y aurait une distinction entre la faisabilité et l'irréalisabilité.

Si vous ne le faites pas, vous mélangez des solutions irréalisables et faisables dans toute la gamme de vos qualités.

Edit : Je pense aussi qu'il y a quelque chose qui ne va pas avec votre fonction de fitness. Il manque probablement des parenthèses.