Evolucinarni algoritam

Po najčešće korišćenoj klasifikaciji, Evolucionarni algoritmi, zajedno sa Fazi logikama i Neuralnim mrežama, je deo od takozvanog Soft Computing. EA uključuje Genetske algoritme, Evolucionarno programiranje, Evolucionarne strategije, Genetsko programiranje i neke slične tehnike.

Evolucionarni algoritmi se primenjuju na neke optimizacione probleme - bilo teoretske (job shop scheduling, traveling salesperson) or practical (ekonomsko modeliranje, projektovanje naftovoda); na mašinsko učenje; na teoriju igara; na neuralne mreže itd.

Darvinova teorija evolucije i Mendelovi zakoni nasleđivanja predstavljaju teoretsku inspiraciju za Evolucione Algoritme. Ako Darvinova teorija objašnjava pojave i procese u prirodi, tada EA imitira prirodne procese u pokušaju da se reši konkretan problem.

Prema Darvinu, jedinke u populaciji se takmiče za resurse. Činjenice koje leže u osnovi procesa prirodne selekcije su:

• Bolje prilagođene jedinke preživljavaju i oni imaju jači uticaj na oformljenje novih generacija. 
• Jedinke u novoj generaciji se kreiraju rekombinacijom genetskog materijala roditelja.
• S vremena na vreme mutacija (slučajna izmena genetskog materijala) dolazi do izražaja.

Velika popularnost EA leži u činjenici da dobijanje novih rešenja ima, u svojoj suštini, paralelnu prirodu. Holland je uočio paralelnu prirodu reproduktive paradigme i usađenu efikasnost paralelnog procesiranja dest godina pre formalnog nastanka EA.

Nadalje, Evolucionarni algoritmi se lako hibridizuju: oni lako mogu biti kombinovani sa ostalim algoritmima koji rešavaju konkretan problem. Novi, hibridni, algoritam ima dobre karakteristike oba bazna algoritma.

EA imaju sledeću strukturu:

• Prostor pretrage - prostor svih mogućih rešenja.
• Populacija - skup aktuelnih kandidata za rešenja; elementi populacije su jedinke ili čvorovi pretrage, ili tačke u prostoru pretrage.
• Prostor niski - prostor koji sadrži niske sa genetskim kodovima jedinki. 
• Funkcije za konverziju između tačaka u prostoru pretrage i tačaka u prostoru niski (kodiranje i dekodiranje). 
• Skup genetskih operatora za generisanje novih niski (i novih jedinki).
• Funkcija prilagođenosti - ona izračunava prilagođenost (nivo adaptacije) za svaku jedinku u populaciji.
• Stohastička kontrola genetskih operatora.

Osnovni koraci kod genetskih algoritama su:

1. Inicijalizacija - generisanje inicijalne populacije slučajnim sampliranjem. 
2. Evaluacija - izračunavanje prilagođenosti za sve jedinke u populaciji.
3. Selekcija - izbor jedinki u populaciji koje preživljavaju, zavisno od vrednosti funkcije prilagođenosti.
4. Rekombinacija (uključuje ukrštanje i mutaciju) - promena genetskog koda jedinke.
5. Ponavljanje koraka 1 do 4, sve dok se ne ispuni kriterijum završetka.

Karakteristike koje razlikuju EA od drugih metoda za rešavanje problema su:

• EA radi sa kodovima koji predstavljaju jedinke, a ne sa čistim jedinkama.
• EA pretražuje po više tačaka simultano, pa je stoga vrlo robustna.
• EA korisiti probabilistička, a ne deterministička pravila prelaska.
• EA (u svojoj čistoj formi) ne eksploatiše dodatne informacije o prirodi problema.

Početak

Web servis

Web servis za Evolucionarni algoritam, nazvan EaWebService (.wsdl | .asmx), može biti korišćen u svim scenarijima koji uključuju optimizaciju pomoću EA. U isto vreme, servis može biti korišćen i na GP način.

Pri izvršavanju EA, aplikacija šalje web servisu pet XML niski:

• parameterXML - parametri EA koji će biti izvršen. Neki od ovih parametara (kao što su zamena populacije, selekcija, kriterijum završetka, generator slučajnih brojeva, izveštaji) ne zavise od reprezentacije jedinke dok neki drugi (npr. tip populacije, inicijalizacija, instanca, ukrštanje i mutacija) zavise. Svaki parametar je XML čvor sa elementima koji određuju vrednost parametara. EaWebService podržava tri tipa reprezentacije jedinki (kao binarna niska, kao broj u pokretnom zarezu i drvoidna reprezentacija);
• problemArgumentsXml – problem (u XML reprezentaciji) koji se rešava putem EA. Na primer, zapis funkcije je predstavljen u XML formati i isti kod može optimizirati različite funkcije;
• initDataXML – kad je potrebno, inicijalni podaci neće biti postavljeni generatorom slučajnih brojeva, već će biti pročitani iz XML-a određenog ovim parametrom;
• topologyXML – veze među web servisima iste vrste koji zajednički rade (paralelno) kako bi se odredilo rešenje;
• knownSolutionXML – predstavlja poznato rešenje, tako da EA može biti zaustavljen kada se dostignr to rešenje (uglavnom korišđeno pri testiranju);

Web servis vraće (u XML formatu) nađeno rešenje i dodatne rezultate koji su neophodni. Na pitanje koji su podaci zahtevani i kada su zahtevani se odgovara postavljanjem na odgovarajuću vrednost XML podčvora unutar parameterXML argumenta.

Web servis dopušta aplikaciji da prekine tekuće izvršavanje i vrati dotadašnji rezultat u ma kom momentu izvršavanja.

Ovaj servis takođe (koriščenjem refleksije) dopušta aplikacijama da dobije informacije o klasama koje predstavljaju posedine delove EA i da, na taj način, omogući lakšu i bržu kreaciju EA.

Ovaj servis je, u isto vrijeme, vrlo kompleksan, vrlo efikasan i može lako da se nadograđuje.

Lakoća nadogradnje sledi iz činjenice da je servis čvrsto zasnovan na interfejsima. Tako, kad god se pristupa metodu ili osobini neke klase van te klase, to se realizuje uzimanjem interfejsa i pristupom metodu odnosno osobini interfejsa (a ne direktno klase). 

Web service’s complexity and efficiency come from the fact that Web Service is multi-threaded application with Execute thread, StopExecution thread, Migrate thread and Cleanup thread.

Kompleksnost i efikasnost web servisa proizilazi iz činjenice da je web servis višenitna aplikacija sa Execute niti, StopExecution niti, Migrate niti i Cleanup niti. 

Početak

XML konfiguracioni fajlovi

Prethodno opisane XML niske su validirane (pomoću schema) na EaWebService serveru.

Sledeći linkovi predstavljaju repozitorijum XML niski koje mogu biti parametri web servisa:

• XML parametri za EA proces:
  • Rešavanje Obmanjivačke funkcije
  • Rešavanje JedanMax funkcije
  • Rešavanje De Jong F1 (Sferne) funkcije
  • Rešavanje De Jong F1 (Sferne) funkcije (reprezentacija u pokretnom zarezu)
  • Rešavanje De Jong F2 (Rozenbrock) funkcije
  • Rešavanje De Jong F3 (Korak) funkcije
  • Rešavanje De Jong F3 (Korak) funkcije (reprezentacija u pokretnom zarezu)
  • Rešavanje De Jong F4 (Četvorni šum) funkcije
  • Rešavanje De Jong F5 (Shekel) funkcije
  • Rešavanje De Jong F6 (Rastring) funkcije
  • Rešavanje De Jong F7 (Schwefel) funkcije
  • Rešavanje De Jong F8 (Griewangk) funkcije
  • Rešavanje De Jong F9 (Sinusna ovojnica - sinusni talas) funkcije
  • Rešavanje De Jong F10 (Skupljeno V - sinusni talas) funkcije
• XML parametri  za problem:
  • Obmanjivački problem
  • JedanMax problem
  • De Jong F1 (Sfera) problem
  • De Jong F2 (Rozenbrock) problem
  • De Jong F3 (Korak) problem
  • De Jong F4 (Četvorni šum) problem
  • De Jong F5 (Shekel) problem
  • De Jong F6 (Rastring) problem
  • De Jong F7 (Schwefel) problem
  • De Jong F8 (Griewangk) problem
  • De Jong F9 (Sinusna ovojnica - sinusni talas) problem
  • De Jong F10 (Skupljeno V - sinusni talas) problem
• XML parametri za  inicijalne podatke:
  • Linearna jednačina 1
  • Linearna jednačina 2
• XML parametri  za topologiju:
  • Three servers topology

Početak

Web aplikacija

Kad je gore opisani servis kreiran, istraživač (čak i kad nije ekspert za EA) može eksperimentisati (podešavanjem vrednosti XML elemenata) radi dobijanja najboljih parametara za rešavanje konkretnog problema, ili lako preći sa jednog problemskog domena na drugi. Aplikacija koja koristi servis samo treba da oformi XML niske koje su parametri EA i da prihvati i prikaže rezultat (koji je takođe XML niska). 

One example of consumer Web application (denoted as EaWebApplication ) that covers almost all different properties of proposed web service and different ways of using it is given there.

Ovde je dat i primer web aplikacije koja koristi servis (označena kao EaWebApplication ) i koja pokriva skoro sve različite osobine predloženog web servisa i različite načine korišćenja.

Početak

Sva pitanja, komentare, sugestije i ispravke slati na adresu : 

vladaf@matf.bg.ac.yu    or

vladofilipovic@hotmail.com