Primjena modela evolucijskog učenja na probleme optimizacije

master's thesis

• Title (english): Application of learnable evolution model to optimization problems
• Author: Edi Smoljan
• Mentor: Domagoj Jakobović (mentor)
• Committee member: Domagoj Jakobović (predsjednik povjerenstva)
• Committee member: Stjepan Groš (član povjerenstva)
• Committee member: Marko Čupić (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2015-07-17, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing

Abstract

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... More 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.
Less

Abstract (english)

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... More 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.
Less

• Keywords: genetski algoritam; evolucijsko učenje; dubinska analiza podataka; strojno učenje; Learnable Evolution Model; optimizacija
• Keywords (english): genetic algorithm; evolutionary learning; data mining; machine learning; Learnable Evolution Model; optimization
• Language: croatian
• URN:NBN: urn:nbn:hr:168:956221
• Study programme: Title: Computing; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra inženjer/inženjerka računarstva (magistar/magistra inženjer/inženjerka računarstva)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Closed access
• Created on: 2018-02-06 11:50:27