[C++][Sieć Neuronowa jednokierunkowa][Algorytm genetyczny] Kilka pytań

[Firez]

Witam,
Tworzę w ramach nauki oraz na własne potrzeby silnik prostej sieci neuronowej w c++. Jest to sieć jednokierunkowa (tzn feedforward). Jako 'algorytmu' uczącego używam algorytmu ewolucyjnego (rozmnażam moje sieci, mutuję dzieci, zabijam gorszą połowę sieci i tak w nieskończoność).
Mam kilka pytań:
1. Wybrałem ten (dość nieoptymalny algorytm), gdyż spodziewam się by moja sieć potrafiła przewidywać zjawiska które są częściowo losowe (np. mamy 6 kostek, korzystając z kostki nr 1 mamy większą szansę na to, że wyrzucimy jedynkę; chcę by sieć potrafiła przewidzieć średni wynik rzutu jeśli znany jest numer kostki (to tylko przykład)). Czy mam rację twierdząc, że algorytm propagacji wstecznej nie sprawdzi się w takich warunkach?

2. Moja sieć działa na liczbach całkowitych (int) - zapisuję tak bias, wagi neuronów, punkt strzału neuronu. Wyjście neuronu to -1 lub 1 (w zależności od przekroczenia progu wystrzału). Na wejściowe i wyjściowe neurony (tzn te z pierwszej i ostatniej warstwy) odpowiednio ustawiam i spodziewam się cyfr binarnych (np wejście 1 0 wyjście 1 w przypadku xor'a). Czy to jest sensowne podejście? Kiedyś pisałem sieci oparte o float i wydawały mi się one mniej optymalne [chociaż poprzednia sieć była w java a ta jest w c++ więc trudno je bezpośrednio porównywać].

3. 80% czasu działania skrypt poświęca na 'strzelanie' neuronami, 15% na ich rozmnażanie, 5% na ich mutację (w przypadku sieci 3,2,2,2 (4 warstwowa o danej liczbie neuronów)). Czy taka statystyka jest mniej więcej sensowna?

4. Eksperymentował ktoś z sieciami zmieniającymi własności środowiska? Typu stopień mutacji, wielkość stada? Osiągnęliście jakieś sensowne efekty?

5. Myślę o systemie zapobiegającym utknięciu sieci w lokalnym maksimum. Zastanawiałem się dlaczego prawdziwa ewolucja nie utknęła w lokalnym maksimum. Myślę, że jednym z czynników jest odległość pomiędzy osobnikami. Planuję stworzyć np. 128 różnych środowisk, każde z nich będzie oddzielnie ewoluować przez jakiś czas. Następnie zacznę 'łączyć kontynenty' doprowadzając do zetknięcia się parami różnych stad. Przeżyją ofc tylko najlepsze osobniki. Będę je łączyć do czasu uzyskania 1 stada. Ktoś próbował czegoś podobnego? Czy takie podejście ma jakiś sens?

Dziękuje za wszystkie odpowiedzi .

[Kosz85]

1. Zależy jak tego będziesz uczyć, bo jeśli chcesz uczyć średni wynik rzutu, to nie widzę tego sensu, propagacja wsteczna będzie dużo bardziej skuteczna. Uczysz średniego rzutu, czyli na wyjściu z sieci oczekujesz tej średniej (musisz ją wyliczyć), a na wejściu dajesz nr kostki. Czyli tak naprawdę uczysz sieć: nr kostki -> średnia z rzutów, czyli stałych liczb, tyle tylko, że średnia nie jest dokładna na początku. Właściwie czego ma się tu uczyć sieć, skoro średnia już jest wystarczająco dobrym oszacowaniem? Przykład bez sensu.

2. Eeee? na liczbach całkowitych? Chyba na stało przecinkowych(też się robi na intach)? Jak sobie wyobrażasz by to działało? Wagi muszą być liczbami rzeczywistymi, szczególnie dla wyjścia neuronu -1 i 1, nie napisałeś też nic o funkcji aktywacji, chyba że to ADALINE. Co zrobisz gdy będzie trzeba będzie dodać do wagi 0.01, co będzie miało miejsce w 90% przypadków?
I co to jest ten strzał neuronu? Nie wydaje mi się byś pisał o sieciach spajkujących.
Tu masz o stałoprzecinkowych: p://sharpneat.sourceforge.net/integer_network.html
Ale radzę korzystać z typu double.

3. Na co sieć 4 warstwowa? chyba, że liczysz wejście i wyjście, czego się zwykle nie robi.
Skąd te procenty? prawdopodobnie 80% powinien zajmować proces ewolucji, który jest mniej wydajny.

4. Bawiłem się, po testuj, niestety większość zależy od problemu i większość daje się sprowadzić do problemu standardowego

5. Skąd wiesz, że prawdziwa ewolucja nie utknęła w lokalnym maksimum?, stwierdziłbym raczej przeciwnie. Jedyna różnica w życiu jest taka, że funkcja oceny się zmienia z czasem i bywa różna dla różnych osobników. Możesz to imitować posiadając zestaw danych uczących i losować (jeden zestaw lub kilka) do których osobniki dążą w danej epoce (minimalizują błąd).
Kilka grup osobników(nie koniecznie tak duża jak 128), ocenianych w obrębie własnych grup i co jakiś czas wymieniające osobniki (co epokę z jakimś małym prawdopodobieństwem) to całkiem niezła taktyka. Selekcja raczej turniejowa.

Poczytaj zarówno o metodach ewolucyjnych, uczeniu maszynowym jak i samych sieciach neuronowych. O metodach ewolucyjnych dobra książka jest Arabasa, o uczeniu maszynowym "Systemu uczące się" Pawła Cichosza, o sieciach neuronowych napisano już wiele. I lepsza pewnie będzie propagacja wsteczna, a na pewno szybsza 

[JCoder]

Zamiast AE spróbuj zastosdować VNS (variable neighbourhood search). Lepsze niż AE praktycznie w każdym przypadku (zbiega tak szybko jak back-propagation, ale nie utyka w maksimach lokalnych) i na dodatek prostsze w implementacji i ma mniej parametrów. I mniej pamięciożerne.

Ad 4: Eksperymentowałem. Wielkość stada ma małe znaczenie. Krzyżowanie nie ma znaczenia praktycznie w ogóle. Największe znaczenie ma chyba dobór odpowiedniej strategii selekcji i zastępowania osobników. Ale zapewne zależy to mocno od problemu. Z AE jest ten problem, że parametrów jest dużo, a i tak większość nie ma wyraźnego wpływu na działanie... Szczególnie dla złośliwych funkcji celu można kręcić tymi gałkami na tysiące sposóbów a i tak nie chce być dużo lepiej. Z kolei dla łatwych funkcji celu, nawet totalnie rozregulowany AE działa bardzo sprawnie.

[Firez]

1.

1. Zależy jak tego będziesz uczyć, bo jeśli chcesz uczyć średni wynik rzutu, to nie widzę tego sensu, propagacja wsteczna będzie dużo bardziej skuteczna. Uczysz średniego rzutu, czyli na wyjściu z sieci oczekujesz tej średniej (musisz ją wyliczyć), a na wejściu dajesz nr kostki. Czyli tak naprawdę uczysz sieć: nr kostki -> średnia z rzutów, czyli stałych liczb, tyle tylko, że średnia nie jest dokładna na początku. Właściwie czego ma się tu uczyć sieć, skoro średnia już jest wystarczająco dobrym oszacowaniem? Przykład bez sensu.

Miałem na myśli przypadek gdy średnia jest nieznana. Niemniej możliwe, że rzeczywiście ten przykład jest bez sensu. Chodziło mi o tą grupę zjawisk w których wyniki są zaburzane przez nieznane nam zjawiska losowe.
Kolejny wymyślony przykład - strzelanie piłeczkami (z jakiegoś automatu) w ścianę. Input sieci - np. siła i kąt wystrzału. Output sieci - odległość na jaką odtoczy się piłka po odbiciu się od ściany. Zaburzenia generuje nam wiatr którego siły nie znamy, zakładam także iż niemożliwe jest rozwiązanie hm 'statystyczne' (tzn nie możemy zmierzyć wszystkich sił, kątów wystrzału i zmierzyć odległości na jaką odtoczy się piłka a potem uśrednić wyników, załóżmy że mamy jedynie dane z kilkuset prób przy różnych ustawieniach).
Przykład może i nie jest nadal idealny niemniej chyba wystarczy do dalszych rozważań . Mam wrażenie, że algorytm wstecznej propagacji nie poradzi sobie w takich warunkach (?) Czy w takim przypadku sieć może się przyuczyć jedynie do pojedynczej siły wiatru? A jeśli w danej chwili pojawił się niestandardowo silny podmuch nasza sieć będzie zwracać wyniki z dużym błędem podczas testów?
Drugi przykład, który mi przychodzi do głowy (powiązany z gamedev) - sieci neuronowe symulujące komputerowego gracza w grze strategicznej podobnej do np. Starcraft. Zakładam, iż mamy już napisane skrypty typu 'wybuduj marine', 'wybuduj nową bazę' a nasza sieć decyduje jedynie kiedy je wykonać (na podstawie np. inputu typu kiedy wystąpił ostatni atak, ile zostało nam surowców). Czy takie sieci da się trenować w sposób inny niż ewolucyjnie (mam wrażenie iż strategia turniejowa byłaby tu idealna).

2.

Jak sobie wyobrażasz by to działało? Wagi muszą być liczbami rzeczywistymi, szczególnie dla wyjścia neuronu -1 i 1

Rzeczywiście, przemyślałem to jeszcze raz i moje podejście było błędne. Testowałem swoją sieć jak na razie dla funkcji typu xor i prostych przejść bitów w bity (coś podobnego do map Karnaugha). W takich warunkach sieć sobie radziła ale pewnie zaczęłaby mieć problemy przy bardziej skomplikowanych funkcjach.

nie napisałeś też nic o funkcji aktywacji

Trochę przeinaczyłem pojęcie, pisząc o 'punkcie strzału neuronu' miałem na myśli właśnie funkcje aktywacji (u siebie użyłem coś podobnego do  sgn(x) ).

Ale radzę korzystać z typu double.

Tak zrobię .

3.

chyba, że liczysz wejście i wyjście, czego się zwykle nie robi.

Właśnie tak zrobiłem . Miałem na myśli sieć o dwóch warstwach ukrytych.

prawdopodobnie 80% powinien zajmować proces ewolucji, który jest mniej wydajny.

Hmm czyli możliwe, że mam złe podejście (u mnie rozmnażanie i mutacja razem zajmuje 20%). Jakie macie podejście do mutacji? U mnie to wygląda tak:

Kod:

                        int random2 = rand()%20;//Liczba mutacji
for(int j=0; j< random2; ++j)
{
int random = rand()%5;
if(random == 1) network[i]->mutateBias();//Zmiana wartości bias losowego neuronu
else if(random == 2) network[i]->mutateFirePoint();//Zmiana progu aktywacji neuronu
else network[i]->mutateDendrite();//Dodanie, usuniecie badz zmiana wagi losowego dendrytu
}

'Magic numbers' zmieniają się w zależności od sieci. (w wersji finalnej dla czystości kodu prawdopodobnie zamienię liczby na stałe) Zmieniając liczby odkryłem, że najlepsze efekty daje częstsza mutacja dendrytów niż właściwości neuronu (ale to może zależało mocno od funkcji której użyłem?)


4.

Wielkość stada ma małe znaczenie.

Eksperymentując ze swoim kodem też miałem takie wrażenie. Stado zwykle stanowi grupa prawie identycznych sieci neuronowych, potomków najlepszego (ostatnio) osobnika.

Krzyżowanie nie ma znaczenia praktycznie w ogóle.

Hmm prawdę mówiąc chyba porządne krzyżowanie jest trudne do zaimplementowania. Chyba sensowne może być jedynie krzyżowanie osobników bardzo podobnych, a więc trzeba by było napisać jakąś funkcję do oceny podobieństwa obu sieci ( dlatego w prawdziwym życiu ryba nie krzyżuje się z kotem; btw właściwie ciekawe jakie efekty dałyby trzy-płciowe sieci).

5.

Skąd wiesz, że prawdziwa ewolucja nie utknęła w lokalnym maksimum?

Ojć, zgubiłem słówko, miałem na myśli pojedyncze lokalne maximum - dlaczego wszystkie organizmy nie są identyczne (przynajmniej w tych samych warunkach) co często występuje w środowiskach symulowanych. (oczywiście oprócz naturalnych barier terenowych istnieją inne czynniki ale chyba nie da się ich odwzorować tak dobrze w komputerowo symulowanym środowisku)

Poczytaj zarówno o metodach ewolucyjnych, uczeniu maszynowym jak i samych sieciach neuronowych. O metodach ewolucyjnych dobra książka jest Arabasa, o uczeniu maszynowym "Systemu uczące się" Pawła Cichosza, o sieciach neuronowych napisano już wiele. I lepsza pewnie będzie propagacja wsteczna, a na pewno szybsza

Zamiast AE spróbuj zastosdować VNS (variable neighbourhood search). Lepsze niż AE praktycznie w każdym przypadku (zbiega tak szybko jak back-propagation, ale nie utyka w maksimach lokalnych) i na dodatek prostsze w implementacji i ma mniej parametrów. I mniej pamięciożerne.

Dzięki poczytam .

[Kosz85]

Ad 1. Dalej średnia z próby jest tu już wystarczająco mocnym estymatorem, więc tamten przykład nie miał sensu.
Co do drugiego przykładu, to w takich warunkach nic sobie nie poradzi, prócz jasnowidza. Chyba, że wiatr jest w miarę stały pomiędzy kolejnymi epokami, a sieć ma na wejściu przykładowo dane poprzednio przeprowadzonej próby, wraz z wynikiem. Tak by sieć mogła jakoś estymować siłę wiatru, bo tak z niczego jej nie weźmie. Dla sieci będzie to wyglądało tak, że raz 2+2=4, a innym razem 2+2=35, takiej matematyki nie sposób się nauczyć. Inna sprawa, że sieć może próbować oszacować tą siłę wiatru, z jakichś zupełnie abstrakcyjnych danych, typu obraz z kamery przedstawiający drzewo na które również oddziałuje ten wiatr. Ale jakąś informacje musi o nim mieć, bo wartości od tak nie zgadnie.
Jeśli chodzi o tak zdefiniowany przykład, to propagacja wsteczna sobie poradzi. Algorytm ewolucyjny nie jest żadną cudowną metodą, to inny sposób rozwiązywania tego samego problemu. AE używa się między innymi np. dla sieci o zmiennej topologii (dzięki czemu algorytm może optymalizować również rozmiar sieci), lub topologii nie pozwalającej użyć wstecznej propagacji.
Jeśli chodzi o podmuchy i błąd, to w tym momencie zależy od tego co dasz na wejściu, co powinieneś już zauważyć. No i uczenie sieci powinno przebiegać w warunkach dużej dynamiki wiatru, by sieć nie nauczyła się pojedynczej wartości. Kwestia doboru odpowiedniego zbioru uczącego, jak w każdym innym problemie. Jak dasz zbiór uczący z samymi jedynkami, to nie oczekuj dwójki proste.
Co do Starcrafta, to czemu nie miałoby się tego dać zrobić na propagacji wstecznej? Jeśli tworzysz jedynie system decyzyjny, co w danym momencie robić, to czemu nie? Ale sama sieć może nie wystarczyć, lepiej połączyć to z jakimś algorytmem uczenia przez wzmacnianie, o czym pisaliśmy dzisiaj w temacie obok
Chodzi o to, że sieć jedynie ocenia, czy dana decyzja w danej sytuacji zadanej jej na wejście (numer decyzji (lub 1 na wejściu odpowiadającej danej decyzji) + opis świata, stan jednostek, itp) jest korzystny czy nie i w jakim stopniu. Potem obserwuje jak ta decyzja wpłynęła na rozgrywkę, czy zyskała, czy straciła i odpowiednio premiuje tą decyzję (czyli uczy sieć bardziej pozytywnie reagować, lub bardziej negatywnie na zadany opis świata i decyzję). W Cichoszu możesz o tym poczytać, książkę powinieneś znaleźć na osiołku, lub bibliotece jakiejś politechniki

Ad 3. Może po prostu stosunkowo wolna implementacja sieci? Albo populacje w AE masz niewielkie.
[EDIT] [nie pomyślałem, dla stosunkowo dużego zbioru uczącego, przepropagowanie wszystkich danych przez sieć dla każdego osobnika by policzyć błąd faktycznie jest udręką, więc prawdopodobnie te 80% na działanie sieci jest poprawne ]
 Podejść do mutacji jest tyle ile podchodzących do problemu. Ogólnie jeśli chodzi o AE:
    - niech dodatkowo najlepszy zawsze przechodzi do nowej populacji w niezmienionej formie (co niekoniecznie się dzieje np w Turniejach, lub mutacji)
    - mutacja niech dzieje się jedynie dla pewnego % populacji, nie dla wszystkich.
    - mutacja niech polega na pojedynczej zmianie którejś wagi, chyba że chcesz się bawić w dodawanie usuwanie całych neuronów i topologi bez połączeń każdy z każdym, ale tylko utrudniasz sobie sprawę.
    - jako selekcję, lubię turnieje, zwykle o wielkości 3
    - krzyżowanie.. raczej bym odpuścił, dla pełnej sieci.

Nie wiem czym jest dla ciebie dendryt Próg aktywacji też zdaje się dziwny, ale chyba się domyślam. Standardowy Neuron, standardowej sieci, skałda się z nurona, wag i funkcji aktywacji. Bias to też jakby waga, tylko że do jedynki, zamiast do neuronu z poprzedniej warstwy, na wyjściu neuron ma jakiegoś floata, będącego sumą wag przepuszczoną przez np sgn()

AD 4. Nie wiem ile liczy grupa, być może zbyt mało, być może dałeś zbyt duży nacisk selektywny na swoje grupy. Ale ogólnie to tak jest, że jak masz górkę, a chcesz dojść na szczyt (osobnik to pozycja), to wszystkie dobre osobnik będą wokół szczytu górki, czyli będą bardzo podobne. Chyba, że masz dwie lub więcej górek wtedy się robi ciekawiej
Dobra, to napisze ciut o krzyżowaniu. Krzyżowanie jest ważne, ale powinno być stosunkowo rzadkie i stosuje się je dla sieci o zmiennej topologi, gdzie sieć może sobie dodawać neurony, usuwać, czasem jeszcze może się łączyć pomiędzy neuronami, czasem nawet nie musi być zorganizowana w warstwy jest tylko wejście i wyjście, oraz plątanina neuronów. Wtedy warto rozważyć krzyżowanie.

Hah i to koniec tego eposu Mam nadzieję, że się przyda.

[JCoder]

niech dodatkowo najlepszy zawsze przechodzi do nowej populacji w niezmienionej formie (co niekoniecznie się dzieje np w Turniejach, lub mutacji)

Ryzykowne. Łatwo wtedy zdominować populację jednym osobnikiem i stracić całą różnorodność - czyt. przedwczesna zbieżność.
Trzeba mieć wtedy naprawdę silne (dalekie) mutacje, żeby nie zablokować sobie możliwości wyskakiwania z maksimów lokalnych.

Chyba, że masz dwie lub więcej górek wtedy się robi ciekawiej

Wtedy wszystkie bardzo szybko włażą na najwyższą z nich (a przynajmniej tak mówił na wykładzie J. Arabas), chyba że górki mają dokładnie tę samą wysokość.

[Kosz85]

Jeśli masz selekcję turniejową, wielkości 3 przy populacji 200, to już nie tak łatwo jest zdominować, a łatwo stracić najlepsze rozwiązanie, trzeba przynajmniej mieć je gdzieś zapamiętane. Co do mutacji, to i tak powinny być takie, by w miarę możliwości mogły wyskoczyć z lokalnych optimów. Nie koniecznie muszą być dalekie, wystarczy by dopuszczały taką możliwość, czyli np mutacja rozkładem normalnym.
Bo zauważ, że turnieje nie dominują tak łatwo populacji najlepszym osobnikiem, dlatego jest to tak dobra metoda selekcji. Moim zdaniem lepsza od ruletki, czy wzięcia samych najlepszych.

Co do dwóch górek Też byłem na tym wykładzie i nie przekręcaj nazwiska Arabas, to moje rodzinne I w zachowaniu osobników to jest właśnie to "ciekawe" i nie wchodzą wcale od razu na drugą górkę, tylko przez pewien czas są na obu. Jeśli na wyższej górce jest jeden osobnik, to wręcz może się zdarzyć, że selekcja go odrzuci. W tym właśnie magia AE, by dobrze dobrać parametry i metody selekcji/mutacji/krzyżowania, by algorytm nie kładł bardzo dużego nacisku selektywnego, ale by jakiś jednak kładł. Ciężko znaleźć złoty środek. Osobniki muszą się móc nieco rozchodzić na inne górki, aby znaleźć inne, lepsze rozwiązania. Stąd całkiem niezłą metodą jest kilka odrębnych populacji, o czym Pan Arabas, również wspominał na wykładzie

[JCoder]

Ciężko znaleźć złoty środek

I to mi się właśnie nie podoba w AE.
Nawet nie wiesz, czy źle działa, bo źle dostroiłeś, czy bo masz gdzieś buga w kodzie.
Nawet są spory o kwestie tak podstawowe, czy krzyżowanie w ogóle jest do czegoś potrzebne.

Łatwo zrobić z tego papier, bo jest tyle parametrów/strategii, że zawsze można znaleźć tę jedną dla specyficznego przypadku i pokazać: "o, działa o 5% lepiej niż algorytm X!". Jednak w ogólniejszym przypadku, jest trudno, nie dostajesz nawet gwarancji na to jak daleko jesteś od maksimum globalnego (a niektóre heurystyki to dają: np. branch & bound + relaksacja). Śmieszne jest czasem, jak złożony problem AE potrafi rozwalić ładnie, a na problemie, gdzie na oko natychmiast widać jakie jest optymalne rozwiązanie, AE leży na całej linii.

Czasami wolę mieć algorytm, który deterministycznie podaje "w miarę dobre rozwiązanie" w ograniczonym czasie, niż algorytm, który "zwykle trafia", ale czasem masakrycznie zbłądzi (albo potrzebuje 100x więcej czasu by się wyplątać). Stąd właśnie bardziej bym się kierował w kierunku rozwiązań hybrydowych (np. AE ze wspinaczką, albo algorytm dokładny dokąd się da a później AE..., albo algorytm dokładny + heurystyczny pruning oparty o SONN itp. albo alg. dokładny dla podproblemów + jakaś heurystyka na wyższym poziomie -- możliwości jest naprawdę mnóstwo).

[Xion]

Ciężko znaleźć złoty środek

To jest właśnie problem między eksploracją (rozrzucaniem populacji po jak największej przestrzeni żeby mieć jak największą szansę znaleźć się w obszarze przyciągania minimum) a eksploatacją (przeszukiwaniem bliskiej okolicy populacji w celu poprawy aktualnie znalezionego rozwiązania). Te dwa cele na oko są ze sobą... może nie sprzeczne, ale na pewno konkurencyjne Intuicyjnie na przykład dobór operatora mutacji, który daje duży rozrzut populacji da dobre pokrycie przestrzeni, ale niekoniecznie pozwoli znaleźć rozwiązanie naprawdę najlepsze, itp. itd.

Jakimś wyjściem jest tu lekkie "zaplanowanie" przebiegu algorytmu w ten sposób, żeby we wczesnych fazach preferowana była eksploracja, a w późniejszych eksploatacja. Inaczej mówiąc, coś w stylu symulowanego wyżarzania - do wzorów np. na mutację dodajemy parametr zmniejszający się z każdą iteracją, który kontroluje możliwy zasięg mutacji.

Ale tak wracając do oryginalnego problemu, czyli czym uczyć sieć neuronową, to jednak powiedziałbym, że propagacją wsteczną

[Kosz85]

Dla mnie jasne jest, że AE używa się tam, gdzie inne metody zawodzą. Bo jest to metoda stosunkowo wolna i daje jedynie rozwiązania suboptymalne. Przecież od początku radzę użyć propagacji wstecznej Co nie znaczy, że nie można się pobawić AE, jako że metoda sama w sobie jest ciekawa.

Nawet nie wiesz, czy źle działa, bo źle dostroiłeś, czy bo masz gdzieś buga w kodzie.
Nawet są spory o kwestie tak podstawowe, czy krzyżowanie w ogóle jest do czegoś potrzebne.

Z tym bugiem to trochę przesadzasz AE jest na tyle proste do zaimplementowania, że ciężko zrobić rażące błędy. Ale z parametrami masz już sporo racji, trzeba dobrze poznać problem by odpowiednio ustawić parametry i poszczególne elementy składowe algorytmu. Jest to jednak metoda ostateczna, gdy inne szybsze zawodzą, albo są równie mało wydajne.
Z tym krzyżowaniem trochę przeinterpretowujesz. Krzyżowanie jest bardzo przydatne dla konkretnych klas problemów, być może nie trafiłeś na takie problemy. Krzyżowanie w optymalizacji funkcji, być może nie jest najlepszym pomysłem, chociaż można załatwić w ten sposób ciekawie eksplorację, ale np w problemach które jesteśmy w stanie za modelować na genach (algorytmy genetyczne), krzyżowanie jest bardziej niż wskazane.
Problemy gdzie takie krzyżowanie byłoby bardzo wskazane to np. problem rozdziału kilku zasobów pomiędzy zadania, czy odpowiednio dobrane krzyżowanie w funkcji wielu zmiennych, z wieloma okresowymi optimami. Ogólnie tam gdzie jest to specyfika problemu, bądź możesz wyróżnić kilka odrębnych elementów problemu wymagających optymalizacji.

Czasami wolę mieć algorytm, który deterministycznie podaje "w miarę dobre rozwiązanie" w ograniczonym czasie, niż algorytm, który "zwykle trafia", ale czasem masakrycznie zbłądzi (albo potrzebuje 100x więcej czasu by się wyplątać). Stąd właśnie bardziej bym się kierował w kierunku rozwiązań hybrydowych (np. AE ze wspinaczką, albo algorytm dokładny dokąd się da a później AE..., albo algorytm dokładny + heurystyczny pruning oparty o SONN itp. albo alg. dokładny dla podproblemów + jakaś heurystyka na wyższym poziomie -- możliwości jest naprawdę mnóstwo).

Ogólnie się zgadzam, co napisałem już wcześniej, ale wszystko zależy od problemu. Czasami masz ograniczony czas wykonywania algorytmu, ze względu na potrzebę szybkiego wyliczenia rozwiązania, a standardowe algorytmy nie dają możliwości otrzymania rozwiązania suboptymalnego przy nagłym przerwaniu pracy (np w systemach czasu rzeczywistego, czy chociażby po części gry), wtedy AE ma tą zaletę, że rozwiązanie może być kiepskie, może być dalekie optymalnemu, ale JEST. Bo są klasy zagadnień, gdzie lepsza jest jakakolwiek decyzja w 3s niż żadna. Jak leci samolot, to lepiej by zrobił cokolwiek niż liczył deterministycznym algorytmem 10min rozwiązanie i się rozbił AE i jemu podobne są dobre właśnie w takich przypadkach. Algorytmy deterministyczne jak są to dobrze, ale czasami dla dużych problemów czekałbyś kilka lat, wtedy lepszy wydaje się AE, który możesz w każdym momencie przerwać i otrzymać jakieś rozwiązanie. O tym też było na wykładzie Inna sprawa że u Pana Arabasa, co roku każdy wykład wygląda inaczej.

[Xion]

Algorytmy deterministyczne jak są to dobrze, ale czasami dla dużych problemów czekałbyś kilka lat, wtedy lepszy wydaje się AE, który możesz w każdym momencie przerwać i otrzymać jakieś rozwiązanie.

Istnieją też schematy aproksymacji, czyli algorytmy, które oprócz danych wejściowych przyjmują też dodatkowy parametr kontrolujący wynikową jakość rozwiązania - i, co za tym idzie, czas potrzebny na wykonanie programu. Problemem tu jest jednak to, że nie ma chyba ogólnej metody na konstruowanie takich schematów (a przynajmniej nie kojarzę, by coś takiego obiło mi się o uszy/oczy), więc są one specyficzne dla poszczególnych zagadnień. Dla kontrastu AE jest na tyle ogólnym przepisem, że daje się zastosować do bardzo szerokiego zakresu problemów *).

Inna sprawa że u Pana Arabasa, co roku każdy wykład wygląda inaczej.

Niestety nie za bardzo potrafię powiedzieć, jak wyglądał w moim przypadków, bo gdzieś tak na połowie zajęć mnie nie było Ale akurat o tej zalecie AE (odporność na "przerwanie") jakieś wzmianki mi się kojarzą.


*) Pamięta ktoś referat z którejś IGK (chyba nr 2), w której AE użyto do opracowywania optymalnych animacji szkieletowych?

[JCoder]

Z tym bugiem to trochę przesadzasz Smiley AE jest na tyle proste do zaimplementowania, że ciężko zrobić rażące błędy

No, sam ogólny AE tak, ale już procedura mutacji oraz funkcja dopasowania mogą być długie na wiele plików / wiele tysięcy linii.
Zależy co się optymalizuje.

[Kosz85]

Nie przesadzałbym z tym nadmiernym skomplikowaniem mutacji i krzyżowania Przeważnie są proste, poza tym pisać testów się nie chce co? Odpowiednie pisanie i testowanie fragmentów kodu, zamiast testowania jedynie na końcu całej aplikacji jak sugerujesz, rozwiązuje wiele problemów zanim powstaną Po coś się uczy o metodach wytwarzania oprogramowania i o tym jak ważne w tym procesie jest testowanie
Ale to już zaczyna zakrawać o offtop, więc zakończmy tą w sumie bezcelową dyskusję o AE Nikt Ci nie każe go używać, być może nigdy nie będziesz musiał, warto jednak wiedzieć że taka metoda istnieje i czasem się przydaje

[JCoder]

Przeważnie są proste, poza tym pisać testów się nie chce co?

Napisałem tam "mogą" być złożone.
Mam ~80% pokrycie kodu testami, kod mutacji / funkcji celu jest na ~10 tys. linii (rozbity na wiele modułów) i mimo to co pewien czas znajdywałem w nim nowe błędy. Liczba odnajdywanych błędów spadła drastycznie dopiero po przeprojektowaniu kodu na styl "bardziej funkcyjny, bezstanowy", a nie dzięki dodawaniu kolejnych testów.

AE są bezlitosne w testowaniu wszystkich możliwych ścieżek wykonania programu. Testy zmniejszają ryzyko błędów, ale nigdy nie są pewnym remedium. Musiałbym mieć 100% pokrycie wszystkich ścieżek wykonania, co nie jest możliwe w praktyce (ich liczba rośnie wykładniczo z rozmiarem kodu / danych wej.).

Raczej im dłużej programuję, staję się coraz większym zwolennikiem tezy, że testy jednostkowe powinno się stosować jako ostateczność - wszędzie tam, gdzie nie da się poprawności zapewnić w inny sposób. Kod powinien być tak prosty i czytelny, żeby było oczywiste, że nie ma w nim błędów. Niestety w wielu projektach jest odwrotnie - kod jest tak skomplikowany i nieczytelny, że nie ma w nim oczywistych błędów.

[Kos]

Kos lubi to.