POLITECHNIKA WROCŁAWSKA Temat: Implementacja i analiza eksperymentalna algorytmów metaheurystycznych.
Wydział Elektroniki Automatyka i Robotyka studia inż. Data: Ocena: Prowadzący:
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 pj0
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
(…)
…
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…
…[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…
… 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…
... zobacz całą notatkę
Komentarze użytkowników (0)