Come progettare la funzione di probabilità di accettazione per la ricottura simulata con costi distinti multipli?

Question

Sto utilizzando simulated annealing per risolvere un problema di pianificazione delle risorse NP-complete. Per ogni candidato che ordina i compiti, computo diversi costi (o valori energetici) diversi. Alcuni esempi sono (anche se le specifiche sono probabilmente irrilevante per la questione):

• global_finish_time: Il numero totale di giorni in cui le campate di pianificazione.
• split_cost: il numero di giorni entro i quali ogni attività viene ritardata a causa di interruzioni da parte di altre attività (questo è inteso a scoraggiare l'interruzione di un'attività dopo l'avvio).
• deadline_cost: la somma del numero quadrato di giorni entro cui ogni scadenza mancata è scaduta.

La funzione di probabilità di accettazione tradizionali assomiglia a questo (in 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) 

Finora ho combinato i miei primi due costi in un unico semplicemente aggiungendoli, in modo che possa alimentare il risultato in acceptance_probability. Ma quello che vorrei davvero è che per deadline_cost abbia sempre la precedenza su global_finish_time e che per global_finish_time abbia la precedenza su split_cost.

Quindi la mia domanda su Stack Overflow è: come posso progettare una funzione di probabilità di accettazione che tenga conto di più energie ma considera sempre la prima energia più importante della seconda energia, e così via? In altre parole, vorrei passare in old_cost e new_cost come tuple di diversi costi e restituire un valore ragionevole.

Edit: Dopo alcuni giorni di sperimentazione con le soluzioni proposte ho concluso che l'unico modo che funziona abbastanza bene per me è il suggerimento di Mike Dunlavey, anche se questo crea molte altre difficoltà con componenti di costo che hanno diverse unità . Sono praticamente costretto a confrontare le mele con le arance.

Quindi, ho messo un po 'di sforzo per "normalizzare" i valori. Innanzitutto, deadline_cost è una somma di quadrati, quindi cresce in modo esponenziale mentre gli altri componenti crescono in modo lineare. Per risolvere questo problema, utilizzo la radice quadrata per ottenere un tasso di crescita simile. In secondo luogo, ho sviluppato una funzione che calcola una combinazione lineare dei costi, ma regola automaticamente i coefficienti in base alla componente di costo più elevata vista finora.

Ad esempio, se la tupla dei costi più elevati è (A, B, C) e il vettore del costo di input è (x, y, z), la combinazione lineare è BCx + Cy + z. In questo modo, non importa quanto alto z lo ottiene non sarà mai più importante di un valore x di 1.

Questo crea "frastagliature" nella funzione di costo quando vengono scoperti nuovi costi massimi. Ad esempio, se C sale, allora BCx e Cy saranno entrambi più alti per un dato input (x, y, z) e quindi anche le differenze tra i costi. Una maggiore differenza di costo significa che la probabilità di accettazione diminuirà, come se la temperatura fosse improvvisamente abbassata di un ulteriore passo. In pratica però questo non è un problema perché i costi massimi vengono aggiornati solo poche volte all'inizio e non cambiano in seguito. Credo che si possa persino teoricamente dimostrare che convergere in un risultato corretto poiché sappiamo che il costo convergerà verso un valore inferiore.

Una cosa che mi ha ancora un po 'confuso è cosa succede quando i costi massimi sono 1.0 e inferiori, diciamo 0.5. Con un vettore massimo di (0,5, 0,5, 0,5) questo darebbe la combinazione lineare 0,5 * 0,5 * x + 0,5 * y + z, vale a dire.l'ordine di precedenza è improvvisamente invertito. Suppongo che il modo migliore per affrontarlo sia utilizzare il vettore massimo per ridimensionare tutti i valori su intervalli dati, in modo che i coefficienti possano essere sempre gli stessi (ad esempio, 100x + 10y + z). Ma non l'ho ancora provato.

Answer 1

mbeckish è giusto.

Potresti creare una combinazione lineare delle diverse energie e regolare i coefficienti?

Possibilmente log-trasformandoli dentro e fuori?

Ho eseguito alcuni MCMC utilizzando Metropolis-Hastings. In quel caso sto definendo la verosimiglianza (non normalizzata) di un particolare stato (dati i suoi priori), e trovo che un modo per chiarire il mio pensiero su ciò che voglio.

Answer 2

Dipende da cosa intendi per "ha la precedenza". Ad esempio, cosa succede se lo deadline_cost scende di 0,001, ma il costo di global_finish_time aumenta di 10000? Restituisci 1.0, perché il deadline_cost è diminuito e ciò ha la precedenza su qualsiasi altra cosa? Sembra che sia un giudizio che solo tu puoi fare, a meno che tu non sia in grado di fornire sufficienti informazioni di base sul progetto in modo che altri possano suggerire la propria chiamata di giudizio.

Answer 3

vorrei prendere in considerazione qualcosa sulla falsariga di:

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) 

Naturalmente ciascuno dei tre luoghi che calcolare la probabilità potrebbe utilizzare una funzione diversa.

Answer 4

vorrei prendere un suggerimento da multi-obiettivo algoritmo evolutivo (MOEA) e lo hanno transizione se tutte degli obiettivi passano contemporaneamente la funzione acceptance_probability hai dato. Ciò avrà l'effetto di esplorare il fronte di Pareto in modo molto simile a come gli standard di ricottura simulata esplorano altipiani di soluzioni a energia simile.

Tuttavia, questo rinuncia all'idea di avere la prima priorità.

Probabilmente sarà necessario modificare i parametri, ad esempio aumentando la temperatura iniziale.