È necessario un algoritmo genetico quando il calcolo è infinitamente veloce?

Gli algoritmi genetici sono fondamentalmente una metodologia guidata per tentativi ed errori. L'unico vantaggio che mi viene in mente per un GA su una ricerca esauriente è che, dal momento che GA ottimizza una funzione di fitness in fasi, potrebbe ottenere una soluzione ottimale più velocemente, perché l'AG favorirà soluzioni che sono incrementali meglio. Una ricerca esaustiva che è garantita per trovare una soluzione potrebbe fare il giro del mondo.

• Se "risorse di calcolo" significa CPU ma non memoria, il pool di geni GA potrebbe avere un minore ingombro di memoria, richiedendo meno memoria.

• D'altra parte, a causa dell'arrampicata in salita, un GA potrebbe rimanere bloccato su un massimo locale e amp; eventuali mutazioni potrebbero non essere sufficienti per scuoterlo.

• Inoltre, il tempo di ricerca per GA aumenta in modo esponenziale con la dimensione dell'input, quindi una ricerca esaustiva potrebbe risultare più veloce dopo tutto, a seconda delle dimensioni dello spazio che stai cercando e se è possibile vincola la dimensione dello spazio escludendo le possibilità.

...

Ultimamente ho pensato alle GA in termini di "entropia al secondo" e misurando il progresso della mia GA come misura di quante diverse possibilità percorre al secondo. Quindi posso confrontarlo con l'entropia totale dello spazio del problema. Se una ricerca di forza bruta può battere quella entropia al secondo con parallelizzazione o processori veloci, allora il "miglior punteggio" di un GA non è migliore di un "miglior punteggio" scoperto.

Ma ho appena smanettato; Non ho ancora strumentalizzato un GA in quel modo ancora.

(Entropia è ln(N) per N possibili stati, o ln(N) - sum(n * ln(n) for all n) / N dove n è il modo possibile per ottenere un risultato da N possibili risultati.)

Domanda interessante:)

Sì, se il calcolo fosse libero, non avresti assolutamente bisogno di algoritmi genetici. Ma ricorda che questo è un enorme "se" che nessuno di noi vivrà mai per vedere!

Tuttavia, dal momento che stai chiedendo ... se il calcolo fosse infinitamente veloce, non ci sarebbe alcuna ragione per non applicare il più semplice martello combinatore di forza-e-test combinatorio a un problema. Ogni domanda a cui è possibile rispondere con un insieme finito di informazioni (vale a dire un problema di soddisfazione dei vincoli nel senso più libero possibile di quel termine, che è abbastanza in effetti incoerente) sarebbe immediatamente risolvibile; alpinismo, euristica e tutte le intelligenti semplificazioni che ora usiamo per costruire, ad es. un motore di scacchi di livello mondiale semplicemente non sarebbe necessario.

In altre parole, se il calcolo si avvicina alla velocità infinita, la decisione sull'approccio da utilizzare si fonda su quanto sia difficile scrivere il programma da eseguire, non quanto tempo ci vuole per eseguire effettivamente ; e ciò significa che semplicemente non vale la pena inventare un algoritmo più complicato quando il più semplice possibile funzionerà e funzionerà nello stesso tempo.

Probabilmente, il calcolo si è effettivamente spostato in questa direzione, ma ancora una volta, ricorda, che non siamo ancora arrivati, e probabilmente non lo saremo mai. (A meno che il computer quantistico non sia perfezionato, ovviamente.)

Il problema con calcoli infinitamente veloci è che coprono infinitamente velocemente uno spazio di stato che è più grande del limite di informazione del nostro universo conosciuto. Hai menzionato la "forza bruta", tuttavia considera che gli scacchi forzanti brutali, per esempio, possono produrre un output che supera in dimensione il numero di atomi nell'universo.

Prendendo ulteriormente l'esempio degli scacchi, come bruto gioco di scacchi, devi ridimensionare il numero di combinazioni di scacchi che consideri e dovrai prendere una decisione che dichiara di mantenere e quali stati scartare, quindi in effetti algoritmi selettivi, come gli algoritmi genetici, saranno sempre necessari.

Se con "risorse di calcolo illimitate" intendi che il tuo algoritmo impiegherebbe 0 volte e che la memoria è illimitata e l'elettricità non è un problema, direi che l'unico algoritmo da usare sarebbe un algoritmo di forza bruta che cerca ogni possibile input ed è garantito per trovare il migliore. Se ti riferisci a una memoria illimitata ma a una possibile differenza nel tempo richiesto, allora un algoritmo genetico potrebbe essere preferibile perché potrebbe arrivare a una soluzione più veloce di un algoritmo a forza bruta. Ma la soluzione dell'algoritmo genetico potrebbe non essere ottimale, quindi a seconda del contesto e delle tue esigenze potresti ancora preferire il metodo della forza bruta.

Dato che non sono possibili risorse di calcolo illimitate, all'inizio la domanda sembrava una speculazione inattiva. Ma man mano che acquisiamo sempre più potere computazionale, la questione diventa più rilevante perché non abbiamo bisogno di algoritmi genetici in un'epoca di enormi supercomputer. Tuttavia, ho notato che anche se i computer diventano più potenti, continuiamo a chiedere loro di fare calcoli sempre più difficili con sempre più dati. Quindi, alla fine, penso che gli algoritmi genetici saranno con noi per il prossimo futuro e saranno utilizzati anche quando sarà disponibile molta potenza di calcolo.

Tuttavia, se fossero disponibili risorse di calcolo veramente illimitate, cambierebbe molto di più che usare o meno gli algoritmi genetici.