Qual è il panorama del fitness per soluzioni minimali + vitali?

1

Diciamo che sto cercando di trovare un numero compreso tra 1 e 100. Tutti i numeri in questo intervallo sono "validi", in quanto potrebbero essere interpretati come potenziali soluzioni. Diciamo che il numero ideale è 50. E tutti i numeri > = 50 sono "fattibili" in quanto risolvono effettivamente il problema. E tutti i numeri < 50 sono "non fattibili" (ma ancora validi). Come si codifica uno scenario come questo con una funzione di fitness (assumendo che il paesaggio sia simile ma più complesso di questo esempio inventato)? Dai "bonus" a soluzioni valide? Misurate fino a che punto è rimasta una soluzione impossibile prima di diventare ottimale? E penalizzi le soluzioni eccessive?

if (solution < 50) {
  maximalFitness = f(solution)
} else if (solution >= 50) {
  maximalFitness = 1_000 - f(solution)
}

La curva non sarebbe continua se tutte le soluzioni fattibili fossero strettamente migliori di tutte le soluzioni irrealizzabili, pur avendo una distanza simile dall'ottimale.

    
posta Mark Canlas 05.02.2013 - 17:58
fonte

1 risposta

5

Ciò a cui ti riferisci si chiama "ottimizzazione vincolata". Questo è un ramo del calcolo evolutivo molto ben studiato, e puoi trovare decine di risorse che descrivono tecniche comuni per risolvere questi problemi. Carlos Coello-Coello fa un tutorial sull'argomento ogni anno alla GECCO, la principale conferenza della CE sul campo. Ho trovato le diapositive di una di queste sessioni disponibili qui ( ftp://ftp.cs.bham.ac.uk/.snapshot/nightly.1/pub/authors/WBLangdon/biblio/gecco2008/docs/p2445.pdf ). Potresti trovare un utile punto di partenza per ulteriori studi.

In breve, ci sono due approcci di alto livello che sono di gran lunga i più comuni: penalizzazione e riparazione. In caso di penalizzazione, si riduce l'idoneità delle soluzioni in base a quanto gravemente violano i vincoli. In riparazione, si modificano effettivamente le soluzioni non attuabili direttamente per tentare di spostarle nella regione ammissibile.

La penalizzazione funziona bene se è possibile ottenere lo schema di penalità giusto, ma questo può essere un problema difficile da risolvere ed è essenzialmente sempre dipendente dal problema. Un'opzione è quella di gironzolare con la tua funzione di fitness e calcolare la giusta quantità da penalizzare in modo che le "buone" soluzioni irrealizzabili ottengano abbastanza fitness da non morire immediatamente ma non tanto da essere preferite rispetto a soluzioni fattibili. Un altro metodo è quello di sostituire semplicemente i criteri di selezione per rendere conto direttamente delle soluzioni non ammissibili. Cioè, invece di

if fitness(p1) > fitness(p2):
    # p1 is better
else:
    # p2 is better

hai qualcosa come

if (is_feasible(p1) and is_feasible(p2)) or (not is_feasible(p1) and not is_feasible(p2)):
    if fitness(p1) > fitness(p2):
        # p1 is better
    else:
        # p2 is better
else:
    if is_feasible(p1):
        # p1 is better
    else:
        # p2 is better

Questo esplicitamente gestisce tutti i modi di confrontare soluzioni fattibili e non fattibili e usa i loro valori di fitness solo per rompere i legami. Ora non importa tanto se il valore di fitness crudo di una soluzione irrealizzabile è superiore a una soluzione fattibile a causa di stranezze nel tuo schema di penalizzazione.

La riparazione è spesso preferibile se puoi farlo (non è sempre possibile costruire un operatore di riparazione efficace). Con la riparazione, intendiamo che prendi la soluzione irrealizzabile e la modifichi effettivamente in modo che rientri nella tua regione possibile. Questo potrebbe essere semplice come limitazione del valore all'interno dell'intervallo consentito, ma più spesso richiederà una sorta di ricerca specifica o euristica specifica per dominio. Ad esempio, se si ha un problema con lo zaino e una soluzione ha troppo peso nello zaino, un operatore di riparazione potrebbe iniziare a lanciare casualmente degli oggetti dallo zaino finché il peso totale non fosse inferiore alla capacità. Un operatore migliore potrebbe pregiudicare la rimozione di articoli verso quelli con il più alto rapporto peso / valore. Di solito è utile per la riparazione avere un po 'di casualità - potresti voler influenzare leggermente le cose, ma non vuoi fare sempre una riparazione avida.

Ci sono anche altri approcci. Una recente innovazione è stata quella di trattare ogni vincolo come una funzione obiettivo separata e utilizzare algoritmi di ottimizzazione multi-obiettivo per trovare una gamma di soluzioni trade-off. Per alcuni problemi, questo ha dimostrato di essere efficace, ma penso che la regola generale dovrebbe probabilmente essere quella di vedere prima cosa si può fare con i metodi più semplici come la penalizzazione e la riparazione.

    
risposta data 05.02.2013 - 23:28
fonte

Leggi altre domande sui tag