Algorytmy Genetyczne szukają Symbolu Newtona ;-)

Nie pisałem tutaj o tym choć pisałem na moim "anglojęzycznym" blogu. Bawię się ostatnio w rozwiązywanie zadań, które Google dało kiedyś zawodnikom w trakcie code.jam.Dwa pierwsze zrobiłem w dość krótkim czasie bo spędziłem nad nimi łącznie z 5-6 godzin, ale z trzecim było trudniej ;-) Zajęło mi znacznie dłużej ;-)W końcu dotarłem do algorytmu, który owocował kodem:

public long findMaxF(long d, long b) {    long f = 0;    if (b==1) {       f=d;    } else if (b==d) {       f=(1<Kod ten można jeszcze uprościć wyrzucając kawałek z porównaniem b i d dodając warunek zapewniający, że b nie będzie nigdy większe od d... ale to szczegół, ważne jest to, że ta rekurencja działa dla stosunkowo małych d i b, w przeciwnym wypadku "leci" StackOverflowError.Wiedziałem, że można się jakoś tej rekurencji pozbyć i opisuje to powierzchownie na moim drugim blogu ;-) Wcześniej jednak niż doszedłem do tego, że moja funkcja może zostać zastąpiona przez sumowanie wyników symbolu Newtona poszedłem inną ścieżką ;-)Spróbowałem użyć programu Genetyk, który znalazłem na stronie alife.pl [polecanej na świetnej ewolucja.org].Program ten używa algorytmów genetycznych do szukania funkcji opisujących zadany zestaw wartości. Niby jak wiemy, że AG działają to można sobie taki program wymyśleć, ale jednak zobaczenie jego działania daje po oczach :-)Dla mojego zestawu danych [funkcja przedstawiona wyżej wołana w taki sposób findMaxF(d=20,b={1,20})], który to zestaw został z niewyjaśnionych przyczyn odwrócony prze program ;-) [zamienił oś X z Y, a próba wymuszenia innego ułożenia kończyła się błędnym wczytaniem pliku] program zaczął tworzyć olbrzymią kolumbrynę, która po chyba około 20 tysiącach kroków [ale tu pewien nie jestem ile to było} zbliżała się do oryginalnego wykresu ze średnim błędem na poziomie 5 co jest niezłym osiągnięciem :-)Bardzo ciekawie wygląda proces dochodzenia do rozwiązania. Sam używałem AG do szukania drogi w terenie z przeszkodami [znajdowały ;-) a ja się tym zajmowałem w ramach pracy na studiach podyplomowych ;-)] i do przybliżania wykresów [niby podobne, ale ja zakładałem, że fragment wykresu który chcę przybliżyć jest opisany przez równanie ze współczynnikami i zmieniałem tylko współczynniki - to było mi potrzebne w pracy magisterskiej do obróbki danych z pomiarów :-)]. Ale nadal fascynuje mnie to jak AG rozwiązują skomplikowane problemy.Btw. warto do Ewolucja.org dodać sobie do zakładek alife.pl


Podobne postybeta
Opowieść o małym n ;-)
Rankingi, to nie takie proste ;-)
Krzyżowcy
Java i liczby pierwsze, odsłona druga
Regresja liniowa w Google Docs