Logowanie do System sprawozdań KDM

Algorytmy harmoniczne do optymalizacji na superkomputerach

Kierownik projektu: Łukasz Gil

Politechnika Gdańska

Wydział Elektroniki, Telekomunikacji i Informatyki

Gdańsk

Streszczenie projektu

Projekt dotyczy jednego z rodzajów algorytmów sztucznej inteligencji, algorytmu harmonicznego. Algorytm ten zostanie wykorzystany do rozwiązywania problemu komiwojażera dla różnych danych wejściowych. Rozwiązanie tego problemu minimalizacyjnego polega na znalezieniu najkrótszego cyklu Hamiltona dla zadanego zbioru wierzchołków.



Algorytm harmoniczny został zainspirowany improwizacją jazzową. Tak, jak muzycy podczas improwizacji dążą w kolejnych próbach do uzyskania jak najbardziej zgranego, harmonicznego brzmienia, tak samo rozwiązania w implementacji algorytmu dążą do uzyskania jak najlepszego, modyfikując i dopasowując zbiór rozwiązań przechowywane w pamięci. Rozwiązania porównywane są za pomocą funkcji celu, w przypadku problemu komiwojażera będzie to długość ścieżki. Przebieg algorytmu można przedstawić w poniższych krokach:



1) Inicjalizacja parametrów algorytmu



a) HMS - wielkość pamięci algorytmu(ilość przechowywanych rozwiązań)



b) HMCR - tempo wyboru wartości zmiennych z pamięci



c) PAR - tempo modyfikacji wartości zmiennych z pamięci



d) BW - maksymalny przedział modyfikacji rozwiązania parametrem PAR



e) NG - maksymalna ilość iteracji(improwizacji)



2) Inicjalizacja pamięci harmonii - losowe wartości jako rozwiązania



3) Generowanie nowej improwizacji. Dla każdej pozycji miasta i w nowym rozwiązaniu



a) Losujemy liczbę phmcr z przedziału [0;1]



i) jeśli jest mniejsza niż HMCR - na pozycję i wstawiamy losowe miasto ze zbioru jeszcze nie wybranych



ii) w przeciwnym razie, wybieramy losowo jeden z istniejących wektorów rozwiązań j. Następnie losujemy liczbę ppar z przedziału [0;1], jeśli jest większa niż PAR - na pozycję i wstawiamy odpowiadające miasto z rozwiązania j. W przeciwnym razie - losujemy liczbę k z przedziału [-BW;BW] i na pozycję i wstawiamy miasto z pozycji i + BW z wektora j



4) Po wygenerowaniu nowego rozwiązania, oceniamy je funkcją celu i porównujemy z najgorszym z pamięci. Jeśli nowe jest lepsze - podmieniamy najgorsze.



5) Algorytm kończy działanie, gdy osiągniemy ilość iteracji równą NG.



Uzyskanie rozwiązania optymalnego algorytmowi w wersji sekwencyjnej może zająć, w zależności od danych wejściowych oraz losowanych parametrów nawet kilkaset milionów iteracji. Równoległe wykonywanie obliczeń może zdecydowanie poprawić wydajność algorytmu. Wybór pojedynczego miasta do nowego rozwiązania jest operacja niezależną od wyboru pozostałych miast, co otwiera drogę do prostego zrównoleglenia obliczeń.



Zrównoleglenie algorytmu będzie polegało na równoczesnym generowaniu nowych miast na wszystkich pozycjach w nowym rozwiązaniu. Zostanie wydzielony jeden węzeł master, który będzie zarządzał wykonaniem algorytmu, przechowywał pamięć harmonii oraz dbał, aby prawidłowo uzupełniać nowe rozwiązanie, tzn. aby miasta w cyklu się nie powtarzały (będzie to realizowane w ten sposób, że przed dodaniem miasta każdy węzeł będzie odpytywał mastera, czy dane miasto nie zostało już wykorzystane). Pozostałe węzły będą wykonywały przydzielone obliczenia i wysyłały wyniki do mastera.



Implementacja algorytmu nie wymaga żadnych zewnętrznych bibliotek. Obliczenia będą realizowane przy pomocy protokołu MPI, nie jest wymagana nawet żadna biblioteka do operacji matematycznych. Implementacja zostanie wykonana w języku C, przy użyciu standardowych bibliotek.

Centrum Informatyczne Trójmiejskiej Akademickiej Sieci Komputerowej
ul. G. Narutowicza 11/12, 80-233 Gdańsk   |   tel. 58-347-24-11
email: office@task.gda.pl   |   NIP: 584-020-35-93