(Simulated annealing, SA)
Simulirano kaljenje je S-metaheuristika zasnovana na lokalnom pretraživanju koja dozvoljava posećivanje lošijih rešenja u cilju nalaženja globalnog optimuma. Inspirisana je procesom kaljenja čelika. Metoda započinje izborom početnog rešenja (na slučajan način ili nekom heuristikom) i postavljanjem parametra koji predstavlja temperaturu na relativno visoku vrednost $T_0$. U svakoj iteraciji na slučajan način se bira sused $x_0$ iz (unapred određene) okoline tekućeg rešenja $x$. Ako je izabrano rešenje $x_0$ bolje od $x$ (u pogledu vrednosti funkcije cilja), ono postaje tekuće i nastavlja se sa pretraživanjem njegove okoline. Ukoliko je lošije od tekućeg, $x_0$ se prihvata sa određenom verovatnoćom. Verovatnoća prihvatanja lošijeg rešenja obično zavisi od temperature, kao i stepena degradacije lošijeg rešenja, i opada sa povećanjem broja iteracija algoritma. Pri kraju izvrsavanja verovatnoća prihvatanja lošijeg resenja je minimalna, tj. vrlo verovatno se neće prihavtiti lošije rešenje jer se smatra da je već dostignut određen kvalitet rešenja i na ovaj način se izbegava moguće pogoršavanje tekućeg rešenja. Jedan od mogućih načina definisanja verovatnoće je:
$$ p(T)=e^{-\delta/T},\ \delta=f(x')-f(x) $$
Za svaku vrednost temperature, izvršava se nekoliko iteracija u kojima se na slučajan način bira novo rešenje iz okoline tekućeg sa ciljem stabilizovanja rešenja na trenutnoj temperaturi. Potom se, nakon određenog broja iteracija vrši snižavanje temperature, čime se smanjuje verovatnoća prihvatanja lošijeg rešenja kako pretraga napreduje. Pri veoma niskoj temperaturi algoritam teži lokalnom pretraživanju.
%Generisanje inicijalnog resenja, postavljanje parametara, definisanje okoline
x=x_0;
T=T0; %postavljanje inicijalne temperature
while T>Tf %dok je temperatura veca od minimalne
for i=1:iter %iter - broj iteracija na istoj termperaturi
x'= generisi_nasumicno_resenje_u_okolini_tekuceg(x);
delta = f(x')-f(x);
if delta<=0 %nasli smo bolje resenje
x=x';
else
resenje x' prihvatamo za tekuce sa verovatnocom p(T);
end
end
T=T*v; %snizavanje temperature (hladjenje)
end
(Tabu search, TS)
Tabu pretraživanje je S-metaheuristika zasnovana na lokalnom pretraživanju koja koristi memoriju procesa pretrage u cilju izbegavanja zamke lokalnog optimuma. Kratkoročna memorija procesa pretrage u kojoj se skladište informacije o lokalnim optimumima, ili o potezima koji vode u nedavno posećene lokalne optimume, naziva se tabu lista. Dužina tabu liste je ključni parametar ove metaheuristike i najčešće je konstantne dužine.
Osnovna varijanta tabu pretraživanja započinje generisanjem početnog rešenja i lokalnom pretragom u njegovoj okolini. Po završetku lokalne pretrage, pronađeni lokalni optimum se ubacuje u tabu listu i u određenom broju narednih iteracija biva isključen iz okoline. U međuvremenu se nastavlja sa lokalnim pretraživanjem tako modifikovane okoline i daljim kreiranjem tabu liste. Svaki element tabu liste se nakon određenog broja iteracija (tzv. tabu vreme) oslobađa iz tabu liste i ponovo uključuje u proces pretrage.
%Citanje podataka i postavljanje parametara
x=x0 %generisanje inicijalnog resenja
x_best=x;
TL={}; %prazna tabu lista
while nije_ispunjen_kriterijum_zaustavljanja
x'= naci_najbolje_resenje_u_okolini_tekuceg(x,TL); %x' ne pripada tabu listi
if f(x') < f(x_best)
x_best=x';
end
TL=TL U x';
if (|TL| > r) %nakon r iteracija resenja se brisu iz tabu liste
TL=TL \\ x_r;
end
x=x'; %prihavtamo i losija resenja
end
%Funkcija vraca x_best i f_best
Kako bi se smanjili memorijski zahtevi TS algoritma, često se umesto čuvanja celokupnog rešenja čuvaju potezi koji dovode do zabranjenih rešenja. Međutim, koristeći ovaj pristup kreiranja tabu liste, dešava se da budu zabranjena sva rešenja koja imaju istu osobinu kao i ono rešenje koje je zaista zabranjeno, čime se onemogućava pretraživanje čitavog prostora.
Takođe, loš izbor dužine tabu liste može dovesti do pojačane diverzifikacije (predugačka tabu lista) i pojave ciklusa (suviše mala tabu lista). Neki od načina prevazilaženja ovih problema su korišćenje tabu liste promenljive dužine i uvođenje aspiracijske funkcije kojom se proverava prag značajnosti nekog rešenja. Najčešće korišćen aspiracijski kriterijum ukida tabu status onih poteza koji vode do rešenja koja imaju bolju vrednost funkcije cilja od vrednosti funkcije cilja najboljeg posećenog rešenja. Još jedan nedostatak TS metode je i veliki broj parametara koje treba adekvatno izabrati.
U cilju povećanja stepena intenzifikacije, odnosno diverzifikacije pretrage, razvijene su varijante TS metode koje koriste srednjeročnu, odnosno dugoročnu, memoriju procesa pretrage. Srednjeročne memorije čuvaju elemente dobrih rešenja posećenih u nekoliko prethodnih iteracija, što utiče na intenzivnije pretraživanje onih delova prostora u kojima se očekuju dobra rešenja. Sa druge strane, dugoročne memorije pamte informacije o elementima tekućeg rešenja tokom cele pretrage čime se omogućava diverzifikacija pretrage.
Prva razlika je što TS koristi memorijske strukture u procesu pretraživanja, sto je odsutno kod SA metode. Pored toga, SA metoda u svakoj iteraciji nasumično bira rešenje iz okoline tekućeg rešenja i na njega se primenjuje unapred denisani kriterijum prihvatanja koji odlučuje da li će se potez izvršiti ili ne, dok TS pretražuje celu okolinu (ili veći deo) da bi identifikovao rešenja visokog kvaliteta. Budući da SA lako nalazi kvalitetne delove pretraživačkog prostora, često se koristi hibridizacija u kojoj SA generiše početno rešenje TS metode. Još jedan nedostatak TS metode je taj što može doći do pojave ciklusa (kada je dužina ciklusa veća od dužine tabu liste). U takvim situacijama deterministicka priroda TS metode otežava izlazak iz ciklusa. Ovaj nedostatak se meže rešiti odgovarajućom hibridizacijom sa SA metodom budući da stohastička karakteristika simuliranog kaljenja da slucajno bira rešenje sprečava pojavu ciklusa u pretrazi.
(Capacitated Vehicle Routing Problem - CVRP)