(Bee colony optimization, BCO)
BCO (Bee Colony Optimization) je populaciona metaheuristika inspirisana ponašanjem pčela pri traženju hrane. Prvi korak BCO metode sastoji se od inicijalizacije kolonije veštačkih pčela, pri čemu svaka pčela predstavlja jedno dopustivo (kandidat) rešenje. Nakon inicijalizacije, algoritam se odvija kroz glavnu petlju u kojoj se naizmenično smenjuju dve osnovne faze: let unapred (forward pass) i let unazad (backward pass). Ove faze omogućavaju interakciju između pčela i razmenu informacija unutar roja.
Osnovna varijanta BCO metode je konstruktivnog tipa, što znači da se rešenje postepeno izgrađuje tokom faze leta unapred. Neka je $B$ broj veštačkih pčela, a $NC$ broj koraka (interakcija) u toku jedne iteracije algoritma. U svakom koraku $u$, gde je $u$=1,…,$NC$ svaka pčela $b = 1, \dots, B$ razmatra skup mogućih poteza i bira naredni potez primenom pravila ruletske selekcije. Na taj način, potezi koji vode ka kvalitetnijim rešenjima imaju veću verovatnoću izbora.
Nakon završetka leta unapred, u fazi leta unazad vrši se evaluacija konstruisanih rešenja. Na osnovu kvaliteta rešenja, svaka pčela donosi odluku da li će ostati lojalna svom rešenju, čime dobija ulogu regrutera, ili će ga odbaciti i postati neopredeljena pčela.
Verovatnoća sa kojom pčela $b$ ostaje lojalna svom rešenju nakon $u$-tog koraka određuje se funkcijom koja zavisi od kvaliteta njenog rešenja i trenutne faze pretrage, i najčešće se računa kao:
$$ p_b^{u+1}=e^{-\frac{O_{max}-O_b}{u}} $$
Na ovaj način, rešenja boljeg kvaliteta (sa većim vrednostima $O_b$) imaju veću verovatnoću da budu zadržana, dok se lošija rešenja češće odbacuju. Takođe, kako broj koraka $u$ raste, uticaj razlike u kvalitetu rešenja postaje izraženiji, čime se pretraga postepeno usmerava ka eksploataciji kvalitetnijih rešenja.
Ukoliko se rešava problem minimizacije, normalizovana vrednost funkcije cilja definiše se na sledeći način:
$$ O_b=\frac{C_{max}- C_b}{C_{max}-C_{min}}, b=1,...,B. $$
Za problem maksimizacije, koristimo formulu:
$$ O_b=\frac{C_{b}- C_{min}}{C_{max}-C_{min}}, b=1,...,B. $$
$C_b$ - vrednost funkcije cilja rešenja koje je određeno pčelom $b$,
$C_{min}/C_{max}$ - minimalna i maksimalna vrednost funkcije cilja u čitavom roju.
Dakle, bolja rešenja imaju veću normalizovanu vrednost funkcije cilja, pa je samim tim veća i verovatnoća da će pčela ostati lojalna takvom rešenju. Kako proces pretrage napreduje, kriterijum selekcije postaje sve izraženiji, odnosno verovatnoća odbacivanja lošijih rešenja se povećava. Pčele koje ostanu lojalne svojim rešenjima postaju regruteri. Neka je $R$ broj pčela koje su dobile status regrutera. Svaka neopredeljena pčela bira jedno od rešenja regrutera primenom pravila ruletske selekcije, pri čemu je verovatnoća izbora rešenja pčele $b$ data izrazom:
$$ p_b=\frac{O_b}{\sum_{k=1}^{R}O_k}, $$
tj. kvalitetnija rešenja imaju veću verovatnoću da budu izabrana.
Nakon izvršenih $NC$ koraka (letova unapred i unazad), vrši se ažuriranje najboljeg pronađenog rešenja, a zatim se opisani postupak ponavlja sve dok se ne ispuni zadati kriterijum zaustavljanja.