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

Question

J'utilise le recuit simulé pour résoudre un problème de planification des ressources NP complet. Pour chaque commande candidat des tâches je calcule plusieurs coûts différents (ou des valeurs d'énergie). 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 la durée de l'horaire
• split_cost. Le nombre de jours de chaque tâche est retardée en raison d'interruptions par d'autres tâches (cela vise à décourager l'interruption d'une tâche une fois qu'il a commencé)
• 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 veux vraiment est pour deadline_cost toujours prendre la priorité sur global_finish_time, et pour global_finish_time prendre la priorité sur split_cost.

Alors ma question à Stack Overflow est: comment puis-je concevoir une fonction de probabilité d'acceptation qui prend en compte de multiples énergies, mais considère toujours la première énergie à être plus importante que la deuxième énergie, et ainsi de suite? Autrement dit, je voudrais passer old_cost et new_cost comme tuples de plusieurs coûts et retourner une valeur raisonnable.

Modifier 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 les éléments de coût qui ont des unités différentes. Je suis pratiquement obligé de comparer des pommes avec des oranges.

Alors, je mets un peu d'effort en « normalisant » les valeurs. Tout d'abord, deadline_cost est une somme des carrés, il croît de façon exponentielle tandis que les autres composants se développent de façon linéaire. Pour répondre à ce que j'utilise la racine carrée pour obtenir un taux de croissance similaire. En second lieu, j'ai développé une fonction qui calcule une combinaison linéaire des coûts, mais ajuste automatiquement les coefficients en fonction du composant le plus élevé des coûts vu jusqu'à présent.

Par exemple, si le tuple des coûts les plus élevés est (A, B, C) et le vecteur de coût d'entrée est (x, y, z), la combinaison linéaire est BCx + Cy + z. De cette façon, peu importe à quelle hauteur z obtient il ne sera jamais plus important que la valeur x de 1.

Cela crée « crénelage » dans la fonction de coût que de nouveaux coûts maximaux sont découverts. Par exemple, si C monte alors BCx et Cy seront à la fois plus élevé pour un (x, y, z) entrée et il en sera de différences entre les coûts. Une différence plus élevée du coût signifie que la probabilité d'acceptation va baisser, comme si la température a été abaissée brusquement une étape supplémentaire. En pratique, bien que ce n'est pas un problème parce que les coûts maximaux 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 prouvé converger vers un résultat correct puisque nous savons que le coût convergent vers une valeur inférieure.

Une chose qui m'a encore un peu confus est ce qui se passe lorsque les coûts maximaux sont 1,0 et inférieure, 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, à savoir l'ordre de priorité est brusquement inversée. Je suppose que la meilleure façon de traiter avec elle est d'utiliser le vecteur maximal à l'échelle de toutes les valeurs à intervalles donnés, de sorte que les coefficients peuvent toujours être les mêmes (par exemple, 100x + 10Y + z). Mais je ne l'ai pas essayé encore.

Answer 1

mbeckish est juste.

Pouvez-vous faire une combinaison linéaire des différentes énergies, et d'ajuster les coefficients?

les log-transformation Peut-être dedans et dehors?

Je l'ai fait un peu MCCM utilisant Metropolis-Hastings. Dans ce cas, je suis la définition (non normalisé) log-vraisemblance d'un état particulier (compte tenu de ses prieurs), et je trouve que le moyen de clarifier ma pensée sur ce que je veux.

Answer 2

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 un peu comme le recuit simulé standard explore les plateaux de solutions même énergie.

Cependant, cela ne donne à l'idée d'avoir la première priorité d'une prise.

Vous aurez probablement à modifier vos paramètres, tels que donner une température initiale plus élevée.

Answer 3

Je considérerais 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

Cela dépend de ce que vous entendez par « a priorité ». Par exemple, si l'deadline_cost diminue de 0,001, mais le coût de global_finish_time monte par 10000? Est-ce que vous revenez 1.0, parce que le deadline_cost a diminué, et qui a priorité sur toute autre chose? Cela semble que c'est un jugement que vous seul pouvez faire, à moins que vous pouvez fournir suffisamment de renseignements généraux sur le projet afin que les autres peuvent proposer leur propre appel un jugement éclairé.