Vad är genetiska algoritmer?

Under de senaste åren har det varit mycket livligt kring artificiell intelligens (AI). Stora företag som Google, Apple och Microsoft arbetar aktivt med ämnet. AI är faktiskt ett paraply som omfattar många mål, tillvägagångssätt, verktyg och tillämpningar. Genetiska algoritmer (GA) är bara ett av verktygen för intelligent sökning bland många möjliga lösningar.

GA är en metaheuristisk sök- och optimeringsteknik som bygger på principer som finns i den naturliga evolutionen. Den tillhör en större klass av evolutionära algoritmer.

GA upprätthåller en population av kromosomer – en uppsättning potentiella lösningar för problemet. Tanken är att “evolutionen” ska hitta en optimal lösning för problemet efter ett antal på varandra följande generationer, vilket liknar det naturliga urvalet.

GA efterliknar tre evolutionära processer: urval, gencrossover och mutation.

Som i det naturliga urvalet är det centrala begreppet för GA:s urval fitness. De kromosomer som är mer lämpliga har en bättre chans att överleva. Fitness är en funktion som mäter kvaliteten på den lösning som kromosomen representerar. I huvudsak representerar varje kromosom i populationen de ingående parametrarna. Om ditt problem till exempel innehåller två ingående parametrar, till exempel pris och volym i handeln, kommer varje kromosom logiskt sett att bestå av två element. Hur elementen kodas i kromosomen är ett annat ämne.

Under urvalet bildar kromosomerna par av föräldrar för avel. Varje barn tar med sig egenskaper från sina föräldrar. I princip representerar barnet en rekombination av egenskaper från sina föräldrar: En del av egenskaperna tas från en förälder och en del från en annan förälder. Utöver rekombinationen kan en del av egenskaperna mutera.

Då bättre lämpade kromosomer producerar fler barn kommer varje efterföljande generation att ha bättre lämplighet. Vid någon tidpunkt kommer en generation att innehålla en kromosom som representerar en tillräckligt bra lösning för vårt problem.

GA är kraftfull och brett tillämpbar för komplexa problem. Det finns en stor klass av optimeringsproblem som är ganska svåra att lösa med konventionella optimeringstekniker. Genetiska algoritmer är effektiva algoritmer vars lösning är ungefärlig optimal. De välkända tillämpningarna omfattar schemaläggning, transport, ruttplanering, gruppteknik, layoutdesign, träning av neurala nätverk och många andra.

Tillämpning i praktiken

Exemplet som vi ska titta på kan betraktas som GA:s “Hello World”. Detta exempel gavs ursprungligen av J. Freeman i Simulating Neural Networks with Mathematica. Jag tog det från Genetic Algorithms and Engineering Design av Mitsuo Gen och Runwei Cheng.

I Word-Matching Problem försöker man utveckla ett uttryck med en genetisk algoritm. Inledningsvis ska algoritmen “gissa” frasen “to be or not to be” från slumpmässigt genererade listor med bokstäver.

Med tanke på att det finns 26 möjliga bokstäver för var och en av de 13 platserna i listan är sannolikheten för att vi ska få fram rätt fras på ett rent slumpmässigt sätt (1/26)^13=4.03038×10-19, vilket är ungefär två chanser av en (Gen & Chong, 1997).

Vi kommer att definiera problemet lite bredare här, vilket gör lösningen ännu svårare. Låt oss anta att vi inte är begränsade till det engelska språket eller en specifik fras. Det kan sluta med att vi har att göra med vilket alfabet som helst, eller till och med vilken uppsättning symboler som helst. Vi har ingen kunskap om språket. Vi vet inte ens om det finns något språk överhuvudtaget.

Vad sägs om vår motståndare tänkte på en godtycklig fras, inklusive vitrymder. Vi känner till frasens längd och antalet symboler i alfabetet. Det är den enda kunskap vi har. Efter varje gissning berättar vår motståndare för oss hur många bokstäver som finns på plats.

Varje kromosom är en sekvens av index för symbolerna i alfabetet. Om vi talar om det engelska alfabetet representeras “a” av 0, “b” av 1, “c” av 2 och så vidare. Så till exempel kommer ordet “be” att representeras som .

Vi kommer att demonstrera alla steg med hjälp av kodutdrag från Java, men kunskaper i Java krävs inte för att förstå varje steg.

Kärnan i den genetiska algoritmen

Vi kan börja med en allmän implementering av den genetiska algoritmen:

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

Det här är den enkla uppsättning steg som varje GA mer eller mindre består av. I initialiseringssteget genererar vi en initial population av fraser. Storleken på populationen bestäms av populationSize. Hur frasen genereras beror på implementeringen av supplier.

I iterationssteget utvecklar vi populationen tills avslutningsvillkoren är uppfyllda inom whileslingans test. Avslutningsvillkoren kan omfatta både antalet generationer och exakt matchning av en av fraserna i populationen. termination kapslar in en exakt implementering.

I varje iteration utför vi de typiska GA-stegen:

1. Gör ett urval över populationen baserat på kromosomernas lämplighet.
2. Företag en ny “generation” via crossover-operationen.
3. Företag en rekombination av vissa bokstäver i vissa fraser.

Kärnan i algoritmen är mycket enkel och domän-agnostisk. Den kommer att vara densamma för alla problem. Det du behöver justera är implementeringen av de genetiska operatörerna. Därefter kommer vi att titta närmare på var och en av de GA-operatorer som tidigare nämnts.

Selektion

Som vi redan vet är selektion en process som går ut på att hitta efterföljare till de aktuella kromosomerna – de kromosomer som är mer lämpade för vårt problem. Under urvalet måste vi se till att kromosomer med bättre fitness har en bättre chans att överleva.

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

Tanken bakom detta genomförande är följande: Populationen representeras som konsekutiva intervall på den numeriska axeln. Hela populationen ligger mellan 0 och 1.

Den bit av intervallet som en kromosom tar är proportionell mot dess fitness. Detta resulterar i att en bättre kromosom får en större del av området. Sedan tittar vi slumpmässigt på ett tal mellan 0 och 1 och hittar ett intervall som inkluderar talet. Det är uppenbart att större intervall har större chans att väljas ut, och därför har bättre lämpade kromosomer större chans att överleva.

Om vi inte känner till detaljerna om fitnessfunktionen måste vi normalisera fitnessvärdena. Fitnessfunktionen representeras av fitness, som omvandlar en kromosom till en godtycklig dubbel som representerar kromosomens fitness.

I koden hittar vi fitnessvärden för alla kromosomer i populationen, och vi hittar också den totala fitnessen. Inom for-slingan utför vi en kumulativ summa över sannolikheter som skalats ned med den totala fitnessen. Matematiskt sett bör detta resultera i att den slutliga variabeln har värdet 1. På grund av den oprecisa flyttalsvariabeln kan vi inte garantera detta, så vi ställer in den på 1 bara för att vara säkra.

Slutligt genererar vi ett slumpmässigt tal för ett antal gånger som är lika stort som antalet inmatade kromosomer, hittar ett intervall som innefattar talet och väljer sedan motsvarande kromosom. Som du kanske märker kan samma kromosom väljas flera gånger.

Crossover

Nu behöver vi till kromosomerna för att “avla”.

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 fördefinierade sannolikheten crossoverProbability väljer vi föräldrar för avel. De utvalda föräldrarna blandas så att alla kombinationer kan uppstå. Vi tar par av föräldrar och tillämpar operatorn crossover. Vi tillämpar operatören två gånger för varje par eftersom vi måste hålla populationens storlek oförändrad. Barnen ersätter sina föräldrar i populationen.

Mutation

Slutligt utför vi rekombination av egenskaperna.

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 fördefinierad sannolikhet mutationProbability utför vi “mutation” på kromosomerna. Själva mutationen definieras av mutation.

Problemspecifik algoritmkonfiguration

Nu ska vi ta en titt på vilken typ av problemspecifika parametrar vi behöver ge vår generiska 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;

Parametrarna är följande:

1. Crossover-operatör
2. Crossover-sannolikhet
3. Fitness-funktion
4. Mutationsoperatör
5. Mutationssannolikhet
6. Populationens storlek
7. Kromosomleverantör för den initiala populationen
8. Termineringsfunktion

Här är konfigurationen för vårt 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()

Korsningsoperatör och sannolikhet

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

Sannolikheten för korsning är 0.25, så vi förväntar oss att i genomsnitt 25 procent av kromosomerna kommer att väljas ut för crossover. Vi utför en enkel procedur för crossover av ett kromosompar. Vi genererar ett slumpmässigt tal n från intervallet , där length är längden på en kromosom. Nu parar vi det valda paret genom att ta de första n tecknen från den ena kromosomen och de resterande tecknen efter från den andra.

Fitnessfunktion

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

Fitnessfunktionen räknar helt enkelt antalet matchningar mellan målfrasen och den givna kromosomen.

Mutationsoperatör och sannolikhet

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 utförs oberoende av varandra på varje kromosom. Sannolikheten för mutation är 0,05, så vi förväntar oss att i genomsnitt fem procent av populationen kommer att muteras. Vi muterar genom att välja en slumpmässig bokstavsposition och ersätta dess värde med en slumpmässig bokstav från alfabetet. Vi gör det två gånger för varje muterad kromosom.

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

Leverantören genererar slumpmässiga fraser genom att ta slumpmässiga bokstäver från alfabetet. Varje fras har en konstant fördefinierad längd.

Avslutningsfunktion

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

Avslutningsfunktionen räknar antalet anrop och returnerar true om det antingen finns en exakt matchning eller om generationsantalet når 3 000.

Uppförande

Nu är vi redo att testa vår algoritm. Om du kör den flera gånger kommer du att märka att inte alla körningar lyckas. Varje gång kommer antalet iterationer att vara olika. Detta beror på algoritmens probabilistiska natur. Algoritmen har flera punkter där den kan förbättras. Du kan leka med crossover- och mutationssannolikheterna.

Släpper du ner antalet leder det till en stabil men långsam lösning. Ett mindre antal kromosomer kommer att påverkas av de genetiska operatörerna och därför kommer det att krävas fler iterationer för att få fram en lösning.

Om man ökar antalet kommer algoritmen att bli snabbare, men det kommer också att göra lösningen instabil. Passande kromosomer kommer inte bara att bevaras, utan också påverkas av de genetiska operatörerna. Därför kommer de att förlora sina “goda” gener.

Det är viktigt att hitta en bra balans. Om man ökar antalet iterationer får algoritmen fler möjligheter att hitta en lösning, men å andra sidan tar det mer tid. Du kan också tillämpa olika metoder för crossover och mutation. Ett bra val av dessa operatörer kommer att drastiskt förbättra lösningens kvalitet.

Vi har bara täckt toppen av isberget här. Vi tog ett exempel som bara har en ingång, och ingången kan enkelt presenteras som en kromosom. De genetiska operatörerna är enkla och tydliga.

Det är mycket intressant att ta ett verkligt problem och tillämpa den genetiska algoritmen på det. Du kommer att upptäcka olika tillvägagångssätt för att koda verkliga indata samt olika crossover- och mutationsimplementationer.

Om ett problem kan uttryckas genom en uppsättning parametrar som vi måste gissa oss till för att optimera ett mått, kan vi snabbt sätta upp en GA som vi kan använda för att lösa det.

Ett av de mest intressanta problemen är att lära ut artificiella neurala nätverk. Vi kan ställa in de parametrar som kan optimeras till att vara synapsstyrkor och fitnessmåttet till att vara den procentuella andelen ingångar för vilka vårt neurala nätverk gav rätt svar. Därefter kan vi luta oss tillbaka och låta vårt neurala nätverk utvecklas till den idealiska lösning vi önskar. Eller åtminstone tills vi får något som är tillräckligt bra, eftersom evolutionen tar tid.