PREGLED OPTIMIZACIJSKIH METOD IN OPTIMIZACIJA SINHRONSKEGA MOTORJA S TRAJNIMI MAGNETI

(1)

Univerza v Ljubljani

Fakulteta za elektrotehniko

ŽIVA STARE

PREGLED OPTIMIZACIJSKIH METOD IN OPTIMIZACIJA SINHRONSKEGA MOTORJA S

TRAJNIMI MAGNETI

Magistrsko delo

Magistrski študijski program druge stopnje Elektrotehnika

Mentor: prof. dr. Damijan Miljavec

Ljubljana, 2021

(2)

(3)

iii

Zahvala

Zahvaliti se želim svojemu mentorju prof. dr. Damijanu Miljavcu, univ. dipl. inž. el., za deljeno znanje v času študija in tekom izdelave magistrske naloge.

Posebno zahvalo namenjam moji družini. Partnerju, staršem in bratu se zahvaljujem za vso potrpljenje med stresnimi trenutki na moji študijski poti. Iskrena hvala pa tudi mojemu pokojnemu dedku, ki me je prvi navdušil nad matematiko in fiziko.

(4)

iv

(5)

v

Povzetek

V magistrski nalogi so opisane optimizacijske metode, ki so del računalniškega programa Matlab, ter predstavljena optimizacija z roji delcev na električnem sinhronskem motorju s trajnimi magneti.

Magistrska naloga se deli na dva večja sklopa. V prvem sklopu so opisane vse optimizacijske metode, ki so na voljo v Matlab globalno optimizacijskem programskem paketu. Poleg popularnih naravnih algoritmov, kot so genetski algoritmi, simulirano žarjenje in optimizacija z roji delcev, so v paketu dodane tudi manj znane, a še vedno pogosto uporabljene metode, kot so optimizacija z iskanjem vzorcev, optimizacija z nadomestnimi deli ter multi-start optimizacija in globalno iskanje. Programski paket omogoča tudi večkriterijsko optimizacijo.

Pregled optimizacijskih metod je razdeljen na sam opis metode, potek optimizacije in predstavitev prednosti in slabosti omenjene metode.

Drugi sklop je namenjen preizkušanju metode z roji delcev na problemu optimizacije sinhronskega motorja s površinsko nameščenimi trajnimi magneti. Pred samo optimizacijo je opisan tudi potek načrtovanja sinhronskega motorja na podlagi podanih zahtevanih nazivnih podatkov. Analitično načrtovan sinhronski motor je bil sprva optimiziran na podlagi kriterija, da ima motor čim višjo vrednost kvocienta nazivnega navora in mase železnih delov motorja.

Optimizirani motor ima vrednost kvocienta za 23,4-% višjo kot prvotni motor. Nato je bil isti prvotni sinhronski motor še optimiziran na podlagi kriterija, da ima motor čim višjo vrednost produkta nazivnega navora in izkoristka motorja. Optimizirani motor ima vrednost produkta za 76,2-% višjo kot prvotni motor. Na vseh treh verzijah sinhronskega motorja so bile izvedene tudi simulacije v simulacijskem programu FEMM 4.2. Simulirani so bili poteki gostote magnetnega pretoka v prerezu motorja ter navorni karakteristiki nazivnega in samodržnega navora. Pri optimiziranih verzijah motorja se je poleg povišanja amplitudne vrednosti nazivnega navora povečala tudi amplitudna vrednost samodržnega navora.

Ključne besede: optimizacija, optimizacija z roji delcev, Matlab, sinhronski motor s trajnimi magneti

(6)

vi

(7)

vii

Abstract

The master's thesis describes optimization methods that are part of the Matlab computer program and presents particle swarm optimization performed on an electric permanent magnet synchronous motor.

The master's thesis is divided into two major parts. The first part describes all the optimization methods available in the Matlab global optimization software package. In addition to popular natural algorithms such as genetic algorithms, simulated annealing and particle swarm optimization, the package also includes less known but still commonly used methods such as pattern search optimization, surrogate optimization, multi-start optimization and global search.

The software package also enables multiobjective optimization. The overview of the optimization methods is divided into a description of the methods, the course of an optimization and a presentation of the advantages and disadvantages of this method.

The second part is intended for testing the particle swarm method on the problem of optimizing a synchronous motor with surface-mounted permanent magnets. Prior to the optimization, the design process of the synchronous motor is described on the basis of the given required nominal data. The analytically designed synchronous motor was initially optimized based on the criteria that the motor has the highest possible value of the quotient of the nominal torque and the mass of the iron parts of the motor. The optimized engine has a quotient value 23,4-% higher than the original engine. Then, the same original synchronous motor was further optimized based on the criteria that the motor has the highest possible value of the product of nominal torque and motor efficiency. The optimized motor has a product value 76,2-% higher than the original one.

Calculations using the FEMM 4.2 simulation program were also performed on all three versions of the synchronous motor. The magnetic flux density distribution in the cross section of the motor was calculated, as well as the nominal torque characteristics and cogging torque. In the optimized versions, in addition to increasing the amplitude value of the nominal torque, the amplitude value of the cogging torque was also increased.

Key words: optimization, particle swarm optimization, Matlab, permanent magnet synchronous motor

(8)

viii

(9)

ix

Vsebina

Seznam slik xv

Seznam tabel xvii

Seznam uporabljenih simbolov xix

1 Uvod 23

2 Genetski algoritmi 24

2.1 Opis metode genetski algoritmi ... 24

2.2 Potek metode genetski algoritmi ... 25

2.3 Genetske operacije ... 26

2.3.1 Umerjanje kondicijskih vrednosti ... 26

2.3.2 Operacija izbire ... 27

2.3.3 Operacija križanja ... 28

2.3.4 Operacija mutacije ... 30

2.3.5 Sprejem novonastalih kromosomov v novo generacijo ... 31

2.4 Prednosti in slabosti metode genetski algoritmi ... 32

2.4.1 Prednosti ... 32

2.4.2 Slabosti ... 32

3 Simulirano žarjenje 34 3.1 Opis metode simulirano žarjenje ... 34

3.2 Potek metode simulirano žarjenje ... 35

3.2.1 Generiranje nove točke ... 36

3.2.2 Sprejemni mehanizem ... 37

3.2.3 Urnik ohlajevanja ... 38

3.2.4 Ponovno žarjenje ... 39

3.3 Konvergenca rezultatov ... 39

3.4 Prednosti in slabosti simuliranega žarjenja ... 39

3.4.2 Slabosti ... 40

(10)

x

4 Optimizacija z roji delcev 41

4.1 Opis optimizacije z roji delcev ... 41

4.2 Potek optimizacije z roji delcev ... 42

4.2.1 Definiranje prostora rešitev ... 43

4.2.2 Definiranje objektivne funkcije ... 43

4.2.3 Inicializacija naključne lokacije in hitrosti roja ... 43

4.2.4 Sistematično letenje delcev skozi prostor rešitev ... 44

4.2.5 Ponovitev ... 45

4.3 Velikost roja ... 46

4.4 Analiza konvergence ... 47

4.5 Prednosti in slabosti optimizacije z rojem delcev ... 47

4.5.2 Slabosti ... 47

5 Optimizacija z iskanjem vzorcev 48 5.1 Opis splošne optimizacije z iskanjem vzorcev ... 48

5.1.1 Definicija pojmov mreže in vzorca ... 49

5.1.1 Raziskovalni korak in korak posodabljanja ... 50

5.2 Potek splošne optimizacije z iskanjem vzorcev ... 51

5.3 Metoda mrežno prilagodljivega iskanja ... 52

5.4 Konvergenca pri optimizaciji z iskanjem vzorcev ... 53

5.5 Prednosti in slabosti optimizacije z iskanjem vzorcev ... 53

5.5.2 Slabosti ... 53

6 Optimizacija z nadomestnimi modeli 54 6.1 Opis optimizacijske metode z nadomestnimi modeli ... 54

6.2 Potek optimizacijske metode z nadomestnimi modeli ... 55

6.2.1 Določitev vzorčnih točk ... 57

6.2.2 Gradnja nadomestnih modelov ... 57

6.2.3 Ocenitev nadomestnih modelov ... 58

6.2.4 Iskanje minimuma objektivne funkcije ... 59

6.3 Vrednostna funkcija ... 60

6.4 Prednosti in slabosti optimizacije z nadomestnimi modeli ... 61

(11)

xi

6.4.2 Slabosti ... 61

7 Multi-start optimizacija 62 7.1 Opis multi-start optimizacije ... 62

7.2 Potek multi-start optimizacije ... 63

7.2.1 Definiranje problema ... 64

7.2.2 Generiranje začetne točke optimizacije in izbira lokalnega reševalnika 64 7.2.3 Generiranje začetnih točk za lokalni reševalnik ... 64

7.2.4 Lokalno reševanje ... 64

7.2.5 Prekinitveni kriteriji in generiranje končne rešitve ... 65

7.3 Ponavljajoče lokalno iskanje ... 65

7.3.1 Proces motenja in sprejemni kriterij ... 66

7.3.2 Tabu iskanje ... 66

7.4 Pohlepno naključni prilagodljiv iskalni postopek ... 66

7.5 Prednosti in slabosti ... 67

7.5.2 Slabosti ... 67

8 Globalno iskanje 68 8.1 Opis metode globalnega iskanja ... 68

8.2 Potek metode globalnega iskanja ... 69

8.2.1 Definiranje zastavljenega problema ... 70

8.2.2 Uporaba lokalnega reševalnika ... 70

8.2.3 Generiranje poskusnih točk ... 71

8.2.4 Inicializacija dolin privlačnosti in pragu lokalnega reševanja ... 71

8.2.5 Glavna zanka metode globalnega iskanja ... 72

8.3 Razlika med metodo globalnega iskanja in multi-start metodo ... 73

8.5 Prednosti in slabosti metode globalnega iskanja ... 73

8.5.2 Slabosti ... 73

9 Večkriterijska optimizacija 75 9.1 Opis večkriterijske optimizacije ... 75

9.1.1 Pareto optimalnost ... 76

9.2 Metoda utežene vsote ... 78

(12)

xii

9.2.1 Združevanje objektivnih funkcij v eno ... 78

9.2.2 Prednosti in slabosti metode utežene vsote ... 78

9.3 Metoda z є-omejitvami ... 78

9.3.1 Prednosti in slabosti metode z є-omejitvami ... 79

9.4 Genetski algoritmi za večkriterijske probleme ... 80

9.4.1 Elitni ne-dominirani razvrstilni genetski algoritem ... 81

9.4.2 Kontrolirani elitni genetski algoritem ... 81

9.5 Algoritem Pareto iskanja ... 82

9.5.1 Potek Paretovega iskanja ... 82

10Konstrukcija električnega sinhronskega motorja 83 10.1 Premer rotorja in dolžina motorja ... 83

10.2 Statorsko navitje ... 84

10.2.1 Navijalni načrt ... 84

10.2.2 Število ovojev statorskega faznega navitja ... 85

10.3 Zračna reža ... 86

10.4 Dimenzije zob ... 87

10.5 Dimenzije utorov ... 87

10.6 Višina statorskega in rotorskega jarma ... 88

10.7 Magnetne napetosti ... 88

10.7.1. Magnetna napetost v statorskem zobu ... 89

10.7.2. Magnetna napetost v zračni reži ... 89

10.7.3. Magnetna napetost v statorskem jarmu ... 89

10.7.4. Magnetna napetost v rotorskem jarmu ... 90

10.7.5. Magnetno vzbujanje ... 91

10.8 Trajni magneti ... 91

10.9 Izgube v bakru ... 92

10.10 Izgube v železu ... 93

10.10.1. Izgube v železu – statorski zobje ... 93

10.10.2 Izgube v železu – statorski jarem ... 94

10.10.3. Skupne izgube v železu ... 94

10.11 Izkoristek ... 94

10.12 Tabela geometrijskih podatkov prvotnega sinhronskega motorja ... 95 11Optimizacija sinhronskega motorja z roji delcev 96

(13)

xiii 11.1 Izbira optimizacije ... 96

11.2 Optimizacija sinhronskega motorja ... 97 11.2.1 Optimizacija glede na kvocient navora proti masi motorja ... 97 11.2.2 Predstavitev rezultatov optimizacije glede na kvocient nazivnega navora

proti masi motorja ... 105 11.2.3 Optimizacija glede na vrednost produkta nazivnega navora in izkoristka

motorja ... 106 11.2.4 Predstavitev rezultatov optimizacije glede na produkt nazivnega navora

in izkoristka motorja ... 108

12Analiza optimiziranih sinhronskih motorjev 110 12.1 Analiza prvotnega (ne-optimiziranega) sinhronskega motorja ... 110 12.1.1 Porazdelitev gostote magnetnega pretoka v celotnem prerezu motorja v prostem teku ... 111 12.1.2 Porazdelitev gostote magnetnega pretoka v celotnem prerezu motorja

pri nazivni točki delovanja ... 112 12.1.3 Potek normalne komponente gostote magnetnega pretoka vzdolž zračne

reže pod enim polovim parom v prostem teku ... 113 12.1.4 Potek normalne komponente gostote magnetnega pretoka vzdolž zračne

reže pod enim polovim parom pri nazivni točki delovanja ... 114 12.1.5 Potek samodržnega navora v odvisnosti od lege rotorja ... 115 12.1.6 Navorna karakteristika v odvisnosti od kolesnega kota pri nazivnem

toku ... 116 12.2 Analiza optimiziranega sinhronskega motorja glede na kvocient nazivnega

navora proti masi motorja ... 119 12.2.1 Porazdelitev gostote magnetnega pretoka v celotnem prerezu motorja v prostem teku ... 119 12.2.2 Porazdelitev gostote magnetnega pretoka v celotnem prerezu motorja

toku ... 124 12.3 Analiza optimiziranega sinhronskega motorja glede na produkt nazivnega

navora in izkoristka motorja ... 125 12.3.1 Porazdelitev gostote magnetnega pretoka v celotnem prerezu motorja v prostem teku ... 126

(14)

xiv 12.3.2 Porazdelitev gostote magnetnega pretoka v celotnem prerezu motorja

toku ... 130

Zaključek 131

Literatura 132

(15)

xv

Seznam slik

Slika 1: Potek metode genetski algoritmi ... 25

Slika 2: Operacija križanja ... 29

Slika 3: Operacija mutacije ... 31

Slika 4: Operacija elitizma ... 32

Slika 5: Potek metode simuliranega žarjenja ... 36

Slika 6: Premikanje posameznega delca v roju [2]... 42

Slika 7: Potek optimizacije z roji delcev ... 43

Slika 8: Konvergiranje roja v optimalno rešitev [15] ... 46

Slika 9: Shematičen potek optimizacije z iskanjem vzorcev [21] ... 49

Slika 10: Potek splošne optimizacije z iskanjem vzorcev ... 51

Slika 11: Izdelava nadomestnega modela [1] ... 55

Slika 12: Iskanje minimuma [1] ... 56

Slika 13: Potek optimizacije z nadomestnimi modeli ... 57

Slika 14: Potek multi-start metode ... 63

Slika 15: Dolina privlačnosti [1] ... 69

Slika 16: Potek metode globalnega iskanja ... 70

Slika 17: Pareto fronta [1] ... 77

Slika 18: Primerjava Pareto front pri metodi z є-omejitvami [2] ... 80

Slika 19: Navijalni načrt z enoplastnim navitjem [36] ... 85

Slika 20: Navijalni načrt z dvoplastnim navitjem [36] ... 85

Slika 21: Potek optimizacije ene spremenljivke pri 100 delcih v roju ... 98

Slika 22: Potek optimizacije treh spremenljivk pri 100 delcih v roju ... 101

Slika 23: Model prvotnega sinhronskega motorja z enoplastnim navitjem... 111

Slika 24: Potek gostote magnetnega pretoka v prostem teku (celoten prvotni motor) ... 112

Slika 25: Potek gostote magnetnega pretoka pri nazivnem obratovanju (celoten prvotni motor) ... 113

Slika 26: Potek normalne komponente gostote magnetnega pretoka vzdolž zračne reže pod enim polovim parom v prostem teku (prvotni motor) ... 114

Slika 27: Potek normalne komponente gostote magnetnega pretoka vzdolž zračne reže pod enim polovim parom pri nazivnem obratovanju (prvotni motor) ... 115

Slika 28: Potek samodržnega navora v odvisnosti od zasuka rotorja (prvotni motor) ... 116

Slika 29: Navorna karakteristika v odvisnosti od zasuka rotorja (prvotni motor) ... 116

(16)

xvi Slika 30: Navorna karakteristika v odvisnosti od kolesnega kota (prvotni motor) ... 117 Slika 31: Graf Fourierove analize navorne karakteristike (prvotni motor) ... 118 Slika 32: Model optimiziranega sinhronskega motorja glede na kvocient 𝑘𝑘𝑘𝑘𝑘𝑘 ... 119 Slika 33: Potek gostote magnetnega pretoka v prostem teku (celoten optimiziran motor glede na kvocient 𝑘𝑘𝑘𝑘𝑘𝑘) ... 120 Slika 34: Potek gostote magnetnega pretoka pri nazivnem obratovanju (celoten optimiziran motor glede na kvocient 𝑘𝑘𝑘𝑘𝑘𝑘) ... 121 Slika 35: Potek normalne komponente gostote magnetnega pretoka vzdolž zračne reže pod enim polovim parom v prostem teku (optimiziran motor glede na kvocient 𝑘𝑘𝑘𝑘𝑘𝑘) ... 122 Slika 36: Potek normalne komponente gostote magnetnega pretoka vzdolž zračne reže pod enim polovim parom pri nazivnem obratovanju (optimiziran motor glede na kvocient 𝑘𝑘𝑘𝑘𝑘𝑘) ... 123 Slika 37: Potek samodržnega navora v odvisnosti od zasuka rotorja (optimiziran motor glede na kvocient 𝑘𝑘𝑘𝑘𝑘𝑘) ... 123 Slika 38: Navorna karakteristika v odvisnosti od kolesnega kota (optimiziran motor glede na kvocient 𝑘𝑘𝑘𝑘𝑘𝑘) ... 124 Slika 39: Model optimiziranega sinhronskega motorja glede na produkt 𝑝𝑝𝑘𝑘𝑝𝑝... 125 Slika 40: Potek gostote magnetnega pretoka v prostem teku (celoten optimiziran motor glede na produkt 𝑝𝑝𝑘𝑘𝑝𝑝) ... 126 Slika 41: Potek gostote magnetnega pretoka pri nazivnem obratovanju (celoten optimiziran motor glede na produkt 𝑝𝑝𝑘𝑘𝑝𝑝) ... 127 Slika 42: Potek normalne komponente gostote magnetnega pretoka vzdolž zračne reže pod enim polovim parom v prostem teku (optimiziran motor glede na produkt 𝑝𝑝𝑘𝑘𝑝𝑝) ... 128 Slika 43: Potek normalne komponente gostote magnetnega pretoka vzdolž zračne reže pod enim polovim parom pri nazivnem obratovanju (optimiziran motor glede na produkt 𝑝𝑝𝑘𝑘𝑝𝑝) ... 129 Slika 44: Potek samodržnega navora v odvisnosti od zasuka rotorja (optimiziran motor glede na produkt 𝑝𝑝𝑘𝑘𝑝𝑝) ... 129 Slika 45: Navorna karakteristika v odvisnosti od kolesnega kota (optimiziran motor glede na produkt 𝑝𝑝𝑘𝑘𝑝𝑝) ... 130

(17)

xvii

Seznam tabel

Tabela 1: Podatki električnih motorjev za primer prikaza Pareto fronte ... 77

Tabela 2: Podane zahteve za sinhronski motor ... 83

Tabela 3: Geometrijske dimenzije sinhronskega motorja ... 95

Tabela 4: Optimiziranje ene spremenljivke pri 10 delcih v roju ... 97

Tabela 7: Optimiziranje dveh spremenljivk pri 20 delcih v roju ... 99

Tabela 10: Optimiziranje treh spremenljivk pri 30 delcih v roju ... 100

Tabela 13: Optimiziranje štirih spremenljivk pri 40 delcih v roju ... 101

Tabela 16: Optimiziranje petih spremenljivk pri 50 delcih v roju ... 102

Tabela 19: Optimiziranje šestih spremenljivk pri 60 delcih v roju ... 103

Tabela 22: Optimiziranje sedmih spremenljivk pri 70 delcih v roju ... 104

Tabela 25: Geometrijski podatki optimiziranega motorja glede na kvocient nazivnega navora pri masi ... 106

Tabela 26: Primerjava prvotnega in optimiziranega motorja glede na kvocient nazivnega navora proti masi ... 106

Tabela 27: Optimiziranje sinhronskega motorja glede na 𝑝𝑝𝑘𝑘𝑝𝑝 pri 70 delcih v roju ... 107

(18)

xviii Tabela 30: Geometrijski podatki optimiziranega motorja glede na produkt nazivnega navora in izkoristka ... 108 Tabela 31: Primerjava prvotnega in optimiziranega motorja glede na kvocient navora proti masi ... 109 Tabela 32: Primerjava izračunanih vrednosti med prvotnim in optimiziranima motorjema .. 109

(19)

xix

Seznam uporabljenih simbolov

V pričujočem zaključnem delu so uporabljene naslednje veličine in simboli:

Veličina Enota

Ime Simbol Ime Simbol

Carterjev faktor 𝑘𝑘𝑐𝑐 - -

Carterjev koeficient 𝐾𝐾 - -

delec v roju 𝑖𝑖 - -

dolžina motorja 𝑙𝑙 meter m

dolžina žice 𝑙𝑙_{𝑐𝑐𝑐𝑐} meter m

električni tok 𝐼𝐼 amper A

faktor krčenja 𝜃𝜃_𝑘𝑘 - -

faktor moči 𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐 - -

faktor navitja osnovnega

harmonika 𝐾𝐾_𝑤𝑤1 - -

faktor polnjenja utora 𝑘𝑘𝑐𝑐𝑐𝑐 - -

faktor razsipanja trajnega

magneta 𝑘𝑘𝜎𝜎 - -

faktor razširitve 𝜙𝜙_𝑘𝑘 - -

frekvenca 𝑓𝑓 Hertz Hz

globalno najboljša lokacija roja 𝒈𝒈^∗ - -

gostota 𝜌𝜌 kilogram na

kubični meter

kg m³

gostota električnega toka 𝐽𝐽 amper na

kvadratni meter

A m²

gostota magnetnega pretoka 𝐵𝐵 tesla T

hitrost delca 𝒗𝒗_𝑖𝑖 - -

inducirana napetost 𝐸𝐸_{𝑖𝑖𝑖𝑖𝑖𝑖} volt V

iteracija 𝑡𝑡,𝑘𝑘 - -

izgube 𝑃𝑃 watt W

izkoristek 𝑝𝑝 - -

koeficient 𝑘𝑘,𝑐𝑐 - -

koeficient aritmetičnega

povprečenja 𝛼𝛼𝑖𝑖 - -

koeficient permeance 𝑃𝑃𝑃𝑃 - -

koercitivnost trajnega magneta 𝐻𝐻_𝑐𝑐 amper na meter A

kondicijska vrednost 𝑓𝑓𝑖𝑖 - m-

kot 𝜃𝜃,𝛼𝛼 radian, stopinja rad, °

(20)

xx kvocient nazivnega navora proti

masi motorja 𝑘𝑘𝑀𝑀𝑀𝑀 Newton meter

na kilogram

Nm kg

lokalna rešitev 𝑗𝑗,𝑘𝑘 - -

magnetna napetost 𝜃𝜃 amper A

magnetna poljska jakost 𝐻𝐻 amper na meter A

magnetni pretok 𝜙𝜙 weber Wbm

maksimalna hitrost 𝒗𝒗𝑀𝑀𝑚𝑚𝑚𝑚 - -

masa 𝑘𝑘 kilogram kg

Maxwellov napetostni tenzor 𝜎𝜎_𝐹𝐹 paskal Pa

mehanska vrtilna hitrost 𝜔𝜔 radiani na

sekundo

rad s

moč 𝑃𝑃 watt W

najboljša lokacija delca 𝒙𝒙_𝑖𝑖^∗ - -

naključna številka 𝑟𝑟 - -

naključni vektor 𝒓𝒓 - -

napetost 𝑈𝑈 volt V

navor 𝑘𝑘 newton meter Nm

niz vektorjev {𝒅𝒅_𝑖𝑖} - -

nominalna vrednost 𝑘𝑘 - -

objektivna funkcija 𝑓𝑓,𝑓𝑓𝑖𝑖(𝒙𝒙) - -

objektivna vrednost 𝑓𝑓,𝑓𝑓𝑝𝑝,𝑓𝑓𝑞𝑞 - -

ohlajevalni faktor α - -

Pareto-optimalno število 𝒙𝒙_∗ - -

permeabilnost 𝜇𝜇 henry na meter H

poljubno število є𝑖𝑖 - m-

polmer rotorja 𝑟𝑟𝑟𝑟 meter m

polnilni faktor železa 𝑘𝑘𝑓𝑓𝑓𝑓 - -

polova delitev 𝜏𝜏_𝑝𝑝 meter m

polovi pari 𝑝𝑝_𝑝𝑝 - -

pospeševalna konstanta 𝛼𝛼,𝛽𝛽 - -

povprečje vsote kvadratov

rezultatov 𝑘𝑘𝑀𝑀𝑀𝑀 - -

površina (presek) 𝑀𝑀,𝐴𝐴 kvadratni meter m²

pozitivno celo število 𝑘𝑘 - -

prednostna funkcija 𝜙𝜙�𝑓𝑓1(𝒙𝒙), … ,𝑓𝑓𝑀𝑀(𝒙𝒙)� - -

premer rotorja 𝑀𝑀𝑟𝑟 meter m

produkt nazivnega navora in

izkoristka motorja 𝑝𝑝𝑀𝑀𝑀𝑀 Newton meter Nm

(21)

xxi

prostor rešitev 𝛺𝛺 - -

razdalja 𝑑𝑑(𝑥𝑥) - -

razlika 𝛥𝛥 - -

razmerje signala proti šumu 𝑀𝑀/𝑁𝑁 - -

remanenčna gostota trajnega

magneta 𝐵𝐵_𝑟𝑟 tesla T

rezultirajoča točka 𝑥𝑥_𝑝𝑝,𝑥𝑥_𝑞𝑞 - -

specifične izgube 𝑝𝑝𝑐𝑐𝑝𝑝𝑓𝑓𝑐𝑐 watt na

kilogram

W kg

spremenljivka 𝑖𝑖 - -

srednja dolžina magnetne poti 𝜏𝜏_{𝑦𝑦𝑐𝑐},𝜏𝜏_{𝑦𝑦𝑟𝑟} meter m

statorski utori 𝑄𝑄 - -

širina 𝑏𝑏 meter m

širina trajnega magneta 𝑎𝑎𝑝𝑝𝑀𝑀 meter m

širina zračne reže 𝛿𝛿 meter m

število bitov (točka križanja) 𝑛𝑛,𝑘𝑘 - -

število delcev v roju 𝑘𝑘 - -

število faz 𝑘𝑘 - -

število kromosomov

(posameznikov) 𝑛𝑛 - -

število neodvisnih spremenljivk 𝑁𝑁 - -

število objektivnih funkcij 𝑘𝑘 - -

število ovojev faznega navitja 𝑁𝑁 - -

število podskupin 𝐿𝐿 - -

število ponovitev poskusov 𝑛𝑛 - -

število vodnikov na utor 𝑍𝑍𝑞𝑞 - -

temperatura 𝑇𝑇 kelvin K

tokovna obloga 𝐴𝐴 amper na meter A

trenutna lokacija delca 𝒙𝒙_𝑖𝑖 - m-

umerjena razdalja 𝑀𝑀(𝑥𝑥) - -

umerjena vrednost

nadomestnega modela 𝑀𝑀(𝑥𝑥) - -

upornost 𝑅𝑅 ohm Ω

utežni koeficient 𝜔𝜔_𝑖𝑖,𝜔𝜔 - -

utorska delitev 𝜏𝜏_𝑐𝑐 meter m

vektor odločitvenih

spremenljivk 𝒙𝒙 - -

velikost mreže 𝛥𝛥^𝑀𝑀 - -

verjetnost 𝑝𝑝 - -

(22)

xxii

verjetnost križanja 𝑝𝑝𝑐𝑐 - -

verjetnost mutacije 𝑝𝑝_𝑀𝑀 - -

višina ℎ meter m

višina trajnega magneta ℎ_{𝑝𝑝𝑀𝑀} meter m

volumen 𝑉𝑉 kubični meter m³

vrednost nadomestnega modela 𝑐𝑐(𝑥𝑥) - -

vrednosti ponovljenih

rezultatov enega poskusa 𝑦𝑦1,2… - -

vrednostna funkcija 𝑓𝑓_{𝑣𝑣𝑟𝑟𝑓𝑓𝑖𝑖}(𝑥𝑥) - -

vrtilna hitrost 𝑛𝑛 vrtljaji na

minuto

vrt min

vzorec {𝒗𝒗_𝑖𝑖} - -

vztrajnostna funkcija 𝜃𝜃(𝑡𝑡) - -

začetna točka 𝑝𝑝,𝑥𝑥0 - -

zaporedna številka kromosoma

(posameznika) v populaciji 𝑖𝑖 - -

zunanji premer motorja 𝑀𝑀_𝑐𝑐 meter m

žarilni parameter 𝑘𝑘 - -

Pri čimer so vektorji in matrike zapisani s poudarjeno pisavo. Natančnejši pomen simbolov ter njihovih indeksov je razviden iz ustreznih slik ali pojasnjen v spremljajočem besedilu, kjer je simbol uporabljen.

V magistrski nalogi so za določene funkcije in ukaze, ki so del računalniškega programa Matlab, uporabljeni izrazi, ki niso poslovenjeni. Ti ukazi so zapisani v navednicah.

(23)

23

1 Uvod

Optimizacijska metoda je algoritem, ki se ukvarja z iskanjem lokalnih in globalnih optimumov objektivne funkcije ali več objektivnih funkcij, s katerimi se opiše zastavljeni problem. Uporaba optimizacijskih metod pri reševanju inženirskih problemov se je močno razširila v zadnjih desetletjih. Razlogov je več, predvsem pa je k širši uporabi pripomogel tehnološki napredek na zmogljivosti osebnih računalnikov, saj je tako postala optimizacija dostopna širši javnosti in ni bila več omejena samo na laboratorije. Z boljšo zmogljivostjo osebnih računalnikov se je razširila tudi ponudba računalniških orodij, ki omogočajo uporabo različnih optimizacijskih metod. Eden od ponudnikov je tudi računalniški program Matlab, ki ponuja s svojim globalno optimizacijskim programskim paketom optimizacijo problemov z različnimi metodami.

Povod za nastanek magistrske naloge je bila množica optimizacijskih metod, ki jih ponuja program Matlab, saj se lahko nevešči uporabnik hitro izgubi med vsemi ponujenimi možnostmi.

Prav tako se je zaradi razširitve uporabe optimizacijskih metod eksponentno povečala tudi količina literature na temo optimizacije, kar oteži odločanje med metodami, ki jih ponuja računalniško orodje. Cilj magistrske naloge je na enem mestu zbrati vso potrebno znanje, da se inženir lahko odloči, katera metoda bo najbolje ustreza njegovemu problemu. Velik poudarek je tudi na razlagi poteka optimizacijskih metod, saj je odločanje med metodami lažje, če poznamo njihovo delovanje. Pri samem pregledu in opisu metod smo si pomagali predvsem z Matlabovim uporabniškim priročnikom [1] ter knjigo avtorja Xin-She Younga, ki opisuje naravne algoritme [2]. Opisane metode si v magistrski nalogi sledijo v naslednjem zaporedju, genetski algoritmi, simulirano žarjenje, optimizacija z roji delcev, optimizacija z iskanjem vzorcev, optimizacija z nadomestnimi modeli, multi-start optimizacija, globalno iskanje in na koncu še večkriterijska optimizacija.

Drugi cilj magistrske naloge je optimizacija sinhronskega motorja s površinsko nameščenimi trajnimi magneti z uporabo Matlabovega globalno optimizacijskega programskega paketa. Med vsemi ponujenimi metodami smo se nato odločili, da bomo optimizacijo izvedli z optimizacijo z roji delcev, saj je bila želja uporabiti učinkovit, a redkeje uporabljen naravni algoritem. Pred samo optimizacijo sledi poglavje, ki opisuje potek analitičnega dimenzioniranja sinhronskega motorja. Pri načrtovanju smo si pomagali s knjigo Juhe Pyrhönen [3]. Dimenzionirani sinhronski motor smo v poglavju, ki sledi, optimizirali z roji delcev. Pri nastavitvah optimizacije smo si ponovno pomagali z Matlabovim uporabniškim priročnikom [1]. Po optimizaciji sledi še analiza prvotnega in optimiziranih motorjev ter primerjava med njimi.

(24)

24

2 Genetski algoritmi

Prva optimizacijska metoda, ki je opisana, so genetski algoritmi (ang. genetic algorithms, kratica GA). Genetski algoritmi so iskalni in optimizacijski algoritmi, ki temeljijo na načelih naravnega razvoja (evolucije), prvič pa so bili predstavljeni v 70. letih prejšnjega stoletja. Pionir genetskih algoritmov je bil ameriški znanstvenik John Henry Holland. Optimizacija pri genetskih algoritmih se izvaja s pomočjo simulacije razvoja vrst skozi naravno selekcijo.

Algoritem je na splošno sestavljen iz dveh procesov. Prvi postopek je izbira posameznika za razvoj naslednje generacije. Posameznika se izbere s pomočjo izbirnega mehanizma. Z njim določimo tudi število potomcev, ki jih ima izbrani posameznik. Pomen drugega postopka je oblikovanje naslednje generacije. To storimo s spreminjanjem izbranega posameznika z različnimi križanji in mutacijskimi tehnikami. Glavno načelo strategije je ''preživetje najmočnejših bo zmagalo'' [4], [5].

2.1 Opis metode genetski algoritmi

Metoda temelji na biološki evoluciji živih bitij. Genetski algoritmi poskušajo zastavljeni problem opisati kot populacijo posameznikov ter z iterativnim ustvarjanjem naslednjih generacij iščejo najprimernejše oziroma najboljše posameznike. GA predpostavljajo, da so ti posamezniki rešitev zastavljenega problema in jih lahko opišemo s parametri. Ti parametri so analogija genom kromosomov in se jih lahko združi v nize binarne kode. Vrednost kromosoma opišemo s kondicijsko vrednostjo. Ta opisuje stopnjo primernosti kromosoma za reševanje zastavljenega problema. Postopek optimizacije se začne z začetno populacijo, ki je sestavljena iz naključnih posameznikov, nato pa so pri vsaki naslednji generaciji na vsakem posamezniku zaporedno uporabljene tri osnovne genetske operacije: izbira, križanje in mutacija. S procesom evolucije preko genetskih operacij boljši kromosomi razvijejo več potomcev ter imajo tako višjo možnost preživetja v naslednji generaciji. S tem je posneman mehanizem zakona močnejšega v naravi [4], [5].

Pri GA je prostor za iskanje sestavljen iz različnih nizov, ki jih imenujemo kromosomi. Vsak kromosom predstavlja možno rešitev problema, njegovo objektivno funkcijsko vrednost pa ocenjujemo s kondicijsko vrednostjo. Skupino kromosomov skupaj z njihovimi kondicijskimi vrednostmi imenujemo populacija. Generacije pa so populacije, ki so iterativno generirane s pomočjo GA [4].

Metoda GA deluje na podlagi hipoteze ''gradnje z bloki'', ki opisuje delovanje GA kot gradnjo optimalnih nizov (kromosomov) iz osnovnih blokov (genov), ki jih generiramo s pomočjo genetskih operacij (izbira, križanje, mutacija). Operacija križanja po navadi ohranja genetsko informacijo, zato se s časom sposobnost generiranja novih osnovnih blokov zmanjšuje. Po drugi strani pa operacija mutacije ne ohranja genetskih informacij, zato je z njo možno generirati ogromno novih nizov. Upoštevati moramo tudi operacijo izbire, ki je nagnjena h gradnji nizov z višjo kondicijsko vrednostjo, zato da se ta vrednost ohranja iz generacije v generacijo.

(25)

25 Hipoteza predpostavlja, da dobra izbira staršev rezultira v dobrih potomcih z visoko kondicijsko vrednostjo, kar pa ni vedno res. Odvisno od narave objektivne funkcije problema obstaja tudi možnost, da se iz dobrih staršev razvijejo slabi potomci z majhno kondicijsko vrednostjo.

Takšnim objektivnim funkcijam pravimo GA-zavajajoče funkcije [5], [6].

2.2 Potek metode genetski algoritmi

Potek optimizacijske metode genetski algoritmi je viden na sliki 1 ter opisan v naslednjih korakih:

Slika 1: Potek metode genetski algoritmi

(26)

26 1. Začetek: generiranje naključne populacije z 𝑛𝑛 kromosomi.

2. Kondicijska vrednost: ocenitev kondicijske vrednosti 𝑓𝑓_𝑖𝑖 posameznega 𝑖𝑖 kromosoma v populaciji. Nato je treba te kondicijske vrednosti še umeriti, da dobimo primernejši razpon kondicijskih vrednosti.

3. Nova populacija: izdelava nove populacije s ponavljanjem korakov 3.a, 3.b, 3.c in 3.d.

Korake ponavljamo, dokler ni končana celotna populacija.

a. Izbira: izbira dveh kromosomov iz populacije, da postaneta starša, na podlagi njune kondicijske vrednosti. Višjo kondicijsko vrednost kot ima kromosom, večja je verjetnost, da bo izbran.

b. Križanje: z verjetnostjo križanja križamo starša, da ustvarimo potomce (otroke).

Če križanje ni izvedeno, potem so potomci točna kopija svojih staršev.

c. Mutacija: z verjetnostjo mutacije se vsakega potomca mutira na nekem bitnem mestu v binarni kodi kromosoma.

d. Sprejetje: novega potomca dodamo v novo (naslednjo) populacijo.

4. Zamenjava: z novonastalo populacijo nadaljujemo postopek algoritma (vrnemo se na 2.

korak).

5. Testiranje: če populacija zadosti končnemu pogoju, se optimizacija zaključi. Končni pogoji so lahko različni, npr. doseženo željeno število evolucijskih ciklov, dosežena željena raznolikost posameznikov med generacijami oziroma dosežena željena kondicijska vrednost. Rezultati so najboljše rešitve v trenutni populaciji [1], [4], [5].

2.3 Genetske operacije

GA delujejo na iskanju rešitev za zastavljeni problem s tremi genetskimi operacijami: izbiranje, križanje in mutacija. V tem poglavju so opisane različne metode, s katerimi lahko dosežemo prej naštete genetske operacije. Prav tako je opisano tudi umerjanje kondicijskih vrednosti ter sprejemanje novonastalih kromosomov v populacijo.

2.3.1 Umerjanje kondicijskih vrednosti

GA z metodo umerjanja kondicijske vrednosti poskrbijo, da so kondicijske vrednosti v primernejšem vrednostnem razponu za operacijo izbire. Prav tako je od razpona kondicijskih vrednosti kromosomov odvisno delovanje celotne optimizacije. Če je razpon vrednosti preširok, potem se kromosomi z višjo kondicijsko vrednostjo prehitro reproducirajo in posledično prehitro zavzamejo genski bazen, kar metodi GA prepreči, da bi raziskala še druge predele prostora rešitev. Po drugi strani, če je pa razpon vrednosti premajhen, potem imajo vsi kromosomi približno isto možnost reprodukcije, kar rezultira v počasnejšo konvergenco v optimalno rešitev [1].

Privzeto umerjanje v Matlab globalno optimizacijskem programskem paketu (ang. Matlabs's global optimization toolbox, kratica GOPP) je metoda rangiranja. Z njo kromosome umerimo

(27)

27 na podlagi njihovega ranga in ne na podlagi kondicijske vrednosti. Rang kromosoma se določi glede na njegovo pozicijo med drugimi kromosomi: kromosom z najvišjo vrednostjo kondicijske funkcije ima rang 1, kromosom z drugo najvišjo kondicijsko vrednostjo ima rang 2 itd. Umerjena vrednost kromosoma je sorazmerna z ¹

√𝑟𝑟 , kjer število 𝑟𝑟 predstavlja njegov rang [1].

Umerimo lahko tudi z metodo najboljših. Z metodo najboljših najprej v generaciji izberemo kromosome, ki spadajo v zgornji 40-% delež vseh kromosomov na podlagi njihove kondicijske vrednosti, torej izberemo kromosome z višjimi vrednostmi kondicijske funkcije in jim določimo isto umerjeno vrednost. Ostalim kromosomom dodelimo vrednost 0. Z drugimi besedami, samo 40 % kromosomov z najvišjimi kondicijskimi vrednostmi so lahko starši.

Metoda najboljših je v primerjavi z metodo rangiranja manj raznolika, saj so starši lahko le kromosomi z najvišjimi vrednostmi kondicijske funkcije [1].

Poleg opisanih metod umerjenja ima Matlab GOPP tudi možnosti linearnega umerjanja kondicijske vrednost kromosomov ter možnost, da sami definiramo metodo umerjanja [1].

2.3.2 Operacija izbire

Z izbirno operacijo izberemo najboljše posameznike v trenutni populaciji, ki bodo kot starši generirali potomce. Kriterij za izbiro posameznikov je kondicijska vrednost. Obstaja veliko metod, s katerimi lahko določimo najprimernejše kromosome, Matlab GOPP pa nam tudi omogoča, da sami definiramo izbirno metodo [4], [5].

Primarna operacija izbire Matlab GOPP-a

Pri primarni operaciji izbire v Matlab GOPP-u so kromosomi postavljeni v linijo, kjer je dolžina, ki jo zasede kromosom, sorazmerna z njegovo kondicijsko vrednostjo. Algoritem se premika po liniji v korakih, ki so vsi enake dolžine. Pri vsakem koraku algoritem pristane na nekem kromosomu in ga nato izbere kot starša [1].

Izbira s pomočjo rulete

Starši so izbrani glede na njihovo kondicijsko vrednost. Boljši so kromosomi, večja je verjetnost, da bodo izbrani. To metodo si lahko predstavljamo tako, kot da so na ruleto postavljeni vsi kromosomi iz populacije, vendar kromosomi z višjo kondicijsko vrednostjo zasedejo več prostora. Na podlagi tega bodo kromosomi z višjimi vrednostmi izbrani večkrat.

Težave s to metodo nastanejo, ko so kondicijske vrednosti med kromosomi preveč različne. Na primer, če ima en kromosom kondicijsko vrednost, ki zasede 90 % rulete, bodo imeli ostali kromosomi zelo majhne možnosti, da bodo izbrani. Ta metoda je kljub določenim slabostim v praksi največkrat uporabljena [4], [5].

(28)

28 Izbira na podlagi preostanka

Pri izbiri na podlagi preostanka se starše izbere glede na njihov celoštevilski del kondicijske vrednosti. Na decimalnem preostanku kondicijske vrednosti pa se nato izvede izbira na podlagi rulete. Torej če ima kromosom npr. kondicijsko vrednost enako 2,3, potem je dvakrat izbran kot starš, saj je celoštevilski del kondicijske vrednosti enak 2. Ko enkrat določimo starše na podlagi njihovega celoštevilskega dela, ostali del staršev določimo stohastično. Verjetnost, da bo starš izbran v tem koraku, je sorazmerna z decimalnim delom njegove kondicijske vrednosti [1].

Enoten izbor

Enoten izbor izbere starše na podlagi njihove kondicijske vrednosti in števila željenih staršev.

Enoten izbor je primeren za testiranje in optimiziranje iskanja optimalne vrednosti, ni pa primeren potem za samo optimizacijo zastavljenega problema [1].

Izbira na podlagi turnirja

V Matlab GOPP-u je možno izbirati med različnimi operacijami izbire. Poleg zgoraj opisanih metod program omogoča tudi uporabo izbire na podlagi turnirja. Pri izbiri na podlagi turnirja se iz trenutne populacije naključno izbere določeno število kromosomov in se jih primerja med sabo. Za starša je izbran kromosom z najvišjo kondicijsko vrednostjo [1].

2.3.3 Operacija križanja

Ko se enkrat določi, kateri kromosomi iz trenutne populacije bodo starši, jih je treba med seboj križati in mutirati. Produkt operacije križanja dveh staršev sta dva nova potomca, ki nastaneta s kopiranjem posameznih bitov od posameznega starša. Na primer, potomec ima v svoji binarni kodi na mestu 𝑖𝑖 bit, ki je bil skopiran iz mesta 𝑖𝑖 iz binarne kode enega od staršev. S križno masko določimo, kateri starš prispeva svoj bit za določeno pozicijo v potomčevi kodi.

Verjetnost križanja 𝑝𝑝_𝑐𝑐 določimo v območju med 0,6 in 1. Določitev faktorja verjetnosti je kompleksen in nelinearen optimizacijski problem, obstajajo pa določena priporočila. Za manjše populacije (okoli 30 kromosomov) uporabimo vrednosti okoli 0,9, pri večji populacijah (okoli 100 kromosomov) pa je verjetnost križanja 0,6. S povečevanjem verjetnosti križanja se povečuje število različnih kombinacij osnovnih gradnikov, vendar se poveča tudi motenje dobrih genov. Splošen komentar na primernost različnih križanj je, da je vsako križanje zelo koristno za nekatere vrste problemov, a precej neučinkovito za druge, vendar se eksperimentalno najslabše odreže enotočkovno križanje [4]–[6].

Pri Matlab GOPP-u kromosomi niso sestavljeni iz binarnih kod, vendar jih predstavimo kot vektorje. Potek operacij poteka na enak način, kot če v binarni kodi zamenjamo bit, le da se pri vektorjih zamenja podatek na določeni lokaciji v vektorju. Na sliki 2 je na poenostavljen način prikazana operacija križanja.

(29)

29 Slika 2: Operacija križanja

Enotočkovno križanje

Pri enotočkovnem križanju ima potomec prvih 𝑛𝑛 bitov prekopiranih od prvega starša, ostale bite pa dobi od drugega starša. Vsakič, ko je izbrano enotočkovno križanje, se točka križanja določi naključno in se nato ustvari še križno masko. Binarna koda križne maske je sestavljena iz 𝑛𝑛 števila 1, ostalo so 0. Točka križanja predstavlja število bitov 𝑛𝑛 [4].

Na primer, če je binarna koda kromosomov dolga 8 bitov, imamo enotočkovno križanje, enotočkovno križanje pa je določilo točko križanja pri 5 bitih, je binarna koda križne maske enaka 1111 1000. Prvi potomec ima torej prvih 5 bitov istih kot prvi starš, ostale 3 pa ima enake kot drugi starš. Pri drugem potomcu je postopek enak, samo vrstni red staršev se zamenja, torej je drugi potomec sestavljen iz bitov, ki niso bili uporabljeni pri prvem potomcu.

Dvotočkovno križanje

Pri dvotočkovnem križanju so potomci narejeni z dvema zamenjavama bitov med staršema, torej je narejen z zamenjavo sredinskega dela binarne kode enega starša s sredinskim delom kode drugega starša. Določimo torej dve točki križanja 𝑛𝑛 in 𝑚𝑚. Potomec ima prvih 𝑛𝑛 bitov enakih kot prvi starš, nato sledijo biti drugega starša in na 𝑚𝑚 mestu v binarni kodi se ponovno ponovijo biti prvega starša. Kot pri enotočkovnem križanju je drugi potomec narejen z zamenjavo vlog staršev, torej prvi starš postane drugi in obratno [1], [4].

Na primer, imamo ponovno kromosome z 8 bitno binarno kodo in dvotočkovnim križanjem, ki je določil prvo točko križanja 3, drugo točko križanja pa 6. Prva točka določi število mest, ki jih bodo zasedle 0 v kodi križne maske (v našem primeru bodo torej prvi trije biti 0), nato sledijo 1 in nato druga točka križanja določi mesto, na katerem se spet nadaljujejo 0. Torej je binarna koda maske 0001 1100 in se bosta med staršema zamenjali biti, ki so na isti poziciji, kot so 1 v kodi maske.

(30)

30 Raztreseno križanje

Pri raztresenem križanju je celotna križna maska določena naključno, vendar je v navadi tako, da oba starša prispevata približno enako število genov. V različnih literaturah se ta možnost imenuje tudi enotno križanje [1], [4], [5].

Na primer, ponovno imamo 8 bitne binarne kode, križna maska ima naključno generirano kodo 0110 0111. Prvi potomec bo imel na mestih, kjer ima križna maska v kodi bit 1, kopiran bit od prvega starša, kjer pa je bit 0, tam bo kopiran bit drugega starša. Pri drugem potomcu se vlogi prvega in drugega starša zamenjata.

Že veliko študij se je ukvarjalo s primerjavo različnih metod križanj, predvsem med dvotočkovnim in raztresenim križanjem. Raztreseno križanje zamenja bite ne glede na njihovo pozicijo, kar lahko privede do motenj pri iskanju rešitve. Po drugi strani pa sta enotočkovno in dvotočkovno križanje manj moteča, saj menjata bite po določeni shemi, vendar ju to naredi manj raziskovalne, predvsem ko populacija postaja bolj homogena. Empirični dokazi priporočajo, da se raztreseno križanje uporabi pri manjših populacijah, za večje pa je primernejše dvotočkovno. Motnje, ki nastanejo zaradi raztresenega križanja, pomagajo ohranjati raziskovanje v manjših populacijah. Pri večjih populacijah pa je raznolikost že dana, zato je dvotočkovno križanje primernejše [6].

Vmesno, hevristično in aritmetično križanje

Operacije križanja, kot so vmesno, hevristično in aritmetično, generirajo potomce kot vsoto obeh staršev. Pri vmesnem križanju potomec nastane kot utežena vsota obeh staršev, kjer vrednosti uteži nastavimo sami. Pri hevrističnem križanju potomec ponovno nastane kot utežena vsota obeh staršev, vendar je bolj podoben staršu, ki ima višjo kondicijsko vrednost.

Nasprotno pa potomec pri aritmetičnem križanju nastane kot aritmetična vsota obeh staršev [1].

Poleg naštetih in opisanih operacij križanja Matlab GOPP tudi omogoča, da uporabnik sam definira metodo križanja.

2.3.4 Operacija mutacije

Poleg operacije križanja, kjer je potrebno sodelovanje dveh staršev, obstaja tudi operacija mutacije, kjer so potomci narejeni iz enega starša. Operacija mutacije v binarni kodi starša naključno izbere en bit in mu spremeni njegovo vrednost in tako nastane potomec. Verjetnost mutacije 𝑝𝑝𝑚𝑚 je v primerjavi z verjetnostjo križanja veliko manjša, in sicer manjša od 0,1.

Določitev faktorja verjetnosti je kompleksen in nelinearen optimizacijski problem, obstajajo pa določena priporočila. Za manjše populacije (okoli 30 kromosomov) uporabimo vrednosti okoli 0,01, pri večji populacijah (okoli 100 kromosomov) pa je verjetnost križanja 0,001. S povečevanjem verjetnosti mutacije se genetsko iskanje rešitve problema spremeni v bolj naključno iskanje, vendar se lahko tako ponovno najde izgubljen genetski material [4]–[6].

(31)

31 V Matlab GOPP-u imamo za operacijo mutacije 4 možne izbire: Gaussova mutacija, enotna mutacija, prilagodljiva mutacija ter možnost, da sami definiramo operacijo mutacije. Gaussova in enotna mutacija se uporabljata za neomejene probleme, prilagodljivo mutacijo pa uporabljamo pri omejenih problemih. Na sliki 3 je na poenostavljen način prikazana operacija mutacije [1].

Slika 3: Operacija mutacije

Gaussova mutacija

Gaussova mutacija je privzeta metoda za neomejene probleme. Algoritem podatkom v starševskem vektorju doda naključno generirano številko na podlagi Gaussove porazdelitve s povprečno vrednostjo 0 [1].

Enotna mutacija

Tudi enotna mutacija je namenjena neomejenim problemom, vendar je ta sestavljena iz dveh korakov. Prvi korak je izbira deleža podatkov v kromosomskem vektorju, ki imajo verjetnost 𝑝𝑝_𝑚𝑚, da bodo mutirani. Privzeta verjetnost 𝑝𝑝_𝑚𝑚 ima vrednost 0,01. Pri naslednjem koraku algoritem zamenja izbrane kromosomske podatke z naključno generirano številko [1].

2.3.5 Sprejem novonastalih kromosomov v novo generacijo

Po končanih operacijah izbire, križanja in mutacije imamo sedaj razvite potomce, kateri nadomestijo staro generacijo. Obstajajo različne metode zamenjave stare generacije z novo. Pri Matlab GOPP-u imamo metodo, kjer sami določimo število posameznih vrst potomcev v novi generaciji. Prav tako je možna uporaba elitnega štetja, kjer določimo število kromosomov iz trenutne generacije, ki bodo zagotovo preživeli v naslednjo generacijo, saj imajo najvišjo kondicijsko vrednost. Te kromosome imenujemo elitni potomci. Na sliki 4 je na poenostavljen način prikazano, kako dobimo elitne potomce. Druga možnost je delež križanja. S to možnostjo določimo število (delež) kromosomov v novi generaciji, ki so nastali z operacijo križanja.

Ostanek generacije sestavljajo potomci, ki so nastali z operacijo mutacije [1].

(32)

32 Slika 4: Operacija elitizma

Opisani metodi spadata v generacijske zamenjave, kjer se zamenjajo vsi kromosomi v trenutni populaciji s potomci. V literaturi [5] pa je predlagana tudi generacijska zamenjava, kjer se zamenja samo del populacije. Ta metoda se uporablja v primerih, ko imamo manjše število potomcev. Potomci pogosto nadomestijo najslabše kromosome iz stare generacije, poznana pa je tudi tehnika, ko potomci direktno zamenjajo svoje starše.

2.4 Prednosti in slabosti metode genetski algoritmi

2.4.1 Prednosti

Prednost GA je, da ni težav pri določanju omejitev zastavljenega problema, saj se jih vgradi kar v kromosomsko binarno kodo. Prav tako se lahko GA uporabljajo tudi za večkriterijske probleme in probleme, ki imajo diskretno, stohastično ali močno nelinearno objektivno funkcijo. Največja prednost je njena enostavna in široka uporaba, saj se jo lahko implicira v različne probleme, tako matematične kot ne-matematične. Poleg tega jo je možno vgraditi v že narejene simulacije oziroma modele [1], [5].

2.4.2 Slabosti

Največja kritika pri GA-metodi je čas, ki je porabljen za računanje (optimizacijo). To je razumljivo, saj GA niso matematično vodena rešitev problema, ampak je stohastičen, diskreten in nelinearen iskalni algoritem. Za uporabo GA v praktične namene, predvsem na področju krmiljenja in obdelave signalov, je treba najprej skrajšati optimizacijski čas. To se predvsem rešuje z združevanjem GA z drugimi optimizacijskimi metodami [5].

Težave z GA-metodo se lahko pojavijo tudi pri sami optimizaciji, saj obstajajo GA-zavajajoče funkcije, ki jih GA ne znajo dobro optimizirati, zato se skozi generacije razvijejo slabi kromosomi (slabe rešitve na zastavljeni problem) [5].

Težave nastanejo tudi pri optimizaciji dinamičnih podatkov, saj je možno, da kromosomi začnejo prehitro konvergirati proti rešitvam, ki ne bodo uporabne za kasnejše podatke, ter dobimo rešitev, ki je lokalni optimum in ne globalni. Ta pojav imenujemo genetsko odnašanje,

(33)

33 njegova rešitev pa je predvsem povečanje genetske raznolikosti v populaciji, saj s tem preprečimo prehitro konvergenco. Metod za povečanje genetskih raznolikosti je veliko, npr.

mehanizem naključnih imigrantov, ko del populacije zamenjamo z naključno generiranimi kromosomi. Bolj preprosta rešitev pa je povečanje verjetnosti mutacij [5], [7].

(34)

34

3 Simulirano žarjenje

V tretjem poglavju je opisana optimizacijska metoda simulirano žarjenje. Simulirano žarjenje (ang. simulated annealing, kratica SŽ) je iskalni algoritem, ki je zmožen ubežati lokalnemu optimumu in najti globalni optimum zastavljenega problema. SŽ je zaradi svoje enostavne uporabe, dobrih konvergenčnih lastnosti ter zmožnosti izogibanja lokalnemu optimumu postalo zelo priljubljeno optimizacijsko orodje. Navadno se uporablja za reševanje diskretnih problemov, možno pa ga je uporabiti tudi za zvezne optimizacijske probleme [8].

Prvotno se je SŽ-algoritem uporabljal za reševanje ekonomskih problemov. Začetki algoritma segajo v 80. leta prejšnjega stoletja, njegovi avtorji so Kirkpatrick, Gelatt in Vechhi. Smisel algoritma je iskanje globalnega maksimuma oziroma minimuma pri funkciji, ki ima več kot en lokalni optimum [9], [10].

Ime in navdih za algoritem prideta iz fizičnega procesa žarjenja pri obdelavi kovine. Žarjenje je proces, pri katerem snov segrejemo in ohladimo, da se spremenijo njene fizikalne lastnosti.

Posledica sprememb fizikalnih lastnosti je tudi spremenjena notranja zgradba materiala [9].

3.1 Opis metode simulirano žarjenje

V vsaki iteraciji algoritma se generira nova naključna točka (rešitev). Razdaljo med trenutno točko in novo točko se določi na podlagi porazdelitvene verjetnosti, ki je sorazmerna s temperaturo oziroma temperaturnim parametrom (pri razlagi simuliranega žarjenja sta pojma temperatura in temperaturni parameter zamenljiva). Za nadaljnjo obdelavo so izbrane vse boljše rešitve ter tudi delček slabih, v upanju, da se pri iskanju globalnega optimuma izognemo lokalnemu. Dobra rešitev je tista, ki pri iskanju npr. globalnega minimuma zmanjša vrednost objektivne funkcije, slabša pa je tista, ki jo zvišuje. Verjetnost izbire slabih rešitev je odvisna od temperaturnega parametra, ki tipično ne narašča z vsako naslednjo ponovitvijo algoritma.

Sistematično zmanjševanje temperaturnega koeficienta dosežemo z urnikom ohlajevanja [1], [8], [9].

Pri SŽ je temperatura parameter, ki vpliva na dva vidika optimizacijskega algoritma. Z njo vplivamo na razdaljo med trenutno in novo točko. Prav tako pa z njo določamo verjetnost, da bo za trenutno točko izbrana slabša točka [1].

Žarilni parameter

Pri simuliranem žarjenju uporabljamo tudi žarilni parameter, ki zastopa številko iteracije.

Algoritem lahko poviša temperaturo sistema tako, da nastavi žarilni parameter na vrednost, ki je manjša od številke trenutne iteracije [1].

(35)

35 Ponovno žarjenje

Pri metodi simuliranega žarjenja uporabimo tehniko žarjenja za kontrolirano zmanjševanje temperature sistema, s čimer želimo doseči optimalno stanje oziroma rešitev. Uporabimo pa lahko tudi tehniko ponovnega žarjenja, kjer sistemu ponovno povišamo temperaturo. Algoritem najprej sprejme določeno število novih točk, nato pa se iskanje optimalne rešitve ponovno začne pri višji temperaturi. Z metodo ponovnega žarjenja dosežemo, da se algoritem izogne lokalnemu optimumu [1].

3.2 Potek metode simulirano žarjenje

Pred začetkom optimizacije zastavljenega problema z metodo SŽ moramo najprej določiti prostor rešitev Ω, torej določiti moramo vse možne rešitve našega problema. Nato določimo objektivno funkcijo, s katero bomo iz celotnega prostora rešitev dobili rešitev našega problema.

Rešitev bo globalni optimum, od problema pa je odvisno, ali iščemo globalni minimum ali maksimum [8].

Konec optimizacije dosežemo z različnimi prekinitvenimi pogoji, npr. dosežena je bila tolerančna razlika med objektivnima funkcijskima vrednostma v dveh zaporednih iteracijah, doseženo je bilo maksimalno dovoljeno število iteracij oziroma maksimalni dovoljeni čas za izračun itd. [1].

Na sliki 5 je prikazan potek metode simuliranega žarjenja.

(36)

36 Slika 5: Potek metode simuliranega žarjenja

3.2.1 Generiranje nove točke

Optimizacija se začne z naključnim generiranjem nove točke, ki je od trenutne točke oddaljena za razdaljo, ki je določena na podlagi porazdelitvene verjetnosti, ki je sorazmerna s trenutnim temperaturnim parametrom. Razdalje novih točk in njihovo porazdeljenost po prostoru rešitev določimo na podlagi različnih funkcij. V Matlab GOPP-u imamo na voljo dve možnosti, prav tako nam program omogoča, da sami definiramo funkcijo [1].

Hitro žarjenje

Pri funkciji hitrega žarjenja je razdalja med novo in trenutno točko enaka trenutni temperaturi.

Smer nove točke je določena naključno, vendar so točke enotno porazdeljene [1].

Boltz žarjenje

Pri funkciji Boltz žarjenja je razdalja med novo in trenutno točko enaka kvadratnemu korenu trenutne temperature. Smer nove točke pa je ponovno določena naključno, prav tako so vse točke enotno porazdeljene [1].

(37)

37 3.2.2 Sprejemni mehanizem

Nato je treba definirati sprejemni mehanizem, ki odloči, katero stanje (rešitev) bo postalo novo trenutno stanje. Sprejemni mehanizem v začetnih korakih (pri visoki temperaturi sistema) prednjači raziskovanje prostora rešitev in sprejema nova stanja ne glede na njihovo funkcijsko vrednost; kasneje, pri nižji temperaturi, pa mora sprejemni mehanizem izbirati le boljša stanja (rešitve) [11].

Pri Matlab GOPP-u sta na voljo dva različna sprejemna mehanizma oziroma sprejemni funkciji.

Prva možnost je, da sami definiramo sprejemno funkcijo, druga, privzeta sprejemna funkcija pa je opisana z enačbo (3.1).

𝑝𝑝= 1

1 +𝑒𝑒^{max(𝑇𝑇)}^{𝛥𝛥𝑓𝑓}

(3.1)

Kjer je 𝑝𝑝 verjetnost, da bomo sprejeli slabšo rešitev, 𝛥𝛥𝑓𝑓 predstavlja razliko med novo in staro (trenutno) objektivno vrednostjo in je pozitivna vrednost. Če je razlika negativna, potem je nova objektivna vrednost manjša od trenutne in je točka avtomatično sprejeta kot naslednja trenutna točka. Vrednost 𝑇𝑇 je trenutna temperatura sistema in je prav tako vedno pozitivna. Pri višjih temperaturah sistema je sprejemna verjetnost, da bomo za naslednjo rešitev izbrali slabšo, večja, kot pri nižjih temperaturah. Prav tako pa večje razlike med objektivnima vrednostma vodijo v manj pogosto sprejemanje slabših točk [1].

V različnih literaturah je pogosto omenjen in uporabljen tudi Metropolisov sprejemni mehanizem. Sprejemna verjetnost je pri tem kriteriju opisana z Boltzmannovo porazdeljenostjo.

Na primer, pri problemu, kjer iščemo globalni minimum, bodo vsa stanja, ki zmanjšujejo vrednost objektivne funkcije 𝑓𝑓, sprejeta. Prav tako pa bodo občasno z verjetnostjo 𝑝𝑝 sprejeta tudi stanja, ki povečujejo vrednost objektivne funkcije. Verjetnost 𝑝𝑝 temelji na Boltzmannovi porazdeljenosti in jo podaja enačba (3.2) [2], [8], [10], [11].

𝑝𝑝=𝑒𝑒^{−𝛥𝛥𝑓𝑓}^𝑇𝑇 > 𝑟𝑟 (3.2)

Kjer je 𝑇𝑇 ponovno trenutna temperatura sistema in 𝛥𝛥𝑓𝑓 razlika objektivne funkcije. V enačbi (3.2) nastopa še naključno izbrana številka 𝑟𝑟, ki jo uporabljamo za mejo. Če je 𝑝𝑝> 𝑟𝑟, potem je poteza sprejeta. Pogosto je 𝑟𝑟 podana v intervalu [0 1] [2].

Generiranje nove rešitve in sprejemanje novega trenutnega stanja na podlagi verjetnosti sta koraka metode, ki se ponavljata v določenem številu iteracij oziroma dokler ni doseženo ravnotežnostno stanje. Pravkar opisana metoda SŽ se ponavlja periodično v vsaki iteraciji, začenši v trenutnem stanju (rešitvi), vendar pri vedno nižji temperaturi 𝑇𝑇 [11].

(38)

38 3.2.3 Urnik ohlajevanja

Z urnikom ohlajevanja določimo, kako hitro se bo naš sistem ohlajeval. Pri fizičnem žarjenju material ohlajujemo in mu znižujemo temperaturo, pri algoritmu pa je temperatura le kontrolni parameter. Pri algoritmu z urnikom ohlajevanja počasi znižujemo temperaturo sistema, kar posledično počasi znižuje verjetnost uporabe slabše rešitve za trenutno rešitev. Poznamo več različnih urnikov npr. logaritmični, hitri, geometrijski itd. [10], [11].

Pri Matlab GOPP-u imamo poleg možnosti, da sami definiramo urnik ohlajevanja, še druge tri možnosti.

Eksponentna temperatura

Eksponentna temperatura je privzeti ohlajevalni urnik pri programu Matlab. Opišemo ga z enačbo (3.3), kjer je 𝑘𝑘 žarilni parameter in 𝑇𝑇₀ začetna temperatura določene spremenljivke 𝑖𝑖 in 𝑇𝑇 trenutna temperatura sistema [1].

𝑇𝑇= 𝑇𝑇₀⋅0,95^𝑘𝑘 (3.3)

Hitra temperatura

Hitra temperatura je ohlajevalni urnik, ki je opisan z enačbo (3.4) [1].

𝑇𝑇=𝑇𝑇₀

𝑘𝑘 (3.4)

Boltz temperatura

Boltz temperatura je ohlajevalni urnik, ki je opisan z enačbo (3.5) [1].

𝑇𝑇= 𝑇𝑇₀

log(𝑘𝑘) (3.5)

Geometrijski urnik ohlajevanja

Geometrijski urnik ohlajevanja ni eden od ponujenih možnosti ohlajanja sistema v Matlab GOPP-u, vendar ga lahko sami definiramo, saj je zelo enostaven za uporabo in je v literaturi pogosto omenjen. Pri geometrijskem urniku ohlajevanja (enačba (3.6)), moramo trenutno temperaturo sistema pomnožiti z ohlajevalnim faktorjem α, za katerega trdimo, da je konstanten v intervalu [0,9 1). Če je vrednost ohlajevalnega faktorja visoka, potem se sistem počasneje ohlaja in je večja možnost, da dosežemo globalni optimum. Po drugi strani pa manjši ohlajevalni faktor pomeni hitrejše ohlajevanje in se optimizacija hitreje zaključi [10]–[12].

𝑇𝑇=𝛼𝛼 ⋅ 𝑇𝑇₀ (3.6)

(39)

39 3.2.4 Ponovno žarjenje

S tehniko ponovnega žarjenja sistemu ponovno zvišamo temperaturo in s tem poskrbimo, da se algoritem izogne lokalnemu optimumu. To se stori tako, da se žarilnemu parametru 𝑘𝑘 nastavi vrednost, ki je manjša od zaporedne številke trenutne iteracije. Žarilni parameter je odvisen od ocenjenega gradienta objektivne funkcije v vsaki dimenziji ter trenutni in začetni temperaturi določene spremenljivke 𝑖𝑖 [1].

Prav tako moramo definirati, po kolikšnem številu sprejetih novih točk naj se izvede ponovno žarjenje. Pri tem moramo paziti, da ne nastavimo intervala točk na premajhno vrednost, saj lahko s tem preprečimo iskalniku, da bi znal prepoznati optimum [1].

3.3 Konvergenca rezultatov

Z metodo SŽ bo konvergenca v globalni optimum dosežena, če bo pri vsaki temperaturi sistema dosežena stacionirana porazdeljenost, ki ji bo sledilo dovolj počasno ohlajanje. To na žalost pripelje do časovno zelo dolge optimizacije, zato se poslužujemo različnih pohitritev, kot je npr. že vnaprej določeno število iteracij in hitri urniki ohlajevanja [11].

Na tem mestu se poraja vprašanje, ali lahko dokažemo, da bodo rešitve s SŽ-algoritmom res konvergirale k optimalni rešitvi. Z določenimi poenostavitvami lahko SŽ-algoritem modeliramo kot Markovsko verigo [2] in za zastavljeni problem dokažemo konvergenco. Po navadi pri dokazovanju konvergence pridemo do zaključka, da SŽ-metoda konvergira ''asimptomatsko v verjetnosti''. To pomeni, da lahko dosežemo, da je verjetnost, da smo našli globalni minimum skoraj enaka 1, če opravimo dovolj veliko ponovitev (teoretično neskončno ponovitev) algoritma. Z drugimi besedami, SŽ je v temeljnem smislu dobro zasnovana metoda, vendar nimamo nobenega (matematičnega) jamstva, da bo naša rešitev konvergirala, ko bomo SŽ uporabili na resničnem problemu [10].

3.4 Prednosti in slabosti simuliranega žarjenja

3.4.1 Prednosti

Največja prednost SŽ-ja je možnost izogiba lokalnemu optimumu, medtem ko išče globalni optimum. V članku [9] so SŽ optimizacijo ponovili več kot 10-krat ter ugotovili, da algoritem nikoli ni nakazal začetka konvergence proti lokalnemu optimumu. Metodo se prav tako lahko uporablja za diskretne probleme oziroma za zvezne probleme, ki imajo singularne točke, saj te točke ne vplivajo na proces optimizacije. Trdimo lahko tudi, da algoritem ni zapleten in je enostaven za uporabo, saj za optimizacijo potrebuje le vrednost objektivne funkcije [12].

(40)

40 3.4.2 Slabosti

Težava SŽ-metode je njena počasnost. Razlog za to je njena iterativna narava iskanja rešitve, saj moramo izračunati veliko različnih konfiguracij pri zelo veliko različnih temperaturah, da najdemo pravilno (optimalno rešitev). Čeprav računalnik za vsako potezo ne porabi veliko časa, je treba narediti zelo veliko potez, tako da lahko optimizacija poteka tudi več ur oziroma dni pri zahtevnejših in daljših problemih [10].

Slabost SŽ-metode je tudi, da algoritem ni primeren za vse probleme. Primernost problema določimo glede na strukturo njegovega prostora rešitev (večdimenzionalna struktura hribov in dolin, kjer hrib predstavlja lokalni maksimum in dolina predstavlja lokalni minimum). Če je prostor sestavljen iz relativno malo hribov in dolin, ki se počasi zvišujejo/znižujejo, potem algoritem nima težav pri iskanju globalnega optimuma. Težave nastopijo pri prostorih z veliko hribi in dolinami, ki se močno razlikujejo po svoji višini/globini. Takrat obstaja možnost, da se zaradi postopnega zmanjševanja temperature sistema algoritem ne more dovolj hitro ''izkopati'' iz lokalnega minimuma, saj se z zmanjševanjem temperature manjša možnost potez ''navzgor v hrib'' in celoten algoritem obtiči v lokalnem optimumu [10].

(41)

41

4 Optimizacija z roji delcev

Naslednja metoda, ki jo bomo opisali, je optimizacija z roji delcev. Optimizacijo z roji delcev (ang. particle swarm optimization, kratica ORD) sta razvila ameriški psiholog James Kennedy in električni inženir Russell C. Eberhart leta 1995. Metoda uporablja enostaven mehanizem, ki oponaša obnašanje ptic in čebel v rojih, da bi delce pri raziskovanju vodila do globalno optimalne rešitve [2], [13].

Že od samega začetka je ORD-metoda požela ogromno zanimanja, na podlagi katerega so se kasneje razvile inačice prvotne metode, sedaj pa jih s skupnim imenom imenujemo inteligence roja. Kljub novim metodam velja ORD še vedno za najbolj pogosto uporabljeno metodo med vsemi inteligencami roja, predvsem zaradi svoje enostavnosti in prilagodljivosti na različne probleme [2].

Največ težav pri ORD povzroča prehitra konvergenca, ko se iskanje globalne rešitve zatakne v lokalnem optimumu [13].

4.1 Opis optimizacije z roji delcev

Metodo ORD lahko opišemo z analogijo letenja roja čebel po polju. Njihov cilj je najti lokacijo na polju, kjer so cvetlice posejane najgosteje. Na začetku čebele naključno preletavajo celotno polje pri naključnih hitrostih. Vsaka posamezna čebela si zapomni, na katerem mestu polja je videla, da so cvetlice tam gosto posejane, ter ve, na kateri lokaciji so ostale čebele videle gosto posejane cvetlice. Čebela je sedaj razdvojena med tem, da bi se vrnila na lokacijo, kjer je sama našla največ cvetlic ali bi šla raziskovati območje, kjer so ostale čebele našle cvetlice.

Ambivalentna čebela pospešuje v obe smeri, na velikost pospeševanja v posamezno smer pa vplivata nostalgija in socialni pritisk ostalih čebel. Na svoji poti lahko čebela najde novo lokacijo, kjer so še gosteje posejane cvetlice in jo nato ''privlači'' ta lokacija. Lahko se celo zgodi, da ima ta lokacija najgosteje posejane cvetlice, kar so jih do sedaj našle vse čebele, zato roj začne leteti proti tej lokaciji. Sčasoma bo celoten roj letel okoli te lokacije (točke), saj so bile tam najdene najgosteje posejane cvetlice na celotnem polju [14].

ORD-algoritem rešuje zastavljeni problem tako, da raziskuje prostor rešitev dane objektive funkcije s spreminjanjem oziroma prilagajanjem smeri posameznih delcev. Delec predstavlja potencialno rešitev zastavljenega optimizacijskega problema. Premikanje rojnega delca je sestavljeno iz dveh komponent: stohastične (naključne) in deterministične (določene) komponente. Vsak posamezni delec se premika v smeri globalno najboljše lokacije 𝒈𝒈^∗ ter v smeri njegove najboljše lokacije 𝒙𝒙_𝑖𝑖^∗. Prav tako ima vsak delec težnjo po naključnem premikanju.

Na sliki 6 je shematično prikazano premikanja delca pri ORD. Ko delec najde lokacijo, ki je boljša od vseh prejšnjih, posodobi svojo najboljšo lokacijo na pravkar najdeno (trenutno). Vsak delec 𝑖𝑖 ima svojo najboljšo lokacijo v vsakem trenutku (iteraciji) 𝑡𝑡. Cilj metode ORD je najti