Optimizacija z metahevristiko

Pozdravljeni v oddaji Frequenza della scienza znanstvene redakcije Radia Študent. V oddaji pred dobrim mesecem smo govorili o bioloških zdravilih, nocoj pa se bomo posvetili optimizaciji v tehniki in znanosti. Govorili bomo o uporabi evolucijskih algoritmov in inteligence rojev ter spoznali, kaj so metahevristične metode.

Obravnavali bomo probleme, ki so po navadi za običajne postopke optimizacije preveč zahtevni. Največkrat zato, ker tudi računalniki ne bi mogli preveriti vseh možnih rešitev in izbrati najboljše, čeprav bi imeli na voljo čas celotnega obstoja vesolja. Tako vam bomo v oddaji predstavili, kako lahko s posnemanjem naravnih procesov shekamo prepreke, ne da bi jih sploh do potankosti razumeli. Spoznali pa bomo tudi, kako lahko z računalniškim algoritmom, ki posnema obnašanje čebel, najdemo zelo dobro rešitev za probleme, ki jih je z eksaktnimi metodami nemogoče optimizirati.

V drugem delu oddaje bomo s spoznavanjem metahevristike videli, kako je mogoče te principe uporabiti pri preprekah, ki si jih zadajamo ljudje. Za začetek pa se spoznajmo z matematičnimi osnovami problemov, s katerimi se bomo ubadali v današnji oddaji.

V srednji šoli smo se pri matematiki nemara lahko naučili, kako najti največje razmerje med prostornino, ki jo lahko zajemamo s stožcem, in površino njegovega plašča. Treba je le izraziti, kako se spreminja volumen v odvisnosti od površine plašča. Izraz, ki povezuje prostornino stožca in površino plašča, najprej obdelamo z matematično operacijo, imenovano odvod.

Odvod nam namreč pove, kako hitro se prostornina spreminja, ko spreminjamo površino plašča stožca. Če poiščemo ničlo takega izraza ali odvoda, lahko zaradi njegovih zakonitosti nekaj izvemo tudi o prvotni povezavi med prostornino in površino. Ali natančneje, določimo lahko njuno optimalno razmerje. Optimalna rešitev je v tem primeru optimizacijskega problema samo ena, najdemo pa jo z domiselno uporabo srednješolske matematike.

Preden gremo na težje vrste matematičnih problemov, pa razjasnimo še osnovne pojme. Matematične probleme lahko rešujemo z algoritmi - torej z natančno določenim zaporedjem korakov, v katerih izvedemo določene matematične operacije. Če uporabimo analogijo s kuhanjem čaja, bi bila naloga skuhati čaj matematični problem, natančen recept za kuhanje čaja pa  algoritem za reševanje problema. Tako kot lahko čaj skuhamo na več načinov, velja tudi, da lahko posamezen matematični problem rešimo z več algoritmi.

Med optimizacijske probleme - torej probleme, kjer med vsemi rešitvami iščemo najboljšo - poleg iskanja največjega razmerja med prostornino in površino plašča stožca štejemo tudi matematični problem potujočega trgovca. Pričujoči problem se glasi takole: Trgovec ima seznam mest, ki jih mora obiskati, in ve, kolikšni so stroški za pot med poljubnima dvema mestoma. Ti stroški se med različnimi mesti razlikujejo, trgovec pa si želi po najcenejši poti obiskati vsako mesto natanko enkrat in se na koncu vrniti domov. Na videz se problem ne zdi preveč zahteven, a se je izkazalo, da spada med ene od najtežjih matematičnih problemov.

Kot smo že omenili, lahko posamezen matematični problem rešimo oziroma izračunamo na več načinov, torej z različnimi algoritmi. Algoritem pomeni namreč končno zaporedje operacij, ki, če mu sledimo, reši določen problem. Seveda pa si želimo med algoritmi, ki rešujejo isti problem, izbrati čim boljšega. To običajno pomeni, da iščemo čim hitrejšega. A kako definiramo hitrost samega algoritma?

Definicija gotovo vključuje čas reševanja posameznega matematičnega problema s konkretnimi podatki. Toda takih matematičnih problemov je neskončno: kot smo lahko videli, je pri problemu potujočega trgovca število mest lahko poljubno, prav tako so lahko stroški za pot med posameznimi pari mest poljubna pozitivna števila. Tako hitrosti algoritma očitno ne moremo oceniti z enim samim številom, ampak jo merimo s tako imenovano časovno zahtevnostjo algoritma.

Tako so pri problemu potujočega trgovca problemi z enako velikostjo vhodnih podatkov tisti, ki imajo enako število mest, stroški poti med dvema mestoma pa so za vsakega od teh problemov različni. Časovna zahtevnost algoritma nam pove največje število računskih korakov, ki jih pri določeni velikosti vhodnih podatkov potrebuje algoritem, da izračuna rešitev. Četudi je pri algoritmu število korakov končno, to ne pomeni vedno, da lahko za vsake konkretne podatke algoritem v razumnem času vrne rešitev problema. Nekateri algoritmi so lahko zaradi velikosti začetnih podatkov zelo počasni.

Matematično pravilno bi časovno zahtevnost algoritma opredelili kot funkcijo f(n), katere vrednost navzgor omeji število operacij za izvedbo algoritma pri vhodnih podatkih velikosti n. To seveda ne pomeni, da različni podatki enake velikosti terjajo enako število korakov algoritma.

Recimo, da nas zanima, ali je celoten strošek poti potujočega trgovca manjši od 2000 evrov. Da bi znali odgovoriti na to vprašanje, bi morali pregledati vsa možna zaporedja šestih mest, sešteti stroške med mesti in preveriti, ali je celoten strošek manjši od 2000 evrov. Vseh možnih zaporedij je 120, lahko pa se zgodi, da je že strošek prvega naključno izbranega zaporedja mest nižji od 2000 evrov in nam tako ni treba preverjati ostalih 119 vrstnih redov. V najslabšem primeru pa bi to zaporedje izbrali nazadnje, torej po tem, ko smo pregledali že vsa ostala zaporedja. Časovna zahtevnost bi bila v tem primeru 120 korakov.

Algoritme torej ocenjujemo s primerjavo njihovih časovnih zahtevnosti. Pri tem nas zanima predvsem, kako hitro časovna zahtevnost algoritma raste, ko rešujemo čedalje večje probleme. Od tega je namreč odvisno, kako velike probleme bomo z izbranim algoritmom še uspeli rešiti v doglednem času. Glede na hitrost rasti časovne zahtevnosti pa se lahko algoritmi med seboj drastično razlikujejo.

Razlika med algoritmi s polinomsko časovno zahtevnostjo, ki jih imenujemo tudi polinomski algoritmi, in tistimi z eksponentno časovno zahtevnostjo je bistvena. Čas izvajanja algoritmov pri večanju vhodnih podatkov se bistveno hitreje daljša pri algoritmih z eksponentno časovno zahtevnostjo kot pri tistih s polinomsko. Veča se tudi razlika v času izvajanja med polinomskimi in eksponentnimi algoritmi. Kako se čas daljša glede na časovno zahtevnost algoritma in kako se večajo razlike med polinomskimi in eksponentnimi algoritmi, ko povečamo velikost vhodnih podatkov, nam predstavi profesor Marko Petkovšek s Fakultete za matematiko in fiziko:

Recimo, da imamo ...

Zdaj, ko vemo, da so polinomski algoritmi tisti, katerih časovna zahtevnost je polinomska funkcija, pa si bomo ogledali, kaj so zahtevnostni razredi P, NP in NP-polnih problemov.

Razred P je pa razred ...

Zahtevnostni razredi nam tako povedo, kako zahtevne algoritme lahko pričakujemo za problem. V primeru potujočega trgovca se odločitvena verzija tega problema glasi: Ali obstaja pot, katere stroški so nižji od k evrov, pri enakih predpostavkah kot za prvotni problem. Ta problem potem spada vsaj v zahtevnostni razred NP, saj če nam nekdo prišepne, kakšna je najcenejša pot, z lahkoto preverimo, ali bo odgovor na vprašanje ‘Ali obstaja pot, katere stroški so nižji od k evrov?’ pritrdilen ali nikalen. Z razlago, kaj so NP-polni problemi, nadaljuje profesor Petkovšek.

No, potem so pa ...

Kot smo že omenili, algoritme ločujemo glede na časovno zahtevnost, matematične probleme pa lahko ločimo v zahtevnostne razrede P, NP in NP-polne. Četudi se problemi sprva zdijo zelo različni, so matematično enakovredni. Če najdemo učinkovit algoritem za nek NP-poln problem, recimo problem potujočega trgovca, znamo napisati učinkovit algoritem za igro potapljanja ladjic, Super Maria ali tetris in seveda vse ostale NP-polne probleme.

Še malo se vrnimo k problemu potujočega trgovca in si poglejmo možen algoritem za reševanje tega problema. Rešitev pričujočega problema je določen vrstni red oziroma permutacija mest. Najbolj direkten pristop bi bil, da preverimo vse permutacije in vrnemo tisto, katere pot je najcenejša. Vseh permutacij za n mest, kjer je n poljubno naravno število, je n-1 fakulteta. To je produkt vseh naravnih števil od ena do n-1. Če imamo 6 mest, moramo tako pregledati 1 krat 2 krat 3 krat 4 krat 5 možnosti, kar je enako 120, če pa je mest 11 pa skoraj štiri milijone. Vidimo, da število permutacij bliskovito narašča, še mnogo hitreje kot eksponentna funkcija.

Ker računalniki še nekaj časa ne bodo dovolj sposobni, da bi za neke realne primere z nekaj 100 mesti preverili vse permutacije ali pa računali rešitev z eksponentnimi algoritmi, so začeli razvijati tako imenovane aproksimacijske algoritme. To so algoritmi, ki vrnejo približen rezultat, a se jih uporablja, ker pridejo do rezultata veliko hitreje kot točni algoritmi. Pri aproksimacijskih algoritmih je pomembno vedeti, kako velika je lahko napaka, torej za koliko se dana rešitev razlikuje od optimalne.

Razjasnili smo si torej, da se ubadamo s problemi, ki imajo preveč možnih rešitev, da bi lahko učinkovito preverili vse in izbrali najboljšo. V nadaljevanju oddaje pa bomo govorili o metahevrističnih metodah, s katerimi naredimo aproksimacijske algoritme za reševanje optimizacijskih problemov. Kaj je to metahevristika, nam natančneje razloži dr. Bogdan Filipič z Inštituta Jožef Stefan.

Torej najprej je tako, da že seveda ...

Če se ozremo okoli sebe, lahko hitro vidimo, da na vsakem koraku resnični svet ponuja nešteto podobno kompleksnih problemov. Kljub temu pa pri opazovanju vseh oblik življenja vidimo, da se organizmi s časom prilagodijo in uspešneje premagujejo določene prepreke. Proces evolucije poteka namreč samodejno, a ne linearno in vsekakor brez inherentno določenega smotra, pri tem pa same populacije ali posamezni osebki ne opravljajo sprotne refleksije in analiz lastnega razvoja.

Evolucijske spremembe v naravi nam služijo kot inspiracija za zasnovo evolucijskih optimizacijskih metahevrističnih metod. Vendar pa namen teh metod ni popolna poustvaritev evolucijskih procesov. Z njimi le na zelo preprost način posnemamo nekatere procese, ki se v naravi odražajo veliko bolj kompleksno.

Kot osnovni primer evolucijske metahevristike si podrobneje poglejmo genetske algoritme. Takšni postopki so zanimivi, ker nam omogočajo reševanje tudi precej zapletenih problemov, ki so podobni že omenjenemu problemu potujočega trgovca. Predstavljajmo si, da imamo nalogo planirati proizvodnjo v tovarni, ki stalno dela različne izdelke. Za izdelavo vsakega izdelka mora biti opravljenih več različnih operacij. Poleg tega pa tudi različni stroji opravljajo zgolj določene postopke.

Kako bi torej delo po strojih razporedili tako, da bi za vse izdelke čim bolje ujeli zapovedane roke izdelave? Po premisleku hitro vidimo, da bi porabili veliko časa s preverjanjem vseh rešitev, da bi prišli do optimalne.

Tu pa nam na pomoč lahko priskočijo že omenjeni postopki genetskih algoritmov. Genetski algoritem nam sicer ne zagotavlja optimalne rešitve za omenjen problem. Njegova prednost je predvsem to, da lahko z njim najdemo zelo dobro rešitev v času, ki je dejansko sprejemljiv. Na omenjenem primeru planiranja proizvodnje bomo predstavili, kako poteka genetski algoritem.

Optimizacija ne pomeni samo poiskati katere koli rešitve omenjenega problema, ampak najti čim boljšo. Da lahko med sabo primerjamo različne rešitve, jih je treba najprej zapisati v primerni obliki. V našem primeru optimizacije proizvodnje bi bila ta oblika seznam vseh operacij za vse izdelke s pripadajočim časom začetka izdelave in oznako stroja, na katerem se bo operacija izvajala.

Pri genetskem algoritmu sprva z računalniškim programom naključno ustvarimo začetno populacijo osebkov, ki predstavljajo kandidatne rešitve zastavljenega problema. Vsak osebek je torej niz števil, kjer je položaj števila vezan na konkretno operacijo v proizvodnji, vrednost števila pa na čas, kdaj se ta operacija izvaja, in stroj, na katerem se izvaja. Osebke, ki predstavljajo predlagane rešitve, moramo med seboj razločiti na boljše in slabše, da bomo lahko iz boljših ustvarili naslednjo generacijo. Kako definiramo sposobnost preživetja osebkov, nam pove dr. Ivan Bratko s Fakultete za računalništvo in informatiko:

Zdej v uporabi …

Na podlagi podatkov, torej seznama razporeditve operacij, ki jih predstavlja vsak osebek, smo izračunali čas zamud in ga uporabili kot kriterij za razvrstitev osebkov. Za stvaritev nove generacije osebkov potrebujemo najboljše osebke iz prejšnje generacije in dva operatorja - križanje in mutacijo.

Križanje je poenostavljena analogija kombiniranja genetskega materiala dveh staršev v živem svetu. Običajno poteka tako, da v zapisu osebka, ki je zgolj seznam števil, program naključno izbere mesto, na katerem se zapis enega starša zaključi in se začne zapis drugega. Ta potem predstavlja zapis kode za enega potomca, za drugega pa lahko uporabimo preostali zapis kode staršev.

Izbere pa se tudi kratke odseke kode, v katerih poteče naključna mutacija oziroma sprememba zapisa. Odseke se lahko zamenja z drugimi znaki oziroma števili, zrcalno obrne ali kako drugače spremeni. V vsakem primeru s tem zagotovimo, da se v populaciji osebkov ohrani raznovrstnost, in preprečimo, da bi se ti začeli prezgodaj razvijati v smer določene rešitve. S tem bi namreč dobili slabšo rešitev, kot bi jo lahko pri večji stopnji mutacij. Stopnja mutacij pa po drugi strani tudi ne sme biti previsoka, saj se v tem primeru začnemo zgolj naključno sprehajati skozi prostor iskanja, ker boljše rešitve mutirajo v slabše.

Če smo vse omenjene parametre genetskega algoritma uspešno nastavili, se nove generacije osebkov sčasoma nehajo bistveno razlikovati med sabo. Tako preko genetskega algoritma dobimo enega ali več planov proizvodnje, ki so optimalni ali pa blizu optimalnim. Zaključek algoritma lahko tudi predvidimo, tako da vnaprej določimo minimalni cilj, ki ga želimo doseči, ali pa nastavimo število generacij, količino časa ali dopustne stroške.

Genetski algoritem lahko uporabimo pri optimizaciji najrazličnejših problemov. Najbolj znani izmed teh so poleg planiranja proizvodnje zasnova sestavnih delov, kot so antene in zrcala za sončne zbiralnike, ter usmerjanje prometnih tokov. Pogoj je le, da si zamislimo naslednji stvari: veličino, za katero iščemo optimalno rešitev - v našem primeru je bil to čas zamud. In genetsko prestavitev vseh dejavnikov, od katerih je ta veličina odvisna, kar je predstavljala razporeditev vseh možnih del po strojih.

Za uporabo principov genetskih algoritmov pa obstaja še veliko drugih načinov. Eden izmed njih je genetsko programiranje, o katerem nam pove več dr. Ivan Bratko:

Recimo ena izpeljanka …

Sedaj sledi glasbeni premor, po katerem bomo obravnavali optimizacijske metahevristične metode, ki temeljijo na inteligenci roja.

Ponovno pozdravljeni v oddaji Frequenza della scienza na 89,3 MHz. V prvem delu oddaje smo predstavili računske probleme, ki jih zelo težko optimiziramo oziroma za katere težko najdemo najboljšo rešitev. Videli smo, da lahko z algoritmi, ki posnemajo nekatere evolucijske in genetske procese, take probleme rešimo precej učinkovito. V drugem delu oddaje pa bomo predstavili optimizacijske algoritme, ki prav tako, a na malce drugačen način, svoj navdih črpajo v delovanju narave.

Poglejmo si torej, kako delujejo optimizacijski pristopi, ki jih uvrščamo v področje inteligence rojev. Gre za algoritme, ki temeljijo na osnovi obnašanja čebel, mravelj, opic, volkov in drugih skupinskih živali. Vsak izmed naštetih pristopov pa ima več različic, zato bomo obravnavali samo dva značilna primera. Kasneje se bomo tudi vprašali, kako smiselna je sploh delitev na toliko različnih metod in ali je narava res vedno navdih za nove optimizacijske algoritme ali pa ta kdaj prihaja predvsem iz želje po objavi članka v strokovni reviji.

Vrnimo se torej na inteligenco rojev. Kaj je zanjo značilno in kako se je razvila, nam pove dr. Bogdan Filipič z Inštituta Jožef Stefan:

Ko govorimo o inteligenci rojev ...

Na primerih bomo videli, da za usklajeno delovanje sistema ni potrebe po centralnem upravljanju celotnega roja. Namesto tega poteka usklajevanje roja decentralizirano - na način, da vsak agent prispeva k premikom drugih agentov in tako posledično k premikom celotnega roja.

Lep primer optimizacijskega algoritma, ki deluje po principu roja, je optimizacija z rojem delcev ali tako imenovana Particle Swarm Optimization. Omenjeni algoritem sta leta 1995 iznašla socialni psiholog Kennedy in elektrotehnik Eberhart, ki sta sprva nameravala narediti simulacijo premikanja ptičev. Ti naj bi v dvodimenzionalnem prostoru iskali hrano in se izogibali plenilcem. Ko sta poskušala sprogramirati, da bi jata ptic iskala hrano avtonomno, pa je njuna simulacija začenjala dobivati podobo optimizacijskega algoritma.

Raziskovalca sta po eksperimentiranju in poenostavitvi iz jate ptic v roj delcev prišla do zelo preprostega algoritma. Z njim se da namesto izmišljene hrane učinkovito iskati zelo dobre rešitve za podobne optimizacijske probleme, kot smo jih omenjali v prvem delu oddaje.

Osebek, ki bi imel pri genetskem algoritmu v svoji rešitvi dvajset elementov, se pri optimizaciji z rojem delcev nahaja kot delec ali agent v dvajsetdimenzionalnem koordinatnem sistemu. Bistvo optimizacije z rojem delcev je, da delci letijo skozi prostor rešitev, ki ima toliko dimenzij, kolikor elementov vsebuje rešitev. Primer tega razloži dr. Ivan Bratko s Fakultete za računalništvo in informatiko:

Zdej si bom zlo na hitro moral ...

Če se še vedno sprašujete, kako je možno, da delci letijo čez recimo večdimenzionalni prostor, raje odmislite besedo prostor. Rešitev z dvajsetimi dimenzijami je kombinacija dvajsetih različnih vrednosti, od katerih odvisna veličina, ki jo optimiziramo.

Poglejmo si torej, kako poteka algoritem optimizacije z rojem delcev. Začne se s tem, da v n-dimenzionalnem prostoru začne leteti roj delcev v naključnih smereh. Algoritem vsebuje zanko, v kateri v vsakem koraku delci na podlagi hitrosti spremenijo svoj položaj in preverijo ustreznost rešitve s kriterijsko funkcijo. Če sta položaj oziroma rešitev boljša od prejšnjih položajev, si delec ta položaj zapomni kot najboljši lokalni položaj delca.

Preden se zanka pomakne v naslednji korak, pa delci tudi spremenijo smer in velikost svoje hitrosti. Pri tem pa ne smemo pozabiti, da je vektor hitrosti prav tako n-dimenzionalen, kot je tudi prostor. Na spremembo hitrosti vplivata najboljši položaj, na katerem se je nahajal delec, in najboljši položaj, na katerem se je nahajal katerikoli delec v roju. Vpliva teh dveh vrednosti - lokalnega in globalnega najboljšega položaja - in same inercije oziroma vpliva že obstoječega gibanja, določajo števila, ki jim pravimo uteži.

Na koncu vsakega koraka zanke se torej vektor hitrosti vsakega delca spremeni tako, da se usmerja proti omenjenima točkama najboljših položajev, ki sta si ju zapomnila roj in posamezni delec. Da lahko algoritem preišče večji prostor, pa se pri določanju vplivov vsak prispevek k spremembi hitrosti tudi množi s številom med ena in nič, ki je pri vsakem koraku naključno generirano.

Optimizacija z rojem delcev je precej preprosta in robustna metoda, s katero se da zelo učinkovito poiskati dobre rešitve za problem, ki ga poskušamo optimizirati. Na obnašanje algoritma lahko vplivamo s spreminjanjem parametrov algoritma. Ti parametri so že omenjene vrednosti uteži, ki določajo vpliv kolektivnega znanja, lastnih izkušenj in inercije, pomemben parameter pa je tudi število delcev.

Naslednja metahevristična metoda, ki jo bomo na kratko obravnavali, tokrat neposredno črpa navdih pri obnašanju živali. Algoritmi, ki so narejeni po metodi optimizacije z umetnimi kolonijami čebel, posnemajo čebele pri nabiranju hrane. O tem, kako si čebele med sabo poročajo o kakovosti paše, nam več razjasni dr. Janko Božič z Biotehniške fakultete.

Čebelja družina ima dejansko kar ...

Božič nadalje pove več o tem, zakaj nekatere čebele raziskujejo okolico in iščejo nove paše.

Zadeva ni taka ...

Če metahevristično metodo primerjamo z obnašanjem čebel, lahko začrtamo naslednje vzporednice: v umetnih kolonijah čebel predstavlja vir hrane rešitev. Virtualne čebele izvidnice iščejo hrano tako, da preizkušajo vrednosti naključnih rešitev v prostoru iskanja rešitev. Kakovost nektarja nadomesti kriterijska funkcija, s katero preverimo ustreznost rešitev. Čebele delavke pa predstavljajo iskanje novih rešitev v neposredni bližini že znanih rešitev.

Sam algoritem umetnih kolonij čebel je kompleksnejši od optimizacije z rojem delcev, a vseeno vpeljuje podobne principe. Posamezni agenti tudi tu vplivajo drug na drugega, tokrat s poročanjem o kakovosti različnih rešitev. Vpliv se odraža v tem, da se čebele na osnovi poročil o najdiščih hrane odločijo, kako se bodo razporedile in izkoriščale vire hrane. Pri tem pa se tudi samoorganizirajo v čebele izvidnice, čebele delavke in čakajoče čebele.

Parametri algoritma so v primeru umetnih kolonij čebel velikost populacije, maksimalno število ciklov in limita, ki določa, po koliko poskusih lahko čebele opustijo iskanje rešitev v okolici, kjer ni več dovolj dobrih rešitev. Vidimo torej, da ima tudi ta algoritem svoje parametre, ki jim morajo biti predpisane neke vrednosti. Več o vseh možnih načinih nastavljanja parametrov nam pove doktor Bogdan Filipič z Inštituta Jožef Stefan:

Zdej za nastavljanje parameterov ...

Obstajajo pa tudi načini, da se parametri, ki določajo delovanje algoritma, spreminjajo med njegovim izvajanjem. Nadaljuje Filipič:

Kar se pa tiče nastavljanja …

Še vedno poslušate oddajo Frequenza della scienza znanstvene redakcije Radia Študent. Pobližje smo spoznali nekaj metahevrističnih metod, s katerimi je mogoče optimizirati zelo zahtevne probleme. V zadnjem delu oddaje pa se bomo posvetili širši sliki. Najprej se bomo vprašali, kako lahko različne metode primerjamo med seboj in na kaj se osredotočamo, ko jih apliciramo. Na koncu pa se bomo srečali s kritičnostjo znotraj samega področja metahevristik in z najnovejšim razvojem ter različnimi aplikacijami.

Ena izmed težav optimizacijskih algoritmov v splošnem je to, da se lahko ujamejo v lokalne optimume. V primeru funkcije, ki je odvisna od dveh spremenljivk - x in y - bi bil lokalni optimum videti kot vrh gore, ki pa ni najvišji v gorovju. Ujetost v lokalni optimum pomeni, da optimizacijski algoritem vidi rešitev funkcije na določenih koordinatah kot optimalno vrednost. Zaradi tega se ne more pomakniti naprej in najti globalnega optimuma. Funkcije z velikim številom lokalnih optimumov predstavljajo učinkovito prepreko, na kateri lahko preizkusimo, kako se algoritem obnaša. Več o tem in o drugih kriterijih za ocenjevanje algoritmov nam pove dr. Bogdan Filipič z Inštituta Jožef Stefan:

Torej vprašanje o primerjavi je vedno ...

Intenziven razvoj na področju metahevrističnih metod je v strokovni literaturi opaziti v zadnjih dveh desetletjih. Morda so na žalost na prvi pogled bolj vidni pojavi, ki za samo vedo niso najbolj produktivni. Raziskovalec Kenneth Sörensen z univerze v Antwerpu pojasnjuje, kako se nekateri raziskovalci na vse pretege trudijo, da bi iznašli nove metahevristične metode. Gre za metode, ki se jih da razložiti z novo metaforo in besednjakom, ki ju je moč najti izven področja metahevristike.

Za iskanje novih metafor pride prav večina primerov rojenja žuželk, popularne pa so postale tudi metode, ki temeljijo na bolj čudnih primerih. To so recimo: metahevristika inteligentnih vodnih kapljic, kjer naj bi z algoritmi posnemali vodne kapljice, ki tečejo v morje. Ali pa metahevristika iskanja harmonije, ki trdi, da temelji na osnovi igranja jazz glasbenikov v skupini. Objavljeni so bili članki o kukavičjem iskanju, metahevristiki kresničk, kačjih pastirjev, žab, svetlobe, vrtenja galaksij, imperijev in še česa.

A podrobnejša analiza je pokazala, da je mnogo teh primerov le nekakšna malenkostno spremenjena različica že znanih metahevrističnih metod s povsem spremenjenim besednjakom. Lep primer je omenjena metahevristična metoda iskanja harmonije iz leta 2001, ki naj bi posnemala jazz glasbenike. Za to metodo se je leta 2010 in 2011 dokazalo, da je le poseben primer metahevristične metode evolucijskih strategij, ki je bila znana že leta 1973.

Kljub omenjenim težavam, ki so posledica neustreznosti sistema vrednotenja citiranja in hiperprodukcije strokovnih člankov, pa se moramo zavedati, da iskanje inspiracije v naravi samo po sebi ni napačno. V metahevristiko je prineslo veliko novih pristopov, s katerimi je sedaj možno reševati kompleksne probleme.

A pojdimo za konec k razvoju in dosežkom. O najnovejših odkritjih in zanimivih aplikacijah nam več pove dr. Bogdan Filipič z Inštituta Jožef Stefan.

Eno od aktualnih področij je ...

Nadalje nam Filipič predstavi razvoj nadomestnih modelov s pomočjo metahevristike in z evolucijsko robotiko.

Potem druga zadeva je povezava ...

Spoznali smo torej del metahevristike, v katerega spadata področji evolucijskega računanja in inteligence rojev, ki smo ju obravnavali v današnji oddaji. Na področju optimizacije se pojavljajo vedno novi izzivi, ki pa jih lahko uspešno rešujemo tako, da se pri snovanju optimizacijskih metod zgledujemo po naravi. Analiza tega procesa nam omogoča tudi zanimiv uvid v to, zakaj se lahko življenje razvije na določen način. Hkrati pa nas tudi spodbuja, da pogledamo abstraktno na procese in metode reševanja problemov, ki so nastali z evolucijo organizmov.

Določen razmislek glede delovanja možganov in kognicije pa nam lahko ponudijo tudi ugotovitve iz preseka računalništva in biologije, o katerem nocoj nismo govorili. Tako bomo nevronske mreže in strojno učenje obravnavali v kateri izmed naslednjih oddaj. Naslednjič nas lahko spremljate 30. marca, ko bomo poročali s Tedna možganov.

Oddajo smo pripravili Jaka, Maja in vajenka Ana.

Urednikovala je Teja.

Brala sva Valentina in Biga.

Tehniciral je JureG.

Evolved Virtual Creatures

Nazoren prikaz uporabe genetskega algoritma nam nudi vizualna demonstracija Evolved Virtual Creatures. Gre za simulacijo evolucije živih bitij z računalniškim programom, ki osebke oziroma rešitve zastavljenega problema predstavi tudi vizualno. V začetku so osebki sestavljeni povsem naključno iz nekaj geomterijskih teles, ki se na naključnih mestih stikajo in se naključno premikajo po simuliranem fizičnem okolju.

Simuliranim bitjem je zadana naloga, ki jo morajo čim bolje opraviti. Prikupni stvorčki razvijejo najrazličnejše strategije za spopadanje z nalogo, ki včasih precej spominjajo na tiste v živem svetu. Tako tista bitja, ki imajo nalogo plavati v vodi, včasih razvijejo preproste plavuti ali celo propelerje, tista, ki morajo z drugimi tekmovati za posestvo nekega predmeta, pa pridobijo ročice, s katerimi predmet obdajo ali ustavijo nasprotnika.