Algoritmi genetici: căutare și optimizare prin selecție naturală

Ce sunt algoritmii genetici?

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

GA este o tehnică de căutare și optimizare metaeuristică bazată pe principii prezente în evoluția naturală. 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ția, încrucișarea genelor și mutația.

Similar cu selecția naturală, conceptul central al selecției GA este fitness. Cromozomii care sunt mai potriviți au șanse mai mari de supraviețuire. Fitness este o funcție care măsoară calitatea soluției reprezentate de cromozom. În esență, fiecare cromozom din populație 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 consta în mod logic din două elemente. Modul în care elementele sunt codificate în cromozom 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ți. Practic, copilul reprezintă o recombinare de caracteristici de la părinții săi: Unele dintre caracteristici sunt preluate de la un părinte și altele de la altul. Pe lângă recombinare, unele dintre caracteristici pot suferi mutații .

Deoarece cromozomii mai în formă produc mai mulți copii, fiecare generație ulterioară va avea o formă 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 tehnicile convenționale de optimizare. Algoritmii genetici sunt algoritmi eficienți a căror soluție este aproximativ optimă. Aplicațiile binecunoscute includ programarea, transportul, rutarea, tehnologiile de grup, designul de layout, antrenamentul rețelei neuronale și multe altele.

Punerea lucrurilor în practică

Exemplul pe care îl vom analiza poate fi considerat „Hello World” a GA. Acest exemplu a fost dat inițial de J. Freeman în Simularea rețelelor neuronale cu Mathematica . L-am luat de la Algoritmi genetici și design de inginerie de la Mitsuo Gen și Runwei Cheng.

Problema potrivirii cuvintelor încearcă să evolueze o expresie cu un algoritm genetic. Inițial, algoritmul ar trebui să „ghicească” expresia „a fi sau a nu fi” din listele de litere generate aleatoriu.

Deoarece există 26 de litere posibile pentru fiecare dintre cele 13 locații [excluzând spațiile albe] din listă, probabilitatea de a obține expresia corectă într-un mod pur aleatoriu este (1/26)^13=4,03038×10-19, care este de aproximativ două șanse dintr-un [quintilion] (Gen & Chong, 1997).

Vom defini problema un pic mai pe larg aici, făcând soluția și mai dificilă. Să presupunem că nu ne limităm la limba engleză sau la o anumită expresie. Putem ajunge să avem de-a face cu orice alfabet, sau chiar cu orice set de simboluri. Nu avem cunoștințe de limbă. Nici măcar nu știm dacă există vreo limbă.

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

Fiecare cromozom este o succesiune de indici ai simbolurilor din alfabet. Dacă vorbim despre alfabetul englez, atunci „a” va fi reprezentat cu 0, „b” cu 1, „c” cu 2 și așa mai departe. Deci, de exemplu, cuvântul „fi” va fi reprezentat ca [4, 1] .

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

Nucleul algoritmului genetic

Putem î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 constă mai mult sau mai puțin fiecare GA. La pasul 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ă expresia depinde de implementarea supplier .

În pasul de iterație, evoluăm populația până când condițiile de terminare sunt îndeplinite în testul 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. termination încapsulează o implementare exactă.

În cadrul fiecărei iterații, efectuăm pașii tipici GA:

1. Efectuați o selecție asupra populației pe baza aptitudinii cromozomilor.
2. Produceți o nouă „generație” prin operațiunea crossover.
3. Efectuați o recombinare a unor litere în unele fraze.

Miezul algoritmului este foarte simplu și independent de domeniu. Va fi la fel pentru toate problemele. Ceea ce va trebui să reglați este implementarea operatorilor genetici. În continuare, vom arunca o privire atentă la 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 potriviti pentru problema noastră. În timpul selecției, trebuie să ne asigurăm că cromozomii cu o fitness mai bună au șanse mai mari 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[fitnesses.length]; for (int i = 0; i < fitnesses.length; i++) { sum += fitnesses[i] / totalFitness; probabilities[i] = sum; } probabilities[probabilities.length - 1] = 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 consecutive pe axa numerică. Întreaga populație este între 0 și 1.

Porțiunea din intervalul pe care o ia un cromozom este proporțională cu fitness-ul său. Acest lucru are ca rezultat un cromozom mai potrivit care primește o bucată mai mare. Apoi aruncăm o privire la un număr între 0 și 1 și găsim un interval care include numărul. Evident, intervalele mai mari au șanse mai mari de a fi selectate și, prin urmare, cromozomii mai în formă 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 rate de fitness pentru toți cromozomii din populație și găsim, de asemenea, fitnessul total. În cadrul buclei for , efectuăm o sumă cumulativă asupra probabilităților reduse de fitness total. Din punct de vedere matematic, aceasta ar trebui să rezulte ca variabila finală să aibă valoarea 1. Din cauza impreciziei virgulei mobile, nu putem garanta asta, așa că o setăm la 1 doar pentru a fi sigur.

În cele din urmă, de 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 puteți observa, același cromozom poate fi selectat de mai multe ori.

Crossover

Acum avem nevoie de cromozomi pentru a se „înmulți”.

 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[2 * i]; final int index2 = indexes[2 * i + 1]; 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 crossoverProbability predefinită, selectăm părinții pentru reproducere. Părinții selectați sunt amestecați, permițând orice combinații să aibă loc. Luăm perechi de părinți și aplicăm operatorul crossover . Aplicăm operatorul de două ori pentru fiecare pereche deoarece trebuie să păstrăm aceeași dimensiunea 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ă de mutationProbability , efectuăm „mutație” asupra cromozomilor. Mutația în sine este definită de mutation .

Configurare algoritm specifică problemei

Acum să aruncăm o privire 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. Operator crossover
2. Probabilitatea de încrucișare
3. Funcția fitness
4. Operator de mutație
5. Probabilitatea mutației
6. Dimensiunea populației
7. Furnizor de cromozomi pentru populația inițială
8. Funcția de terminare

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

Operator de încrucișare și probabilitate

 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 de 0,25, așa că ne așteptăm ca în medie 25% dintre 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 [0..length] , unde length este lungimea unui cromozom. Acum împerechem perechea selectată luând primele n caractere dintr-un cromozom și caracterele rămase după de la al doilea.

Funcția de fitness

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

Funcția de fitness numără pur și simplu numărul de potriviri dintre fraza țintă și cromozomul dat.

Operator de mutație și probabilitate

 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[location] = ALPHABET[letter]; } return result; }

Operația de mutație se realizează independent pe fiecare cromozom. Probabilitatea de mutație este de 0,05, așa că ne așteptăm ca, în medie, cinci la sută din populație să fie mutată. Mutăm prin alegerea unei poziții aleatorii a unei litere și înlocuirea valorii acesteia cu o literă aleatorie din alfabet. O facem de două ori pentru fiecare cromozom mutant.

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[i] = ALPHABET[letter]; } return result; }

Furnizorul generează fraze aleatorii luând litere aleatorii 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ă ne testăm algoritmul. Dacă îl rulați de mai multe ori, veți observa că nu toate rulările au succes. 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. Puteți juca cu probabilități de încrucișare și mutație.

Scăderea 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 numerelor va accelera algoritmul, dar va face și soluția instabilă. Cromozomii potriviți nu vor fi doar păstrați, ci vor fi și afectați de operatorii genetici. Prin urmare, își vor pierde genele „bune”.

Este important să găsiți un echilibru bun. 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 încrucișare și mutație. O selecție bună a acestor operatori va îmbunătăți drastic calitatea soluției.

Ce urmează?

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

Este foarte interesant să luăm o problemă din lumea reală și să-i aplici algoritmul genetic. Veți descoperi diferite abordări în codificarea datelor de intrare reale, 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 GA pe care îl putem folosi pentru a o rezolva.

Una dintre cele mai interesante probleme este predarea rețelelor neuronale artificiale. Putem seta parametrii optimizabili să fie puterile 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 pe loc și lăsăm rețeaua noastră neuronală să evolueze în soluția ideală pe care o dorim. Sau cel puțin până obținem ceva suficient de bun, pentru că evoluția necesită timp.