foo / evo Goto Github PK

Fragment programu pomijający algorytm SGA. Trzeba sprawdzić i jakoś zwizualizować to, czy operatory krzyżowania psują dobrych osobników.

Funkcja przystosowania jest używana wielokrotnie w każdej iteracji. Powinniśmy ją policzyć tylko raz na iterację i spamiętać. Najlepiej zmodyfikować sga.cpp/hpp w taki sposób, żeby dodać funkcję evaluate_population, która liczy wartości osobników i ich funkcji przystosowania i przekazuje do mutation,crossover,replacement itp.

Modyfikacja funkcji mutation_function. Aktualnie wszscy osobnicy mutują co iterację, a chcielibyśmy żeby mutowały z pewnym prawdopodobieństwem. Prawdopodobieństwo można określić np. odwrotnie proporcjonalnie do współczynnika przystosowania.

Zamiast X iteracji możnaby sprawdzać, czy jest jakiś postęp przez ostatnie iteracje lub sprawdzać, czy wszyscy osobnicy to nie są kopie tego samego.

Cytuję kawałek treści naszego zadania ze strony Lipińskiego:

"Raport z wykonania projektu powinien zawierać zwięzłą dokumentację programu oraz opis wykonanych eksperymentów"

To też trzeba zrobić do środy i mu pokazać.

Proponuję wykorzystać fakt, że używamy githuba i taką dokumentację sporządzić w Wiki.

Chyba, że wolisz texa?

Zmontowanie wykresu przedstawiającego liczbę duplikatów w populacji w zależności od iteracji.

A raczej naprawienie. Trzeba zrobić tak, aby ładnie nam wykresiki zbiegały do optimum, a nie tak jak teraz jest. Utworzyłem nowy branch 'experimental' gdzie będę próbował znaleźć rozwiązanie tego problemu, a jednocześnie nie chcę nabroić za bardzo w oryginalnym kodzie, bo mam zamiar dużo stałych nawrzucać.

Na dobry początek zmieniłem plotowanie grafu PMX/OX/CX. Teraz są kolorki i jest wszystko widoczniejsze :)

Napisanie ciała funkcji evaluation z pliku main.cpp.
Funkcja ma symulować wykonanie N zadań na N maszynach i zwracać czas potrzebny na wykonanie wszystkich zadań.

Dodatkowy target w doc/makefile (najlepiej orir), nowy plik orir.tex.

Dobrze by uprzatnąc poprzednie dane testowe (nie wyrzucić - tylko ponazywać tak, żeby nie były first-class), prezentacje itp.

Napisanie programu przeszukującego przestrzeń permutacji, wykonującego zadaną liczbę ewaluacji. Dopisanie do programu ewolucyjnego zliczania liczby ewaluacji. Dla każdych danych testowych poza wynikiem programu ewolucyjnego znaleźć wynik, który uda się znaleźć w identycznej liczbie kroków programem brute-force.

Ten sam seed => funkcje liczyły to samo. Póki co jest ok, ale jak zaczniemy porównywać operatory pod względem skuteczności i wyjdzie nam, że działają z podobną skutecznością to powinniśmy jeszcze sprawdzić, czy przypadkiem nie są to te same funkcje.

\sum w_i T_i

Aktualnie w replacement odrzucamy najgorszych osobników. Takie rozwiązanie cechuje zbyt szybka zbieżność i utykanie w ekstremach lokalnych. Osobnicy powinni być usuwani z prawdopodobieństwem odwrotnie proporcjonalnym do wartości funkcji przystosowania.

Czasem się pętli, czasem nie.. głupie to. Poza tym jak uzywam 'fabs' to otrzymuje segfaulty? jak to możliwe?

W kodzie są takie stałe:

• liczność populacji
• długość łańcucha do krzyżowania
• ppb mutacji
  ...i pewnie jakieś jeszcze inne

Powinniśmy zrobić brainstorm, jakie jeszcze testy możemy przeprowadzić.

Zaprojektowanie (co mierzymy - co na x, co na y) i wykonanie wykresów dotyczących szybkości równoległego algorytmu.

Pierwsza propozycja: na x - na ile podpopulacji dzielimy - na y - jaki najlepszy wynik uzyskujemy po n sekundach, gdzie n jest parametrem programu.

Wykresy projektujemy przez dodawanie flag uruchomieniowych programu (np. --max-seconds 600) i ustalenie celu w doc/makefile, np.:

001.res: $(in_orir)/001.in
$(program) -e --max-seconds 600 --subpopulations 10 --population-size 200 < $< > $@

Pomysł nr 1:

Podział populacji na stałą liczbę populacji - eval, mutation każdej w osobnym wątku i join na końcu pętli SGA.

Modyfikacja funkcji crossover_function. Przy wyborze rodziców powinno być trochę losowości. Najlepiej wybierać rodziców z prawdopodobieństwem zależnym od funkcji przystosowania.

Napisanie generatora dla problemu szeregowalności. Napisanie wczytywania tych danych do programu.

Format:

W pierwszej linijce znajduje się liczba N.
W następnych linijkach znajduje się macierz NxN. Komórka (i,j) zawiera informację, że i-te zadanie wykonuje się na j-tej maszynie m[i][j] jednostek czasu.

Zmodyfikowanie programu tak, żeby dostawał optimum (jako argument linii komend) i kończył się dopiero po jego znalezieniu (lub przejściu --max-iter iteracji, gdzie max-iter - duże) i wypisywał ile iteracji mu to zajęło.

Zbiżamy się do pierwszej daty w terminarzu:
https://github.com/foo/evo/wiki/Terminarz

Do najbliższej środy musimy wysłać maila ze składem grupy do dr Lipińskiego. W tym mailu musimy też określić, jaką odmianą problemu się zajmujemy. Ja nie za bardzo wiem, co tam napisać, bo nie zajmujemy się żadną odmianą tylko pro prostu rozwiązujemy opisany problem. Niemniej coś trzeba napisać.

Należy też zaprezentować grupie rozwiązywany przez nas problem. Proponuję prezentację złożyć na wiki:

https://github.com/foo/evo/wiki/Prezentacja-wstępna

W treści zadania jest jeszcze CX, OX. Trzeba by je znaleźć, rozkminić, zaklepać i dopisać do pliku mutation.cpp.