Comment concevoir la fonction de probabilité d'acceptation pour un recuit simulé avec des coûts distincts multiples?

Question

J'utilise simulated annealing pour résoudre un problème de planification de ressources NP-complet. Pour chaque candidat ordonnant les tâches, je calcule plusieurs coûts différents (ou valeurs énergétiques). Quelques exemples sont (bien que les détails ne sont probablement rien à voir avec la question):

• global_finish_time: Le nombre total de jours que les durées de calendrier.
• split_cost: Le nombre de jours pendant lesquels chaque tâche est retardée en raison d'interruptions par d'autres tâches (ceci est destiné à décourager l'interruption d'une tâche une fois qu'elle a démarré).
• deadline_cost: La somme du nombre de jours au carré par lequel chaque échéance manquée est en retard.

La fonction de probabilité d'acceptation traditionnelle ressemble à ceci (en Python):

def acceptance_probability(old_cost, new_cost, temperature): 
    if new_cost < old_cost: 
     return 1.0 
    else: 
     return math.exp((old_cost - new_cost)/temperature) 

Jusqu'à présent, j'ai combiné mes deux premiers coûts en un, en les ajoutant simplement, pour que je puisse nourrir le résultat dans acceptance_probability. Mais ce que je voudrais vraiment, c'est que deadline_cost prenne toujours le pas sur global_finish_time et que global_finish_time prenne le pas sur split_cost. Donc, ma question à Stack Overflow est la suivante: comment puis-je concevoir une fonction de probabilité d'acceptation qui prend en compte plusieurs énergies mais considère toujours que la première énergie est plus importante que la seconde énergie, et ainsi de suite? En d'autres termes, je voudrais passer en old_cost et new_cost comme tuples de plusieurs coûts et retourner une valeur raisonnable.

Edit: Après quelques jours d'expérimentation avec les solutions proposées, je conclus que la seule façon qui fonctionne assez bien pour moi est la suggestion de Mike Dunlavey, même si cela crée beaucoup d'autres difficultés avec des composants de coûts qui ont des unités différentes . Je suis pratiquement obligé de comparer des pommes avec des oranges. Donc, je me suis efforcé de «normaliser» les valeurs. Tout d'abord, deadline_cost est une somme de carrés, de sorte qu'il croît exponentiellement tandis que les autres composants croissent linéairement. Pour y remédier, j'utilise la racine carrée pour obtenir un taux de croissance similaire. Deuxièmement, j'ai développé une fonction qui calcule une combinaison linéaire des coûts, mais ajuste automatiquement les coefficients en fonction de la composante de coût la plus élevée vue jusqu'à présent. Par exemple, si le tuple des coûts les plus élevés est (A, B, C) et que le vecteur des coûts d'entrée est (x, y, z), la combinaison linéaire est BCx + Cy + z. De cette façon, peu importe la valeur de z, elle ne sera jamais plus importante qu'une valeur x de 1.

Cela crée des "jaggies" dans la fonction de coût lorsque de nouveaux coûts maximaux sont découverts. Par exemple, si C augmente, alors BCx et Cy seront tous les deux plus élevés pour une entrée donnée (x, y, z) et il en sera de même pour les différences entre les coûts. Une différence de coût plus élevée signifie que la probabilité d'acceptation diminuera, comme si la température était soudainement abaissée d'un pas supplémentaire. En pratique, ce n'est pas un problème, car les coûts maximums ne sont mis à jour que quelques fois au début et ne changent pas plus tard. Je crois que cela pourrait même être théoriquement convergé vers un résultat correct puisque nous savons que le coût convergera vers une valeur inférieure. Une chose qui me fait encore un peu confus est ce qui se passe lorsque les coûts maximaux sont de 1,0 et moins, disons 0,5. Avec un vecteur maximum de (0,5, 0,5, 0,5), cela donnerait la combinaison linéaire 0,5 * 0,5 * x + 0,5 * y + z, c'est-à-dire.l'ordre de préséance est soudainement inversé. Je suppose que la meilleure façon d'y remédier est d'utiliser le vecteur maximum pour mettre à l'échelle toutes les valeurs à des intervalles donnés, afin que les coefficients puissent toujours être les mêmes (disons, 100x + 10y + z). Mais je n'ai pas encore essayé.

Answer 1

mbeckish a raison. Pourriez-vous faire une combinaison linéaire des différentes énergies et ajuster les coefficients?

Peut-être les transformer en log-in et out?

J'ai fait du MCMC en utilisant Metropolis-Hastings. Dans ce cas, je définis la log-vraisemblance (non-normalisée) d'un état particulier (étant donné ses priors), et je trouve que c'est un moyen de clarifier ma pensée sur ce que je veux.

Answer 2

Cela dépend de ce que vous entendez par "a priorité". Par exemple, que se passe-t-il si le deadline_cost diminue de 0,001, mais le coût global_finish_time augmente de 10000? Renvoyez-vous 1.0, parce que le deadline_cost a diminué, et cela a préséance sur toute autre chose? Cela semble être un appel de jugement que vous seul pouvez faire, à moins que vous ne puissiez fournir suffisamment d'informations générales sur le projet pour que d'autres personnes puissent suggérer leur propre jugement éclairé.

Answer 3

je considère quelque chose le long des lignes de:

If (new deadline_cost > old deadline_cost) 
    return (calculate probability) 

else if (new global finish time > old global finish time) 
    return (calculate probability) 

else if (new split cost > old split cost) 
    return (calculate probability) 

else 
    return (1.0) 

Bien sûr chacun des trois endroits que vous calculez la probabilité pourrait utiliser une autre fonction.

Answer 4

je prendrais un soupçon d'algorithme évolutif multi-objectifs (MOEA) et avoir la transition si tous des objectifs passent en même temps que la fonction acceptance_probability que vous avez donné. Cela aura pour effet d'explorer le front de Pareto comme le recuit simulé standard explore les plateaux de solutions de même énergie.

Cependant, cela abandonne l'idée d'avoir le premier priorité.

Vous devrez probablement modifier vos paramètres, par exemple en lui donnant une température initiale plus élevée.