Hvad er genetiske algoritmer?

I løbet af de sidste par år har der været en fantastisk summen omkring kunstig intelligens (AI). Store virksomheder som Google, Apple og Microsoft arbejder aktivt med emnet. Faktisk er AI en paraply, der dækker over mange mål, tilgange, værktøjer og applikationer. Genetiske algoritmer (GA) er blot et af værktøjerne til intelligent søgning gennem mange mulige løsninger.

GA er en metaheuristisk søge- og optimeringsteknik baseret på de principper, der findes i den naturlige evolution. Den hører til en større klasse af evolutionære algoritmer.

GA vedligeholder en population af kromosomer – et sæt af potentielle løsninger til problemet. Ideen er, at “evolutionen” vil finde en optimal løsning for problemet efter et antal på hinanden følgende generationer – svarende til naturlig selektion.

GA efterligner tre evolutionære processer: selektion, gen-crossover og mutation.

Som i naturlig selektion er det centrale begreb i GA-selektion fitness. De kromosomer, der er bedst egnet, har en bedre chance for at overleve. Fitness er en funktion, der måler kvaliteten af den løsning, der repræsenteres af kromosomet. I det væsentlige repræsenterer hvert kromosom i populationen de indgående parametre. Hvis dit problem f.eks. indeholder to inputparametre, f.eks. pris og volumen i handel, vil hvert kromosom logisk set bestå af to elementer. Hvordan elementerne er kodet i kromosomet er et andet emne.

Under udvælgelsen danner kromosomer par af forældrepar til avl. Hvert barn tager egenskaber fra sine forældre. Dybest set repræsenterer barnet en rekombination af egenskaber fra dets forældre: Nogle af egenskaberne er taget fra den ene forælder og nogle fra den anden. Ud over rekombinationen kan nogle af egenskaberne mutere.

Da federe kromosomer producerer flere børn, vil hver efterfølgende generation have en bedre fitness. På et tidspunkt vil en generation indeholde et kromosom, der vil repræsentere en tilstrækkelig god løsning for vores problem.

GA er kraftfuld og bredt anvendelig til komplekse problemer. Der findes en stor klasse af optimeringsproblemer, som er ret svære at løse med konventionelle optimeringsteknikker. Genetiske algoritmer er effektive algoritmer, hvis løsning er omtrent optimal. De velkendte anvendelser omfatter planlægning, transport, ruteføring, gruppeteknologier, layoutdesign, træning af neurale netværk og mange andre.

Ting i praksis

Det eksempel, vi skal se på, kan betragtes som GA’s “Hello World”. Dette eksempel blev oprindeligt givet af J. Freeman i Simulating Neural Networks with Mathematica (Simulering af neurale netværk med Mathematica). Jeg har taget det fra Genetic Algorithms and Engineering Design af Mitsuo Gen og Runwei Cheng.

Det ordmatchende problem forsøger at udvikle et udtryk med en genetisk algoritme. I første omgang skal algoritmen “gætte” udtrykket “to be or not to be” ud fra tilfældigt genererede lister af bogstaver.

Da der er 26 mulige bogstaver for hver af de 13 placeringer på listen, er sandsynligheden for, at vi får det korrekte udtryk på en rent tilfældig måde, (1/26)^13=4.03038×10-19, hvilket er ca. to chancer ud af en (Gen & Chong, 1997).

Vi vil definere problemet lidt bredere her, hvilket gør løsningen endnu vanskeligere. Lad os antage, at vi ikke er begrænset til det engelske sprog eller en bestemt sætning. Vi kan ende med at have med et hvilket som helst alfabet eller endog et hvilket som helst sæt af symboler at gøre. Vi har intet kendskab til sproget. Vi ved ikke engang, om der overhovedet er noget sprog.

Lad os sige, at vores modstander har tænkt på en vilkårlig sætning, herunder whitespace. Vi kender længden af sætningen og antallet af symboler i alfabetet. Det er den eneste viden, vi har. Efter hvert gæt fortæller vores modstander os, hvor mange bogstaver der er på plads.

Hvert kromosom er en sekvens af indekser for symbolerne i alfabetet. Hvis vi taler om det engelske alfabet, vil “a” være repræsenteret ved 0, “b” ved 1, “c” ved 2 osv. Så for eksempel vil ordet “be” blive repræsenteret som .

Vi vil demonstrere alle trin gennem Java-kodesnipsler, men kendskab til Java er ikke påkrævet for at forstå hvert enkelt trin.

Genetisk algoritmes kerne

Vi kan starte med en generel implementering af den genetiske algoritme:

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

Dette er det simple sæt trin, som enhver GA mere eller mindre består af. Ved initialiseringstrinnet genererer vi en indledende population af sætninger. Størrelsen af populationen bestemmes af populationSize. Hvordan sætningen genereres, afhænger af implementeringen af supplier.

I iterationstrinnet udvikler vi populationen, indtil afslutningsbetingelserne er opfyldt inden for while-loopens test. Afslutningsbetingelserne kan omfatte både antallet af generationer og den nøjagtige matchning af en af sætningerne i populationen. termination indkapsler en nøjagtig implementering.

I hver iteration udfører vi de typiske GA-trin:

1. Udfører en udvælgelse over populationen baseret på kromosomernes egnethed.
2. Producerer en ny “generation” via crossover-operationen.
3. Udfører en rekombination af nogle bogstaver i nogle sætninger.

Kernen i algoritmen er meget enkel og domæne-agnostisk. Den vil være den samme for alle problemer. Det, du skal indstille, er implementeringen af genetiske operatører. Herefter vil vi se nærmere på hver af de GA-operatorer, der tidligere er nævnt.

Selektion

Som vi allerede ved, er selektion en proces, der går ud på at finde efterfølgere til de aktuelle kromosomer – de kromosomer, der passer bedre til vores problem. Under udvælgelsen skal vi sikre, at kromosomer med bedre fitness har en bedre chance for at overleve.

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

Den idé, der ligger bag denne implementering, er følgende: Populationen er repræsenteret som konsekutive intervaller på den numeriske akse. Hele populationen ligger mellem 0 og 1.

Den del af intervallet, som et kromosom tager, er proportional med dets fitness. Dette resulterer i, at et bedre kromosom får en større del af området. Derefter kigger vi tilfældigt på et tal mellem 0 og 1 og finder et område, der omfatter tallet. Det er klart, at større intervaller har større chancer for at blive udvalgt, og derfor har federe kromosomer en bedre chance for at overleve.

Da vi ikke kender detaljerne om fitnessfunktionen, er vi nødt til at normalisere fitnessværdierne. Fitnessfunktionen er repræsenteret ved fitness, som omdanner et kromosom til en vilkårlig dobbeltværdi, der repræsenterer kromosomets fitness.

I koden finder vi fitnessværdierne for alle kromosomer i populationen, og vi finder også den samlede fitness. Inden for for-loopet udfører vi en kumulativ sum over sandsynligheder nedskaleret med den samlede fitness. Matematisk set bør dette resultere i, at den endelige variabel har værdien 1. På grund af upræcisionen ved flydende komma kan vi ikke garantere dette, så vi sætter den til 1 for at være sikre.

Sidst genererer vi for et antal gange svarende til antallet af indgangskromosomer et tilfældigt tal, finder et område, der omfatter tallet, og vælger derefter det tilsvarende kromosom. Som du måske bemærker, kan det samme kromosom vælges flere gange.

Crossover

Nu skal vi til kromosomerne til at “avle.”

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

Med den foruddefinerede sandsynlighed crossoverProbability vælger vi forældre til avl. De udvalgte forældre blandes, så alle kombinationer kan forekomme. Vi tager par af forældrepar og anvender operatoren crossover. Vi anvender operatoren to gange for hvert par, fordi vi er nødt til at holde populationens størrelse ens. Børnene erstatter deres forældre i populationen.

Mutation

Sidst udfører vi rekombination af egenskaberne.

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

Med en foruddefineret sandsynlighed mutationProbability udfører vi “mutation” på kromosomerne. Selve mutationen er defineret af mutation.

Problemspecifik algoritmekonfiguration

Nu skal vi se på, hvilken type problemspecifikke parametre vi skal give vores generiske implementering.

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;

Parametrene er henholdsvis:

1. Krydsningsoperatør
2. Krydsningssandsynlighed
3. Fitness-funktion
4. Mutationsoperatør
5. Mutationssandsynlighed
6. Størrelse af populationen
7. Kromosomleverandør for den oprindelige population
8. Termineringsfunktion

Her er konfigurationen for vores problem:

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

Crossover-operator og sandsynlighed

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

Sandsynligheden for crossover er 0.25, så vi forventer, at i gennemsnit 25 procent af kromosomerne vil blive udvalgt til crossover. Vi udfører en simpel procedure for crossover af et par kromosomer. Vi genererer et tilfældigt tal n fra intervallet , hvor length er længden af et kromosom. Nu parrer vi det valgte par ved at tage de første n tegn fra det ene kromosom og de resterende tegn efter fra det andet kromosom.

Fitnessfunktion

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

Fitnessfunktionen tæller simpelthen antallet af match mellem målfrasen og det givne kromosom.

Mutationsoperatør og sandsynlighed

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

Mutationsoperationen udføres uafhængigt af hinanden på hvert kromosom. Sandsynligheden for mutation er 0,05, så vi forventer, at der i gennemsnit vil blive muteret fem procent af populationen. Vi muterer ved at vælge en tilfældig bogstavposition og erstatte dens værdi med et tilfældigt bogstav fra alfabetet. Vi gør det to gange for hvert muteret kromosom.

Leverandør

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

Leverandøren genererer tilfældige sætninger ved at tage tilfældige bogstaver fra alfabetet. Hver sætning har en konstant foruddefineret længde.

Afslutningsfunktion

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

Afslutningsfunktionen tæller antallet af opkald og returnerer true, hvis der enten er et nøjagtigt match, eller hvis genereringstallet når op på 3.000.

Udførelse

Nu er vi klar til at teste vores algoritme. Hvis du kører den flere gange, vil du bemærke, at det ikke er alle kørsler, der lykkes. Hver gang vil antallet af iterationer være forskelligt. Det skyldes algoritmens probabilistiske karakter. Algoritmen har flere punkter, hvor den kan forbedres. Du kan lege med crossover- og mutationssandsynlighederne.

Hvis du sænker antallet, får du en stabil, men langsom løsning. Et mindre antal kromosomer vil blive påvirket af genetiske operatorer, og der vil derfor være behov for flere iterationer for at finde løsningen.

Højere antal vil fremskynde algoritmen, men det vil også gøre løsningen ustabil. Passende kromosomer vil ikke kun blive bevaret, men vil også blive påvirket af de genetiske operatorer. Derfor vil de miste deres “gode” gener.

Det er vigtigt at finde en god balance. Hvis antallet af iterationer øges, vil algoritmen få flere muligheder for at finde en løsning, men på den anden side vil det tage mere tid. Du kan også anvende forskellige metoder til crossover og mutation. Et godt valg af disse operatører vil forbedre kvaliteten af løsningen drastisk.

Vi har kun dækket toppen af isbjerget her. Vi tog et eksempel, der kun har ét input, og input kan nemt præsenteres som et kromosom. De genetiske operatører er klare og enkle.

Det er meget interessant at tage et problem fra den virkelige verden og anvende den genetiske algoritme på det. Du vil opdage forskellige tilgange til kodning af virkelige inputdata samt forskellige crossover- og mutationsimplementeringer.

Hvis et problem kan udtrykkes gennem et sæt parametre, som vi skal gætte for at optimere en metrik, kan vi hurtigt opstille en GA, som vi kan bruge til at løse det.

Et af de mest interessante problemer er at undervise kunstige neurale netværk. Vi kan indstille de parametre, der kan optimeres, til at være synapsestyrker, og fitness-metrikken til at være den procentdel af input, for hvilke vores neurale netværk gav det rigtige svar. Herefter kan vi læne os tilbage og lade vores neurale netværk udvikle sig til den ideelle løsning, som vi ønsker. Eller i det mindste indtil vi får noget, der er godt nok, for evolution tager tid.