OzWSI/LSN

From WikiZMSI

Spis treści 1 Laboratoria 1 --- Symulowane wyżarzanie 2 Laboratoria 2 --- Strategie ewolucyjne lub ewolucja różnicowa 3 Laboratoria 3 --- Particle swarm optimization lub firefly optymization 4 Laboratoria 4 --- Algorytmy mrówkowe

Laboratoria 1 --- Symulowane wyżarzanie

Celem laboratorium jest implementacja symulowanego wyżarzania dla jednego z wybranych problemów

1. n-hetmanów
2. komiwojażera z n miastami
3. binarnego problemu plecakowego z n obiektami.

Wymagane elementy programu:

1. zadawana wymiarowość problemu n
2. stan problemu (kandydat na rozwiązanie) reprezentowany jest jako:
   1. lista ustawień hetmanów w wierszach (każdy hetman ustawiony jest w innej kolumnie),
   2. lista miast odwiedzanych po kolei przez komiwojażera,
   3. lista elementów w plecaku
3. stan początkowy ma być losowany
4. funkcją celu
   1. zlicza parami atakujących się hetmanów, zatem oczekiwanym globalnym optimum jest wartość funkcji = 0;
   2. liczy sumę odległości pomiędzy miastami odwiedzonymi przez komiwojażera (z ostatniego miast trzeba pojechać do pierwszego); odległość całkowita ma być minimalizowana
   3. liczy zysk z obiektów w plecaku lub zysk dzielony przez wagę; poszukujemy takiego zestawu elementów, który daje największy zysk, ale nie przekracza wagowego ograniczenia plecaka
5. funkcja generująca sąsiedni stan.
   1. przesuwa losowo wybranego hetmana do losowo wybranego pustego pola dozwolonego dla danego hetmana; w wariancie steepest powinna generować listę wszystkich możliwych przesunięć;
   2. zamienia losowo wybrane dwa miasta; w wariancie steepest powinna zmieniać parami wszystkie miasta
   3. dodaje lub odejmuje elementy z plecaka
6. temperaturę początkową ustalić jako
   1. Uruchomić procedurę generowania potomków k razy
   2. Obliczyć dla każdego potomka E
   3. Obliczyć odchylenie standardowe z E w próbie k
   4. T0, czyli temperatura początkowa jest równa odchyleniu standardowemu
7. rozkład temperatury ustalić jako Tk+1=Tk*0.95
8. warunkiem zatrzymania powinna być liczba wykonanych kroków i brak zmian w funkcji celu po wykonaniu pewnej zadanej liczby prób
9. program po wykonaniu optymalizacji powinien wyświetlać:
   • stan, który został wskazany przez program jako rozwiązanie i jego wartość funkcji celu
   • demonstrować w postaci listy/wykresu zmienność wartości funkcji celu w procesie optymalizacji (w krokach)
10. uruchomić algorytm dziesięciokrotnie i podać średnie wyniki z najlepszych znalezionych rozwiązań. Porównać wyniki.

Każde własne propozycje lub wykorzystane z literatury techniki doboru parametrów lub prezentacji wyników będą dodatkowo punktowane.

Termin oddania programu to 18.12.2016

Laboratoria 2 --- Strategie ewolucyjne lub ewolucja różnicowa

Celem laboratorium jest implementacja strategii ewolucyjnej lub ewolucji różnicowej dla rzeczywistoliczbowego problemu optymalizacyjnego. Szczegóły implementacji:

1. Parametrem programu ma być optymalizowana funkcja. Na stronie Go test problem lub Virtual Library... dostępna jest lista funkcji testowych. Algorytm należy przetestować na funkcji wielomodalnej Griewank, jednomodalnej Rosenbrock i Easom.
2. Strategie ewolucyjne:
   1. implementacja selekcji plus lub comma
   2. parametry (np. liczność populacji) zadawane jako parametr
   3. operacje (krzyżowanie/mutacja) na osobnikach wykonywane zgodnie z opisem z ćwiczeń
3. Ewolucja różnicowa
   1. podawanie parametrów metody jako parametr
   2. operacje krzyżowania i mutacji zgodnie z opisem z ćwiczeń
4. Wynikiem działania programu ma być położenie znalezionego przez algorytm optimum (może być też odległość od znanego globalnego optimum), wykres zmienności przystosowania najlepszego osobnika w generacjach, średnie przystosowanie populacji
5. Warunkiem zatrzymania może być z góry zadana maksymalna liczba generacji lub uzyskanie błędu optymalizacji mniejszego niż zadany

Termin oddania programu to 15.01.2017

Laboratoria 3 --- Particle swarm optimization lub firefly optymization

Celem laboratorium jest implementacja PSO lub firefly optymization dla rzeczywistoliczbowego problemu optymalizacyjnego. Szczegóły implementacji:

1. Parametrem programu ma być optymalizowana funkcja. Na stronie Go test problem dostępna jest lista funkcji testowych. Algorytm należy przetestować na funkcji wielomodalnej Griewank, jednomodalnej Rosenbrock i Easom.
2. Dla PSO
   1. Podawanie paramtrów wpływu "indywidualnego" i "społecznego" oraz wagi dla bezwładności.
   2. Jako dodatek (nieobowiązkowo) można zaimplementować różne formy sąsiedztwa.
3. Dla Firefly

1. Wynikiem działania programu ma być położenie znalezionego optimum (może być też odległość od znanego globalnego optimum), wykres prezentujący zmienność położenia najlepszej cząstki w roju, jako dodatek wizualizacja roju na powierzchni optymalizowanej.
2. Warunkiem zatrzymania jest z góry zadana maksymalna liczba generacji lub uzyskanie błędu optymalizacji mniejszego niż zadany.

Termin oddania programu to 15.01.2017

Laboratoria 4 --- Algorytmy mrówkowe

Celem laboratorium jest implementacja algorytmu Ant Colony Optimization dla jednego z wybranych problemów:

1. n-hetmanów
2. komiwojażera z n miastami
3. binarnego problemu plecakowego z n obiektami.

Parametry, które mogą być zmienne dla ACO, to:

• n - rozmiar problemu
• liczba mrówek
• maksymalna liczba iteracji
• parametry alfa i beta dla ant-routing table
• ilość rozkładanego feromonu powinna być kontrolowana wielkością ro
• początkowa wartość feromonu

Wyniki powinny demonstrować zmienność rozwiązań w iteracjach, pokazywać najlepsze znalezione rozwiązanie.

Termin oddania programu to 29.01.2017