Hill Escalade et Tabu Recherche dans OptaPlanner

Question

J'utilise OptaPlanner pour résoudre certains problèmes de planification. J'ai lu la documentation et je ne sais pas exactement comment fonctionnent les algorithmes de Hill Climbing et Tabu Search. Ce que je ne suis pas sûr de est:

• n'escalade colline choisir seulement se déplace avec le meilleur score qui est mieux que le courant d'un ou permet-il de choisir se déplace avec le meilleur score qui est pas plus mal que l'actuel?
• Est-ce que la recherche tabu permet de sélectionner des coups qui ont un score WORSE supérieur au score actuel s'il n'y a pas de mouvement menant à une solution avec un score meilleur ou égal au score actuel?

Answer 1

Pour Climbing Hill, voir HillClimbingAcceptor#isAccepted(...). Il accepte tout mouvement dont le score est supérieur ou égal à jusqu'au dernier point. Et en regardant la config forager par défaut pour le climation de la colline (au LocalSearchPhaseConfig, qui dit foragerConfig.setAcceptedCountLimit(1);), dès que 1 mouvement est accepté, c'est le coup gagnant.

Pour Tabu Search, il sélectionnera les mouvements qui ont un score pire, si:

• dans le nombre de coups qu'il choisit par étape (habituellement acceptedCountLimit est configuré pour 1000 ou presque), pas mieux move est vu
• OU tous les mouvements qui mènent à un meilleur score sont dans la liste des tabous (ils sont "tabous à utiliser"). Pour solutionTabu, cela signifie qu'il y a une garantie qu'ils ne mèneront pas à une nouvelle meilleure solution (mais solutionTabu est inutile). Pour entityTabu il n'y a pas une telle garantie de 100%, mais vous obtiendrez de meilleurs résultats dans environ 99.999999999999999999999999999999999999999999999999999999999999999% des cas si vous avez plus de 50+ variables (et plus si vous avez plus de 1000 variables).

PS: L'escalade en montagne suce. Il n'y a jamais une bonne raison de ne pas utiliser Late Acceptance ou Tabu Search à la place. PPS: Utilisez le Benchmarker, laissez HC, LA, TS, ... se battre les uns contre les autres.

Cela vous donnera beaucoup de perspicacité.