Algoritminis pasaulis yra gražus, nes įvairios strategijos ir įrankiai kuriami visą parą, kad būtų patenkintas didelio našumo skaičiavimas. Tiesą sakant, kai algoritmai yra įkvėpti gamtos dėsnių, pastebimi įdomūs rezultatai. Tokiai algoritmų klasei priklauso evoliuciniai algoritmai. Šie algoritmai sukurti taip, kad imituotų tam tikrą elgesį ir evoliucinius žmogaus genomo bruožus. Be to, toks algoritminis dizainas yra ne tik suvaržytas žmonėms, bet ir gali būti įkvėptas natūralaus tam tikrų gyvūnų elgesio. Pagrindinis tokių metodikų kūrimo tikslas yra pateikti realistiškus, aktualius ir vis dėlto nebrangius problemų, kurių iki šiol nebuvo galima išspręsti įprastomis priemonėmis, sprendimus.
Taigi, remiantis tokiais evoliuciniais algoritmais, išsivystė skirtingi optimizavimo metodai ir taip atvėrė metaeuristikos sritį. Metaheuristinis yra kilęs iš dviejų graikiškų žodžių, būtent Meta prasmė vienu lygiu aukščiau ir heuriskein prasmė rasti . Algoritmai, tokie kaip dalelių spiečiaus optimizavimas (PSO) ir skruzdžių kolonijų optimizavimas (ACO), yra spiečiaus intelekto ir metaeuristikos pavyzdžiai. Spiečiaus intelekto tikslas – sukurti intelektualias kelių agentų sistemas, įkvėpus kolektyvinio socialinių vabzdžių, tokių kaip skruzdėlės, termitai, bitės, vapsvos, ir kitų gyvūnų bendruomenių, tokių kaip paukščių pulkai ar žuvų būriai, elgesio.
Fonas:
Skruzdžių kolonijos optimizavimo technika yra tik įkvėpta maisto ieškojimas skruzdžių kolonijų elgseną, pirmą kartą pristatė Marco Dorigo 1990 m. Skruzdėlės yra eusocialūs vabzdžiai, kurie teikia pirmenybę bendruomenės išlikimui ir palaikymui, o ne kaip atskiroms rūšims. Jie bendrauja tarpusavyje naudodami garsą, prisilietimą ir feromonus. Feromonai yra skruzdėlių išskiriami organiniai cheminiai junginiai, kurie sukelia socialinį atsaką tos pačios rūšies atstovams. Tai cheminės medžiagos, galinčios veikti kaip hormonai už išskiriančio individo kūno ribų, kad paveiktų priimančio asmens elgesį. Kadangi dauguma skruzdžių gyvena ant žemės, jos naudoja dirvos paviršių, kad paliktų feromonų pėdsakus, kuriuos gali sekti (užuostyti) kitos skruzdėlės.
Skruzdėlės gyvena bendruomenės lizduose, o pagrindinis ACO principas yra stebėti skruzdėlių judėjimą iš savo lizdų, kad būtų galima ieškoti maisto kuo trumpesniu keliu. Iš pradžių skruzdėlės pradeda atsitiktinai judėti, ieškodamos maisto aplink savo lizdus. Ši atsitiktinė paieška atveria kelis maršrutus nuo lizdo iki maisto šaltinio. Dabar, atsižvelgiant į maisto kokybę ir kiekį, skruzdėlės neša dalį maisto atgal su reikiama feromonų koncentracija. Atsižvelgiant į šiuos feromonų tyrimus, tikimybė, kad šios skruzdėlės pasirinks konkretų kelią, būtų pagrindinis veiksnys nustatant maisto šaltinį. Akivaizdu, kad ši tikimybė yra pagrįsta feromono koncentracija ir garavimo greičiu. Taip pat galima pastebėti, kad kadangi feromonų išgaravimo greitis taip pat yra lemiamas veiksnys, kiekvieno kelio ilgį galima lengvai apskaičiuoti.
Aukščiau pateiktame paveikslėlyje, siekiant paprastumo, buvo apsvarstyti tik du galimi keliai tarp maisto šaltinio ir skruzdžių lizdo. Etapas galima analizuoti taip:
- 1 etapas: visos skruzdėlės yra savo lizde. Aplinkoje nėra feromonų. (Algoritminiam projektavimui galima atsižvelgti į likutinį feromonų kiekį, netrukdant tikimybei) 2 etapas: skruzdėlės pradeda ieškoti vienoda (po 0,5) tikimybe kiekviename kelyje. Akivaizdu, kad lenktas kelias yra ilgesnis, todėl laikas, per kurį skruzdėlės pasiekia maisto šaltinį, yra ilgesnis nei kitų. 3 etapas: skruzdėlės trumpesniu keliu anksčiau pasiekia maisto šaltinį. Akivaizdu, kad dabar jie susiduria su panašia atrankos dilema, tačiau šį kartą dėl jau turimo feromonų tako trumpesniu keliu atrankos tikimybė yra didesnė. 4 etapas: daugiau skruzdėlių grįžta trumpesniu keliu, o vėliau feromonų koncentracija taip pat didėja. Be to, dėl garavimo sumažėja feromonų koncentracija ilgesniame kelyje, todėl mažėja šio kelio pasirinkimo tikimybė tolimesniuose etapuose. Todėl visa kolonija palaipsniui naudojasi trumpesniu keliu su didesnėmis tikimybėmis. Taigi, kelio optimizavimas pasiektas.
Algoritminis dizainas:
Atsižvelgiant į minėtą skruzdėlių elgesį, dabar galima sukurti algoritminį dizainą. Paprastumo dėlei buvo svarstoma apie vieną maisto šaltinį ir vieną skruzdžių koloniją, turinčią tik du galimus kelius. Visas scenarijus gali būti įgyvendintas naudojant svertinius grafikus, kur skruzdžių kolonija ir maisto šaltinis veikia kaip viršūnės (arba mazgai); takai tarnauja kaip briaunos, o feromonų reikšmės yra su kraštais susiję svoriai.
Tegul grafikas būna G = (V, E) kur V, E yra grafo briaunos ir viršūnės. Mūsų nuomone, viršūnės yra INs (Šaltinio viršūnė – skruzdžių kolonija) ir INd (Paskirties viršūnė – maisto šaltinis), du kraštai yra IR1 ir IR2 su ilgiais L1 ir L2 priskirtas kiekvienam. Dabar galima daryti prielaidą, kad susijusios feromonų vertės (nurodančios jų stiprumą) yra R1 ir R2 viršūnėms E1ir E2atitinkamai. Taigi kiekvienos skruzdėlės pradinė kelio pasirinkimo tikimybė (tarp E1ir E2) gali būti išreikštas taip:
Akivaizdu, kad jei R1>R2, tikimybė pasirinkti E1yra aukštesnis ir atvirkščiai. Dabar, grįždamas šiuo trumpiausiu keliu, pasakykite Ei, atnaujinama atitinkamo kelio feromonų reikšmė. Atnaujinimas atliekamas atsižvelgiant į takų ilgį ir feromonų garavimo greitį. Taigi, atnaujinimas gali būti vykdomas laipsniškai taip:
- Pagal kelio ilgį -
Aukščiau pateiktame atnaujinime i = 1, 2 ir „K“ yra modelio parametras. Be to, atnaujinimas priklauso nuo kelio ilgio. Kuo trumpesnis kelias, tuo didesnis pridedamas feromonas. Pagal feromonų išgaravimo greitį –
Parametras „v“ priklauso intervalui (0, 1), kuris reguliuoja feromonų garavimą. Be to, i = 1, 2.
Kiekvienos iteracijos metu visos skruzdėlės yra V šaltinio viršūnėjes(skruzdžių kolonija). Vėliau skruzdėlės pajuda iš Vspas Vd(maisto šaltinis) atlikdami 1 veiksmą. Tada visos skruzdėlės grįžta atgal ir sustiprina pasirinktą kelią pagal 2 veiksmą.
Pseudokodas:
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>
Feromonų atnaujinimą ir tinkamumo skaičiavimus aukščiau esančiame pseudokode galima rasti naudojant aukščiau paminėtus laipsniškus diegimus.
Taigi buvo įdiegta ACO optimizavimo technika. ACO taikymas gali būti išplėstas įvairioms problemoms, tokioms kaip garsiosios TSP (keliaujančio pardavėjo problema) .
Nuorodos:
https://www.ics.uci.edu/~welling/teaching/271fall09/antcolonyopt.pdf