J'utilise recuit simulé pour résoudre un problème de planification de ressources NP-complet. Pour chaque commande de candidats des tâches, j'ai calculé plusieurs coûts différents (ou valeurs énergétiques). Certains exemples sont (bien que les spécificités soient probablement non pertinentes pour la question):
global_finish_time : le nombre total de jours que la planification s'étend sur.
-
split_cost : le nombre de jours par lesquels chaque tâche est retardée en raison d'interruptions par d'autres tâches (ceci est censé décourager l'interruption d'une tâche une fois qu'elle a démarré).
-
date limite_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): xxx jusqu'à présent, j'ai combiné mes deux premiers coûts en un seul en les ajoutant simplement , afin que je puisse nourrir le résultat dans acceptation_probabilité . Mais ce que je voudrais vraiment, c'est pour mortsline_cost pour toujours primer sur global_finish_time , et pour global_finish_time pour primer sur Split_cost . Donc, ma question à la pile de pile est la suivante: comment puis-je concevoir une fonction de probabilité d'acceptation qui prend plusieurs énergies en compte, mais considère toujours la première énergie à être plus importante que la deuxième énergie, etc. ? En d'autres termes, je voudrais passer dans old_cost et nouveau_cost comme tubulles de plusieurs coûts et renvoyer une valeur sensible. EDIT: Après quelques jours d'expérimentation avec les solutions proposées, j'ai conclu que la seule façon qui fonctionne assez bien pour moi est la suggestion de Mike Dunlavey, même si cela crée de nombreuses autres difficultés avec des composants de coûts qui ont des unités différentes. Je suis pratiquement forcé de comparer les pommes avec des oranges. Donc, je mets des efforts en "normalisation" les valeurs. Tout d'abord, mortsline_cost est une somme de carrés, de sorte qu'il s'agrandit de manière exponentielle, tandis que les autres composants se développent linéairement. Pour résoudre ce problème, 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 du composant de coûts le plus élevé observé jusqu'à présent. Par exemple, si le tuple des coûts les plus élevés est (a , B, C) et le vecteur des coûts d'entrée sont (x, y, z), la combinaison linéaire est BCX + CY + Z. De cette façon, peu importe la hauteur de z obtient ne sera jamais plus importante qu'une valeur x de 1.
Ceci crée des "jaggies" dans la fonction de coût, car de nouveaux coûts maximaux sont découverts. Par exemple, si C monte, BCX et CY seront les deux plus élevés pour une entrée donnée (x, y, z) et 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'une étape supplémentaire. En pratique, ce n'est pas un problème, car les coûts maximum sont mis à jour à quelques reprises au début et ne changent pas plus tard. Je crois que cela pourrait même être théoriquement prouvé de converger à un résultat correct puisque nous savons que le coût convergera vers une valeur inférieure à 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 plus bas, 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 la priorité est soudainement inversé. Je suppose que la meilleure façon de gérer est d'utiliser le vecteur maximum pour réduire toutes les valeurs à des gammes données, de sorte que les coefficients puissent toujours être les mêmes (par exemple, 100x + 10Y + Z). Mais je n'ai pas encore essayé ça.
4 Réponses :
Cela dépend de ce que vous entendez par "prime la priorité".
Par exemple, que si le mortsline_cost diminue de 0,001, mais le coût global_finish_time augmente de 10000? Retournez-vous 1.0, car le mortline_cost a diminué, et qui a priorité sur autre chose?
Cela semble être un jugement appelant que vous seul pouvez faire, à moins que vous ne puissiez fournir suffisamment d'informations de base sur le projet afin que d'autres puissent suggérer leur propre appel de jugement informé.
Oui, les délais sont toujours plus importants que l'heure de finition mondiale. Même si le temps de finition mondial augmente de 10000, je souhaite que le système favorise un coût de délai inférieur. C'est ce que j'ai essayé d'expliquer dans la question, je suis désolé si ce n'était pas clair.
Je considérerais quelque chose dans le sens de: bien sûr, chacun des trois endroits que vous calculez que la probabilité pourrait utiliser une fonction différente.
Je vais essayer et vous revenir à vous. Je pensais à quelque chose de semblable mais que je vois un problème potentiel dans le fait qu'une différence X dans la première valeur représente la même probabilité qu'une différence X dans la deuxième valeur. Intuitivement une différence dans la deuxième valeur devrait représenter une valeur qui est en quelque sorte une probabilité infiniment inférieure. Un problème ici est qu'il est difficile de vous convaincre grâce à l'essai et à l'erreur que votre algorithme est sonore. Cela pourrait fonctionner pour des cas simples mais créer un comportement étrange dans des scénarios complexes. Je souhaite une confirmation théorique de la méthode.
Je suppose que c'est une approche heuristique qui n'est pas rare dans les solutions NP-complètes.
Je l'ai essayé et il génère des solutions assez bonnes. Le seul problème est qu'une fois que la composante la plus prioritaire s'est installée sur une valeur optimale, l'algorithme est trop susceptible de sauter de cette solution même à des températures basses. Ceci est logique puisque le déplacement de (0, 0) à (1, 0) a exactement la même probabilité que de passer de (0, 0) à (0, 1). Je laisserai la question ouverte pendant un moment et continuerai à expérimenter si quelque chose vaut mieux. À l'heure actuelle, j'éprouve une sorte de différence de magnitude dans la probabilité lors de l'évaluation d'un composant de priorité inférieure.
mbeckish a raison.
Pourriez-vous faire une combinaison linéaire des différentes énergies et ajuster les coefficients?
éventuellement en train de les transformer en et à l'extérieur?
J'ai fait du MCMC en utilisant Metropolis-Hastings. Dans ce cas, je définisize le log-risque (non normalisé) d'un État particulier (compte tenu de ses priors), et je trouve qu'un moyen de clarifier ma pensée à ce que je veux.
Les différentes quantités n'ont pas toujours des unités compatibles. Par exemple, la valeur de la date limite est carrée pour obtenir un type d'optimisation des moindres carrés, c'est-à-dire que je préfère retarder 3 tâches de 1 jour chacune plutôt que de retarder une tâche de 3 jours. J'en ai considéré cela, mais j'ai bien peur de rencontrer de nombreux cas frontières où le système ne fait pas la bonne chose parce que je n'ai pas fait les coefficients "juste juste" (s'il y a même une telle chose). Voir aussi réponse à McBeckish
@FLODIN: Vous voulez que votre surface d'énergie globale soit continue, je serais donc timide de si les déclarations. Outre cela, vous pouvez le faire joliment non linéaire, comme une repoussion de la justice des cas de frontière - une pensée.
Je prendrais un indice d'algorithme évolutif multi-objectif (Moée) et de transition si tous des objectifs passe simultanément avec la fonction Cependant, cela abandonne l'idée d'avoir la première priorité.
Vous devrez probablement modifier vos paramètres, tels que lui donner une température initiale plus élevée. acceptation_probabilité la fonction que vous avez donnée. Cela aura pour effet d'explorer le façade de Pareto, comme le recuit simulé standard explore les plateaux des solutions d'énergie.
Je serais intéressé de savoir s'il s'agit d'un problème d'industrie ou d'un académique. Salutations
Ce n'est pas universitaire. J'utilise cela comme une alternative au projet MS. L'objectif principal du programme est de faciliter la réponse à la question "Quand votre équipe peut-elle ajouter X à notre logiciel?"
Je sais que cette question est une des années d'âge, mais pour quelqu'un d'autre qui trébuche sur cette page via google ... dans la logique floue La somme pondérée est l'équivalent de logique - ou, donc vous disiez efficacement "si condition a ou < / i> condition b etc. ". Ce que vous voulez vraiment, c'est un et b et C, et de le faire avec la multiplication. Il y a quelques mises en garde (par exemple, vos poids doivent maintenant être des pouvoirs) mais il est bien meilleur que le gâchis que vous essayez de tout. Wiki "modèle de somme pondéré" et "modèle de produit pondéré" pour plus de détails.