Muszę napisać algorytm genetyczny. Mógłby ktoś przedstawić mi pseudokod? Ogólnie wiem o co chodzi, ale nie potrafię tego przelać na kod C.
A z pseudokodu już tak?
- Wygeneruj populacje losowo
- Utwórz pewien procent nowych osobników (20%...200%) selekcja normalna lub turniejowa, krzyżowanie też ma wiele opcji.
- Posortuj wszystkich wg bliskości do funkcji celu.
- Zabij tyle osobników by zastało tyle samo co w kroku pierwszym.
- Przejdź do punktu 2.
A tak BTW. Genetyczny to ten sam algorytm co ewolucyjny?
Algorytmy genetyczne (takie jak opisał to poprzednik) stanowią podklasę algorytmów ewolucyjnych czyli bazujących ogólnie na idei ewolucji (np. zmieniający się w trakcie działania program w zależności od czynników zewnętrznych).
Niedawno pisałem ewolucyjne HelloWorld (chyba najprostszy możliwy przykład, rozwiązaniem problemu jest string identyczny z wzorcem), które teraz (w wolnych chwilach) uogólniam i chcę stworzyć prosty framework do rozwiązywania problemów za pomocą algorytmu ewolucyjnego. To HelloWorld w najprostszym wydanie to mniej więcej tak wyglaða:
- Klasa jednostki zawiera jego wartość (rozwiązanie problemu, tutaj: string) i dwie metody mutuj (z określonym prawdopodobieństwem) oraz krzyżuj (argumentem jest inna jednostka, zwracana jest nowa jednostka będąca np. średnią dwóch stringów.
- Klasa funkcji oceniajacej: zawiera string będący wzorcem ("HelloWorld") oraz metodę, która liczy jak blisko wzorca jest jednostka (z punktu 1.) - suma kwadratów różnic na poszczególnych pozycjach w stringu jednostki i wzorca.
- Kolekcja populacji - np. 20 jednostek.
- Coś co generuje nową populacje na podstawie starej populacji i funkcji matchującej np. nowe jednostek będących skrzyżowaniem losowych jednostek z podzbioru najlepszych dziesięciu starej populacji (czasami zmutowanych) np. one.crossover(two).mutate()
Zapuszczamy generowanie nowych populacji, aż najlepsza jednostka będzie identyczna z wzorcem. Można kombinować z różnymi ilościami jednostek w populacji, funkcjami oceniającymi, sposobami generowania nowej etc.
EDIT:
Jeśli coś jest niejasne to sorki, jest 3 i właśnie lecę spać. Jak coś to pytaj, bo trochę jestem zajawiony tematyką.