Application of learnable evolution model to optimization problems

U ovom radu ispitane su mogućnosti implementacije LEM-a (Learnable Evolution Model) u svrhu rješavanja problema iz različitih domena korištenjem pravila ili uzoraka koji se pojavljuju u samim podacima. Opisano je testno okružje u kojemu je implementiran modularni algoritam i sve komponente koje su potrebne za rješavanje određenih problema. Implementacija LEM-a nad problemima čije je rješenje prikazano poljem realnih brojeva izvedena je na dva načina: pronalaskom pravila uz pomoć C4.5 poboljšanog AdaBoost-om i pronalaskom pravila AQ algoritmom. Implementacije su testirane nad COCO bibliotekom funkcija. Problemima čije je rješenje prikazano poljem bitova napisana su dva načina stvaranja novih jedinki postupkom učenja: pronalaženjem pravila uz pomoć C4.5 poboljšanog AdaBoost-om i korištenjem CHARM algoritma pronalaska čestih zatvorenih skupova stavki. Implementacije su testirane nad problemom stvaranja Booleovih funkcija koje moraju čim bolje zadovoljiti određene kriterije. Postupak učenja nad problemima čije je rješenje prikazano permutacijom ostvareno je koristeći dva načina: pronalaskom čestih grupa vrijednosti koristeći sufiksno stablo i pronalaskom sekvencijalnih uzoraka koristeći CM-SPADE algoritam. Načini su testirani nad podskupom problema iz poznate biblioteke TSPLIB. Za probleme kojima je rješenje prikazano stablom učenje novih rješenja ostvareno je na dva načina: korištenjem algoritma gSpan i Apriori algoritmom prilagođenim za pronalazak čestih uzoraka u skupu stabala. Testiranje je obavljeno je nad problemom SantaFe traga i problemima simboličke regresije.This thesis presents some implementation possibilities of the LEM (Learnable Evolution Model) algorithm with the purpose of solving problems from different domains using rules or patterns that occur in the data. The testing framework in which the modular algorithm is implemented and all components used for solving particular problems have been described. The implementation of LEM for solving problems which solution is represented by an floating point array has been done in two different ways: by discovering rules using the C4.5 algorithm boosted with AdaBoost and by discovering rules through the AQ algorithm. These implementations have been tasted on the COCO test platform. For the problems which solution is represented with a vector of bits, two ways of constructing new solutions in the learning phase have been implemented: by discovering rules using the C4.5 algorithm boosted with AdaBoost and by using the CHARM frequent itemset mining algorithm. Those implementations have been tested on the problem of creating a Boolean function which has to satisfy a combination of criteria as good as possible. The LEM learning phase for problems which solution is represented with a permutation has been realized in two ways: by finding frequent groups of values using a suffix tree and by mining sequential patterns using the CM-SPADE algorithm. These two realizations have been tested on a subset of standard TSP problems from TSPLIB. For the problems which solution is represented by a tree data structure the LEM learning phase has been achieved in two ways: using the gSpan algorithm and a version of Apriori specially tuned for tree frequent pattern mining. These two methods have been tested on two different problems: the first being Santa Fe trail problem and the second a set of symbolic regression problems