Algoritmi Genetici

Alegeţi una din problemele din lista de mai jos, pe care urmează să o rezolvaţi prin două metode: HillClimbing sau Simulated Annealing (bonus dacă sunt prezentate ambele) şi Algoritm Genetic.

1. Găsirea clicii maximale într-un graf (grafuri de test: [1])
2. Colorarea grafurilor: găsirea unei colorări a nodurilor cu un număr minim de culori, astfel încât oricare două noduri adiacente să aibă culori diferite (grafuri de test: [1], [2])
3. Problema comis-voiajorului (TSP: Travelling Salesman Problem; grafuri de test: [3])
4. 2D bin-packing: o mulţime de obiecte rectangulare trebuie aşezate într-un recipient, de asemenea rectangular, cu lăţime fixă, astfel încât lungimea zonei acoperite să fie minimă
5. Problema satisfiabilităţii (ex: 3SAT; date de test: [4] [5])

O listă mai vastă de probleme NP complete dintre care se poate alege una pentru studiu se găseşte la A compendium of NP optimization problems.

Etape:

• Modelare: săptămâna 6
• Prezentarea primei metode (HC | SA): săptămânile 7-8
• Prezentarea Algoritmului Genetic: săptămânile 8-9
• Finalizare, redactare raport (vezi şablonul recomandat), prezentare: săptămânile 9-10

Temă (pt. săptămâna 6)

Pentru cel puţin una din problemele de mai sus, gândiţi-vă la modul în care trebuie definite:

• reprezentarea
• funcţia fitness
• operatorii genetici