Ce sunt algoritmii genetici?

În ultimii câțiva ani, a existat o mare agitație în jurul Inteligenței Artificiale (AI). Companii importante precum Google, Apple și Microsoft lucrează activ la acest subiect. De fapt, IA este o umbrelă care acoperă o mulțime de obiective, abordări, instrumente și aplicații. Algoritmii genetici (GA) sunt doar unul dintre instrumentele de căutare inteligentă prin multe soluții posibile.

GA este o tehnică metaeuristică de căutare și optimizare bazată pe principiile prezente în evoluția naturală. Ea aparține unei clase mai mari de algoritmi evolutivi.

GA menține o populație de cromozomi – un set de soluții potențiale pentru problemă. Ideea este că “evoluția” va găsi o soluție optimă pentru problemă după un număr de generații succesive – similar cu selecția naturală.

GA imită trei procese evolutive: selecție, încrucișare de gene și mutație.

Similar cu selecția naturală, conceptul central al selecției GA este fitness-ul. Cromozomii care sunt mai apți au șanse mai mari de supraviețuire. Fitness-ul este o funcție care măsoară calitatea soluției reprezentate de cromozom. În esență, fiecare cromozom din cadrul populației reprezintă parametrii de intrare. De exemplu, dacă problema dvs. conține doi parametri de intrare, cum ar fi prețul și volumul în tranzacționare, fiecare cromozom va fi format, în mod logic, din două elemente. Modul în care sunt codificate elementele în cadrul cromozomului este un subiect diferit.

În timpul selecției, cromozomii formează perechi de părinți pentru reproducere. Fiecare copil preia caracteristici de la părinții săi. Practic, copilul reprezintă o recombinare a caracteristicilor de la părinții săi: O parte din caracteristici sunt preluate de la un părinte și o parte de la alt părinte. În plus față de recombinare, unele dintre caracteristici pot suferi mutații.

Pentru că cromozomii mai potriviți produc mai mulți copii, fiecare generație următoare va avea o fitness mai bună. La un moment dat, o generație va conține un cromozom care va reprezenta o soluție suficient de bună pentru problema noastră.

GA este puternică și aplicabilă pe scară largă pentru probleme complexe. Există o clasă mare de probleme de optimizare care sunt destul de greu de rezolvat prin tehnici de optimizare convenționale. Algoritmii genetici sunt algoritmi eficienți a căror soluție este aproximativ optimă. Aplicațiile bine-cunoscute includ programarea, transportul, rutarea, tehnologiile de grup, proiectarea layout-ului, antrenarea rețelelor neuronale și multe altele.

Punerea în practică

Exemplul pe care îl vom analiza poate fi considerat “Hello World” al GA. Acest exemplu a fost dat inițial de J. Freeman în Simulating Neural Networks with Mathematica. Eu l-am preluat din Genetic Algorithms and Engineering Design de Mitsuo Gen și Runwei Cheng.

Problema de potrivire a cuvintelor încearcă să facă să evolueze o expresie cu ajutorul unui algoritm genetic. Inițial, algoritmul ar trebui să “ghicească” expresia “a fi sau a nu fi” din liste de litere generate la întâmplare.

Din moment ce există 26 de litere posibile pentru fiecare dintre cele 13 locații din listă, probabilitatea ca noi să obținem expresia corectă într-un mod pur aleator este (1/26)^13=4.03038×10-19, ceea ce reprezintă aproximativ două șanse dintr-o (Gen & Chong, 1997).

Vom defini problema un pic mai larg aici, ceea ce va face ca soluția să fie și mai dificilă. Să presupunem că nu suntem limitați la limba engleză sau la o anumită frază. Putem ajunge să avem de-a face cu orice alfabet, sau chiar cu orice set de simboluri. Nu avem niciun fel de cunoștințe despre limbă. Nici măcar nu știm dacă există vreo limbă.

Să presupunem că adversarul nostru s-a gândit la o frază arbitrară, incluzând spații albe. Cunoaștem lungimea frazei și numărul de simboluri din alfabet. Aceasta este singura cunoaștere pe care o avem. După fiecare ghicire, adversarul nostru ne spune câte litere sunt la locul lor.

Care cromozom este o secvență de indici ai simbolurilor din alfabet. Dacă vorbim despre alfabetul englezesc, atunci “a” va fi reprezentat de 0, “b” de 1, “c” de 2, și așa mai departe. Deci, de exemplu, cuvântul “be” va fi reprezentat prin .

Vom demonstra toți pașii prin fragmente de cod Java, dar nu este necesară cunoașterea Java pentru a înțelege fiecare pas.

Genetic Algorithm Core

Potem începe cu o implementare generală a algoritmului genetic:

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); }}

Acesta este setul simplu de pași din care mai mult sau mai puțin constă fiecare AG. La etapa de inițializare, generăm o populație inițială de fraze. Mărimea populației este determinată de populationSize. Modul în care este generată fraza depinde de implementarea supplier.

În etapa de iterație, facem să evolueze populația până când sunt îndeplinite condițiile de terminare în cadrul testului buclei while. Condițiile de terminare pot include atât numărul de generații, cât și potrivirea exactă a uneia dintre frazele din populație. încapsulează o implementare exactă.

În cadrul fiecărei iterații, efectuăm etapele tipice ale AG:

1. Realizăm o selecție asupra populației pe baza aptitudinii cromozomilor.
2. Produce o nouă “generație” prin intermediul operației de încrucișare.
3. Realizează o recombinare a unor litere din anumite fraze.

Nucleul de bază al algoritmului este foarte simplu și agnostic domeniului. Acesta va fi același pentru toate problemele. Ceea ce va trebui să reglați este implementarea operatorilor genetici. În continuare, vom analiza îndeaproape fiecare dintre operatorii GA menționați anterior.

Selecție

După cum știm deja, selecția este un proces de găsire a succesorilor cromozomilor actuali – cromozomii care sunt mai potriviți pentru problema noastră. În timpul selecției, trebuie să ne asigurăm că cromozomii cu o fitness mai bună au o șansă mai mare de supraviețuire.

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());}

Ideea din spatele acestei implementări este următoarea: Populația este reprezentată ca intervale consecvente pe axa numerică. Întreaga populație este cuprinsă între 0 și 1.

Partea de interval pe care o ia un cromozom este proporțională cu fitness-ul său. Acest lucru are ca rezultat faptul că un cromozom mai apt primește o porțiune mai mare. Apoi tragem cu ochiul la întâmplare la un număr între 0 și 1 și găsim un interval care include numărul respectiv. Evident, intervalele mai mari au șanse mai mari de a fi selectate și, prin urmare, cromozomii mai apți au șanse mai mari de supraviețuire.

Pentru că nu cunoaștem detalii despre funcția de fitness, trebuie să normalizăm valorile de fitness. Funcția de fitness este reprezentată de fitness, care transformă un cromozom într-un dublu arbitrar care reprezintă fitness-ul cromozomului.

În cod, găsim ratele de fitness pentru toți cromozomii din populație și găsim, de asemenea, fitness-ul total. În cadrul buclei for, efectuăm o sumă cumulativă asupra probabilităților scalate în funcție de fitness-ul total. Din punct de vedere matematic, acest lucru ar trebui să aibă ca rezultat faptul că variabila finală are valoarea 1. Din cauza impreciziei virgulei flotante, nu putem garanta acest lucru, așa că o setăm la 1 doar pentru a fi siguri.

În cele din urmă, pentru un număr de ori egal cu numărul de cromozomi de intrare, generăm un număr aleatoriu, găsim un interval care include numărul și apoi selectăm cromozomul corespunzător. După cum se poate observa, același cromozom poate fi selectat de mai multe ori.

Crossover

Acum avem nevoie de cromozomi pentru “împerechere.”

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)); }}

Cu probabilitatea predefinită crossoverProbability, selectăm părinții pentru împerechere. Părinții selectați sunt amestecați, permițând apariția oricăror combinații. Se iau perechi de părinți și se aplică operatorul crossover. Aplicăm operatorul de două ori pentru fiecare pereche, deoarece trebuie să păstrăm aceeași dimensiune a populației. Copiii își înlocuiesc părinții în populație.

Mutație

În cele din urmă, efectuăm recombinarea caracteristicilor.

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))); } }}

Cu o probabilitate predefinită mutationProbability, efectuăm “mutația” pe cromozomi. Mutația în sine este definită de mutation.

Configurarea algoritmului specific problemei

Acum să ne uităm la ce tip de parametri specifici problemei trebuie să furnizăm implementării noastre generice.

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;

Parametrii, respectiv, sunt:

1. Operatorul de încrucișare
2. Probabilitatea de încrucișare
3. Funcția de potrivire
4. Operatorul de mutație
5. Probabilitatea de mutație
6. Dimensiunea populației
7. Furnizorul de cromozomi pentru populația inițială
8. Funcția de terminare

Aceasta este configurația pentru problema noastră:

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()

Operatorul de încrucișare și probabilitatea de încrucișare

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;}

Probabilitatea de încrucișare este 0.25, deci ne așteptăm ca, în medie, 25 % din cromozomi să fie selectați pentru încrucișare. Efectuăm o procedură simplă pentru încrucișarea unei perechi de cromozomi. Generăm un număr aleator n din intervalul , unde length este lungimea unui cromozom. Acum împerechem perechea selectată luând primele n caractere n de pe un cromozom și restul caracterelor de pe al doilea cromozom.

Funcția de potrivire

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

Funcția de potrivire numără pur și simplu numărul de potriviri între fraza țintă și cromozomul dat.

Operatorul de mutație și probabilitatea

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;}

Operația de mutație este efectuată independent pe fiecare cromozom. Probabilitatea de mutație este de 0,05, deci ne așteptăm ca, în medie, cinci procente din populație să fie mutate. Mutația se face prin alegerea unei poziții aleatoare a unei litere și înlocuirea valorii acesteia cu o literă aleatorie din alfabet. Facem acest lucru de două ori pentru fiecare cromozom care a suferit o mutație.

Furnizor

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;}

Furnizorul generează fraze aleatoare luând litere aleatoare din alfabet. Fiecare frază are o lungime constantă predefinită.

Funcția de terminare

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;}

Funcția de terminare numără numărul de apeluri și returnează true dacă există fie o potrivire exactă, fie dacă numărul de generații ajunge la 3.000.

Execuție

Acum suntem gata să testăm algoritmul nostru. Dacă îl executați de mai multe ori, veți observa că nu toate execuțiile sunt reușite. De fiecare dată, numărul de iterații va fi diferit. Acest lucru se datorează naturii probabilistice a algoritmului. Algoritmul are mai multe puncte în care poate fi îmbunătățit. Vă puteți juca cu probabilitățile de încrucișare și mutație.

Diminuarea numărului va duce la o soluție stabilă, dar lentă. Un număr mai mic de cromozomi va fi afectat de operatorii genetici și, prin urmare, vor fi necesare mai multe iterații pentru soluție.

Creșterea numărului va accelera algoritmul, dar va face, de asemenea, ca soluția să fie instabilă. Cromozomii potriviți nu numai că vor fi păstrați, dar vor fi și afectați de operatorii genetici. Prin urmare, ei își vor pierde genele “bune”.

Este important să se găsească un bun echilibru. Creșterea numărului de iterații va oferi algoritmului mai multe oportunități de a găsi o soluție, dar, pe de altă parte, va dura mai mult timp. De asemenea, puteți aplica diferite metode de crossover și mutație. O bună selecție a acestor operatori va îmbunătăți drastic calitatea soluției.

Am acoperit aici doar vârful icebergului. Am luat un exemplu care are doar o singură intrare, iar intrarea poate fi prezentată cu ușurință ca un cromozom. Operatorii genetici sunt clari și simpli.

Este foarte interesant să luăm o problemă din lumea reală și să îi aplicăm algoritmul genetic. Veți descoperi diferite abordări în codificarea datelor reale de intrare, precum și diferite implementări de crossover și mutație.

Dacă o problemă poate fi exprimată printr-un set de parametri pe care trebuie să îi ghicim pentru a optimiza o metrică, putem configura rapid un AG pe care îl putem folosi pentru a o rezolva.

Una dintre cele mai interesante probleme este predarea rețelelor neuronale artificiale. Putem seta ca parametrii optimizabili să fie intensitatea sinapselor, iar metrica de fitness să fie procentul de intrări pentru care rețeaua noastră neuronală a dat răspunsul corect. După aceea, putem sta liniștiți și lăsa rețeaua noastră neuronală să evolueze în soluția ideală pe care o dorim. Sau cel puțin până când obținem ceva suficient de bun, pentru că evoluția necesită timp.