What Are Genetic Algorithms?

De laatste paar jaar is er een enorme buzz geweest rond Artificial Intelligence (AI). Grote bedrijven als Google, Apple en Microsoft zijn actief bezig met dit onderwerp. In feite is AI een paraplu die een heleboel doelen, benaderingen, hulpmiddelen en toepassingen omvat. Genetische Algoritmen (GA) is slechts een van de hulpmiddelen voor het intelligent zoeken door vele mogelijke oplossingen.

GA is een metaheuristische zoek- en optimalisatietechniek gebaseerd op principes die in de natuurlijke evolutie aanwezig zijn. Het behoort tot een grotere klasse van evolutionaire algoritmen.

GA onderhoudt een populatie van chromosomen-een set van potentiële oplossingen voor het probleem. Het idee is dat “evolutie” een optimale oplossing voor het probleem zal vinden na een aantal opeenvolgende generaties – vergelijkbaar met natuurlijke selectie.

GA bootst drie evolutionaire processen na: selectie, genkruising, en mutatie.

Gelijk aan natuurlijke selectie, is het centrale concept van GA-selectie fitness. De chromosomen die meer fit zijn hebben een betere kans om te overleven. Fitness is een functie die de kwaliteit meet van de oplossing die door het chromosoom wordt voorgesteld. In wezen vertegenwoordigt elk chromosoom in de populatie de inputparameters. Als uw probleem bijvoorbeeld twee inputparameters bevat, zoals prijs en volume in de handel, zal elk chromosoom logischerwijs uit twee elementen bestaan. Hoe de elementen binnen het chromosoom worden gecodeerd, is een ander onderwerp.

Tijdens de selectie vormen chromosomen ouderparen voor de fok. Elk kind neemt kenmerken van zijn ouders over. In wezen vertegenwoordigt het kind een recombinatie van kenmerken van zijn ouders: Sommige kenmerken zijn afkomstig van de ene ouder en andere van de andere. Naast de recombinatie kunnen sommige kenmerken muteren.

Omdat fittere chromosomen meer kinderen voortbrengen, zal elke volgende generatie een betere fitness hebben. Op een gegeven moment zal een generatie een chromosoom bevatten dat een goed genoeg oplossing voor ons probleem zal vertegenwoordigen.

GA is krachtig en breed toepasbaar voor complexe problemen. Er is een grote klasse van optimalisatieproblemen die vrij moeilijk op te lossen zijn met conventionele optimalisatietechnieken. Genetische algoritmen zijn efficiënte algoritmen waarvan de oplossing bij benadering optimaal is. Bekende toepassingen zijn o.a. planning, transport, routing, groepstechnologieën, layout ontwerp, neurale netwerk training, en vele andere.

Praktijk

Het voorbeeld dat we zullen bekijken kan worden beschouwd als de “Hallo Wereld” van GA. Dit voorbeeld is oorspronkelijk gegeven door J. Freeman in Simulating Neural Networks with Mathematica. Ik heb het overgenomen uit Genetic Algorithms and Engineering Design van Mitsuo Gen en Runwei Cheng.

Het Word-Matching Probleem probeert een uitdrukking te laten evolueren met een genetisch algoritme. Aanvankelijk wordt het algoritme verondersteld de zin “to be or not to be” te “raden” uit willekeurig gegenereerde lijsten van letters.

Omdat er 26 mogelijke letters zijn voor elk van de 13 plaatsen in de lijst, is de kans dat we de juiste zin op een zuiver willekeurige manier krijgen (1/26)^13=4.03038×10-19, dat is ongeveer twee kansen op een (Gen & Chong, 1997).

We zullen het probleem hier wat ruimer definiëren, waardoor de oplossing nog moeilijker wordt. Laten we aannemen dat we niet beperkt zijn tot de Engelse taal of een specifieke zin. We kunnen te maken krijgen met elk alfabet, of zelfs elke verzameling symbolen. We hebben geen kennis van de taal. We weten zelfs niet of er überhaupt een taal bestaat.

Laten we zeggen dat onze tegenstander een willekeurige zin heeft bedacht, inclusief witruimte. We kennen de lengte van de zin en het aantal symbolen in het alfabet. Dat is de enige kennis die we hebben. Na elke gok vertelt onze tegenstander ons hoeveel letters er op de plaats staan.

Elk chromosoom is een opeenvolging van indexen van de symbolen in het alfabet. Als we het hebben over het Engelse alfabet, dan wordt “a” voorgesteld door 0, “b” door 1, “c” door 2, enzovoort. Dus, bijvoorbeeld, het woord “be” zal worden weergegeven als .

We zullen alle stappen demonstreren door middel van Java code snippets, maar kennis van Java is niet vereist om elke stap te begrijpen.

Genetisch Algoritme Kern

We kunnen beginnen met een algemene implementatie van het genetisch 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); }}

Dit is de eenvoudige reeks stappen waaruit elke GA min of meer bestaat. Bij de initialisatiestap genereren we een initiële populatie van zinnen. De grootte van de populatie wordt bepaald door populationSize. Hoe de frase wordt gegenereerd hangt af van de implementatie van de supplier.

In de iteratiestap evolueren we de populatie totdat aan de beëindigingsvoorwaarden is voldaan binnen de while test van de lus. De beëindigingsvoorwaarden kunnen zowel het aantal generaties als de exacte overeenkomst van een van de zinnen in de populatie omvatten. De termination kapselt een exacte implementatie in.

In elke iteratie voeren we de typische GA-stappen uit:

1. Voer een selectie uit over de populatie op basis van chromosoom fitness.
2. Voorzie een nieuwe “generatie” via de crossover operatie.
3. Voer een recombinatie uit van enkele letters in enkele zinnen.

De kern van het algoritme is zeer eenvoudig en domein-agnostisch. Het zal voor alle problemen hetzelfde zijn. Wat je moet afstemmen is de implementatie van de genetische operatoren. Vervolgens zullen we elk van de eerder genoemde GA-operatoren onder de loep nemen.

Selectie

Zoals we al weten, is selectie een proces van het vinden van opvolgers voor de huidige chromosomen – de chromosomen die beter geschikt zijn voor ons probleem. Tijdens de selectie moeten we ervoor zorgen dat de chromosomen met een betere fitness een betere overlevingskans hebben.

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

Het idee achter deze implementatie is het volgende: De populatie wordt voorgesteld als resulterende bereiken op de numerieke as. De hele populatie ligt tussen 0 en 1.

Het deel van het bereik dat een chromosoom inneemt, is evenredig met zijn fitness. Dit betekent dat een fitter chromosoom een groter stuk krijgt. Dan kijken we willekeurig naar een getal tussen 0 en 1 en zoeken een reeks die dat getal omvat. Het is duidelijk dat grotere reeksen meer kans hebben om geselecteerd te worden, en dus hebben fittere chromosomen meer kans om te overleven.

Omdat we geen details over de fitnessfunctie kennen, moeten we de fitnesswaarden normaliseren. De fitness-functie wordt voorgesteld door fitness, die een chromosoom omzet in een willekeurig dubbel dat de fitness van het chromosoom weergeeft.

In de code vinden we fitness-waarden voor alle chromosomen in de populatie, en we vinden ook de totale fitness. Binnen de for lus, voeren we een cumulatieve som over kansen geschaald door de totale fitness. Wiskundig gezien zou dit moeten resulteren in de laatste variabele met de waarde 1. Vanwege de onnauwkeurigheid van drijvende komma’s kunnen we dat niet garanderen, dus stellen we het voor de zekerheid in op 1.

Tot slot genereren we voor een aantal keren dat gelijk is aan het aantal ingevoerde chromosomen een willekeurig getal, vinden een bereik dat het getal omvat, en selecteren vervolgens het bijbehorende chromosoom. Zoals u wellicht zult opmerken, kan hetzelfde chromosoom meerdere malen worden geselecteerd.

Kruising

Nu moeten we de chromosomen “fokken.”

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

Met de vooraf bepaalde waarschijnlijkheid crossoverProbability selecteren we de ouders voor het fokken. De geselecteerde ouders worden geschud, zodat alle combinaties mogelijk zijn. We nemen paren van ouders en passen de operator crossover toe. We passen de operator tweemaal toe voor elk paar omdat we de grootte van de populatie gelijk moeten houden. De kinderen vervangen hun ouders in de populatie.

Mutatie

Tot slot voeren we recombinatie van de kenmerken uit.

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

Met een vooraf bepaalde waarschijnlijkheid mutationProbability voeren we “mutatie” op de chromosomen uit. De mutatie zelf wordt gedefinieerd door mutation.

Probleemspecifieke algoritmeconfiguratie

Laten we nu eens kijken wat voor soort probleemspecifieke parameters we aan onze generieke implementatie moeten meegeven.

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;

De parameters, respectievelijk, zijn:

1. Kruisingsoperator
2. Kruisingswaarschijnlijkheid
3. Geschiktheidsfunctie
4. Mutatieoperator
5. Mutatiewaarschijnlijkheid
6. Grootte van de populatie
7. Chromosoomleverancier voor de initiële populatie
8. Terminatiefunctie

Hier is de configuratie voor ons probleem:

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 and Probability

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

De waarschijnlijkheid van crossover is 0.25, dus we verwachten dat gemiddeld 25 procent van de chromosomen geselecteerd zullen worden voor crossover. We voeren een eenvoudige procedure uit voor de cross-over van een chromosomenpaar. We genereren een willekeurig getal n uit de reeks , waarbij length de lengte van een chromosoom is. Nu paren we het geselecteerde paar door de eerste n tekens van het ene chromosoom te nemen en de resterende tekens daarna van het tweede.

Fitness Function

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

De fitness-functie telt eenvoudig het aantal overeenkomsten tussen de doelzin en het gegeven chromosoom.

Mutatie-operator en waarschijnlijkheid

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

De mutatie-operatie wordt onafhankelijk op elk chromosoom uitgevoerd. De kans op mutatie is 0.05, dus we verwachten dat gemiddeld vijf procent van de populatie gemuteerd zal worden. We muteren door een willekeurige letterpositie te kiezen en de waarde daarvan te vervangen door een willekeurige letter uit het alfabet. We doen dit tweemaal voor elk gemuteerd chromosoom.

Leverancier

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

De leverancier genereert willekeurige zinnen door willekeurige letters uit het alfabet te nemen. Elke zin heeft een constante vooraf bepaalde lengte.

Termination Function

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

De termination function telt het aantal aanroepen en retourneert true als er een exacte overeenkomst is, of als het aantal generatie 3.000 bereikt.

Execution

Nu zijn we klaar om ons algoritme te testen. Als je het verschillende keren uitvoert, zul je merken dat niet alle runs succesvol zijn. Het aantal iteraties zal elke keer anders zijn. Dat komt door de probabilistische aard van het algoritme. Het algoritme kan op verschillende punten worden verbeterd. U kunt spelen met de crossover en mutatie kansen.

Lager het aantal zal leiden tot een stabiele maar langzame oplossing. Een kleiner aantal chromosomen zal worden beïnvloed door genetische operatoren en daarom zullen meer iteraties nodig zijn voor de oplossing.

Het verhogen van de aantallen zal het algoritme versnellen, maar het zal ook de oplossing onstabiel maken. Geschikte chromosomen zullen niet alleen behouden blijven, maar zullen ook worden beïnvloed door de genetische operatoren. Daarom zullen zij hun “goede” genen verliezen.

Het is belangrijk om een goed evenwicht te vinden. Door het aantal iteraties te verhogen, krijgt het algoritme meer kansen om een oplossing te vinden, maar daar staat tegenover dat het meer tijd kost. Je kunt ook verschillende crossover- en mutatiemethoden toepassen. Een goede selectie van deze operatoren zal de kwaliteit van de oplossing drastisch verbeteren.

We hebben hier slechts het topje van de ijsberg behandeld. We hebben een voorbeeld genomen dat slechts één input heeft, en de input kan gemakkelijk worden gepresenteerd als een chromosoom. De genetische operatoren zijn duidelijk en eenvoudig.

Het is zeer interessant om een probleem uit de echte wereld te nemen en daarop het genetisch algoritme toe te passen. Je zult verschillende benaderingen ontdekken in het coderen van echte invoergegevens, evenals verschillende crossover- en mutatie-implementaties.

Als een probleem kan worden uitgedrukt door een set parameters die we moeten raden om een metriek te optimaliseren, kunnen we snel een GA opzetten waarmee we het kunnen oplossen.

Een van de meest interessante problemen is het onderwijzen van kunstmatige neurale netwerken. We kunnen de optimaliseerbare parameters instellen op synaps sterktes, en de fitness metriek op het percentage van de inputs waarvoor ons neurale netwerk het juiste antwoord gaf. Daarna kunnen we achterover leunen en ons neuraal netwerk laten evolueren tot de ideale oplossing die we wensen. Of tenminste tot we iets hebben dat goed genoeg is, want evolutie kost tijd.