Zastosowanie algorytmów genetycznych

Abstract

Celem algorytmu, który został zaproponowany w pracy jest zapewnienie i zrównoważonego obciążenia w systemach wieloprocesorowych. Jest to algorytm bazujący na idei algorytmów genetycznych a decyzje zakodowane są w postaci dziesiętnej – dwuwymiarowej. Najważniejszą funkcją, mającą decydujący wpływ na skuteczność algorytmu jest funkcja celu, od której zależy ile procesorów będziemy w stanie równomiernie obciążyć. Kluczową cechą algorytmu jest zdolność do równoważenia obciążenia dla takiej liczby procesorów jaka występuje w systemie. Oceny własności algorytmu dokonano na podstawie eksperymentów symulacyjnych.
Autorzy: Łukasz BARDZIŃSKI, Leszek KOSZAŁKA

1. WPROWADZENIE

Jednym z podstawowych pojęć zdefiniowanego tematu jest pojecie równoważenia obciążenia w systemie. Rozumie się przez nie równomierny podział zadań do wykonania oraz przydzielenie ich jednostkom wykonawczym czyli procesorom w taki sposób żeby każdy z nich był w bardzo podobnym stopniu obciążony [1].

W dzisiejszych czasach wszystkie systemy obliczeniowe pracujące w układach wieloprocesorowych posiadają implementację algorytmów pozwalających na równoważenie obciążenia, dzięki czemu są w stanie zwiększyć swą moc obliczeniową.

Zastosowanie do tego problemu algorytmów genetycznych pozwala na dokonanie podziału zadań w sposób optymalny lub bliski optimum [2]. Celem tej publikacji jest zaproponowanie algorytmu genetycznego, który będzie w stanie realizować dynamiczne równoważenie obciążenia w systemach wieloprocesorowych.

Przedstawiony algorytm genetyczny działa na tablicach zawierających zadania. Populacja tworzona jest na podstawie permutacji generowanej tablicy a jej wielkość rośnie wraz ze wzrostem procesorów w systemie. Po selekcji osobników najlepiej przystosowanych oraz za pośrednictwem funkcji krzyżowania i mutacji wybierana jest najlepsza tablica zadań spełniająca równoważenie obciążenia dla wszystkich procesorów znajdujących się w systemie.