Memetički algoritmi

Na početku ovog rada opisali smo evolucijske algoritme i njihove značajke. Evolucijski algoritmi najčešće se koriste za rješavanje problema optimizacije, a baziraju se na principima Darwinove teorije o prirodnoj selekciji. Temeljni način evolucijskog rješavanja problema oslanja se na metodu pokušaja i pogreške. Ideja je jedinke što bolje prilagoditi nekoj danoj okolini s obzirom na određene karakteristike. Intuitivno, želimo izvesti analogiju između evolucije u stvarnom svijetu i evolucijskog programiranja na način da okolina predstavlja zadani problem koji treba riješiti, jedinke predstavljaju rješenja, a podobnost jedinki (eng. fitness) predstavlja koliko je to rješenje dobro. Do boljeg rješenja u svakoj generaciji dolazimo pomoću operatora varijacije: mutacije i rekombinacije. Njih primjenjujemo na roditelje u svrhu dobivanja podobnijih potomaka, odnosno boljih rješenja. Memetički algoritmi zapravo su evolucijski algoritmi kombinirani s drugim tehnikama ili pak nadograđeni nekim metodama ili strukturama podataka. Ono što najčešće želimo implementirati jesu podaci o samom problemu koji želimo riješiti. Važan dio memetičkog programiranja je lokalno pretraživanje. U najopćenitijim crtama to je iterativni proces koji ispituje skup točaka oko trenutnog rješenja, i ukoliko nađe bolje rješenje u tom skupu, onda ga postavi za novo trenutno rješenje. Također, operatori koji se koriste u evolucijskom programiranju mogu se nadograditi stečenim znanjima ili pak možemo odmah u inicijalizaciju umetnuti informacije koje bi nam pomogle pri rješavanju problema. Time automatski dobivamo bolji i efikasniji algoritam. Na kraju smo teoriju demonstrirali praktičnim primjerom u MATLAB-u i to algoritmom skakutanja žaba (eng. Shuffled Frog Leaping Algorithm- SFLA). Gledali smo populaciju od 500 žaba na području \([-10,10] \times [-10,10]\) s funkcijom podobnosti \(f(x,y)=x^2+y^2\), gdje je \((x,y)\) pozicija svake žabe. Primjer nam je dao očekivane rezultate s obzirom na teorijsku podlogu koju smo obradili u prva dva poglavlja. Pokazalo se da je upotreba memetičkih algoritama izrazito korisna u praksi i čini istraživačko područje koje posjeduje veliki potencijal za daljnja istraživanja.At the beginning of this graduate thesis we have described evolutionary algorithms and their features. They are most commonly used for solving optimization problems and they form a class of algorithms that are based on the Darwinian principles of natural selection. The fundamental way of evolutionary computing relates to a particular style of problem solving– that of trial and error. The idea is to adapt individuals to better suit the given environment. Intuitively, we want to link the evolution in ‘real world’ to the evolutionary computing and we do that in a way that environment represents a given problem, individuals represent solutions, and fitness of every individual represents a measure of how good solution solves a given problem. In every generation we make new (better) solutions by using variation operators: mutation and recombination. They are applied to the so-called parents, producing one or more children (new solutions). Memetic algorithms are actually evolutionary algorithms combined with other techniques or have other methods or data structures incorporated within them. In most cases we want to include information about the problem we are solving into the evolutionary algorithm. The important phase of memetic algorithm is local search. Briefly described, local search is an iterative process of examining the set of points in the neighbourhood of the current solution, and replacing it with a better neighbour if one exists. Variation operators that are used in evolutionary algorithms can also be upgraded by incorporating problem-specific knowledge, or we can just incorporate that information in initialization phase as well. By making these changes we instantly get a better and more efficient algorithm. In the end, we demonstrated the theory with a practical example in MATLAB. The example we have described is called Shuffled Frog Leaping Algorithm (SFLA). We observed the population of 500 frogs in the \([-10,10] \times [-10,10]\) environment with fitness function \(f(x,y)=x^2+y^2\), in which \((x,y)\) represents position of each frog. The example yielded the expected results considering the theory we have explained in the first two chapters. It turned out that memetic algorithms are very successful in practice and they form a rapidly growing research area with great potential