Jak zaprojektować funkcję prawdopodobieństwa akceptacji dla symulowanego wyżarzania z wieloma różnymi kosztami?

ja używamsymulowanego wyżarzania rozwiązać problem kompletnego planowania zasobów NP. Dla każdego kandydata zamawiającego zadania obliczam kilka różnych kosztów (lub wartości energii). Oto kilka przykładów (choć szczegóły są prawdopodobnie nieistotne dla pytania):

global_finish_time: Łączna liczba dni, przez które harmonogram obejmuje.split_cost: Liczba dni, o które każde zadanie jest opóźnione z powodu przerw w innych zadaniach (ma to na celu zniechęcenie do przerwania zadania po jego uruchomieniu).deadline_cost: Suma kwadratowej liczby dni, o którą każdy nieudany termin jest zaległy.

Tradycyjna funkcja prawdopodobieństwa akceptacji wygląda następująco (w Pythonie):

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)

Do tej pory połączyłem moje dwa pierwsze koszty w jeden, dodając je po prostu, aby móc wprowadzić wynikacceptance_probability. Ale tym, czego naprawdę chciałbym, jestdeadline_cost zawsze mieć pierwszeństwo przedglobal_finish_time, i dlaglobal_finish_time mieć pierwszeństwo przedsplit_cost.

Moje pytanie do Stack Overflow brzmi: jak zaprojektować funkcję prawdopodobieństwa akceptacji, która uwzględnia wiele energii, ale zawsze uważa, że ​​pierwsza energia jest ważniejsza niż druga energia, i tak dalej? Innymi słowy, chciałbym przekazaćold_cost inew_cost jako krotki kilku kosztów i zwracają rozsądną wartość.

Edytować: Po kilku dniach eksperymentowania z proponowanymi rozwiązaniami doszedłem do wniosku, że jedynym sposobem, który działa dla mnie wystarczająco dobrze, jest sugestia Mike'a Dunlavey'a, chociaż stwarza to wiele innych trudności z komponentami kosztowymi, które mają różne jednostki. Jestem praktycznie zmuszony do porównywania jabłek z pomarańczami.

Dlatego wkładam trochę wysiłku w „normalizację” wartości. Pierwszy,deadline_cost jest sumą kwadratów, więc rośnie wykładniczo, podczas gdy inne składniki rosną liniowo. Aby rozwiązać ten problem, używam pierwiastka kwadratowego, aby uzyskać podobną szybkość wzrostu. Po drugie, opracowałem funkcję, która oblicza liniową kombinację kosztów, ale automatycznie dostosowuje współczynniki zgodnie z najwyższą widoczną dotąd składową kosztów.

Na przykład, jeśli krotka najwyższych kosztów to (A, B, C), a wektor kosztów wejściowych to (x, y, z), kombinacją liniową jest BCx + Cy + z. W ten sposób, bez względu na to, jak wysokie będzie z, nigdy nie będzie ważniejsze niż wartość x równa 1.

Stwarza to „utratę” funkcji kosztu, ponieważ odkrywa się nowe maksymalne koszty. Na przykład, jeśli C pójdzie w górę, BCx i Cy będą wyższe zarówno dla danych wejściowych (x, y, z), jak i różnic między kosztami. Większa różnica w kosztach oznacza, że ​​prawdopodobieństwo akceptacji spadnie, tak jakby temperatura została nagle obniżona o dodatkowy krok. W praktyce nie stanowi to problemu, ponieważ maksymalne koszty są aktualizowane tylko kilka razy na początku i nie zmieniają się później. Uważam, że można nawet teoretycznie udowodnić, że osiągnie on poprawny wynik, ponieważ wiemy, że koszt zbiegnie się w kierunku niższej wartości.

Jedną z rzeczy, która wciąż mnie trochę myli, jest to, co się dzieje, gdy maksymalne koszty wynoszą 1,0 i mniej, powiedzmy 0,5. Przy maksymalnym wektorze (0,5, 0,5, 0,5) daje to kombinację liniową 0,5 * 0,5 * x + 0,5 * y + z, tj. Kolejność pierwszeństwa zostaje nagle odwrócona. Przypuszczam, że najlepszym sposobem radzenia sobie z tym jest użycie wektora maksymalnego do skalowania wszystkich wartości do podanych zakresów, tak aby współczynniki zawsze mogły być takie same (powiedzmy 100x + 10y + z). Ale jeszcze tego nie próbowałem.

questionAnswers(4)

yourAnswerToTheQuestion