Divers codages des problèmes et opérateurs de voisinage associés aux codages
Codages analogues à ceux utilisés pour les algorithmes génétiques
Bien que le vocabulaire utilisé dans la littérature sur les méthodes d'amélioration par voisinage n'utilise pas les notions de chromosomes, de gènes, d'allènes etc. qui sont issus de l'analogie avec la reproduction naturelle, les codages utilisés pour les méthodes par voisinages sont les mêmes que pour les algorithmes génétiques
codages directs, indirects ou partiellement direct et partiellement indirect (un générateur n'étant utilisé que pour une partie des inconnues du problèmes),
codages binaires ou symboliques ou de permutations ou par des matrices etc.
Opérateurs de voisinage
Ce sont des opérateurs unaires.
Tous les opérateurs de mutation peuvent être utilisés comme opérateurs de voisinage.
Lorsque c'est possible, on donne une probabilité plus forte de visiter des voisins que l'on espère de meilleure qualité que le point courant.
Intérêt des codages mixtes (semi-directs et semi-indirects)
La solution d'un problème est définie par la valeur que prennent les inconnues du problème.
Pour les problèmes concrets complexes, on peut partitionner les inconnues en plusieurs grandes familles.
Souvent, des problèmes concrets difficiles deviennent faciles si on fixe la valeur d'une grande famille de ses inconnues.
Si c'est le cas, on met dans le codage les inconnues de cette grande famille et on utilise un programme pour trouver la solution optimale compte tenu des inconnues fixées.
Par exemple, pour le problème de la paella avec une seule personne pour réaliser la recette, on met dans le codage l'ordre dans lequel sont exécutées les tâches manuelles et un programme PERT permet de pénaliser les solutions non réalisables car il y a des circuits induits dans le graphe potentiel tâche ou sinon est capable de calculer les dates au plus tôt de réalisation de la recette.
