Evolucijski algoritam

Izvor: Wikipedija
Prijeđi na navigaciju Prijeđi na pretraživanje
Potpuni ispis nakon pokretanja programa poznatog pod nazivom Dawkinsova lasica koji evoluira 100 jedinki po generaciji sa 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.[1] 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.[2] 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[uredi VE | uredi]

Slijedi primjer generičkog genetskog algoritma sa 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 sa najmanjom sposobnošću preživljavanja (fitnesom) u postojećoj generaciji populacije sa novim jedinkama potomcima.

Darwinova lasica[uredi VE | uredi]

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 sys
sys.path.append('C:\\Python27\\CherryPy-3.2.2')
import cherrypy
import random
import string

CONST_STR = "METHINKS IT IS LIKE A WEASEL"
CONST_SIZE = 100
CONST_PROB = 5


def genRandChar():  # print random uppercase letter or whitespace
    """Return random uppercase letter or whitespace."""
    return random.choice(string.ascii_uppercase + string.whitespace)


def genRandStr():   # print random string of length CONST_STR
    """Return random string of length CONST_STR."""
    randStr = ''
    for x in range(0, len(CONST_STR)):
        randStr = randStr + genRandChar()
    return randStr


def compStr(randStr):   # compare CONST_STR with randStr
    """Return index of randStr -- number of common characters in randStr and CONST_STR."""
    randStrIndex = 0
    for i in range(0, len(CONST_STR)):
        if CONST_STR[i] == randStr[i]:
            randStrIndex += 1
    return randStrIndex


def modRandStr(randStr):    # modify each character of randStr with probability CONST_PROB%
    """Return modified randStr -- each character of randStr is modified with probability CONST_PROB%."""
    newRandStr = randStr
    for x in range(0, len(CONST_STR)):
        randInt = random.randint(1, 100)
        if randInt <= CONST_PROB:
            newRandStr = newRandStr[:x] + genRandChar() + newRandStr[x + 1:]
    return newRandStr


class WeaselProgram:
    def index(self):
        loopNumber = 0
        strFound = False
        randStr = genRandStr()
        resultList = []
        while not strFound:
            strList = [''] * CONST_SIZE
            indexList = [None] * CONST_SIZE
            for x in range(0, CONST_SIZE):
                strList[x] = modRandStr(randStr)
                indexList[x] = compStr(strList[x])
            maxIndex = max(indexList)
            if maxIndex == len(CONST_STR):
                strFound = True
            randStr = strList[indexList.index(maxIndex)]
            resultList.append(str(loopNumber) + ": " + randStr + " -- score: " + str(maxIndex))
            loopNumber += 1
        return '<br>'.join(resultList)
    index.exposed = True

cherrypy.quickstart(WeaselProgram())

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[uredi VE | uredi]

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), [3] 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[uredi VE | uredi]

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. [4] Takvo neizravno (tj. generativno ili razvojno) kodiranje također omogućava procesu evolucije iskorištavanje regularnosti u okolišu. [5] 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. [6]

Povezane tehnike[uredi VE | uredi]

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 [7]
  • 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. [8]
  • Particle Swarm optimizacija - Na temelju spoznaja o ponašanju životinja koje stvaraju jato. Također prvenstveno pogodan za probleme numeričke optimizacije .

Primjeri[uredi VE | uredi]

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. [9]

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

Galerija[uredi VE | uredi]

[10]

Reference[uredi VE | uredi]

  1. Vikhar (2016). "Evolutionary algorithms: A critical review and its future prospects". Proceedings of the 2016 International Conference on Global Trends in Signal Processing, Information Computing and Communication (ICGTSPICC): 261–265
  2. (2003) Advances in evolutionary computing : theory and applications, Berlin: Springer ISBN 3-540-43330-9
  3. (2003) Advances in evolutionary computing : theory and applications, Berlin: Springer ISBN 3-540-43330-9
  4. G.S. Hornby and J.B. Pollack. "Creating high-level components with a generative representation for body-brain evolution". Artificial Life, 8(3):223–246, 2002.
  5. J. Clune, C. Ofria, and R. T. Pennock, "How a generative encoding fares as problem-regularity decreases", in PPSN (G. Rudolph, T. Jansen, S. M. Lucas, C. Poloni, and N. Beume, eds.), vol. 5199 of Lecture Notes in Computer Science, pp. 358–367, Springer, 2008.
  6. Ferreira, C., 2001. "Gene Expression Programming: A New Adaptive Algorithm for Solving Problems". Complex Systems, Vol. 13, issue 2: 87–129.
  7. F. Merrikh-Bayat, "The runner-root algorithm: A metaheuristic for solving unimodal and multimodal optimization problems inspired by runners and roots of plants in nature", Applied Soft Computing, Vol. 33, pp. 292–303, 2015
  8. Khalafallah Ahmed (1. svibnja 2011.). "Electimize: New Evolutionary Algorithm for Optimization with Application in Construction Engineering". Journal of Computing in Civil Engineering 25 (3): 192–201
  9. Gent, Edd. "Artificial intelligence is evolving all by itself", Science | AAAS, objavljeno 13. travnja 2020. pristupljeno 16. travnja 2020. (engleski) Arhivirano s izvorne stranice 16. travnja 2020.
  10. Simionescu (2004). "Constrained optimization problem solving using estimation of distribution algorithms": 1647–1653 pristupljeno 7. siječnja 2017.

vanjske poveznice[uredi VE | uredi]

Bibliografija[uredi VE | uredi]

  • 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, Wiley.
  • Računalna inteligencija: metodološki uvod Krusea, Borgelta, Klawonna, Moewesa, Steinbrechera, održanog, 2013, Springer,ISBN 978-1-4471-5012-1
  • Rahman (2017). "Shrimp Feed Formulation via Evolutionary Algorithm with Power Heuristics for Handling Constraints". Complexity 2017: 1–12