Algoritmiskā pasaule ir skaista ar daudzveidīgām stratēģijām un rīkiem, kas tiek izstrādāti visu diennakti, lai nodrošinātu vajadzību pēc augstas veiktspējas skaitļošanas. Faktiski, kad algoritmus iedvesmo dabas likumi, tiek novēroti interesanti rezultāti. Evolūcijas algoritmi pieder pie šādas algoritmu klases. Šie algoritmi ir izstrādāti tā, lai atdarinātu noteiktu uzvedību, kā arī cilvēka genoma evolūcijas iezīmes. Turklāt šāds algoritmiskais dizains ir ne tikai ierobežots cilvēkiem, bet arī to var iedvesmot dažu dzīvnieku dabiskā uzvedība. Šādu metodoloģiju izstrādes pamatmērķis ir nodrošināt reālistiskus, atbilstošus un tomēr dažus zemu izmaksu risinājumus problēmām, kuras līdz šim nav atrisināmas ar tradicionāliem līdzekļiem.
Tādējādi, pamatojoties uz šādiem evolūcijas algoritmiem, ir attīstījušās dažādas optimizācijas metodes un tādējādi pavērušas metaheiristikas jomu. Metaheiristisks ir atvasināts no diviem grieķu vārdiem, proti, Meta nozīmē vienu līmeni augstāk un heuriskein nozīmē atrast . Tādi algoritmi kā daļiņu spieta optimizācija (PSO) un skudru kolonijas optimizācija (ACO) ir spieta izlūkošanas un metaheiristikas piemēri. Baru izlūkošanas mērķis ir izstrādāt viedas daudzu aģentu sistēmas, iedvesmojoties no tādu sociālo kukaiņu kā skudru, termītu, bišu, lapseņu un citu dzīvnieku sabiedrību, piemēram, putnu vai zivju baru, kolektīvās uzvedības.
Fons:
Skudru kolonijas optimizācijas tehnika ir tikai iedvesmota no barības meklējumi skudru koloniju uzvedība, ko pirmo reizi ieviesa Marko Dorigo deviņdesmitajos gados. Skudras ir eusociāli kukaiņi, kas dod priekšroku kopienas izdzīvošanai un uzturēšanai, nevis kā atsevišķas sugas. Viņi sazinās savā starpā, izmantojot skaņu, pieskārienu un feromonus. Feromoni ir organiski ķīmiski savienojumi, ko izdala skudras un kas izraisa sociālo reakciju vienas sugas pārstāvjiem. Tās ir ķīmiskas vielas, kas spēj darboties kā hormoni ārpus sekrēcijas indivīda ķermeņa, lai ietekmētu saņēmēju indivīdu uzvedību. Tā kā lielākā daļa skudru dzīvo uz zemes, tās izmanto augsnes virsmu, lai atstātu feromonu pēdas, kurām var sekot (smaržot) citas skudras.
Skudras dzīvo kopienas ligzdās, un ACO pamatprincips ir novērot skudru pārvietošanos no ligzdām, lai pēc iespējas īsākā ceļā meklētu barību. Sākotnēji skudras sāk nejauši pārvietoties, meklējot barību ap savām ligzdām. Šī nejaušā meklēšana paver vairākus ceļus no ligzdas uz barības avotu. Tagad, pamatojoties uz barības kvalitāti un kvantitāti, skudras atgriežas atpakaļ ar nepieciešamo feromonu koncentrāciju. Atkarībā no šiem feromonu izmēģinājumiem, varbūtība, ka šādas skudras izvēlēsies konkrētu ceļu, būtu noteicošais faktors pārtikas avotam. Acīmredzot šī varbūtība ir balstīta uz feromona koncentrāciju, kā arī iztvaikošanas ātrumu. Var arī novērot, ka, tā kā feromonu iztvaikošanas ātrums ir arī noteicošais faktors, katra ceļa garumu var viegli aprēķināt.
Iepriekš redzamajā attēlā vienkāršības labad ir apsvērti tikai divi iespējamie ceļi starp barības avotu un skudru ligzdu. Šos posmus var analizēt šādi:
string.substring java
- 1. posms: visas skudras atrodas savā ligzdā. Apkārtējā vidē nav feromonu satura. (Algoritmiskajā projektēšanā var ņemt vērā atlikušo feromonu daudzumu, neiejaucoties varbūtībā.) 2. posms: skudras sāk meklēšanu ar vienādu (katra 0,5) varbūtību katrā ceļā. Skaidrs, ka izliektais ceļš ir garāks, un tāpēc laiks, kas skudrām nepieciešams, lai sasniegtu barības avotu, ir ilgāks nekā otram. 3. posms: skudras pa īsāko ceļu sasniedz barības avotu agrāk. Tagad acīmredzot viņi saskaras ar līdzīgu atlases dilemmu, taču šoreiz feromonu takas dēļ pa jau pieejamo īsāko ceļu atlases iespējamība ir lielāka. 4. posms: vairāk skudru atgriežas pa īsāku ceļu, un pēc tam palielinās arī feromonu koncentrācija. Turklāt iztvaikošanas dēļ feromonu koncentrācija garākajā ceļā samazinās, samazinot šī ceļa izvēles iespējamību turpmākajos posmos. Tāpēc visa kolonija pakāpeniski izmanto īsāko ceļu ar lielākām varbūtībām. Tātad ceļa optimizācija ir sasniegta.
Algoritmiskais dizains:
Saistībā ar iepriekš minēto skudru uzvedību tagad var izstrādāt algoritmisku dizainu. Vienkāršības labad ir apsvērts viens barības avots un viena skudru kolonija ar tikai diviem iespējamiem šķērsošanas ceļiem. Visu scenāriju var realizēt, izmantojot svērtos grafikus, kur skudru kolonija un barības avots darbojas kā virsotnes (vai mezgli); ceļi kalpo kā malas, un feromonu vērtības ir svari, kas saistīti ar malām.
Lai grafiks ir G = (V, E) kur V, E ir grafa malas un virsotnes. Virsotnes saskaņā ar mūsu apsvērumiem ir INs (Avota virsotne – skudru kolonija) un INd (Galamērķa virsotne — pārtikas avots), abas malas ir UN1 un UN2 ar garumiem L1 un L2 piešķirts katram. Tagad var pieņemt, ka saistītās feromonu vērtības (kas liecina par to stiprumu) ir R1 un R2 virsotnēm E1un E2attiecīgi. Tādējādi katrai skudrai ceļa izvēles sākuma varbūtība (starp E1un E2) var izteikt šādi:
python rstrip
Acīmredzot, ja R1> R2, varbūtība izvēlēties E1ir augstāks un otrādi. Tagad, atgriežoties pa šo īsāko ceļu, sakiet Ei, feromona vērtība tiek atjaunināta attiecīgajam ceļam. Atjaunināšana tiek veikta, pamatojoties uz ceļu garumu, kā arī feromonu iztvaikošanas ātrumu. Tātad atjauninājumu var pakāpeniski realizēt šādi:
- Atbilstoši ceļa garumam -
Iepriekš minētajā atjauninājumā i = 1, 2 un 'K' kalpo kā modeļa parametrs. Turklāt atjauninājums ir atkarīgs no ceļa garuma. Jo īsāks ceļš, jo augstāks pievienotais feromons. Saskaņā ar feromonu iztvaikošanas ātrumu -
Parametrs “v” pieder intervālam (0, 1), kas regulē feromonu iztvaikošanu. Turklāt i = 1, 2.
Katrā iterācijā visas skudras tiek novietotas avota virsotnē Vs(skudru kolonija). Pēc tam skudras pārvietojas no Vsuz Vd(pārtikas avots) pēc 1. darbības. Pēc tam visas skudras veic atpakaļceļu un pastiprina izvēlēto ceļu, pamatojoties uz 2. darbību.
Pseidokods:
Procedure AntColonyOptimization: Initialize necessary parameters and pheromone trials; while not termination do : Generate ant population; Calculate fitness values associated with each ant; Find best solution through selection methods; Update pheromone trial; end while end procedure>
Feromonu atjauninājumu un piemērotības aprēķinus iepriekš minētajā pseidokodā var atrast, izmantojot iepriekš minētās pakāpeniskas ieviešanas.
Tādējādi ir izveidota ACO optimizācijas tehnikas ieviešana. ACO pielietojumu var attiecināt uz dažādām problēmām, piemēram, slavenajām TSP (ceļojošā pārdevēja problēma) .
Atsauces:
https://www.ics.uci.edu/~welling/teaching/271fall09/antcolonyopt.pdf