Algorithme génétique efficace

Question

Considérant ce problème: Ayant un vecteur de 1000 nombres réels positifs, trouve la partition optim des 1000 éléments en 7 parties de sorte que la somme des parties ait des valeurs (proches) approximatives.

Comment pourriez-vous faire la représentation des chromosomes, les opérateurs (mutation, crossover), la fonction de remise en forme, la sélection .. de sorte que vous résolvez le problème de la façon la plus efficace &?

Mon idée est de donner un indice à chaque nombre (le plus petit nombre a l'indice 1, le plus haut a l'indice 1000 par exemple) ... mais je ne pense pas que ce soit le moyen le plus efficace? Toutes les suggestions sont les bienvenues!

Answer 1

Comme c'est un problème de partition, je pense que vous devez avoir l'ensemble complet dans un seul chromosome. Dites que vous avez un tableau de longueur 1000 qui peut avoir des valeurs de 1 à 7. La fonction de fitness peut calculer la différence de la somme de chaque partition (moins c'est mieux). Crossover peut être fait avec un seul point ou double point. Puis la mutation peut changer aléatoirement un gène individuel de sa valeur à une valeur aléatoire, disons que la position 102 est 4, puis mute à 1. Avec cette solution, vous garantissez que chaque chromosome est une solution valable, même si elle est mauvaise. Je dois vérifier après chaque itération les chromosomes qui ne respectent pas les règles du problème (un problème que vous auriez si vous choisissiez d'avoir un chromosome par partition). Comme d'habitude, les critères de croisement et de probabilité de mutation nécessitent une exploration et un réglage avant d'obtenir la meilleure performance.