La definizione del punto di arresto di un algoritmo genetico vanifica lo scopo dell'algoritmo?

La funzione fitness valuta l' output del tuo algoritmo. È abbastanza possibile riconoscere un output ideale quando lo vedi, ma non conoscere i passaggi per produrre quell'output da un dato input. Ecco dove gli algoritmi genetici sono più utili.

Ad esempio, una comune applicazione divertente di GA sta producendo un'animazione in grado di spostare una creatura virtuale in modo efficiente. È facile capire se la creatura si muove a una certa velocità in una linea relativamente diritta. Questa è la tua funzione di fitness. È molto più difficile dire l'esatta sequenza di movimenti "muscolari" per farlo.

Spesso è possibile determinare l'idoneità di una soluzione ma non determinare direttamente la soluzione. Supponiamo che tu stia cercando di evolvere conigli veloci e ci sono una manciata di geni che influiscono sulla velocità del coniglio. Puoi testare la velocità del coniglio, ma enumerare tutte le combinazioni di geni relativi alla velocità sarebbe poco pratico. In tal caso, potresti avere un GA che corre con i conigli e alleva quelli più veloci. Potresti farlo per sempre, ma probabilmente preferiresti smettere quando:

• hai trovato un coniglio più veloce di X o
• il miglioramento incrementale su n generazioni è sceso al di sotto di qualche soglia, o
• hai allevato conigli attraverso le generazioni

L'intero punto dell'AG è quello di darti la soluzione al problema che ha quel livello di forma fisica. Questa soluzione sarebbe molto difficile da trovare utilizzando altri algoritmi di ricerca più convenzionali, che di solito è il motivo per cui si sta utilizzando un GA in primo luogo.

Oppure invece di un limite di valore di fitness, puoi decidere quante generazioni vuoi eseguire (più generazioni corri, maggiori possibilità hai di trovare valori di fitness sempre più alti). Ad esempio, nel problema del commesso viaggiatore, ottenere un percorso che abbia il costo più basso tra le città da attraversare.

Se la condizione di arresto è un certo livello di forma fisica che è accettabile o un determinato vincolo di tempo (l'esecuzione dell'AG per un periodo di tempo massimo o un numero limitato di generazioni per applicazioni critiche come pathfinder o applicazioni AI) viene determinata di solito dal tuo dominio del problema.

Intuitivamente, lo scopo di un algoritmo genetico è di formulare una soluzione algoritmica a un problema che non si presta a un'analisi logica semplice. Una volta raggiunto l'obiettivo, l'AG non deve proseguire oltre.

Ovviamente, se si desidera una "forma fisica" migliore, l'algoritmo genetico può essere lasciato in esecuzione per vedere se può trovare una soluzione più ottimizzata, o l'algoritmo genetico può essere modificato per vedere se convergerà su una migliore soluzione.

Un algoritmo genetico richiede un modo per premiare i buoni geni con una maggiore propagazione. Se non avessi modo di distinguere i geni buoni dai geni cattivi, non potresti assolutamente usare un algoritmo genetico.

Affinché un algoritmo genetico funzioni, è necessario consentire alle soluzioni più idonee di riprodursi preferibilmente rispetto alle soluzioni meno adatte. Altrimenti, staresti provando solo soluzioni casuali.

Ecco un esempio tipico della mia esperienza: sviluppando uno dei primi sistemi di composizione vocale, abbiamo avuto difficoltà a trovare un algoritmo per abbinare un nome parlato a una copia memorizzata con lo stesso nome. Ci è stato detto che era sufficiente l'accuratezza del 95% scegliendo un nome su 25. Avevamo un gruppo di persone memorizzate che dicevano 25 nomi 10 volte ciascuno.

In primo luogo, abbiamo sviluppato un sistema di input che misurava la lunghezza della parola parlata e l'energia di frequenza in diversi blocchi normalizzati di essa. Poi abbiamo sviluppato un algoritmo che assegnava pesi alle partite su quei parametri e confrontava due serie di parametri attraverso quei pesi.

Ora, abbiamo avuto un ultimo passaggio: quale dovrebbe essere il valore di tali pesi?

Abbiamo creato 1.000 set di pesi casuali e li abbiamo testati contro il corpus. Abbiamo buttato via la 500 che ha fatto il peggio. Per i restanti 500, abbiamo duplicato ciascuno e in uno di essi, alzato o abbassato in modo casuale uno dei pesi.

Abbiamo ripetuto questo processo su un computer per circa due settimane fino a quando alla fine ha avuto un set di pesi che ha soddisfatto il criterio di accuratezza del 95%. Quindi lo abbiamo testato su dati non nel corpus. Era accurato al 92% circa. Quindi abbiamo eseguito più tempo per ottenere una precisione del 98% sul corpus e quell'insieme di pesi ha prodotto un'accuratezza del 95% sui dati non nel corpus.

Quindi, il punto è che devi avere una funzione di fitness per eseguire un algoritmo genetico. Se non hai modo di distinguere i geni buoni dai geni cattivi, come puoi assicurarti che i geni buoni si riproducano e i geni cattivi no?

Iterare finché una soluzione non differisce molto dall'interazione precedente. Per molto, per favore comprendi una tolleranza fissa.

Solution in iteration n-6: 600
Solution in iteration n-5: 800
Solution in iteration n-4: 768
Solution in iteration n-3: 780 
Solution in iteration n-2: 778
Solution in iteration n-1: 778.23
Solution in iteration n: 780.18
Solution in iteration n+1: 780.1815

In questo esempio, se la tua tolleranza fissa era 0.01 allora (n + 1) ti dice di fermarti perché abs (soluzione (n + 1) -soluzione (n)) < 0,01.

Riprendendo, è quando il tuo algoritmo può dire: questo non migliorerà!

Per una rapida risposta alla tua domanda principale: C'è una grande differenza tra sapere cosa vuoi ottenere e sapere come arrivarci.

Più in dettaglio, ad esempio, con uno dei problemi più comuni risolti utilizzando algoritmi genetici / evolutivi, di solito un caso di studio in classe, trovando la via ottimale in un grafico. Questo è spesso usato in rete per trovare il percorso più economico da un'estremità all'altra. Definendo i costi (# di luppolo, costo di ogni salto, ecc ...) si definisce anche il costo target (livello di forma fisica) al quale si è soddisfatti del risultato. Il tuo algoritmo potrebbe non trovare il migliore, ma troverà un ottimo algoritmicamente accettabile. Con questo intendo che il rapporto costi / benefici di trovare una risposta migliore è proibire.

Con GA / EA scoprirai che è normale che trovi rapidamente una risposta ottimale del 95% +, ma restringere l'ultimo 5% è esponenzialmente più costoso. Quindi la teoria è che tu definisca un ottimo accettabile per ottenere il miglior risultato nel minor tempo possibile. Poiché il costo del rilevamento, ad esempio l'1% superiore, potrebbe superare i suoi benefici rispetto al 5% più alto, definisci il tuo valore accettabile.

Per riassumere, non si è ora la risposta a un problema particolare, si definisce solo, per problema, il proprio optimum accettabile, il punto in cui trovare una risposta migliore non è pratico.

Esistono alcune ricerche su che risolvono i bug in C con gli algoritmi genetici fornendo valori negativi e positivi casi di test come funzioni di fitness, insieme a codice spezzato come input. Questo è un esempio di un problema che potrebbe essere risolto da un umano, ma è più facile da fare per un algoritmo genetico. È importante notare:

Although the methods described in this paper do not evolve new programs from scratch, they do show how to evolve legacy software to repair existing faults.

Tuttavia, i nuovi programmi hanno si sono evoluti da zero - non solo in C. I pochi programmi non banali scritti in Malbolge linguaggio di programmazione esoterico hanno tutti (a mia conoscenza) sono stati evoluti, non scritti. Il linguaggio è troppo complesso per un programmatore da utilizzare e troppo complesso per dedurre in modo efficiente i programmi dalla sola logica, quindi la maggior parte dei programmi scritti in essa sono stati prodotti da algoritmi genetici. La funzione fitness è generalmente la distanza di modifica per l'uscita prevista.

Questo è graziosamente circolare, in un certo senso. Osservando che il codice genetico complesso è scritto da processi evolutivi, possiamo simulare processi evolutivi per produrre codice in un linguaggio diverso e complesso, senza nemmeno sapere come funziona il codice!