Gibt es in der Constraint-Programmierung Modelle, die die Anzahl der Variablenänderungen berücksichtigen?

10

Stellen Sie sich ein CSP-Modell vor, bei dem das Ändern des Werts einer bestimmten Variablen teuer ist. Gibt es Arbeiten, bei denen die Zielfunktion auch die Anzahl der Änderungen des Werts der Variablen während des Suchvorgangs berücksichtigt?

Ein Beispiel: Die Variable, deren Änderung teuer ist, kann von einem anderen Agenten gesteuert werden, und es besteht ein gewisser Aufwand, diesen Agenten in die Änderung der Variablen einzubeziehen. Ein weiteres Beispiel: Die Variable nimmt an einer der Einschränkungen teil, und die Erfüllung dieser Einschränkung beinhaltet das Aufrufen einer teuren Funktion (z. B. eines Simulators), z. B. ist die Einschränkung, und ist eine teure Funktion. zu berechnende Funktion. Daher sind und teuer zu ändernde Variablen.z=f(x,y)fxy

algorithms constraint-programming amit
quelle
1
Die Zielfunktion spricht über die Endwerte des CSP und kennt den Suchprozess nicht. In Standardformulierungen sind die Änderungen solcher Variablen daher nicht dem CSP-Modell ausgesetzt. Einige Löser, wie z. B. Choco, bieten Heuristiken zur Steuerung des Suchprozesses. Einige davon können sogar benutzerdefiniert sein. Vielleicht ist dies der Ort, um die Art und Weise der Suche zu ändern.
Dave Clarke
1
Aber warum sollte die Zielfunktion widerspiegeln, wie teuer es war, eine Lösung zu finden? Sollten Sie Lösungen nicht danach vergleichen, wie nützlich sie im Problembereich sind? Oder ist die Zeit bis zur Lösung Teil des realen Problems?
Raphael
1
Es hört sich so an, als ob Sie sich in der Einstellung einer verteilten Einschränkungszufriedenheit befinden, und es klingt so, als würden Sie nach Heuristiken suchen.
Dave Clarke

Antworten:

4

Es hört sich so an, als ob Sie eine kostensensitive (kostenbewusste, budgetierte) Optimierungstechnik wünschen . Das Minimieren von zwei Werten (z. B. die Lösung Ihres Ziels und die Betriebskosten für und ) ist ein Optimierungsproblem mit mehreren Kriterien , und diese sind in der Regel sehr schwer zu lösen. Ein üblicher Ansatz besteht darin, ein Budget für die maximal zulässigen Kosten anzugeben und dann die Zielfunktion in Bezug auf die minimieren . Diese Formulierung passt als zusätzliche Einschränkung gut in vorhandene Frameworks. Natürlich kann es schwierig sein, die Kostenfunktion und das zulässige Budget so anzugeben, dass Sie aussagekräftige Lösungen erhalten - dies hängt von dem spezifischen Problem ab, das Sie lösen möchten.xycosts(x,y)≤Budget

Nick
quelle