Zastosowanie algorytmów genetycznych cd.

4. OPIS ZAPROPONOWANYCH ALGORYTMóW

4.1. WYPEŁNIANIE TABLICY ZADAŃ

Przykładowa tablica zaprezentowana na Rysunku 2 została wypełniona kolejnymi zadaniami z puli zadań do wykonania. Oznacza to, że nie została jeszcze zrównoważona pod względem obciążenia czasowego dla poszczególnych procesorów. Zrównoważenie to zostanie dokonane za pomocą zaproponowanego algorytmu genetycznego.



4.2. TWORZENIE POPULACJI OSOBNIKóW

W prezentowanym algorytmie, po badaniach doświadczalnych, przyjęto wielkość populacji równą wielkości tablicy zadań. Każdy kolejny osobnik populacji tworzony jest poprzez losową permutację zadań. Każdy z osobników populacji tworzony jest w następujący sposób: dla kolejnych elementów tablicy zadań losowany jest numer elementu do przestawienia, następnie zadania te są zamieniane miejscami. Cykl ten powtarzany jest dla wszystkich zadań w tablicy. Proces ilustruje Rysunek 3.



4.3. FUNKCJA CELU

Funkcja celu zdefiniowana została jako następujący iloczyn:



gdzie: Pi – wykorzystanie i-tego procesora w systemie, liczone według Wzoru 2,
B- ilość procesorów, których obciążenie jest zrównoważone,
A- ilość wszystkich procesorów w systemie.



gdzie: ti – czas zadań do wykonania na procesorze i,
t – czas wszystkich zadań do wykonania w systemie.

Na podstawie tak policzonej funkcji celu (Wzór 1) dla każdego osobnika populacji, możemy przystąpić do selekcji, która realizowana jest za pośrednictwem algorytmu ruletki [5] z odpowiednim prawdopodobieństwem, którego sposób wyliczenia przedstawia Tabela 4.


4.4. KRZYŻOWANIE

Wybrane osobniki populacji poddawane zostają procesowi krzyżowania [3]. Losowany jest punkt krzyżówki osobnika, następnie zadanie odpowiadające temu punktowi wymieniane jest z zadaniem drugiego rodzica lezącym na tej samej pozycji w tabeli. Następnie znajdowane jest zadanie, które zostało zdublowane i znów wymieniane jest z zadaniem leżącym na tej samej pozycji w drugim rodzicu. Proces powtarzany jest do momentu wyeliminowania zdublowanych zadań. Proces krzyżowania przedstawiony został na Rysunku 5.



4.5. MUTACJA

Mutacji poddawany jest jeden (losowo wybrany) członek nowej populacji. Proces mutacji polega na wymianie kolejności wykonywania dwóch zadań [4] i został przedstawiony na Rysunku 6.



4.6. WYBóR NAJLEPSZEGO POTOMKA

Korzystając ze Wzoru 1 obliczamy dla każdego osobnika populacji wartość funkcji celu. Następnie tworzymy dla całej populacji tabelę prawdopodobieństwa oraz przedziały wartości (Rysunek 4), na podstawie których będzie wybierany najbardziej przystosowany osobnik, to znaczy ten, który będzie w stanie zrównoważyć obciążenie dla największej ilości procesorów występujących w systemie.
5. WYNIKI BADAŃ I ICH ANALIZA
Jeden z testów zaprojektowanego algorytmu polegał na obliczeniu wartości procentowych zrównoważenia obciążenia dla różnych ilości procesorów zainicjowanych w systemie. Jak widać na Rysunku 7 nawet dla siedmiu procesorów zrównoważenie obciążenia utrzymuje się na poziomie 82%. Natomiast w systemie do pięciu procesorów przekracza 90 % co w praktyce oznacza, że zaproponowany algorytm genetyczny w 9 na 10 przydziałów zadań będzie w stanie zrównoważyć obciążenie dla wszystkich jednostek arytmetyczno-logicznych w systemie.

Badania zostały przeprowadzone zarówno dla systemu już zrównoważonego pod względem obciążenia jak i dla obciążeń niezrównoważonych. Rysunek 8 przedstawia ilość cykli algorytmu genetycznego potrzebnych do zrównoważenia systemu wytrąconego z równowagi. W skrajnej sytuacji badawczej dla siedmiu procesorów algorytm potrzebuje tylko 3,5 cyklu by zrównoważyć system.

Dla zaproponowanego algorytmu najlepiej wypadł system z pięcioma procesorami. Wartość równoważenia obciążenia utrzymuje się na poziomie 95% a doprowadzenie do równowagi systemu zajmuje 2,1 cyklu. Po skończeniu analizy przedstawionych badań sam nasuwa się pomysł na poszukiwanie optymalnej modyfikacji funkcji celu bardziej uzależniającą swą wartość od aktualnie obsługiwanej ilość procesorów.

Autorzy: Łukasz BARDZIŃSKI, Leszek KOSZAŁKA 

LITERATURA

[1] M. Sysło, N. Deo, S. Kowalik – „Algorytmy optymalizacji dyskretnej” – PWN 1995.
[2] David E. Goldberg – „Algorytmy genetyczne i ich zastosowania” – WNT 2003.
[3] A. Zomaya, Mee-Hwei Teh – “Observatiions on Rusing Genetic Algorithms for Dynamic Load-Balancing” – IEEE Transactions - Vol. 12 no. 9 September 2001, 899-911
[4] A. Zomaya – “Genetic Scheduling for Parallel Processor Systems” - IEEE Transactions - Vol. 10 no. 8 August 1999, 795-811
[5] Rutkowska, M. Piliński, L. Rutkowski – „Sieci neuronowe, algorytmy genetyczne i systemy rozmyte” – PWN 1999.