Evolucijski algoritam

Potpuni ispis nakon pokretanja programa poznatog pod nazivom Dawkinsova lasica koji evoluira 100 jedinki po generaciji s 5% vjerojatnoti pojave mutacije prilikom kopiranja svakog pojedinog slova. Samo najsposobnija jedinka/string je prikazan po svakoj generaciji. Možete primijetiti da u osmoj generaciji 25. znak, koji je bio točno pogođen (A), postaje ponovo netočan znak (I). Program ne "zaključava" točno pogođene znakove, nego pri svakoj iteraciji mjeri koliko je cijeli string blizu stringu znakova ciljne fraze.

U računalnoj inteligenciji (CI), evolucijski algoritam (EA) je generički metaheuristički optimizacijski algoritam zasnovan na populacijama i podvrsta je evolucijskog računarstva. EA koristi mehanizme nadahnute biološkom evolucijom, poput reprodukcije, mutacije, rekombinacije i selekcije. Kandidati rješenja problema optimizacije igraju ulogu pojedinih organizama tj. jedinki u populaciji, a funkcija sposobnosti preživljavanja, ili kraće fitnesa, određuje kvalitetu svakog od ponuđenih rješenja u pojedinoj generaciji. Pokretanjem računanja nakon apliciranja gore navedenih operatora nastupa Evolucija populacije rješenja.

Evolucijski algoritmi često jako dobro izvršavaju zadaće pronalaženja aproksimativnih rješenja svih vrsta problema jer u idealnom slučaju inicijalno ne pretpostavljaju osnovni krajolik fitnesa tj. adaptivni krajolik. Tehnike evolucijskih algoritama primijenjene na modeliranje biološke evolucije uglavnom su ograničene na istraživanja mikroevolucijskih procesa i modela planiranja temeljenih na staničnim procesima. U većini stvarnih primjena računska složenost EA algoritama je ograničavajući faktor za raširenost primjene ovakve vrste računalne optimizacije. Spomenuta razmjerno velika računska složenost uglavnom je rezultat složenog računanja funkcije sposobnosti preživljavanja tj. fitnes funkcije. Jedan od načina da se ta složenost umanji je korištenje tehnika za aproksimaciju fitnes funkcije. Svejedno, ipak je poznato da naizgled jako jednostavan evolucijski algoritam često može riještiti i vrlo složene probleme tako da je moguće da ne mora postojati izravna i čvrsta veza između složenosti samog problema i složenosti potrebnog evolucijskog mehanizma da se problem riješi.

Implementacija

Slijedi primjer generičkog genetskog algoritma s jedinstvenim ciljem:

Prvi korak: Nasumično generiramo početnu populaciju jedinki. (Prva generacija)

Drugi korak: Ponavljamo sljedeće regeneracijske korake do završetka optimizacije:

1. Procijenjujemo fitnes svake jedinke u populaciji (uz kriterij vremenskog ograničenja, postignutog dovoljnog fitnesa itd.)
2. Selektiramo najsposobnije jedinke za reprodukciju. Te jedinke predstavljaju roditelje novoj generaciji.
3. Razmnožavamo nove jedinke koristeći operacije križanja i mutacije kako bi stvorili potomstvo.
4. Zamijenimo jedinke s najmanjom sposobnošću preživljavanja (fitnesom) u postojećoj generaciji populacije s novim jedinkama potomcima.

Darwinova lasica

Dobar primjer evolucijskog tj. genetičkog algoritma je takozvana Dawkinsova lasica poznata i pod nazivom Weasel program. Richard Dawkins ga je opisao u svojoj knjizi Slijepi urar a od tada se često koristi kao ilustracija mogućnosti genetskih algoritama.

import random


def generate_random_sequence(goal, characters):
    sequence = ""
    for i in range(len(goal)):
        sequence += characters[random.randint(0, len(characters)-1)]
    return sequence


def get_score(sequence, goal):
    score = 0
    for i in range(len(goal)):
        if goal[i] == sequence[i]:
            score += 1
    return score


def mutate_sequence(sequence, characters):
    result = ""
    for i in range(len(sequence)):
        if random.randint(0, 100) <= 5:
            result += characters[random.randint(0, len(characters)-1)]
        else:
            result += sequence[i]
    return result


def get_sequence_mutations(sequence, characters):
    sequence_list = []
    for i in range(100):
        sequence_list.append(mutate_sequence(sequence, characters))
    return sequence_list


def get_mutated_sequence(sequence, goal, characters):
    sequence_list = get_sequence_mutations(sequence, characters)
    best_seq = sequence_list[0]
    best_similarity_factor = get_score(best_seq, goal)
    for seq in sequence_list:
        similarity_factor = get_score(seq, goal)
        if similarity_factor > best_similarity_factor:
            best_similarity_factor = similarity_factor
            best_seq = seq
    return best_seq


def main():
    goal = "METHINKS IT IS LIKE A WEASEL"
    characters = "ABCDEFGHIJKLMNOPQRSTUVWXYZ "
    generations = 0
    current_sequence = generate_random_sequence(goal, characters)
    print("Generation", generations, ":", current_sequence)
    while current_sequence != goal:
        current_sequence = get_mutated_sequence(
            current_sequence, goal, characters)
        generations += 1
        print("Generation", generations, ":", current_sequence)


main()

Ono što je posebno zanimljivo je to da se procjenjuje da bi i najmoćnijim konvencionalnim superračunalima današnjice brute force nasumičnim algoritmom trebalo nekoliko milijuna milijuna godina da ispravno pogode zadani niz od 28 znakova, dok je vaše obično kućno računalo koristeći gore opisani genetski algoritam sposobno pogoditi zadani niz u nekoliko sekundi. Na taj način najbolje ilustriramo razliku između nasumičnog procesa pogađanja i evolucije koja je pokretana također nasumičnim mutacijama, ali je istovremeno vođena ne-nasumičnim mehanizmom prirodne selekcije.

Vrste

Slične tehnike razlikuju se u reprezentaciji gena i ostalim detaljima implementacije te u prirodi primjene na pojedinu vrstu problema:

• Genetski algoritam - ovo je najpopularnija vrsta EA. Rješenje problema traži se u obliku nizova brojeva (tradicionalno binarnih, premda su najbolji prikazi obično oni koji odražavaju prirodu problema koji se rješava), primjenom operatora kao što su rekombinacija i mutacija (ponekad jedan, ponekad oba). Ova vrsta EA često se koristi za rješavanje problema optimizacije .
• Genetsko programiranje - Ovdje su rješenja u obliku računalnih programa, a njihov fitnes je određen sposobnošću rješavanja zadanog računalnog problema.
• Evolucijsko programiranje - slično genetskom programiranju, ali je struktura programa fiksna te je dopušten razvoj njegovih numeričkih parametara.
• Programiranje ekspresije gena - Poput genetskog programiranja, GEP također evoluira računalne programe, ali istražuje sustav genotip-fenotip, gdje su računalni programi različitih veličina kodirani u linearne kromosome fiksne duljine.
• Strategija evolucije - Radi s vektorima realnih brojeva koji predstavljaju rješenja i obično koristi stope samoadaptirajuće mutacije.
• Diferencijalna evolucija - Temelji se na vektorskim razlikama i stoga je prvenstveno pogodan za probleme numeričke optimizacije.
• Neuroevolucija - Slično genetskom programiranju, ali genomi predstavljaju umjetne neuronske mreže opisujući strukturu i težinu neuronskih veza. Kodiranje genoma može biti izravno ili neizravno.
• Učenje sustava klasifikatora - ovdje je rješenje skup klasifikatora (pravila ili uvjeta). Michigan-LCS evoluira na razini pojedinačnih klasifikatora, dok Pittsburgh-LCS koristi populacije skupova klasifikatora. U početku su klasifikatori bili samo binarni, ali sada uključuju realne brojeve kao i neuronske mreže. Fitnes se obično određuje putem snage povratne mreže ili se točnost temelji na mašinskom učenju.

Usporedba s biološkim procesima

Moguće ograničenje mnogih evolucijskih algoritama je to što u njima nedostaje jasna razlika između genotipa i fenotipa. U prirodi, oplođena jajna stanica prolazi kroz složeni proces poznat kao embriogeneza kako bi poprimila oblik odraslog fenotipa. Vjeruje se da ovo neizravno kodiranje genetsku pretragu čini robusnijom (npr. smanjuje vjerojatnost fatalnih mutacija), a također može poboljšati evolubilnost organizma. Takvo neizravno (tj. generativno ili razvojno) kodiranje također omogućava procesu evolucije iskorištavanje regularnosti u okolišu. Nedavni radovi na polju umjetne embriogeneze tj. proučavanja umjetnih razvojnih sustava nastoje riješiti ove probleme. I programiranje putem ekspresije gena uspješno istražuje vezu genotip-fenotip, gdje se genotip sastoji od linearnih multigenih kromosoma fiksne duljine, a fenotip se sastoji od više stabala ekspresije ili računalnih programa različitih veličina i oblika.

Povezane tehnike

Rojni algoritmi koji uključuju:

• Optimizacija kolonije mrava - Na temelju spoznaja o mravljem istraživanju terena potpomognutim feromonskom komunikacijom kako bi se stvorili utabani putovi. Primarno pogodan za kombinatornu optimizaciju i probleme s grafovima .
• Runner-root algoritam (RRA) nadahnut je funkcijom klica i korijena biljaka u prirodi
• Algoritam umjetne košnice - Temelji se na ponašanju pčela kod potrage za hranom. Prvenstveno predlagan za korištenje u numeričkoj optimizaciji i proširen za korištenje u rješavanju kombinatornih, ograničenih i višeciljnih problema optimizacije.
• Algoritam pčela temelji se na ponašanju pčela medonoša. Primijenjen je u mnogim aplikacijama kao što su usmjeravanje i raspoređivanje.
• Kukavičja pretraga nadahnuta je mračnim parazitizmom vrste ptica kukavice. Ova tehnika također koristi Lévyjeve letove pa je stoga pogodna za rješavanje problema globalne optimizacije.
• Elektronska optimizacija - Na temelju ponašanja toka elektrona kroz grane električnog kruga s najmanjim električnim otporom.
• Particle Swarm optimizacija - Na temelju spoznaja o ponašanju životinja koje stvaraju jato. Također prvenstveno pogodan za probleme numeričke optimizacije .

Primjeri

Google je 2020. izjavio da njihov AutoML-Zero može uspješno poptpuno samostalno otkriti tj. izumiti klasične algoritme poput koncepta neuronskih mreža.

Računalne simulacije Tierra i Avida pokušavaju modelirati makroevolucijsku dinamiku.

Galerija

• 
  EA pretraga s dvije populacije preko ograničene Rosenbrockove funkcije s ograničenim globalnim optimumom.
• 
  EA pretraga s dvije populacije preko ograničene Rosenbrockove funkcije . Globalni optimum nije ograničen.
• 
  Procjena algoritma distribucije nad Keaneovom funkcijom
• 
  EA pretraga ograničene optime Simionescuove funkcije s dvije populacije.

Bibliografija

• Ashlock, D. (2006), Evolucijsko računanje za modeliranje i optimizaciju, Springer,ISBN 0-387-22196-4 .
• Bäck, T. (1996), Evolucijski algoritmi u teoriji i praksi: Evolucijske strategije, Evolucijsko programiranje, Genetički algoritmi, Oxford Univ. Pritisnite.
• Bäck, T., Fogel, D., Michalewicz, Z. (1997), Priručnik evolucijskog računanja, Oxford Univ. Pritisnite.
• Banzhaf, W., Nordin, P., Keller, R., Francone, F. (1998), Genetsko programiranje - uvod, Morgan Kaufmann, San Francisco
• Eiben, AE, Smith, JE (2003), Uvod u evolucijsko računanje, Springer.
• Holland, JH (1992), Prilagodba u prirodnim i umjetnim sustavima, Sveučilište Michigan Press, Ann Arbor
• Michalewicz Z., Fogel DB (2004.). Kako to riješiti: Moderna heuristika, Springer.
• Benko, Attila; Dosa, Gyorgy; Tuza, Zsolt (2010). "Bin Packing/Covering with Delivery, solved with the evolution of algorithms". 2010 IEEE Peta međunarodna konferencija o bio-nadahnutom računanju: teorije i primjene (BIC-TA). str. 298–302. doi : 10.1109 / BICTA.2010.5645312. ISBN Benko, Attila; Dosa, Gyorgy; Tuza, Zsolt (2010). "Bin Packing/Covering with Delivery, solved with the evolution of algorithms". Benko, Attila; Dosa, Gyorgy; Tuza, Zsolt (2010). "Bin Packing/Covering with Delivery, solved with the evolution of algorithms". S2CID 16875144 .
• Poli, R.; Langdon, W. B.; McPhee, N. F. (2008). Terenski vodič za genetsko programiranje. Lulu.com, slobodno dostupan s Interneta. ISBN Poli, R.; Langdon, W. B.; McPhee, N. F. (2008). Poli, R.; Langdon, W. B.; McPhee, N. F. (2008). izvornika 27. svibnja 2016. Pristupljeno 05.03.2011. [ izvor koji je sam objavio ]
• Price, K., Storn, RM, Lampinen, JA, (2005). "Diferencijalna evolucija: praktični pristup globalnoj optimizaciji", Springer.
• Ingo Rechenberg (1971): Evolutionsstrategie - Optimierung technischer Systeme nach Prinzipien der biologischen Evolution (doktorska disertacija). Pretisnuo Fromman-Holzboog (1973).
• Hans-Paul Schwefel (1974): Numerische Optimierung von Computer-Modellen (doktorska disertacija). Pretisnuo Birkhäuser (1977).
• Simon, D. (2013): Evolucijski algoritmi za optimizaciju  Arhivirana inačica izvorne stranice od 10. ožujka 2014. (Wayback Machine), Wiley.
• Računalna inteligencija: metodološki uvod Krusea, Borgelta, Klawonna, Moewesa, Steinbrechera, održanog, 2013, Springer,ISBN 978-1-4471-5012-1
• Rahman, Rosshairy Abd. 2017. Shrimp Feed Formulation via Evolutionary Algorithm with Power Heuristics for Handling Constraints. Complexity. 2017: 1–12

Vanjske poveznice

• Pregled povijesti i okusi evolucijskih algoritama