POLITECHNIKA WROCŁAWSKA |
Temat: Implementacja i analiza eksperymentalna algorytmów metaheurystycznych. |
||
Mateusz Gralka |
|
||
Wydział Elektroniki PN 11:15 Automatyka i Robotyka studia inż. |
Data: 24.01.2008 |
Ocena: |
Prowadzący: dr inż. M.Lichtenstein |
PROBLEM:
Dany jest zbiór n zadań J={J1, J2, ..., Jn} oraz zbiór m identycznych maszyn M={M1, M2, ..., Mm}. Każde zadanie Jj€J (j=1,2,..,n) jest niezależne,
niepodzielne, dostępne w chwili t=0 i musi zostać wykonane przez dokładnie
jedną z maszyn, przy czym jego wykonanie zajmuje każdej z maszyn pj>0
jednostek czasu. Każda maszyna może wykonywać w danym momencie co
najwyżej jedno zadanie. Problem polega na takim przyporządkowaniu zadań
do maszyn, aby zminimalizować czas zakończenia wykonywania ostatniego
zadania (czyli kryterium tzw. długości uszeregowania Cmax):
Cmax = max 1≤j≤n{Cj},
gdzie Cj oznacza moment zakończenia wykonywania j-tego zadania.
Zaimplementować:
Część I.
Algorytm LSA:
1. Utwórz dowolną listę zadań 1,2,…,n.
2. Pobieraj zadania kolejno i przyporządkowuj do najwcześniej dostępnej
maszyny.
Algorytm LPT:
1. Utwórz listę zadań 1,2,…,n taką, że p1 ≥ p2 ≥ … ≥ pn.
2. Pobieraj zadania kolejno i przyporządkowuj do najwcześniej dostępnej
maszyny.
Część II.
Algorytm METAHEURYSTYCZNY:
1. Utwórz dowolną listę zadań 1,2,…,n.
2. Pobieraj zadania kolejno i przyporządkowuj do dowolnej losowej
maszyny.
3. Losowo wybrany element wyciąć z jednej maszyny i dodać do innej ponownie policzyć współczynnik, jeżeli po nowym przydziale współczynnik Ra jest mniejszy lub większy, ale nie więcej niż 0,02 to zapisać zmianę i powtórzyć powyższą operacje zadaną ilość razy. (W moim przypadku 100 000 razy.)
Eksperymenty należy przeprowadzić dla:
• trzech wartości m (ilość procesorów): 10, 15, 20 (można przyjąć inne
wartości jeśli czasy będą wychodziły zbyt długie lub zbyt krótkie);
• trzech wartości n (ilość zadań): 2*m, 3*m i 5*m;
• czasy wykonywania zadań należy generować losowo, jako liczby
całkowite, zgodnie z rozkładem jednostajnym na następujących dwóch
przedziałach:
pj € (0; 20] lub (20; 50], j = 1,2,…,n.
Po przeanalizowaniu poprzedniej i obecnej części zadania, doszedłem do wniosku ze nie ma sensu porównywać algorytmu metaheurystycznego z algorytmem LSA dlatego, usunąłem z programu odpowiedzialne za niego części kodu a wyniki zestawiłem z algorytmem LPT
Ważne fragmenty kodu:
1. Funkcja „dzialanie”, to nią wywolujemy wszystkie poboczne funkcje takie jak zerowanie, sortowanie czy zapis do pliku.
void dzialanie(int IloscMaszyn, int IloscZadan, int Przedzial, int Poczatek, char a[]) { for(int i=0; i<powtorzen; i++) { Zeruj_Procesy(); Zerowanie_Maszyn(); Losowanie_Procesow(IloscZadan, Przedzial, Poczatek); Przydzielanie_Procesow(IloscMaszyn, IloscZadan); float WKLA=Wyzarzanie(IloscMaszyn,IloscZadan); WynikiKLASY[i]=WKLA;
ZerowanieCzasuMaszyn(); ZerowanieCzasowZadan(); KopiujWartosci(IloscMaszyn,IloscZadan); Sortowanie(JakieZadania,IloscZadan); Przydzielanie_Zadan(IloscMaszyn,IloscZadan); float LPT = WspolczynnikRa(IloscMaszyn,IloscZadan); WynikiLPT[i]=LPT; } zapis_do_pliku(a); } |
2. Funkcja symulująca przydzielanie kolejnego zadania do pierwszej wolnej maszyny.
void Przydzielanie_Procesow(int IloscMaszyn, int IloscZadan) { int maszyna;
for(int i=0; i<IloscMaszyn; i++) { Tablica_Maszyn[i].zeruj_ilosc_procesow(); }
for(int i=0; i<IloscZadan; i++) { maszyna=randint(0, IloscMaszyn-1); Tablica_Maszyn[maszyna].dodaj_proces(Tablica_Procesow[i]); }
for(int i=0; i<IloscMaszyn; i++) { Tablica_Maszyn[i].licz_sume(); } } |
3. Funkcja kopiująca wartości z procesów dla algorytmu metaheurystycznego do algorytmu LPT.
void KopiujWartosci(int IleMaszyn, int IleZadan) { for (int i=0; i <IleZadan ; i++) { JakieZadania[i]=Tablica_Procesow[i].zwroc_czas(); } } |
4. Funkcja wyżarzania, to właśnie w niej szukamy najlepszego rozwiązania dla problemu, w bardzo dużej części zależna od 3 czynników ilości powtórzeń operacji (iteracje), odchylenia od wyniku(jeżeli wynik jest gorszy ale nie przekracza danej wartości (eps)), zadanej wartości dla której program automatycznie zakończy działanie.
float Wyzarzanie(int IloscMaszyn, int IloscZadan) { Maszyna pomoc; Maszyna pomoc2; int numer_zadania=0; int numer_maszyny=0; int nowa_maszyna=0; bool znaleziono=false; float wspolczynnik_przed=0; float wspolczynnik_po=0; float wspolczynnik=0;
for(int i=0; i<iteracje; i++) { numer_zadania=randint(0, IloscZadan-1); znaleziono=false; wspolczynnik_przed=Wspolczynnik_Ra(IloscMaszyn,IloscZadan); for(int j=0; j<IloscMaszyn && !znaleziono; j++) { znaleziono=Tablica_Maszyn[j].czy_jest_proces(Tablica_Procesow[numer_zadania]); numer_maszyny=j; } pomoc=Tablica_Maszyn[numer_maszyny]; Tablica_Maszyn[numer_maszyny].usun_proces(Tablica_Procesow[numer_zadania]); nowa_maszyna=randint(0, IloscMaszyn-1); while(nowa_maszyna==numer_maszyny) { nowa_maszyna=randint(0, IloscMaszyn-1); } pomoc2=Tablica_Maszyn[nowa_maszyna]; Tablica_Maszyn[nowa_maszyna].dodaj_proces(Tablica_Procesow[numer_zadania]); wspolczynnik_po=Wspolczynnik_Ra(IloscMaszyn,IloscZadan); if(wspolczynnik_po<wspolczynnik_przed) { } else { if(wspolczynnik_po-wspolczynnik_przed<eps) { }
else { Tablica_Maszyn[nowa_maszyna]=pomoc2; Tablica_Maszyn[numer_maszyny]=pomoc; } } } wspolczynnik=Wspolczynnik_Ra(IloscMaszyn,IloscZadan); return wspolczynnik; } |
Wyniki:
m/z |
10/20 |
10/30 |
10/50 |
15/30 |
15/45 |
15/75 |
20/40 |
20/60 |
20/100 |
|
|||||||||
LPT dla wartości losowanych z przedziału 1-20 |
|||||||||
|
|||||||||
min |
1,02041 |
1,00437 |
1 |
1,01786 |
1,0181 |
1,00134 |
1,02302 |
1,01124 |
1,00196 |
śr |
1,1111542 |
1,05584 |
1,019873 |
1,092185 |
1,06516 |
1,022348 |
1,087867 |
1,065479 |
1,021329 |
max |
1,36691 |
1,12211 |
1,04822 |
1,22845 |
1,17647 |
1,04381 |
1,19481 |
1,12436 |
1,04945 |
|
|||||||||
LPT dla wartość losowanych z przedziału 21-50 |
|||||||||
|
|||||||||
min |
1,01156 |
1,00216 |
1,00058 |
1,01622 |
1,00604 |
1,0004 |
1,013 |
1,00691 |
1,00176 |
śr |
1,053093 |
1,027027 |
1,00932 |
1,048953 |
1,028986 |
1,009607 |
1,044121 |
1,027639 |
1,010169 |
max |
1,17851 |
1,06033 |
1,02236 |
1,13611 |
1,06292 |
1,02049 |
1,10632 |
1,06503 |
1,02157 |
m/z |
10/20 |
10/30 |
10/50 |
15/30 |
15/45 |
15/75 |
20/40 |
20/60 |
20/100 |
|
|||||||||
Wyżarzanie dla wartości losowanych z przedziału 1-20 i ilosci iteracji 100K |
|||||||||
|
|||||||||
min |
1,00872 |
1,00905 |
1,00981 |
1,01704 |
1,0164 |
1,01528 |
1,01955 |
1,01729 |
1,01616 |
śr |
1,0224959 |
1,023956 |
1,022599 |
1,03307 |
1,032221 |
1,03181 |
1,039993 |
1,042269 |
1,043378 |
max |
1,05021 |
1,04695 |
1,04011 |
1,05897 |
1,05416 |
1,0543 |
1,07842 |
1,06881 |
1,07832 |
|
|||||||||
Wyżarzanie dla wartości losowanych z przedziału 21-50 i ilosci iteracji 100K |
|||||||||
|
|||||||||
min |
1,00872 |
1,00883 |
1,01109 |
1,01612 |
1,01314 |
1,01672 |
1,01803 |
1,018 |
1,0179 |
śr |
1,0224959 |
1,020643 |
1,021596 |
1,028786 |
1,02945 |
1,030147 |
1,036432 |
1,039139 |
1,037597 |
max |
1,05021 |
1,03731 |
1,04976 |
1,05559 |
1,05617 |
1,05411 |
1,07233 |
1,06761 |
1,06225 |
Wnioski:
Po zanalizowaniu wyników doszedłem do wniosku, że szybszym w niektórych przypadkach jest algorytm LPT w niektórych zaś algorytm symulowanego wyżarzania. Jednak różnice miedzy maksymalnym a minimalnym czasem są mniejsze dla algorytmu metaheurystycznego. Wyniki pokazują, że ów algorytm dla dużej części pomiarów utrzymuje średnią oraz minimum i maksimum. Wnioskować można, że dla większości kombinacji wyniki będą zbliżone. Jak nietrudno zauważyć LPT najlepsze wyniki uzyskuje dla stosunkowo dużej liczby zadań w porównaniu do liczby maszyn.
Można zauważyć podobna zależność w przypadku różnych przedziałów losowania, lepsze wyniki uzyskuje się dla losowania z przedziału 21-50. Uważam, że jest to spowodowane tym, iż stosunek miedzy największą możliwą wartością a najmniejszą jest dużo mniejszy niż w przypadku zakresu 1-20.
Najlepszym możliwym współczynnikiem jest RLPT =1, oznacza on, że wszystkie maszyny skończyły wykonywać przydzielone im zadania w tym samym czasie. Taki wynik można uzyskać zupełnie przypadkowo i nie jest on zależny od zastosowanego algorytmu, liczby zadań czy przedziału. W algorytmie wyżarzania dodatkowo można dopisać instrukcję, która przerywałaby iterację i tym samym działanie programu gdyby współczynnik zbliżył się na zadaną wartość od „idealnego” współczynnika. Ogromny wpływ na wyniki ma liczba iteracji - tj. ilości powtórzeń losowania i przydzielania pojedynczego procesu do maszyny, duża liczba iteracyjna w połączeniu z instrukcją przerywania - gdy współczynnik osiągnie zadaną wartość mogłyby znacząco poprawić wynik.
Algorytm wyżarzania jest bardzo efektywnym i bardzo „równym” algorytmem, jest doskonały gdy chcemy otrzymać wyniki na stałym poziomie. Jest on jednak bardzo czasochłonny i wymagający dla sprzętu.
Wybór algorytmu powinniśmy ustosunkować wg własnego uznania i potrzeb. Jeśli potrzeba „równych” wyników najlepszym wyborem będzie algorytm metaheurystyczny, jeśli natomiast dokładność jaką oferuje nam algorytm LPT jest wystarczająca, to jest on lepszym wyborem ponieważ działa znacznie szybciej mimo zastosowania w moim przypadku do sortowania wolnego algorytmu bąbelkowego.