Diferencialni pristop s stigmergijo mravelj k optimizaciji v zveznem prostoru
Peter Korošec1,2, Jurij Šile1
1	Institut " Jožef Štefan", Odsek za računalniške sisteme, Jamova cesta 39, SI-1000 Ljubljana, Slovenija
2	Univerza na Primorskem, Fakulteta za matematiko, naravoslovje in informacijske tehnologije, Glagoljaška 8, SI-6000 Koper, Slovenija
E-pošta: peter, korosec @ ijs. si
Povzetek. V prispevku je predstavljena optimizacijska metoda s kolonijami mravelj za optimizacijo v zveznem prostoru. Predlaganje nov splošen optimizacijski algoritem, imenovan DASA (iz angl. Differential Ant-Stigmergy Algorithm), kije primerjan z znanimi in uveljavljenimi evolucijskimi algoritmi za zvezno optimizacijo. Ovrednotenje algoritma DASA, ki je narejeno na standardni množici preskusnih problemov, kaže na njegovo primernost in uporabnost pri reševanju težkih optimizacij skih problemov v zveznem prostoru.
Ključne besede: stigmergija, optimiziranje, zvezni prostor, preskusne funkcije
A Differential Ant-Stigmergy Approach to Continuous Optimization
Extended abstract. The paper presents an extension of the ant-colony optimization metaphor for continuous domain. This new approach was named a Differential Ant-Stigmergy Algorithm (DASA) and was studied on a set of benchmark suite of real-parameter optimization problems defined in 2005 at the IEEE Congress of Evolutionary Computation.
The algorithm was compared with a number of evolutionary optimization algorithms including Covariance Matrix Adaptation Evolutionary Strategy, Differential Evolution, Real-Coded Memetic Algorithm, and Continuous Estimation of Distribution Algorithm.
The result obtained indicates a promising performance of the new approach. One can notice that for a small number of function evaluations the DASA performs better than the rest of the algorithms. Since the selected test functions reflect a different kind of pseudo-real optimization problems, the DASA is applicable to many real-parameter optimization problems.
In future, the important issue of pure continuous ant-stigmergy algorithm needs to solved. Here, the so-called parameter differences will be in a continuous form instead in the fine-grained discrete form.
Key words: stigmergy, optimization, continuous space, benchmark functions
načinu komunikacije v koloniji mravelj, kjer so te vodene s sledjo feromonov. Pri sestavljanju rešitev se uporablja hevristika, temelječa na verjetnostnem pravilu, ki pravi, daje verjetnost neke odločitve določena z intenzivnostjo feromonov in dodatno hevristično informacijo. Slednja zajema znanje o reševanem problemu, ki je pridobljeno pred izvajanjem algoritma.
Algoritem ACO, ki je bil uspešno uporabljen na klasičnih NP-težkih kombinatoričnih optimizacij skih problemih, je bil v Elektrotehniškem vestniku že predstavljen [6,7,9]. Vendar pa neposredna uporaba algoritma ACO za reševanje optimizacij skih problemov z realnimi parametri ni preprosta. Do zdaj je bilo predlaganih le nekaj prilagoditev algoritma ACO za optimizacijo v zveznem prostoru [2,5,11,13].
V tem sestavku je predstavljen nov, diferencialni pristop s stigmergijo mravelj, ki je primeren za optimizacijo v zveznem prostoru.
1 Uvod
Marco Dorigo je v svoji doktorski disertaciji [4] predstavil zanimiv optimizacij ski algoritem, imenovan optimizacija s kolonijami mravelj (ACO iz angl. Ant-Colony Optimization). Algoritem se zgleduje po posrednem
2 Diferencialni pristop s stigmergijo mravelj
2.1 Diskretizacija zveznega prostora
Prevedba zvezne v drobnozrnato diskretno obliko poteka na naslednji način. Naj bo p\ trenutna vrednost ¿-tega parametra pi. Med iskanjem njegove optimalne vrednosti se parametru pi prireja nova vrednost takole:
pi=p'i + Si
d)
Slika 1. Predstavitev z diferencialnim grafom Figure 1. Differential graph representation
Pri tem je Si t. i. diferenca parametra in je izbrana iz množice A* = Ar U {0} U A+, kjer je
At = {5+k\6+k = bk+L<~\k = l,2,...,di}.
Tu je di = Ui — L i + 1. Za vsak parameter^ je njegova diferenca & iz intervala med b l in
, kjer je b t. i. baza
diskretizacije. Pri tem velja Lt = [log6(s^)J in Ui = [log6 (max(pi) — min(pi))J. S konstanto e\ je nastavljena največja natančnost parametra pi, ki je omejena z računalniško aritmetiko s plavajočo vejico.
2.2 Preiskovalni graf
Iz množic A^, 1 < i < D se zgradi t. i. diferencialni graf Q = (V,E), kjer je V množica vozlišč, E množica povezav med njimi in D število parametrov (slika 1). Množica A^ je predstavljena z množico vozlišč
Vi = {viA,..., Vi^di+i} in velja V = \J?=1 Vi. Torej je predstavitev
= |'■■■'Si~,di-U-1)' ■ ■ ■''°> A~
K:..........'V.,;,)
A+
X
enakovredna predstavitvi
Vi =	• • • ... ,Vi,di,Vi,di+i,
o
Vi,di+ 2, ■ ■ ■ , l^di + l+j J ■ ■ ■ J Vi,2di + 1
kjer velja j = 1, 2,..., di ter vid
Vi,di+1 0 in viidi+i+j
Da bo omogočeno bolj prosto premikanje po iskalnem prostoru je dodana utež cj, tako da enačba (1) preide v:
P* = Pi H-	(2)
kjer je o; naključno izbrano celo število z intervala [1,6).
Vsako vozlišče iz množice Vi je povezano z vsemi vozlišči, ki pripadajo množici V^+i. Torej je Q usmerjen graf, kjer so vse poti, ki se začno v začetnem vozlišču start in končajo v enem od končnih vozlišč, enako dolge. Pot v je definirana kot: v = v\ • • • Vi • • • vd, kjer je Vi G 14 i = 1,2,..., D.
2.3 Algoritem DASA
Zastavljena optimizacij ska naloga je poiskati takšno pot v, da bo /(p) < /(p'), kjer je p' trenutna najboljša rešitev in p = p' + A (v) (z upoštevanjem enačbe (2) za vse elemente pi G p). Ce je vrednost kriterijske funkcije/(p) manjša od /(p;)> se vrednost p' nadomesti z vrednostjo p.
Psevdo koda (algoritem 1) opisuje diferencialni pristop s stigmergijo mravelj k optimizaciji v zveznem prostoru, imenovan algoritem DASA (iz angl. Differential Ant-Stigmergy Algorithm).
Algoritem 1 DASA l: p/ = Naključna_rešitev(parametri) 2: najboljša = Ovrednotenje( pO 3: preiskovalni_graf = Inicializacija(parametri) 4: Inicializacij a_grafa(začetna_količina_feromona) 5: while ni izpolnjen pogoj za končanje do 6: 7:
trenutno .najboljša = inf for all m mravelj do
pot = Najdena_pot(preiskovalni_graf) p = p' + cjč(pot) rezultat = Ovrednotenj e(p) if rezultat < trenutno .najboljša then trenutno .najboljša = rezultat
najbolj ša.pot = pot pb=p
end if end for
if trenutno .najboljša < najboljša then
najboljša = trenutno .najboljša p'=pb
Prerazporeditev _feromona(najboljša_pot) end if
Izhlapevanje Jeromona(preiskovalni^graf) Izredna_akcija	//možnost
9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23:
24: end while
Najprej se izbere, lahko tudi naključno, neka rešitev p', ki se tudi ovrednoti. Nato se kreira preiskovalni graf, v katerega vozlišča se odloži začetna količina feromona. To se naredi takole. Za vsako množico vozlišč V C V, 1 < i < D, ki pomeni parameter pi, se feromon porazdeli po Gaussovi funkciji
Gauss (pi, p, a) = rz° +
r\/27r
(p i-p)2 ' 2CT2
kjer je /i srednja vrednost, a standardni odklon in r2° najnižja vrednost količine feromona za parameter pi. Na začetku velja p = 0, cr = 1 in crmax = 1 (glej sliko 2).
Pi

Pi-1:
©•••© ••• 0
©-© •• © •• ©
Pd : (va
Slika 2. Začetna porazdelitev feromona Figure 2. Initial pheromone distribution
Jedro algoritma je zanka, kjer ob vsaki ponovitvi m mravelj sočasno začne pot po preiskovalnem grafu (vedno iz vozlišča start). Mravlje izberejo naslednje vozlišče na svoji poti po verjetnostnem pravilu; mravlja a se v koraku i premakne iz nekega vozlišča v množici Vi-1 v vozlišče

G ..., Vii2di+i} z verjetnostjo:
prob - (a, i) =


l<k<2di+l
r{vi:ky
kjer je r(v^k) količina feromona v vozlišču v^k- To ponavlja, dokler ne doseže končnega vozlišča. Tako ustvarjena pot (oz. rešitev) p se ovrednoti s kriterijsko funkcijo /(p). Najboljša izmed m rešitev se primerja s trenutno najboljšo. Ce je ta rešitev boljša, potem postane to nova trenutno najboljša rešitev. Kadar se to zgodi, se količina feromona prerazporedi glede na pot, s katero je bila ta, nova trenutno najboljša rešitev, dosežena (glej sliko 3). Izhlapevanje feromona je upoštevano pri spreminjanju faktorjev /j, in cr takole:
^NEW = ^ _ ^OLD
" (l + p)aOLD (1 + p)aOLD < crmax
1
(jmax otherwise
kjer je p v naprej določen faktor izhlapevanja.
Postopek se ponavlja, dokler ni izpolnjen pogoj za končanje (npr. vnaprej omejeno število ovrednotenj). Skozi izvajanje algoritma se crmax počasi zmanjšuje in s tem se izboljšuje konvergenca algoritma (tj. primer izredne akcije).
Figure 3. Pheromone distribution
3 Uspešnost algoritma DASA
3.1	Eksperimentalno okolje
Preskusi so potekali na računalniškem sistemu s procesorjem AMD Opteron™ 2.6-GHz, 2 GB RAM pomnilnika in operacijskim sistemom Microsoft® Windows® XP. Algoritem DASA je izveden v programskem jeziku Borland® Delphi™.
Algoritem DASA ima tri parametre: število mravelj m, faktor izhlapevanja feromonov p in natančnost parametrov s, ki so predmet optimizacije. Za parametre so bile izbrane naslednje vrednosti: m = 10, p = 0.1 in e = 10-12. Te so bile določene na podlagi omejenega števila predhodnih preskusov (brez podrobnejšega finega nastavljanja).
3.2	Preskusne funkcije
Algoritem DASA je bil preskušen na štirih 30 dimenzijskih preskusnih funkcijah. Podroben opis funkcij je na voljo v [12].
Funkcija /3 (Shifted Rotated High Conditional Elliptic Function) je enomodalna, /9 (Shifted Rastrigin's Function) pa je večmodalna. Funkciji /13 (Expanded Extended Griewangk's plus Rosenbrock's Function) in /15 (Hybrid Composition Function) sta rezultat kompozicije več funkcij.
3.3	Primerjani algoritmi
Algoritem DASA je bil na podoben način kot v [3] primerjan s štirimi uveljavljenimi populacijskimi algoritmi:
• evolucijsko strategijo z adaptacijo kovariančne matrike (CMA-ES) [1],
•	diferencialno evolucijo (DE) [10],
•	memetskim algoritmom (MA) [8] in
•	evolucijskim algoritmom z oceno distribucije (EDA) [14],
ki so bili 2005 predstavljeni na kongresu IEEE o evolucijskem računanju leta 2005.
3.4 Ovrednotenje
Algoritme smo ovrednotili glede na napako funkcije (oz. odstopanje od optimuma) e = /(p) — /(p*), kjer je p* znani optimum. Napako funkcije smo izračunali po 1000 in 300.000 ovrednotenjih. Te podatke smo zbrali s 25-kratno optimizacijo vsake funkcije, nakar smo naredili statistično analizo; poiskali smo najboljšo in najslabšo vrednost in mediano, izračunali smo tudi aritmetično sredino in standardni odklon. Vrednosti so zbrane v tabelah 1 in 2.
Prikazani rezultati kažejo obetavno kakovost algoritma DASA. Po razvrščanju glede na aritmetično sredino napake se je naš algoritem pri majhnem številu ovrednotenj (1000) izkazal kot najboljši, pri velikem številu ovrednotenj (300 000) pa kot drugi najboljši, takoj za algoritmom CMA-ES.
Konvergenca algoritma DASA za preskusne funkcije /3, /9, /13 in /15 je prikazana na sliki 4, in sicer kot povprečje 25-kratne optimizacije vsake od funkcij. Slika prikazuje odvisnost povprečne vrednosti napake od števila ovrednotenj.
1.E+12 1.E+10 1.E+08 « 1.E+06
| 1.E+04
i 1.E+02
| 1.E+00 c
£ 1.E-02 ©
o. 1.E-04 >
a- 1.E-06 1.E-08 1.E-10 1.E-12
0 50000 100000 150000 200000 250000 300000 število ovrednotenj
Slika 4. Konvergenca algoritma DASA za preskusne funkcije Figure 4. Convergence for the DASA algorithm on test funetions
4 Sklep
Predlaganje bil nov splošen optimizacijski algoritem, ki je bil primerjan z nekaterimi znanimi evolucijskimi algo-
funkcija	napaka	CMA-ES					DE		MA			EDA		DASA	
po 1000 ovrednotenjih															
	najmanjša	4	07	io-	9	5,46		•104	5,55	• 105	2	27	• 106	1,27	• 105
	mediana	5	44	io-	9	2,	43	• 105	7,64	• 105	3	66	• 106	4,32	• 105
h	največja	8	66	io-	9	9,00		• 105	1,56	• 106	5	88	• 106	8,15	• 105
	aritmetična sredina	5	55	io-	9	2,	89	• 105	8,77	• 105	3	75	• 106	4,59	• 105
	standardni odklon	1	09	io-	9	1,93		• 105	5,81	•104	9	09	• 105	2,02	• 105
	najmanjša	4	35	io-	6			0	7,78-	io-9	2	10	•102		0
	mediana	9	95	io-	1			0	9,95-	lo-1	2	30	•102		0
h	največja	4	97					0		1,99	2	48	•102		0
	aritmetična sredina	9	38-	io-	1			0	6,81 •	io-1	2	30	•102		0
	standardni odklon	1	18					0	1,21-	io-1			9,44		0
	najmanjša	1	10					2,31		1,33	3	82	•101	9,62-	io-1
	mediana	2	61					3,89		2,54	6	86	•101		1,93
/l3	največja	3	20			1,	39	•101	1,03	•101	1	29	•102		2,56
	aritmetična sredina	2	49					4,51		3,96	7	36	•101		1,88
	standardni odklon	5	13	io-	1			2,26	5,38-	io-1	2	36	•101	3,99-	io-1
	najmanjša	2	00	102		4	75	•102	2,00	•102	4	35	•102		0
	mediana	2	00	102		4	81	•102	3,00	•102	4	59	•102	3,00	•102
/l5	največja	3	00	102		5	86	•102	5,00	•102	5	63	•102	5,00	•102
	aritmetična sredina	2	08	102		4	84	•102	3,56	•102	4	81	•102	2,33	•102
	standardni odklon	2	75	101		2	14	•101	1,51	•101	4	67	•101	1,58	•102
po 300.000 ovrednotenjih															
	najmanjša	3	84	108		2	18	•108	9,63	•107	8	95	•108	6,11	•107
	mediana	1	00	109		5	66	•108	2,69	•108	1	23	•109	2,80	•108
h	največja	2	07	109		9	53	•108	5,82	•108	1	92	•109	5,57	•108
	aritmetična sredina	1	07	109		5	53	•108	2,94	•108	1	25	•109	3,10	•108
	standardni odklon	4	43	108		1	78	•108	3,04	•107	2	67	•108	1,31	•108
	najmanjša	2	19	102		2	99	•102	1,82	•102	4	07	•102	4,60	•IO1
	mediana	2	50	102		3	72	•102	3,00	•102	4	76	•102	9,13	•IO1
h	največja	2	87	102		4	25	•102	4,00	•102	5	44	•102	1,52	•102
	aritmetična sredina	2	53	102		3	77	•102	2,99	•102	4	80	•102	9,29	•IO1
	standardni odklon	1	65	101		3	00	•101	1,00	•101	3	51	•101	2,75	•IO1
	najmanjša	3	05	101		3	12	•104	4,09	•102	4	66	• 105	1,33	•IO4
	mediana	7	36	101		1	29	• 105	3,86	• 103	7	39	• 105	1,38	• 105
/l3	največja	4	98	102		4	33	• 105	1,06	•104	1	13	• 106	6,47	• 105
	aritmetična sredina	1	14	102		1	62	• 105	3,95	• 103	7	50	• 105	2,12	• 105
	standardni odklon	1	07	102		8	66	•104	4,62	•102	1	93	• 105	1,81	• 105
	najmanjša	4	93	102		8	82	•102	5,46	•102	1	03	• 103	2,32	•102
	mediana	6	93	102		1	08	• 103	7,49	•102	1	14	•103	6,28	•102
/l5	največja	8	51	102		1	19	• 103	1,05	• 103	1	21	•103	7,84	•102
	aritmetična sredina	6	69	102		1	08	• 103	7,62	•102	1	13	• 103	5,89	•102
	standardni odklon	1	15	102		7	13	•101	2,64	•101	4	50	•101	1,50	•102
Tabela 1. Vrednosti napake po 1000 in 3000.000 ovrednotenjih Table 1. Error values after 1000 and 300, 000 function evaluations
ritmi za zvezno optimizacijo. Ovrednotenje je bilo narejeno na standardni množici preskusnih problemov in je potrdilo njegovo primernost in uporabnost za reševanje težkih optimizacijskih problemov v zveznem prostoru.
5 Literatura
[1] A. Auger, N. Hansen, A restart CMA evolution strategy with increasing population size, Proc. IEEE Congress on Evolutionary Computation, Edinburgh, UK, Sept. 2005.
[2]	G. Bilchev, I. C. Parmee, The ant colony metaphor for searching continuous design spaces, Lect. Notes Comp. Sc. 993, 1995, pp. 25-39.
[3]	J. Brest, B. Boškovič, S. Greiner, Y. Žumer, M. Sepesy Maučec, Performance comparison of self-adaptive and adaptive differential evolution algorithms, Soft Comput. 11, 2007, pp. 617-629.
[4]	M. Dorigo, Optimization, learning and natural algorithms, PhD thesis, Dipartimento di Elettronica, Politécnico di Milano, Italy, 1992.
[5]	J. Dréo, P. Siarry, A new ant colony algorithm using the heterarchical concept aimed at optimization of multimin-ima continuous functions, Lect. Notes Comp. Sc. 2463, 2002, pp. 216-227.
[6]	P. Korošec, J. Sile, B. Robič, Populacijske metode kot oblika metahevristične kombinatorične optimizacije, Elek-troteh. vestn. 72, 2005, pp. 214-219.
[7]	P. Korošec, J. Sile, B. Robič, Razdelitev mreže s kolonijami mravelj, Elektroteh. vestn. 73, 2006, pp. 215-220.
[8]	D. Molina, F. Herrera, M. Lozano, Adaptive local search parameters for real-coded memetic algorithms, P roc. IEEE Congress on Evolutionary Computation, Edinburgh, UK, Sept. 2005.
[9]	I. Pešl, V. Zuner, J. Brest, Optimizacija s pomočjo kolonije mravelj, Elektroteh. vestn. 73, 2006, pp. 93-98.
[10] J. Ronkkonen, S. Kukkonen, K. V. Price, Real-parameter optimization with differential evolution, Proc. IEEE Congress on Evolutionary Computation, Edinburgh, UK, Sept. 2005.
[11]	K. Socha, ACO for continuous and mixed-variable optimization, Lect. Notes Comp. Sc. 3172, 2004, pp. 25-36.
[12]	P. N. Suganthan, N. Hansen, J. J. Liang, Y. -P. Chen, A. Auger, S. Tiwari, Problem Definitions and Evaluation Criteria for the CEC 2005 Special Session on Real-Parameter Optimization, Technical Report, Nanyang Technological University, Singapore, May 2005.
[13]	S. Tsutsui, An enhanced aggregation pheromone system for real-parameter optimization in the ACO metaphor, Lect. Notes Comp. Sc. 4150, 2006, pp. 60-71.
[14]	B. Yuan, M. Gallagher, Experimental results for the special session on real-parameter optimization at CEC 2005: A simple, continuous EDA, Proc. IEEE Congress on Evolutionary Computation, Edinburgh, UK, Sept. 2005.
Peter Korošec je raziskovalec na Institutu "Jožef Štefan" v Ljubljani in predavatelj na Fakulteti za matematiko, naravoslovje in informacijske tehnologije v Kopru. Njegovo raziskovalno področje je uporaba metahevrističnih optimizaci-jskih metod pri numeričnem in kombinatoričnem optimiziranju.
Jurij Sile je višji znanstveni sodelavec na Odseku za računalniške sisteme Instituta "Jožef Štefan" v Ljubljani. Raziskovalno se ukvarja računalniškimi sistemi in strukturami ter metahevrističnim optimiziranjem.