Teknologia
Geneettiset algoritmit: haku ja optimointi luonnollisella valinnalla
Mitä ovat geneettiset algoritmit?
Viime vuosina keinotekoinen älykkyys (AI) on ollut kohinaa. Suuret yritykset, kuten Google, Apple ja Microsoft, työskentelevät aktiivisesti tämän ongelman parissa. Itse asiassa tekoäly on vain sateenvarjo, joka kattaa monia tavoitteita, lähestymistapoja, työkaluja ja sovelluksia. Geneettiset algoritmit (GA) ovat vain yksi älykkäistä työkaluista, jotka etsivät monia mahdollisia ratkaisuja.
AG on metaheuristinen haku sekä optimointitekniikka, joka perustuu luonnollisessa evoluutiossa esiintyviin periaatteisiin. Se kuuluu pidempään evoluutioalgoritmien luokkaan.
AG ylläpitää a kromosomipopulaatio —Joukko mahdollisia ratkaisuja ongelmaan. Ajatuksena on, että 'evoluutio' löytää optimaalisen ratkaisun ongelmaan useiden peräkkäisten sukupolvien jälkeen - samanlainen kuin luonnollinen valinta.
AG jäljittelee kolmea evoluutioprosessia: valinta, kromosomien ylitys ja mutaatio.
Luonnollisen valinnan tavoin AG-valinnan keskeinen käsite on sopeutuminen. Paremmin sopeutuvilla kromosomeilla on paremmat mahdollisuudet selviytyä. Sopeutuminen on toiminto, joka mittaa kromosomin edustaman liuoksen laatua. Pohjimmiltaan kukin kromosomi populaatiossa edustaa syöttöparametreja, kuten tilavuus ja vaihtokurssi, kukin kromosomi koostuu loogisesti kahdesta elementistä. Se, miten elementit koodataan kromosomissa, on toinen asia.
Valinnan aikana kromosomit muodostavat paria vanhemmat varten jäljentäminen . Jokainen lapsi ottaa huomioon hänen vanhempiensa ominaisuudet. Periaatteessa lapsi edustaa vanhempiensa ominaisuuksien rekombinaatiota: Osa ominaisuuksista on otettu yhdeltä vanhemmalta ja osa toisilta. Rekombinaation lisäksi jotkut ominaisuudet voivat muuttua .
Koska sopivimmat kromosomit tuottavat enemmän lapsia, jokainen seuraava sukupolvi on sopivampi. Jossain vaiheessa sukupolvi sisältää kromosomin, joka edustaa riittävän hyvää ratkaisua ongelmaan.
AG on tehokas ja laajasti sovellettavissa monimutkaisiin ongelmiin. On olemassa laaja joukko optimointiongelmia, joita on jonkin verran vaikea ratkaista käyttämällä perinteisiä optimointitekniikoita. Geneettiset algoritmit ovat tehokkaita algoritmeja, joilla on suunnilleen optimaaliset ratkaisut. Tunnettuja sovelluksia ovat aikataulut, kuljetus, reittisuunnittelu, ryhmäteknologiat, suunnitelmien suunnittelu, hermoverkkokoulutus ja monet muut.
Asioiden toteuttaminen käytännössä
Esimerkkiä, jota näemme, voidaan pitää AG: n 'Hello World'. Tämän esimerkin esitti alun perin J.Freeman vuonna Neuroverkkojen simulointi Mathematican avulla . Otin sen Geneettiset algoritmit ja tekninen suunnittelu Mitsuo Gen ja Runwei Cheng.
Maailman simulointiongelma yrittää kehittää lauseketta geneettisellä algoritmilla. Aluksi algoritmin on 'arvattava' lause 'olla tai olla' satunnaisesti tuotetuista kirjainluetteloista.
Koska luettelossa on 26 mahdollista kirjainta kullekin 13 sijainnista (lukuun ottamatta tyhjiä kohtia), mahdollisuus saada oikea lause puhtaasti satunnaisesti on (1/26) ^ 13 = 4,03038 × 10-19, joten mikä on noin kaksi mahdollisuutta [biljoonaan] (Gen & Chong, 1997).
Aiomme määritellä ongelman hieman enemmän tekemällä ratkaisun vielä vaikeampaa. Oletetaan, että emme ole rajoittuneet englannin kieleen tai tiettyyn lauseeseen. Voimme päätyä käsittelemään mitä tahansa aakkosia tai jopa mitä tahansa symboleja. Meillä ei ole kielitaitoa. Emme edes tiedä onko kieliä.
Sanotaan, että vastustajamme ajatteli mielivaltaisen lauseen, mukaan lukien aihiot. Tiedämme lauseen pituuden ja aakkosien symbolien määrän. Se on ainoa tieto, joka meillä on. Jokaisen arvauksen jälkeen vastustaja kertoo meille, kuinka monta kirjainta hänen tilallaan on.
Jokainen kromosomi on aakkosjärjestyksessä olevien indeksien sekvenssi. Jos puhumme englannin aakkosista, niin a: ta edustaa 0, b: tä 1: llä, c: tä 2: lla ja niin edelleen. Joten esimerkiksi sana 'olla' esitetään muodossa [4, 1].
Esittelemme kaikki vaiheet Java-koodinpalojen kautta, mutta tieto Java jokaista vaihetta ei tarvitse ymmärtää.
Geneettisen algoritmin keskus
Voimme aloittaa geneettisen algoritmin yleisestä toteutuksesta:
public void find() { // Initialization List 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 joukko yksinkertaisia vaiheita, jotka jokaisella AG: llä pitäisi olla. Alkuvaiheessa luodaan ensimmäinen lausejoukko. Populaation koko määräytyy populationSize Ja kuinka tämä lause syntyy, riippuu supplier -sovelluksen toteutuksesta.
Iteraatiovaiheessa kehitämme populaatiota, kunnes termiehdot täyttyvät, solmutestin while sisällä. Ehto-olosuhteet voivat sisältää sukupolvien lukumäärän ja yhden väestön lauseen täydellisen yhteensopivuuden. termination sisältää tarkan toteutuksen.
Jokaisessa iteraatiossa teemme tyypilliset AG-vaiheet:
- Se valitsee populaation kromosomien riittävyydestä.
- Tuottaa uuden 'sukupolven' crossover-toiminnolla.
- Se suorittaa rekombinaation joistakin kirjaimista joissakin lauseissa.
Algoritmin ydin on hyvin yksinkertainen ja toimialueen agnostinen. Se olisi sama kaikissa ongelmissa. Mitä sinun on mukautettava, on geneettisten toimijoiden toteutus. Sitten tarkastelemme tarkemmin kaikkia edellä mainittuja AG-operaattoreita.
Valinta
Kuten jo tiedämme, valinta on prosessi, jolla löydetään nykyisten kromosomien seuraajat - kromosomit, jotka parhaiten sopivat ongelmasi. Valinnan aikana meidän on varmistettava, että parhaiten yhteensopivilla kromosomeilla on paremmat mahdollisuudet selviytyä.
private List selection(List population) { final double[] fitnesses = population.stream() .mapToDouble(fitness) .toArray(); final double totalFitness = DoubleStream.of(fitnesses).sum(); double sum = 0; final double[] probabilities = new double[fitnesses.length]; for (int i = 0; i { int index = binarySearch(probabilities, random()); if (index <0) { index = -(index + 1); } return population.get(index); }).collect(toList()); } Tämän toteutuksen idea on seuraava: Väestö on esitetty seurauksena piirteitä numeerisella akselilla. Koko väestö on välillä 0 ja 1.
Kromosomin ottaman sarjan osa on verrannollinen sen riittävyyteen. Tämä johtaa paljon sopivampaan kromosomiin, joka vie suuremman palan. Sitten valitsemme satunnaisesti luvun 0 ja 1 välillä ja löydämme sarjan, joka sisältää tämän numeron. On selvää, että suuremmilla sarjoilla on paremmat mahdollisuudet valituksi, joten sopivimmilla kromosomeilla on paremmat mahdollisuudet selviytyä.
Koska emme tiedä yksityiskohtia kunto-toiminnosta, meidän on normalisoitava kuntoarvot. Kuntofunktiota edustaa fitness, joka muuttaa kromosomin mielivaltaiseksi kaksoiskappaleeksi, joka edustaa kromosomin kuntoa.
Koodista löydämme vastaavuusprosentin kaikille populaation kromosomeille ja löydämme myös koko vastaavuuden. Solmun for sisällä suoritamme kumulatiivisen summan yli todennäköisyyksien, jotka ovat pienentyneet kokonaissovituksella. Matemaattisesti tämän pitäisi johtaa lopullisen muuttujan arvoon 1. Liukuluvun epätarkkuuden vuoksi emme voi taata sitä, joten asetamme sen arvoon 1 turvalliseksi.
Lopuksi, generoimme satunnaislukumäärän ajan, joka on yhtä suuri kuin saapuvien kromosomien lukumäärä, löydämme sarjan, joka sisältää luvun, ja valitsemme sitten vastaavan kromosomin. Kuten olet ehkä huomannut, sama kromosomi voidaan valita monta kertaa.
Crossover
Nyt tarvitaan kromosomeja 'lisääntymään'.
private void crossover(List population) { final int[] indexes = range(0, population.size()) .filter(i-> random() Kun todennäköisyys on ennalta määritelty nimellä crossoverProbability, valitsemme vanhemmat jalostukseen. Valitut vanhemmat ovat sekoitettuja, mikä mahdollistaa minkä tahansa yhdistelmän tekemisen. Otamme vanhempapareja ja käytämme operaattoria crossover Käytämme operaattoria kahdesti kullekin parille, koska meidän on pidettävä populaatiokoko samana. Lapset korvaavat vanhemmat väestössä.
Mutaatio
Lopuksi suoritamme ominaisuuksien rekombinaation.
private void mutation(List population) { for (int i = 0; i Todennäköisyydellä mutationProbability ennalta määritelty, suoritamme 'mutaation' kromosomeissa. Mutaatio sinänsä määritellään seuraavasti: mutation
Ongelmakohtainen algoritmin määritys
Katsotaan nyt, minkä tyyppiset ongelmaparametrit meidän on tarjottava yleiseen toteutukseen.
private BiFunction crossover; private double crossoverProbability; private ToDoubleFunction fitness; private Function mutation; private double mutationProbability; private int populationSize = 100; private Supplier supplier; private Predicate termination; Parametrit ovat vastaavasti: 1. Crossover-operaattori 2. Crossover-todennäköisyys 3. Soveltuvuustoiminto 4. Mutaatio-operaattori 5. Mutaation todennäköisyys 6. Populaation koko 7. Kromosomintarjoaja alkuperäiselle populaatiolle 8. Funktion termi
Tässä on ongelmamme kokoonpano:
new GeneticAlgorithm() .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-operaattori 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; } Crossoverin todennäköisyys on 0,25, joten odotamme, että keskimäärin 25 prosenttia kromosomeista valitaan crossoverille. Suoritamme yksinkertaisen menettelyn kromosomiparin risteytykselle. Luomme satunnaisluvun n valittavaksi [0..length], missä length on kromosomin pituus. Liitymme nyt valittuun pariin ottamalla ensimmäinen symboli n yhden kromosomista ja loput symboleista toisen jälkeen.
Riittävä toiminto
private double fitness(char[] value) { return range(0, value.length) .filter(i -> value[i] == expected[i]) .count(); } Oikea toiminto laskee yksinkertaisesti avainlauseen ja annetun kromosomin välisten yhdistelmien määrän.
Mutaatio- ja todennäköisyysoperaattori
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[location] = ALPHABET[letter]; } return result; } Mutaatiooperaatio suoritetaan itsenäisesti kussakin kromosomissa. Mutaation todennäköisyys on 0,05, joten odotamme, että keskimäärin viisi prosenttia populaatiosta mutatoituu. Mutaatio tapahtuu valitsemalla satunnaisen kirjaimen sijainti ja korvaamalla sen arvo aakkosen satunnaisella kirjaimella. Teemme sen kahdesti jokaiselle mutatoidulle kromosomille.
Palveluntarjoaja
private char[] supplier(int length) { final char[] result = new char(length); for (int i = 0; i Palveluntarjoaja tuottaa lauseita satunnaisesti ottamalla aakkoset yhtä satunnaisesti. Jokaisella lauseella on ennalta määritelty vakiopituus.
Termi Toiminto
private boolean termination(Collection chars) { count++; final Optional 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; } Termi-funktio laskee puheluiden määrän ja palauttaa true, jos täsmällinen vastaavuus on jo olemassa tai jos sukupolvien määrä saavuttaa 3000.
Suoritus
Nyt olemme valmiita testaamaan algoritmiamme. Jos suoritat sen useita kertoja, huomaat, että kaikki ajot 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 pelata crossover- ja mutaatiotodennäköisyydellä.
Laske numero vakaan mutta hitaaseen ratkaisuun. Geneettiset toimijat vaikuttavat pienempään määrään kromosomeja, joten liuokseen tarvitaan enemmän iteraatioita.
Lukujen lisääminen nopeuttaa algoritmia, mutta se tekee ratkaisusta myös epävakaan. Oikeat kromosomit eivät vain säily, vaan myös geneettiset toimijat vaikuttavat niihin. Tästä syystä he menettävät 'hyvät' geeninsä.
On tärkeää löytää hyvä tasapaino. Toistojen määrän lisääminen antaa algoritmille enemmän mahdollisuuksia löytää ratkaisu, mutta toisaalta se vie enemmän aikaa. Käytä myös erilaisia menetelmiä crossoverille ja mutaatiolle. Hyvä valinta näistä operaattoreista parantaa ratkaisun laatua dramaattisesti.
Mitä seuraavaksi?
Olemme peittäneet vain jäävuoren kärjen. Otamme esimerkin, jolla on vain yksi merkintä ja joka voidaan helposti esittää kromosomina. Geneettiset operaattorit ovat yksinkertaisia.
On erittäin mielenkiintoista ottaa ongelma tosielämästä ja soveltaa siihen geneettistä algoritmia. Löydät erilaisia lähestymistapoja todellisten tietopanosten koodaamiseen sekä erilaisia crossoverin ja mutaation toteutuksia.
Jos ongelma voidaan ilmaista joukolla parametreja, jotka meidän on arvattava metriikan optimoimiseksi, voimme nopeasti perustaa AG: n, jolla voimme ratkaista sen.
Yksi mielenkiintoisimmista ongelmista on keinotekoisten hermoverkkojen opettaminen. Voimme asettaa optimoidut parametrit synapsivoimiksi ja siten, että sopiva metri on prosenttiosuus tuloista, joille hermoverkkoomme ovat antaneet oikean vastauksen. Sen jälkeen voimme rentoutua ja antaa hermoverkkojemme kehittyä haluamallemme ihanteelliselle ratkaisulle. Tai ainakin siihen asti, kunnes meillä on jotain tarpeeksi hyvää, koska evoluutio vie aikaa.
