Che cosa sono gli algoritmi genetici?

Negli ultimi anni, c’è stato un grande fermento intorno all’intelligenza artificiale (AI). Grandi aziende come Google, Apple e Microsoft stanno lavorando attivamente sull’argomento. Infatti, l’IA è un ombrello che copre un sacco di obiettivi, approcci, strumenti e applicazioni. Algoritmi genetici (GA) è solo uno degli strumenti per la ricerca intelligente attraverso molte soluzioni possibili.

GA è una tecnica meta-euristica di ricerca e ottimizzazione basata sui principi presenti nell’evoluzione naturale. Appartiene a una classe più ampia di algoritmi evolutivi.

GA mantiene una popolazione di cromosomi, un insieme di potenziali soluzioni per il problema. L’idea è che “l’evoluzione” troverà una soluzione ottimale per il problema dopo un certo numero di generazioni successive – simile alla selezione naturale.

GA imita tre processi evolutivi: selezione, crossover genico e mutazione.

Simile alla selezione naturale, il concetto centrale della selezione GA è la fitness. I cromosomi che sono più in forma hanno una migliore possibilità di sopravvivenza. Il fitness è una funzione che misura la qualità della soluzione rappresentata dal cromosoma. In sostanza, ogni cromosoma all’interno della popolazione rappresenta i parametri di input. Per esempio, se il vostro problema contiene due parametri di input, come il prezzo e il volume nel trading, ogni cromosoma sarà logicamente composto da due elementi. Come gli elementi sono codificati all’interno del cromosoma è un argomento diverso.

Durante la selezione, i cromosomi formano coppie di genitori per la riproduzione. Ogni figlio prende caratteristiche dai suoi genitori. Fondamentalmente, il figlio rappresenta una ricombinazione di caratteristiche dai suoi genitori: Alcune caratteristiche sono prese da un genitore e altre da un altro. Oltre alla ricombinazione, alcune delle caratteristiche possono mutare.

Perché i cromosomi più adatti producono più figli, ogni generazione successiva avrà una migliore fitness. Ad un certo punto, una generazione conterrà un cromosoma che rappresenterà una soluzione abbastanza buona per il nostro problema.

GA è potente e ampiamente applicabile per problemi complessi. C’è una grande classe di problemi di ottimizzazione che sono abbastanza difficili da risolvere con le tecniche di ottimizzazione convenzionali. Gli algoritmi genetici sono algoritmi efficienti la cui soluzione è approssimativamente ottimale. Le applicazioni ben note includono la programmazione, il trasporto, il routing, le tecnologie di gruppo, la progettazione di layout, l’addestramento di reti neurali, e molti altri.

Mettere le cose in pratica

L’esempio che vedremo può essere considerato il “Ciao mondo” di GA. Questo esempio è stato inizialmente dato da J. Freeman in Simulazione di reti neurali con Mathematica. L’ho preso da Genetic Algorithms and Engineering Design di Mitsuo Gen e Runwei Cheng.

Il Word-Matching Problem cerca di far evolvere un’espressione con un algoritmo genetico. Inizialmente, si suppone che l’algoritmo “indovini” la frase “essere o non essere” da liste di lettere generate a caso.

Siccome ci sono 26 lettere possibili per ciascuna delle 13 posizioni della lista, la probabilità di ottenere la frase corretta in modo puramente casuale è (1/26)^13=4.03038×10-19, che è circa due possibilità su un (Gen & Chong, 1997).

Definiremo qui il problema un po’ più ampiamente, rendendo la soluzione ancora più difficile. Supponiamo di non essere limitati alla lingua inglese o a una frase specifica. Possiamo finire per avere a che fare con qualsiasi alfabeto, o anche con qualsiasi insieme di simboli. Non abbiamo alcuna conoscenza della lingua. Non sappiamo nemmeno se esiste una lingua.

Diciamo che il nostro avversario ha pensato a una frase arbitraria, compresi gli spazi bianchi. Conosciamo la lunghezza della frase e il numero di simboli nell’alfabeto. Questa è l’unica conoscenza che abbiamo. Dopo ogni ipotesi, il nostro avversario ci dice quante lettere ci sono.

Ogni cromosoma è una sequenza di indici dei simboli dell’alfabeto. Se stiamo parlando dell’alfabeto inglese, allora “a” sarà rappresentata da 0, “b” da 1, “c” da 2, e così via. Così, per esempio, la parola “be” sarà rappresentata come .

Dimostreremo tutti i passi attraverso frammenti di codice Java, ma la conoscenza di Java non è necessaria per capire ogni passo.

Core dell’algoritmo genetico

Possiamo iniziare con un’implementazione generale dell’algoritmo genetico:

public void find() { // Initialization List<T> population = Stream.generate(supplier) .limit(populationSize) .collect(toList()); // Iteration while (!termination.test(population)) { // Selection population = selection(population); // Crossover crossover(population); // Mutation mutation(population); }}

Questa è la semplice serie di passi che ogni GA più o meno consiste. Nella fase di inizializzazione, generiamo una popolazione iniziale di frasi. La dimensione della popolazione è determinata da populationSize. Il modo in cui la frase viene generata dipende dall’implementazione del supplier.

Nel passo di iterazione, facciamo evolvere la popolazione fino a quando le condizioni di terminazione sono soddisfatte all’interno del test del ciclo while. Le condizioni di terminazione possono includere sia il numero di generazioni che la corrispondenza esatta di una delle frasi nella popolazione. Il termination incapsula un’implementazione esatta.

In ogni iterazione, eseguiamo i tipici passi GA:

1. Effettuiamo una selezione sulla popolazione basata sul fitness del cromosoma.
2. Produrre una nuova “generazione” tramite l’operazione di crossover.
3. Effettuare una ricombinazione di alcune lettere in alcune frasi.

Il nucleo dell’algoritmo è molto semplice e ignaro del dominio. Sarà lo stesso per tutti i problemi. Quello che dovrete mettere a punto è l’implementazione degli operatori genetici. Successivamente, daremo un’occhiata da vicino a ciascuno degli operatori GA precedentemente menzionati.

Selezione

Come già sappiamo, la selezione è un processo di ricerca dei successori dei cromosomi correnti, i cromosomi che sono più adatti al nostro problema. Durante la selezione, dobbiamo assicurarci che i cromosomi con migliore fitness abbiano una migliore possibilità di sopravvivenza.

private List<T> selection(List<T> population) { final double fitnesses = population.stream() .mapToDouble(fitness) .toArray(); final double totalFitness = DoubleStream.of(fitnesses).sum(); double sum = 0; final double probabilities = new double; for (int i = 0; i < fitnesses.length; i++) { sum += fitnesses / totalFitness; probabilities = sum; } probabilities = 1; return range(0, probabilities.length).mapToObj(i -> { int index = binarySearch(probabilities, random()); if (index < 0) { index = -(index + 1); } return population.get(index); }).collect(toList());}

L’idea dietro questa implementazione è la seguente: La popolazione è rappresentata come intervalli conseguenti sull’asse numerico. L’intera popolazione è compresa tra 0 e 1.

La porzione di intervallo che un cromosoma prende è proporzionale al suo fitness. Questo si traduce in un cromosoma più adatto che ottiene una porzione più grande. Quindi sbirciamo a caso un numero tra 0 e 1 e troviamo un intervallo che include il numero. Ovviamente, gli intervalli più grandi hanno maggiori possibilità di essere selezionati, e quindi i cromosomi più adatti hanno una migliore possibilità di sopravvivenza.

Perché non conosciamo i dettagli della funzione di fitness, abbiamo bisogno di normalizzare i valori di fitness. La funzione di fitness è rappresentata da fitness, che converte un cromosoma in un doppio arbitrario che rappresenta il fitness del cromosoma.

Nel codice, troviamo i tassi di fitness per tutti i cromosomi nella popolazione, e troviamo anche il fitness totale. All’interno del ciclo for, eseguiamo una somma cumulativa sulle probabilità scalate per il fitness totale. Matematicamente, questo dovrebbe risultare nella variabile finale che ha il valore di 1. A causa dell’imprecisione della virgola mobile, non possiamo garantirlo, quindi lo impostiamo a 1 solo per essere sicuri.

Infine, per un numero di volte pari al numero di cromosomi in ingresso, generiamo un numero casuale, troviamo un intervallo che include il numero, e poi selezioniamo il cromosoma corrispondente. Come potete notare, lo stesso cromosoma può essere selezionato più volte.

Crossover

Ora abbiamo bisogno dei cromosomi da “allevare”.

private void crossover(List<T> population) { final int indexes = range(0, population.size()) .filter(i-> random() < crossoverProbability) .toArray(); shuffle(Arrays.asList(indexes)); for (int i = 0; i < indexes.length / 2; i++) { final int index1 = indexes; final int index2 = indexes; final T value1 = population.get(index1); final T value2 = population.get(index2); population.set(index1, crossover.apply(value1, value2)); population.set(index2, crossover.apply(value2, value1)); }}

Con la probabilità predefinita crossoverProbability, selezioniamo i genitori per la riproduzione. I genitori selezionati vengono mescolati, permettendo qualsiasi combinazione. Prendiamo coppie di genitori e applichiamo l’operatore crossover. Applichiamo l’operatore due volte per ogni coppia perché abbiamo bisogno di mantenere la dimensione della popolazione uguale. I figli sostituiscono i genitori nella popolazione.

Mutazione

Infine, eseguiamo la ricombinazione delle caratteristiche.

private void mutation(List<T> population) { for (int i = 0; i < population.size(); i++) { if (random() < mutationProbability) { population.set(i, mutation.apply(population.get(i))); } }}

Con probabilità predefinita mutationProbability, eseguiamo la “mutazione” sui cromosomi. La mutazione stessa è definita da mutation.

Configurazione dell’algoritmo specifico del problema

Ora diamo un’occhiata al tipo di parametri specifici del problema che dobbiamo fornire alla nostra implementazione generica.

private BiFunction<T, T, T> crossover;private double crossoverProbability;private ToDoubleFunction<T> fitness;private Function<T, T> mutation;private double mutationProbability;private int populationSize = 100;private Supplier<T> supplier;private Predicate<Collection<T>> termination;

I parametri, rispettivamente, sono:

1. Operatore di crossover
2. Probabilità di crossover
3. Funzione di fitness
4. Operatore di mutazione
5. Probabilità di mutazione
6. Dimensione della popolazione
7. Fornitore di cromosomi per la popolazione iniziale
8. Funzione di terminazione

Ecco la configurazione del nostro problema:

new GeneticAlgorithm<char>() .setCrossover(this::crossover) .setCrossoverProbability(0.25) .setFitness(this::fitness) .setMutation(this::mutation) .setMutationProbability(0.05) .setPopulationSize(100) .setSupplier(() -> supplier(expected.length)) .setTermination(this::termination) .find()

Operatore di crossover e probabilità

private char crossover(char value1, char value2) { final int i = (int) round(random() * value1.length); final char result = new char(value1.length); System.arraycopy(value1, 0, result, 0, i); System.arraycopy(value2, i, result, i, value2.length - i); return result;}

La probabilità di crossover è 0.25, quindi ci aspettiamo che in media il 25% dei cromosomi sia selezionato per il crossover. Eseguiamo una semplice procedura per il crossover di una coppia di cromosomi. Generiamo un numero casuale n dall’intervallo , dove length è la lunghezza di un cromosoma. Ora accoppiamo la coppia selezionata prendendo i primi n caratteri da un cromosoma e i restanti caratteri dal secondo.

Funzione di fitness

private double fitness(char value) { return range(0, value.length) .filter(i -> value == expected) .count();}

La funzione di fitness conta semplicemente il numero di corrispondenze tra la frase obiettivo e il cromosoma dato.

Operatore di mutazione e probabilità

private char mutation(char value) { final char result = Arrays.copyOf(value, value.length); for (int i = 0; i < 2; i++) { int letter = (int) round(random() * (ALPHABET.length - 1)); int location = (int) round(random() * (value.length - 1)); result = ALPHABET; } return result;}

L’operazione di mutazione viene eseguita indipendentemente su ogni cromosoma. La probabilità di mutazione è 0,05, quindi ci aspettiamo che, in media, il cinque per cento della popolazione sia mutato. Mutiamo scegliendo una posizione casuale della lettera e sostituendo il suo valore con una lettera casuale dell’alfabeto. Lo facciamo due volte per ogni cromosoma mutato.

Fornitore

private char supplier(int length) { final char result = new char(length); for (int i = 0; i < length; i++) { int letter = (int) round(random() * (ALPHABET.length - 1)); result = ALPHABET; } return result;}

Il fornitore genera frasi casuali prendendo lettere a caso dall’alfabeto. Ogni frase ha una lunghezza costante predefinita.

Funzione di terminazione

private boolean termination(Collection<char> chars) { count++; final Optional<char> result = chars.stream() .filter(value -> round(fitness(value)) == expected.length) .findAny(); if (result.isPresent()) { System.out.println("Count: " + count); System.out.println(result.get()); return true; } final boolean terminated = count == 3000; if (terminated) { chars.forEach(System.out::println); } return terminated;}

La funzione di terminazione conta il numero di chiamate e restituisce true se c’è una corrispondenza esatta, o se il conteggio della generazione raggiunge 3.000.

Esecuzione

Ora siamo pronti per testare il nostro algoritmo. Se lo eseguite diverse volte, noterete che non tutte le esecuzioni hanno successo. Ogni volta, il numero di iterazioni sarà diverso. Questo è dovuto alla natura probabilistica dell’algoritmo. L’algoritmo ha diversi punti in cui può essere migliorato. Puoi giocare con le probabilità di crossover e di mutazione.

Basso il numero porterà ad una soluzione stabile ma lenta. Un numero minore di cromosomi sarà influenzato dagli operatori genetici e, quindi, saranno necessarie più iterazioni per la soluzione.

Aumentare il numero accelererà l’algoritmo, ma renderà anche la soluzione instabile. I cromosomi adatti non solo saranno conservati, ma saranno anche influenzati dagli operatori genetici. Pertanto, perderanno i loro geni “buoni”.

È importante trovare un buon equilibrio. Aumentare il numero di iterazioni darà all’algoritmo più opportunità di trovare una soluzione ma, d’altra parte, richiederà più tempo. È anche possibile applicare diversi metodi di crossover e mutazione. Una buona selezione di questi operatori migliorerà drasticamente la qualità della soluzione.

Abbiamo coperto solo la punta dell’iceberg. Abbiamo preso un esempio che ha un solo input, e l’input può essere facilmente presentato come un cromosoma. Gli operatori genetici sono chiari e semplici.

È molto interessante prendere un problema del mondo reale e applicarvi l’algoritmo genetico. Scoprirete diversi approcci nella codifica dei dati di input reali così come diverse implementazioni di crossover e mutazione.

Se un problema può essere espresso attraverso un insieme di parametri che dobbiamo indovinare per ottimizzare una metrica, possiamo impostare rapidamente un GA che possiamo usare per risolverlo.

Uno dei problemi più interessanti è l’insegnamento delle reti neurali artificiali. Possiamo impostare i parametri ottimizzabili come la forza delle sinapsi, e la metrica di fitness come la percentuale di input per i quali la nostra rete neurale ha dato la risposta giusta. Dopo di che, possiamo sederci e lasciare che la nostra rete neurale si evolva nella soluzione ideale che desideriamo. O almeno finché non otteniamo qualcosa di abbastanza buono, perché l’evoluzione richiede tempo.