Mit jelentenek a genetikai algoritmusok?

Az elmúlt néhány évben a mesterséges intelligencia (AI) körül óriási volt a felhajtás. Olyan nagyvállalatok, mint a Google, az Apple és a Microsoft aktívan dolgoznak a témán. Valójában a mesterséges intelligencia egy ernyő, amely rengeteg célt, megközelítést, eszközt és alkalmazást takar. A genetikai algoritmus (GA) csak az egyik eszköz a sok lehetséges megoldás intelligens keresésére.

A GA egy metaheurisztikus keresési és optimalizálási technika, amely a természetes evolúcióban jelen lévő elveken alapul. Az evolúciós algoritmusok egy nagyobb osztályába tartozik.

A GA kromoszómák populációját – a probléma lehetséges megoldásainak halmazát – tartja fenn. Az elképzelés szerint az “evolúció” számos egymást követő generáció után megtalálja a probléma optimális megoldását – hasonlóan a természetes szelekcióhoz.

A GA három evolúciós folyamatot utánoz: szelekció, génátvitel és mutáció.

A természetes szelekcióhoz hasonlóan a GA szelekciójának központi fogalma a fitnesz. Az alkalmasabb kromoszómáknak nagyobb esélyük van a túlélésre. A fitnesz egy olyan függvény, amely a kromoszóma által képviselt megoldás minőségét méri. Lényegében a populáción belül minden kromoszóma a bemeneti paramétereket képviseli. Például, ha a probléma két bemeneti paramétert tartalmaz, mint például az ár és a kereskedési volumen, akkor minden kromoszóma logikusan két elemből fog állni. Az, hogy az elemek hogyan vannak kódolva a kromoszómán belül, egy másik téma.

A szelekció során a kromoszómák szülőpárokat alkotnak a tenyésztéshez. Minden gyermek átveszi a tulajdonságokat a szüleitől. Alapvetően a gyermek a szüleitől származó tulajdonságok rekombinációját jelenti: A tulajdonságok egy részét az egyik szülőtől, más részét pedig a másik szülőtől veszi át. A rekombináció mellett a tulajdonságok egy része mutálódhat.

Mivel a fittebb kromoszómák több gyermeket hoznak létre, minden egyes következő generáció jobb fittséggel rendelkezik. Egy bizonyos ponton egy generáció olyan kromoszómát fog tartalmazni, amely elég jó megoldást képvisel a problémánkhoz.

Az GA nagy teljesítményű és széles körben alkalmazható komplex problémákra. Az optimalizálási problémáknak van egy nagy osztálya, amelyeket a hagyományos optimalizálási technikákkal meglehetősen nehéz megoldani. A genetikai algoritmusok hatékony algoritmusok, amelyek megoldása megközelítőleg optimális. A jól ismert alkalmazások közé tartozik az ütemezés, a szállítás, az útvonaltervezés, a csoporttechnológiák, az elrendezéstervezés, a neurális hálózatok képzése és sok más.

A dolgok átültetése a gyakorlatba

A példát, amelyet megnézünk, a GA “Hello World”-jének tekinthetjük. Ezt a példát eredetileg J. Freeman adta a Simulating Neural Networks with Mathematica című könyvében. Én Mitsuo Gen és Runwei Cheng Genetic Algorithms and Engineering Design című könyvéből vettem át.

A Word-Matching Problem egy kifejezést próbál genetikus algoritmussal fejleszteni. Kezdetben az algoritmusnak a “lenni vagy nem lenni” kifejezést kell “kitalálnia” véletlenszerűen generált betűlistákból.

Mivel a lista 13 helyére 26 lehetséges betű jut, annak a valószínűsége, hogy tisztán véletlenszerűen megkapjuk a helyes kifejezést, (1/26)^13=4.03038×10-19, ami körülbelül két esélyből kettő (Gen & Chong, 1997).

Itt egy kicsit tágabban definiáljuk a problémát, ami még nehezebbé teszi a megoldást. Tegyük fel, hogy nem korlátozódunk az angol nyelvre vagy egy adott kifejezésre. Végeredményben bármilyen ábécével, vagy akár szimbólumok bármilyen halmazával foglalkozhatunk. Nincs nyelvtudásunk. Még azt sem tudjuk, hogy egyáltalán van-e nyelv.

Tegyük fel, hogy ellenfelünk egy tetszőleges, szóközöket is tartalmazó kifejezésre gondolt. Ismerjük a mondat hosszát és az ábécé szimbólumainak számát. Ez az egyetlen tudásunk. Minden kitalálás után ellenfelünk megmondja, hogy hány betű van a helyén.

Minden kromoszóma az ábécé szimbólumainak indexeinek sorozata. Ha az angol ábécéről beszélünk, akkor az “a”-t a 0, a “b”-t az 1, a “c”-t a 2, és így tovább. Így például a “be” szót -nak fogjuk ábrázolni.

Az összes lépést Java kódrészleteken keresztül mutatjuk be, de az egyes lépések megértéséhez nem szükséges a Java ismerete.

Genetikus algoritmus mag

A genetikus algoritmus általános megvalósításával kezdhetjük:

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

Ez a lépések egyszerű halmaza, amelyből többé-kevésbé minden GA áll. Az inicializálási lépésnél létrehozunk egy kezdeti populációt a mondatokból. A populáció méretét a populationSize határozza meg. A frázisok generálásának módja a supplier megvalósításától függ.

Az iterációs lépésben addig fejlesztjük a populációt, amíg a while ciklus tesztjén belül a befejezési feltételek teljesülnek. A befejezési feltételek közé tartozhat mind a generációk száma, mind a populációban lévő egyik kifejezés pontos egyezése. A termination egy pontos megvalósítást foglal magába.

Minden egyes iterációban elvégezzük a GA tipikus lépéseit:

1. Végezzünk szelekciót a populáción a kromoszóma fitnesz alapján.
2. Új “generációt” hozunk létre a keresztezési művelet segítségével.
3. Új rekombinációt hajtunk végre egyes betűkkel egyes mondatokban.

Az algoritmus magja nagyon egyszerű és domain-agnosztikus. Minden problémára ugyanaz lesz. Amit tuningolni kell, az a genetikai operátorok implementációja. A következőkben a korábban említett GA-operátorok mindegyikét alaposan megvizsgáljuk.

Szelekció

A szelekció – mint már tudjuk – az aktuális kromoszómák utódainak – a problémánkhoz jobban illeszkedő kromoszómáknak – a megtalálását jelenti. A szelekció során biztosítanunk kell, hogy a jobb fitneszű kromoszómáknak nagyobb esélyük legyen a túlélésre.

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

A megvalósítás lényege a következő: A populációt következetes tartományokként ábrázoljuk a numerikus tengelyen. A teljes populáció 0 és 1 között van.

A tartománynak az a darabja, amelyet egy kromoszóma elfoglal, arányos a fitneszével. Ez azt eredményezi, hogy az alkalmasabb kromoszóma nagyobb darabot kap. Ezután véletlenszerűen megnézünk egy 0 és 1 közötti számot, és keresünk egy olyan tartományt, amely tartalmazza a számot. Nyilvánvaló, hogy a nagyobb tartományok nagyobb eséllyel kerülnek kiválasztásra, és ezért az alkalmasabb kromoszómáknak nagyobb esélyük van a túlélésre.

Mivel nem ismerjük a fitneszfüggvény részleteit, normalizálnunk kell a fitneszértékeket. A fitneszfüggvényt a fitness jelöli, amely egy kromoszómát egy tetszőleges kettősre alakít át, amely a kromoszóma fitneszét jelenti.

A kódban a populáció összes kromoszómájának fitneszrátáját, valamint a teljes fitneszértéket találjuk meg. A for cikluson belül egy kumulatív összeget végzünk a valószínűségeken a teljes fitneszre skálázva. Matematikailag ennek azt kellene eredményeznie, hogy a végső változó értéke 1. A lebegőpontos számítás pontatlansága miatt ezt nem tudjuk garantálni, ezért a biztonság kedvéért 1-re állítjuk.

Végül a bemeneti kromoszómák számával megegyező számú alkalommal generálunk egy véletlen számot, keresünk egy olyan tartományt, amely tartalmazza a számot, majd kiválasztjuk a megfelelő kromoszómát. Mint észrevehetjük, ugyanazt a kromoszómát többször is kiválaszthatjuk.

Keresztezés

Most a kromoszómákat kell “szaporítani”.

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

Az előre meghatározott crossoverProbability valószínűséggel kiválasztjuk a szülőket a szaporításhoz. A kiválasztott szülőket megkeverjük, így bármilyen kombináció előfordulhat. Fogjuk a szülők párjait, és alkalmazzuk a crossover operátort. Az operátort minden párra kétszer alkalmazzuk, mert a populáció méretét változatlanul kell tartanunk. A gyermekek helyettesítik szüleiket a populációban.

Mutáció

Végül elvégezzük a jellemzők rekombinációját.

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

Előre meghatározott mutationProbability valószínűséggel “mutációt” hajtunk végre a kromoszómákon. Magát a mutációt a mutation határozza meg.

Problémaspecifikus algoritmus konfiguráció

Most nézzük meg, hogy milyen problémaspecifikus paramétereket kell megadnunk az általános implementációnknak.

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;

A paraméterek ennek megfelelően a következők:

1. Crossover operátor
2. Crossover valószínűség
3. Fitness függvény
4. Mutációs operátor
5. Mutációs valószínűség
6. Populáció mérete
7. Kromoszóma szállító a kezdeti populációhoz
8. Terminációs függvény

Itt van a problémánk konfigurációja:

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

Keresztezési operátor és valószínűsége

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

A keresztezés valószínűsége 0.25, tehát arra számítunk, hogy átlagosan a kromoszómák 25 százalékát választjuk ki keresztezésre. Egyszerű eljárást végzünk egy kromoszómapár keresztezésére. Generálunk egy n véletlen számot a tartományból, ahol length a kromoszóma hossza. Most a kiválasztott párt párosítjuk úgy, hogy az első n karaktert az egyik kromoszómából, az utána maradó karaktereket pedig a másodikból vesszük.

Fitneszfüggvény

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

A fitneszfüggvény egyszerűen a célkifejezés és az adott kromoszóma közötti egyezések számát számolja.

Mutációs operátor és valószínűség

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

A mutációs műveletet minden kromoszómán függetlenül végezzük. A mutáció valószínűsége 0,05, tehát arra számítunk, hogy átlagosan a populáció öt százaléka mutálódik. A mutációt úgy végezzük, hogy kiválasztunk egy véletlenszerű betűhelyet, és annak értékét az ábécé egy véletlenszerű betűjével helyettesítjük. Ezt minden mutálódott kromoszómánál kétszer végezzük el.

Szállító

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

A szállító úgy generál véletlen mondatokat, hogy véletlen betűket vesz az ábécéből. Minden mondat állandó, előre meghatározott hosszúságú.

Terminációs függvény

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

A terminációs függvény megszámolja a hívások számát, és true adja vissza, ha vagy pontos egyezés van, vagy ha a generációs szám eléri a 3000-et.

Futtatás

Most készen állunk az algoritmusunk tesztelésére. Ha többször futtatjuk, észre fogjuk venni, hogy nem minden futtatás sikeres. Minden alkalommal más lesz az iterációk száma. Ez az algoritmus valószínűségi jellegéből adódik. Az algoritmusnak több olyan pontja van, ahol javítani lehet. Játszhat a keresztezési és mutációs valószínűségekkel.

A szám csökkentése stabil, de lassú megoldáshoz vezet. Kisebb számú kromoszómára hatnak a genetikai operátorok, ezért több iterációra lesz szükség a megoldáshoz.

A számok növelése gyorsítja az algoritmust, de instabillá teszi a megoldást. Az illeszkedő kromoszómák nemcsak megmaradnak, hanem a genetikai operátorok is hatással lesznek rájuk. Ezért elveszítik a “jó” génjeiket.

A jó egyensúly megtalálása fontos. Az iterációk számának növelése több lehetőséget ad az algoritmusnak a megoldás megtalálására, másrészt viszont több időt vesz igénybe. A keresztezés és mutáció különböző módszereit is alkalmazhatja. Ezeknek az operátoroknak a jó megválasztása drasztikusan javítja a megoldás minőségét.

Ezzel csak a jéghegy csúcsát fedeztük le. Egy olyan példát vettünk, amelynek csak egy bemenete van, és a bemenet könnyen bemutatható kromoszómaként. A genetikai operátorok egyszerűek és világosak.

Nagyon érdekes, ha veszünk egy valós problémát, és alkalmazzuk rá a genetikai algoritmust. Különböző megközelítéseket fedezhetünk fel a valós bemeneti adatok kódolásában, valamint különböző keresztezési és mutációs implementációkat.

Ha egy probléma kifejezhető egy olyan paraméterkészleten keresztül, amelyet meg kell találnunk egy metrika optimalizálásához, akkor gyorsan felállíthatunk egy GA-t, amelyet használhatunk a probléma megoldására.

Az egyik legérdekesebb probléma a mesterséges neurális hálózatok tanítása. Beállíthatjuk, hogy az optimalizálható paraméterek a szinapszisok erősségei legyenek, a fitnesz metrika pedig azon bemenetek százalékos aránya, amelyekre a neurális hálózatunk helyes választ adott. Ezek után hátradőlhetünk, és hagyhatjuk, hogy neurális hálózatunk a kívánt ideális megoldássá fejlődjön. Vagy legalábbis addig, amíg valami elég jót nem kapunk, mert az evolúcióhoz idő kell.