Študija samoprilagajanja krmilnih parametrov pri algoritmu DEMOwSA
Aleš Zamuda, Janez Brest, Borko Boškovič, Viljem Žumer
Univerza v Mariboru
Fakulteta za elektrotehniko, računalništvo in informatiko
Inštitut za računalništvo
Smetanova 17, 2000 Maribor, Slovenija
E-pošta: ales.zamuda@uni-mb.si, janez.brest@uni-mb.si, borko.boskovic@uni-mb.si, zumer@uni-mb.si
Povzetek. V članku predstavljamo študijo samoprilagodljivih krmilnih parametrov algoritma diferencialne evolucije za večkriterijsko optimizacijo, ki ga krmili samoprilagoditveni mehanizem, predstavljen v evolucijskih strategijah. Samoprilagajanje parametrov omogoča danemu evolucijskemu algoritmu učinkovitejše iskanje, saj se algoritem lahko prilagodi optimizacijskemu problemu, ki ga rešuje. Z eksperimentom prikažemo dejanske vrednosti in spreminjanje samoprilagodljivih krmilnih parametrov na znanih testnih funkcijah.
Ključne besede: evolucijsko računanje, diferencialna evolucija, večkriterijska optimizacija, samoprilagoditev
A Study in Self-adaptation of Control Parameters in the DEMOwSA Algorithm
Extended Abstract. In this paper we present an experimental analysis showing that the self-adaptation of control parameters plays an important role in the multiobjective optimization process (refer to Figure 1 for notion of multiobjective optimality). Experimental results of a self-adaptive differential evolution algorithm are evaluated on the set of benchmark functions provided for the CEC 2007 Special session on Performance Assessment & Competition on Multi-objective Optimization Algorithms, as seen in Tables 2-7. Self-adaptation is proven to statistically outperform fixed parameters, using t-test on the empirical results in these tables. The values of control parameters are encoded in each individual (see Figure 2) and changed during the optimization process. They depend on the nature of the problem being solved, as can be seen in Table 1 and Figures 3 and 4 which show how using self-adaptation good control parameters are obtained to improve the search results.
Key words: evolutionary computation, differential evolution, multi-objective optimization, self-adaptation
1 Uvod
V članku predstavljamo študijo samoprilagajanja krmilnih parametrov, ki smo jo izvedli na testnih funkcijah in s pomočjo orodij, ki so bila predlagana na posebni sekciji za oceno učinkovitosti večkriterijskih algoritmov za optimizacijo [13]. Za študijo smo uporabili naš algoritem, kije bil prvič predstavljen na mednarodni konferenci evolucijskega računanja CEC 2007 [21].
Prispevek je organiziran takole. V drugem poglavju predstavimo večkriterijsko optimizacijo in pristope za reševanje večkriterijskih problemov. Tretje poglavje govori o diferencialni evoluciji za večkriterijsko optimizacijo s samoprilagoditvenim mehanizmom za krmilne parametre. V četrtem poglavju opisujemo nastavitev parametrov in eksperimentalne rezultate pri večkriterijski optimizaciji na izbranih testnih funkcijah. Sledi še sklepno poglavje z idejami za nadaljnje delo.
2 Večkriterijska optimizacija
V vsakdanjem življenju se pri odločanju pogosto srečujemo z zahtevo po izbiri različnih možnosti. To lažje opravimo s postavitvijo kriterijev. Ker so si ti kriteriji pogosto v nasprotju, izboljšanje ocene rešitve po enem kriteriju lahko povzroči poslabšanje ocene po drugih kriterijih. Tedaj ena sama rešitev ni optimalna po vseh kriterijih, temveč se srečamo z množico optimalnih rešitev. Za lažjo izbiro ene same od rešitev problema pogosto želimo dobro spoznati, kakšne možnosti sploh imamo, oz. kakšne najboljše možnosti imamo, ter se šele pozneje odločiti za eno od njih. Ta pristop opisuje večkriterijsko optimizacijo, tj. sočasno optimizacijo več konfliktnih kriterijev.
Problem večkriterijske optimizacije (ang. multiobjective optimization problem - MOP) definiramo kot iskanje dopustnega vektorja spremenljivk oz. parametrov x = {x\, X2, • • •, xd ), ki optimizira (minimizira) vek-
h,
E
F •
f(x)
¡f(D)
f|(G) i	f(B)
^f(A) •
:	f(E)
•njfi
A
* Princip optimalnosti, imenovan po Vilfredu Paretu, 1848-1923.
X1,1,G	- ! X1,D,G	F1,G	crI,G	fi\G)\ JJi\G)
G	••• I h,D,G	F2,G	CR2,G	fj\o) \ ...
X3,1,G	\ X3,D,G	F3,G	CR3,G	ff\G) ... \f^3,G)
				
\XNP,D,G		fnp,g	crnp,g	fj\PJ\ ... \f(jXNPJ
Tabela 1. Vrednosti krmilnih parametrov po 5e+5 FES Table 1. Control parameters values after 5e+5 FES
/i
Slika 1. Dominantnost na primeru večkriterijske funkcije f (x) Figure 1. Dominance of multiobjective function f(x)
torsko funkcijo: f(x) = (/i(x),/2(x),...,/M(x)) in spremenljivke zadoščajo m neenakostnim omejitvam:
(x) >0; i = 1,2,...,m.
Rešitev večkriterijskega optimizacij skega problema x dominira rešitev y (x ■< y), če velja, da rešitev x ni slabša od rešitve y po vseh kriterijih (fi(x) < f^(y), \/i = 1,..., M) in je x boljša od rešitve y po vsaj enem kriteriju (3j G {!,..., M}: f7(x) < f7(y)). Prostor
kriterijev R (M je št. kriterijev) je z relacijo ^ delno urejen, saj nekatere rešitve medsebojno niso primerljive. Za slikovno razjasnitev pojma dominantnosti glej sliko 1. Kot je videti iz slike, je rešitev A dominantna (boljša) od B in D, neprimerljiva zErnG, ter slabša od G in F.
Množica nedominiranih rešitev, imenovana tudi nedo-minirana fronta, iz množice rešitev P je podmnožica vseh tistih rešitev iz P, ki jih nobena rešitev iz množice P ne dominira. Podmnožica nedominiranih rešitev celotnega prostora dopustnih rešitev se imenuje optimalna fronta Pareto*, njeni elementi pa optimalne rešitve Pareto. Množico nedominiranih rešitev na sliki 1 tvorijo rešitve G, G in P, saj niso dominirane z nobeno drugo rešitvijo, tj. f (G), f (G) in f (P) so manjše od drugih po vsaj enem kriteriju. Osnovna cilja večkriterijske optimizacije sta porazdelitev in bližina takih rešitev glede na fronto Pareto.
V začetku večkriterijske optimizacije so se uporabljale klasične enokriterijske optimizacij ske metode, pri katerih se je večkriterijski problem z utežno funkcijo preslikal v enokriterijski problem [17]. Pozneje se je pri večkriterijski optimizaciji precej povečal interes za
Zap. št.	Funkcija	F ± imp	
1.	OKA2	0,53 (0,32)	0,40 (0,19)
2.	SYMPART	0,17 (0,06)	0,75 (0,16)
3.	S-ZDTl	0,26 (0,08)	0,55 (0,14)
4.	S.ZDT2	0,31 (0,09)	0,56 (0,14)
5.	S.ZDT4	0,32 (0,10)	0,55 (0,14)
6.	R_ZDT4	0,45 (0,23)	0,26 (0,17)
7.	S.ZDT6	0,55 (0,00)	0,40 (0,00)
8.	S.DTLZ2JVI3	0,32 (0,09)	0,49 (0,13)
9.	R-DTLZ2JVI3	0,68 (0,15)	0,35 (0,11)
10.	S.DTLZ3JVI3	0,33 (0,10)	0,48 (0,12)
11.	WFG1.M3	0,52 (0,16)	0,24 (0,08)
12.	WFG8.M3	0,35 (0,12)	0,46 (0,13)
13.	WFG9.M3	0,63 (0,18)	0,31 (0,10)
14.	S.DTLZ2JVI5	0,36 (0,11)	0,32 (0,09)
15.	R_DTLZ2JV[5	0,61 (0,16)	0,23 (0,07)
16.	S.DTLZ3JVI5	0,62 (0,16)	0,06 (0,02)
17.	WFG1.M5	0,63 (0,16)	0,24 (0,07)
18.	WFG8.M5	0,54 (0,15)	0,40 (0,10)
19.	WFG9.M5	0,66 (0,16)	0,27 (0,08)
Slika 2. Predstavitev samoprilagodljivih krmilnih parametrov Figure 2. Self-adaptive control parameters presentation
uporabo populacijskih iskalnih algoritmov [8, 9, 10, 22, 1, 23, 16], kot so evolucijski algoritmi, ki so se pokazali kot zelo uporabni pri reševanju kompleksnih večkriterijskih optimizacij skih problemov [9].
3 Diferencialna evolucija za večkriterijsko optimizacijo s samoprilagajanjem
Za namen te študije smo uporabili algoritem za večkriterijsko optimizacijo DEMOwSA [21, 20]. Izvorni kod in idejna zasnova algoritma temeljita na algoritmu DEMO [16, 19], ki vsebuje večkriterijske selekcij ske strategije NSGA-II [10], SPEA2 [22] in IBEA [23]. Poleg selekcij skih strategij algoritem DEMO sestavlja še osnovni algoritem diferencialne evolucije (DE) [18]. Ker gre za osnovno varianto DE, DEMO nima mehanizma za samoprilagajanje krmilnih parametrov v DE. DE s samoprilagajanjem krmilnih parametrov deluje bolje in robust-neje [15, 6, 5, 7]. Pristop s samoprilagajanjem z varianto algoritma diferencialne evolucije so izbrali tudi drugi algoritmi za večkriterijsko optimizacijo [1,2].
V našem algoritmu DEMOwSA smo implementirali nov način mehanizma samoprilagajanja, ki je loga-ritmično normalno porazdeljeno samoprilagajanje krmilnih parametrov, znano iz evolucijskih strategij (ES) [4, 3]. V ES so krmilni parametri vključeni v posameznike skupaj z iskalnimi parametri. Vsak posameznik (glej sliko 2) algoritma DEMOwSA je razširjen s samopri-lagodljivimi krmilnimi parametri P in CR. Vrednosti teh parametrov se prilagajajo med evolucijskim procesom. V tem procesu izdelamo nov primerek iz starševskih primerkov v populaciji s pomočjo operatorjev selekcije,
Tabela 2. Rezultati za indikator R na testnih funkcijah 1-7 Table 2. Results for R indicator on the benchmark functions 1-7
	1. OKA2	2. SYMPART	3. S-ZDTl	4. S.ZDT2	5. S.ZDT4	6. R_ZDT4	7. S.ZDT6
Najboljši	-9,9912e-04	l,2418e-06	3,5832e-09	8,8060e-08	-5,1506e-09	l,1625e-04	-l,0216e-06
Srednji	-9,1005e-04	l,5838e-06	4,9212e-07	l,2702e-06	3,0912e-04	5,2437e-04	-l,0216e-06
Najslabši	-6,5077e-05	2,0972e-06	5,4084e-06	4,0190e-02	6,8877e-04	l,4756e-03	4,5350e-02
Povprečje	-8,4180e-04t	l,5972e-06t	9,3739e-07t	l,7634e-02	2,6829e-04t	5,7458e-04i	3,6224e-03*
Standardni odklon	2,2104e-04	l,9206e-07	l,2040e-06	2,0304e-02	l,8110e-04	3,1949e-04	l,2536e-02
Tabela 3. Rezultati za indikator R na testnih funkcijah 8-13 z M = 3 Table 3. Results for R indicator on the benchmark functions 8-13 when M — 3
	8. S.DTLZ2	9. R.DTLZ2	10. S.DTLZ3	11. WFG1	12. WFG8	13. WFG9
Najboljši	3,1669e-06	l,9488e-04	l,7962e-07	3,7746e-02	-2,667 le-02	-8,9602e-03
Srednji	l,9806e-05	2,7225e-04	l,3207e-06	4,1318e-02	-2,5825e-02	-7,8284e-03
Najslabši	3,7352e-05	l,8596e-03	5,9104e-06	4,3197e-02	-2,4263e-02	-6,3708e-03
Povprečje	l,9844e-05t	4,4428e-04t	l,6725e-06t	4,0943e-02t	-2,5818e-02i	-7,8520e-03t
Standardni odklon	8,9721e-06	3,9119e-04	l,4308e-06	l,6153e-03	6,030le-04	6,4689e-04
Tabela 4. Rezultati za indikator R na testnih funkcijah 8-13 z M = 5 Table 4. Results for R indicator on the benchmark functions 8-13 when M — 5
	8. S.DTLZ2	9. R.DTLZ2	10. S.DTLZ3	11. WFG1	12. WFG8	13. WFG9
Najboljši	7,0462e-06	7,3698e-05	l,3937e-06	4,5506e-02	-l,3866e-03	l,3504e-03
Srednji	l,0496e-05	9,3354e-05	l,9857e-06	4,6004e-02	9,113 le-04	2,4433e-03
Najslabši	l,8683e-05	2,2076e-04	3,0883e-06	4,6334e-02	2,7408e-03	3,2385e-03
Povprečje	l,0820e-05*	9,8614e-05t	2,0119e-06t	4,5998e-02$	6,5218e-04$	2,3653e-03t
Standardni odklon	2,7352e-06	3,0240e-05	4,3690e-07	2,2415e-04	l,0519e-03	4,9068e-04
SYMPART: F povp. SYMPART: Fst. dev.
0 1000 2000 3000 4000 5000 (a) SYMPART
1000 2000 3000 4000 5000 (b) S.ZDT4
0 1000 2000 3000 (c) S-DTLZ3 z M = 3
4000
WFG1_M3: F povp. WFG1 M3: F st. dev.
1000 2000 3000 (d) WFG1 z M = 3
4000
0.8 0.6 0.4 0.2
S_DTLZ3_M5: F povp. S DTLZ3 M5: F st. dev.
0	200	400
(e) S.DTLZ3 z M = 5
600
1
0.8 0.6 0.4 0.2
WFG1_M5: F povp. WFG1 M5: F st. dev.
200	400
(f) WFG1 z M = 5
600
Slika 3. Na 25 generacij povprečena vrednost povprečne izboljšane vrednosti krmilnega parametra F za 25 neodvisnih zagonov Figure 3. Each 25 generations-averaged value of the average improved value for control parameter F of 25 independent runs
križanja in mutacije.
Glavna razlika med algoritmoma DEMOwSA in DEMO je v operatorju mutacije. DEMOwSA za ustvarjanje novega posameznika za generacijo G + 1 uporablja samoprilagodljivi faktor ojačenja diferenčnega vektorja Fi za vsakega od posameznikov i iz generacije G:
Fi,G+! = (FG)i x eTjv(°'1), Tu r označuje stopnjo učenja in je ponavadi sorazmeren
s r ^ l/v/2£) ter D označuje dimenzijo problema. 7V(0,1) je po Gaussu normalno porazdeljeno naključno število. Izraz (Fg)% označuje povprečenje parametra F i-tega obravnavanega posameznika:
(FG)i = (FiiG + FruG + Fr2;G + Fr3iG)/4-
Vrednosti ri, r2 in 7-3 označujejo indekse uniformno naključno izbranih posameznikov iz generacije G, ki sodelujejo pri ustvarjanu novega posameznika v mutaci-
1
0.8 0.6 0.4 0.2 0
1000 2000 3000 4000 5000 (a) SYMPART
WFG1_M3: CR povp. WFG1_M3: CR St. dev.
1000 2000 3000 (d) WFG1 z M = 3
4000
1000 2000 3000 4000 5000 (b) S.ZDT4
S_DTLZ3_M5: CR povp. -S_DTLZ3_M5: CR St. dev.
0.6 0.4 0.2
0	200	400
(e) S.DTLZ3 z M = 5
600
1
0.8 0.6 0.4 0.2
S_DTLZ3_M3: CR povp. -S_DTLZ3_M3: CR St. dev.
1
0.8 0.6 0.4 0.2
0 1000 2000 3000 (c) S-DTLZ3 z M = 3
4000
WFG1_M5: CR povp. WFG1_M5: CR St. dev.
200	400
(f) WFG1 z M = 5
600
Slika 4. Na 25 generacij povprečena vrednost povprečne izboljšane vrednosti krmilnega parametra CR za 25 neodvisnih zagonov Figure 4. Each 25 generations-averaged value of the average improved value for the control parameter CR of 25 independent runs
Tabela 5. Rezultati za indikator Ijj na testnih funkcijah 1-7 Table 5. Results for I-ft indicator on the benchmark functions 1-7
	1. OKA2	2. SYMPART	3. S-ZDTl	4. S.ZDT2	5. S.ZDT4	6. R_ZDT4	7. S.ZDT6
Najboljši	5,2590e-03	3,6018e-06	l,3953e-04	l,9139e-04	8,4608e-07	3,2074e-04	-2,3094e-04
Srednji	7,6196e-03	4,7420e-06	l,4616e-04	2,1250e-04	l,4826e-03	l,7670e-03	-2,2958e-04
Najslabši	2,4920e-02	6,1155e-06	l,6669e-04	4,8226e-02	2,5823e-03	4,4835e-03	l,0198e-01
Povprečje	9,3329e-03t	4,7780e-06t	l,4747e-04	2,1184e-02	l,2154e-03t	l,7640e-03*	7,9347e-03i
Standardni odklon	5,8079e-03	5,4239e-07	5,1448e-06	2,4157e-02	7,3065e-04	9,5558e-04	2,8247e-02
Tabela 6. Rezultati za indikator na testnih funkcijah 8-13 z M = 3 Table 6. Results for I-ft indicator on the benchmark functions 8-13 when M — 3
	8. S.DTLZ2	9. R.DTLZ2	10. S.DTLZ3	11. WFG1	12. WFG8	13. WFG9
Najboljši	3,7128e-05	9,4432e-03	l,0378e-10	l,9567e-01	-l,6428e-01	-5,767 le-02
Srednji	8,1187e-05	l,1602e-02	l,2057e-08	2,1337e-01	-l,6045e-01	-5,4269e-02
Najslabši	l,3746e-04	l,9873e-02	2,3965e-07	2,2280e-01	-l,5359e-01	-5,0538e-02
Povprečje	8,2895e-05	l,2067e-02t	3,7420e-08t	2,1158e-0lt	-l,6011e-0lt	-5,4009e-02t
Standardni odklon	2,8280e-05	2,4892e-03	6,248 le-08	8,1245e-03	2,6295e-03	2,1130e-03
Tabela 7. Rezultati za indikator Ijj na testnih funkcijah 8-13 z M = 5 Table 7. Results for I-ft indicator on the benchmark functions 8-13 when M — 5
	8. S.DTLZ2	9. R.DTLZ2	10. S.DTLZ3	11. WFG1	12. WFG8	13. WFG9
Najboljši	4,4943e-07	7,5310e-03	3,6717e-10	5,1646e-01	-2,1199e-01	-l,2990e-01
Srednji	l,8934e-06	8,7524e-03	l,6341e-09	5,2159e-01	-l,9635e-01	-l,2384e-01
Najslabši	6,8299e-06	l,1796e-02	6,9752e-09	5,2409e-01	-l,7477e-01	-l,1667e-01
Povprečje	2,6355e-06$	8,8118e-03t	2,0630e-09t	5,2126e-01	-l,9555e-01$	-l,2346e-0lt
Standardni odklon	l,8277e-06	8,8397e-04	l,6132e-09	2,1147e-03	l,0860e-02	3,3397e-03
jskem procesu DE. Mutacij ski proces za ¿-tega muti-ranega posameznika v^g+i v generaciji G + 1 operira takole:
Vi,G+l = Xri,G + Fi,G+1 X (xr2,G ~ Xr3;G)•
Proces rekombinacije v algoritmu DEMOwSA je povzet iz strategije 'rand/l/bin\ tj. ene temeljnih strategij algoritma DE, zapisanih v [18, 12] oz. prvotnem
DEMO [16]. Krmilni parameter tega procesa, stopnjo križanja CR, smo prilagajali podobno kot krmilni parameter mutacije, stopnjo mutacije F, in zanj izbrali:
CRiiG+i = (CRG)i xeTN^\
ter podobno kot prej izračunali:
(CRG)i = (CRi,G + CRruG + CRr^G + CRr^c)/4.
Nov CRi^c je nato uporabljen pri izdelavi kandidata Ui,j,G+i z binarnim operatorjem križanja:
u.
i,j,G+1
Vi,j,G+1 if rand(0,1) < CR^g+i ali
J = Jrand Xij:G sicer,
kjer j G [1, D} označuje j-ti iskalni parameter, rand(0,1) G [0,1] pomeni vzorčenje uniformno (psevdo) naključno porazdeljenega naključnega števila in jrand pomeni uniformno naključen indeks iskalnega parametra, ki ga vedno vzamemo iz v i j,g+i (da bi s tem preprečili izdelavo enakih posameznikov).
Po križanju sledi operator selekcije, ki v G + 1 lahko zamenja z boljšim u^g+i in tako pomaga pri ustreznem prilagajanju parametrov F in CR, saj preživijo le posamezniki, ki se prilagajajo dobrim iskalnim in krmilnim parametrom. Zato se iskanje hitreje približa boljšim rešitvam, ki tudi bolj verjetno preživijo, ustvarijo več potomcev in s tem razširijo svoje krmilne parametre [11].
4 Poskusi in rezultati
Za namen študije smo v algoritmu DEMOwSA nastavili naslednje vrednosti parametrov. Krmilna parametra smo omejili na 0,1 < F < 0,9 in 1/24 < CR < 0,9. Parameter r smo nastavili na r = 2/^2D, kar sovpada s priporočili iz [4]. V začetni populaciji imajo vsi posamezniki krmilni parameter Finu = 0, 5 in krmilni parameter CRinu = 0,3 (predlagan v [16], izbran tudi v [19]). Za študijo smo izbrali selekcijsko strategijo SPEA2, kije dajala najboljše rezultate.
vrednosti, zato ni mogoče sklepati o fiksni vrednosti posameznega parametra, ki bi enako dobro delovala za vse funkcije. Pri vseh funkcijah vidimo, da začetne vrednosti CRinit = 0,3 ni med njimi, kar dodatno nakazuje na uspešno samoprilagajanje krmilnih parametrov. Po 5e+5 FES znaša razpon dobljenih povprečnih vrednosti za parameter F od 0,17±0,06 (SYMPART) do 0,68±0,15 (R_DTLZ2JM3) ter za parameter CR od 0,06±0,02 (S-DTLZ3JM5) do 0,75±0,16 (SYMPART). Krmilna parametra F in CR zajameta različne kombinacije nižjih in višjih vrednosti. Tako sta si pri funkciji S.DTLZ2 JM5 podobna ter pri funkcijah SYMPART in S_DTLZ3_M5 precej v kontrastu.
Ker je za nekatere izmed funkcij dinamika krmilnih parametrov F in CR precej različna, na slikah 3 in 4 prikazujemo tudi nekaj izbranih grafov le-teh. Iz slik vidimo, da vrednosti pogosto spreminjajo smer samoprilagajanja, saj algoritem menjava faze lokalnega in globalnega iskanja, ki ju krmilna parametra nadzorujeta.
Opravili smo tudi primerjavo med učinkovitostjo samoprilagajanja in fiksnimi krmilnimi parametri F in CR (z enakimi začetnimi nastavitvami za oba poskusa). Iz statističnih t-testov v tabelah 2-7 je razvidno, da je samoprilagajanje za algoritem boljše od fiksnih parametrov. Z f oz. £ označimo z 99,9-odstotno zanesljivostjo pomembno izboljšanje oz. poslabšanje pri samoprilagajanju, tj. skupaj 21 izboljšanj indikatorja, 12 poslabšanj in 5 brez razlik. Ker je iz študije dinamike krmilnih parametrov F in CR razvidno, da se ti precej spreminjajo in jih ni mogoče nastaviti enako za poljuben problem, samoprilagajanje še toliko bolj pomaga pri reševanju industrijskih problemov [8].
4.1	Indikatorji kakovosti
Predstavljeni algoritem smo 25-krat zagnali na 19 testnih funkcijah [13]. V tabelah 2-7 so najboljša, srednja (medi-alna), najslabša in povprečna vrednost ter standardna de-viacija za indikatorje [14] in Ijj (manjša vrednost je boljša) testnih funkcij po 500.000 ovrednotenjih (FES). Iz vseh dobljenih tabel za uporabljene indikatorje je opaziti, da je algoritem v veliki meri uspešen glede na indikatorje. Referenčne množice imajo vrednosti indikatorjev enako 0. Ko je dobljena vrednost indikatorja negativna, aproksimacijska množica presega kakovost podane referenčne množice glede na podan indikator.
4.2	Dinamika krmilnih parametrov F in CR
Iz tabele 1 vidimo povprečja vrednosti krmilnih parametrov F in CR pri vsaki od funkcij po 5e+5 FES. Posamezna vrednost pomeni povprečje (oz. standardni odklon) zadnjih 25 generacij za vse neodvisne zagone, za primerke, ki so izboljšali starševsko rešitev. Kot vidimo, se krmilna parametra samoprilagodita na precej različne
5	Sklep
V članku smo opravili študijo krmilnih parametrov pri samoprilagodljivem algoritmu diferencialne evolucije DEMOwSA. Z zmožnostjo samoprilagajanja krmilnih parametrov dosega algoritem v povprečju boljše rezultate pri večkriterijski optimizaciji in je bolj robusten za uporabo na novih funkcijah, saj uporabniku ni treba nastaviti krmilnih parametrov F in CR. S tem smo z algoritmom dosegli dva pomembna cilja. Kot nadaljnje delo vidimo izboljšavo mutacijskih in selekcijskih mehanizmov v večkriterijski optimizaciji.
6	Literatura
[1]	H.A. Abbass, R.Sarker in C.Newton. PDE: A Pareto-frontier Differential Evolution Approach for Multi-objective Optimization Problems. Y: Proceedings of the Congress on Evolutionary Computation 2001 (CEC'2001), letnik 2, str. 971-978, Piscataway, New Jersey, 2001. IEEE Service Center.
[2]	B. Y. Babu in M. M. Leenus Jehan. Differential Evolution for Multi-Objective Optimization. V: Proceedings of the 2003 Congress on Evolutionary Computa-
tion (CEC'2003), letnik 4, str. 2696-2703, Canberra, Australia, 2003. IEEE Press.
[3]	T. Bäck. Evolutionary Algorithms in Theory and Practice: Evolution Strategies, Evolutionary Programming, Genetic Algorithms. Oxford University Press, New York, 1996.
[4]	H. G. Beyer in H. P. Schwefel. Evolution strategies — A comprehensive introduction. Natural Computing, 1:3-52, 2002.
[5]	J. Brest, B. Boškovič, S. Greiner, V. Žumer in M. Sepesy Maučec. Performance comparison of self-adaptive and adaptive differential evolution algorithms. Soft Computing - A Fusion of Foundations, Methodologies and Applications, 11(7):617-629, 2007.
[6]	J. Brest, S. Greiner, B. Boškovič, M. Mernik in V. Žumer. S elf-Adapting Control Parameters V Differential Evolution: A Comparative Study on Numerical Benchmark Problems. IEEE Transactions on Evolutionary Computation, 10(6):646-657, 2006.
[7]	J. Brest, V. Žumer in M. S. Maučec. Population size in differential evolution algorithm. Elektrotehniški vestnik, 74(l-2):55-60, 2007.
[8]	C. A. Coello Coello. 20 Years of Evolutionary Multi-Objective Optimization: What Has Been Done and What Remains to be Done. V: Computational Intelligence: Principles and Practice, poglavje 4, str. 73-88. IEEE Computational Intelligence Soc., Vancouver, Canada, 2006.
[9]	K. Deb. Multi-Objective Optimization using Evolutionary Algorithms. John Wiley & Sons, Chichester, UK, 2001. ISBN 0-471-87339-X.
[10]	K. Deb, S. Agrawal, A. Pratab in T. Meyarivan. A Fast Elitist Non-Dominated Sorting Genetic Algorithm for Multi-Objective Optimization: NSGA-II. V: Proceedings of the Parallel Problem Solving from Nature VI Conference, str. 849-858, Paris, France, 2000. Springer. Lecture Notes in Computer Science No. 1917.
[11]	A. E. Eiben, R. Hinterding in Z. Michalewicz. Parameter control in evolutionary algorithms. IEEE Trans, on Evolutionary Computation, 3(2): 124-141, 1999.
[12]	V. Feoktistov. Differential Evolution: In Search of Solutions (Springer Optimization and Its Applications). Springer-Verlag New York, Inc., Secaucus, NJ, USA, 2006.
[13]	V. L. Huang, A. K. Qin, K. Deb, E. Zitzler, P. N. Sugan-than, J. J. Liang, M. Preuss in S. Huband. Problem Definitions for Performance Assessment & Competition on Multi-objective Optimization Algorithms. Technical Report TR-07-01, Nanyang Technological University et. al., Singapore, 2007.
[14]	J. Knowles, L. Thiele in E. Zitzler. A Tutorial on the Performance Assessment of Stochastic Multiobjective Optimizers. 214, Computer Engineering and Networks Laboratory (TIK), ETH Zurich, Switzerland, February 2006. Revised version.
[15]	K. Liang, X. Yao in C. Newton. Adapting Self-adaptive Parameters in Evolutionary Algorithms. Applied Intelligence, 15(3): 171—180, 2001.
[16]	T. Robič in B. Filipič. DEMO: Differential Evolution for Multiobjective Optimization. V: Proceedings of the Third International Conference on Evolutionary Multi-Criterion Optimization - EMO 2005, letnik 3410 of Lecture Notes in Computer Science, str. 520-533. Springer, 2005.
[17]	J. D. Schaffer. Multiple Objective Optimization with Vector Evaluated Genetic Algorithms. V: Proceedings of the 1st International Conference on Genetic Algorithms, str. 93-100, Mahwah, NJ, USA, 1985.
[18]	R. Storn in K. Price. Differential Evolution - A Simple and Efficient Heuristic for Global Optimization over Continuous Spaces. Journal of Global Optimization, 11:341-359, 1997.
[19]	T. Tušar in B. Filipič. Differential Evolution versus Genetic Algorithms in Multiobjective Optimization. V: Proceedings of the Fourth International Conference on Evolutionary Multi-Criterion Optimization - EMO 2007, letnik 4403 of Lecture Notes in Computer Science, str. 257-271. Springer, 2007.
[20]	A. Zamuda. Samoprilagajanje krmilnih parametrov pri algoritmu diferencialne evolucije za večkriterijsko optimizacijo. Mag. naloga, Fakulteta za elektrotehniko, računalništvo in informatiko, Univerza v Mariboru, 2008.
[21]	A. Zamuda, J. Brest, B. Boškovič in V. Žumer. Differential Evolution for Multiobjective Optimization with Self Adaptation. V: The 2007 IEEE Congress on Evolutionary Computation CEC 2007, str. 3617-3624. IEEE Press, 2007.
[22]	E. Zitzler, M. Laumanns in L. Thiele. SPEA2: Improving the Strength Pareto Evolutionary Algorithm for Multiobjective Optimization. V: Evolutionary Methods for Design Optimization and Control with Applications to Industrial Problems, strani 95-100, Athens, Greece, 2001. International Center for Numerical Methods in Engineering.
[23]	E. Zitzler in S. Kiinzli. Indicator-Based Selection in Multiobjective Search. V: X. Yao et al., editors, Parallel Problem Solving from Nature (PPSN VIII), str. 832-842, Berlin, Germany, 2004. Springer-Verlag.
Aleš Zamuda je leta 2008 magistriral na podiplomskem študijskem programu računalništvo in informatika na Fakulteti za elektrotehniko, računalništvo in informatiko Univerze v Mariboru. Trenutno je podiplomski študent in zaposlen v Laboratoriju za računalniške arhitekture in jezike, kjer raziskuje na področju večkriterijske optimizacije in proučuje mehanizme samoprilagajanja za diferencialno evolucijo. Je član IEEE Computational Intelligence Society.
Janez Brest je izredni profesor na Fakulteti za elektrotehniko, računalništvo in informatiko Univerze v Mariboru. Zaposlen je v Laboratoriju za računalniške arhitekture in jezike, kjer se ukvarja s paralelnim in porazdeljenim procesiranjem, s programskimi jeziki, ukvarja pa se tudi z optimizacijskimi raziskavami in evolucijskim računanjem s poudarkom na diferencialni evoluciji in samoprilagajanju krmilnih parametrov.
Borko Boškovič je diplomiral leta 2003 na Fakulteti za elektrotehniko, računalništvo in informatiko Univerze v Mariboru. Od leta 2000 je zaposlen v Laboratoriju za računalniške arhitekture in jezike, kjer se ukvarja s spletnim programiranjem, programskimi jeziki, evolucijskimi algoritmi in iskalnimi algoritmi s poudarkom na algoritmih za igranje iger med dvema igralcema, popolno informacijo in ničelno vsoto.