Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
Rozdział1.Algorytmyoptymalizacji–wybranezagadnienia
17
Metaheurystykistanowiąmetodęobliczeniową,łączącwsposóbabstrak-
cyjnyfunkcjecelu(funkcjeoceniająceprzydatnośćelementu)lubheurystyki.
Połączenietojestczęstowykonywaneprzezwykorzystaniestatystykipróbek
zprzestrzeniprzeszukiwańlubnapodstawiemodelupewnegonaturalnego
zjawiskalubprocesufizycznego.Przeznaczonesąonedorozwiązywaniaogól-
nejklasyproblemówiniegwarantująznalezieniarozwiązaniaorazniemożna
przewidywaćczasuichdziałania.
Naobserwacjinaturybazująalgorytmy,którychinspiracjąstałasięin-
teligencjaroju.Naśladująonezachowaniazwierzątiptaków.Dotejklasy
algorytmównależąmiędzyinnymialgorytmy:mrówkowe(ACOAntColony
Optimization),pszczele(BABeeAlgorithms)irojucząstek(PSOParticle
SwarmOptimization).
AlgorytmPSOjestmetodąobliczeniowąbazującąnapewnymzbiorze
rozwiązań,któraoptymalizujeproblemprzeziteracyjnedoskonaleniekandy-
datównarozwiązaniewodniesieniudodanegośrodka.
Pionierskimiopracowaniamidotyczącymioptymalizacjirojemcząstekby-
cyjnych,takichjakalgorytmygenetyczne–jednakwprzeciwieństwiedonich,
PSOniemaoperatorówewolucyjnych(krzyżowaniaimutacji).Metaheury-
styki,takiejakPSOniegwarantująznalezieniaoptymalnegorozwiązania.
Algorytmtenmożebyćstosowanydorozwiązaniaproblemówoptymalizacji
dyskretnej[126].
Algorytmyewolucyjnenaśladująnaturalnąewolucjęitraktująkandyda-
tówrozwiązaniajakoosobniki,którekonkurująwśrodowiskuwirtualnym.Są
oneszczególnymprzypadkiemalgorytmówstochastycznych.Algorytmyewo-
lucyjnestanowiąniejakometaforęorganizmówbiologicznych,zapożyczając
odnichterminologięimechanizmydziałania.Algorytmytewkażdejitera-
cjizwanejpokoleniemprzetwarzająpopulacjęreprezentującąpróbęlosową
należącądodziedzinyrozwiązań,czyliśrodowiska.Populacjajestzbiorem
osobnikówprzetwarzanychwkażdejiteracji.Stopieńprzydatnościosobników
zostajepoddanyweryfikacjiśrodowiskazasprawątzw.funkcjiprzystosowania
(wzadaniuoptymalizacyjnymzwanejfunkcjącelulubfunkcjąkosztów).
Walgorytmachewolucyjnychorozkładzieosobnikówwśrodowiskudecy-
dująmechanizmyadaptacjizapożyczonezbiologii.Należądonichoperatory
genetyczne,takiejak:mutacja,krzyżowanieorazselekcja.Operatorytereali-
zująfunkcjeodpowiedzialnezaeksploracjęśrodowiskaorazeksploatacjęob-
szarówekstremówlokalnych.Osobnikopisanyjestgenotypem,składającym
sięzchromosomówimającymswojąreprezentacjęwfenotypie,ocenianym
przezfunkcjęprzystosowania,któramożezawieraćelementyskalowaniaczy
teżkary.Mechanizmyadaptacjiczyniątealgorytmybardziejefektywnyminiż
całkowicieprzypadkoweprzeszukiwanieprzestrzenirozwiązań.
Opróczmetodinspirowanychnaturąewolucji,istniejąrównieżmetody,
którenaśladująprocesyfizyczne,takiejaksymulowanewyżarzanie(Simu-
