Rezolvarea problemei rucsacului folosind tehnici de metauristici

Rezumare

In aceasta lucrare mi-am propus o metodologie hibrida pentru rezolvarea unei problem de optimizare, mai exact problema rucsacului. Aceasta problema apare in diverse situatii practice, cum ar fi selectarea proiectelor de investitie a bugetului. In general, pentru a rezolva problema aceasta, putem folosi algoritmi exacti, care ne dau solutii exacte sau metaeuristici care nu garanteaza solutii exacte, ci in general, ne permit sa obtinem solutii “bune” aproximative. Totusi, aplicarea metodelor exacte este limitata de marimea instantelor din problema, de resursele computationale disponibile, in timp ce metaeuristicile ne obtin “calitatea” solutiilor pentru problem mai largi folosind resurse acceptabile. Metoda propusa consta in combinarea a doua tehnici de metaeuristici care au dat performante bune in natura combinatoriala: metoda ant colony optimization si metoda scatter search. Pentru a evalua performanta acestei metode am comparat mai multe rezultate din intreaga literatura.

1.Introducere

Sa presupunem ca avem un set de obiecte ale caror valor si greutati sunt cunoscute si un sac cu o capacitate limitata. Pentru a umple sacul cu obiectele intr-o metoda in care totalul valorii lor e cea mai mare vaoare posibila e cunoscuta ca fiind problema rucsacului. Aceasta problema este foarte populara in literature si a fost foarte extensive studiata de multi autori (de exemplu Martello & Toth, 1990, Pisinger, 1995, Visee et al, 1998, Captivo et al, 2003 si Ziter, 1999). Multe probleme din viata reala pot fi formulate ca problema rucsacului sau una din variantele ei, ca de exemplu: probleme de incarcare, probleme de selectare a proiectului, probleme de buget capital, problem de lichidare de stoc. Mai mult, poate fi gasita ca o subproblema in multe modele, cum ar fi partitia si proiectarea circuitelor electronice si alegerea unei echipe de zbor(Freville, 2004; Ehrgott & Ryan, 2002; Martello & Toth, 1990).

Sunt multe abordari care pot fi folosite pentru a rezolva asemenea feluri de probleme. Aceste abordari sunt clasificate ca metode exacte si metode approximate sau metaeuristici. Solutiile obtinute de metode exacte sunt solutii exacte, in timp ce acelea obtinute de metaeuristici sunt solutii aproximative. Datorita lipsei de resurse de calculare si marimii problemelor, metodele exacte au aplicatii limitate, de exemplu devin ineficare, mai exact in instante de dimensiuni mari (Visee et al, 1998, Captivo et al, 2003 si Luila, 2008); in timp ce metodele euristice, desi ele nu dau solutii exacte, au fost folosite a o alternative pe care te poti baza, deoarece s-au dovedit a fi eficiente cand ai de aface cu problem foarte mari, deoarece ele ajung la solutii aproximative “bune” si folosesc resurse putine, cee ace ar fi practic imposibil de realizat prin metode exacte (Ghosh, 2004; Freville, 2004).

In articolul acesta este prezentat un algoritm hibrid bazat pe combinarea a doua metaeuristici, care in particular au aratat performante bun in rezolvarea mai multor problem de combinatorie in natura: metoda ant colony optimization si metoda scatter search. Ideea e sa introducem niste imbunatatiri in algoritmul de colonie propus de Alaya et al (2007) sa poata fi combinat cu metoda scatter search propusa de Gomes da

Silva et al (2006) sis a analizam aplicarea ei prin rezolvarea unei instante mari de variante a problemei rucsacului cu o constrangere sau mai multe.

Restul lucrarii e organizat cum urmeaza: in sectiunea 2 sunt prezentate unele din conceptele teoretice care au legatura cu optimizarea combinarii multi-obiectiv si o definitie formala a celor doua variante de problem din studiu; sectiunile 3 si 4 sunt dedicate metaeuristicilor ant colony optimization si scatter search; in sectiunea 5 sunt prezentate strategii diverse de combinare a celor doua metaeuristici studiate; in sectiunea 6 sunt rezultatele prezentate si comentarii legate cu privire la experimentele pe calculator puse in metodele implementate; si sectiunea 7 prezinta concluziile principale.

2. Multi-obiectiv combinatorial

Optimizare

In anumite probleme reale ale vietii sunt mai mult decat un obiectiv de intalnit (de xemplu Kwark et al, 1996; Teng and Tzeng, 1996). Problemele combinatoriale de optimizare (in engleza MCOP) este denumirea comuna pentru problem de combinare cu mai mult de un obiectiv de optimizat. Aceste problem sunt caraterizate prin un numar mai mare de solutii, nu exista o singura solutie (optimul globar) dar un set de solutii de incredere poisibile numite set Pareto sau solutii non-dominate, care sunt superioare celorlalte cand luam in considerare toate obiectivele. Multiplicitatea solutiilor este explicata de faptul ca obiectivele se bat cap in cap. De xemplu, cand alegem o masina noua sa o cumparam anumite obiective pot fi luate in considerate. Pe de o parte este de dorit sa achizitionam o masina care are o performanta buna (in termeni de viteza maxima si capacitate de accelerare). Pe de alta parte masina trebuie sa fie sigura, economica si sa aiba un cost cat mai mic de achizitie.

Mai formal, un MCOP (in cazul problemei de maximizare) poate fi definit de urmatoarele:

unde zi(x)=cix reprezinta al i-lea obiectiv al functiei; ci reprezinta vectorul de valori asociat al obiectivului cu numarul I al functiei; n este numarul de variabile decizionale; X reprezinta regiunea posibila in spatial de decizie; h este numarul de restrictii/constrangeri; x este vectorul de variabile de decizie, x=(x1,x2,…,xn)r; A reprezinta coeficientul tehnologic al matricei (h x n) si b este vectorul de termeni independent ai restirctiilor.