Geneetiline programmerimine e. GP

Kuna olen juba müsteeriumide lainel, siis mõtlesin, et kirjutan geneetilisest programmeerimisest e. GP-st. Gp on küllaltki müstiline iseenesest ja paljud ei võta evolutsioonilisi meetodeid reaalselt kasutatava vahendina. “Algorithm design manual” ütleb, et ainuke töötav metaheuristiline meetod on Simulated Annealing. “Metaheuristiline” tähendab laias laastus meetodit, mis iteratiivselt üritab  parandada olemasolevat lahendust mingi etteantud mõõdupuu järgi.

Gp-d siiski kasutavad täiesti tavalised progejad firmades, kui mitte igapäevaselt, siis vahest ikka. Tüüpiline situatsioon, kus on vaja leida bitte manipuleerides mingi rida käsklusi, mis annaks vajaliku funktsiooni, näiteks Intel SIMD instruktsioone  kasutades, lastakse huvi pärast ikka GP programmist läbi.

Müstiline on, et GP suudab töötada suuremas otsinguruumis edukamalt, kui lihtsalt Random otsing. See põhineb Building Block teoorial, mis põhimõtteliselt siis ütlebki, et Gp kasutab paremate lahenduste leidmiseks olemasolevaid häid lahendusi.

Võrreldes Gp-d Superoptimizeriga, mis töötab kusjuures ka mitte kõiki lahendusi läbi proovides, kuid siiski garanteerib lahenduse leidmise(kuigi see aeg võib olla aastasadu), siis suudab GP nimetatud bitioperatsioonide probleemi lahendada aktsepteeritava ajaga palju pikema lahenduse leidmiseks. Minu enda kogemus on, et Superoptimizer leidis umbes ~5 rea pikkuse assembleri koodijupi maksimaalselt. Samas situatsioonis GP leidis 8 rea pikkuse. Kindlasti on juhud, kus GP ei leia midagi, aga millegipärast ta leidis enamasti. Mingit statistikat ei postita sellle kohta, sest kes teab kuidas GP töötab, saab aru, et see on müstiline.

Mainiks veel seda, et isiklikult ei ole ma kunagi ühtagi “vajaminevat” lahendust leidnud GP-d kasutades. Kuid mängides selle ideega, tegin vapraid katsetusi masinnnägemise probleemi lahendamiseks, mis kasutas väga highlevel koodi ja olemasolevaid teeke. Andsin GP-le hulga masinnägemise primitiivseid operatsioone, millest ta pidi välja otsima nende õige jäjekorra ja parameetrid, mis aitaks tuvastada sarnastel piltidel eteantud ala. Sellega ta hakkama ei saanud, kuid üritus tundus tehtav olevat. Vähemalt olemasolev kirjandus toetas mu tööd. Tõenäoliselt ei andnud õigeid operatsioone GP-le, mille taha enamus kirjandus GP-d kaitstes poebki. GP koos Superoptimizeriga väiksemate ülesannete jaoks tundub vähem müstiline.

Kokkuvõttes nagu öeldakse, kes ei otsi, see ei leia.

Advertisements