Algoritmi evolutivi: cos'è e perché sono necessari

Sommario:

Algoritmi evolutivi: cos'è e perché sono necessari
Algoritmi evolutivi: cos'è e perché sono necessari
Anonim

Nel campo dell'intelligenza artificiale, un algoritmo evolutivo (EA) è un sottoinsieme dei calcoli della popolazione totale basati sull'ottimizzazione metaeuristica. EA utilizza meccanismi ispirati allo sviluppo biologico come riproduzione, mutazione, ricombinazione e selezione. La soluzione candidata al problema degli algoritmi di ottimizzazione evolutiva gioca il ruolo degli individui nella popolazione. E anche la funzione fitness determina la qualità delle risposte.

Gli algoritmi evolutivi spesso approssimano bene le soluzioni a tutti i tipi di problemi. Perché idealmente non fanno ipotesi sul panorama del fitness sottostante. I metodi utilizzati per la modellazione evolutiva e gli algoritmi genetici sono generalmente limitati allo studio dei processi microevolutivi e ai modelli di pianificazione basati su stadi cellulari. Nella maggior parte delle applicazioni EA reali, la complessità computazionale è un fattore proibitivo.

In re altàquesto problema è correlato alla stima della funzione fitness. L'approssimazione della forma fisica è una soluzione per superare questa difficoltà. Tuttavia, un EA apparentemente semplice può risolvere problemi spesso complessi. Pertanto, non può esserci una relazione diretta tra la complessità della sequenza e il problema. Maggiori dettagli possono essere trovati nei libri "Algoritmi evolutivi".

Attuazione

modelli evolutivi e algoritmi
modelli evolutivi e algoritmi

Il primo passo consiste nel creare una popolazione iniziale di individui a caso.

Il secondo passo consiste nel valutare l'idoneità di ogni individuo in questo gruppo (limite di tempo, preparazione sufficiente, ecc.).

Fase tre: ripeti i seguenti passaggi di rigenerazione fino al completamento:

  1. Seleziona le persone più adatte all'allevamento (genitori).
  2. Porta nuovi individui che hanno superato l'algoritmo evolutivo usando il crossover e la mutazione per ottenere una prole.
  3. Valutare la forma fisica individuale delle nuove persone.
  4. Sostituisci con loro la popolazione meno in forma.

Tipi

L'algoritmo genetico è una sequenza evolutiva, il tipo più popolare di Expert Advisor. Si cerca una soluzione al problema sotto forma di stringhe di numeri (tradizionalmente binari, anche se le migliori rappresentazioni sono solitamente quelle che riflettono maggiormente il problema da risolvere) applicando operatori come ricombinazione e mutazione (a volte uno, in alcuni casi entrambi). Questo tipo di Expert Advisor viene spesso utilizzato nei problemi di ottimizzazione. Un altro nome per questo è fetura (dal latino "nascita"):

  1. Programmazione genetica. Presenta soluzioni come codici informatici e la loro idoneità è determinata dalla loro capacità di eseguire compiti di calcolo.
  2. Programmazione evolutiva. Simile all'algoritmo genetico evolutivo, ma la struttura è fissa e i suoi parametri numerici possono cambiare.
  3. Programmazione dell'espressione genica. Sviluppa applicazioni per computer, ma esplora il sistema genotipo-fenotipo, dove progetti di diverse dimensioni sono codificati su cromosomi lineari a lunghezza fissa.
  4. Strategia. Funziona con vettori di numeri reali come rappresentazioni di soluzioni. Di solito utilizza algoritmi di tasso di mutazione evolutiva autoadattativi.
  5. Sviluppo differenziale. Basato su differenze vettoriali e quindi adatto principalmente a problemi di ottimizzazione numerica.
  6. Neuroevoluzione. Simile alla programmazione evolutiva e agli algoritmi genetici. Ma queste ultime sono reti neurali artificiali, che descrivono la struttura e il peso delle connessioni. La codifica del genoma può essere diretta o indiretta.

Confronto con i processi biologici

Una possibile limitazione di molti algoritmi evolutivi è la mancanza di una chiara distinzione tra genotipo e fenotipo. In natura, un ovulo fecondato subisce un complesso processo noto come embriogenesi per diventare maturo. Si pensa che questa codifica indiretta renda le ricerche genetiche più affidabili (cioè, meno propensi a causare mutazioni fatali) e possa anche migliorare la capacità dell'organismo di svilupparsi. Tale indiretto (in altre parole,codifiche generative o di sviluppo) consentono anche all'evoluzione di sfruttare la regolarità nell'ambiente.

Il lavoro recente sull'embriogenesi artificiale o sui sistemi di sviluppo cerca di affrontare questi problemi. Durante la programmazione dell'espressione genica, viene esplorata con successo la regione genotipo-fenotipo, dove il primo è costituito da cromosomi multigene lineari di lunghezza fissa e il secondo da molti alberi di espressione o programmi per computer di varie dimensioni e forme.

Tecniche correlate

algoritmi evolutivi
algoritmi evolutivi

Gli algoritmi includono:

  1. Ottimizzazione della colonia di formiche. Si basa sull'idea che gli insetti cercano il cibo collegandosi con i feromoni per formare percorsi. Adatto principalmente per l'ottimizzazione combinatoria e problemi di grafi.
  2. Algoritmo di scorrimento della radice. Il creatore è stato ispirato dalla funzione delle radici delle piante in natura.
  3. Algoritmo per colonie di api artificiali. Basato sul comportamento delle api mellifere. Viene proposto principalmente per l'ottimizzazione numerica ed esteso alla risoluzione di problemi combinatori, limitati e multiobiettivo. L'algoritmo delle api si basa sul comportamento di foraggiamento degli insetti. È stato applicato in molte applicazioni come il routing e la pianificazione.
  4. Ottimizzazione dello sciame di particelle - basata su idee sul comportamento della mandria di animali. E anche principalmente adatto per attività di processo numerico.

Altri metodi metaeuristici popolari

  1. Ricerca di caccia. Un metodo basato sulla cattura di gruppo di alcuni animali, come i lupi, ad esempio, chedistribuire i loro doveri per circondare la preda. Ciascuno dei membri dell'algoritmo evolutivo si relaziona in qualche modo agli altri. Questo è particolarmente vero per il leader. Questo è un metodo di ottimizzazione continua adattato come metodo di processo combinatorio.
  2. Cerca per misure. A differenza dei metodi metaeuristici basati sulla natura, l'algoritmo del processo adattivo non utilizza la metafora come principio principale. Piuttosto, utilizza un semplice metodo orientato alle prestazioni basato sull'aggiornamento del parametro del rapporto dimensione di ricerca ad ogni iterazione. L'algoritmo Firefly si ispira al modo in cui le lucciole si attraggono con la loro luce lampeggiante. Ciò è particolarmente utile per l'ottimizzazione multimodale.
  3. Cerca l'armonia. Basato sulle idee del comportamento dei musicisti. In questo caso, gli algoritmi evolutivi sono la strada da percorrere per l'ottimizzazione combinatoria.
  4. Adattamento gaussiano. Basato sulla teoria dell'informazione. Utilizzato per massimizzare le prestazioni e la disponibilità media. Un esempio di algoritmi evolutivi in questa situazione: entropia in termodinamica e teoria dell'informazione.

Memetico

modellazione evolutiva
modellazione evolutiva

Un metodo ibrido basato sull'idea di un meme di Richard Dawkins. Di solito assume la forma di un algoritmo basato sulla popolazione combinato con procedure di apprendimento individuali in grado di eseguire perfezionamenti locali. Enfatizza l'uso della conoscenza specifica del problema e tenta di organizzare ricerche globali e a grana fine in modo sinergico.

Evolutivogli algoritmi sono un approccio euristico a problemi che non possono essere risolti facilmente in tempo polinomiale, come i problemi NP-hard classici e qualsiasi altra cosa che richiederebbe troppo tempo per essere elaborata in modo esaustivo. Se usati in modo indipendente, sono solitamente usati per problemi combinatori. Tuttavia, gli algoritmi genetici sono spesso usati in tandem con altri metodi, agendo come un modo rapido per trovare più punti di partenza ottimali con cui lavorare.

La premessa dell'algoritmo evolutivo (noto come consigliere) è abbastanza semplice dato che hai familiarità con il processo di selezione naturale. Contiene quattro passaggi principali:

  • inizializzazione;
  • scelta;
  • operatori genetici;
  • fine.

Ognuno di questi passaggi corrisponde grosso modo a un certo aspetto della selezione naturale e fornisce modi semplici per modularizzare quella categoria di algoritmi. In poche parole, in EA, i membri più in forma sopravviveranno e si riprodurranno, mentre i membri inadatti moriranno e non contribuiranno al pool genetico della prossima generazione.

Inizializzazione

Per avviare l'algoritmo, devi prima creare un insieme di soluzioni. La popolazione conterrà un numero arbitrario di possibili affermazioni di problemi, spesso indicate come membri. Sono spesso generati casualmente (entro i vincoli del compito) o, se si conosce qualche conoscenza precedente, provvisoriamente centrati su ciò che è considerato ideale. È importante che la popolazione copra un'ampia gamma di soluzioni,perché è essenzialmente un pool genetico. Pertanto, se si vogliono esplorare molte diverse possibilità all'interno di un algoritmo, si dovrebbe sforzarsi di avere molti geni diversi.

Scelta

codici genetici
codici genetici

Una volta creata la popolazione, i suoi membri devono ora essere valutati in base alla funzione fitness. La funzione fitness prende le caratteristiche di un membro e fornisce una rappresentazione numerica di quanto sia in forma il membro. Crearli può essere spesso molto difficile. È importante trovare un buon sistema che rappresenti accuratamente i dati. Questo è molto specifico per il problema. Ora è necessario calcolare l'idoneità di tutti i partecipanti e selezionare alcuni dei migliori membri.

Funzioni obiettivo multiple

Gli EA possono anche essere estesi per utilizzare questi sistemi. Ciò complica in qualche modo il processo, perché invece di identificare un punto ottimale, quando li si utilizza si ottiene un insieme. L'insieme delle soluzioni è chiamato frontiera di Pareto e contiene elementi ugualmente adatti, nel senso che nessuno di essi domina su nessun altro.

Operatori genetici

Questo passaggio include due passaggi secondari: crossover e mutazione. Dopo aver selezionato i termini migliori (di solito i primi 2, ma questo numero può variare), vengono ora utilizzati per creare la generazione successiva nell'algoritmo. Applicando le caratteristiche dei genitori scelti, si creano nuovi figli che sono un misto di qualità. Questo può essere spesso difficile a seconda del tipo di dati, ma di solito in problemi combinatoriè del tutto possibile mescolare e produrre combinazioni valide.

Ora è necessario introdurre nuovo materiale genetico nella generazione. Se questo importante passo non viene compiuto, lo scienziato si bloccherà molto rapidamente negli estremi locali e non otterrà risultati ottimali. Questo passaggio è una mutazione, e viene fatto semplicemente, cambiando una piccola parte dei bambini in modo tale che non riflettano prevalentemente sottoinsiemi dei geni dei genitori. La mutazione di solito avviene in modo probabilistico, poiché la probabilità che un bambino la ottenga, così come la sua gravità, è determinata dalla distribuzione.

Risoluzione

modellazione e algoritmi
modellazione e algoritmi

Alla fine, l'algoritmo deve finire. Questo di solito accade in due casi: o ha raggiunto un tempo massimo di esecuzione o ha raggiunto una soglia di prestazioni. A questo punto, viene selezionata e restituita la soluzione finale.

Esempio di algoritmi evolutivi

Ora, per illustrare il risultato di questo processo, devi vedere il consulente in azione. Per fare questo, possiamo ricordare come diverse generazioni di dinosauri abbiano imparato a camminare (gradualmente padroneggiando la terra), ottimizzando la struttura del loro corpo e applicando la forza muscolare. Anche se i rettili della prima generazione non potevano camminare, il consigliere è stato in grado di evolverli nel tempo attraverso mutazioni e incroci in una forma che potesse camminare.

Questi algoritmi stanno diventando sempre più rilevanti nel mondo moderno, poiché le soluzioni basate su di essi sono sempre più utilizzate in settori come il marketing digitale, la finanza eassistenza sanitaria.

Dove vengono utilizzati gli EA?

Più in generale, gli algoritmi evolutivi vengono utilizzati in un'ampia varietà di applicazioni come l'elaborazione di immagini, il routing dei veicoli, l'ottimizzazione delle comunicazioni mobili, lo sviluppo di software e persino l'addestramento di reti neurali artificiali. Questi strumenti sono al centro di molte delle app e dei siti Web che le persone utilizzano quotidianamente, tra cui Google Maps e persino giochi come The Sims. Inoltre, il campo medico utilizza l'EA per aiutare a prendere decisioni cliniche relative al trattamento del cancro. In effetti, gli algoritmi evolutivi sono così robusti che possono essere utilizzati per risolvere quasi tutti i problemi di ottimizzazione.

Legge di Moore

La crescente prevalenza di EO è determinata da due fattori principali: la potenza di calcolo disponibile e l'accumulo di grandi set di dati. Il primo può essere descritto dalla legge di Moore, che afferma essenzialmente che la quantità di potenza di calcolo in un computer raddoppia circa ogni due anni. Questa previsione dura da decenni. Il secondo fattore riguarda la crescente dipendenza dalla tecnologia, che consente alle istituzioni di raccogliere una quantità incredibilmente grande di dati, che consente loro di analizzare le tendenze e ottimizzare i prodotti.

In che modo gli algoritmi evolutivi possono aiutare i marketer?

modellazione genetica
modellazione genetica

Le condizioni di mercato stanno cambiando rapidamente e sono molto competitive. Ciò ha costretto i responsabili del marketing a competere per un migliore processo decisionale. Aumento della disponibilitàla potenza di calcolo ha portato i lavoratori a utilizzare EA per la risoluzione dei problemi.

Ottimizzazione delle conversioni

modellistica e algoritmi genetici
modellistica e algoritmi genetici

Uno degli obiettivi principali è aumentare il tasso di visitatori del sito. Questo problema si riduce all'ottimizzazione del numero di utenti che fanno ciò che vuole il marketer. Ad esempio, se un'azienda vende laptop, l'ideale è aumentare il numero di visitatori del sito che finiscono per acquistare il prodotto. Questa è l'essenza dell'ottimizzazione del tasso di conversione.

Uno degli aspetti sorprendentemente importanti è la scelta dell'interfaccia utente. Se il web design non è molto user friendly, c'è chi finisce per non acquistare il prodotto per un motivo o per l' altro. L'obiettivo è quindi ridurre il numero di utenti che finiscono per non convertire, il che aumenta il profitto complessivo.

Consigliato: