Mitä ovat geneettiset algoritmit?
Viime vuosina tekoälyn (AI) ympärillä on vallinnut valtava pöhinä. Suuret yritykset, kuten Google, Apple ja Microsoft, työskentelevät aktiivisesti aiheen parissa. Itse asiassa tekoäly on sateenvarjo, joka kattaa paljon tavoitteita, lähestymistapoja, työkaluja ja sovelluksia. Geneettiset algoritmit (Genetic Algorithms, GA) on vain yksi työkalu älykkääseen hakuun monien mahdollisten ratkaisujen läpi.
GA on metaheuristinen haku- ja optimointitekniikka, joka perustuu luonnollisessa evoluutiossa esiintyviin periaatteisiin. Se kuuluu evoluutioalgoritmien laajempaan luokkaan.
GA ylläpitää kromosomipopulaatiota, joka on joukko mahdollisia ratkaisuja ongelmaan. Ajatuksena on, että “evoluutio” löytää ongelman optimaalisen ratkaisun useiden peräkkäisten sukupolvien jälkeen – samaan tapaan kuin luonnollisessa valinnassa.
GA jäljittelee kolmea evoluutioprosessia: valintaa, geenien risteytymistä ja mutaatiota.
Keskeisenä käsitteenä GA:n valinnassa on luonnollisen valinnan tapaan fitness. Kuntoisimmilla kromosomeilla on paremmat mahdollisuudet selviytyä. Fitness on funktio, joka mittaa kromosomin edustaman ratkaisun laatua. Pohjimmiltaan jokainen kromosomi populaatiossa edustaa syöttöparametreja. Jos ongelmasi sisältää esimerkiksi kaksi syöttöparametria, kuten hinta ja volyymi kaupankäynnissä, jokainen kromosomi koostuu loogisesti kahdesta elementistä. Se, miten elementit koodataan kromosomissa, on eri aihe.
Valinnan aikana kromosomit muodostavat vanhempien parit jalostusta varten. Kukin lapsi ottaa ominaisuuksia vanhemmiltaan. Periaatteessa lapsi edustaa vanhempiensa ominaisuuksien rekombinaatiota: Osa ominaisuuksista on otettu yhdeltä vanhemmalta ja osa toiselta vanhemmalta. Rekombinaation lisäksi osa ominaisuuksista voi mutaantua.
Koska kyvykkäämmät kromosomit tuottavat enemmän lapsia, jokaisen seuraavan sukupolven kunto on parempi. Jossain vaiheessa sukupolvi sisältää kromosomin, joka edustaa riittävän hyvää ratkaisua ongelmaamme.
GA on tehokas ja laajasti sovellettavissa monimutkaisiin ongelmiin. On olemassa suuri luokka optimointiongelmia, joita on melko vaikea ratkaista perinteisillä optimointitekniikoilla. Geneettiset algoritmit ovat tehokkaita algoritmeja, joiden ratkaisu on likimain optimaalinen. Tunnettuja sovelluksia ovat muun muassa aikataulutus, kuljetus, reititys, ryhmätekniikat, layout-suunnittelu, neuroverkkojen harjoittelu ja monet muut.
Käytännön toteutus
Esimerkkiä, jota tarkastelemme, voidaan pitää GA:n “Hello Worldina”. Tämän esimerkin antoi alun perin J. Freeman kirjassa Simulating Neural Networks with Mathematica. Otin sen teoksesta Genetic Algorithms and Engineering Design, jonka ovat kirjoittaneet Mitsuo Gen ja Runwei Cheng.
Sanojen yhdistämisongelmassa yritetään kehittää lauseketta geneettisen algoritmin avulla. Aluksi algoritmin on tarkoitus “arvata” “olla tai olla olematta” -lause satunnaisesti generoiduista kirjainluetteloista.
Koska luettelossa on 26 mahdollista kirjainta jokaiseen 13:sta kohdasta, todennäköisyys sille, että saamme oikean lauseen puhtaasti satunnaisesti on (1/26)^13=4.03038×10-19, mikä on noin kaksi mahdollisuutta a:sta (Gen & Chong, 1997).
Määrittelemme ongelman tässä hieman laajemmin, mikä tekee ratkaisusta vielä vaikeamman. Oletetaan, että emme rajoitu englannin kieleen tai tiettyyn lauseeseen. Voimme päätyä käsittelemään mitä tahansa aakkosia tai jopa mitä tahansa symbolijoukkoa. Meillä ei ole tietoa kielestä. Emme edes tiedä, onko kieltä ylipäätään olemassa.
Asettakaamme, että vastustajamme keksi mielivaltaisen lauseen, joka sisältää välilyönnit. Tiedämme lauseen pituuden ja aakkosten symbolien lukumäärän. Se on ainoa tieto, joka meillä on. Jokaisen arvauksen jälkeen vastustajamme kertoo meille, kuinka monta kirjainta on paikallaan.
Jokainen kromosomi on sarja aakkosten symbolien indeksejä. Jos puhumme englantilaisista aakkosista, a:ta edustaa 0, b:tä 1, c:tä 2 ja niin edelleen. Joten esimerkiksi sana “be” esitetään muodossa .
Demonstroimme kaikki vaiheet Java-koodinpätkien avulla, mutta Java-taitoa ei tarvita jokaisen vaiheen ymmärtämiseen.
Geneettisen algoritmin ydin
Voidaan aloittaa geneettisen algoritmin yleisestä toteutuksesta:
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); }}Tämä on yksinkertainen joukko vaiheita, joista jokainen GA enemmän tai vähemmän koostuu. Aloitusvaiheessa luomme alkupopulaation lausekkeista. Populaation koko määräytyy populationSize:n mukaan. Se, miten lauseet luodaan, riippuu supplier:n toteutuksesta.
Iteraatiovaiheessa kehitämme populaatiota, kunnes päättymisehdot täyttyvät while-silmukan testissä. Lopetusehtoja voivat olla sekä sukupolvien lukumäärä että jonkin populaatiossa olevan lauseen täsmällinen vastaavuus. termination kapseloi tarkan toteutuksen.
Kussakin iteraatiossa suoritamme tyypilliset GA:n vaiheet:
- Toteutetaan valinta populaation yli kromosomien kelpoisuuden perusteella.
- Tuotetaan uusi “sukupolvi” crossover-operaation avulla.
- Toteutetaan joidenkin lauseiden joidenkin kirjainten rekombinaatio.
Algoritmin ydin on hyvin yksinkertainen ja domain-agnostinen. Se on sama kaikille ongelmille. Se, mitä sinun täytyy virittää, on geneettisten operaattoreiden toteutus. Seuraavaksi tarkastelemme lähemmin kutakin aiemmin mainittua GA-operaattoria.
Valinta
Kuten jo tiedämme, valinnassa etsitään nykyisille kromosomeille seuraajia – kromosomeja, jotka sopivat paremmin ongelmaamme. Valinnan aikana meidän on varmistettava, että paremman kelpoisuuden omaavilla kromosomeilla on paremmat mahdollisuudet selviytyä.
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());}Toteutuksen idea on seuraava: Populaatio esitetään numeerisella akselilla johdonmukaisina vaihteluväleinä. Koko populaatio on välillä 0-1.
Kromosomin ottaman vaihteluvälin osuus on verrannollinen sen kuntoon. Tämä johtaa siihen, että sopivampi kromosomi saa suuremman palan. Sitten kurkistetaan satunnaisesti luku väliltä 0 ja 1 ja etsitään alue, joka sisältää kyseisen luvun. On selvää, että suuremmilla alueilla on suuremmat mahdollisuudet tulla valituksi, ja siksi fittereillä kromosomeilla on paremmat mahdollisuudet selviytyä.
Koska emme tiedä yksityiskohtia fitness-funktiosta, meidän on normalisoitava fitness-arvot. Kuntofunktiota edustaa fitness, joka muuntaa kromosomin mielivaltaiseksi kaksoiskertoimeksi, joka edustaa kromosomin kuntoa.
Koodissa löydämme kaikkien populaatiossa olevien kromosomien kuntoarvot ja lisäksi löydämme kokonaiskunnon. for-silmukassa suoritamme kumulatiivisen summan todennäköisyyksistä, jotka on skaalattu kokonaiskuntoisuuden mukaan. Matemaattisesti tämän pitäisi johtaa siihen, että lopullisen muuttujan arvo on 1. Liukuluvun epätarkkuuden vuoksi emme voi taata tätä, joten asetamme sen arvoksi 1 varmuuden vuoksi.
Viimeiseksi luomme satunnaisluvun syötettyjen kromosomien lukumäärää vastaavalle määrälle kertoja, etsimme luvun sisältävän vaihteluvälin ja valitsemme sitten vastaavan kromosomin. Kuten saatat huomata, sama kromosomi voidaan valita useita kertoja.
Risteytys
Jatkossa tarvitsemme kromosomeja “jalostettavaksi.”
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)); }}Valitaan ennalta määritellyllä todennäköisyydellä crossoverProbability vanhemmat jalostukseen. Valitut vanhemmat sekoitetaan, jolloin kaikki yhdistelmät ovat mahdollisia. Otetaan vanhempien parit ja sovelletaan crossover-operaattoria. Sovellamme operaattoria kahdesti jokaiseen pariin, koska meidän on pidettävä populaation koko samana. Lapset korvaavat vanhempansa populaatiossa.
Mutaatio
Viimeiseksi suoritamme ominaisuuksien rekombinaation.
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))); } }}Edeltä määritellyllä todennäköisyydellä mutationProbability suoritamme kromosomeille “mutaation”. Itse mutaatio määritellään mutation.
Obgelmakohtainen algoritmikonfiguraatio
Katsotaan nyt, millaisia ongelmakohtaisia parametreja meidän on annettava geneeriselle toteutuksellemme.
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;Parametrit ovat vastaavasti:
- Crossover-operaattori
- Crossover-todennäköisyys
- Kelpoisuusfunktio
- Mutaatio-operaattori
- Mutaatiotodennäköisyys
- Populaation koko
- Aloituspopulaation kromosomitoimittaja
- Terminaatiofunktio
Näissä on konfiguraatiomme ongelmaa varten:
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()Risteytysoperaattori ja todennäköisyys
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;}Risteytyksen todennäköisyys on 0.25, joten odotamme, että keskimäärin 25 prosenttia kromosomeista valitaan risteytykseen. Suoritamme yksinkertaisen menettelyn kromosomiparin ristiinkytkennälle. Generoimme satunnaisluvun n alueelta , jossa length on kromosomin pituus. Nyt paritamme valitun parin ottamalla ensimmäiset n merkit yhdestä kromosomista ja loput merkit sen jälkeen toisesta kromosomista.
Kelpoisuusfunktio
private double fitness(char value) { return range(0, value.length) .filter(i -> value == expected) .count();}Kelpoisuusfunktio yksinkertaisesti laskee kohdelausekkeen ja annetun kromosomin välisten osumien lukumäärän.
Mutaatio-operaattori ja -todennäköisyys
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;}Mutaatio-operaatio suoritetaan kumpaankin kromosomiin erikseen. Mutaation todennäköisyys on 0,05, joten odotamme, että keskimäärin viisi prosenttia populaatiosta mutatoituu. Mutaatio suoritetaan valitsemalla satunnainen kirjainpaikka ja korvaamalla sen arvo satunnaisella kirjaimella aakkosista. Teemme tämän kahdesti jokaiselle mutatoituneelle kromosomille.
Toimittaja
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;}Toimittaja luo satunnaisia lauseita ottamalla aakkosista satunnaisia kirjaimia. Jokaisella lauseella on vakio ennalta määritetty pituus.
Terminaatiofunktio
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;}Terminaatiofunktio laskee kutsujen lukumäärän ja palauttaa true, jos löytyy joko tarkka täsmällinen vastaavuus tai jos sukupolvien määrä saavuttaa 3000.
Toteutus
Nyt olemme valmiita testaamaan algoritmiamme. Jos suoritat sen useita kertoja, huomaat, että kaikki suoritukset eivät onnistu. Joka kerta iteraatioiden määrä on erilainen. Tämä johtuu algoritmin todennäköisyydestä. Algoritmissa on useita kohtia, joissa sitä voidaan parantaa. Voit leikkiä risteytys- ja mutaatiotodennäköisyyksillä.
Luvun pienentäminen johtaa vakaaseen mutta hitaaseen ratkaisuun. Geneettiset operaattorit vaikuttavat pienempään määrään kromosomeja, joten ratkaisuun tarvitaan enemmän iteraatioita.
Lukumäärän kasvattaminen nopeuttaa algoritmia, mutta tekee ratkaisusta myös epävakaan. Sopivat kromosomit eivät ainoastaan säily, vaan geneettiset operaattorit vaikuttavat niihin. Siksi ne menettävät “hyvät” geeninsä.
On tärkeää löytää hyvä tasapaino. Iteraatioiden määrän lisääminen antaa algoritmille enemmän mahdollisuuksia löytää ratkaisu, mutta toisaalta se vie enemmän aikaa. Voit myös soveltaa erilaisia risteytys- ja mutaatiomenetelmiä. Näiden operaattoreiden hyvä valinta parantaa ratkaisun laatua huomattavasti.
Olemme käsitelleet tässä vain jäävuoren huippua. Otimme esimerkin, jossa on vain yksi syöte, ja syöte voidaan helposti esittää kromosomina. Geneettiset operaattorit ovat selkeitä ja yksinkertaisia.
On hyvin mielenkiintoista ottaa todellinen ongelma ja soveltaa geneettistä algoritmia siihen. Löydät erilaisia lähestymistapoja todellisen syötetiedon koodaamiseen sekä erilaisia crossover- ja mutaatiototeutuksia.
Jos ongelma voidaan ilmaista joukolla parametreja, jotka meidän on arvattava optimoidaksemme metriikkaa, voimme nopeasti laatia GA:n, jota voimme käyttää sen ratkaisemiseen.
Yksi mielenkiintoisimmista ongelmista on keinotekoisten neuroverkkojen opettaminen. Voimme asettaa optimoitaviksi parametreiksi synapsien voimakkuudet ja kuntomittariksi niiden syötteiden prosenttiosuuden, joihin neuroverkkomme antoi oikean vastauksen. Tämän jälkeen voimme istua alas ja antaa neuroverkkomme kehittyä haluamallemme ideaaliratkaisulle. Tai ainakin kunnes saamme jotain riittävän hyvää, sillä evoluutio vie aikaa.