Exemple de recherche par Tabu question

Question

Pourriez-vous s'il vous plaît me aider à comprendre ce Tabu search page 7 exemple:

TS est une méthode d'optimisation mathématique, appartenant à la classe des techniques basées sur la trajectoire . recherche Tabu améliore la performance d'une méthode de recherche locale en utilisant des structures de mémoire qui décrivent les solutions visitées: une fois une solution potentielle a été déterminé, il est marqué comme « tabou » (« Tabu » étant une autre orthographe le même mot) de sorte que l'algorithme ne visite pas cette possibilité à plusieurs reprises. Tabu recherche est attribué à Fred W. Glover

Je ne comprends pas pourquoi un triangle supérieur est utilisé, et pourquoi est- ceci:

La structure tabu montre maintenant que permuter les positions des modules 4 et 5 est interdit pour 3 itérations. Le mouvement le plus d'améliorer à cette étape est d'échanger 3 et 1 pour un gain de 2.

Pourriez-vous s'il vous plaît expliquer pourquoi le triangle et pourquoi est-ce la déclaration ci-dessus?

???

Answer 1

La déclaration

Dans l'exemple du powerpoint, ils ont choisi une durée de 3. Chaque fois qu'un échange est fait, il sera Tabu pour les 3 prochains mouvements.

C'est pourquoi à l'étape 1 (note: je commence à l'étape 0) vous avez fait la déclaration suivante:

La structure Tabu montre maintenant que échangeant les positions des modules 4 et 5 est interdite pour 3 itérations. Le mouvement le plus d'améliorer à cette étape est d'échanger 3 et 1 pour un gain de 2.

Permutation 3 et 1 à cette étape est la meilleure décision pour augmenter la valeur. Après votre dernière étape (étape 3), ils échangent réellement 4 et 5 même si c'est tabu en raison du critère d'aspiration. (20> 18 qui est le meilleur rapport qualité-prix jusqu'à présent).

Le triangle

La représentation est un triangle parce que la manipulation de permutation est symétrique. Vous n'avez donc pas besoin de plus d'un triangle supérieur pour représenter votre structure tabou.

Dans chaque cellule de la structure tabou, vous avez la durée restante (la durée restante pour que le mouvement soit tabu) de la paire (x, y) = (y, x). Je ne connais pas beaucoup la recherche de tabous, mais j'espère que cela aide.