Algorytm genetyczny problem

Cześć próbuję zaimplementować algorytm genetyczny który jako funkcje do optymalizacji przyjmuje funkcje rosenbrocka. Generalnie wszystko już napisałem jednak gdzieś pojawił się błąd mianowicie funkcja dopasowania mimo iż powinna spadać z każdym kolejną generacją zachowuje się chaotycznie(raz rośnie , raz maleje) próbowałem już różnych opcji selekcji rodziców( turniej , ruletka) jednak nic to nie daje. Mógłby ktoś zerknąć i sprawdzić dlaczego tak może się dziać?

https://pastebin.com/qeUnBZJE

Tak na pierwszy rzut oka widzę kilka problemów:

• crossing-over polega u Ciebie na tym, że potomek dostaje jedną współrzędną jednego rodzica i drugą współrzędną drugiego rodzica. W efekcie jeśli masz N rodziców, to masz N współrzędnych X i N współrzędnych Y, które sobie zamieniasz i nic z tego nie wynika. W przypadku algorytmu genetycznego (takiego klasycznego, gdzie informacja o osobniku jest zakodowana jako ciąg bitów) Crossing over powinien polegać na tym, że krzyżujesz w jakimś losowo wybranym punkcie przecięcia.
• nie wprowadzasz w ogóle mutacji - tzn. od czasu do czasu powinny się pojawiać losowe zmiany, mniejsze lub większe. Jeżeli wartości nie są zakodowane, to mogą być po prostu jakieś losowo wygenerowane odchylenia (np. z rozkładu Gaussa czy coś), jeśli zakodowane - to wtedy losowo 'flipujesz' pojedyncze bity. Tylko pamiętaj, żeby kodowanie mapowało ciągły zakres liczb zmiennoprzecinkowych na ciągły zakres wartości binarnych, a nie było kodowaniem IEEE 754, bo jak zaczniesz flipować bity znaku czy cechy to wszystko się sypnie
• Cały mechanizm wyboru osobników do porównania wygląda dziwnie, losujesz do niego X osobników z puli, po czym wybierasz z nich najlepszego i go zwracasz, po czym robisz krzyżowanie...

Ogólnie w absolutnie najprostszym wypadku powinno to wyglądać tak:

• losujesz początkową populację
• oceniasz
• na podstawie oceny wybierasz kto się "rozmnaża"
• krzyżujesz osobniki wybrane do rozmnożenia
• robisz mutacje
• oceniasz
• i tak dalej...

Generalnie ten cross brałem z tego artykułu http://www.worldscientificnews.com/wp-content/uploads/2012/11/WSN-6-2015-41-56.pdf

Istnieje jakiś łatwy sposób aby liczbę double przedstawić przy pomocy ciągu bitów?

https://4programmers.net/Forum/C_i_C++/333768-program_w_c_reprezentacja_zmiennoprzecinkowa?p=1638608#id1638608

Chyba najłatwiejszy to założyć, że masz pewien zakres liczb zmiennoprzecinkowych i określoną liczbę bitów, na których będziesz reprezentować ten zakres. Mając do dyspozycji N bitów będziesz mógł przedstawić 2^N liczb, gdzie 00...00 to będzie najmniejsza wartość z zakresu, a 11..11 największa.

Zamiana zakodowanej wartości na liczbę to będzie coś w stylu

x_float = x_min + (x_max - x_min) * (x_binary / (2^N - 1))

Dlaczego 2^N - 1? Bo to największa liczba, jaką jesteś w stanie zakodować na N bitach. 2^N wymaga już N + 1 bitów.

Jeśli zdecydujesz się zrobić to bez kodowania binarnego (tylko wtedy to nie będzie klasyczny algorytm genetyczny, tylko bardziej ewolucyjny), to mutowanie / krzyżowania możesz załatwić nieco inaczej:

• mutowanie, tak jak wspomniałem, przez losowe odchylenia - tu możesz sobie jeszcze pozwolić np. na sterowanie wielkością tych odchyleń i np. zacząć od dużych i stopniowo zmniejszać. Na odwrót nie ma sensu, bo najpierw znajdziesz jakieś lokalne / globalne minimum, a potem i tak je opuścisz.
• krzyżowanie może być przez wybranie współrzędnej od jednego z rodziców, ale w tym przypadku wydaje mi się to trochę średnim pomysłem, bo rezultaty takiego krzyżowania mogą być właściwie tylko dwa, ale może się mylę. Zamiast tego spróbowałbym zrobić krzyżowanie przez wybór losowych wartości z zakresu (x_a ... x_b), (y_a, y_b)... i tak dalej. Wprowadzisz dodatkową zmienność, no i trochę bardziej będzie to przypominać wartości kodowania binarnego, gdzie krzyżując w losowych punktach uzyskiwałbyś zupełnie nowe wartości a nie tylko kombinacje istniejących.

superdurszlak napisał(a):

Chyba najłatwiejszy to założyć, że masz pewien zakres liczb zmiennoprzecinkowych i określoną liczbę bitów, na których będziesz reprezentować ten zakres. Mając do dyspozycji N bitów będziesz mógł przedstawić 2^N liczb, gdzie 00...00 to będzie najmniejsza wartość z zakresu, a 11..11 największa.

Zamiana zakodowanej wartości na liczbę to będzie coś w stylu

x_float = x_min + (x_max - x_min) * (x_binary / (2^N - 1))

Dlaczego 2^N - 1? Bo to największa liczba, jaką jesteś w stanie zakodować na N bitach. 2^N wymaga już N + 1 bitów.

Jeśli zdecydujesz się zrobić to bez kodowania binarnego (tylko wtedy to nie będzie klasyczny algorytm genetyczny, tylko bardziej ewolucyjny), to mutowanie / krzyżowania możesz załatwić nieco inaczej:

• mutowanie, tak jak wspomniałem, przez losowe odchylenia - tu możesz sobie jeszcze pozwolić np. na sterowanie wielkością tych odchyleń i np. zacząć od dużych i stopniowo zmniejszać. Na odwrót nie ma sensu, bo najpierw znajdziesz jakieś lokalne / globalne minimum, a potem i tak je opuścisz.
• krzyżowanie może być przez wybranie współrzędnej od jednego z rodziców, ale w tym przypadku wydaje mi się to trochę średnim pomysłem, bo rezultaty takiego krzyżowania mogą być właściwie tylko dwa, ale może się mylę. Zamiast tego spróbowałbym zrobić krzyżowanie przez wybór losowych wartości z zakresu (x_a ... x_b), (y_a, y_b)... i tak dalej. Wprowadzisz dodatkową zmienność, no i trochę bardziej będzie to przypominać wartości kodowania binarnego, gdzie krzyżując w losowych punktach uzyskiwałbyś zupełnie nowe wartości a nie tylko kombinacje istniejących.

Próbowałem zrobić tak jak mówisz to znaczy wybierać potomka z przedzialu od parent1.x do parent2.x jednak nic to nie daje.Nie za bardzo rozumiem o co chodzi z tym równaniem x_float (gdzie i kiedy powinienem tego użyć oraz czym jest np. x_binary). Dodatkowo spróbowałem przedstawić rodziców jako bajtowe tablice i łączyć je ze sobą w zależności od jakiegoś losowego punkty przecięcia. Jednak w tej chwili natrafiłem na problem w którym w pewnym momencie obliczenia w ogóle nie posuwają się do przodu. Spróbowałem wybierać rodziców ruletkowo ale nic to nie daje.
Screen z wynikami:
http://prntscr.com/qbojuo
Kod:
https://pastebin.com/QMcXs8RY

aje123 napisał(a):

Próbowałem zrobić tak jak mówisz to znaczy wybierać potomka z przedzialu od parent1.x do parent2.x jednak nic to nie daje.Nie za bardzo rozumiem o co chodzi z tym równaniem x_float (gdzie i kiedy powinienem tego użyć oraz czym jest np. x_binary).

Ok, powiedzmy że chcesz mieć liczby z przedziału 2...17 i chcesz je zakodować na 4 bitach. W normalnych warunkach wziąłbyś trochę więcej bitów, ale to przykład. Szerokość Twojego przedziału, czyli (x_max - x_min), wynosi 15. Masz cztery bity, więc największa liczba do zakodowania to 0b1111, czyli też 15.

I teraz tak, trzymasz sobie te liczby cały czas zakodowane jako x_binary, a dekodujesz tylko do obliczenia funkcji celu. Wtedy potrzebujesz x_float.

Teraz powiedzmy, że Twoje x_binary = 0b0110, czyli 6. Podstawiasz:

x_float = x_min + (x_max - x_min) * (x_binary / (2^N - 1))
x_float = 2 + (17 - 2) * (6 / (16 - 1))
x_float = 2 + 15 * (6 / 15)
x_float = 2 + 6
x_float = 8

Czyli wychodzi na to, że wartość 0b0110 koduje w tym przypadku 8. Ale gdyby zakres był inny, albo byłaby inna liczba bitów, to mogłoby kodować np. liczbę -1.343 albo 27.145828847(3) - ale to nie jest problem, bo formuła pozostaje ta sama, a Ciebie interesuje jedynie konwersja z postaci binarnej do zmiennoprzecinkowej na potrzeby obliczenia funkcji celu, no i podania końcowego wyniku.

Dodatkowo spróbowałem przedstawić rodziców jako bajtowe tablice i łączyć je ze sobą w zależności od jakiegoś losowego punkty przecięcia. Jednak w tej chwili natrafiłem na problem w którym w pewnym momencie obliczenia w ogóle nie posuwają się do przodu. Spróbowałem wybierać rodziców ruletkowo ale nic to nie daje.

Zrobiłeś dokładnie to, przed czym ostrzegałem. Dziabiesz w reprezentacji liczb rzeczywistych, w której część bitów koduje cechę (czyli wykładnik w notacji naukowej) a część mantysę (czyli część ułamkową), jeden koduje znak, istnieją specjalne kombinacje i tak dalej. To się nie uda.

Przenoszę do posta bo robił się monolog na trzy komentarze:

A nie mógłbym spróbować przedstawić dwóch liczb w postaci Stringów i tworzyc z nich inny uzywajac punkty przeciecia?

Tylko po co tak utrudniać sobie życie? Będziesz się męczyć z tym, jak prawidłowo wybrać taki punkt przecięcia i tak dalej. To podejście z kodowaniem to po prostu takie klasyczne podejście, gdzie próbowano się wzorować dosłownie na tym, jak to działa w naturze więc wymyślono żeby kodować dane binarnie, ale z drugiej strony trzeba było kodować tak żeby nie wybuchało przy pierwszej lepszej mutacji i krzyżowaniu (co miałoby miejsce gdyby skrzyżować dwie zmienne zakodowane zgodnie ze standardem IEEE 754.

Jak nie zależy Ci na tym, żeby to był taki czysty, klasyczny algorytm genetyczny to kodowanie binarne możesz pominąć, ale wtedy musisz po prostu dostosować swoje operatory genetyczne do tego, jak reprezentujesz dane. To znaczy operując na liczbach zmiennoprzecinkowych nie będziesz już grzebał w bitach, tylko wykonywał jakieś operacje matematyczne które mają przynieść zbliżony skutek. A jak jednak chcesz mieć kodowanie binarne to jedyne czego tak naprawdę potrzebujesz, to typy całkowite (najlepiej bez znaku, ale w Javie jako takiej ich nie ma) i parę operacji bitowych: AND, OR, XOR i ew. przesunięcia bitowe. Nic skomplikowanego.

1. Do kodowania x_binary użyj kodów Graya - w czasie mutacji wartość w kodzie Graya, w trakcie obliczeń zdekodowana.

2. Do robienia mutacji floata możesz założyć albo to kodowanie przedziałowe, albo mutować w nieznanym kierunku. Czyli możesz np. założyć że szukana liczba jest w przedziale +-10E+6 z dokładnością 10E-99. Możesz albo "dziubać" każdą wartość z wymaganą dokładnością albo jak opisano wyżej zmieniać wartość ze zmienną wielkością zmiany w różnym kierunku (+,- itd).

3. Jeśli chodzi o crossover to możesz się pokusić o interpretowanie IEEEE 754, ten papier pokazuje że to się sprawdza:
   https://dergipark.org.tr/en/download/article-file/83541
   (TL;DR)

Chyba tak właśnie zrobię, zastanawia mnie jeszcze jedno dlaczego dla 6 wynik x_float jest równy 8.

Przecież masz rozpisane od początku do końca z czego to wynika, masz zakres na przykład od 2 do 17. Wymyśliłem taki, żeby liczby były ładne i okrągłe, ale w rzeczywistości pewnie będą różne ułamki. Zakładasz, że minimalnej wartości z zakresu (2) odpowiada minimalna wartość w tym kodowaniu (0). Dla maksymalnej to samo, czyli 17 jest zakodowana jako 0b1111 albo po naszemu 15. Do wartości pośrednich są też są przypisane jakieś wartości - jeśli masz powiedzmy liczbę ze środka zakresu wartości, to po zdekodowaniu też będziesz gdzieś w środku. Jeśli będziesz bliżej początku, powiedzmy w 1/3, to po zdekodowaniu też tak będzie i zdekodowana wartość będzie w 1/3.

Skoro są "w tym samym miejscu", to można to wyrazić ułamkiem i tak właśnie robię w przykładzie :)

I rozumiem ze w przypadku zapisu w ten sposób mogę spokojnie zmieniać dowolne bity?

Dopóki dopuszczasz wszystkie możliwe wartości - tak. Jeśli sobie przyjmiesz jakieś dodatkowe swoje obostrzenia, bo np. chcesz mieć w wyniku okrągłe ułamki więc wykorzystujesz tylko liczby od 0 do 100 mając 7 bitów czy coś podobnego - to siłą rzeczy musisz sprawdzać, czy po mutacji / krzyżowaniu nowa wartość jest dalej poprawna wg. tych reguł, które sobie wymyśliłeś. Ale w najprostszym przypadku nie musisz się tym martwić.