Konvencionalna optimizacija podrazumijeva maksimiziranje ili minimiziranje funkcije cilja nad danim skupom dopustivih rješenja koja zadovoljavaju određena ograničenja. Međutim, u stvarnim situacijama, ulazni podaci su često nepoznati i podložni promjenama. Suvremena metoda za rad s takvim nesigurnostima se zove robusna optimizacija. Ovaj rad se bavi robusnim varijantama problema maksimalnog težinskog nezavisnog skupa (problem MTNS). Koriste se tri osnovna kriterija robusnosti: apsolutna robusnost, robusna devijacija te relativna robusna devijacija. Također se promatraju i općenitiji OWA kriteriji. Nesigurnost u pogledu težina vrhova izražena je preko eksplicitnog skupa scenarija ili pomoću intervala. Neka je \(G=(V,E)\) neusmjereni graf, gdje je \(V\) skup vrhova, a \(E\) skup bridova. Nezavisni skup od \(G\) je podskup skupa vrhova \(X \subseteq V\) takav da ne postoje dva vrha iz \(X\) koja su susjedna (povezana bridom iz \(E\)). Nadalje, neka je \(G=(V,E)\) neusmjereni graf čiji vrhovi imaju cjelobrojne nenegativne težine. Maksimalni težinski nezavisni skup} od \(G\) je nezavisni skup od \(G\) takav da je zbroj težina vrhova najveći mogući. Problem nalaženja takvog skupa za dani graf se naziva (konvencionalni) problem maksimalnog težinskog nezavisnog skupa (MTNS).Da bismo definirali robusne varijante problema tj. njihova rješenja, prvo uvodimo sljedeće oznake. Označimo sa \(S\) skup svih scenarija i pretpostavimo da je svaki scenarij zadan s \(n\)-torkom uređenih brojeva gdje \(n\) predstavlja broj vrhova. Za \(X\) proizvoljni nezavisni skup, \(F(X,s)\) je vrijednost funkcije cilja konvencionalnog problema za scenarij \(s\). Funkcija \(F(X,s)\) je jednaka zbroju težina vrhova iz skupa \(X\) za scenarij \(s\). Nadalje \(F^*_s\) je optimalna vrijednost funkcije cilja konvencionalnog problema za scenarij \(s\). \(\Phi\) je kolekcija svih nezavisnih skupova. Apsolutno robusno rješenje \(X_A\) je nezavisni skup čiji je minimum funkcije cilja, mjerene po svim scenarijima, najveći mogući tj. \[\begin{equation*} \text{opt}_A = \max_{X \in \Phi} \min_{s \in S} F(X,s) = \max_{X \in \Phi} F_A(X) = F_A(X_A). \end{equation*}\] Robusno devijantno rješenje \(X_D\) je nezavisni skup čije je maksimalno odstupanje od konvencionalnog optimuma, mjerenog po svim scenarijima, najmanje moguće tj. \[\begin{equation*} \text{opt}_D= \min_{X \in \Phi} \max_{s \in S} \Big( F^*_s - F(X,s) \Big) = \min_{X \in \Phi} F_D(X) = F_D(X_D). \end{equation*}\] Relativno robusno devijantno rješenje \(X_R\) je nezavisni skup čije je maksimalno relativno odstupanje od konvencionalnog optimuma, mjerenog po svim scenarijima, najmanje moguće tj. \[\begin{equation*} \text{opt}_R= \min_{X \in \Phi} \max_{s \in S} \Big((F^*_s - F(X,s))/F^*_s \Big) = \min_{X \in \Phi} F_R(X) = F_R(X_R). \end{equation*}\] OWA kriteriji su generalizacija navedenih kriterija. Primjerice, OWA\(_A\) se definira na sljedeći način. Za odabrano rješenje \(X\) pripadne vrijednosti funkcije cilja \(F(X,s)\) sortiramo uzlazno: \[\begin{equation*} F(X,s_{\sigma(1)}) \leq F(X,s_{\sigma(2)}) \leq \ldots \leq F(X,s_{\sigma(p)}), \end{equation*}\] \(\sigma\) je permutacija. Tada se \(OWA_A\) cijena za \(X\) računa: \[ O_A(X) = \sum_{i=1}^p a_i\cdot F(X,s_{\sigma(i)}) . \] OWA\(_A\) rješenje \(X_{OA}\) je nezavisni skup koje maksimizira funkciju \(O_A(X)\) na skupu svih mogućih rješenja tj. \[\begin{equation*} \text{opt}_{OA} =O_A(X_{OA}) =\max_{X \in \Phi} O_A(X). \end{equation*}\] U radu prvo istražujemo odnos između robusnih varijanti našeg problema i robusnih varijanti problema minimalnog težinskog vršnog pokrivača (problem MTVP). Definirajmo problem MTVP. Neka je \(G=(V,E)\) neusmjereni graf, gdje je \(V\) skup vrhova, a \(E\) skup bridova. Vršni pokrivač od \(G\) je podskup skupa vrhova \(Y \subseteq V\) takav da je svaki brid iz \(E\) incidentan s barem jednim vrhom iz \(Y\). Neka je \(G=(V,E)\) neusmjereni graf čiji vrhovi imaju cjelobrojne nenegativne težine. Minimalni težinski vršni pokrivač od \(G\) je vršni pokrivač od \(G\) takav da je zbroj težina vrhova najmanji mogući. Problem nalaženja takvog skupa za dani graf se naziva (konvencionalni) problem minimalnog težinskog vršnog pokrivača (MTVP). Istražujemo je li komplement robusno optimalnog nezavisnog skupa robusno optimalni vršni pokrivač i obratno (kao što vrijedi za konvencionalne optimume). Pokazuje se da odgovor na to pitanje nije trivijalan. Točnije, odgovor ovisi o odabranom kriteriju robusnosti. Komplement robusnog devijantnog rješenja problema MTNS je robusno devijantno rješenje problema MTVP i obratno. Za ostale kriterije ne vrijedi ekvivalencija osim u nekim specijalnim slučajevima. Potom se bavimo rješavanjem robusnih varijanti problema MTNS na običnim grafovima. Kako je rješavanje konvencionalnog problema MTNS već NP-teško, nalaženje egzaktnog rješenja njegove robusne varijante neće biti ništa lakše. Stoga predlažemo približni algoritam za rješavanje spomenutih robusnih varijanti koji se temelji na evolucijskom računanju i na kolekciji različitih operatora križanja i mutacija. Navedeni algoritam je eksperimentalno testiran na odgovarajućim instancama problema. Pokazuje se da je moguće postići zadovoljavajuća rješenja u prihvatljivom vremenu. Konačno, istražujemo složenost navedenih robusnih varijanti na stablima. Poznato je da je konvencionalni problem MTNS na stablima rješiv u polinomijalnom vremenu. Nažalost, pokazuje se da su gotovo sve robusne varijante NP teške. Stoga predlažemo približni algoritam dizajniran specijalno za stabla koji uzima u obzir njihovu specifičnu strukturu. Detaljnije, algoritam kombinira dobre osobine dinamičkog programiranja, evolucijskog računanja i pohlepnog odlučivanja. Navedeni algoritam je također eksperimentalno testiran na odgovarajućim instancama problema. Opet se pokazuje da je moguće postići zadovoljavajuća rješenja u prihvatljivom vremenu.