Gli algoritmi genetici sono adatti a problemi come il problema di Knuth?
Sappiamo tutti che gli algoritmi genetici possono fornire una soluzione ottimale o quasi ottimale. Quindi, in alcuni problemi come quelli NP-hard, con un compromesso tra tempo e soluzione ottimale, la soluzione quasi ottimale è abbastanza buona.
Poiché non vi è alcuna garanzia di trovare la soluzione ottimale, GA è considerata una buona scelta per risolvere il problema di Knuth?
Secondo Artificial intelligence: A modern approach (terza edizione), sezione 3.2 (p. 73):
Knuth ipotizzò che, a partire dal numero 4, una sequenza di operazioni fattoriali, radice quadrata e floor raggiungerà qualsiasi numero intero positivo desiderato.
Ad esempio, 5 può essere raggiunto da 4:
piano (sqrt (sqrt (sqrt (sqrt (sqrt ((4!)!))))))
Quindi, se abbiamo un numero (5) e vogliamo conoscere la sequenza delle operazioni dei 3 citati per raggiungere il numero dato, ogni gene del cromosoma sarà un numero che rappresenta una certa operazione con un numero aggiuntivo per (nessuna operazione) e la funzione fitness sarà la differenza assoluta tra il numero dato e il numero che otteniamo applicando le operazioni in un certo ordine per ciascun cromosoma (al min). Consideriamo che il numero delle iterazioni (generazioni) è fatto senza una soluzione ottimale e il numero più vicino che abbiamo è 4 (con fitness 1), il problema è che possiamo ottenere 4 non applicando nessuna operazione su 4 mentre per 5 abbiamo bisogno molte operazioni, quindi la soluzione quasi ottimale non è nemmeno vicina alla soluzione.
Quindi, GA non è adatto a questo tipo di problemi? O la rappresentazione cromosomica suggerita e la funzione fitness non sono abbastanza buone?
Risposte
Prima di provare a rispondere alla tua domanda in modo più diretto, permettimi di chiarire una cosa.
Le persone spesso usano il termine algoritmi genetici (GA), ma, in molti casi, ciò che realmente intendono è algoritmi evolutivi (EA), che è una raccolta di algoritmi di ottimizzazione basati sulla popolazione (cioè più soluzioni sono mantenute allo stesso tempo) e approcci ispirati al darwinismo e alla sopravvivenza del più adatto . GAs è uno di questi approcci, in cui i cromosomi sono binari e hai sia la mutazione che l'operazione di cross-over. Esistono altri approcci, come strategie evolutive o programmazione genetica .
Come hai anche notato, gli EA sono meta-euristici e, sebbene ci siano alcune ricerche sulle loro proprietà di convergenza [ 1 ], in pratica potrebbero non convergere. Tuttavia, quando qualsiasi altro potenziale approccio ha fallito, gli EA possono essere decisamente utili.
Nel tuo caso, il problema è davvero trovare un'espressione in forma chiusa (o analitica ) di una funzione, che è composta da altre funzioni più piccole. Questo è davvero ciò per cui è stata creata la programmazione genetica (in particolare, GP basata sugli alberi). In effetti, il problema di Knuth è un caso particolare del problema della regressione simbolica , che è un problema tipico a cui viene applicato GP. Quindi, GP è probabilmente il primo approccio che dovresti provare.
Nel frattempo, ho implementato un semplice programma in DEAP che cerca di risolvere il problema di Knuth. Controlla qui . L'idoneità della migliore soluzione che ha trovato finora (con un po 'di seed) è 4 e la soluzione è floor(sqrt(float(sqrt(4))))(qui floatconverte solo l'input in un numero in virgola mobile, per garantire la sicurezza del tipo). Ho usato la differenza come funzione fitness e ho eseguito l'algoritmo GP per 100 generazioni con 100 individui per ogni generazione (che non è molto!). Non ho modificato molto gli iperparametri, quindi, forse, con il seme e gli iperparametri giusti, puoi trovare la soluzione giusta.
Per rispondere alle tue preoccupazioni, in linea di principio, potresti usare quella codifica, ma, come noti, l'AG potrebbe effettivamente tornare $4$ come la migliore soluzione (che in realtà non è così lontana da $5$), che potresti evitare che uccida, ad ogni generazione, qualsiasi individuo che abbia proprio quel valore.
Non ho trascorso molto tempo sulla mia implementazione e pensando a questo problema, ma, come ho detto sopra, anche con la programmazione genetica e utilizzando solo le operazioni di Knuth, potrebbe rimanere bloccato negli ottimali locali. Potresti provare ad aumentare la mia (o la tua) implementazione con altre operazioni, come la moltiplicazione e l'addizione, e vedere se qualcosa migliora.