Optimizacije v inženirstvu Reševanje problemov z metahevrističnimi metodami v okolju MATLAB Avtorja Janez Gotlih Mirko Ficko November 2025 Naslov Optimizacije v inženirstvu Title Optimization in Engineering Podnaslov Reševanje problemov z metahevrističnimi metodami v Subtitle okolju MATLAB Solving Problems With Metaheuristic Methods in MATLAB Avtorja Janez Gotlih Authors (Univerza v Mariboru, Fakulteta za strojništvo) Mirko Ficko (Univerza v Mariboru, Fakulteta za strojništvo) Recenzija Miran Brezočnik Review (Univerza v Mariboru, Fakulteta za strojništvo) Simon Klančnik (Univerza v Mariboru, Fakulteta za strojništvo) Jezikovni pregled Danica Gotlih Language editing Tehnična urednika Marina Bajić Technical editors (Univerza v Mariboru, Univerzitetna založba) Jan Perša (Univerza v Mariboru, Univerzitetna založba) Oblikovanje ovitka Jan Perša Cover designer (Univerza v Mariboru, Univerzitetna založba) Grafika na ovitku Striped textile, foto: Scott Wemb, unsplash.com, 2020 Cover graphic Grafične priloge Vsi viri so lastni, če ni navedeno drugače. Graphic material Gotlih, Ficko (avtorja), 2025 Založnik Univerza v Mariboru Published by Univerzitetna založba Slomškov trg 15, 2000 Maribor, Slovenija https://press.um.si, zalozba@um.si Izdajatelj Univerza v Mariboru Issued by Fakulteta za strojništvo Smetanova ulica 17, 2000 Maribor, Slovenija https://www.fs.um.si/, fs@um.si Izdaja Prva izdaja Edition Vrsta publikacije E-knjiga Publication type Dostopno na https://press.um.si/index.php/ump/catalog/book/1076 Available at Published at Izdano Maribor, Slovenija, november 2025 © Univerza v Mariboru, Univerzitetna založba / University of Maribor, University of Maribor Press Besedilo / Text © Gotlih, Ficko (avtorja), 2025 To delo je objavljeno pod licenco Creative Commons Priznanje avtorstvaNekomercialno 4.0 Mednarodna./This work is published under a Creative Commons 4.0 International licence (CC BY NC 4.0). Uporabnikom je dovoljeno reproduciranje, distribuiranje, dajanje v najem, javna priobčitev in predelava izvirnega ali derivativnega avtorskega dela, vendar samo v nekomercialne namene ter pod pogojem, da navedejo avtorja dela. Vsa gradiva tretjih oseb v tej knjigi so objavljena pod licenco Creative Commons, razen če to ni navedeno drugače. Če želite ponovno uporabiti gradivo tretjih oseb, ki ni zajeto v licenci Creative Commons, boste morali pridobiti dovoljenje neposredno od imetnika avtorskih pravic. https://creativecommons.org/licenses/by-nc/4.0/ CIP - Kataložni zapis o publikaciji Univerzitetna knjižnica Maribor 62:519.8(035)(0.034.2) GOTLIH, Janez Optimizacije v inženirstvu [Elektronski vir] : reševanje problemov z metahevrističnimi metodami v okolju MATLAB / avtorja Janez Gotlih, Mirko Ficko. - 1. izd. - E-knjiga. - Maribor : Univerza v Mariboru, Univerzitetna založba, 2025 Način dostopa (URL): https://press.um.si/index.php/ump/catalog/book/1076 ISBN 978-961-299-079-4 (PDF) doi: 10.18690/um.fs.11.2025 COBISS.SI-ID 256635651 ISBN 978-961-299-079-4 (pdf) DOI https://doi.org/10.18690/um.fs.11.2025 Cena Brezplačni izvod Price Odgovorna oseba založnika Prof. dr. Zdravko Kačič, For publisher rektor Univerze v Mariboru Citiranje Gotlih, J., Ficko, M.(2025). Optimizacije v inženirstvu: reševanje Attribution problemov z metahevrističnimi metodami v okolju MATLAB. Univerza v Mariboru, Univerzitetna založba. doi:10.18690/um.fs.11.2025 OPTIMIZACIJE V INŽENIRSTVU: REŠEVANJE PROBLEMOV Z METAHEVRISTIČNIMI METODAMI V OKOLJU MATLAB J. Gotlih, M. Ficko Kazalo 1 Uvod .......................................................................................................................... 1 2 Optimizacija z enim ciljem ....................................................................................... 5 2.1 Vaje s področja optimizacij z enim ciljem ........................................................................................ 6 2.1.1 Vaja: Enodimenzionalne optimizacije z enim ciljem ...................................................................... 7 2.1.2 Vaja: Večdimenzionalne optimizacije z enim ciljem .................................................................... 10 2.1.3 Vaja: Optimizacija s škatlastimi omejitvami ................................................................................... 11 2.1.4 Vaja: Optimizacija z enakovrednostnimi omejitvami ................................................................... 14 2.1.5 Vaja: Optimizacije z neenakovrednostnimi omejitvami .............................................................. 17 2.2 Samostojno delo s področja optimizacij z enim ciljem ................................................................ 19 2.2.1 Samostojno delo: Optimizacija obdelave z genetskim algoritmom........................................... 20 2.2.2 Samostojno delo: Optimizacija funkcije Rastrigin ........................................................................ 20 2.2.3 Samostojno delo: Optimizacija funkcije Himmelblau.................................................................. 21 2.2.4 Samostojno delo: Optimizacija funkcije Gomez and Levy ......................................................... 21 2.2.5 Samostojno delo: Optimizacija funkcije Rosenbrock z omejitvami .......................................... 22 3 Optimizacija z več cilji ............................................................................................ 23 3.1 Vaje s področja optimizacij z več cilji ............................................................................................. 26 3.1.1 Vaja: Večkriterijska optimizacija procesa odrezavanja ................................................................. 26 3.2 Samostojno delo s področja optimizacij z več cilji ....................................................................... 29 3.2.1 Samostojno delo: Optimizacija funkcij Binh and Korn............................................................... 29 3.2.2 Samostojno delo: Optimizacija funkcij Chakong and Haimes ................................................... 30 3.2.3 Samostojno delo: Večkriterijska optimizacija testnih funkcij ..................................................... 30 4 Algoritem rojev delcev ............................................................................................. 31 4.1 Matematična formulacija PSO .......................................................................................................... 32 4.1.1 Inicializacija začetnega roja ................................................................................................................ 34 4.1.2 Evalvacija ciljne funkcije .................................................................................................................... 35 4.1.3 Shranjevanje najboljših vrednosti ..................................................................................................... 36 4.1.4 Posodobitev hitrosti in položaja ....................................................................................................... 36 4.1.5 Ponavljanje algoritma PSO ................................................................................................................ 38 4.2 Vaje s področja algoritma PSO......................................................................................................... 39 4.2.1 Vaja: Inicializacija začetnega roja PSO ............................................................................................ 40 4.2.2 Vaja: Evalvacija ciljne funkcije v začetnem roju ........................................................................... 46 4.2.3 Vaja: Shranjevanje najboljših vrednosti v začetnem roju ............................................................ 47 4.2.4 Vaja: Ponavljanje algoritma PSO ..................................................................................................... 50 4.2.5 Vaja: Posodobitev hitrosti in položaja ............................................................................................ 51 4.2.6 Vaja: Shranjevanje najboljših vrednosti .......................................................................................... 53 4.2.7 Vaja: Stekanje algoritma ..................................................................................................................... 55 4.2.8 Vaja: Ciljna funkcija kot zunanja funkcija ...................................................................................... 57 ii KAZALO. 4.2.9 Vaja: Algoritem PSO kot zunanja funkcija .................................................................................... 59 4.2.10 Vaja: Uporabite funkcijo PSO_opt .................................................................................................. 61 4.3 Samostojno delo s področja algoritma PSO .................................................................................. 65 4.3.1 Samostojno delo: Vpliv parametrov na konvergenco .................................................................. 66 4.3.2 Samostojno delo: Inicializacija z znano začetno točko ................................................................ 67 4.3.3 Samostojno delo: Parametrična ustavitvena merila ...................................................................... 67 4.3.4 Samostojno delo: Stroga omejitev gibanja ...................................................................................... 67 4.3.5 Samostojno delo: Enakovrednostne in neenakovrednostne omejitve ...................................... 68 4.3.6 Samostojno delo: Primerjava z genetskim algoritmom................................................................ 68 5 Optimizacijske funkcije .......................................................................................... 71 5.1 Funkcija Sphere ................................................................................................................................... 71 5.2 Funkcija Rastrigin ................................................................................................................................ 72 5.3 Funkcija Himmelblau ......................................................................................................................... 73 5.4 Funkcija Gomez and Levy (modified) ............................................................................................ 74 5.5 Funkcija Rosenbrock z omejitvami ................................................................................................. 75 6 Primeri Pareto front ................................................................................................ 77 6.1 Pareto fronta Binh and Korn ............................................................................................................ 77 6.2 Pareto fronta Chakong and Haimes ................................................................................................ 78 6.3 Pareto fronta Kursawe ....................................................................................................................... 79 6.4 Pareto fronta Deb Bimodal ............................................................................................................... 80 6.5 Pareto fronta Kita ............................................................................................................................... 81 6.6 Pareto fronta DTLZ1 ......................................................................................................................... 83 6.7 Pareto fronta DTLZ7 ......................................................................................................................... 84 7 Sklep ....................................................................................................................... 87 Literatura ............................................................................................................................... 89 OPTIMIZACIJE V INŽENIRSTVU: REŠEVANJE PROBLEMOV Z METAHEVRISTIČNIMI METODAMI V OKOLJU MATLAB J. Gotlih, M. Ficko 1 Uvod V inženirstvu se skoraj vsak dan srečujemo z odločitvami, pri katerih je treba izbrati najboljšo možno rešitev med mnogimi alternativami. Naj bo to optimizacija stroškov, iskanje najprimernejših procesnih parametrov, izboljšanje kakovosti izdelka ali usklajevanje med hitrostjo in zanesljivostjo se za vsako od teh nalog skriva osnovni princip: kako nekaj narediti boljše. Optimizacija kot znanstvena in aplikativna disciplina nam omogoča, da take odločitve ne sprejemamo več zgolj na podlagi občutka ali preizkusov z metodo poskusov in napak, temveč sistematično, z uporabo matematičnih modelov in algoritmov. Namen teh skript je ponuditi uvod v področje optimizacije v inženirstvu na način, ki povezuje teoretično ozadje z uporabo v praksi. Obravnavajo temeljne pojme enokriterijske in večkriterijske optimizacije, posebnosti obravnave omejitev ter implementacijo metahevrističnih algoritmov, kot sta genetski algoritem (GA) in algoritem rojev delcev (PSO). Poudarek je na razumevanju, ne zgolj na uporabi orodij, kar pomeni, da bo bralec razumel tudi ozadje, zakaj in kako algoritem deluje, ne le kateri ukaz v izbranem programskem okolju uporabiti. V teh skriptih posebno pozornost namenjamo metahevrističnim algoritmom, saj so se izkazali kot zelo učinkoviti pri reševanju zahtevnih inženirskih optimizacijskih nalog. Za razliko od klasičnih metod, ki pogosto zahtevajo gladkost, konveksnost ali 2 OPTIMIZACIJE V INŽENIRSTVU. odvodljivost funkcij, metahevristike omogočajo iskanje rešitev tudi v nelinearnih, večdimenzionalnih in diskretnih prostorih. Zaradi svoje prilagodljivosti in robustnosti se uspešno uporabljajo na številnih področjih, kot so načrtovanje proizvodnje, optimizacija virov, vodenje procesov in načrtovanje poti oz. povsod tam, kjer so razmere kompleksne, omejitve številne, cilji pa med seboj v konfliktu. Skripta so razdeljena na več vsebinskih sklopov. Po uvodnem nagovoru se najprej posvetimo optimizacijam z enim ciljem oz. enokriterijskim optimizacijam, kjer spoznamo osnovne koncepte in matematične modele za optimizacijo brez omejitev in z njimi. Na tem temelju gradimo praktične vaje, kot so optimizacija izdelovalnih procesov, vključevanje škatlastih, enakovrednostnih in neenakovrednostnih omejitev, ter dopolnjujemo razumevanje z nalogami za samostojno delo. V nadaljevanju obravnavamo optimizacijo z več cilji oz. večkriterijsko optimizacijo in pojem Pareto optimalnosti, vključno z vajami in dodatnimi nalogami, ki od študentov zahtevajo razmislek o kompromisih med cilji. Posebno poglavje je posvečeno algoritmu rojev delcev, kjer postopoma razvijemo njegovo matematično formulacijo, implementacijo v MATLAB-u in vaje, ki vodijo od osnovne inicializacije do vizualizacije konvergence in primerjav med parametri. Na koncu je predstavljen nabor značilnih optimizacijskih funkcij, kot so Sphere, Rastrigin, Himmelblau in Rosenbrock, ter primeri Pareto front, ki služijo kot referenčni testni primeri za večkriterijsko optimizacijo. Pri vajah in nalogah ni bistveno, da študent najde absolutno pravilno rešitev, temveč da zna zasnovati optimizacijski problem, poiskati primerno metodo, ovrednotiti rezultat in se naučiti nekaj novega o delovanju algoritmov. Zato skripta spodbujajo aktivno delo skozi raziskovanje, primerjanje in vizualizacijo rezultatov. Vsi algoritmi so predstavljeni tako, da jih bralec lahko razume in samostojno implementira v okolju MATLAB, ki je bilo izbrano kot programska podlaga za vse primere v teh skriptih. Vsi prikazani primeri so bili razviti in testirani v okolju MATLAB R2024a. Za izvajanje skript sta potrebna naslednja dodatka (angl. toolbox oz. Add-In): − Optimization Toolbox, − Global Optimization Toolbox. 1 Uvod 3, Čeprav optimizacija na prvi pogled deluje kot matematično zahtevna tema, si ta skripta prizadevajo pokazati, da je mogoče ključne koncepte razumeti tudi brez naprednega matematičnega predznanja, s pomočjo analogij, vizualizacij in preprostih primerov. Bralec je vabljen, da k obravnavanim vsebinam pristopi z radovednostjo in odprtostjo. Če razumevanje na začetku še ni popolno, se s postopnim napredovanjem oblikuje jasnejša slika. In kar je najlepše, optimizacijo se da naučiti tako, da jo preprosto začnemo uporabljati. 4 OPTIMIZACIJE V INŽENIRSTVU. OPTIMIZACIJE V INŽENIRSTVU: REŠEVANJE PROBLEMOV Z METAHEVRISTIČNIMI METODAMI V OKOLJU MATLAB J. Gotlih, M. Ficko 2 Optimizacija z enim ciljem V inženirstvu se pogosto srečujemo s problemi, kjer je cilj izboljšati en sam kriterij, na primer minimizirati stroške, maksimirati učinkovitost ali zmanjšati porabo energije. Tovrstne probleme označujemo kot optimizacije z enim ciljem oz. enokriterijske optimizacijske probleme (angl. single-objective optimization). Neomejene optimizacije z enim ciljem Osnovni enokriterijski optimizacijski problem se lahko matematično zapiše kot: 𝐦𝐦𝐦𝐦𝐦𝐦 𝒇𝒇 𝒎𝒎 ( 𝒙𝒙 ) pri 𝒙𝒙 ∈ ℝ, (2.1) kjer je: − 𝑚𝑚 𝒙𝒙 ∈ ℝ: vektor spremenljivk. V inženirski praksi so to npr. parametri postopka. Velikost vektorja 𝒙𝒙 definira dimenzijo problema; − 𝑓𝑓(𝒙𝒙): ciljna funkcija (npr. strošek, napaka, čas, energija). Omejene optimizacije z enim ciljem V praksi se optimizacijski problemi pogosto pojavljajo z različnimi omejitvami, ki jih je treba upoštevati pri njihovi zasnovi. Pri mehanski obdelavi na primer največja dovoljena hitrost vretena omejuje možen čas obdelave, čeprav bi višja rezalna hitrost teoretično lahko vodila do njegovega skrajšanja. 6 OPTIMIZACIJE V INŽENIRSTVU. Matematično lahko omejeni enokriterijski optimizacijski problem zapišemo kot: min 𝑓𝑓(𝒙𝒙) pri 𝒙𝒙 ∈ 𝑆𝑆 , (2.2) kjer je f skalarna funkcija in S nabor omejitev. Omejitve so lahko definirane kot: 𝑆𝑆 𝑚𝑚 = { 𝒙𝒙 ∈ ℝ: 𝒙𝒙 ≤ 𝒙𝒙 ≤ 𝒙𝒙 ; ℎ(𝒙𝒙 ) = 0; 𝑔𝑔(𝒙𝒙) ≥ 0}, min max kjer so: − 𝑆𝑆: dopustna množica vseh vrednosti 𝒙𝒙, ki izpolnjujejo omejitve. Če rešitev ne ustreza omejitvam, ni dopustna; 𝒙𝒙min ≤ 𝒙𝒙 ≤ 𝒙𝒙max; (2.3) − 𝒙𝒙 , min 𝒙𝒙 : škatlaste omejitve prostora spremenljivk (angl. box constraints). max Določajo domeno iskanja oz. dopustno območje vrednosti posameznih spremenljivk in so običajno definirane kot neenačbene; ℎ (𝒙𝒙) = 0; (2.4) − ℎ(𝒙𝒙) = 0 : enačbene (enakovrednostne) omejitve. Stroge omejitve, ki jih mora rešitev natančno izpolnjevati; 𝑔𝑔 (𝒙𝒙) ≥ 0; (2.5) − 𝑔𝑔(𝒙𝒙) ≥ 0: neenačbene (neenakovrednostne) omejitve. Omejitve, ki jih rešitev ne sme kršiti, vendar imajo nekaj prostosti. 2.1 Vaje s področja optimizacij z enim ciljem V tem poglavju so predstavljene naloge, ki se osredotočajo na reševanje optimizacijskih problemov z enim ciljem (2.1). Vaje so zasnovane tako, da omogočajo razumevanje vpliva parametrov algoritmov in razvoja ustreznih modelov 2 Optimizacija z enim ciljem 7, za iskanje optimalnih rešitev na primerih, ki ponazarjajo realne tehnološke zahteve, kot so varna območja delovanja stroja in stabilnost sil med obdelavo. Poglavje poudarja pomen pravilnega modeliranja, uporabe ustreznih omejitev in interpretacije rezultatov optimizacije v inženirski praksi. 2.1.1 Vaja: Enodimenzionalne optimizacije z enim ciljem Cilj te vaje je najti optimalno vrednost hitrosti podajanja 𝑣𝑣 𝑓𝑓, ki minimizira obrabo orodja. Ker je hitrost podajanja edina neodvisna spremenljivka, pravimo, da je problem enodimenzionalen. Obraba orodja je v tem študijskem primeru modelirana s preprosto kvadratno funkcijo: 𝑓𝑓�𝑣𝑣 2, � = 𝑣𝑣 𝑓𝑓 𝑓𝑓 kjer je: − 𝑓𝑓�𝑣𝑣 𝑓𝑓 �: funkcija obrabe orodja v odvisnosti od podajalne hitrosti 𝑣𝑣 in je ciljna 𝑓𝑓 funkcija optimizacijskega problema. Za obrabo orodja v praksi velja: nižja je boljša; − 𝑣𝑣 : hitrost podajanja v mm/min in je spremenljivka optimizacijskega problema. 𝑓𝑓 Ciljna funkcija je konveksna kvadratna funkcija z minimumom pri 𝑥𝑥 = 0 . Vrednost minimuma ciljne funkcije pri 𝑥𝑥 = 0 pa je prav tako 𝑓𝑓�𝑣𝑣 𝑓𝑓� = 0.  V okolju MATLAB ustvarite nov skript z imenom PSO_1D.m.  V odprt skript prilepite spodnjo kodo.  Kodo zaženite s klikom na gumb Run ali s pritiskom tipke F5. %% Matlab vaja: Optimizacija hitrosti podajanja z algoritmom rojev delcev (PSO) %% Definicija problema % Število spremenljivk (dimenzija problema) steviloSpremenljivk = 1; % Definicija ciljne funkcije (obraba orodja kot kvadrat podajalne hitrosti) 8 OPTIMIZACIJE V INŽENIRSTVU. CiljnaFunkcija = @funkcija_obrabe; %% Zagon algoritma rojev delcev (PSO) [v_f, y] = particleswarm(CiljnaFunkcija, steviloSpremenljivk); %% Ciljna funkcija function y = funkcija_obrabe(v_f) % FUNKCIJA_OBRABE - model kvadratne odvisnosti obrabe orodja od hitrosti podajanja % Kvadratna funkcija obrabe y = v_f^2; end Zapisano kodo lahko razdelimo na tri logične dele, ki so v skriptu ločeni z oznako %%. Znak % označuje komentarje, ki se ne izvajajo in služijo za razlago kode, medtem ko %% označuje začetek novega odseka, ki ga lahko samostojno zaženemo. Takšna razdelitev olajša strukturiranje, preglednost in testiranje skripta. Prvi del običajno vsebuje definicijo problema, drugi del zajema definicijo ciljne funkcije in morebitnih omejitev, ki so lahko zapisane neposredno v skript, na njenem dnu ali v ločeni funkcijski datoteki. Tretji del predstavlja zagon optimizacijskega algoritma in prikaz rezultatov. V odseku definicije problema določa spremenljivka steviloSpremenljivk dimenzijo optimizacijskega problema. Ker je ciljna funkcija odvisna od ene same spremenljivke, hitrosti podajanja (v_f), je dimenzija problema enaka 1. CiljnaFunkcija je ročica (angl. function handle) do funkcije funkcija_obrabe, ki predstavlja ciljno funkcijo optimizacije. V odseku zagon algoritma funkcija particleswarm izvede optimizacijo z algoritmom rojev delcev (PSO) za dano ciljno funkcijo. Prvi argument funkcije particleswarm je ročica do ciljne funkcije funkcija_obrabe, drugi argument pa določa število optimizacijskih spremenljivk. Funkcija particleswarm vrne dva rezultata: v_f je optimalna vrednost hitrosti podajanja, ki minimizira obrabo orodja, y pa je pripadajoča minimalna vrednost ciljne funkcije (tj. najmanjša obraba). V odseku ciljna funkcija je definirana funkcija funkcija_obrabe, ki modelira obrabo orodja kot kvadratno odvisnost od hitrosti podajanja. 2 Optimizacija z enim ciljem 9, Po zagonu skripta se v delovnem prostoru (Workspace) pojavijo štiri spremenljivke (Slika 1). Spremenljivki CiljnaFunkcija in steviloSpremenljivk sta del definicije problema in se samo prepišeta v delovni prostor. Rezultat optimizacije je shranjen v spremenljivki v_f, katere vrednost je 4,9209e-06, kar je praktično enako vrednosti nič. Spremenljivka y vsebuje vrednost ciljne funkcije pri tem optimumu, v tem primeru 2,4215e-11, kar je kvadrat optimalne hitrosti in prav tako zelo blizu nič. Tak rezultat potrjuje pravilno delovanje algoritma, saj vemo, da je minimum kvadratne funkcije obrabe 𝑦𝑦 = 0 dosežen pri podajalni hitrosti 𝑣𝑣 𝑓𝑓 = 0. Slika 1: Izpis rezultatov optimizacije v delovnem prostoru (Workspace) Slika 2 prikazuje izpis v ukaznem oknu (Command Window), ki sporoča, da je bila optimizacija zaključena, ker se vrednost ciljne funkcije v zadnjih iteracijah ni več bistveno spreminjala. To pomeni, da je algoritem dosegel stabilno rešitev in ustavil postopek optimizacije na podlagi ustavitvenega kriterija FunctionTolerance. Tak zaključek pomeni, da je bila konvergenca dosežena pred porabo maksimalnega števila iteracij. Slika 2: Izpis rezultatov v ukaznem oknu (Command Window) 10 OPTIMIZACIJE V INŽENIRSTVU. 2.1.2 Vaja: Večdimenzionalne optimizacije z enim ciljem Poleg hitrosti podajanja pa na obrabo orodja vpliva še več dejavnikov, zato moramo tudi optimizacijski problem znati razširiti na več spremenljivk. V našem primeru optimizacije obrabe orodja lahko k hitrosti podajanja dodamo še rezalno hitrost, tako da obravnavamo problem z dvema spremenljivkama: − 𝑣𝑣 𝑓𝑓 : hitrost podajanja (mm/min), − 𝑣𝑣 𝑐𝑐 : rezalna hitrost (m/min). Zaradi preglednosti bomo tudi v tem primeru kot ciljno funkcijo uporabili preprosto kvadratno funkcijo. Če torej v model obrabe vključimo še rezalno hitrost, dobi ciljna funkcija obliko dvodimenzionalne kvadratne funkcije: 𝑓𝑓 2 2 ( 𝒙𝒙 ) = 𝑣𝑣 . + 𝑣𝑣 𝑓𝑓 𝑐𝑐 Minimum ciljne funkcije 𝑓𝑓(𝑥𝑥 1, 𝑥𝑥2) = 0 je pri 𝑥𝑥1 = 𝑣𝑣𝑓𝑓 = 0 in 𝑥𝑥2 = 𝑣𝑣𝑐𝑐 = 0. Prostor spremenljivk 𝒙𝒙 je v tem primeru dvodimenzionalni vektor, saj imamo pri optimizacijskem problemu dve neodvisni spremenljivki 𝑣𝑣 in 𝑓𝑓 𝑣𝑣 . Ciljni prostor je 𝑐𝑐 enodimenzionalen, saj imamo samo en cilj oz. kriterij tj. obraba orodja.  Ustvarite nov skript z imenom PSO_2D.m.  V odprt skript prilepite spodnjo kodo.  Kodo zaženite s klikom na gumb Run ali s pritiskom tipke F5. %% Matlab vaja: Optimizacija podajalne in rezalne hitrosti s PSO %% Definicija problema % Število spremenljivk (dimenzija problema) steviloSpremenljivk = 2; % Definicija ciljne funkcije (obraba orodja kot kvadrat voste) CiljnaFunkcija = @funkcija_obrabe; %% Zagon algoritma rojev delcev (PSO) [x_opt, fval] = particleswarm(CiljnaFunkcija, steviloSpremenljivk); %% Ciljna funkcija 2 Optimizacija z enim ciljem 11, function y = funkcija_obrabe(x) % Model kvadratne odvisnosti obrabe orodja od hitrosti podajanja in rezalne hitrosti y = x(1)^2+x(2)^2; end Razlika med prejšnjo in zdajšnjo vajo je v tem, da iz enodimenzionalnega problema preidemo v dvodimenzionalni optimizacijski problem s spremenljivkama x(1) in x(2), pri čemer se spremeni tudi ciljna funkcija, ki zdaj upošteva oba vpliva. Slika 3: Rezultati optimizacije podajalne in rezalne hitrosti s PSO Slika 3 prikazuje delovni prostor po zaključeni optimizaciji z algoritmom rojev delcev. Optimalna vrednost spremenljivk x_opt predstavlja hitrost podajanja in hitrost rezanja, ki skupaj minimizirata obrabo orodja. Vrednost ciljne funkcije fval pri teh parametrih je zelo blizu nič (1,2037e-11), kar potrjuje uspešno iskanje minimuma kvadratne funkcije. Da rezultat ni povsem enak nič, ampak le zelo blizu, je posledica postopnega približevanja optimumu (konvergence) ter ustavitvenega kriterija algoritma, ki določa, kdaj se iskanje zaključi. 2.1.3 Vaja: Optimizacija s škatlastimi omejitvami Pri realnih inženirskih optimizacijskih problemih spremenljivke pogosto ne smejo presegati določenih fizičnih ali tehnoloških mej. Tovrstne omejitve imenujemo škatlaste (angl. box constraints), saj omejujejo iskanje rešitve na pravokotni oz. škatlasti podprostor vektorja spremenljivk (2.3). 12 OPTIMIZACIJE V INŽENIRSTVU. Za dvodimenzionalni primer obdelave intervale omejitev določa proizvajalec orodja ali tehnološki postopek. V našem primeru izberemo: − 50 ≤ 𝑣𝑣 𝑓𝑓 ≤ 150 [mm min ⁄], − 100 ≤ 𝑣𝑣 𝑐𝑐 ≤ 300 [m min ⁄]. Spodnji meji (𝒙𝒙 ) za hitrost podajanja in rezanja preprečujeta neučinkovito ali min nemogočo obdelavo, ki bi jo povzročile premajhne vrednosti. Zgornji meji (𝒙𝒙 ) max pa lahko preprečujeta pregretje, lom ali druge poškodbe orodja, nestabilnosti obdelave, lahko pa sta tudi pogojeni z zmogljivostjo stroja. Zaradi vpeljave škatlastih omejitev prilagodimo ciljno funkcijo: 𝑓𝑓 2 2 ( 𝒙𝒙 ) = �𝑣𝑣 𝑓𝑓 − 100 � + ( 𝑣𝑣 𝑐𝑐 − 200). S to spremembo ciljne funkcije smo modelirali realno situacijo, v kateri optimum ni več v matematični ničli, temveč v tehnično priporočeni točki. Najmanjša obraba orodja bo dosežena pri hitrosti podajanja 𝑣𝑣 mm/min in rezalni hitrosti 𝑓𝑓 = 100𝑣𝑣𝑐𝑐 = 200 m/min, torej v notranjosti dovoljenega območja, ne na njegovih mejah.  Ustvarite nov skript z imenom GA_skatlaste_omejitve.m.  V odprt skript prilepite spodnjo kodo.  Kodo zaženite s klikom na gumb Run ali s pritiskom tipke F5. %% Matlab vaja: Optimizacija podajalne in rezalne hitrosti s škatlastimi omejitvami %% Definicija problema % Število spremenljivk (dimenzija problema) steviloSpremenljivk = 2; % škatlaste omejitve prostora spremenljivk lb = [50 150]; ub = [100 300]; % Definicija ciljne funkcije (obraba orodja kot kvadrat razlike) CiljnaFunkcija = @funkcija_obrabe; 2 Optimizacija z enim ciljem 13, % možnosti GA options = optimoptions(@ga, 'PlotFcn', {@gaplotbestf}, 'Display', 'iter'); %% Zagon genetskega algoritma (GA) [x_opt, fval] = ga(CiljnaFunkcija, steviloSpremenljivk, [], [], [], [], lb, ub, [], options); %% Ciljna funkcija function y = funkcija_obrabe(x) % FUNKCIJA_OBRABE - model kvadratne odvisnosti obrabe orodja od hitrosti podajanja in rezalne hitrosti y = (x(1)-100)^2+(x(2)-200)^2; end Problem je v tej vaji razširjen z uvedbo škatlastih omejitev, kar pomeni, da sta za vsako izmed dveh spremenljivk določeni spodnja in zgornja meja. Druga ključna sprememba pri tej vaji je uporaba drugega optimizacijskega algoritma. Namesto algoritma rojev delcev je uporabljen genetski algoritem, ki je posebej primeren za optimizacijske probleme z omejitvami. Dodatno so v strukturi options vključene možnosti za sprotno vizualizacijo poteka optimizacije in izpis rezultatov po posameznih iteracijah, kar omogoča boljši vpogled v konvergenco algoritma. Pomembno je poudariti, da kljub tej bistveni spremembi v načinu iskanja optimuma osnovna definicija optimizacijskega problema ostaja skoraj nespremenjena. Ciljna funkcija in število spremenljivk ostajata enaka, spremenijo se le argumenti funkcije ga, ki so prilagojeni posebnostim uporabe genetskega algoritma. Poleg rezultatov v delovnem prostoru se nam med izvajanjem algoritma izriše graf poteka konvergence (Slika 4). Graf za naš primer prikazuje hitro konvergenco genetskega algoritma, saj se vrednosti ciljne funkcije že po nekaj generacijah približajo ničli. Razlika med najboljšo in povprečno rešitvijo pa je majhna, kar kaže na stabilno in učinkovito delovanje algoritma. 14 OPTIMIZACIJE V INŽENIRSTVU. Slika 4: Potek konvergence genetskega algoritma 2.1.4 Vaja: Optimizacija z enakovrednostnimi omejitvami V obdelovalnem procesu je pogosto tehnološka zahteva, da rezalna sila ostane na določeni ciljni vrednosti, na primer 700 N. Takšna zahteva izhaja iz potrebe po stabilnosti procesa, omejevanju mehanskih obremenitev ter zagotavljanju ponovljive obrabe orodja. V optimizacijskem modelu to zahtevo upoštevamo kot enakovrednostno omejitev (2.4), kar pomeni, da mora biti izračunana rezalna sila enaka vnaprej določeni ciljni vrednosti. Zapis enakovrednostne omejitve: ℎ (𝒙𝒙) = 𝐹𝐹 𝑟𝑟𝑟𝑟𝑟𝑟(𝒙𝒙) − 700 = 0 . Če ℎ(𝒙𝒙) ≠ 0, je rešitev neveljavna. S tem optimizacijski algoritem prisilimo, da išče take parametre procesa, ki izpolnjujejo to tehnološko zahtevo. Za model rezalne sile je uporabljen poenostavljen linearni izraz, ki povezuje rezalno silo z obema vhodnima spremenljivkama (hitrost podajanja in rezalna hitrost): 𝐹𝐹 𝑟𝑟𝑟𝑟𝑟𝑟 = 600 + 0.5𝑣𝑣𝑓𝑓 + 0.3𝑣𝑣𝑐𝑐 .  Ustvarite nov skript z imenom GA_enakovrednostne_omejitve.m. 2 Optimizacija z enim ciljem 15,  V odprt skript prilepite spodnjo kodo.  Kodo zaženite s klikom na gumb Run ali s pritiskom tipke F5. %% Matlab vaja: Optimizacija podajalne in rezalne hitrosti z enakovrednostnimi omejitvami % Število spremenljivk (dimenzija problema) steviloSpremenljivk = 2; % škatlaste omejitve prostora spremenljivk lb = [50 150]; ub = [100 300]; % Definicija ciljne funkcije CiljnaFunkcija = @funkcija_obrabe; % Definicija omejitev EnakovrednostneOmejitve = @omejitve; % možnosti GA options = optimoptions(@ga, 'PlotFcn', {@gaplotbestf}, 'Display', 'iter'); %% Zagon genetskega algoritma (GA) [x_opt, fval] = ga(CiljnaFunkcija, steviloSpremenljivk, [], [], [], [], lb, ub, EnakovrednostneOmejitve, options); %% Ciljna funkcija function y = funkcija_obrabe(x) % model kvadratne odvisnosti obrabe orodja od hitrosti podajanja in rezalne hitrosti y = 0.1*((x(1)-100)^2+(x(2)-200)^2); end %% Enakovrednostne omejitve function [c, ceq] = omejitve(x) 16 OPTIMIZACIJE V INŽENIRSTVU. % Model rezalne sile F_rez = 600 + 0.5 * x(1) + 0.3 * x(2); % Enakovrednostna omejitev ceq = F_rez - 700; c = []; % brez neenakovrednostnih omejitev end V tej vaji je bil optimizacijski problem nadgrajen z uvedbo enakovrednostne omejitve, ki zahteva, da mora biti izračunana rezalna sila F_rez enaka 700 N. Rezalna sila je definirana kot funkcija hitrosti podajanja in rezalne hitrosti. Omejitvena funkcija je definirana ločeno in dodeljena spremenljivki EnakovrednostneOmejitve, kar poveča preglednost programske kode in omogoča formulacijo omejitev tudi v zunanji datoteki. Dodatno je pri ciljni funkciji uporabljena utež 0,1, ki služi skaliranju cilja, da so vrednosti obrabe orodja skladne s fizikalno pričakovanimi velikostmi in primerljive z drugimi kriteriji. Slika 5: Površina ciljne funkcije z označeno omejitvijo na rezalno silo in optimalno točko Slika 5 prikazuje kompromis med iskanjem optimuma in izpolnjevanjem tehnoloških omejitev. Na sliki je prikazana površina ciljne funkcije, ki predstavlja obrabo orodja v odvisnosti od podajalne hitrosti in rezalne hitrosti. Barvna lestvica ponazarja vrednost funkcije, pri čemer nižje vrednosti ustrezajo manjšim obrabam. Črna črta označuje območje, kjer je izpolnjena enakovrednostna omejitev, torej rezalna sila znaša natanko 700 N. Na tej krivulji je z rdečo piko označena optimizirana točka, ki 2 Optimizacija z enim ciljem 17, predstavlja kombinacijo hitrosti, pri kateri je obraba minimalna ob hkratnem upoštevanju omejitve na silo. 2.1.5 Vaja: Optimizacije z neenakovrednostnimi omejitvami Z neenakovrednostnimi omejitvami 𝑔𝑔(𝒙𝒙) želimo preprečiti, da bi se proces obdelave izvajal v območju, kjer se pojavljajo regenerativne vibracije. Te vibracije negativno vplivajo na kakovost obdelane površine, obrabo orodja in varnost obdelovalnega postopka, saj lahko povzročijo poškodbe sistema. Vibracijsko območje v prostoru procesnih parametrov (podajalna hitrost 𝑣𝑣 𝑓𝑓 in rezalna hitrost 𝑣𝑣 ) lahko približno opišemo s krogom s središčem v 𝑐𝑐 (𝑣𝑣𝑓𝑓0, 𝑣𝑣𝑐𝑐0) in polmerom 𝑟𝑟 ter omejitev zapišemo v obliki neenačbe (2.5): 𝑟𝑟 2 2 2 − �𝑣𝑣 𝑓𝑓 − 𝑣𝑣 𝑓𝑓0 � − ( 𝑣𝑣 𝑐𝑐 − 𝑣𝑣 𝑐𝑐0 ) ≤ 0. Če pogoj 𝑔𝑔(𝒙𝒙) ≤ 0 ni izpolnjen, to pomeni, da je rešitev znotraj območja vibracij, kjer je proces nestabilen. Takšne rešitve so iz tehnološkega vidika nesprejemljive, zato jih optimizacijski postopek zavrne. S to omejitvijo zagotovimo, da bodo dovoljene rešitve le tiste, ki ležijo zunaj vibracijskega območja.  Ustvarite nov skript z imenom GA_neenakovrednostne_omejitve.m.  V odprt skript prilepite spodnjo kodo.  Kodo zaženite s klikom na gumb Run ali s pritiskom tipke F5. %% Matlab vaja: Optimizacija podajalne in rezalne hitrosti z neenakovrednostnimi omejitvami % Število spremenljivk (dimenzija problema) steviloSpremenljivk = 2; % škatlaste omejitve prostora spremenljivk lb = [50 150]; ub = [100 300]; % Definicija ciljne funkcije (obraba orodja kot kvadrat razlike) CiljnaFunkcija = @funkcija_obrabe; 18 OPTIMIZACIJE V INŽENIRSTVU. % možnosti GA options = optimoptions(@ga, 'PlotFcn', {@gaplotbestf}, 'Display', 'iter'); %% Zagon genetskega algoritma (GA) [x_opt, fval] = ga(CiljnaFunkcija, steviloSpremenljivk, [], [], [], [], lb, ub, @omejitve, options); %% Ciljna funkcija function y = funkcija_obrabe(x) % model kvadratne odvisnosti obrabe orodja od hitrosti podajanja in rezalne hitrosti y = 0.1*(x(1)-100)^2+(x(2)-200)^2; end %% Nenakovrednostne omejitve function [c, ceq] = omejitve(x) % Središče vibracijskega območja vf0 = 95; vc0 = 195; % Polmer kroga vibracijskega območja r = 10; % Neenačbena omejitev c <= 0 pomeni, da smo ZUNAJ kroga (varno) krog = (x(1) - vf0)^2 + (x(2) - vc0)^2; c = r^2 - krog; % Ni enakovrednostnih omejitev ceq = []; end V tej različici kode je glavna sprememba uvedba neenakovrednostne omejitve c, ki predstavlja prepovedano območje v prostoru hitrosti. Optimizacijski algoritem, mora upoštevati varnostno mejo, saj mora rešitev ležati izven kroga s središčem v 2 Optimizacija z enim ciljem 19, točki (95, 195) in polmerom 10. To pomeni, da algoritem išče optimum, ki je izven tega območja. Slika 6 prikazuje kompromis med iskanjem optimalne kombinacije hitrosti in izogibanjem tehnološko neugodnim območjem. Svetlo sivo označeno območje na ciljni površini predstavlja prepovedano območje, v katerem bi lahko zaradi kombinacij hitrosti prišlo do neželenih vibracij. To območje je modelirano kot krog v prostoru hitrosti in ga optimizacijski algoritem obravnava kot neenakovrednostno omejitev, ki se ji je treba izogniti. Rdeča pika označuje optimizirano točko, ki leži izven vibracijskega območja in hkrati minimizira obrabo orodja. Slika 6: Optimizacija obrabe z uporabo neenakovrednostih omejitev za izogibanje vibracijskemu območju 2.2 Samostojno delo s področja optimizacij z enim ciljem V okviru tega poglavja so predstavljene samostojne naloge, katerih namen je poglabljanje razumevanja postopkov optimizacije z enim ciljem. Vsaka naloga vključuje implementacijo in uporabo izbranega optimizacijskega algoritma, kot sta genetski algoritem ali algoritem rojev delcev, za reševanje standardnih ali poenostavljenih inženirskih problemov. Obravnavani so tako realistični tehnični primeri (npr. optimizacija obdelovalnih hitrosti) kot tudi znane matematične testne funkcije, kot so Rastrigin, Himmelblau, Gomez and Levy ter Rosenbrock. Namen vaj ni le iskanje globalnega minimuma v podanem prostoru, temveč tudi vizualizacija rezultatov, primerjava uspešnosti različnih algoritmov ter razmislek o fizikalnem smislu dobljenih rešitev. Naloge spodbujajo razumevanje omejitev, občutljivosti na inicializacijo ter pomena dobro definirane ciljne funkcije in iskalnega prostora. 20 OPTIMIZACIJE V INŽENIRSTVU. 2.2.1 Samostojno delo: Optimizacija obdelave z genetskim algoritmom Preoblikujte obstoječo optimizacijsko kodo iz poglavja 2.1.2, ki uporablja algoritem rojev delcev (PSO), tako da bo namesto tega uporabljala genetski algoritem (GA). Namen naloge je poiskati kombinacijo podajalne in rezalne hitrosti, ki minimizira preprosto kvadratno ciljno funkcijo obrabe orodja: 𝑓𝑓 2 2 ( 𝒙𝒙 ) = 𝑣𝑣 + 𝑣𝑣 . 𝑓𝑓 𝑐𝑐 Namig: Če potrebujete pomoč glede uporabe funkcije ga(), si pomagajte z MATLAB dokumentacijo ali Help. Zahteve naloge:  Implementirajte ciljno funkcijo v obliki funkcije.  Nastavite meje iskanja za hitrosti 𝑣𝑣 𝑓𝑓 ∈ [50; 150] in 𝑣𝑣𝑐𝑐 ∈ [100; 300].  Uporabite funkcijo ga za iskanje minimuma funkcije v prostoru dveh spremenljivk 𝑣𝑣 in 𝑓𝑓𝑣𝑣 . 𝑐𝑐  Izpišite optimalno rešitev in pripadajočo vrednost ciljne funkcije.  Utemeljite, ali ima rešitev, pri kateri je 𝑣𝑣 𝑓𝑓 = 0 ali 𝑣𝑣 smisel v kontekstu 𝑐𝑐 = 0, obdelovalnih procesov. 2.2.2 Samostojno delo: Optimizacija funkcije Rastrigin V tej nalogi boste optimirali znano testno funkcijo Rastrigin z uporabo optimizacijskega algoritma rojev delcev (PSO). Cilj je poiskati globalni minimum funkcije v omejenem prostoru ter prikazati potek in rezultat optimizacije. Zahteve naloge:  Implementirajte Rastriginovo funkcijo (poglavje 5.2) v obliki funkcije.  Nastavite meje iskanja na [−5,12; 5,12] za vsako spremenljivko.  Uporabite funkcijo particleswarm za iskanje minimuma funkcije za primer z dvema spremenljivkama (𝑛𝑛 = 2).  Izpišite optimalno rešitev in pripadajočo vrednost funkcije.  (Dodatno): Prikažite 3D-graf funkcije z označeno rešitvijo in primerjajte delovanje z drugim algoritmom (npr. genetskim algoritmom). 2 Optimizacija z enim ciljem 21, 2.2.3 Samostojno delo: Optimizacija funkcije Himmelblau V tej nalogi boste optimirali znano testno funkcijo Himmelblau z uporabo optimizacijskega genetskega algoritma (GA). Cilj je poiskati enega izmed globalnih minimumov funkcije v omejenem prostoru ter prikazati potek in rezultat optimizacije. Zahteve naloge:  Implementirajte funkcijo Himmelblau (poglavje 5.3) v obliki funkcije.  Nastavite meje iskanja na [−5; 5] za obe spremenljivki.  Uporabite funkcijo ga za iskanje minimuma funkcije.  Izpišite optimalno rešitev in pripadajočo vrednost funkcije.  Večkrat ponovno zaženite optimizacijo. Kaj ugotovite?  (Dodatno): Prikažite 3D-graf funkcije z označeno rešitvijo in primerjajte delovanje z drugim algoritmom (npr. algoritem roja delcev). 2.2.4 Samostojno delo: Optimizacija funkcije Gomez and Levy V tej nalogi boste optimirali testno funkcijo Gomez and Levy z uporabo genetskega algoritma. Cilj je poiskati globalni minimum funkcije v omejenem prostoru ter prikazati potek in rezultat optimizacije. Zahteve naloge:  Implementirajte funkcijo Gomez and Levy (poglavje 5.4) v obliki funkcije.  Implementirajte neenačbno omejitev v obliki funkcije.  Nastavite meje iskanja na [−1; 0,75] za spremenljivko 𝒙𝒙 in [−1; 1] za 𝑦𝑦.  Uporabite funkcijo ga za iskanje minimuma funkcije.  Izpišite optimalno rešitev in pripadajočo vrednost ciljne funkcije.  (Dodatno): Prikažite 3D-graf funkcije z označeno rešitvijo in primerjajte delovanje z algoritmom roja delcev. Kaj ugotovite? 22 OPTIMIZACIJE V INŽENIRSTVU. 2.2.5 Samostojno delo: Optimizacija funkcije Rosenbrock z omejitvami V tej nalogi boste optimirali funkcijo Rosenbrock z omejitvami z uporabo genetskega algoritma. Naloga vključuje iskanje globalnega minimuma funkcije v omejenem prostoru in pod dvema nelinearnima omejitvama. Zahteve naloge:  Implementirajte funkcijo Rosenbrock (poglavje 5.5) v obliki funkcije.  Implementirajte obe neenačbni omejitvi v obliki funkcije.  Nastavite meje iskanja na [−1,5; 1,5] za 𝑥𝑥 in [−0,5; 2,5] za 𝑦𝑦.  Uporabite funkcijo ga za iskanje minimuma funkcije.  Izpišite optimalno rešitev in pripadajočo vrednost funkcije. Preverite, ali algoritem ob vsakem ponovnem zagonu zanesljivo najde minimum funkcije, in utemeljite, zakaj je tako.  (Dodatno): V začetno populacijo vključite posameznika, postavljenega blizu točke globalnega minimuma, in preverite vpliv dobre inicializacije na uspešnost in hitrost optimizacije. OPTIMIZACIJE V INŽENIRSTVU: REŠEVANJE PROBLEMOV Z METAHEVRISTIČNIMI METODAMI V OKOLJU MATLAB J. Gotlih, M. Ficko 3 Optimizacija z več cilji Pri reševanju realnih problemov je pogosto treba upoštevati ne le več spremenljivk, temveč tudi več ciljev, ki so med seboj pogosto v nasprotju. Optimizacija z več cilji omogoča iskanje rešitev, ki vzpostavljajo ustrezno ravnovesje med temi cilji. Namesto ene optimalne rešitve dobimo množico kompromisnih rešitev, med katerimi lahko izbiramo glede na prednostne usmeritve ali zahteve sistema. Optimizacija z več cilji ali večkriterijska optimizacija je v matematični obliki lahko zapisana kot: min[𝑓𝑓 1(𝒙𝒙), 𝑓𝑓 2(𝒙𝒙), … , 𝑓𝑓 𝑛𝑛(𝒙𝒙)] pri 𝒙𝒙 ∈ 𝑆𝑆, (3.1) kjer je 𝑛𝑛 > 1 in S nabor omejitev. 𝑆𝑆 𝑚𝑚 = { 𝒙𝒙 ∈ ℝ: 𝒙𝒙 ≤ 𝒙𝒙 ≤ 𝒙𝒙 ; ℎ(𝒙𝒙 ) = 0; 𝑔𝑔(𝒙𝒙) ≥ 0}. min max Ciljni prostor (angl. objective space) je prostor, v katerega preslikamo spremenljivke 𝒙𝒙 s ciljno funkcijo 𝒇𝒇(𝒙𝒙). Množica vseh možnih vrednosti ciljev, ki so dosegljive ob upoštevanju omejitev, se imenuje ciljni prostor ali dosegljiva množica in je označena z: 𝑪𝑪 𝑛𝑛 = { 𝒚𝒚 ∈ ℝ: 𝒚𝒚 = 𝒇𝒇(𝒙𝒙); 𝒙𝒙 ∈ 𝑆𝑆}. 24 OPTIMIZACIJE V INŽENIRSTVU. Koncept skalarne optimalnosti, značilen za enokriterijske optimizacijske probleme, ni neposredno prenosljiv v večkriterijske sisteme. Zato uvedemo pojem Pareto optimalnosti, ki temelji na primerjavi med rešitvami glede na vse ciljne funkcije hkrati. Naj bo ∗ ∗ 𝒙𝒙 ∈ 𝑆𝑆 rešitev večkriterijskega problema. Rečemo, da je 𝒙𝒙 (globalni) Pareto optimum, če ne obstaja nobena druga rešitev 𝒙𝒙 ∈ 𝑆𝑆, za katero velja: 𝑓𝑓 𝑖𝑖 (𝐱𝐱) ∗ ≤ 𝑓𝑓 𝑖𝑖 ( 𝒙𝒙) za vse 𝑖𝑖 ∈ {1, … , 𝑛𝑛} , in obstaja vsaj en 𝑖𝑖 s strogo neenakostjo. To pomeni, da ni nobene druge rešitve, ki bi bila boljša (ali enaka) v vseh ciljih in strogo boljša vsaj v enem cilju, kar opisuje naravo kompromisov med cilji. Definicije: Šibka optimalna rešitev Pareto ∗ 𝒙𝒙 ∈ 𝑆𝑆 je taka, da ne obstaja 𝒙𝒙 ∈ 𝑆𝑆, za katerega velja: 𝑓𝑓 ∗ za vse 𝑖𝑖 ( 𝒙𝒙 ) < 𝑓𝑓 𝑖𝑖 ( 𝒙𝒙 )𝑖𝑖 ∈ {1, … , 𝑛𝑛}. Stroga optimalna rešitev Pareto ∗ 𝒙𝒙 ∈ 𝑆𝑆 (ali kar optimalna rešitev Pareto) je taka, da ne obstaja 𝒙𝒙 ∈ 𝑆𝑆, za katerega velja: 𝑓𝑓 ∗ ∗ , in ( 𝒙𝒙 ) ≤ 𝑓𝑓 ( 𝒙𝒙 ) za vse 𝑖𝑖 ∈ {1, … , 𝑛𝑛 } 𝑓𝑓 ( 𝒙𝒙 ) < 𝑓𝑓 ( 𝒙𝒙) za vsaj en 𝑗𝑗. (3.2) 𝑖𝑖 𝑖𝑖 𝑗𝑗 𝑗𝑗 Lokalna optimalna točka Pareto je definirana podobno kot globalna, vendar z omejitvijo na okolico točke ∗ ∗ 𝒙𝒙 . Naj bo 𝐵𝐵 ( ∗ 𝒙𝒙 , 𝜀𝜀 ) krogla z radijem 𝜀𝜀 > 0 . Potem je 𝒙𝒙 lokalni Pareto optimum, če ne obstaja ∗ 𝒙𝒙 ∈ 𝑆𝑆 ∩ 𝐵𝐵 ( 𝒙𝒙, 𝜀𝜀), za katerega velja: 𝑓𝑓 𝑖𝑖 ( ∗ 𝒙𝒙 ) ≤ 𝑓𝑓 𝑖𝑖 ( 𝒙𝒙) za vse 𝑖𝑖 ∈ {1, … , 𝑛𝑛}, in ∗ 𝑓𝑓 𝑗𝑗 ( 𝒙𝒙 ) < 𝑓𝑓 𝑗𝑗 ( 𝒙𝒙) za vsaj en 𝑗𝑗. Pareto fronta: Pareto fronta, imenovana tudi Pareto krivulja ali Pareto ploskev (odvisno od števila ciljev), predstavlja množico vseh nedominiranih točk v ciljnem prostoru. To so točke 𝒚𝒚 = 𝒇𝒇(𝒙𝒙), kjer je 𝒙𝒙 Pareto optimalna rešitev. 3 Optimizacija z več cilji 25, Oblika Pareto fronte ponazarja kompromise med različnimi ciljnimi funkcijami. Slika 7 prikazuje primer Pareto krivulje za primer dvokriterijske optimizacije (večkriterijska optimizacija z dvema ciljema), kjer vse točke med (𝑓𝑓 2(𝒙𝒙�), 𝑓𝑓 1(𝒙𝒙�)) in �𝑓𝑓 2(𝒙𝒙�), 𝑓𝑓 1(𝒙𝒙�)� tvorijo Pareto fronto. Te točke so nedominirane oziroma nepodrejene, saj jih po definiciji Pareto optimalnosti ni mogoče izboljšati v enem cilju, ne da bi jih s tem poslabšali v drugem cilju (3.2). Slika 7: Primer Pareto krivulje Slika 8 prikazuje primer šibkega in strogega optimuma Pareto. Točki 𝑝𝑝 in 1 𝑝𝑝 sta 5 šibka optimuma Pareto, točke 𝑝𝑝 2, 𝑝𝑝3 in 𝑝𝑝4 pa so strogi optimumi Pareto. Slika 8: Primer šibkega in strogega optimuma Pareto 26 OPTIMIZACIJE V INŽENIRSTVU. 3.1 Vaje s področja optimizacij z več cilji To poglavje vključuje naloge, namenjene razumevanju optimizacije z več cilji, kjer je cilj iskanje kompromisnih rešitev med različnimi merili optimizacije. Vaje vodijo študenta skozi postopke generiranja Pareto front in analize učinkov posameznih parametrov algoritmov na porazdelitev rešitev. 3.1.1 Vaja: Večkriterijska optimizacija procesa odrezavanja Cilj vaje je izvesti večkriterijsko optimizacijo procesa odrezavanja, pri čemer upoštevamo dva med seboj izključujoča se cilja: minimizirati čas izdelave, saj krajši čas pomeni večjo produktivnost, in minimizirati strošek izdelave, ker nižji stroški povečujejo ekonomsko učinkovitost procesa (3.1). Cilja sta v konfliktu, saj krajši čas izdelave zahteva višje režime obdelave, kar vodi do višjih stroškov. Odločanje temelji na dveh procesnih parametrih: − 𝑥𝑥 1 = 𝑣𝑣𝑓𝑓, podajanje [mm/min.], − 𝑥𝑥 , hitrost rezanja [m/min.]. 2 = 𝑣𝑣 𝑐𝑐 Za reševanje problema uporabimo genetski algoritem za večkriterijsko optimizacijo gamultiobj, ki vrne množico Pareto optimalnih rešitev. Ciljni funkciji: Čas izdelave: 𝑓𝑓 1(𝒙𝒙) = (3.3) 1 𝑥𝑥1 ⋅ 𝑥𝑥2 Čas je obratno sorazmeren z volumnom odrezanega materiala na enoto časa. Strošek: 𝑓𝑓 10 2 2 ( 𝒙𝒙 ) = ⋅ 𝑥𝑥 (3.4) 2 𝑥𝑥 1 + 0,01 + 0,3 3 Optimizacija z več cilji 27, Strošek izdelave pada s hitrostjo podajanja (hitrejša izdelava) in narašča s hitrostjo rezanja (večja obraba orodja). Omejitve: Ponovno uporabimo škatlaste omejitve: − 50 ≤ 𝑣𝑣 𝑓𝑓 ≤ 150 [mm min. ⁄] , − 100 ≤ 𝑣𝑣 𝑐𝑐 ≤ 300 [m min. ⁄]. Izbrane meje definirajo omejitve tehnološkega procesa.  Ustvarite nov skript z imenom GA_veckriterijsko.m.  V odprt skript prilepite spodnjo kodo.  Kodo zaženite s klikom na gumb Run ali s pritiskom tipke F5. %% Optimizacija z več cilji % Število spremenljivk (dimenzija problema) steviloSpremenljivk = 2; % škatlaste omejitve prostora spremenljivk lb = [50 150]; ub = [100 300]; % Definicija ciljne funkcije (čas izdelave in stroški) CiljnaFunkcija = @cas_in_stroski; % možnosti GA options = optimoptions(@gamultiobj,'PlotFcn',{@gaplotpareto,@gaplotscorediversi ty}); % Zagon večkriterijskega genetskega algoritma (GA) [x,fval] = gamultiobj(CiljnaFunkcija,steviloSpremenljivk,[],[],[],[],lb,ub,[], options); %% Ciljna funkcija function y = cas_in_stroski(x) y(1) = 1/(x(1) * x(2)); % Čas izdelave 28 OPTIMIZACIJE V INŽENIRSTVU. y(2) = 10/(x(1) + 0.01) + 0.3 * x(2)^2; % Strošek izdelave end V tej nalogi je optimizacijski problem razširjen na večkriterijsko optimizacijo, kjer sta hkrati upoštevana dva cilja: minimizacija časa izdelave in minimizacija stroškov. To predstavlja bistveno spremembo v primerjavi s prejšnjimi primeri, kjer je bila ciljna funkcija ena (npr. obraba orodja). Ciljna funkcija cas_in_stroski zdaj vrača vektor dveh vrednosti, pri čemer prvi element predstavlja čas izdelave, drugi pa strošek, kar omogoča iskanje kompromisnih rešitev. Namesto funkcije ga, ki se uporablja za enokriterijsko optimizacijo, je zdaj uporabljen večkriterijski genetski algoritem gamultiobj, ki generira Pareto fronto optimalnih rešitev (3.2). V options so definirane dodane funkcije za vizualizacijo: gaplotpareto prikazuje razvoj Pareto fronte, gaplotscorediversity pa raznolikost populacije rešitev. Slika 9: Rezultati večkriterijske optimizacije 3 Optimizacija z več cilji 29, Tudi število spremenljivk in škatlaste omejitve ostajajo enaki kot v prejšnjih nalogah, kar omogoča neposredno primerjavo med enokriterijskim in večkriterijskim pristopom. Glavna sprememba je torej v ciljni funkciji in v uporabi ustreznega algoritma, ki je prilagojen iskanju več med seboj konkurenčnih ciljev. Slika 9 v zgornjem grafu prikazuje Pareto fronto oz. množico optimalnih rešitev. Osi predstavljata vrednosti dveh ciljev: čas izdelave (Objective 1) (3.3) in strošek izdelave (Objective 2) (3.4). Točka na levi zgoraj ima najmanjši čas, a najvišje stroške, medtem ko ima desna spodaj najnižje stroške, a daljši čas izdelave. Prikazana fronta ponazarja kompromis med obema ciljema. V spodnjem grafu z naslovom Score Histogram (Slika 9) je prikazana razpršenost vrednosti posameznih ciljev v populaciji rešitev. Vidimo, da je več posameznikov doseglo enake vrednosti za čas izdelave ( Objective 1), medtem ko so vrednosti za strošek izdelave (Objective 2) bolj razpršene. To pomeni, da je bila populacija bolj uspešna pri optimizaciji časa, medtem ko so stroški pokazali večjo raznolikost med rešitvami. 3.2 Samostojno delo s področja optimizacij z več cilji V tem poglavju samostojno oblikujete in rešujete večkriterijske optimizacijske naloge na podlagi danih primerov. Cilj je poglobiti razumevanje kompromisov med cilji ter razviti sposobnost interpretacije in predstavitve Pareto optimalnih rešitev. 3.2.1 Samostojno delo: Optimizacija funkcij Binh and Korn V tej nalogi boste izvedli večkriterijsko optimizacijo funkcij Binh and Korn (poglavje 6.1) z uporabo primernega algoritma. Gre za eno najpogosteje uporabljenih testnih funkcij v večkriterijski optimizaciji, saj vsebuje dve konfliktni ciljni funkciji in dve nelinearni omejitvi. Cilj je poiskati nabor rešitev na Pareto fronti znotraj omejenega prostora. Zahteve naloge:  Implementirajte obe ciljni funkciji in obe omejitvi.  Uporabite večkriterijski optimizacijski algoritem gamultiobj. 30 OPTIMIZACIJE V INŽENIRSTVU.  Prikažite Pareto fronto ter izpišite nabor optimalnih rešitev v prostoru spremenljivk.  (Dodatno): Rešite večkriterijski problem z združitvijo obeh ciljnih funkcij v eno samo ciljno funkcijo z uteženo vsoto in optimizacijo izvedite z uporabo genetskega algoritma ga. Izvedite optimizacijo za vsaj pet različnih kombinacij uteži in za vsak primer zabeležite optimalno rešitev v prostoru ciljev. Rezultate prikažite grafično v obliki aproksimirane Pareto fronte. 3.2.2 Samostojno delo: Optimizacija funkcij Chakong and Haimes V tej nalogi boste izvedli večkriterijsko optimizacijo funkcij Chakong and Haimes (poglavje 6.2), ki vključuje dve ciljni funkciji in dve nelinearni omejitvi. Naloga je zasnovana kot test za algoritme večkriterijske optimizacije, saj cilji in omejitve določajo zanimivo Pareto fronto. Zahteve naloge:  Implementirajte obe ciljni funkciji in obe omejitvi.  Uporabite večkriterijski optimizacijski algoritem paretosearch.  Prikažite Pareto fronto ter izpišite nabor optimalnih rešitev v prostoru spremenljivk.  (Dodatno): Uporabite še algoritem gamultiobj ter primerjajte Pareto fronto in čas izvedbe z rezultati algoritma paretosearch. 3.2.3 Samostojno delo: Večkriterijska optimizacija testnih funkcij V tej nalogi boste izvedli večkriterijsko optimizacijo funkcij Kursawe (poglavje 6.3), Deb Bimodal (poglavje 6.4), Kita (poglavje 6.5), DTLZ1 (poglavje 6.6), DTLZ7 (poglavje 6.7). Za vsako funkcijo upoštevajte pripadajoče omejitve. Zahteve naloge:  Implementirajte ciljne funkcije in omejitve.  Uporabite primeren večkriterijski optimizacijski algoritem.  Prikažite Pareto fronte ter izpišite nabore optimalnih rešitev v prostoru spremenljivk. OPTIMIZACIJE V INŽENIRSTVU: REŠEVANJE PROBLEMOV Z METAHEVRISTIČNIMI METODAMI V OKOLJU MATLAB J. Gotlih, M. Ficko 4 Algoritem rojev delcev Algoritem rojev delcev (PSO, angl. Particle Swarm Optimization) je metahevristični optimizacijski algoritem, ki temelji na skupinski inteligenci in sodelovalnem vedenju skupin živali, kot so jate ptic, jate rib ali roji žuželk. Vsak posameznik v takšni skupini, ki ga v algoritmu imenujemo delec, predstavlja eno od možnih rešitev problema. Delci se premikajo po prostoru rešitev, ocenjujejo kakovost svojih položajev in jih sproti prilagajajo na podlagi lastnih izkušenj ter izkušenj drugih. V naravi številne vrste uspešno rešujejo kompleksne naloge s pomočjo skupinske inteligence. Ptice v jatah med selitvijo usklajeno prilagajajo smer in hitrost leta, da zmanjšajo zračni upor in povečajo energetsko učinkovitost. Ribe z zaznavanjem gibanja sosedov skupaj manevrirajo, da se izognejo plenilcem ali najdejo območja z več hrane. Mravlje s feromonskimi sledmi najdejo najkrajše poti do hrane, čebele pa si lokacije bogatih virov hrane sporočajo s plesom. Takšni sistemi temeljijo na preprostih lokalnih vedenjskih vzorcih posameznikov, a kljub temu dosegajo učinkovito globalno vedenje skupine brez centralnega nadzora. Delovanje algoritma PSO posnema ta načela. Pri iskanju najboljše rešitve oz. pri premikanju po prostoru spremenljivk upošteva vsak delec tri osnovne vplive: vztrajnost, kognitivno komponento in socialno komponento. Vztrajnostna komponenta pomeni, da delec ohranja del svoje prejšnje hitrosti, podobno kot ptica 32 OPTIMIZACIJE V INŽENIRSTVU. ali riba ohranja smer gibanja. Kognitivna komponenta predstavlja zanašanje na lastne izkušnje, saj si delec zapomni najboljšo točko, ki jo je do zdaj obiskal. Socialna komponenta pa odraža vpliv skupine, saj se delec približuje tisti točki, ki jo je kot najboljšo zaznal katerikoli drug delec v roju. Preplet teh vplivov delcem omogoča usmerjeno iskanje optimalne rešitve, pri čemer se učenje posameznika dopolnjuje z učenjem skupine. Pri vseh populacijskih algoritmih pa je ključno tudi spoznanje, da posamezni člani populacije na začetku iskanja še niso seznanjeni s problemom. Roj sprva nima izkušenj z okolico in ne razpolaga z informacijami o tem, kje bi lahko iskali dobre rešitve. V primeru algoritma rojev delcev (PSO) to pomeni, da imajo delci sicer določen začetni položaj, vendar še nimajo znanja o kakovosti rešitev v prostoru možnih rešitev. Zato je pomembno, da se na začetku učinkovito razporedijo po iskalnem prostoru. To začetno razporeditev imenujemo začetni roj oziroma začetna populacija delcev, ki predstavlja izhodišče celotnega optimizacijskega postopka. Razpršitev začetnega roja imenujemo inicializacija. Ena možnost inicializacije je, da vsak delec iskanje začne na naključno določeni lokaciji. V prvi ponovitvi algoritma vsak delec na svojem položaju ovrednoti kakovost svoje lokacije oz. prilagojenost na ciljno funkcijo in si lokacijo zapomni kot trenutno najboljšo. In šele nato lahko začne posodabljati svojo hitrost in položaj na podlagi treh ključnih vplivov: vztrajnosti, ki ohranja del prejšnjega gibanja, kognitivne komponente, ki ga usmerja proti njegovi najboljši zaznani točki, in socialne komponente, ki ga privlači k najboljši znani točki v roju. V nadaljevanju bomo to vedenje opisali z matematičnimi izrazi, ki omogočajo numerično izvedbo algoritma PSO na poljubnih ciljih funkcijah, tudi takšnih s kompleksno večdimenzionalno površino in nelinearnimi omejitvami. 4.1 Matematična formulacija PSO Algoritem rojev delcev (PSO) je zasnovan na načelih skupinskega vedenja in temelji na izmenjavi informacij med posameznimi delci v roju. Vsak delec predstavlja kandidatno rešitev in se skozi iteracije premika po prostoru rešitev z namenom izboljšanja svoje prilagojenosti glede na ciljno funkcijo. Premiki delcev temeljijo na treh osnovnih vplivih: vztrajnosti, kognitivnem vplivu oz. lastnih izkušnjah in socialnem vplivu oz. izkušnjah drugih delcev v roju. 4 Algoritem rojev delcev 33, Matematično lahko vsak delec 𝑖𝑖 v trenutni iteraciji 𝑡𝑡 opišemo s tremi glavnimi količinami: − 𝒙𝒙𝑖𝑖(𝑡𝑡): položaj je trenutna lokacija delca v prostoru rešitev. − 𝒗𝒗𝑖𝑖(𝑡𝑡): hitrost je vektorska količina, ki določa smer in velikost premika delca. − 𝒑𝒑 : najboljša lastna pozicija je položaj, kjer je delec do sedaj našel najugodnejšo 𝑖𝑖 vrednost ciljne funkcije. Poleg lastnosti delca pa je pomembna še najboljša globalna pozicija 𝒈𝒈, ki je najboljša do sedaj najdena rešitev med vsemi delci. Celoten postopek optimizacije z algoritmom PSO se izvede iterativno. Koraki pri izvajanju algoritma PSO 1. Inicializacija: Vsak delec se naključno postavi v prostor rešitev in pridobi naključno začetno hitrost. 2. Evalvacija: Vsak delec oceni vrednost ciljne funkcije na svoji trenutni poziciji. 3. Shranjevanje najboljših vrednosti: Če je nova pozicija boljša od dosedanje najboljše, se ta shrani kot nova osebna najboljša. Če je boljša od globalne, postane nova globalna najboljša. 4. Posodobitev hitrosti in položaja: Na podlagi vztrajnosti, kognitivnega vpliva in socialnega vpliva se posodobita hitrost in položaj vsakega delca. 5. Ponavljanje: Koraki 2–4 se ponavljajo, dokler ni dosežen ustavitveni kriterij. Natančno zaporedje izvedbe posameznih korakov lahko nazorno opišemo s psevdokodo. Psevdokodo razdelimo na dva dela: psevdokodo za začetni roj PSO in psevdokodo ponavljanja PSO. Psevdokoda za začetni roj PSO: 1. naključna postavitev delcev v prostor rešitev 2. za vsak delec: 2.1. za vsako dimenzijo: 2.1.1. določi začetni položaj 2.1.2. določi začetno hitrost 34 OPTIMIZACIJE V INŽENIRSTVU. 2.2. ovrednoti ciljno funkcijo 2.3. shrani osebni optimum 2.4. če je rezultat boljši od globalnega optimuma: 2.4.1. posodobi globalni optimum Psevdokoda ponavljanja PSO: 3. dokler ni dosežen ustavitveni kriterij: 3.1. za vsak delec v roju: 3.1.1. posodobi hitrost 3.1.2. posodobi položaj 3.1.3. ovrednoti ciljno funkcijo 3.1.4. če je rezultat boljši od osebnega optimuma: 3.1.4.1. posodobi osebni optimum 3.1.5. če je rezultat boljši od globalnega optimuma: 3.1.5.1. posodobi globalni optimum 4.1.1 Inicializacija začetnega roja V prvem koraku algoritma PSO je treba določiti začetne vrednosti za vse delce v roju. Vsak delec ima: − (0) 𝒙𝒙: začetni položaj, 𝑖𝑖 − (0) 𝒗𝒗: začetno hitrost, 𝑖𝑖 − ( 0) 𝒑𝒑: začetni najboljši položaj. 𝑖𝑖 Inicializacija vključuje naslednje korake za vsak delec 𝑖𝑖 = 1,2, … , 𝑛𝑛, kjer je 𝑛𝑛 število delcev: 1. ( 0) Naključno določi začetni položaj 𝒙𝒙 znotraj dovoljene domene spremenljivk: 𝑖𝑖 𝒙𝒙(0) min max , 𝑖𝑖𝑗𝑗 ∼ 𝒰𝒰�𝒙𝒙 𝑗𝑗 , 𝒙𝒙 𝑗𝑗 � kjer 𝑗𝑗 = 1,2, … , 𝒟𝒟 označuje dimenzijo problema, 𝒰𝒰 je enakomerna porazdelitev in 𝒟𝒟 je število spremenljivk. 4 Algoritem rojev delcev 35, 2. (0) Naključno določi začetno hitrost 𝒗𝒗, npr. iz simetričnega območja: 𝑖𝑖 𝒗𝒗(0) max max , 𝑖𝑖𝑗𝑗 ∼ 𝒰𝒰�−𝒗𝒗 𝑗𝑗 , 𝒗𝒗 𝑗𝑗 � kjer je max max min 𝒗𝒗 pa določa začetno intenzivnost 𝑗𝑗 = 𝛼𝛼�𝒙𝒙 , parameter 𝑗𝑗 − 𝒙𝒙 𝑗𝑗 � 𝛼𝛼 ∈ [0,1] raziskovanja. 3. Določi začetno najboljšo pozicijo: 𝒑𝒑 (0) (0) = 𝒙𝒙. 𝑖𝑖 𝑖𝑖 Začetni najboljši položaj je v začetnem roju za vsak delec enak trenutnemu položaju. Opomba: Izbira začetnih hitrosti vpliva na konvergenco. Prevelike hitrosti povzročijo divergenco, premajhne pa prezgodnjo konvergenco. Namesto povsem naključne inicializacije se lahko uporabi tudi statistična disperzija (npr. latin hypercube), ki izboljša pokritost prostora. 4.1.2 Evalvacija ciljne funkcije V fazi evalvacije vsak delec izračuna vrednost ciljne funkcije na svojem trenutnem položaju. Ta vrednost predstavlja sposobnost delca, tj. merilo kakovosti rešitve, ki jo predstavlja njegov položaj v prostoru spremenljivk. Za funkcijo 𝑛𝑛 𝑓𝑓 𝑖𝑖 : ℝ → ℝ to pomeni, da za vsak delec 𝑖𝑖 izračunamo: 𝑓𝑓 𝑖𝑖 = 𝑓𝑓(𝒙𝒙 , 𝑖𝑖 ) kjer je 𝒙𝒙𝑖𝑖 trenutni položaj delca. Pri minimizacijskih problemih je nižja vrednost funkcije boljša. 36 OPTIMIZACIJE V INŽENIRSTVU. 4.1.3 Shranjevanje najboljših vrednosti Po evalvaciji vsak delec primerja trenutno sposobnost z najboljšo, ki jo je do zdaj že dosegel. Če je nova vrednost boljša, delec shrani trenutni položaj kot svoj novi osebni optimum: če 𝑓𝑓(𝒙𝒙𝑖𝑖) < 𝑓𝑓(𝒑𝒑𝑖𝑖), potem 𝒑𝒑𝑖𝑖 = 𝒙𝒙𝑖𝑖, hkrati pa se posodobi tudi osebna najboljša sposobnost: 𝑓𝑓 (𝒑𝒑 𝑖𝑖) = 𝑓𝑓(𝒙𝒙𝑖𝑖) . Nato se preveri, ali je katera od osebnih najboljših vrednosti boljša od globalne najboljše vrednosti v roju. Če je tako, se shrani nova globalna najboljša rešitev: če 𝑓𝑓(𝒑𝒑𝑖𝑖) < 𝑓𝑓(𝒈𝒈), potem 𝒈𝒈 = 𝒑𝒑𝑖𝑖, kjer je 𝒈𝒈 položaj najboljšega delca celotnega roja do zdaj. 4.1.4 Posodobitev hitrosti in položaja Spremembo položaja delca si lahko predstavljamo kot vektorsko vsoto treh hitrosti, ki vplivajo nanj. Slika 10 ponazarja te vplive v obliki usmerjenih puščic, ki skupaj določijo novo hitrost 𝒗𝒗𝑖𝑖(𝑡𝑡 + 1) in novi položaj 𝒙𝒙𝑖𝑖(𝑡𝑡 + 1) delca 𝑖𝑖. 𝒑𝒑 𝑖𝑖 (t) 𝒙𝒙 𝑡𝑡 𝒙𝒙 𝑖𝑖𝑖𝑖 𝑡𝑡 + 1 𝒗𝒗 𝑖𝑖 𝑡𝑡 + 1 𝒈𝒈 𝑡𝑡 Slika 10: Sprememba hitrosti in položaja delca kot vektorska vsota vztrajnostne, kognitivne in socialne komponente Nova hitrost delca 𝒗𝒗𝑖𝑖 (𝑡𝑡 + 1) se določi z vsoto treh komponent po enačbi: 𝒗𝒗𝑖𝑖(𝑡𝑡 + 1) = 𝑟𝑟 ∙ 𝜔𝜔 ∙ 𝒗𝒗𝑖𝑖(𝑡𝑡) + 𝑟𝑟 1 ∙ 𝑐𝑐1 ∙ �𝒑𝒑𝑖𝑖(𝑡𝑡) − 𝒙𝒙𝑖𝑖(𝑡𝑡)� + 𝑟𝑟2 ∙ 𝑐𝑐2 ∙ (4.1) ( �𝒈𝒈 𝑡𝑡 ) − 𝒙𝒙 𝑖𝑖 ( 𝑡𝑡 ) � , 4 Algoritem rojev delcev 37, kjer so: − 𝜔𝜔: koeficient vztrajnosti, ki določa težnjo delca, da ohrani trenutno smer gibanja; − 𝑐𝑐 1, 𝑐𝑐2: koeficienta pospeška, ki uravnavata vpliv osebne in kolektivne izkušnje; − 𝑟𝑟, 𝑟𝑟 1, 𝑟𝑟 2: naključna števila iz enakomerne porazdelitve v intervalu [0,1], ki prispevajo k stohastični naravi algoritma. Vsaka od komponent ima poseben pomen: − 𝒗𝒗𝑖𝑖,𝑣𝑣𝑟𝑟𝑣𝑣(𝑡𝑡 + 1) = 𝑟𝑟 ∙ 𝜔𝜔 ∙ 𝒗𝒗𝑖𝑖(𝑡𝑡): vztrajnostna komponenta spodbuja gladko gibanje in preprečuje prehitro spreminjanje smeri; − 𝒗𝒗𝑖𝑖,𝑘𝑘𝑘𝑘𝑘𝑘(𝑡𝑡 + 1) = 𝑟𝑟 1 ∙ 𝑐𝑐1 ∙ �𝒑𝒑𝑖𝑖(𝑡𝑡) − 𝒙𝒙𝑖𝑖(𝑡𝑡)�: kognitivna komponenta usmerja delca proti točki, kjer je sam zaznal najboljši rezultat; − 𝒗𝒗𝑖𝑖,𝑠𝑠𝑘𝑘𝑐𝑐 (𝑡𝑡 + 1) = 𝑟𝑟 2 ∙ 𝑐𝑐2 ∙ �𝒈𝒈(𝑡𝑡) − 𝒙𝒙𝒊𝒊(𝑡𝑡)�: socialna komponenta privlači delec h globalno najboljši točki, ki jo je do sedaj našel roj. Ko je hitrost določena, se položaj delca posodobi po enačbi: 𝒙𝒙𝑖𝑖(𝑡𝑡 + 1) = 𝒙𝒙𝑖𝑖(𝑡𝑡) + 𝒗𝒗𝑖𝑖(𝑡𝑡 + 1). (4.2) S tem delec naredi naslednji korak v prostoru rešitev. Opomba: Izbira parametrov 𝜔𝜔, 𝑐𝑐 in 𝑐𝑐 bistveno vpliva na delovanje algoritma. Visok 1 2 𝜔𝜔 spodbuja raziskovanje, nizek vodi v hitrejšo konvergenco. Razmerje med 𝑐𝑐 in 1𝑐𝑐2 določa, ali je posameznik bolj samozavesten ali bolj posluša skupino. V praksi se pogosto uporabljajo metode, kot je Clerc-Kennedyjeva korekcija, kjer se konstante izračunajo za zagotovitev stabilne konvergence. Določitev parametrov 𝜔𝜔, 𝑐𝑐 in po metodi Clerc-Kennedy vključuje določitev 1 𝑐𝑐 2 konstant Chi (𝛸𝛸), Phi (𝛷𝛷), Kapa (𝛫𝛫): 𝛸𝛸 = , 2 2𝛫𝛫 �2 − 𝛷𝛷 − √𝛷𝛷 − 4𝛷𝛷� 0 ≤ Κ ≤ 1 , 38 OPTIMIZACIJE V INŽENIRSTVU. 𝛷𝛷 = 𝛷𝛷1 + 𝛷𝛷2 ≥ 4 , pri čemer je: 𝜔𝜔 = 𝛸𝛸 , 𝑐𝑐1 = 𝛸𝛸𝛷𝛷1, 𝑐𝑐2 = 𝛸𝛸𝛷𝛷 . 2 4.1.5 Ponavljanje algoritma PSO Po inicializaciji, evalvaciji in shranjevanju najboljših vrednosti delcev v začetnem roju sledi ponavljajoči se del algoritma PSO, kjer delci postopoma izboljšujejo svoje rešitve. Vsaka ponovitev oz. iteracija algoritma vključuje naslednje korake: 1. Posodobitev hitrosti delca. 2. Posodobitev položaja delca z uporabo nove hitrosti. 3. Evalvacija ciljne funkcije na novi lokaciji. 4. Shranjevanje osebnih in globalnih optimumov, če so se izboljšali. Ti koraki se ponavljajo toliko časa, dokler ni dosežen ustavitveni kriterij. Kot ustavitveni kriterij se pogosto uporablja: − največje število iteracij, − konvergenca (zadostna nespremenljivost rezultata), − dovolj nizka vrednost ciljne funkcije, − ali kombinacija več kriterijev. Doseženo največje število iteracij Algoritem se ustavi, ko število opravljenih iteracij 𝑡𝑡 doseže vnaprej določeno mejo 𝑡𝑡𝑚𝑚𝑚𝑚𝑚𝑚 : 𝑡𝑡 ≥ 𝑡𝑡 , 𝑚𝑚𝑚𝑚𝑚𝑚 4 Algoritem rojev delcev 39, kjer je: − 𝑡𝑡: trenutna iteracija, − 𝑡𝑡 : 𝑚𝑚𝑚𝑚𝑚𝑚največje dovoljeno število iteracij. Konvergenca Če se vrednost ciljne funkcije ali najboljša rešitev v zaporednih iteracijah spremeni za manj kot vnaprej določeni prag 𝜀𝜀, štejemo, da je algoritem konvergiral: �𝑓𝑓�𝒙𝒙(t) (t−k) (t) (t−k) ali � − 𝑓𝑓�𝒙𝒙 �� < 𝜀𝜀 �𝒙𝒙 − 𝒙𝒙� < 𝜀𝜀, (4.3) kjer je: − (t) 𝒙𝒙: najboljša znana rešitev v iteraciji t, − 𝑓𝑓(⋅): ciljna funkcija, − 𝑘𝑘: št. korakov iteracije, − 𝜀𝜀: vnaprej določena toleranca (npr. −6 10). Dosežena dovolj nizka vrednost ciljne funkcije Postopek optimizacije se lahko ustavi tudi, ko vrednost ciljne funkcije doseže vnaprej določeno minimalno vrednost 𝑓𝑓 𝑚𝑚𝑖𝑖𝑛𝑛, ki velja za sprejemljivo rešitev: 𝑓𝑓�𝒙𝒙 (t)� ≤ 𝑓𝑓 . min 4.2 Vaje s področja algoritma PSO Vaje vodijo študenta skozi postopno sestavljanje algoritma rojev delcev (PSO), od osnovne inicializacije do modularne funkcijske oblike. Na začetku se ustvari začetni roj delcev z naključno določenimi položaji znotraj podanih mej, hitrostmi, ocenami ciljne funkcije in začetnimi osebnimi optimumi. Sledi ovrednotenje ciljne funkcije, določitev globalnega optimuma ter izvedba iterativnega postopka, kjer vsak delec posodablja svojo hitrost in položaj glede na osebne in globalne najboljše rešitve. Vizualizacija gibanja delcev in konvergence omogoča vpogled v učinkovitost optimizacije. Algoritem se nato modularizira, tako da se ciljna funkcija in algoritem 40 OPTIMIZACIJE V INŽENIRSTVU. PSO preneseta v zunanji funkciji, ki omogočata fleksibilno uporabo z različnimi vhodnimi parametri in funkcijami. V zaključni fazi se funkcija PSO prikliče iz ločenega skripta, kar omogoča enostavno prilagoditev različnim optimizacijskim problemom. Takšna zasnova sledi principu modularnosti, podobno kot so definirane funkcije v knjižnici za globalno optimizacijo v okolju MATLAB. 4.2.1 Vaja: Inicializacija začetnega roja PSO V tej vaji boste pripravili začetni roj delcev za algoritem PSO. Cilj je ustvariti 100 delcev, vsakega z naključnim položajem v prostoru spremenljivk, začetno hitrostjo nič, oceno kakovosti rešitve (ovrednotena ciljna funkcija) in shranjenim najboljšim osebnim rezultatom.  Ustvarite nov skript z imenom inicializacija_roja.m.  V odprt skript prilepite spodnjo kodo. %% Inicializacija roja delcev - vaja % V tej vaji boste dopolnili manjkajoče dele kode za inicializacijo PSO. clear; clc; close all; Ta del kode izbriše vse spremenljivke v delovnem prostoru (clear), zapre vsa odprta grafična okna (close all) in počisti ukazno okno (clc).  Dodajte naslednje vrstice. %% Parametri algoritma nvar = 2; % Število spremenljivk (dimenzija problema) vel_roj = 100; % Velikost roja (število delcev) S temi parametri določite, koliko neodvisnih spremenljivk bo imel vsak delec (nvar) in koliko delcev bo sodelovalo v algoritmu (vel_roj). 4 Algoritem rojev delcev 41,  Dodajte naslednje vrstice. %% Omejitve prostora spremenljivk lb = [-100 -100]; % Spodnje meje ub = [100 100]; % Zgornje meje Tukaj določite meje prostora iskanja. lb je spodnja meja za prvo in drugo spremenljivko delca in ub je zgornja meja za prvo in drugo spremenljivko delca. Vsak delec mora imeti začetni položaj znotraj teh mej.  Dodajte naslednje vrstice. %% Struktura posameznega delca delec.pol = []; delec.hitrost = []; delec.sposobnost = []; delec.naj_pol = []; delec.naj_sposobnost = []; Vsak delec ima svoj trenutni položaj v prostoru spremenljivk (delec.pol), hitrost, s katero se bo premikal (delec.hitrost), sposobnost oz. vrednost ciljne funkcije (delec.sposobnost), najboljši osebni položaj do sedaj (delec.naj_pol) ter sposobnost na tem najboljšem položaju (delec.naj_sposobnost). Spremenljivka delec je definirana kot struktura (angl. struct), ki se v MATLAB-u uporablja za organizirano in pregledno shranjevanje podatkov z različnimi tipi in imeni polj v eni spremenljivki.  Dodajte naslednje vrstice. %% Globalni optimum naj_delec_sposobnost = inf; naj_delec_pol = zeros(nvar,1); Na začetku optimizacije še nimamo dobrih rešitev, zato globalni optimum (naj_delec_sposobnost) nastavimo na zelo slabo vrednost (neskončno oziroma inf). Ta vrednost se bo med inicializacijo posodabljala, če kateri koli delec ponudi boljšo rešitev. Za spremenljivko naj_delec_pol, ki predstavlja lokacijo globalnega minimuma, vnaprej rezerviramo pomnilnik (angl. preallocate) z ustvarjanjem vektorja dimenzije nvar, pri čemer vse vrednosti inicializiramo z ničlo. 42 OPTIMIZACIJE V INŽENIRSTVU.  Dodajte naslednje vrstice. %% Inicializacija vseh delcev delec = repmat(delec, vel_roj, 1); Funkcija repmat naredi kopijo strukture delec po vrsticah vel_roj-krat. S tem ustvarimo celoten roj delcev, v katerem ima vsak delec enako strukturo, kot smo jo določili zgoraj.  Dodajte naslednje vrstice. for i = 1 : vel_roj for j = 1 : nvar % Dopolni: naključni začetni položaj znotraj meja % Dopolni: začetna hitrost = 0 end end V tem koraku smo dodali dve for zanki. V zunanji zanki poteka inicializacija vseh delcev v roju, pri čemer spremenljivka i predstavlja posamezni delec, zanka pa se izvede tolikokrat, kot je velikost roja (vel_roj). Če imamo na primer 100 delcev, bo ta zanka izvedena 100-krat, enkrat za vsak delec. Znotraj zunanje zanke se nahaja še notranja zanka, ki poteka po vseh dimenzijah, ki jih ima vsak delec (nvar). Spremenljivka j predstavlja indeks posamezne dimenzije prostora rešitev. Če ima naš optimizacijski problem dve spremenljivki, bomo vsak delec obravnavali v dveh dimenzijah, npr. koordinati 𝑥𝑥 in 𝑦𝑦, ki določata položaja delca. Znotraj teh dveh zank bomo v nadaljevanju za vsak delec in vsako njegovo spremenljivko določili začetne vrednosti za položaj in hitrost. Torej bomo za vsako kombinacijo i in j izvedeli inicializacijo posamezne komponente položaja (𝑥𝑥, 𝑦𝑦) in hitrosti (𝑣𝑣 𝑚𝑚, 𝑣𝑣𝑦𝑦). 4 Algoritem rojev delcev 43, Izziv za samostojno delo: Cilj je za vsak delec in vsako dimenzijo določiti naključni začetni položaj znotraj omejitev domene iskanja ter nastaviti začetno hitrost delca na nič. Na začetku algoritma delci še niso seznanjeni s problemom in nimajo izkušenj, na podlagi katerih bi lahko sprejeli odločitev, kam naj se premikajo, zato naj bo njihova začetna hitrost enaka 0.  Določite naključni začetni položaj delca znotraj omejitev.  Nastavite začetno hitrost vseh delcev na 0. Namig: Za naključno vrednost med spodnjo in zgornjo mejo uporabite funkcijo rand, ki generira naključno število med 0 in 1. Po inicializaciji delcev lahko preverimo, kako so se delci razporedili po prostoru spremenljivk. Zapišimo funkcijo, ki izriše začetne položaje vseh delcev v dveh dimenzijah. Vizualizacija nam pomaga oceniti, ali so delci ustrezno razpršeni po iskalnem prostoru ali pa so skoncentrirani le na določenem območju. Ustrezna začetna razpršenost je pomembna za uspešnost optimizacije, saj zagotavlja, da roj učinkovito preišče celoten prostor rešitev.  Ustvarite nov skript z imenom test_disperzije.m.  V odprt skript prilepite spodnjo kodo. function test_disperzije(delec) polozaji = reshape([delec.pol], [], length(delec))'; figure; scatter(polozaji(:,1), polozaji(:,2), 20, 'filled'); xlabel('x_1'); ylabel('x_2'); title('Začetna razpršenost roja'); axis equal; grid on; end Za klic funkcije znotraj skripta inicializacija_roja.m mora biti skript test_disperzije.m shranjen v isti mapi kot skript inicializacija_roja.m. 44 OPTIMIZACIJE V INŽENIRSTVU.  V skript inicializacija_roja.m na koncu dodajte naslednje vrstice. % Klic funkcije test_disperzije test_disperzije(delec);  Kodo zaženite s klikom na gumb Run ali s pritiskom tipke F5. Rešitev: %% Inicializacija roja delcev - vaja % V tej vaji boste dopolnili manjkajoče dele kode za inicializacijo PSO. clear; clc; close all; %% Parametri algoritma nvar = 2; % Število spremenljivk (dimenzija problema) vel_roj = 100; % Velikost roja (število delcev) %% Omejitve prostora spremenljivk lb = [-100 -100]; % Spodnje meje ub = [100 100]; % Zgornje meje %% Struktura posameznega delca delec.pol = []; delec.hitrost = []; delec.sposobnost = []; delec.naj_pol = []; delec.naj_sposobnost = []; %% Globalni optimum naj_delec_sposobnost = inf; naj_delec_pol = zeros(nvar,1); %% Inicializacija vseh delcev delec = repmat(delec, vel_roj, 1); for i = 1 : vel_roj for j = 1 : nvar 4 Algoritem rojev delcev 45, % Dopolni: naključni začetni položaj znotraj meja delec(i).pol(j) = lb(j) + rand * (ub(j) - lb(j)); % Dopolni: začetna hitrost = 0 delec(i).hitrost(j) = 0; end end test_disperzije(delec); Koda ustvari roj delcev za PSO tako, da vsakemu delcu določi naključni začetni položaj znotraj podanih mej in mu nastavi začetno hitrost na nič. Globalni optimum se na začetku postavi na neskončno vrednost, njegova lokacija pa se pripravi z vnaprej dodeljenim pomnilnikom. Funkcija test_disperzije.m preveri razpršenost delcev v prostoru rešitev. Slika 11 prikazuje začetno razpršenost roja delcev v dveh dimenzijah prostora rešitev (x₁ in x₂). Izris je rezultat funkcije test_disperzije.m, ki vizualno prikaže, ali so delci enakomerno porazdeljeni znotraj podanih meja iskanja. Vidimo, da so delci dobro razpršeni po celotnem območju, kar je ključno za učinkovito iskanje globalnega optimuma v zgodnjih fazah optimizacije. Slika 11: Začetna razpršenost roja delcev v omejenem iskalnem prostoru 46 OPTIMIZACIJE V INŽENIRSTVU. 4.2.2 Vaja: Evalvacija ciljne funkcije v začetnem roju V tej vaji boste za vsak delec izračunali vrednost ciljne funkcije. Uporabili boste dvodimenzionalno kvadratno funkcijo.  Odprite skript inicializacija_roja.m.  Pred koncem zunanje zanke zapišite ukaz za ovrednotenje dvodimenzionalne funkcije Sphere (poglavje 5.1).  Kodo zaženite s klikom na gumb Run ali s pritiskom tipke F5.  V delovnem prostoru (Workspace) poglejte, kako so se posodobile lastnosti delcev. Namig: Ukaz za ovrednotenje ciljne funkcije zapišite v vrstico pod komentarjem »Dopolni: ovrednotenje ciljne funkcije«, kot je razvidno v spodnjem odseku kode. for i = 1 : vel_roj for j = 1 : nvar % Dopolni: naključni začetni položaj znotraj meja delec(i).pol(j) = lb(j) + rand * (ub(j) - lb(j)); % Dopolni: začetna hitrost = 0 delec(i).hitrost(j) = 0; end % Dopolni: ovrednotenje ciljne funkcije end Rešitev: for i = 1 : vel_roj for j = 1 : nvar % Dopolni: naključni začetni položaj znotraj meja delec(i).pol(j) = lb(j) + rand * (ub(j) - lb(j)); % Dopolni: začetna hitrost = 0 delec(i).hitrost(j) = 0; end % Dopolni: ovrednotenje ciljne funkcije delec(i).sposobnost = sum(delec(i).pol.^2); end 4 Algoritem rojev delcev 47, V tem delu kode v polje sposobnost zapišemo vrednost ciljne funkcije (Sphere), ki oceni kakovost trenutne rešitve in se uporablja pri nadaljnjem iskanju globalnega optimuma. Pomembno: Pika pred kvadratom v zapisu pol.^2 pomeni elementno potenciranje, kar pomeni, da se vsaka komponenta vektorja posebej kvadrira. V našem primeru je pol dvodimenzionalni vektor z dvema elementoma, ki se najprej kvadrirata, nato pa se njuna kvadrata seštejeta z ukazom sum. Slika 12: Struktura delec po inicializaciji položaja, hitrosti in ovrednotenju ciljne funkcije Slika 12 prikazuje strukturo delec, ki vsebuje 100 delcev, vsak s petimi polji: pol, hitrost, sposobnost, naj_pol in naj_sposobnost. Polje pol vsebuje naključno določen položaj v 2D--prostoru, hitrost je inicializirana na [0, 0], kar pomeni, da delci na začetku mirujejo. V polju sposobnost je izračunana vrednost ciljne funkcije (funkcija Sphere) na osnovi trenutnega položaja. Polji naj_pol in naj_sposobnost sta prazni, saj se osebni optimumi še niso določali. Slika potrjuje, da je inicializacija roja pravilno izvedena. 4.2.3 Vaja: Shranjevanje najboljših vrednosti v začetnem roju V tej vaji boste za vsak delec shranili njegov trenutni položaj kot najboljši osebni položaj, shranili vrednost ciljne funkcije kot osebno najboljšo sposobnost in posodobili globalni optimum, če je trenutni delec boljši od vseh prejšnjih.  Shranite trenutni položaj delca kot njegov osebni najboljši položaj.  Shranite trenutno sposobnost kot njegovo osebno najboljšo sposobnost.  Shranite globalni optimum, če je trenutni delec boljši od globalnega optimuma. Namig: Ukaza za nastavitev osebnega optimuma (naj_pol in naj_sposobnost) zapišite v vrstico pod komentarjem »Dopolni: nastavitev osebnega optimuma«. Podobno zapišite pogoj za posodobitev globalnega optimuma pod komentarjem »Dopolni: 48 OPTIMIZACIJE V INŽENIRSTVU. posodobitev globalnega optimuma« znotraj if stavka, kot je prikazano v spodnjem odseku kode. Z if stavkom preverite, ali je trenutna sposobnost manjša od dosedanjega globalnega optimuma. end % Dopolni: evalvacija ciljne funkcije (Sphere function) delec(i).sposobnost = sum(delec(i).pol.^2); % Dopolni: nastavitev osebnega optimuma % Dopolni: posodobitev globalnega optimuma if delec(i).sposobnost < naj_delec_sposobnost end Rešitev: %% Inicializacija roja delcev - vaja % V tej vaji boste dopolnili manjkajoče dele kode za inicializacijo PSO. clear; clc; close all; %% Parametri algoritma nvar = 2; % Število spremenljivk (dimenzija problema) vel_roj = 100; % Velikost roja (število delcev) %% Omejitve prostora spremenljivk lb = [-100 -100]; % Spodnje meje ub = [100 100]; % Zgornje meje %% Struktura posameznega delca delec.pol = []; delec.hitrost = []; 4 Algoritem rojev delcev 49, delec.sposobnost = []; delec.naj_pol = []; delec.naj_sposobnost = []; %% Globalni optimum naj_delec_sposobnost = inf; naj_delec_pol = zeros(nvar,1); %% Inicializacija vseh delcev delec = repmat(delec, vel_roj, 1); for i = 1 : vel_roj for j = 1 : nvar % Dopolni: naključni začetni položaj znotraj meja delec(i).pol(j) = lb(j) + rand * (ub(j) - lb(j)); % Dopolni: začetna hitrost = 0 delec(i).hitrost(j) = 0; end % Dopolni: evalvacija ciljne funkcije (Sphere function) delec(i).sposobnost = sum(delec(i).pol.^2); % Dopolni: nastavitev osebnega optimuma delec(i).naj_pol = delec(i).pol; delec(i).naj_sposobnost = delec(i).sposobnost; % Dopolni: posodobitev globalnega optimuma if delec(i).sposobnost < naj_delec_sposobnost naj_delec_sposobnost = delec(i).sposobnost; naj_delec_pol = delec(i).pol; end end V delu kode, kjer nastavljamo osebni optimum, se trenutni položaj in sposobnost vsakega delca shranita kot njegov najboljši znani položaj in vrednost. V nadaljevanju se preveri, ali je trenutna sposobnost delca boljša od trenutnega globalnega optimuma. Če je, se globalni optimum ustrezno posodobi. Takšna inicializacija zagotavlja, da ima vsak delec svojo referenčno vrednost, vsem delcem v roju pa je znana najboljša začetna rešitev. 50 OPTIMIZACIJE V INŽENIRSTVU. Slika 13: Struktura delec po posodobitvi osebnih optimumov delcev Slika 13 prikazuje strukturo delec po posodobitvi osebnih optimumov. Vsak delec ima poleg trenutnega položaja in sposobnosti shranjeni tudi polji naj_pol in naj_sposobnost, ki predstavljata njegov osebni najboljši položaj in ustrezno vrednost. Slika 14 prikazuje delovni prostor po posodobitvi globalnih optimumov, kjer sta med spremenljivkami ovrednotena tudi globalni najboljši položaj (naj_delec_pol) in najnižja dosežena vrednost ciljne funkcije (naj_delec_sposobnost), ki predstavljata trenutno najboljšo rešitev celotnega roja. Slika 14: Delovni prostor z rezultati optimizacije 4.2.4 Vaja: Ponavljanje algoritma PSO V tej vaji boste implementirali ponavljajoči del algoritma PSO, ki je ključen za iskanje optimalne rešitve skozi več iteracij. Znotraj vsake iteracije bo vsak delec posodobil svojo hitrost, izračunal nov položaj, ocenil novo vrednost ciljne funkcije, posodobil svoj osebni optimum, če je našel boljšo rešitev, in posodobil globalni optimum, če je njegova rešitev najboljša v roju. 4 Algoritem rojev delcev 51,  Skript inicializacija_roja.m shranite z novim imenom npr. algoritem_PSO.m.  Dodajte novo spremenljivko iterations, ki določa število ponovitev algoritma.  Število ponovitev algoritma nastavite na 100. Rešitev: %% Parametri algoritma nvar = 2; % Število spremenljivk (dimenzija problema) iterations = 100; % Število ponovitev (iteracij) vel_roj = 100; % Velikost roja (število delcev) Ker PSO deluje iterativno, v vsaki ponovitvi delci posodobijo svoje položaje in hitrosti ter ovrednotijo ciljno funkcijo. S parametrom iterations določimo, kolikokrat naj se ta postopek izvede.  Na koncu kode dodajte zanko po številu iteracij.  Znotraj zanke po iteracijah dodajte zanko po vseh delcih v roju. Rešitev: %% Zanka po vseh spremembah položaja roja for iter = 1 : iterations % Zanka po vseh delcih: izračun položaja in ciljne funkcije vsakega delca for i = 1 : vel_roj end end Zanka po številu iteracij (iter) določa, kolikokrat se izvede posodobitev vseh delcev, notranja zanka (i) pa obravnava vsak delec posebej z namenom iskanja boljše rešitve. 4.2.5 Vaja: Posodobitev hitrosti in položaja Znotraj notranje zanke po delcih implementirajte posodobitev hitrosti in položaja (4.1) in (4.2). 52 OPTIMIZACIJE V INŽENIRSTVU.  V zanko vključite posodobitev hitrosti po formuli PSO.  Za vztrajnostni koeficient uporabite vrednost 𝜔𝜔 = 0,99.  Za kognitivni pospešek uporabite 𝑐𝑐 1 = 2.  Za socialni pospešek uporabite 𝑐𝑐 2 = 2.  V zanko vključite posodobitev položaja delca. Rešitev: %% Konstante PSO w = 0.99; % vztrajnostni faktor c1 = 2; % vpliv osebnega optimuma c2 = 2; % vpliv globalnega optimuma Te vrstice zapišemo v začetnem delu kode pri spremenljivkah algoritma. for iter = 1 : iterations % Zanka po vseh delcih: izračun položaja in ciljne funkcije vsakega delca for i = 1 : vel_roj for j = 1 : nvar delec(i).hitrost(j) = ( ... w*rand*delec(i).hitrost(j) ... % sprememba trenutne hitrosti + c1*rand*(delec(i).naj_pol(j) - delec(i).pol(j)) ... % sprememba hitrosti v smeri osebnega optimuma + c2*rand*(naj_delec_pol(j) - delec(i).pol(j))); % sprememba hitrosti v smeri globalnega optimuma delec(i).pol(j) = delec(i).pol(j) + delec(i).hitrost(j); % sprememba položaja delca end end end 4 Algoritem rojev delcev 53, V tem delu vsak delec posodobi obe komponenti svoje hitrosti glede na vztrajnost, osebni in globalni optimum, nato pa izračuna svoj nov položaj s premikom v smeri te hitrosti. 4.2.6 Vaja: Shranjevanje najboljših vrednosti V nadaljevanju boste ovrednotili ciljno funkcijo in po potrebi posodobili najboljše vrednosti delcev in roja.  V zanko vključite ovrednotenje ciljne funkcije.  Vključite posodobitev osebnega optimuma, če je novi rezultat boljši.  Vključite posodobitev globalnega optimuma, če je novi rezultat najboljši v roju. Rešitev: %% Zanka po vseh spremembah položaja roja for iter = 1 : iterations % Zanka po vseh delcih: izračun položaja in ciljne funkcije vsakega delca for i = 1 : vel_roj for j = 1 : nvar delec(i).hitrost(j) = ( ... w*rand*delec(i).hitrost(j) ... % sprememba trenutne hitrosti + c1*rand*(delec(i).naj_pol(j) - delec(i).pol(j)) ... % sprememba hitrosti v smeri osebnega optimuma + c2*rand*(naj_delec_pol(j) - delec(i).pol(j))); % sprememba hitrosti v smeri globalnega optimuma delec(i).pol(j) = delec(i).pol(j) + delec(i).hitrost(j); % sprememba položaja delca end % Ovrednotena ciljna funkcija za vsak delec delec(i).sposobnost = sum(delec(i).pol.^2); % Posodobitev najboljših lastnosti delca 54 OPTIMIZACIJE V INŽENIRSTVU. if delec(i).sposobnost < delec(i).naj_sposobnost % če je boljši kot je bil do zdaj delec(i).naj_sposobnost = delec(i).sposobnost; delec(i).naj_pol = delec(i).pol; end % Posodobitev lastnosti najboljšega delca if delec(i).sposobnost < naj_delec_sposobnost % če je najden boljši delec naj_delec_pol = delec(i).pol; naj_delec_sposobnost = delec(i).sposobnost; end end end V tem delu kode vsak delec po premiku ovrednoti ciljno funkcijo, nato primerja novo vrednost z dosedanjim najboljšim osebnim rezultatom ter ga po potrebi posodobi. Če pa je novi rezultat najboljši v celotnem roju, se posodobi še globalni optimum. Slika 15: Delovni prostor po optimizaciji funkcije Sphere z najdenim globalnim optimumom 4 Algoritem rojev delcev 55, S tem smo zagradili osnovno kodo za optimizacijo z algoritmom PSO. Algoritem uspešno najde minimum ciljne funkcije in ga zapiše v spremenljivko naj_delec_sposobnost. Pripadajoče vrednosti argumentov funkcije se zapišejo v spremenljivko naj_delec_pol (Slika 15). 4.2.7 Vaja: Stekanje algoritma V tem delu boste dodali spremenljivko za shranjevanje najboljših vrednosti skozi iteracije in jih prikazali v časovnem grafu, ki bo prikazoval stekanje oz. konvergenco algoritma (4.3).  V vsaki iteraciji shranite sposobnost najboljšega delca.  V vsaki iteracij shranite povprečno sposobnost roja.  V vsaki iteracij shranite sposobnost najslabšega delca.  Dodajte izris položajev delcev v vsaki iteraciji in izpis konvergence po koncu izvajanja. Rešitev: %% Prelokacija matrik za hitrejše procesiranje konvergenca = zeros(iterations,1); % konvergenca - najboljši delec roja kon_avg = zeros(iterations,1); % konvergenca - povprečje roja kon_max = zeros(iterations,1); % konvergenca - najslabši delec roja Xpol = zeros(vel_roj,1); % koordinata za izris delca Ypol = zeros(vel_roj,1); % koordinata za izris delca V tem delu vnaprej ustvarimo matrike za shranjevanje rezultatov med izvajanjem algoritma. Na ta način rezerviramo pomnilnik, kar pohitri izvajanje kode. Vektorji konvergenca, kon_avg in kon_max beležijo potek optimizacije, Xpol in Ypol pa shranjujeta položaje delcev za grafični prikaz. % Izris in konvergenca Xpol(i) = delec(i).pol(1); % koordinata 1. delca se shrani v spremenljivko za izris Ypol(i) = delec(i).pol(2); % koordinata 2. delca se shrani v spremenljivko za izris 56 OPTIMIZACIJE V INŽENIRSTVU. V tem delu shranimo trenutno pozicijo posameznega delca v vektorja Xpol in Ypol, ki ju uporabimo za sproten izris položajev delcev v prostoru rešitev. Tako lahko vizualno spremljamo gibanje roja skozi iteracije. %% Izris gibanja delcev clf; plot(Xpol, Ypol, '*'); axis([lb(1) ub(1) lb(2) ub(2)]); title(['Položaji delcev – iteracija ', num2str(iter)]); xlabel('x(1)'); ylabel('x(2)'); pause(0.01); V tem delu sproti izrisujemo gibanje delcev v prostoru rešitev. clf izbriše prejšnji izris, plot nariše trenutne položaje vseh delcev, axis določi vidno območje, title, xlabel in ylabel označijo graf, pause pa omogoči animacijo z rahlo zakasnitvijo med posameznimi iteracijami. % Shranjevanje sposobnosti delcev konvergenca(iter) = naj_delec_sposobnost; kon_avg(iter) = mean([delec.sposobnost]); kon_max(iter) = max([delec.sposobnost]); V tem delu beležimo rezultate optimizacije v vsaki iteraciji: konvergenca shrani trenutno najboljšo vrednost ciljne funkcije, kon_avg povprečno sposobnost vseh delcev, kon_max pa najslabšo (največjo) vrednost ciljne funkcije med delci. Ti podatki bodo uporabljeni za izris poteka konvergence algoritma. %% Izris konvergence figure('Name','Konvergenca PSO'); hold on plot(konvergenca, 'LineWidth', 1.5); plot(kon_avg, '--'); plot(kon_max, ':'); legend('Najboljši delec','Povprečje roja','Najslabši delec'); title('Potek konvergence PSO'); xlabel('Iteracija'); ylabel('Vrednost ciljne funkcije'); grid on; hold off 4 Algoritem rojev delcev 57, V tem delu izrišemo potek konvergence algoritma PSO: figure prikaže najboljšo, povprečno in najslabšo vrednost ciljne funkcije v vsaki iteraciji. Z ukazi legend, title, xlabel in ylabel dodamo legendo in ustrezne oznake, kar omogoča lažje razumevanje učinkovitosti in obnašanja algoritma skozi čas. Slika 16 na levi strani prikazuje položaje delcev po deseti iteraciji algoritma PSO. Vidno je, da se je večina delcev že zbrala v okolici minimuma, kar nakazuje uspešno usmerjanje gibanja delcev v iskalnem prostoru. Desna slika prikazuje potek konvergence vrednosti ciljne funkcije najboljšega delca v vsaki iteraciji skozi vse iteracije. Krivulja hitro pada v prvih nekaj korakih, kar pomeni hitro izboljševanje rešitve, nato pa se stabilizira okoli zelo nizke vrednosti. To potrjuje, da so se nekateri delci roja uspešno približali globalnemu minimumu. Slika 16: Razpršenost delcev po prostoru iskanja v deseti iteraciji (levo) in potek konvergence algoritma (desno) 4.2.8 Vaja: Ciljna funkcija kot zunanja funkcija V tej vaji boste ciljno funkcijo (funkcija Sphere) zapisali kot ločeno zunanjo funkcijo v novo datoteko. To omogoča boljšo preglednost programske kode in ponovno uporabo funkcije v različnih skriptih. Datoteko boste shranili v isto mapo kot glavni skript in vanjo vključili ustrezne ukaze.  Ustvarite novo datoteko z imenom sphere_function.m.  Shranite datoteko v isto mapo kot vaš glavni skript.  V datoteko sphere_function.m vnesite naslednjo funkcijo. 58 OPTIMIZACIJE V INŽENIRSTVU. function y = sphere_function(x) y = sum(x.^2); end Funkcija sphere_function definira ciljno funkcijo, ki sprejme vhodni vektor x in vrne vsoto kvadratov njegovih komponent y.  Na začetku algoritma pri spremenljivkah PSO dodajte spodnji vrstici. %% Ciljna funkcija fun = @sphere_function; S to vrstico določimo ciljno funkcijo, ki jo bo algoritem PSO minimiziral, pri čemer z uporabo ročice fun omogočimo, da je optimizacijski postopek univerzalen in prilagodljiv različnim funkcijam brez spreminjanja samega algoritma. @ ne pokliče funkcije sphere_function, ampak ustvari referenco nanjo tj. ročico, ki jo lahko pozneje uporabimo.  Spremenite del glavne kode, kjer kličete ciljno funkcijo v inicializaciji. x = delec(i).pol; % Dopolni: evalvacija ciljne funkcije (Sphere function) delec(i).sposobnost = fun(x); S tem shranimo trenutni položaj delca v spremenljivko x, ki jo nato uporabimo kot vhodni argument pri klicu ciljne funkcije. Tako se izognemo neposrednemu dostopu do strukture delec(i).pol znotraj funkcije in izboljšamo berljivost ter preglednost kode. Nato ovrednotimo ciljno funkcijo za trenutni položaj delca z uporabo zunanje funkcije sphere_function.  Na enak način spremenite del glavne kode, kjer kličete ciljno funkcijo v iteracijah. x = delec(i).pol; % Dopolni: evalvacija ciljne funkcije (Sphere function) delec(i).sposobnost = fun(x); 4 Algoritem rojev delcev 59, S tem smo ločili algoritem od definicije funkcije, kar omogoča enostavno zamenjavo ciljne funkcije brez poseganja v kodo algoritma. Rezultat vaje sta dve datoteki: algoritem_PSO.m in sphere_function.m. V datoteki algoritem_PSO.m je zapisana celotna koda algoritma PSO, vključno z definicijo problema in zagonom optimizacije. Datoteka sphere_function.m pa vsebuje ločeno definirano ciljno funkcijo. Takšna razdelitev omogoča boljšo preglednost in enostavno zamenjavo ciljne funkcije, saj v glavnem skriptu le spremenimo klic funkcije brez poseganja v strukturo algoritma. 4.2.9 Vaja: Algoritem PSO kot zunanja funkcija V tej vaji boste algoritem rojev delcev (PSO), ki ste ga do zdaj razvijali znotraj enega samega skripta, preoblikovali v zunanjo funkcijo. S tem boste dosegli modularnost kode, kar omogoča enostavno ponovno uporabo in testiranje algoritma z različnimi ciljnimi funkcijami, na enak način kot to omogočajo funkcije, ki so na voljo v MATLAB-ovih knjižnicah (npr. Global Optmization Toolbox). Cilja vaje sta preoblikovati kodo PSO v zunanjo funkcijo PSO_opt in doseči, da lahko funkcijo enostavno prikličemo z različnimi parametri in ciljnimi funkcijami.  Ustvarite novo datoteko z imenom PSO_opt.m.  Shranite datoteko v isto mapo kot vaš glavni skript.  V datoteko PSO_opt.m vnesite naslednjo funkcijo. function [x_opt, fval] = PSO_opt(fun, nvar, lb, ub, options) end Kjer sta x_opt, fval rezultata optimizacije, fun je ročica do ciljne funkcije, nvar je število spremenljivk, lb, ub sta vektorja spodnjih in zgornjih mej, options pa je struktura z nastavitvami algoritma (npr. število delcev, iteracij ipd.).  Znotraj funkcije implementirajte celoten algoritem PSO, kot ste ga razvili v prejšnjih vajah.  V algoritmu omogočite strukturo za vhodne spremenljivke (options), ki jih želite nadzorovati zunaj funkcije. 60 OPTIMIZACIJE V INŽENIRSTVU. Rešitev: % struktura options za vhodne spremenljivke iterations = options.iterations; vel_roj = options.vel_roj; w = options.w; c1 = options.c1; c2 = options.c2; V tem odseku iz strukture options preberemo parametre, ki določajo obnašanje algoritma PSO (število iteracij, velikost roja, parametre gibanja). Tako omogočimo, da so nastavitve algoritma ločene od implementacije in jih lahko enostavno spreminjamo iz zunanjega skripta.  Izbrišite naslednje vrstice. %% Ciljna funkcija fun = @sphere_function; nvar = 2; % Število spremenljivk (dimenzija problema) %% Omejitve prostora spremenljivk lb = [-100 -100]; % Spodnje meje ub = [100 100]; % Zgornje meje To so spremenljivke, ki jih zdaj pošiljamo iz zunanje skripte.  Na koncu funkcije pred zadnji end dodajte spodnje vrstice. %% Rezultat x_opt = naj_delec_pol; fval = naj_delec_sposobnost; V tem delu funkcije določimo izhodna rezultata: optimalni položaj delca x_opt in pripadajočo vrednost ciljne funkcije fval. Ta rezultat predstavlja najboljšo rešitev, ki jo je algoritem našel po vseh iteracijah. 4 Algoritem rojev delcev 61, 4.2.10 Vaja: Uporabite funkcijo PSO_opt Cilj naloge je uporabiti algoritem rojev delcev za iskanje globalnega minimuma kvadratne funkcije z dvema spremenljivkama in vizualizirati gibanje delcev ter konvergenco ciljne funkcije.  Ustvarite novo datoteko z imenom zagon_PSO_opt.m.  Zapišite kodo, ki pokliče funkcijo PSO_opt z naslednjimi parametri: − število spremenljivk: 2 − spodnja meja vrednosti spremenljivk: –100 − zgornja meja vrednosti spremenljivk: +100 − število iteracij: 100 − število delcev v roju: 50 − vztrajnostni koeficient ( 𝜔𝜔): 0,9 − kognitivni koeficient (𝑐𝑐 ): 2 1 − socialni koeficient (𝑐𝑐 ): 2 2 Rešitev: % Definicija ciljne funkcije fun = @sphere_function; % Parametri problema nvar = 2; lb = [-100 -100]; ub = [100 100]; % Nastavitve PSO options.iterations = 100; options.vel_roj = 50; options.w = 0.9; options.c1 = 2; options.c2 = 2; % Zagon optimizacije [x_opt, fval] = PSO_opt(fun, nvar, lb, ub, options); % Izpis fprintf('Optimalna rešitev: [%f, %f]\n', x_opt(1), x_opt(2)); fprintf('Vrednost ciljne funkcije: %f\n', fval); 62 OPTIMIZACIJE V INŽENIRSTVU. To je primer kode zagon_PSO_opt.m, ki definira in zažene optimizacijo z algoritmom PSO. Najprej se določi ciljna funkcija sphere_function prek funkcijske ročice fun. Nato se določijo parametri problema (število spremenljivk in meje iskanja) ter nastavitve parametrov PSO (število iteracij, velikost roja in parametri gibanja). Funkcija PSO_opt izvede optimizacijo in vrne optimalno rešitev x_opt ter pripadajočo vrednost ciljne funkcije fval. Na koncu se rezultat izpiše v ukazno okno. Prečiščena koda PSO_opt function [x_opt, fval] = PSO_opt(fun, nvar, lb, ub, options) %% Parametri algoritma iterations = options.iterations; vel_roj = options.vel_roj; %% Konstante PSO w = options.w; c1 = options.c1; c2 = options.c2; %% Prelokacija matrik za hitrejše procesiranje konvergenca = zeros(iterations,1); kon_avg = zeros(iterations,1); kon_max = zeros(iterations,1); Xpol = zeros(vel_roj,1); Ypol = zeros(vel_roj,1); %% Struktura posameznega delca delec.pol = []; delec.hitrost = []; delec.sposobnost = []; delec.naj_pol = []; delec.naj_sposobnost = []; %% Globalni optimum naj_delec_sposobnost = inf; naj_delec_pol = zeros(nvar,1); %% Inicializacija vseh delcev delec = repmat(delec, vel_roj, 1); for i = 1 : vel_roj 4 Algoritem rojev delcev 63, for j = 1 : nvar % Dopolni: naključni začetni položaj znotraj meja delec(i).pol(j) = lb(j) + rand * (ub(j) - lb(j)); % Dopolni: začetna hitrost = 0 delec(i).hitrost(j) = 0; end x = delec(i).pol; % Dopolni: evalvacija ciljne funkcije (Sphere function) delec(i).sposobnost = fun(x); % Dopolni: nastavitev osebnega optimuma delec(i).naj_pol = delec(i).pol; delec(i).naj_sposobnost = delec(i).sposobnost; % Dopolni: posodobitev globalnega optimuma if delec(i).sposobnost < naj_delec_sposobnost naj_delec_sposobnost = delec(i).sposobnost; naj_delec_pol = delec(i).pol; end end %% Zanka po vseh spremembah položaja roja for iter = 1 : iterations % Zanka po vseh delcih, izračun položaja in ciljne funkcije vsakega delca for i = 1 : vel_roj for j = 1 : nvar delec(i).hitrost(j) = ( ... w*rand*delec(i).hitrost(j) ... + c1*rand*(delec(i).naj_pol(j) - delec(i).pol(j)) ... + c2*rand*(naj_delec_pol(j) - delec(i).pol(j))); delec(i).pol(j) = delec(i).pol(j) + delec(i).hitrost(j); end 64 OPTIMIZACIJE V INŽENIRSTVU. x = delec(i).pol; % Dopolni: evalvacija ciljne funkcije (Sphere function) delec(i).sposobnost = fun(x); % Posodobitev najboljših lastnosti delca if delec(i).sposobnost < delec(i).naj_sposobnost delec(i).naj_sposobnost = delec(i).sposobnost; delec(i).naj_pol = delec(i).pol; end % Posodobitev lastnosti najboljšega delca if delec(i).sposobnost < naj_delec_sposobnost naj_delec_pol = delec(i).pol; naj_delec_sposobnost = delec(i).sposobnost; end % Izris in konvergenca Xpol(i) = delec(i).pol(1); Ypol(i) = delec(i).pol(2); end %% Vizualizacija gibanja delcev clf; plot(Xpol, Ypol, '*'); axis([lb(1) ub(1) lb(2) ub(2)]); title(['Položaji delcev – iteracija ', num2str(iter)]); xlabel('x(1)'); ylabel('x(2)'); pause(0.01); % Shranjevanje sposobnosti delcev konvergenca(iter) = naj_delec_sposobnost; kon_avg(iter) = mean([delec.sposobnost]); kon_max(iter) = max([delec.sposobnost]); end 4 Algoritem rojev delcev 65, %% Izris konvergence figure('Name','Konvergenca PSO'); hold on plot(konvergenca, 'LineWidth', 1.5); plot(kon_avg, '--'); plot(kon_max, ':'); legend('Najboljši delec','Povprečje roja','Najslabši delec'); title('Potek konvergence PSO'); xlabel('Iteracija'); ylabel('Vrednost ciljne funkcije'); grid on; hold off %% Rezultat x_opt = naj_delec_pol; fval = naj_delec_sposobnost; end Zapisana funkcija PSO_opt izvaja optimizacijo z algoritmom rojev delcev (PSO). Na začetku nastavi parametre, inicializira delce z naključnimi položaji in vrednoti njihovo sposobnost. Nato sledi glavna zanka, kjer se v vsaki iteraciji posodabljajo hitrosti, položaji, osebni in globalni optimum. Med izvajanjem se vizualizira gibanje delcev in beleži potek konvergence. Na koncu funkcija vrne najboljšo najdeno rešitev in pripadajočo vrednost ciljne funkcije. 4.3 Samostojno delo s področja algoritma PSO Poglavje obsega samostojne naloge, namenjene poglobljenemu razumevanju delovanja algoritma PSO v različnih kontekstih. Skozi naloge raziščete vpliv parametrov na konvergenco in razpršenost, pomen začetne porazdelitve delcev ter uvedbo naprednih ustavitvenih meril. S testnimi funkcijami, kot so Rastrigin, Himmelblau in Rosenbrock, analizirate vedenje algoritma ob prisotnosti več modalnosti in omejitev. Naloge vključujejo tudi omejevanje gibanja delcev znotraj iskalnega prostora ter razširitev algoritma za obravnavo enakovrednostnih in neenakovrednostnih omejitev. Zaključna primerjalna analiza med PSO in GA omogoča oceno učinkovitosti in stabilnosti obeh pristopov. Poglavje spodbuja eksperimentiranje, analitično primerjavo rezultatov in razvijanje občutka za prilagajanje algoritma glede na problem. 66 OPTIMIZACIJE V INŽENIRSTVU. 4.3.1 Samostojno delo: Vpliv parametrov na konvergenco V tej nalogi boste raziskali, kako različne nastavitve parametrov algoritma PSO vplivajo na njegovo vedenje, zlasti na hitrost konvergence, sposobnost raziskovanja prostora rešitev in razpršenost delcev. Cilji naloge so spoznati vpliv nastavitev parametrov PSO na vedenje algoritma, oceniti kompromis med raziskovanjem in konvergenco ter razumeti pomen uravnoteženega sodelovanja med delci v roju. Naloga omogoča poglobljeno razumevanje notranjih mehanizmov algoritma in podpira razvoj intuicije za njegovo učinkovito uporabo. Zahteve naloge:  Uporabite algoritem PSO za optimizacijo funkcije Rastrigin (poglavje 5.2).  Izvedite več zaporednih optimizacij, pri čemer uporabite naslednje kombinacije parametrov: − 𝜔𝜔 = 0,9; 𝑐𝑐 1 = 1,5; 𝑐𝑐2 = 1,5; − 𝜔𝜔 = 0,4; 𝑐𝑐 1 = 2,0; 𝑐𝑐2 = 2,0 ; − 𝜔𝜔 = 0,7; 𝑐𝑐 1 = 2,5; 𝑐𝑐2 = 0,5 ; − 𝜔𝜔 = 0,6; 𝑐𝑐 1 = 0,5; 𝑐𝑐2 = 2,5.  Določite parametre PSO po metodi Clerc-Kennedy za vrednosti spremenljivk: − 𝛫𝛫 = 1; − 𝛷𝛷 1 = 2,05; − 𝛷𝛷2 = 2,05.  Primerjajte značilnosti obnašanja algoritma pri različnih nastavitvah in določite: − konvergenco algoritma, − obseg raziskovanja prostora rešitev, − usklajenost gibanja delcev. Namig: Obseg raziskovanja prostora rešitev lahko ocenite numerično, tako da prikažite standardni odklon položajev vseh delcev v vsaki iteraciji, kar pokaže, kako razpršeni so delci po prostoru. Pri določitvi usklajenosti gibanja delcev pokažite, ali se delci gibljejo usklajeno proti istemu optimumu ali vsak zase, kar je znak slabe koordinacije. Uporabite npr. povprečno razdaljo do globalnega optimuma v vsaki iteraciji. 4 Algoritem rojev delcev 67, 4.3.2 Samostojno delo: Inicializacija z znano začetno točko V tem poglavju raziskujete, kako začetna pozicija posameznega delca vpliva na končni rezultat optimizacije. Cilj je razumeti, kako pomembna je začetna porazdelitev v prostoru rešitev, še posebej pri večmodalnih funkcijah, kot je funkcija Himmelblau Zahteve naloge:  Implementirajte optimizacijo funkcije Himmelblau (poglavje 5.3) z uporabo PSO.  V začetni roj vključite delec z natančno določeno začetno pozicijo. 4.3.3 Samostojno delo: Parametrična ustavitvena merila Pri tej nalogi se osredotočate na napredna ustavitvena merila, ki temeljijo na stabilnosti vrednosti ciljne funkcije. Cilj je razviti bolj robustne pogoje za zaustavitev, ki preprečijo nepotrebno dolge ali prehitre prekinitve optimizacije. Analizirajte trajanje optimizacije in njeno občutljivost na različna merila konvergence. Zahteve naloge:  Implementirajte optimizacijo funkcije Rastrigin (poglavje 5.2) z uporabo PSO.  Razvijte merilo za ustavitev algoritma, ki temelji na spremembi sposobnosti najboljšega delca. Uporabite naslednja parametra: − toleranca spremembe sposobnosti ε = 1e-6, − število zaporednih iteracij (npr. 5), v katerih je sprememba manjša od ε.  Vključite uporabo funkcij tic in toc za merjenje časa izvajanja algoritma. 4.3.4 Samostojno delo: Stroga omejitev gibanja V tem delu raziskujete, kakšen vpliv ima strogo omejevanje gibanja delcev na robove domene iskanja na učinkovitost algoritma. Cilj je razumeti, ali prisilno ohranjanje delcev znotraj dovoljene domene izboljša zanesljivost algoritma ali pa ga omejuje pri iskanju boljših rešitev. 68 OPTIMIZACIJE V INŽENIRSTVU. Zahteve naloge:  Implementirajte optimizacijo funkcije Rastrigin (poglavje 5.2) z uporabo PSO.  Prilagodite kodo PSO tako, da delci med iteracijami ne morejo zapustiti domene iskanja (npr. s prisilnim vračanjem na mejo).  Primerjajte delovanje s prejšnjo verzijo, kjer se je z domeno iskanja omejeval le začetni roj. 4.3.5 Samostojno delo: Enakovrednostne in neenakovrednostne omejitve Pri tej nalogi boste za PSO omogočili optimizacijo z enakovrednostnimi in neenakovrednostnimi omejitvami. Cilji so preveriti, kako PSO ravna z omejitvami, kdaj pride do težav (npr. nihanja ob robovih) in ali lahko algoritem najde optimum, kljub zapletenemu prostoru rešitev. Zahteve naloge:  Implementirajte optimizacijo funkcije Rosenbrock z omejitvami (poglavje 5.5).  Preverite, ali algoritem zanesljivo najde optimum. Opomba: Upoštevajte, da funkcija particleswarm, vgrajena v MATLAB, ne omogoča neposredne uporabe enakovrednostnih in neenakovrednostnih omejitev. 4.3.6 Samostojno delo: Primerjava z genetskim algoritmom Primerjate robustnost in učinkovitost PSO ter GA. Cilji so analizirati, kateri algoritem je zanesljivejši glede na kakovost rešitve, čas izvajanja in stabilnost rezultatov pri večkratnem zagonu na istem problemu z omejitvami. Analizirajte, kateri algoritem je bolj zanesljiv in stabilen pri reševanju problemov z omejitvami. Zahteve naloge:  Rešite problem iz poglavja 4.3.5 tudi z genetskim algoritmom (GA) in uporabite enake ciljne funkcije, omejitve in začetne pogoje. 4 Algoritem rojev delcev 69,  Primerjajte naslednje kazalce: − najdena vrednost ciljne funkcije, − čas izvajanja, − stabilnost rezultatov (izvedite vsaj 5 ponovitev). 70 OPTIMIZACIJE V INŽENIRSTVU. OPTIMIZACIJE V INŽENIRSTVU: REŠEVANJE PROBLEMOV Z METAHEVRISTIČNIMI METODAMI V OKOLJU MATLAB J. Gotlih, M. Ficko 5 Optimizacijske funkcije Poglavje predstavlja izbor klasičnih testnih funkcij, ki se pogosto uporabljajo za preverjanje učinkovitosti optimizacijskih algoritmov. Med njimi so enostavna kvadratna funkcija (Sphere), večmodalni funkciji Rastrigin in Himmelblau, kompleksna Gomez and Levy z neenačbeno omejitvijo ter funkcija Rosenbrock z značilno ukrivljeno dolino in dodatnimi omejitvami. Vsaka funkcija je opisana z izrazom, globalnimi minimumi, domeno iskanja in ključnimi značilnostmi, pomembnimi za analizo vedenja optimizacijskih metod. 5.1 Funkcija Sphere Kvadratna funkcija ali funkcija Sphere je ena najosnovnejših in najpogosteje uporabljenih testnih funkcij v optimizaciji. Predstavlja dobro izhodišče za testiranje osnovne pravilnosti, hitrosti konvergence in vpliva parametrov optimizacijskega algoritma. Ciljna funkcija: 𝑛𝑛 𝑓𝑓 2 ( 𝒙𝒙 ) = � 𝑥𝑥 𝑖𝑖 𝑖𝑖=1 72 OPTIMIZACIJE V INŽENIRSTVU. Globalni minimum: 𝑓𝑓 (𝑥𝑥1, … , 𝑥𝑥𝑛𝑛) = 0 pri 𝒙𝒙𝑛𝑛 = (0, 0, … ,0) Domena iskanja: 𝑥𝑥𝑖𝑖 ∈ [−∞; ∞] za 𝑖𝑖 = 1, 2, … , 𝑛𝑛 Izris: 5.2 Funkcija Rastrigin Funkcija Rastrigin je večmodalna, z mnogimi lokalnimi minimumi. Za 𝑛𝑛 = 2 ima zelo valovito obliko z minimumom v izhodišču. Uporablja se kot testna funkcija pri globalni optimizaciji, npr. z algoritmi rojev delcev, genetskimi algoritmi ipd. Ciljna funkcija: 𝑛𝑛 𝑓𝑓 2 ( 𝒙𝒙 ) = 𝐴𝐴𝑛𝑛 + � [ 𝑥𝑥 − 𝐴𝐴 cos(2𝜋𝜋𝑥𝑥 )], 𝑖𝑖 𝑖𝑖 𝑖𝑖=1 kjer je običajno 𝐴𝐴 = 10. 5 Optimizacijske funkcije 73, Globalni minimum: 𝑓𝑓 (𝑥𝑥1, … , 𝑥𝑥𝑛𝑛) = 0 pri 𝒙𝒙𝑛𝑛 = (0, 0, … ,0) Domena iskanja (za vsako spremenljivko): 𝑥𝑥𝑖𝑖 ∈ [−5,12; 5,12] za 𝑖𝑖 = 1, 2, … , 𝑛𝑛 Izris: 5.3 Funkcija Himmelblau Funkcija Himmelblau je večmodalna in ima več globalnih simetrično razporejenih minimumov. Uporablja se kot testna funkcija pri preverjanju učinkovitosti optimizacijskih algoritmov. Ciljna funkcija: 𝑓𝑓 ( 2 𝑥𝑥 , 𝑦𝑦 ) = ( 2 2 2 𝑥𝑥 + 𝑦𝑦 − 11) + ( 𝑥𝑥 + 𝑦𝑦 − 7) Globalni minimumi (v domeni iskanja): 𝑓𝑓 (3,0; 2,0) = 0 𝑓𝑓 (−2,805; 3,131) ≈ 0 74 OPTIMIZACIJE V INŽENIRSTVU. 𝑓𝑓(−3,779; −3,283) ≈ 0 𝑓𝑓 (3,584; −1,848) ≈ 0 Domena iskanja: 𝑥𝑥, 𝑦𝑦 ∈ [−5; 5] Izris: 5.4 Funkcija Gomez and Levy (modified) Funkcija Gomez and Levy je znana zaradi svoje kompleksne in valovite oblike z več lokalnimi minimumi. Uporablja se kot testni primer v optimizaciji z nelinearnimi omejitvami. Ciljna funkcija: 𝑓𝑓 2 1 4 6 2 4 ( 𝑥𝑥 , 𝑦𝑦 ) = 4 𝑥𝑥 − 2,1 𝑥𝑥 + 𝑥𝑥 + 𝑥𝑥𝑦𝑦 − 4 𝑦𝑦 + 4 𝑦𝑦 3 Neenačbena omejitev: − 2 sin(4 𝜋𝜋𝑥𝑥 ) + 2 sin(2𝜋𝜋𝑦𝑦) ≤ 1,5 5 Optimizacijske funkcije 75, Globalni minimum: 𝑓𝑓 (0,08984201; −0,7126564) = −1,031628453 Domena iskanja: 𝑥𝑥 ∈ [−1; 0,75] in 𝑦𝑦 ∈ [−1; 1] Izris: 5.5 Funkcija Rosenbrock z omejitvami Funkcija Rosenbrock je znana po svoji značilni ozki in ukrivljeni dolini, ki zaradi omejitev ne vodi do globalnega minimuma. Funkcija predstavlja izziv za številne optimizacijske algoritme, saj je zelo občutljiva na začetne pogoje in zahteva natančno usmerjeno iskanje. Uporablja se kot testna funkcija pri testiranju robustnosti in učinkovitosti optimizacijskih metod. Ciljna funkcija: 𝑓𝑓 2 2 2 ( 𝑥𝑥 , 𝑦𝑦 ) = (1 − 𝑥𝑥 ) + 100( 𝑦𝑦 − 𝑥𝑥 ) Neenačbene omejitve: ( 3 𝑥𝑥 − 1) − 𝑦𝑦 + 1 ≤ 0 in 𝑥𝑥 + 𝑦𝑦 − 2 ≤ 0 76 OPTIMIZACIJE V INŽENIRSTVU. Globalni minimum: 𝑓𝑓 (1,0; 1,0) = 0 Domena iskanja: 𝑥𝑥 ∈ [−1,5; 1,5] in 𝑦𝑦 ∈ [−0,5; 2,5] Izris: OPTIMIZACIJE V INŽENIRSTVU: REŠEVANJE PROBLEMOV Z METAHEVRISTIČNIMI METODAMI V OKOLJU MATLAB J. Gotlih, M. Ficko 6 Primeri Pareto front V nadaljevanju so predstavljeni primeri izgradnje nekaterih tipičnih Pareto front pod pogoji, kot jih predlagajo različni avtorji. Za vsak primer so zapisane funkcije in omejitve, ki so jih avtorji pri generaciji front uporabljali. 6.1 Pareto fronta Binh and Korn Problem Binh and Korn je znan testni primer v večkriterijski optimizaciji, ki vključuje dva cilja in dve omejitvi. Pareto fronta te funkcije je nekonveksna, delno omejena z neenačbnimi pogoji, kar omogoča preizkušanje zmožnosti algoritmov za iskanje raznolikih in optimalnih rešitev v prisotnosti omejitev. Primerna je za analizo porazdelitve rešitev na Pareto fronti ter oceno robustnosti in konvergence večkriterijskih optimizacijskih algoritmov. Ciljni funkciji: 𝑓𝑓 2 2 ( 𝑥𝑥 , 𝑦𝑦 ) = 4 𝑥𝑥 + 4 𝑦𝑦 1 𝑓𝑓 2 2 ( 𝑥𝑥 , 𝑦𝑦 ) = ( 𝑥𝑥 − 5) + ( 𝑦𝑦 − 5) 2 78 OPTIMIZACIJE V INŽENIRSTVU. Omejitve: 𝑔𝑔1 ( 2 𝑥𝑥 , 𝑦𝑦 ) = ( 2 𝑥𝑥 − 5) + 𝑦𝑦 ≤ 25 𝑔𝑔 2 2 ( 𝑥𝑥 , 𝑦𝑦 ) = ( 𝑥𝑥 − 8) + ( 𝑦𝑦 + 3) ≥ 7,7 2 Domena iskanja: 𝑥𝑥 ∈ [0; 5] in 𝑦𝑦 ∈ [0; 3] Izris: 6.2 Pareto fronta Chakong and Haimes Problem Chakong and Haimes je klasičen testni primer za večkriterijsko optimizacijo z dvema ciljnima funkcijama in dvema omejitvama. Pareto fronta pri tem problemu je zvezna, gladka in nekonveksna, kar omogoča preizkušanje sposobnosti algoritmov pri iskanju natančne in enakomerno porazdeljene fronte. Uporablja se za analizo uravnoteženosti med konflikti ciljev in preverjanje, kako dobro algoritem pokriva celotno Pareto fronto. 6 Primeri Pareto front 79, Ciljni funkciji: 𝑓𝑓 1 ( 2 𝑥𝑥 , 𝑦𝑦 ) = 2 + ( 2 𝑥𝑥 − 2) + ( 𝑦𝑦 − 1) 𝑓𝑓 2 ( 𝑥𝑥 , 𝑦𝑦 ) = 9 𝑥𝑥 − ( 𝑦𝑦 − 1) 2 Omejitve: 𝑔𝑔 2 2 ( 𝑥𝑥 , 𝑦𝑦 ) = 𝑥𝑥 + 𝑦𝑦 ≤ 225 1 𝑔𝑔2 (𝑥𝑥, 𝑦𝑦) = 𝑥𝑥 − 3𝑦𝑦 + 10 ≤ 0 Domena iskanja: 𝑥𝑥 ∈ [−20; 20] in 𝑦𝑦 ∈ [−20; 20] Izris: 6.3 Pareto fronta Kursawe Problem Kursawe je testni primer za večkriterijsko optimizacijo z dvema ciljema in tremi spremenljivkami v omejenem območju. Zaradi nelinearnih in oscilatornih členov generira dvakrat ločeno nekonveksno Pareto fronto, kar predstavlja izziv za algoritme pri iskanju raznolikih in porazdeljenih rešitev. Uporablja se za testiranje algoritmov na kompleksnih, razdrobljenih frontah. 80 OPTIMIZACIJE V INŽENIRSTVU. Ciljna funkcija: 𝑛𝑛−1 Minimize 2 2 𝑓𝑓 1 𝑖𝑖 ( 𝒙𝒙 ) = � �− 10exp �− 0,2 �𝑥𝑥 + 𝑥𝑥 �� 𝑖𝑖+1 𝑖𝑖=1 𝑛𝑛−1 Minimize 0,8 3 𝑓𝑓 ( 𝒙𝒙 ) = � (| 𝑥𝑥 | + 5sin( 𝑥𝑥 )) 2 𝑖𝑖 𝑖𝑖 𝑖𝑖=1 Domena iskanja: −5 ≤ 𝑥𝑥1, 𝑥𝑥2, 𝑥𝑥3 ≤ 5 Izris: 6.4 Pareto fronta Deb Bimodal Funkcija Deb Bimodal je testni primer za večkriterijsko optimizacijo, kjer avtor z bimodalno funkcijo 𝑔𝑔(𝑥𝑥2) ustvari zanimivo razmerje med ciljnima funkcijama. Prva funkcija je linearna, druga pa vključuje deljenje z 𝑥𝑥 in kompleksno nelinearno 1 funkcijo 𝑔𝑔 (𝑥𝑥 ). 2 6 Primeri Pareto front 81, Rezultat optimizacije je konveksna Pareto fronta, kar omogoča testiranje algoritmov pri obravnavi gladkih, a nelinearno povezanih ciljev. Posebej je primerna za analizo zmožnosti algoritma, da pravilno sledi konveksni strukturi fronte. Ciljna funkcija: Minimize 𝑓𝑓 1 (𝑥𝑥1, 𝑥𝑥2) = 𝑥𝑥1 Minimize 𝑔𝑔(𝑥𝑥2) 𝑓𝑓 2 ( 𝑥𝑥 1 , 𝑥𝑥 2 ) = 𝑥𝑥 1 𝑥𝑥 2 2 − 0,2 𝑥𝑥 − 0,6 𝑔𝑔 2 2 ( 𝑥𝑥 ) = 2,0 − exp �− � � � − 0,8exp �− � � � 2 0,004 0,4 Izris: 6.5 Pareto fronta Kita Problem Kita je znan večkriterijski testni primer, ki temelji na analogiji s termodinamičnimi sistemi. Zasnovan je tako, da vključuje dva cilja, ki sta med seboj v konfliktu in nelinearno povezana, medtem ko omejitve posnemajo značilnosti termodinamičnih enačb. 82 OPTIMIZACIJE V INŽENIRSTVU. Ciljni funkciji vključujeta kvadratni in linearni člen, omejitve pa definirajo nelinearno omejen prostor rešitev. Zaradi kompleksnih robnih pogojev je Pareto fronta delno odrezana in ukrivljena, kar omogoča testiranje algoritmov pri obravnavi več omejitev in različnih vrst povezav med cilji. Ciljna funkcija: Maximize 2 𝑓𝑓 ( 𝑥𝑥 , 𝑦𝑦 ) = −𝑥𝑥 + 𝑦𝑦 1 Maximize 𝑓𝑓 2(𝑥𝑥, 𝑦𝑦) = 𝑥𝑥 + 𝑦𝑦 + 1 2 1 Omejitve: 1 13 𝑥𝑥 + 𝑦𝑦 − ≤ 0 6 2 1 15 𝑥𝑥 + 𝑦𝑦 − ≤ 0 2 2 5 + 𝑦𝑦 − 30 ≤ 0 𝑥𝑥 Domena iskanja: 0 ≤ 𝑥𝑥 ≤ 7 0 ≤ 𝑦𝑦 ≤ 7 Izris: 6 Primeri Pareto front 83, 6.6 Pareto fronta DTLZ1 Funkcija DTLZ1 je del znane družine testnih problemov DTLZ, namenjenih preverjanju učinkovitosti večkriterijskih optimizacijskih algoritmov, zlasti genetskih algoritmov. Zasnovana je za poljubno število ciljev, pri čemer so ciljne funkcije simetrične in vključujejo skupno funkcijo 𝑔𝑔(𝑥𝑥𝑀𝑀). Vhodne spremenljivke so definirane v omejenem območju, rezultat optimizacije pa je večdimenzionalna linearna Pareto ploskev, kar omogoča jasno analizo porazdelitve in pokritosti rešitev. DTLZ1 se pogosto uporablja za testiranje konvergence in raznolikosti algoritmov v večdimenzionalnem prostoru ciljev. Ciljna funkcija: Minimize 𝑓𝑓 1 (𝒙𝒙) = 𝑥𝑥1𝑥𝑥2 … 𝑥𝑥𝑀𝑀−1�1 + 𝑔𝑔(𝑥𝑥𝑀𝑀)� 2 1 Minimize 𝑓𝑓 2(𝒙𝒙) = 𝑥𝑥1𝑥𝑥2 … (1 − 𝑥𝑥𝑀𝑀−1)�1 + 𝑔𝑔(𝑥𝑥𝑀𝑀)� 2 1 Minimize 𝑓𝑓 𝑀𝑀−1 (𝒙𝒙) = 𝑥𝑥1(1 − 𝑥𝑥2)�1 + 𝑔𝑔(𝑥𝑥𝑀𝑀 )� 2 1 Minimize 𝑓𝑓 𝑀𝑀 ( 1 𝒙𝒙 ) = (1 − 𝑥𝑥 1)�1 + 𝑔𝑔(𝑥𝑥𝑀𝑀 2 ) � 𝑔𝑔 2 ( 𝑥𝑥 ) = 100 � | 𝑥𝑥 | + � ( 𝑥𝑥 − 0,5) − cos�20𝜋𝜋(𝑥𝑥 − 0,5)�� 𝑀𝑀 𝑀𝑀 𝑖𝑖 𝑖𝑖 𝑚𝑚𝑖𝑖∈𝑚𝑚𝑀𝑀 Domena iskanja: 0 ≤ 𝑥𝑥𝑖𝑖 ≤ 1 za 𝑖𝑖 = 1,2, … , 𝑛𝑛 84 OPTIMIZACIJE V INŽENIRSTVU. Izris (za 𝒊𝒊 = 𝟑𝟑): 6.7 Pareto fronta DTLZ7 Funkcija DTLZ7 je še en kompleksnejši testni primer iz družine DTLZ, ki ga je predlagal avtor Deb za oceno zmogljivosti večkriterijskih optimizacijskih algoritmov. V tem primeru prve M−1 ciljne funkcije prevzamejo vrednosti posameznih spremenljivk, medtem ko je zadnja funkcija odvisna od vseh prejšnjih in funkcije h, ki vključuje sinusne oscilacije. Rezultat optimizacije za tridimenzionalni problem so štiri nepovezane Pareto ploskve, kar predstavlja velik izziv za algoritme, zlasti pri ohranjanju raznolikosti in pokritosti nepovezanih regij. DTLZ7 je zato primeren za preverjanje raziskovanja prostora rešitev in občutljivosti algoritma na oscilacije v ciljnih funkcijah. Ciljna funkcija: Minimize 𝑓𝑓 1(𝑥𝑥1) = 𝑥𝑥1 Minimize 𝑓𝑓 2(𝑥𝑥2) = 𝑥𝑥2 Minimize 𝑓𝑓 𝑀𝑀−1 (𝑥𝑥𝑀𝑀−1) = 𝑥𝑥𝑀𝑀−1 6 Primeri Pareto front 85, Minimize 𝑓𝑓 𝑀𝑀 (𝑥𝑥) = �1 + 𝑔𝑔(𝑥𝑥𝑀𝑀 )�ℎ(𝑓𝑓 1, 𝑓𝑓 2, … 𝑓𝑓 𝑀𝑀−1, 𝑔𝑔) 𝑔𝑔 (𝑥𝑥𝑀𝑀) = 1 + � 𝑥𝑥𝑖𝑖 | 9 𝑥𝑥𝑀𝑀 | 𝑚𝑚𝑖𝑖∈𝑚𝑚𝑀𝑀 𝑀𝑀−1 𝑓𝑓 ℎ 𝑖𝑖 ( 𝑓𝑓 , 𝑓𝑓 , … 𝑓𝑓 , 𝑔𝑔 ) = 𝑀𝑀 − � � 1 + sin(3𝜋𝜋𝑓𝑓 )�� 1 2 𝑀𝑀−1 𝑖𝑖 1 + 𝑔𝑔 � 𝑖𝑖=1 Domena iskanja: 0 ≤ 𝑥𝑥𝑖𝑖 ≤ 1 za 𝑖𝑖 = 1,2, … , 𝑛𝑛 Izris (za 𝒊𝒊 = 𝟑𝟑): 86 OPTIMIZACIJE V INŽENIRSTVU. OPTIMIZACIJE V INŽENIRSTVU: REŠEVANJE PROBLEMOV Z METAHEVRISTIČNIMI METODAMI V OKOLJU MATLAB J. Gotlih, M. Ficko 7 Sklep Optimizacija v inženirstvu ni zgolj matematično orodje, temveč pomembna miselna naravnanost, ki spodbuja sistematično iskanje izboljšav v realnih procesih, napravah in sistemih. V teh skriptih smo obravnavali temeljne pristope k enokriterijskim in večkriterijskim optimizacijskim problemom ter spoznali, kako lahko z uporabo metahevrističnih populacijskih algoritmov, kot sta genetski algoritem in algoritem rojev delcev, poiščemo rešitve tudi v zahtevnih, nelinearnih in večdimenzionalnih okoljih. Pri delu smo se poleg učenja ukazov in postopkov osredotočili predvsem na razvijanje razumevanja, kaj pomeni kakovostna rešitev v okviru danega problema. Pomemben poudarek je bil na tem, kako takšno rešitev prepoznati, kako ustrezno oblikovati optimizacijski problem glede na cilje in omejitve ter kako rezultate ustrezno interpretirati v širšem inženirskem kontekstu. S tem smo gradili ne le tehnične spretnosti, temveč tudi sposobnost analitičnega razmišljanja in presojanja, ki je ključna pri uporabi optimizacijskih pristopov v praksi. Cilj je bil razviti občutek za smiselno uporabo optimizacijskih metod ter razumevanje njihovih zmogljivosti in omejitev, pri čemer obvladovanje vseh tehničnih podrobnosti ni nujno. Z vključevanjem raznolikih nalog, od enostavnih funkcij z enim ciljem do kompleksnih večkriterijskih kompromisov, smo želeli prikazati širok 88 OPTIMIZACIJE V INŽENIRSTVU. spekter možnosti uporabe optimizacije. Hkrati smo spodbujali, da se vsak udeleženec poglobi v tiste vidike, ki so zanj najbolj pomembni, uporabni ali raziskovalno zanimivi. Iz preučitve vsebin in reševanja vaj izhajajo naslednja znanja in spretnosti: − formulirati enokriterijske in večkriterijske optimizacijske probleme z ustreznimi omejitvami in ciljnimi funkcijami, − izbrati in utemeljiti primeren optimizacijski algoritem (npr. GA, PSO) glede na naravo problema, − nastaviti meje in omejitve ter razumeti njihov vpliv na rešitev, − izvesti in interpretirati optimizacijo v okolju MATLAB, − vizualizirati rezultate in analizirati Pareto fronte pri večkriterijski optimizaciji, − oceniti konvergenco algoritma in analizirati občutljivost rezultatov na parametre algoritmov. Vabim te, da pridobljeno znanje s področja optimizacije uporabiš tudi pri drugih predmetih, projektnih nalogah ali raziskovalnem delu. Optimizacijski pristopi se pojavljajo v najrazličnejših kontekstih, od tehničnih in proizvodnih sistemov do ekonomskih, okoljskih ali organizacijskih odločitev. Povsod tam, kjer si prizadevamo za boljše, učinkovitejše ali bolj uravnotežene rešitve, ima optimizacija pomembno vlogo. Ključno pa je, da znamo prepoznati takšne situacije in znanje, ki smo ga pridobili, ustrezno uporabiti v praksi. OPTIMIZACIJE V INŽENIRSTVU: REŠEVANJE PROBLEMOV Z METAHEVRISTIČNIMI METODAMI V OKOLJU MATLAB J. Gotlih, M. Ficko Literatura Binh, T. T., & Korn, U. (1997). MOBES: A multiobjective evolution strategy for constrained optimization problems. Paper presented at the The third international conference on genetic algorithms (Mendel 97). Clerc, M., & Kennedy, J. (2002). The particle swarm-explosion, stability, and convergence in a multidimensional complex space. IEEE Transactions on Evolutionary Computation, 6(1), 58-73. Coello, C. A. C., Lamont, G. B., & Veldhuizen, D. A. V. (2007). Evolutionary algorithms for solving multi- objective problems: Springer. De Jong, K. A. (1975). An analysis of the behavior of a class of genetic adaptive systems: University of Michigan. Deb, K., Thiele, L., Laumanns, M., & Zitzler, E. (2005). Scalable Test Problems for Evolutionary Multiobjective Optimization. A. Abraham, L. Jain, & R. Goldberg (Eds.), Evolutionary Multiobjective Optimization: Theoretical Advances and Applications (pp. 105-145). London: Springer London. Eberhart, R., & Kennedy, J. (1995). A new optimizer using particle swarm theory. Paper presented at the MHS'95. Proceedings of the sixth international symposium on micro machine and human science. Goldberg, D. E. (1989). Genetic Algorithms in Search, Optimization, and Machine Learning: Addison- Wesley. Himmelblau, D. M. (1972). Applied Nonlinear Programming: McGraw-Hill. Holland, J. H. (1975). Adaptation in natural and artificial systems. University of Michigan Press google schola, 2, 29-41.4 Kennedy, J., & Eberhart, R. (1995). Particle swarm optimization. Paper presented at the Proceedings of ICNN'95-international conference on neural networks. Kennedy, J., & Eberhart, R. (1997). A discrete binary version of the particle swarm algorithm. Paper presented at the 1997 IEEE International conference on systems, man, and cybernetics. Computational cybernetics and simulation. Kursawe, F. (1990). A variant of evolution strategies for vector optimization. Paper presented at the International conference on parallel problem solving from nature. MathWorks Documentation. (2025). Global Optimization Toolbox User's Guide. https://www.mathworks.com/help/gads/ Mühlenbein, H., & Schlierkamp-Voosen, D. (1993). Predictive models for the breeder genetic algorithm I. Continuous parameter optimization. Evolutionary Computation, 1(1), 25-49. Rastrigin, L. A. (1974). Systems of extremal control. Nauka. Rosenbrock, H. (1960). An automatic method for finding the greatest or least value of a function. The computer journal, 3(3), 175-184. Simionescu, P. A. (2020). A collection of bivariate nonlinear optimisation test problems with graphical representations. International Journal of Mathematical Modelling and Numerical Optimisation, 10(4), 365-398. Tamaki, H., Kita, H., & Kobayashi, S. (1996). Multi-objective optimization by genetic algorithms: A review. Paper presented at the Proceedings of IEEE international conference on evolutionary computation. 90 OPTIMIZACIJE V INŽENIRSTVU. Vira, C., & Haimes, Y. Y. (1983). Multiobjective decision making: theory and methodology. Noth- Holland Series in System Science and Engineering, 62-109. Wikipedia contributors. (2025). Test functions for optimization. Wikipedia. https://en.wikipedia.org/wiki/Test_functions_for_optimization Yang, X.-S. (2010). Engineering Optimization: An Introduction with Metaheuristic Applications. Wiley. Yarpiz. (2025). Particle Swarm Optimizationvin MATLAB [Video]. YouTube. https://www.youtube.com/watch?v=sB1n9a9yxJk OPTIMIZACIJE V INŽENIRSTVU: DOI https://doi.org/ 10.18690/um.fs.11.2025 REŠEVANJE PROBLEMOV Z ISBN 978 - 961 - 299 - 079 - 4 METAHEVRISTIČNIMI METODAMI V OKOLJU MATLAB JANEZ GOTLIH, MIRKO FICKO Univerza v Mariboru, Fakulteta za strojništvo, Maribor, Slovenija janez.gotlih@um.si, mirko.ficko@um.si Skripta obravnavajo temeljne pristope optimizacije v inženirstvu s Ključne besede: metahevristične metode, poudarkom na uporabi metahevrističnih metod, kot sta genetski genetski algoritem (GA), algoritem (GA) in algoritem rojev delcev (PSO). Namenjena so algoritem rojev delcev študentom in inženirjem, ki želijo razumeti tako teoretično ozadje (PSO), eno- in večkriterijska kot praktično implementacijo optimizacijskih algoritmov v okolju optimizacija, MATLAB, MATLAB. Vključujejo poglavja o enokriterijskih in večkriterijskih inženirske aplikacije optimizacijskih problemih, obravnavajo omejitve, različne ciljne funkcije ter vizualizacijo rezultatov. Vsako poglavje vsebuje strukturirane vaje in naloge za samostojno delo, ki spodbujajo razumevanje delovanja algoritmov, oblikovanje optimizacijskih modelov in interpretacijo rešitev. Poseben poudarek je na razlagi parametrov algoritmov, primerjavi konvergence ter vplivu nastavitev na vedenje optimizacije. Skripta se zaključijo s pregledom značilnih testnih funkcij in primeri Pareto front za večkriterijsko optimizacijo. Zasnovana so tako, da tudi uporabniki brez poglobljenega matematičnega znanja lahko postopoma razvijejo intuicijo za uporabo optimizacijskih pristopov v realnih inženirskih problemih. DOI OPTIMIZATION IN ENGINEERING: https://doi.org/ 10.18690/um.fs.11.2025 ISBN OLVING ROBLEMS S P 978-961-299-079-4 WITH METAHEURISTIC METHODS IN MATLAB JANEZ GOTLIH, MIRKO FICKO University of Maribor, Faculty of Mechanical Engineering, Maribor, Slovenia janez.gotlih@um.si, mirko.ficko@um.si Keywords: The book covers basic optimization approaches in engineering, metaheuristic methods, focusing on the use of metaheuristic methods such as genetic genetic algorithm (GA), particle swarm optimization algorithms (GA) and particle swarm optimization (PSO). They are (PSO) algorithm, intended for students and engineers who want to understand both single- and multi-objective optimization, the theoretical background and the practical implementation of MATLAB, engineering applications optimization algorithms in the MATLAB environment. They include chapters on singleobjective and multiobjective optimization problems, discuss constraints, various objective functions, and visualization of results. Each chapter contains structured exercises and assignments for independent work that promote understanding of how algorithms work, the design of optimization models, and the interpretation of solutions. Special emphasis is placed on explaining algorithm parameters, comparing c onvergence, and the impact of settings on optimization behavior. The book concludes with an overview of typical test functions and examples of Pareto fronts for multi-objective optimization. It is designed so that even users without in-depth mathematical knowledge can gradually develop an intuition for using optimization approaches in real engineering problems.