Plan pracy magisterskiej
Wstęp
- o czym jest praca?
- algorytmy genetyczne
- historia
- zasada działania
- zastosowania:
- symulacja skomplikowanych procesów
- szukanie optymalnych (lub przybliżonych) rozwiązań złożonych systemów
- zastosowanie procesora graficznego
Motywacja
- problem:
- optymalizacja funkcji wielu zmiennych
- ( ilość danych >> moc sprzętu ) -> długi czas obliczeń
- charakterystyka algorytmów genetycznych:
- symulacja populacji osobników - setki, tysiące, miliony
- duża niezależność osobnika względem populacji - działanie równoległe
- proponowane podejście:
- wykorzystanie architektury procesora graficznego
- wykorzystanie natury algorytmów genetycznych
- wspólny mianownik - działanie równoległe
Program ewolucyjny
Sposób opisu populacji i działań na niej
- reprezentacja zmiennoprzecinkowa (dostosowana do problemu)
- tablice: osobniki + ich oceny
n osobników po dim zmiennych każdyn ocen po jednej zmiennej każda
- działania na populacji
- ocena (ewaluacja)
- funkcja Griewanka jako funkcja dopasowania
- przeliczenie wartości funkcji tak, aby dla lepszych dopasowań zwracała większą wartość
optimum - współrzędne optimum globalnego funkcji, random - dowolne współrzędne niebędące optimum- fit(optimum) > fit(random)
- griewank(optimum) < griewank(random)
- selekcja
- wybór nowej populacji na podstawie ocen starej
- metoda ruletki
- działanie losowe
- najlepiej dopasowany ma największe szanse
- zachowanie najlepszego osobnika ze starej populacji (elitaryzm)
- krzyżowanie
- działanie probabilistyczne:
c - stała wartość prawdopodobieństwa krzyżowania, e - wartość losowa (0, 1)
e >= c: krzyżowanie liniowe (linear crossover)
- z dwóch starych osobników “rodzi się” trzech potomków
- wybór dwóch najlepszych potomków do nowej populacji
e < c: stare osobniki przechodzą do nowej populacji
- mutacja
- działanie probabilistyczne:
m - stała wartość prawdopodobieństwa mutacji, e - wartość losowa (0, 1)
e >= m: osobnik jest poddawany mutacjie < m: osobnik pozostaje niezmieniony
- warunek zatrzymania
- populacja osiągnęła założoną ilość
g pokoleń (timeout)
- z populacji wyłonił się osobnik o dopasowaniu zbliżonym (z dokładnością
eps) do optimum globalnego
- populacja jest jednolita - zawiera osobniki różniące się względem siebie o pewna stałą
eps
Założenia projektowe
- program dla CPU - referencyjny (punkt odniesienia)
- kod źródłowy w C++ (preferowany standard C++11)
- działanie szeregowe + ewentualne rozszerzenie o wielowątkowość na bazie biblioteki Thrust
- program dla GPU - badany
- wykorzystanie biblioteki Thrust bazującej na NVIDIA CUDA
- kod źródłowy w C++ zgodny ze standardem C++11 (ze względu na kompatybilność z Thrust)
- podział kodu programu dla GPU na część host i device
- GPU realizuje zlecone działania przez wykonywanie tzw. rdzeni obliczeniowych (ang. “compute kernels”)
- rdzenie obliczeniowe:
- uruchamiane są przez procesor CPU - część host
- wymagają dostępu do pamięci i podprocedur alokowanych na procesorze GPU - część device
- wektoryzacja działań
- wynika z natury budowy procesora GPU - równoległość danych, SIMD wg. taksonomii Flynna
Implementacja
Uwagi ogólne
- podział algorytmu na etapy odpowiadające operatorom genetycznym
- operatory:
- selekcji
- krzyżowania
- mutacji
- oceny
- sposób na drobnoziarniste zbadanie czasu działania poszczególnych części algorytmu
Program dla GPU
- przeniesienie danych do pamięci GPU w celu uniknięcia niepotrzebnych transferów z/do CPU
- (pozostałe punkty z notatek uszeregowane wg. przynależonści do operatorów genetycznych)
Analiza eksperymentalna
Metoda badawcza
- uruchomienie programów CPU i GPU na wskazanych platformach sprzętowych
- pomiar czasu
t działania programów względem:
- liczebności populacji
n
- ilości wymiarów przestrzeni poszukiwań
dim
- pomiar jakości osobników końcowej populacji po upływie
g pokoleń
Wnioski
- porównanie wyników działania programów