Come si evitano le soluzioni dominanti nella ricottura simulata multiobiettivo?

4

Immagina un gioco di ruolo in cui puoi prendere N oggetti e vuoi massimizzare il danno, la velocità di attacco e l'armatura, dato un insieme di oggetti.

Ho implementato la ricottura simulata in cui una permutazione sostituisce semplicemente un elemento casuale e calcolo l'energia con alcuni calcoli di danno.

Funziona bene per velocità di attacco e danno e tende a trovare oggetti che forniscono entrambi. Ma l'aggiunta di armature non dà mai buoni risultati.

Ho provato una somma ponderata, ma il risultato è sempre N elementi di armatura o N armi.

Questo documento suggerisce di selezionare un funzione di energia casuale o media, ma questo dà risultati molto cattivi non appena utilizzo obiettivi in conflitto.

Ci sono buone funzioni di probabilità per questa attività, o dovrei usare un altro algoritmo?

    
posta Pepijn 16.08.2015 - 10:52
fonte

2 risposte

3

Dici "massimizza il tuo danno, la velocità di attacco e l'armatura". Penso che la risposta alla tua domanda sia definire con precisione cosa significa.

Puoi solo "massimizzare" un singolo valore. Se hai più valori, devi fornire una funzione per trasformarli in questo singolo valore che desideri massimizzare.

Ciò che rende una funzione "buona" per questo è interamente specifica per l'applicazione. Quando dici "funzioni energetiche casuali o medie" dà risultati negativi - cosa rende questi risultati negativi?

Penso che finisci un po 'bloccato se dici di voler "massimizzare" qualcosa e poi dici che vuoi anche escludere alcuni tipi di soluzioni che massimizzano quella cosa. Quindi la chiave è combinare i tuoi valori in un modo che corrisponda effettivamente a quello che vuoi ottenere piuttosto che cercare di predeterminare quali risultati sono validi in primo luogo - se questo ha un senso!?

EDIT: Se hai preso tutti e 3 i valori e li hai normalizzati nell'intervallo [0, 1] e li hai passati in una funzione quadratica (es. 4x - 4x ^ 2) e aggiungi i risultati, riduci il valore di input più alti (cioè 1 mappa su 0), quindi è più probabile che si ottengano soluzioni che combinano gli input attorno a (0,5).

Ma come detto tutto quello che stai facendo qui è scegliere una funzione per produrre un output. Quello che dovresti fare è scegliere la funzione in base al "problema del mondo reale", cioè come gli input relativi della velocità di attacco, dell'armatura ecc. Si comportano nel gioco.

    
risposta data 16.08.2015 - 11:40
fonte
1

Tutti quelli che hanno affermato che la funzione di utilità deve monitorare il vero problema sono corretti. Ecco i miei consigli su come, in particolare, per farlo.

L'utilità delle armi e delle armature in un RPG di tipo D & D è che ti aiutano a vincere battaglie . Quanto utile al margine un'armatura migliore o un'arma migliore dipenderà da cosa stai combattendo: più danni sono inutili se stai già uccidendo un goblin ad ogni colpo, per esempio. Quindi devi trovare una lista ragionevole di incontri e un modo per stimare quanto è buono un kit contro ogni incontro. Questo probabilmente significa calcolare quanto è probabile che tu colpisca quell'avversario, quanto sia probabile che ti colpisca e quanto della salute dell'altro ognuno di voi batterà a ogni colpo. Se colpisci l'80% delle volte per 20 punti di danno e ha 50 punti vita, ti aspetteresti, in media, di avere 2.5 colpi per ucciderlo e 3.125 round per ottenere quei 2.5 colpi.

Il rapporto tra turni attesi per te e uccisioni è atteso da un round in atto per uccidere sei probabilmente un buon euristico da usare in un sistema di combattimento derivato da D & D, e probabilmente puoi capirlo con alcune statistiche di base, ma può fallire in alcune situazioni: in realtà non ti aiuta a fare il 90% di danno invece del 51% se avrai ancora bisogno di due colpi per ucciderlo. Un'alternativa più complessa sarebbe calcolare invece la probabilità di vincere il combattimento. Calcola innanzitutto la probabilità che l'avversario muoia in un colpo, due, tre e così via; quindi quanto è probabile che tu abbia un colpo al primo turno, un colpo al secondo, due colpi al secondo e così via, fino a un numero ragionevole di colpi. Ripeti per i suoi attacchi contro di te, e puoi calcolare le probabilità che ognuno di voi morirà a ogni round.

Per un sistema di combattimento molto più complicato, dove generare un albero di probabilità sarebbe impossibile, potresti dover eseguire alcune simulazioni Monte Carlo di battaglie per ottenere un'accurata ottimizzazione.

L'euristica semplice che vuoi, però, è probabilmente qualcosa del tipo, (YourChanceToHit * YourDPS * YourHealth) / (TheirChanceToHit * TheirDPS * TheirHealth). Ciò cattura l'intuizione che i seguenti sono più o meno equivalenti: colpiscono il doppio più spesso, hanno bisogno della metà dei colpi per ucciderli, vengono colpiti la metà più spesso o sopravvivono il doppio dei colpi.

    
risposta data 30.08.2015 - 04:03
fonte

Leggi altre domande sui tag