1 Algorytmy genetyczne

2 Założenia Milestone 3 Pełna funkcjonalność GUIWizualizacja graficzna populacji chromosomów Statystyka uruchomienia (liczba pokoleń, jakość rozwiązań, wykres dążenia do rozwiązania optymalnego) Implementacja reszty problemów wraz z wizualizacją

3 Wygląd GUI

4 Zaimplementowane API dla zewnętrznych problemówPosiadanie funkcjonalności dzięki której tworzenie kolejnych przypadków użycia algorytmu genetycznego jest nad wyraz proste

5 Implementacja algorytmówZaimpementowanie algrytmów genetycznych które wykorzystują krzyżowania, mutacje oraz możliwość włączenie genów recesywnych

6 Zaawansowane algorytmy selekcjiImplementacja w interfejsie algorytmu możlwiości rozwiązywania problemu dotyczącego minimum lokalnego Elita Ruletka Ranking

7 Rozwiązania problemówProblem komiwojażera

8 Problem komwojażera Problem komiwojażera (TSP - ang. traveling salesman problem) jest to zagadnienie z teorii grafów, polegające na znalezieniu minimalnego cyklu Hamiltona w pełnym grafie ważonym. Nazwa pochodzi od typowej ilustracji problemu, przedstawiającej go z punktu widzenia wędrownego sprzedawcy (komiwojażera): dane jest n miast, które komiwojażer ma odwiedzić, oraz odległość pomiędzy każdą parą miast. Należy znaleźć najkrótszą trasę wychodzącą np. z Kutna i przechodzącą jednokrotnie przez wszystkie pozostałe miasta i wracającą do Kutna. Problem ten jest NP trudnym.

9 Problem komwojażera cd..Rozwiązywanie tego problemu metodą matematyczną wymaga wielkich nakładów mocy obliczeniowej, a także czas samych obliczeń jest bardzo długi. Już przy 20 miastach, liczba możliwych rozwiązań wynosi 19!/2 czyli około Dlatego najefektywniejszym rozwiązaniem tego problemu jest użycie algorytmu genetycznego oraz samej idei ewolucji. Osobniki nowopowstałe poddawane są testowi na długość ścieżki liczonej, w naszym przypadku, liczone wg wzorów euklidesowych, ta wartość jest brana jako główne kryterium tworzenia kolejnego pokolenia.

10 Dolina bananowa Rosenbrocka

11 Dolina bananowa RosenbrockaZnany i (nie)lubiany test algorytmów optymalizacyjnych Wzór F(x,y) = (1-x) (y-x2)2 Długa i płaska dolina, trudne do odnalezienia minimum

12 „Sinusowa kratka”

13 „Sinusowa kratka” Kilka minimów o podobnej jakościWzór F(x,y)=cos2(x) + cos2(y) + cx2 + cy2 Idealne do testowania problemu z „niszami ekologicznymi”

14 Nisze ???

15 Metodologia i organizacja pracyZdalne spotkania poprzez gtalk, gg Studencka organizacja czasu Eksponencjalna efektywność wraz ze zbliżaniem się terminu

16 Ryzyka Awaria laptopa Niespodziewany poziom skomplikowania niektórych modułów

17 Co można jeszcze poprawić…