Algotytm genetyczny - znajdowanie ekstremum funkcji

Odpowiedz Nowy wątek
xxxyyyzzz
2011-05-07 15:20
xxxyyyzzz
0

Witajcie,
muszę ogarnąć algorytm genetyczny, a konkretnie znajdowanie ekstremów przy pomocy tego algorytmu i fajnie by było jakbyscie mnie poprawili i rozwiali moje wątpliwości ;)

otóż mam znaleźć minimum funkcji f(x)=x^2 +x-2 w przedziale <-1,0>

Obliczam rozdzielczość ze wzoru: (max_x - min_x)/(2^l - 1) gdzie l to liczba bitów.

Zakładam że koduję na 4 bitach więc rozdzielczość=0,067

Więc moja populacja wygląda tak:
-1 -> 0000
-0,933 -> 0001
-0,866 -> 0010
-0,799 -> 0011
-0,732 -> 0100
-0,665 -> 0101
-0,598 -> 0110
-0,531 -> 0111
-0,464 -> 1000
-0,397 -> 1001
-0,33 -> 1010
-0,263 -> 1011
-0,196 -> 1100
-0,129 -> 1101
-0,62 -> 1110

nastepnie losuje każdego osobnika(rodzica) u krzyżuje ze soba rodziców - otrzymuje nową popujację
rodzic1 rodzic2 dziecko
-1 -> 0000 -> 0100 -> 0000
-0,933 -> 0001 -> 1010 -> 0010
-0,866 -> 0010 -> 1101 -> 0001
-0,799 -> 0011 -> 0111 -> 0011
-0,732 -> 0100 -> 0010 -> 0110
-0,665 -> 0101 -> 1001 -> 0101
-0,598 -> 0110 -> 1100 -> 0100
-0,531 -> 0111 -> 1000 -> 0100
-0,464 -> 1000 -> 1011 -> 1011
-0,397 -> 1001 -> 0000 -> 1000
-0,33 -> 1010 -> 0011 -> 1011
-0,263 -> 1011 -> 0001 -> 1001
-0,196 -> 1100 -> 0101 -> 1101
-0,129 -> 1101 -> 1110 -> 1110
-0,62 -> 1110 -> 0110 -> 1110

następnie robię mutację negując ostatni bit
-1 -> 0000 -> 0100 -> 0000 -> 0001
-0,933 -> 0001 -> 1010 -> 0010 -> 0011
-0,866 -> 0010 -> 1101 -> 0001 -> 0000
-0,799 -> 0011 -> 0111 -> 0011 -> 0010
-0,732 -> 0100 -> 0010 -> 0110 -> 0111
-0,665 -> 0101 -> 1001 -> 0101 -> 0100
-0,598 -> 0110 -> 1100 -> 0100 -> 0101
-0,531 -> 0111 -> 1000 -> 0100 -> 0101
-0,464 -> 1000 -> 1011 -> 1011 -> 1010
-0,397 -> 1001 -> 0000 -> 1000 -> 1001
-0,33 -> 1010 -> 0011 -> 1011 -> 1010
-0,263 -> 1011 -> 0001 -> 1001 -> 1000
-0,196 -> 1100 -> 0101 -> 1101 -> 1100
-0,129 -> 1101 -> 1110 -> 1110 -> 1111
-0,62 -> 1110 -> 0110 -> 1110 -> 1111

i teraz z tego co się dowiedziałem powinienem znowu krzyżować i mutować i tak w kółko....

ale jak mam znaleźć to minimum? mógłby mi ktoś wyjaśnić co jest źle?

z góry dzięki

Pozostało 580 znaków

2011-05-07 18:23

Rejestracja: 14 lat temu

Ostatnio: 2 minuty temu

0

Rodziców musisz losować nie liniowo zaś albo tylko z pewnej grupy czyli tych którzy najlepiej spełniają kryteria.
Skoro szukasz maksymum to tych którzy dają większą wartość funkcji.
Można też (jeżeli funkcja jest bardzo "stroma") losować wśród wszystkich ale z uwzględnieniem wagi) aby te osobniki którzy dają większą wartość funkcji mieli odpowiednio większą szansę na potomstwo.


Wykonuję programy na zamówienie, pisać na Priv.
Asm/C/C++/Pascal/Delphi/Java/C#/PHP/JS oraz inne języki.

Pozostało 580 znaków

xxxyyyzzz
2011-05-07 21:09
xxxyyyzzz
0

a ta grupa rodziców z której będę losował? jak duża ma być? istnieje na to jakiś przepis/wzór?

Pozostało 580 znaków

2011-05-07 23:05

Rejestracja: 14 lat temu

Ostatnio: 2 minuty temu

0

Nie koniecznie jedna grupa rodziców.
Możesz populacje podzielić losowo na kilka grup a z każdej grupy wylosować przyszłych rodziców.
Grupa rodziców ma być odpowiednia aby nowa populacja nie okazała się większa (ani też mniejsza) niż obecna.
Jeszcze jedno, mutacje rób losowo (czyli nie zawsze) a rodzice przechodzą do następnej generacji.


Wykonuję programy na zamówienie, pisać na Priv.
Asm/C/C++/Pascal/Delphi/Java/C#/PHP/JS oraz inne języki.

Pozostało 580 znaków

wojtekN
2011-05-09 12:18
wojtekN
0

Hey,
jak zamierzasz wykorzystywać AG na funkcji z jedną zmienną to daj chociaż większą dokładność. Bo jak dałeś 4 bity na zmienną to czy nie lepiej sprawdzić wszystkie rozwiązania i wybrać to, gdzie funkcja jest MAX/MIN?
Do tego możesz zwiększyć przedział - dlaczego sprawdzasz jedynie wynik funkcji w przedziale <-1,-0.67>? Daj znacznie większy przedział np. <-10,10> i zakoduj zmienną x np. 10 bitami.
Pozdrawiam

Pozostało 580 znaków

wojtekN
2011-05-09 12:41
wojtekN
0

Małe sprostowanie - kodujesz w przedziale <-1,0> a nie <-1,-0.67>.
Przy okazji zabrakło Ci w populacji możliwości 1111
Nie za bardzo rozumiem tego przechodzenia:

rodzic1 rodzic2 dziecko
-1 -> 0000 -> 0100 -> 0000

rozumiem, że rodzic1 ma wartość (-1) czyli 0000 rodzic 2 wartość 0100 (ale już nie wskazałeś liczbowego odpowiednika tego rodzica) a dziecko ma wartość 0000.
Jednak metod krzyżowania jest bardzo wiele i nie wiem z jakiego Ty korzystasz. Nie będę wnikał czy dobrze :)
Z mutacją znowu jest troszkę możliwości. Nie słyszałem co prawda o mutacji, która by mutowała tylko ostatni bit. Zazwyczaj mutuje się z pewnym prawdopodobieństwem każdy bit. Tzn. dla każdego bitu losuje się pewną liczbę (np. z zakresu <0,1> i gdy wylosowana liczba jest mniejsza/większa od pewnego przyjętego progu to zmienia się ten bit na przeciwny. Oczywiście prawdopodobieństwo zmiany powinno być stosunkowo małe (nie powinno dochodzić zbyt często do mutacji). Pominę już fakt, że często się podważa sens operacji mutowania - w naturze może odgrywa to niebagatelną rolę, ale z tego co ja wiem nie zostało udowodnione, że pomaga w procesie odnajdywania max/min-ów.
Nie wiem również czy poprawnie zrozumiałeś sens krzyżowania. Gdy masz jakąś populację rodziców to losujesz nową populację (również stosując do tego liczbę losową). To nie jest tak, że w nowej populacji masz starych rodziców i losujesz drugiego rodzica do pary. Losujesz obu rodziców z poprzedniej populacji.
Zazwyczaj 1-3 najlepszych osobników przechodzi z automatu ale pozostałych się losuje.
W procesie wyboru musisz obliczyć funkcję celu u każdego rodzica, żeby wiedzieć kto ma większe szanse na wylosowanie. Tzn. nie bierzesz tu pod uwagę wielkości x tylko wynik f(x).
Pozdrawiam

Pozostało 580 znaków

delphiak
2011-05-09 14:52
delphiak
0

Pominę już fakt, że często się podważa sens operacji mutowania - w naturze może odgrywa to niebagatelną rolę, ale z tego co ja wiem nie zostało udowodnione, że pomaga w procesie odnajdywania max/min-ów.

Sens mutacji jest taki, że pozwala ona "wyjść" algorytmowi z ekstremum lokalnego, gdy ten się w nim "zagrzebie" :)
Jej skuteczność jest potwierdzona empirycznie dla wielu algorytmów.

Pozostało 580 znaków

wojtekN
2011-05-09 15:50
wojtekN
0
delphiak napisał(a)

Pominę już fakt, że często się podważa sens operacji mutowania - w naturze może odgrywa to niebagatelną rolę, ale z tego co ja wiem nie zostało udowodnione, że pomaga w procesie odnajdywania max/min-ów.

Sens mutacji jest taki, że pozwala ona "wyjść" algorytmowi z ekstremum lokalnego, gdy ten się w nim "zagrzebie" :)
Jej skuteczność jest potwierdzona empirycznie dla wielu algorytmów.

A jak niby AG może "ugrzęznąć" w minimum lokalnym? Przecież w samym procesie krzyżowania masz już możliwość wyjścia z "ekstremum lokalnego". Prawdopodobieństwo trafienia dwóch rodziców podobnych do siebie (z podobnymi parametrami) jest baaaardzo małe więc ugrzęźnięcie w min/max lokalnym również jest baaaardzo małe.

Druga sprawa to taka, że nie da się do końca zbadać empirycznie czy mutacja daje pozytywny, negatywny czy neutralny efekt. AG działają w sposób losowy - więc po prostu nie da się wyodrębnić wpływu mutacji. No chyba, że wyniki byłyby zdecydowanie lepsze przy korzystaniu z mutacji - jednak z tego co ja wiem tak nie jest.

Na zdrowych chłopski rozum (moim zdaniem) wpływ mutacji jest żaden. Równie dobrze może pomóc w poszukiwaniu optymalnego rozwiązania co zaszkodzić.

Pominę już fakt, że korzystanie z mutacji powoduje zwiększenie operacji algorytmu co jest równoznaczne z wydłużeniem procesu szukania optymalnego rozwiązania, który można byłoby przeznaczyć na dodatkowe przeszukiwanie przestrzeni rozwiązań. Może koszt mutacji nie jest duży ale jednak dla każdego bitu (a każda zmienna może mieć ich od kilku do nawet kilkudziesięciu bitów) trzeba wylosować zmienną, przyrównać ją do danego progu i ewentualnie zmienić wartość danego bitu.

Pozdrawiam

Pozostało 580 znaków

2011-05-09 23:17

Rejestracja: 14 lat temu

Ostatnio: 2 minuty temu

0

Jeżeli funkcja ma kilka minimów lokalnych a przynajmniej jeden jest bardzo "głęboki" (strome zbocza) to może się okazać że prawie cała populacja "siedzi" w tym minimum lokalnym, bo byli zdecydowanie lepsze od innych porozrzucanych wzdłuż osi/płaszczyzny/cokolwiek_by_to_było. Więc mutacja pozwoli jakiemuś osobnikowi trafić w inny minimum lokalny.
Co do kosztów to przesadzasz, nawet jak masz 1000 bitów i masz zrobić mutacje w bitach to wystarczy że wylosujesz jedną jedyną liczbę losową, a mutujesz wg wag.


Wykonuję programy na zamówienie, pisać na Priv.
Asm/C/C++/Pascal/Delphi/Java/C#/PHP/JS oraz inne języki.

Pozostało 580 znaków

wojtekN
2011-05-10 10:54
wojtekN
0
_13th_Dragon napisał(a)

Jeżeli funkcja ma kilka minimów lokalnych a przynajmniej jeden jest bardzo "głęboki" (strome zbocza) to może się okazać że prawie cała populacja "siedzi" w tym minimum lokalnym, bo byli zdecydowanie lepsze od innych porozrzucanych wzdłuż osi/płaszczyzny/cokolwiek_by_to_było. Więc mutacja pozwoli jakiemuś osobnikowi trafić w inny minimum lokalny.
Co do kosztów to przesadzasz, nawet jak masz 1000 bitów i masz zrobić mutacje w bitach to wystarczy że wylosujesz jedną jedyną liczbę losową, a mutujesz wg wag.

Hey,
W początkowym etapie pracy algorytmu prawdopodobieństwo wylosowania całej populacji blisko jednego punktu w przestrzeni jest naprawdę nikłe - już lepiej grać w totka :P. Do tego kształt funkcji celu nie odgrywa tu tak dużej roli, bo nawet jak część osobników trafi np. głębszy dołek to i tak dobór kolejnych rodziców jest wybierana w sposób losowy - z pewnym prawdopodobieństwem - i tu znowu trzeba mieć niezłego "farta", żeby znowu trafić wszystkie osobniki z tego jednego konkretnego dołka... Równie dobrze masz podobne prawdopodobieństwo, że będziesz zawsze trafiać w minima lokalne niezależnie od przyjętej metody krzyżowania czy mutacji...

Podkreślam, że AG działają w sposób losowy! więc nie rozumiem obawy przed "utknięciem" w minimum/maximum lokalnym... Przykładowo, dla podanej wyżej funkcji celu minimum globalne jest bodajże w punkcie (-0.5) a wy się boicie, że cała wylosowana populacja będzie w okolicach np. x=(-1) (a przynajmniej daleko od tego optymalnego punktu).
Losując przykładowo 10 osobników w populacji policz sobie prawdopodobieństwo, że wszystkie osobniki (lub większość) będzie mniejsza np. od (-0,8) lub większa od (-0.2). Chyba nieduże co? :)
Bo jeśli wstępna populacja będzie rozłożona w całej przestrzeni mniej więcej równomiernie to obawa o utknięcie w minimum lokalnym jest naprawdę kiepsko uzasadniona a operatory krzyżowania powinny sobie poradzić z wyjściem z ekstremów lokalnych.
Utknięcie wielu osobników w jednym dołku może być charakterystyczne w końcowym etapie algorytmu ale to jest normalne - po prostu albo algorytm znalazł minimum globalne (lub jest bliski optymalnemu rozwiązaniu) albo się rozłożył i nie poradził sobie. Oczywiście porażka AG jest jak najbardziej normalnym zjawiskiem (nie należy panikować, gdy AG sobie z czymś nie poradziło)! W końcu działa w sposób losowy i nie można mieć żadnej pewności, że znajdzie nawet minimum/maximum lokalne. Równie dobrze może błądzić z dala od ekstremum globalnego - taka natura AG.
Można oczywiście próbować kilka razy przeszukiwać przestrzeń (na nowo losując wstępnych osobników) a później ich krzyżując między sobą.
Tak jak już chyba wcześniej wspomniałem istnieje wiele metod operacji krzyżowania oraz mutacji ale nie ma jakiegoś "najlepszego". Natomiast o mutacji często autorzy różnych książek (np. bodajże dr Gwiazda) negatywnie się wypowiadają. Koszt mutacji może nie jest duży ale czy jest uzasadniony? Bo ja śmiem twierdzić, że nic ona nie daje (tzn. może tak samo pomóc co przeszkodzić w procesie uczenia).
Nigdy nie masz pewności, że dzięki mutacji trafisz w inne minimum lokalne! równie dobrze możesz trafić w gorsze miejsce (funkcja zamiast zmaleć urośnie - lub odwrotnie).

Nie za bardzo rozumiem co masz na myśli, że mutuję według wag? Losuję jedną liczbę i co dalej? mutuję dany bit w każdej wadze (np. ostatni)? a niby dlaczego tak? przecież to bez sensu... A czemu ostatni a nie środkowy lub pierwszy bit? i dlaczego w każdej wadze a nie tylko w jednej lub w kilku? Przecież to się mija z celem mutacji... Mutacja powinna być przeprowadzana w sposób losowy i nie ma żadnych powodów, żeby zmieniać tylko jeden konkretny bit w każdej lub jednej wadze. Co najwyżej możesz użyć np. trzech lub więcej zmiennych losowych i np. zrobić tak, że pierwsza decyduje w której zmiennej zmienić jakiś bit, druga decyduje który bit zmienić a trzecia czy go w ogóle zmienić. Ale tak jak wspomniałem wcześniej sens mutacji jest podważany przez wielu autorów.

Pozdrawiam

Pozostało 580 znaków

2011-05-10 11:36

Rejestracja: 14 lat temu

Ostatnio: 2 minuty temu

0

Czy przypadkiem nie zapomniałeś że wylosowujesz rodziców wg funkcji celu, czyli z większym prawdopodobieństwem tych co najlepiej spełniają tą funkcje.
Z tego co tu wypisujesz wnioskuje że przeczytałeś na ten temat to i owo ale nigdy żadnego AG nie zaimplementowałeś.


Wykonuję programy na zamówienie, pisać na Priv.
Asm/C/C++/Pascal/Delphi/Java/C#/PHP/JS oraz inne języki.

Pozostało 580 znaków

Odpowiedz

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0