Gost autor| Nauka| Životinjski svet

Priroda u službi matematike

nsarski RSS / 04.04.2012. u 09:32

Kao i ranije, rec ima gost autor alselone

Priroda ništa ne radi slučajno i Bog se ne igra kockicama.

Priroda i Bog imaju nešto što nije „klasična“ matematika za rešavanje optimizacionih i svih drugih matematičkih problema već imaju naizgled proste stvari – sirovu snagu i vreme. Recimo ovako, ako bi priroda i Bog želeli da konstruišu biće koje može da pliva brzinom od 50 kilometara na čas oni neće „sesti“ i „računati“ tamo neke izvode, redove, limese i diferencijalne jednačine nego će posejati hiljadu ameba na jednu planetu punu vode i sačekati da se to dogodi. Ili – ako žele da kreiraju najjeftinije vozilo za put na mesec – sačekaće još malo vremena posle kreiranja bića koje pliva brzo. I to je ono što nazivamo Veliki dizajn. Sve je baš onako kako treba da bude i najjeftnije je. Ili će biti, ako sačekamo dovoljno dugo.

Blue_August_by_farhadvm.jpg 

Zatim su Prometeji nauke doneli ovu metodu ljudima. Da vidimo koje su to metode koje koriste Bog i priroda a dostupne su i nama, na par prostih primera.

Recimo da imamo neki prost problem, na primer, imamo neko zemljište i treba da pronadjemo najzeleniji, najplodniji deo. Recimo da je plavo zemljište loše a zeleno je baš dobro i hranljivo. Možemo da idemo tačkicu po tačkicu i proveravamo zemljište a možemo i da posejemo populaciju naših softverskih kunića i pustimo ih da se razmnožavaju i žive na toj teritoriji pa da vidimo šta bi se desilo. Ovo je lep primer za Genetski algoritam.

 

Na početku našeg rešavanja problema pronalaženja najplodnijeg zemljišta posejemo populaciju kunića po izabranoj teritoriji. Pošto su to živa softverska bića ona imaju hromozom koji ih opisuje. Sam hromozom govori koliko je to biće pogodno za razmnožavanje, koliko je “poželjno”. I softverske kunićice znaju da su bolje baje za razmnožavanje oni koji žive u boljoj, zelenijoj gajbi, tako da oni mališani koji su na zelenoj teritoriji imaju više šanse da ostave potomstvo. I tako se se oni najlepsi kombinuju sa najlepsima i prave sledeću generaciju. Pošto mi baš volimo da se igramo Boga, ako vidimo da je neki mališa baš-baš dobar mi ga onda prenesemo celog u sledeću generaciju bez razmnožavanja, nećemo da „pokvarimo“ njegove gene nekih drugim. I uz malo mutacije na sve ovo dobijamo sledeću generaciju. Mutacija nam je bitna da bi smo možda od “običnih” mame i tate dobili Teslu. U sledećoj generaciji već ima mnogo manje kunića na plavom zemljištu a više na zelenom. I ponovo će veću šansu za razmnožavanje imati oni zeleniji. I ponovo uz malo mutacije i naše intervencije dobijamo sledeću generaciju. Ponovimo algoritam dovoljan broj generacija i dobićemo najboljeg. Pogledajte slikovit primer: http://www.glauserweb.ch/gentore.htm. (Uputstvo - kliknuti na Landschaft da bi se kreiralo “zemljište”, zatim na Population da bi se kreirala prva generacija naših kunića i zatim na Go da bi život krenuo)

dna.jpg

Recimo da sada samo malo promenimo problem, ponovo nešto tražimo ali na malo drugačiji način. Tražimo minimum neke funkcije dve promenjive (najlakše zbog vizualizacije), i ponovo imamo neku oblast koju treba da pretražimo. Recimo da tražimo najbogatije cveće polenom na jednoj livadi. Ponovo možemo da proveravamo cvet po cvet redom ili da se malo igramo Boga. Ovo je lep primer za Particle Swarm Optimizaciju. Posejemo po toj našoj livadi gomilu pčelica. One krenu da se muvaju okolo i kako koja pronađe nešto lepo, vikne onim ostalim šta je pronašla. Tako da u jednom momentu sve pčelice znaju šta je koja pronašla i naravno sve krenu prema onoj koja je našla najlepšte cveće. Ako se za vreme tog putovanja, neka pčelica zadesi na još boljem delu livade, viknuće ostalima pa će sve one da krenu prema njoj. Na kraju će pronaći najlepše cveće za svoj med.Evoga lep primer: http://ccl.northwestern.edu/netlogo/models/run.cgi?ParticleSwarmOptimization.703.474

U primeru se pčelice okupljaju oko najbelje površine. Kliknite prvo na Setup da bi kreirali “livadu” a zatim na Go da bi pčelice krenule.

swarm.jpg

Promenimo malo problem. Recimo da treba da stignemo od tačke A do tačke B u gradu. Tačke su udaljene i postoji veliki broj puteva a nama treba najkraći jer je gorivo tako skupo i imamo tako malo vremena. Možemo da sednemo i “peške” računamo kilometražu ili možemo da pustimo naše softverske mrave (Ant Colony Optimization) da nam pronadju najkraću rutu jer su oni tako dobri u tome. Dakle, kreiramo naše mravce na mapi, dodelimo im kuću (naš start) i hranu (naš cilj) oni se manje više slučajno šećkaju okolo i jedan nabasa na cilj. On zna odakle je krenuo i trči brzo kuci što direktnijim putem da javi braći da je pronašao cilj (hranu). Dok trči kući ostavlja trag feromona za sobom da zna još jednom da se vrati. U tom momentu još neki mravci pronalaze slučajan put do hrane i hitalju što kraćim putem nazad ostavljajući feromone. Sada novi mravci kreću ka hrani prateći feromone prvih istraživača. Svaka putanja puna feromona privlači one koji su blizu i oni vraćajući se ostavljaju novu dozu feromona koja sada privlači i one malo dalje jer dalje i miriše. Ako na kraju imamo dve rute ona kraća će ipak da privuče veći broj koji će onda da ostave još feromona dok ne ostane samo jedna ruta. Lep primer:  http://www.youtube.com/watch?v=ROAvtcmtx7Y&feature=related

antColonyCoop.jpg

 

Da uvedemo još malo drugačiji problem koji je tako atraktivan u ovoj krizi. Recimo da imamo 10 nepotrebnih mesečnih troškova koje više ne možemo da finansiramo. To su, na primer, najskuplje cigarete, Kurvoazje XO nedeljom ujutru, a još malo će to da bude i hrana, računi... Svaki račun ima svoju cenu za uslugu koju plaćamo tako da mi hoćemo da se odreknemo tačno 100 evra koji nam fale ali da se odreknemo što je moguće manjeg broja lepih stvari. Naravno, možemo da se bavimo kombinatorikom “peške” a možemo i da upotrebimo još neku od metoda prirode, na primer Metodu pretrage ptice kukavice. Ova metoda je inspirisana ponašanjem parazita.

Kukavica polaže jaje u gnezda drugih ptica. Koliko je to jaje “dobro”, koliko odgovara jajima druge ptice, tolika je verovatnoća da će preživeti, da ga druge ptice neće izbaciti iz gnezda. Postoje mnoge kombinacije rešenja i ona su predstavljena gnezdima drugih ptica, jaja drugih ptica su rešenja našeg problema a kukavičija jaja su nova rešenja. U svakom koraku našeg algoritma kukavica polaže jaje u gnezdo druge ptice koje izabere na sasvim slučajan način. Najbolja gnezda, u ovom slučaju ona koja imaju potrošenu lovu od približno sto evra sa što manje izbačenih stvari, se prenose u sledeću generaciju. Ptica domaćin može da pronadje jaje i u tom slučaju ima dva izbora - ili će izbaciti jaje kukavice ili će napustiti gnezdo i napraviti neko potpuno novo (novi skup rešenja). Cilj kukavice i cilj našeg algoritma je da napravimo što bolje jaje - jaje koje ima najveću verovatnoću da će preživeti a preživljavanje se meri potrošenim parama na što više usluga koje smo kupili. Ako pustimo kukavice da se razmnožavaju dovoljno dugo po prostoru naših rešenja dobićemo najbolje jaje i optimalno rešenje.

240px-Coccyzus-americanus-001.jpg

Sve su ovo jako zanimljive metode koje imaju veliki broj podtipova, unapredjenih verzija i sitnih izmena koje i poboljšavaju kvalitet pretrage i/ili brzinu kao i povećavaju lepotu samog pristupa. Cela naučna oblast je u povoju i novi algoritmi izlaze praktično svakog dana.

 

Koja je životinja koja vas fascinira, signurno može i po njoj da se napiše zanimljiv algoritam jer - ona je najbolja u svojoj oblasti ima univerzalan i “jeftin” pristup jer inače ne bi preživela.



Komentari (201)

Komentare je moguće postavljati samo u prvih 7 dana, nakon čega se blog automatski zaključava

alselone alselone 17:39 07.04.2012

Re: ajdmo, ajde svi na 200

Za Ex-a. Jedan od lepih evolutivnih algoritama koristi i policija za optimizaciju maksimalnog bola tokom tabanja sa minimumom vidljivih posledica i maksimizovanjem trajnih poremecaja. Koliko su samo ljudi morali da namlate da bi to proracunali. Sigurno nisu racnali peske neke sile udaraca, otpor tkiva, osetljivost osobe nego lepo tuku poslednjih X godina i beleze rezultate. To je mala baza znanja.

Arhiva

   

Kategorije aktivne u poslednjih 7 dana