Algorithmes génétiques pour l'optimisation de la coupe guillotine

Question

J'ai revu des algorithmes génétiques avec codage, optimisation et décodage. Mon premier essai était le voyageur de commerce avec une croix ordonnée qui fonctionnait très bien. J'ai trouvé un article qui essayait d'optimiser un génome plus complexe tout en optimisant un problème d'empaquetage 2D.

L'auteur encode le problème en utilisant la notation polonaise inversée qui avait du sens. Il utilise une combinaison de parties et V ou H comme opérateurs.

Ie 34H5V

Avec le décodage de la pile ayant à résoudre à un élément de pile qui est ma mise en page finale. Cela étant dit, le nombre d'opérateurs jusqu'à un certain point doit être inférieur de 1 au nombre de pièces jusqu'au même point. L'auteur indique ensuite qu'il a utilisé une croix mixte en utilisant une croix ordonnée sur les parties et un crossover binaire pour les opérateurs. J'ai réfléchi à cela mais je n'arrive pas à comprendre comment il sépare les pièces et les opérateurs avant de les traverser puis de les recombiner avant d'évaluer les performances et ils offrent peu de détails. Si un croisement binaire s'est produit en remplaçant les parties par un "X" pour conserver les positions relatives, elles peuvent être recombinées après le croisement, mais la relation entre l'opérateur et les parties n'est pas vraie.

Est-ce que quelqu'un a peut-être une ressource qui a traité un scénario similaire ou qui l'a peut-être utilisé avec succès?

Answer 1

Cela semblait beaucoup plus difficile qu'il ne l'était en réalité. Lorsque la population d'origine est générée, vous devez respecter les limitations définies par la notation postfixe. Quand un croisement se produit, vous construisez simplement un masque du parent

Ie xxxxooxoxx

où x est un objet et o est un operaror. Une fois que vous avez le masque contenant les positions, vous pouvez créer une piqûre seulement des opérateurs et un seul des objets. Les opérateurs peuvent être effectués avec un croisement binaire et les objets en tant que croisement partiel de la carte. Une fois cela fait, vous remplissez le masque avec la valeur dans l'ordre dans lequel ils apparaissent dans chaque groupe. Puisque le masque était valide, la progéniture est valide aussi. Le seul problème est d'obtenir tous les arrangements possibles car sans lui, tout sera limité aux masques. Il résout cela en faisant une mutation de swap dictée par les taux de mutation.

1. Sélectionnez un élément au hasard.
2. Si l'article est un opérateur alors A. Swithc l'opérateur à un autre type B. Sélectionnez un autre. Si c'est un objet, assurez-vous que les conditions requises sont remplies et si c'est le cas, changez.