(Variable Neighborhood Search, VNS)
Metoda promenljivih okolina predstavlja jednu od najefikasnijih metaheurističkih metoda baziranih na lokalnom pretraživanju. Osnovna ideja VNS-a je sistematska promena unapred definisanih okolina čime se izbegava zaglavljivanje pretrage u lokalnom optimumu. Metoda promenljivih okolina se oslanja na tri jednostavne činjenice:
VNS je nastao prilikom rešavanja problema kombinatorne optimizacije, ali se vrlo brzo njegova primena proširila i na probleme kontinualne optimizacije. Razvijene su različite determinističke, stohastičke i kombinovane varijante VNS metode koje se danas uspešno koriste za rešavanje različitih problema optimizacije. U nastavku su navedene karakteristike najčešće korišćenih varijanti VNS-a.
(Variable Neighborhood Descent, VND)
VND je deterministička varijanta VNS-a. Imajući u vidu činjenicu da lokalni optimum u odnosu na jednu okolinu ne mora biti lokalni optimum u odnosu na neku drugu, cilj VND metode je naći rešenje koje će biti lokalni optimum u odnosu na sve okoline iz unapred definisanog skupa okolina. Faza inicijalizacije VND metode sastoji se iz adekvatnog odabira okolina $N_k,\ k=1,...,k_{max}$ i generisanja početnog rešenja koje postaje tekuće rešenje $x^$. U svakoj VND iteraciji, nalazi se najbolji sused iz $N_k$ okoline tekućeg rešenja $x^$. Ukoliko pretraga trenutne okoline tekućeg rešenja ne dovede do poboljšanja (u odnosu na vrednost funkcije cilja), algoritam nastavlja sa pretraživanjem $N_{k+1}$ okoline nepromenjenog tekućeg rešenja $x^$. U suprotnom, pronađeno bolje rešenje $x''$ postaje tekuće $(x^ = x'')$ i pretraživanje se nastavlja u okolini $N_1$ tekućeg rešenja. Algoritam se završava ukoliko se ne naiđe na poboljšanje nakon pretraživanja svih okolina tekućeg rešenja.
%VND
%Inicijalizacija: odabir okolina N_k, k=1,...,k_max i ostalih parametara
x*=genrisi_pocetno_resenje(ulazni_podaci);
k=1;
while k<=k_max
x'=naci_najbolje_resenje_u_N_k(x*,k);
if f(x')<f(x*)
x*=x'; %azuriramo tekuce resenje
k=1; %pretragu nastavljamo u okolini N_1
else
k=k+1; %pretrazujemo narednu okolinu nepromenjenog tekuceg resenja
end
(Reduced Variable Neighborhood Search, RVNS)
RVNS je stohastička varijanta VNS-a. RVNS metodu karakteriše odsustvo lokalnog pretraživanja i slučajan odabir rešenja iz trenutne okoline tekućeg rešenja. Budući da je pretraživanje čitave okoline tekućeg rešenja vremenski najzahtevniji korak, njegovim izbacivanjem se dobija na vremenu, ali gubi na kvalitetu dobijenog rešenja. U fazi inicijalizacije RVNS metode vrši se odabir okolina $N_k,\ k=1,...,k_{max},$generiše se početno rešenje koje postaje tekuće rešenje $x^$ i $k$ se postavlja na 1. Potom se, u svakoj iteraciji, na slučajan način bira tačka $x'\in N_k(x^)$. Ukoliko je rešenje $x'$ bolje od tekućeg rešenja, ono postaje tekuće $(x^=x')$ i pretraživanje se nastavlja u okolini $N_1(x^)$. U suprotnom, proces pretrage se nastavlja u narednoj okolini nepromenjenog tekućeg rešenja. Kada $k$ postane veće od $k_{max}$, njegova vrednost se postavlja na $1$ i opisani postupak se ponavlja do zadovoljenja kriterijuma zaustavljanja. Mogu se koristiti različiti kriterijumi zaustavljanja: maksimalan broj iteracija, maksimalan broj iteracija izmedu dva poboljšanja, maksimalno vreme izvršavanja itd. Mala modifikacija RVNS metode, kojom se povećavaju šanse odabira boljeg rešenja u svakoj iteraciji, sastoji se u slučajnom odabiru $m$ rešenja iz okoline tekućeg rešenja od kojih se bira ono sa najboljom vrednošću funkcije cilja.
%RVNS
%Inicijalizacija: odabir okolina N_k, k=1,...,k_max i ostalih parametara
x*=genrisi_nasumicno_pocetno_resenje(ulazni_podaci);
while nije_ispunjen_kriterijum_zaustavljanja
k=1;
while k<=k_max
x'=na_slucajan_nacin_izaberi_resenje_iz_N_k(x*,k);
if f(x')<f(x*)
x*=x'; %azuriramo tekuce resenje
k=1; %pretragu nastavljamo u okolini N_1
else
k=k+1; %pretrazujemo narednu okolinu nepromenjenog tekuceg resenja
end
end
(Basic Variable Neighborhood Search, BVNS)
BVNS predstavlja kombinaciju determinističkog i stohastičkog pristupa što vodi ka balansu između diverzifikacije i intenzifikacije procesa pretrage. Iz tog razloga BVNS metoda je najčešće korišćena varijanta VNS-a. BVNS se sastoji iz dva osnovna dela, faze razmrdavanja i faze lokalnog pretraživanja. U procesu inicijalizacije, vrši se odabir okolina koje će se koristiti u fazi razmrdavanja i fazi lokalnog pretraživanja, generisano početno rešenje postaje tekuće rešenje $x^$ i $k$ se postavlja na $1$. Svaka iteracija BVNS metode počinje fazom razmrdavanja u kojoj se vrši slučajan odabir rešenja $x'$ iz okoline $N_k(x^)$. Potom se, počevši od $x'$, primenjuje neka metoda lokalne pretrage unapred definisane okoline u cilju nalaženja boljeg rešenja. Okolina koja se koristi za lokalnu pretragu ne mora biti ista kao i okolina za razmrdavanje. Rezultat lokalne pretrage $x''$ se poredi sa tekućim rešenjem (korak pomeraja). Ukoliko je lokalnom pretragom dobijeno bolje rešenje u pogledu vrednosti funkcije cilja, $x''$ postaje tekuće rešenje $(x^=x'')$, $k$ se postavlja na $1$ i proces pretrage se nastavlja pretraživanjem okoline za razmrdavanje $N_1(x^)$. U suprotnom, algoritam nastavlja pretraživanje u sledećoj okolini $N_{k+1}$ nepromenjenog tekućeg rešenja. Kada $k$ postane veće od $k_{max}$, njegova vrednost se ažurira na $1$ i nastavlja se sa pretraživanjem okoline $N_1(x^*)$. Opisani koraci se smenjuju do zadovoljenja unapred definisanog kriterijuma zaustavljanja.
%BVNS
%Inicijalizacija: odabir okolina N_k, k=1,...,k_max i ostalih parametara
x*=genrisi_nasumicno_pocetno_resenje(ulazni_podaci);
f*=f(x*);
while nije_ispunjen_kriterijum_zaustavljanja
k=1;
while k<=k_max
%faza razmrdavanja
x'=na_slucajan_nacin_izaberi_resenje_iz_N_k(x*,k);
%faza lokalne pretrage
x"=lokalna_pretraga(x');
if f(x")<f*
x*=x"; %azuriramo tekuce resenje
f*=f(x");
k=1; %pretragu nastavljamo u okolini N_1 novog tekuceg resenja
else
k=k+1; %pretrazujemo narednu okolinu nepromenjenog tekuceg resenja
end
end
(General Variable Neighborhood Search, GVNS)