Lokalna pretraga

(Local Search - LS)

Lokalno pretraživanje predstavlja najstariju i najjednostavniju S-metaheuristiku koja se koristi za rešavanje raznih problema kontinualne i diskretne optimizacije. Ideja ove metode je doći do najboljeg rešenja sukcesivnim pretraživanjem okolina rešenja koja se posećuju tokom procesa pretrage.

Pre implementacije lokalne pretrage za konkretan problem, neophodno je definisati adekvatnu reprezentaciju rešenja, prostor pretrage $X$, generisati početno dopustivo rešenje $x\in X$ i definisati okolinu koja će se lokalno pretraživati. U zavisnosti od topologije prostora, bira se metrika (euklidska, Hamingova, Menhetn...) pomoću koje se za proizvoljno dopustivo rešenje $x$ definiše podskup $N(x)\subseteq X$ koji predstavlja okolinu rešenja $x$, a njeni članovi su susedi od $x$. Metoda počinje pretraživanjem okoline početnog rešenja $N(x)$. Ako se naiđe na bolje rešenje, ono postaje tekuće i nastavlja se sa pretraživanjem njegove okoline. Ukoliko takvo rešenje ne postoji (tekuće rešenje je lokalni optimum), LS se zaustavlja i poslednje tekuće rešenje se uzima za aproksimaciju optimalnog rešenja.

Strategije za odabir novog suseda:

1. Best improvement: Za sledećeg suseda bira se najbolji sused iz okoline $N(x)$, tj. onaj sa najboljom vrednošću funkcije cija. Potrebno je za svakog suseda izračunati vrednost funckije cilja, što može dosta povećati vreme izvršavanja algoritma u celini, posebno ukoliko se pretražuje veća okolina.
2. First improvement: Bira se prvi sused koji je bolji od tekućeg rešenja. Na ovaj način ne ocenjuju se sva rešenja koja se nalaze u okolini tekućeg, već samo određeni broj njih dok se ne pronađe rešenje sa boljom vrednošću funkcije cilja. Prateći određeni redosled generisanja suseda, računaju se njihove vrednosti funkcije cilja i čim se naiđe na poboljšanje, vrši se zamena tekućeg rešenja susedom na kom se to poboljšanje postiže. U najgorem slučaju (ako je tekuće rešenje lokalni optimum) evaluiraju se sva rešenja.
3. Random selection: Nasumično se bira sused koji je bolji og tekućeg rešenja i on postaje novo tekuće rešenje.

Generalno, nedostatak LS heuristike je u tome što se pretraga često zaglavljuje u lokalnom optimumu koji nije globalni. Stoga se razmatraju razna poboljšanja LS heuristike ili se ona koristi u okviru neke druge S ili P-metaheuristike kojom se unosi određeni stepen diverzifikacije u proces pretrage.

Strategije poboljšavanja lokalne pretrage:

1. Multistartni pristup (Multistart Local Search-MLS) Budući da kvalitet rešenja dobijenog LS zavisi i od početnog rešenja, ideja na kojoj se zasniva MLS je generisati više početnih rešenja (na slučajan način) i nad svakim primeniti LS. Sva izvršavanja su međusobno nezavisna i za aproksimaciju optimalnog rešenja bira se najbolji lokalni optimum.
2. Dodatno poboljšanje možemo dobiti povezivanjem lokalnih optimuma dobijenih MLS metodom (npr. rezultat jedne MLS iteracije prosledimo kao početno rešenje sledeće MLS iteracije). Postupak u kojem se vrši perturbacija rešenja dobijenog u jednoj MLS iteraciji i rezultat prosleđuje kao početno rešenje sledeće MLS iteracije naziva se Iterirano lokalno pretraživanje (ILS).

Iterirano lokalno pretraživanje

(Iterated local search - ILS)

Iterativna lokalna pretraga predstavlja metaheuristiku zasnovanu na ponavljanju lokalne pretrage sa ciljem povećavanja kvaliteta uzastopnih dobijenih rešenja. Inicijalno rešenje uglavnom se kreira na slučajan način ili se za njegovo kreiranje koristi određena heuristika. Najpre se izvršava lokalna pretraga nad inicijalnim rešenjem i dobija se odgovarajući lokalni optimum. Potom se u svakoj iteraciji primenjuje perturbacija na dobijenom lokalnom optimumu nakon čega se izvršava lokalna pretraga nad rešenjem koje je dobijeno nakon perturbacije. Novi lokalni optimum se pod određenim uslovima prihvata kao trenutno rešenje. Navedeni proces se ponavlja sve dok se ne ispuni odgovarajući kriterijum zaustavljanja (maksimalan br. iteracija, dostignut određeni kvalitet rešenja, dostignuto maksimalno vreme izvršavanja...). Operator perturbacije u ILS metodi uglavnom kreira rešenje koje je blisko tekućem rešenju, tako što se jedan deo tekućeg rešenja zadržava, dok se drugi deo značajno menja u zavisnosti od istorije, tj. iskustva dobijenog u toku izvršavanja algoritma. Kriterijum prihvatanja rešenja dobijenog nakon perturbacije određuje da li novi lokalni minimum zadovoljava uslove da zameni trenutno rešenje.

s0 = Generisanje_inicijalnog_resenja;
s* = Lokalna_pretraga(s0);
while nije ispunjen kriterijum zaustavljanja 
			new_s= Perturbacija(s*, istorija_pretrage);
			new_s* = Lokalna_pretraga(new_s);
			s* = Kriterijum_prihvatanja_resenja(s*,new_s*,istorija_pretrage);
end
return s*