4.2 Potek optimizacije z roji delcev
Potek metode ORD bomo opisali v naslednjih petih korakih: definiranje prostora rešitev, definiranje objektivne funkcije, inicializacija naključne lokacije in hitrosti roja, sistematično letenje delcev skozi prostor rešitev ter ponovitev. Na sliki 7 je prikazan potek optimizacije z roji delcev.
43 Slika 7: Potek optimizacije z roji delcev
4.2.1 Definiranje prostora rešitev
Prvi korak pri optimizaciji z ORD je določitev parametrov (spremenljivk), ki jih bomo optimizirali. Določiti moramo še območje, v katerem bomo iskali optimalno rešitev, torej določimo zgornjo in spodnjo mejo vrednosti parametrov (spremenljivk) [14].
4.2.2 Definiranje objektivne funkcije
Pri drugem koraku definiramo objektivno funkcijo. Z njo povežemo ORD-algoritem s fizičnim svetom (zastavljeni problem). Pomembno je, da je funkcija zelo dobro definirana, saj z njo ocenjujemo kvaliteto predlaganih (potencialnih) rešitev [14].
4.2.3 Inicializacija naključne lokacije in hitrosti roja
Začetna lokacija delcev je generirana naključno. Prav tako je naključno generirana začetna hitrost in smer gibanja delcev. V prvi iteraciji ima torej delec naključno generirano svojo
44 najboljšo lokacijo 𝒙𝒙𝑖𝑖∗. Prva globalno najboljša lokacija 𝒈𝒈∗ je izbrana med vsemi posameznimi najboljšimi lokacijami na podlagi vrednosti objektivne funkcije v teh točkah [1], [14].
4.2.4 Sistematično letenje delcev skozi prostor rešitev
Vsak delec se mora sedaj premikati skozi prostor rešitev, kot da bi bil čebela v roju. Algoritem v vsaki iteraciji posamezni delec premakne za majhno razdaljo. Na posameznem delcu izvedemo naslednje korake:
Določitev sosednjih delcev
Okoli delca 𝑖𝑖 naključno izberemo določeno število sosednjih delcev. Posamezni delec 𝑖𝑖 in njegovi sosednji delci skupaj tvorijo podpopulacijo. Pri Matlab GOPP-u se naslednji podkoraki izvajajo na podpopulaciji, torej globalno optimalna rešitev velja le za trenutno podpopulacijo, v kateri se nahaja posamezni delec. V literaturi je pogosto predstavljen tudi drugačen pristop, kjer se ti podkoraki izvajajo na celotnem roju [1].
Oceni objektivno vrednost delca
Objektivno vrednost delca dobimo, ko v objektivno funkcijo vstavimo trenutno lokacijo (koordinate) delca. V podpopulaciji se med sabo primerjajo vse objektivne vrednosti. Na koncu se shrani najboljša objektivna vrednost in njena pripadajoča lokacija 𝒈𝒈∗ [1].
Posodobi hitrost delca
Spreminjanje hitrosti delca je ključni del optimizacije z ORD. Hitrost spreminjamo na podlagi lokacij 𝒙𝒙𝑖𝑖∗ in 𝒈𝒈∗(najboljša globalna lokacija v podpopulaciji) z enačbo (4.1). Za vsak delec 𝑖𝑖 določimo njegovo trenutno lokacijo 𝒙𝒙𝑖𝑖 in hitrost 𝒗𝒗𝑖𝑖. Novi vektor hitrosti je določen z enačbo (4.1).
𝒗𝒗𝑖𝑖𝑡𝑡+1 =𝒗𝒗𝑖𝑖𝑡𝑡+𝛼𝛼 ⋅ 𝒓𝒓1(𝒈𝒈∗− 𝒙𝒙𝑖𝑖𝑡𝑡) +𝛽𝛽 ⋅ 𝒓𝒓2�𝒙𝒙𝑖𝑖∗(𝑡𝑡)− 𝒙𝒙𝑖𝑖𝑡𝑡� (4.1) Kjer sta parametra 𝛼𝛼 in 𝛽𝛽 pospeševalni konstanti, ki imata tipično vrednost okoli 2. Z njima določimo privlačnost lokacij 𝒙𝒙𝑖𝑖∗ in 𝒈𝒈∗. Parameter β določi, kolikšen vpliv na delec ima njegov spomin na njegovo najboljšo lokacijo. S parametrom α pa določimo, kolikšen vpliv na delec ima ostali del roja. S povečevanjem parametra β spodbujamo raziskovanje prostora rešitev, saj se vsak delec premika v smeri svoje najboljše lokacije. S povečevanjem parametra α pa spodbujamo izkoriščanje predpostavljenega globalnega optimuma [2], [13], [14].
Vrednosti 𝒓𝒓1 in 𝒓𝒓2 sta naključna vektorja, generirana v intervalu med [0 1]. Z njima simuliramo majhno nepredvidljivost v obnašanju roja [14].
Kot smo že omenili, obstaja veliko novih izpeljank standardne ORD, najbolj pogosto uporabljena izboljšava algoritma je uporaba vztrajnostne funkcije 𝜃𝜃(𝑡𝑡), ki hitrost 𝒗𝒗𝑖𝑖𝑡𝑡 spremeni
45 v 𝜃𝜃(𝑡𝑡)⋅ 𝒗𝒗𝑖𝑖𝑡𝑡. Ta izpeljanka je uporabljena v Matlab GOPP-u. Enačba (4.1) se sedaj preoblikuje v enačbo (4.2) [2].
𝒗𝒗𝑖𝑖𝑡𝑡+1 =𝜃𝜃(𝑡𝑡)⋅ 𝒗𝒗𝑖𝑖𝑡𝑡+𝛼𝛼 ⋅ 𝒓𝒓1(𝒈𝒈∗− 𝒙𝒙𝑖𝑖𝑡𝑡) +𝛽𝛽 ⋅ 𝒓𝒓2�𝒙𝒙𝑖𝑖∗(𝑡𝑡)− 𝒙𝒙𝑖𝑖𝑡𝑡� (4.2) Vrednost vztrajnostne funkcije imenujemo tudi vztrajnostna masa. Z njo določimo, do kolikšne mere delec ostaja na svojo prvotni poti, na katero 𝒙𝒙𝑖𝑖∗ in 𝒈𝒈∗ nimata vpliva. Uporaba 𝜃𝜃(𝑡𝑡) je ekvivalentna uvedbi navidezne mase za stabilizacijo gibanja delcev, kar posledično privede do hitrejše konvergence. Vrednost je konstantna, po navadi v intervalu med [0 1]. Večja vztrajnostna masa pomeni večje globalno raziskovanje, saj delce lokaciji 𝒙𝒙𝑖𝑖∗ in 𝒈𝒈∗ manj privlačita. Nasprotno pa manjša masa pomeni, da delci bolje izkoristijo lokalno območje, saj imata 𝒙𝒙𝑖𝑖∗ in 𝒈𝒈∗ večji vpliv na njih. V Matlab GOPP-u je možna tudi opcija, kjer vrednost vztrajnostne mase linearno zmanjšujemo skozi optimizacijo. Na začetku je vrednost večja, saj s tem potenciramo raziskovanje prostora, nato pa jo postopoma zmanjšujemo, da delci bolje izkoristijo prostor okoli 𝒙𝒙𝑖𝑖∗ in 𝒈𝒈∗ [1], [2], [14].
Premik delca
Ko enkrat določimo hitrost delca, lahko enostavno izračunamo njegovo novo lokacijo. Končna hitrost delca je teoretično lahko neskončna, vendar jo omejimo na 𝒗𝒗𝑚𝑚𝑚𝑚𝑚𝑚. S spremembo hitrosti lahko torej določimo novo lokacijo delca (enačba (4.3)) [2], [13], [14].
𝒙𝒙𝑖𝑖𝑡𝑡+1 =𝒙𝒙𝑖𝑖𝑡𝑡+𝒗𝒗𝑖𝑖𝑡𝑡+1 (4.3) Ponovno oceni objektivno vrednost delca
Sedaj se ponovno oceni objektivno vrednost posameznih delcev. Če je objektivna vrednost trenutne lokacije boljša od vrednosti posameznikove najboljše lokacije 𝒙𝒙𝑖𝑖∗, potem najboljšo lokacijo zamenjamo s trenutno [14].
Nato se primerjava izvede še na celotnem roju, kjer se objektivna vrednost delca na trenutni lokaciji primerja z vrednostjo na globalno najboljšo lokaciji 𝒈𝒈∗. Če nam v trenutni iteraciji uspe (v primeru iskanja globalnega minimuma) zmanjšati globalno najboljšo objektivno vrednost, potem je treba spremeniti še vrednost vztrajnostne funkcije [1].
4.2.5 Ponovitev
Pravkar opisani proces se izvede za vsak posamezni delec v roju v vsaki iteraciji optimizacije in se izvaja v zanki od 4. koraka naprej (sistematično letenje delcev skozi prostor rešitev).
Optimizacija se zaključi, ko so izpolnjeni pogoji za izvršitev prekinitve. Kriterij prekinitve je lahko določeno število izvedenih iteracij, dosežena željena vrednost objektivne funkcije, itd.
[14].
46 Na sliki 8 je shematično prikazano premikanje oziroma konvergiranje roja delcev v optimalno lokacijo. Na sliki so zaradi jasnosti narisane poti le 4 delcev, pri realni problemih pa je za natančno optimizacijo treba uporabiti več delcev. Optimalno število delcev je odvisno od zastavljenega problema in željene natančnosti rezultata, v naslednjem podpoglavju (4.3 Velikost roja) pa je opisana priporočljiva velikost roja za inženirske probleme.