21.03.2016 - Institute Seminar - 13:00, Eryk Laskowski (ICS PAS)

21 03 2016 laskowski

Optymalizacja Ekstremalna (ang. Extremal Optimization, EO) jest efektywną metaheurystyką optymalizacyjną, należącą do dziedziny metod ewolucyjnych. Charakteryzuje się niską złożonością czasową i pamięciową, i jest szczególnie przydatna do rozwiązywania problemów optymalizacji kombinatorycznej. Referat przedstawi prace dotyczące zarówno zastosowania metody EO do rozwiązywania złożonych problemów równoważenia obciążeń procesorów obliczeniowych w systemach rozproszonych, jak również rozwinięcia samej metody EO, opracowane w ostatnim czasie w ZAK IPI. Zaprezentowany zostanie algorytm Optymalizacji Ekstremalnej ze Sterowaną Zmianą Stanu (ang. Extremal Optimization with Guided Search, EO-GS), który jest efektywnym rozszerzeniem klasycznej metody EO o zmianę stanów systemu sterowaną wiedzą dziedzinową (w miejsce całkowicie losowej zmiany stanu stosowanej w oryginalnej metodzie EO).

Metaheurystyka EO-GS została zastosowana w nowym algorytmie równoważenia obciążenia procesorów w systemie rozproszonym. Algorytm ten zaimplementowano w symulatorze rozproszonego systemu równoległego SimDevs, działającym w oparciu o formalizm DEVS. Kolejnym etapem badań było opracowanie równoległej Optymalizacji Ekstremalnej (ang. Parallel Extremal Optimization). W ramach tych badań rozwinięto ogólną metodologię zrównoleglenia algorytmu EO i zidentyfikowano różne warianty równoległego przeszukiwania przestrzeni rozwiązań w algorytmie EO i EO-GS.

Zaproponowane algorytmy zostały poddane badaniom eksperymentalnym, polegającym na równoważeniu obciążenia w trakcie symulowanego wykonywania aplikacji rozproszonych.

ATTENTION! This site uses cookies and similar technologies.

If you do not change your browser settings, you automatically agree to this.

I understand