[C++] algorytm genetyczny, a rozwiązywanie układów równań...

Witam,

głowię się właśnie nad jakimś rozsądnym sposobem rozwiązania następującego problemu:

Napisać algorytm genetyczny (w postaci klasy), który będzie zdolny rozwiązać układ równań typu (przykład):

2*x + y = 9
x*x - y = 2

gdzie x i y przyjmują wartości zmiennoprzecinkowe.

Powiedzmy, że populacja jest dana w tablicy

double populacja[,]; // wymiary to: 2 na wielkosc populacji

gdzie przechowywane są po prostu wartości x oraz y.

Na chwilę obecną jakość danego osobnika populacji (wiersza tablicy) wyznaczam jako pierwiastek sumy kwadratów błędów (sqrt (b1b1, b2b2), gdzie b1 = 2x + y - 9, a b2 = xx - y - 2). Jak ktoś chce wiedzieć dlaczego, to nie wiem, takie coś po prostu mi przyszło do głowy...

Największy problem jest z sortowaniem, selekcją i krzyżowaniem (liczby zmiennoprzecinkowe!) populacji, gdyż jak wiadomo taki układ jak w przykładzie ma 2 rozwiązania. Znowu krzyżówka 2 potencjalnie bardzo dobrych osobników (ale reprezentujących różne rozwiązania) da totalnie beznadziejne wyniki...

Czy ktoś, kto może ma większe doświadczenie w takich rzeczach może rzucić jakąś sugestią, pomysłem?

pozdrawiam,
Mrok

Przy wybieraniu osobników do krzyżowania możesz zrobić tak, że losujesz 4 osobników i łączysz je w pary tak by się bardziej "lubiły". W ten sposób zmniejszysz prawdopodobieństwo krzyżowania się niekompatybilnych osobników. Oczywiście możesz powiększyć ten zbiór do 6.

Znowu krzyżówka 2 potencjalnie bardzo dobrych osobników (ale reprezentujących różne rozwiązania) da totalnie beznadziejne wyniki...

No i co z tego? A gdzie jest powiedziane, że MUSI dać dobre? Ważne jest żeby CZASAMI dawało dobre (lepsze) niż każdy z rodziców. Skrzyżowanie dwóch odległych od siebie osobników jest równoważne dużej mutacji i zwykle ma katastrofalne skutki. Nie należy się tym przejmować, po to masz selekcję, żeby taki kiepski osobnik nie pożył długo.

W ogóle jest bardzo wątpliwe, czy krzyżowanie cokolwiek wnosi do GA - dla wielu klas problemów jego stosowanie tylko pogarsza lub nie zmienia szybkości zbieżności. Zdarzają się nieliczne przypadki, że poprawia, ale funkcja celu musi mieć pewne specyficzne własności. W tym przypadku nie spodziewałbym się jakiejś rewelacji, IMHO algorytm oparty tylko na mutacjach (ES) spokojnie rozwiązuje ten problem.

BTW: wiem, że to pewnie jakiś projekt studencki i dobór algorytmu masz narzucony, ale nie widziałem jeszcze żadnej klasy problemu, dla której GA byłoby najlepszą strategią. Choćby wszelkiej maści odmiany VNS (Variable Neighbourhood Search) zjadają GA na śniadanie dla większości trudnych problemów, a zarazem ich implementacja bywa prostsza niż GA (np. brak wspomnianego krzyżowania). W przypadku rozwiązywania układu równań nieliniowych, co jest raczej łatwym problemem, różnica szybkości między VNS a GA będzie pewnie kilka rzędów wielkości.