Strojové učenie - Machine Learning

[Strojové učenie 2011/2012]

Cvičenie 4

Na tomto cvičení si precvičíme praktické použitie evolučných algoritmov, ktoré sme prebrali na poslednej prednáške. Vyberte si jeden z používaných univerzálnych balíkov, ktoré implementujú väčšinu najpoužívanejších verzií EA:

MIT GAlib - C++, stará, jednoduchá, relatívne prehľadná knižnica
EO (Evolving Objects) - C++, pozor tempates :), prepracovaný balík
alebo jeden zo širokej ponuky dostupných balíkov.

Úloha:

Skompilujte si vybraný systém a vyskúšajte a preštudujte činnosť pribalených príkladov. Buď modifikáciou existujúceho príkladu alebo odznova vytvorte program, ktorý vypočíta, ako rozdeliť N úloh na M strojov (ide o známy problém Job Shop Scheduling, ktorý sa vyskytuje v mnohých verziách, pre mnohé z nich neexistuje polynomický algoritmus, takže je potrebné používať optimalizačné algoritmy). V našom prípade vstupom pre program sú:

počet úloh N, strojov M, závislostí K a odstávok L
čas v minútach (celé číslo) potrebný na spracovanie každej z N úloh, T_i, 1 <= i <= N
relatívna závislosť úloh, t.j. zoznam K dvojíc (u_i,u_j), 1 <= i,j <= N, pričom platí, že úloha u_i musí byť skončená skôr, ako úloha u_j začne
povinné odstávky strojov, čiže zoznam L trojíc (s_i,od_i,do_i), ktorý udáva, že stroj si od minúty od_i (vrátane) má prestávku a je znova voľný od minúty do_i, 1 <= i <= L

Program má vypísať plán spracovania úloh, t.j. zoznam N trojíc (u_i,s_i,t_i), kde úloha u_i sa má vykonávať na stroji s_i nepretržite od minúty t_i.

Príklady vstupných súborov: ex4_input1.txt

Hodnotenie: 5 bodov za riešenie úlohy, uveďte krátky popis algoritmu a nakreslite graf z konvergencie (najlepšie riešenie pre každú generáciu)

Riešenie posielajte mailom (petrovic

fmph.uniba.sk) do 16.10.