Solution Le clonage se produit à des étapes qui produisent un «nouveau meilleur score» d'affilée

Question

Quelque chose qui a récemment attiré mon attention a été une étape plus lente que d'autres lorsqu'un «nouveau meilleur score» est produit. C'est certainement le clonage de la solution qui se produit à chaque étape qui produit un «nouveau meilleur score».

Cela ne pose aucun problème si les étapes "new best score" ne sont pas alignées. Si par exemple nous avons 50 étapes dans une rangée, le processus de clonage de la solution sera exécuté 50 fois. Une façon plus intelligente serait de faire le processus de clonage à la fin de la séquence (une seule fois).

Est-ce quelque chose qui peut être implémenté facilement ou y a-t-il quelque chose qui pourrait l'empêcher? Une autre idée serait de faire le clonage à chaque étape du "nouveau meilleur score", mais seulement de cloner les instances d'entité de planification modifiées par le déplacement sélectionné comme une étape et de les ajouter à la meilleure solution.

Answer 1

Si vous avez 50 étapes d'affilée, et que les 23 premières étapes améliorent la meilleure solution, devons-nous faire un clone de planification au cours de cette étape 23 de cette solution de travail? Oui, nous le faisons, car il n'y a aucune garantie que l'une des 27 prochaines étapes permettra d'améliorer le meilleur score, donc nous ne voulons pas perdre l'état de la solution à l'étape 23. Pas chaque étape améliore le meilleur score, certains aller à un score pire (en particulier avec l'acceptation tardive). Cela étant dit, dans Construction Heuristics - nous ne faisons pas de clones de planification intermédiaires car nous pouvons garantir que la solution ne fera que s'améliorer (plus les variables initialisées sont toujours meilleures).

Dans tous les cas, la meilleure façon de faire des clones de planification d'éclairage est de concevoir un modèle pour lequel la classe d'entités de planification n'a pas de références entrantes (à l'exception de la classe solution bien sûr)