(Greedy Randomized Adaptive Search Procedure, GRASP)
Pohlepna stohastičko-adaptivna procedura pretrage je metaheuristička metoda sa višestartnim pristupom zasnovana na lokalnom pretraživanju. Svaka iteracija se sastoji iz dve osnovne faze: nasumično-pohlepnog algoritma za konstrukciju inicijalnog rešenja i lokalne pretrage. Nakon generisanja dopustivog rešenja u prvoj fazi, algoritam nastavlja sa lokalnim pretraživanjem okoline konstruisanog rešenja u cilju nalaženja lokalnog optimuma. U svakoj iteraciji pamte se dostignuti lokalni optimumi, a najbolje pronađeno rešenje tokom svih GRASP iteracija predstavlja krajnji rezultat GRASP metode.
U prvoj fazi GRASP metode koristi se nasumično-pohlepni algoritam za konstrukciju inicijalnog rešenja (engl. Greedy Randomized Construction, GRC). U GRC fazi rešenje se formira iterativnim dodavanjem jednog po jednog elementa sve dok se ne konstruiše kompletno dopustivo rešenje. Neka je $Cl$ (engl. Candidate List) lista kandidata koji u trenutnoj iteraciji GRC faze mogu postati deo rešenja . Trenutnom skupu elemenata koji će formirati rešenje dodaje se nasumično izabran element iz redukovane liste kandidata (engl. Restrictive Candidate List, $RCL$). Pri formiranju redukovane liste kandidata, svakom elementu $i\in Cl$ se dodeljuje vrednost funkcije ocenjivanja $c(i)$ koja oslikava uticaj elementa na vrednost funkcije cilja i od koje zavisi da li će element biti u $RCL$ ili ne. Dva jednostavna načina koja se koriste za kreiranje $RCL$-a zasnovana su na kardinalnosti i kvalitetu izdvojenih rešenja. Prvim pristupom, $RCL$ se formira od $k$ najboljih kandidata iz $Cl$, gde je $k$ unapred zadata kardinalnost redukovane liste. Drugim pristupom, RCL se kreira na sledeći način:
$$ RCL=\{i\in Cl:\ c(i)\leq c_{min}+\alpha (c_{max}-c_{min})\} $$
gde je $c_{min}=\min \{c(i),\ i\in Cl\}$, $c_{max}=\max \{c(i),\ i\in Cl\}$ i $\alpha \in [0,1]$.
Primetimo da se za $\alpha=0$ GRC algoritam svodi na klasični pohlepni algoritam, a za $\alpha=1$ na potpuno nasumičnu konstrukciju rešenja. Dobar balans izmedu ovih krajnjih slučajeva, postiže se adekvatnim izborom parametra za konkretan problem koji se razmatra.
Kriterijumi zaustavljanja GRASP metode mogu biti različiti: dostignut maksimalan broj iteracija, dostignuto maksimalno vreme izvršavanja, dostignut odredeni kvalitet rešenja, probabilistički kriterijum zaustavljanja (algoritam se zaustavlja onda kada je verovatnoća nalaženja boljeg rešenja manja od unapred zadatog praga) i drugi.
%Inicijalizacija i postvljanje parametara
while nije ispunjen kriterijum zaustavljanja
x=konstrukcija_resenja_pohlepnim_alg(ulazni_podaci); %GRC faza
x*=lokalna_pretraga(x); %faza lokalnog pretrazivanja
if x* je bolje od x_best
x_best=x*;
end
end
return x_best
Socijalna mreža je opisana grafom u kom čvorovi grafa predstavljaju individue, dok se grane grafa odnose na veze i interakcije izmedu njih. U osnovnoj varijanti problema, reč je o netežinskom grafu, iako je moguće dodati težine koje bi simulirale jačinu veze ili učestalost interagovanja između dve individue. Za datu socijalnu mrežu predstavljenu grafom cilj je pronaći što manji skup uticajnih individua (čvorova) koji bi raširio pozitivni uticaj u čitavoj mreži.
Budući da se radi o NP-teškom problemu kombinatorne optimizacije, potrebno je naći brz i efikasan algoritam koji je u stanju da u kratkom vremenskom periodu pronađe rešenje zadovoljavajućeg kvaliteta.
Matematička formulacija
Neka je $G = (V,E)$ prost neusmeren povezan graf sa skupom $V$ od $n$ čvorova i skupom grana
$E ⊂ V ×V$. Za proizvoljna dva čvora $u, v ∈ V$ kažemo da su susedi ukoliko postoji grana $(u,v) ∈ E$ koja ih povezuje. Otvorena okolina čvora $v ∈ V$, u oznaci $N(v)$, definisana je sa $N(v) = \{u ∈ V : (v,u) ∈ E\}$. Broj čvorova susednih čvoru $v$ predstavlja njegov stepen, $deg(v) = |N(v)|$. Podskup čvorova $S ⊆ V$ je dominantan skup sa pozitivnim uticajem ukoliko svaki čvor $v ∈ V$ ima bar polovinu svojih suseda u skupu $S$, preciznije: