Algotytm genetyczny - znajdowanie ekstremum funkcji

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

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.

0

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

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.

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

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

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.

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

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.

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

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ś.

0
_13th_Dragon napisał(a)

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ś.

Mi się natomiast wydaje, że nie do końca czytasz uważnie to co ja piszę.
Tak, z większym prawdopodobieństwem! Sam o tym wspomniałem wcześniej. Ale to nie znaczy, że będziesz losować tylko te lepiej przystosowane! Wylosowanie 1-3 takich samych lub podobnych rodziców może się zdarzyć. Ale wylosowanie całej populacji podobnych osobników jest już mało prawdopodobne. Do tego równie dobrze możesz wylosować samych słabszych osobników - w końcu to, że masz większe prawdopodobieństwo wylosowania danego osobnika to nie znaczy, że go wylosujesz. A im większa populacja i im więcej zmiennych tym trudniej osiągnąć to czego Ty się obawiasz.
Do tego tak jak napisałem wcześniej - mutacja nie gwarantuje Ci znalezienia lepszego rozwiązania.
Pozdrawiam

0

No to właśnie potwierdziłeś moją hipotezę, nigdy żadnego AG nie zaimplementowałeś.
Załóżmy że 10% populacji trafiło do stromego dołka lokalnego, a na pewno w którymś momencie trafią tam te 10% bo inaczej AG nigdy nie dawał by żadnych czytelnych wyników. Załóżmy też że stromy dołek lokalny oznacza że przewaga (czyli szansa na zostania wylosowanym do rozpłodu) tych z dołka lokalnego jest 10-krotna. W takim przypadku ponad polowa wylosowanych rodziców będzie właśnie z tych 10%. Zaś oznacza to że w następnej generacji w tym samym dołku będzie już znajdować się przynajmniej 25% populacji. Po kilku krokach znajdzie się tam prawie cała populacja i tylko przypadkowe mutacje pozwolą szukać jakiegoś innego minima lokalnego.

0
_13th_Dragon napisał(a)

No to właśnie potwierdziłeś moją hipotezę, nigdy żadnego AG nie zaimplementowałeś.
Załóżmy że 10% populacji trafiło do stromego dołka lokalnego, a na pewno w którymś momencie trafią tam te 10% bo inaczej AG nigdy nie dawał by żadnych czytelnych wyników. Załóżmy też że stromy dołek lokalny oznacza że przewaga (czyli szansa na zostania wylosowanym do rozpłodu) tych z dołka lokalnego jest 10-krotna. W takim przypadku ponad polowa wylosowanych rodziców będzie właśnie z tych 10%. Zaś oznacza to że w następnej generacji w tym samym dołku będzie już znajdować się przynajmniej 25% populacji. Po kilku krokach znajdzie się tam prawie cała populacja i tylko przypadkowe mutacje pozwolą szukać jakiegoś innego minima lokalnego.

Nie, czytałem tylko o AG, żeby się przechwalać na forum... Nie wiem na jakiej podstawie wywnioskowałeś tą tezę ale nie będę Ci udowadniać moich osiągnięć w tej dziedzinie. Chociaż muszę powiedzieć, że jestem większym zwolennikiem algorytmów gradientowych niż AG - przynajmniej mam pewność, że chociaż jedno minimum znajdę :]. Niestety w przeciwieństwie do AG, algorytmy gradientowe są mocno ograniczone - chociażby tym, że funkcja celu musi być ciągła. Ale mają też kilka przewag w porównaniu do AG.

Natomiast wracając do tematu:

  1. Skąd wiesz, że miejsce w którym obecnie jesteś nie jest w pobliżu minimum globalnego a mutacja nie spowoduje "ucieknięcie" do innego minimum - lokalnego? Które jest co prawda trochę płycej od poprzedniego położenia ale jest znacznie dalej od minimum globalnego?
  2. Czy rozumiesz ideę krzyżowania?
    Nawet jak masz 10% populacji w jednym dołku to pozostałe 90% jest w innym dołku/dołkach (a dokładniej w innych miejscach w pewnej przestrzeni - bo w przypadku AG trudno trafić nawet na dołek lokalny)!
    Natomiast rodziców dobierasz losowo - tzn. nie łączysz tych z tego jednego dołka tylko mieszasz całą populację między sobą (z pewnym prawdopodobieństwem). Czyli jeden rodzic może być z tego dołka o którym ty mówisz a drugi może być zupełnie z innego miejsca w przestrzeni.
    Natomiast krzyżując tych osobników tworzysz "dzieci", które są jeszcze w innym miejscu w przestrzeni (zależy jaką metodę krzyżowania wybrałeś) oraz czy rodzice są "blisko" siebie.

I teraz tak: gdy rodzice są "podobni" do siebie (np. z tego samego dołka) to dzieci są blisko rodziców i przeszukują ten obszar w którym byli rodzice (szukając bardziej optymalnego miejsca) natomiast gdy rodzice są od siebie oddaleni to dzieci mogą być utworzeni:
a) pomiędzy rodzicami,
b) pomiędzy - bliżej jednego z nich lub
c) bliżej jednego z nich ale nie pomiędzy rodzicami tylko po drugiej stronie jednego z nich...
Kombinacji jest na prawdę sporo!
I mogą być bliżej minimum globalnego jak również dalej... Ale jak oboje rodzice są z dwóch różnych miejsc (a na prawdę, przy większej liczbie zmiennych i przy większej populacji ciężko trafić dwóch rodziców z tego samego dołka) to raczej na pewno dzieci będą jeszcze w innych miejscach więc nie musisz się martwić o utknięcie w minimum lokalnym. Algorytm nawet bez operatora mutacji przeszuka sporą część przestrzeni i ma małe prawdopodobieństwo utknięcia od tak sobie w jednym dołku. I żadna mutacja nie jest Ci potrzebna. Jak dzieci znajdą lepsze rozwiązanie to znowu mają większą szansę na wylosowanie i znowu się mieszają między sobą itd...

Dobrym przykładem może być podana wcześniej funkcja. Gdy nawet 50% populacji będzie miało wartość bliską 0 a drugie 50% populacji będzie miało wartość bliską (-1) to gdy je wymieszasz to przynajmniej część dzieci będzie pochodzić od rodziców z jednego i drugiego końca więc można się spodziewać, że dzieci będą miały wartości bliskie (-0,5). I nie jest Ci do tego potrzebna żadna mutacja.

Tak jak wspomniałem wcześniej znając wynik pewnej funkcji nigdy nie możesz być pewny czy jesteś w dołku lokalnym, dołku globalnym czy w ogóle jesteś w dołku (no, chyba, że policzysz sobie również normę gradientu - czego normalnie w AG się nie robi). Dlatego zarówno przeszukiwanie przestrzeni z dala od rodziców co przeszukiwanie przestrzeni w ich pobliżu jest konieczne!

Pozdrawiam

0

Twój problem polega na tym że nie rozumiesz co to znaczy "wylosowane z pewnym prawdopodobieństwem".
Otóż przeważnie to prawdopodobieństwo jest proporcjonalne spełnieniu funkcji celu.
W założeniach mojego poprzedniego postu 10% populacji spełniają funkcje celu średnio 10 razy lepiej niż pozostałe 90%.
Oblicz sobie jakie jest prawdopodobieństwo tego że przy takich warunkach oba rodzica będą z tych 10%.
Prawdopodobnie nie znasz się na rachunkach prawdopodobieństwa więc daje odpowiedź:
Prawdopodobieństwo że oba rodzica będą z tych 10% wynosi ponad 25% czyli bez mutacji w następnym pokoleniu będzie w tym dołku już 25% populacji.
A po kilku pokoleniach całe 100%.

0
_13th_Dragon napisał(a)

Twój problem polega na tym że nie rozumiesz co to znaczy "wylosowane z pewnym prawdopodobieństwem".
Otóż przeważnie to prawdopodobieństwo jest proporcjonalne spełnieniu funkcji celu.
W założeniach mojego poprzedniego postu 10% populacji spełniają funkcje celu średnio 10 razy lepiej niż pozostałe 90%.
Oblicz sobie jakie jest prawdopodobieństwo tego że przy takich warunkach oba rodzica będą z tych 10%.
Prawdopodobnie nie znasz się na rachunkach prawdopodobieństwa więc daje odpowiedź:
Prawdopodobieństwo że oba rodzica będą z tych 10% wynosi ponad 25% czyli bez mutacji w następnym pokoleniu będzie w tym dołku już 25% populacji.
A po kilku pokoleniach całe 100%.

Ty no, rzeczywiście pojęcia nie mam o rachunku prawdopodobieństwa...
Sorry, ale wróżką nie jestem i nie potrafię odgadywać Twoich "założeń", które często są nieczytelne z uwagi na Twój bardzo oszczędny tryb pisania...

Ale jak taki mądry jesteś to teraz miszczu podaj mi proszę jakiś praktyczny przykład gdzie będziesz miał możliwość wystąpienia takich warunków o których piszesz. Tzn. losujesz np. populację w której jest 100 osobników z czego 10 z nich trafia (chyba jakimś "cudem") do jakiegoś dołka, który nie jest minimum globalnym (i nie jest w jego pobliżu) a pozostałe 90% z nich trafia chyba na jakąś górkę i ma 10 razy gorszy wynik od tych 10%...
Nie wiem w jakim Ty świecie żyjesz i jak miałaby wyglądać taka funkcja i jakiego musiałbyś mieć farta, żeby tak wylosować swoje wstępne zmienne, ale może mi coś podpowiesz?

Pozwól chłopcze, że teraz ja założę pewną hipotezę: może i bawiłeś się AG i wiesz jak one działają, ale nigdy nie wykorzystałeś ich w praktycznych problemach a już na pewno nie porównywałeś wyników działania AG z i bez mutacji.
To o czym Ty piszesz praktycznie nigdy nie powinno mieć miejsca - nawet w końcowym etapie pracy algorytmu. Fakt, może być kilka zestawów znacznie lepszych od innych ale po pierwsze nie będzie to różnica 10-krotna, po drugie zazwyczaj wyniki funkcji są rozłożone mniej więcej równomiernie tzn. gdy najlepszy wynik funkcji f(x) =100 a najgorszy np. f(x) = 1000 to jakieś 50% wyników powinna być w pobliżu f(x) = 500.
A nie w stylu 10 osobników jest w pobliżu f(x)=100 a 90 osobników f(x) w okolicach 1000 -> to jest wręcz śmieszne.
Nie ważne, czy wykorzystujesz AG w problemie komiwojażera czy do optymalizacji wag w sieci neuronowej czy innych zagadnieniach.

A tak z ciekawości możesz mnie oświecić jak doszedłeś do tych 25%?

0
wojtekN napisał(a)

Ty no, rzeczywiście pojęcia nie mam o rachunku prawdopodobieństwa...

wojtekN napisał(a)

A tak z ciekawości możesz mnie oświecić jak doszedłeś do tych 25%?
Robi się ciekawie nie potrafisz tego sam obliczyć? A to podstawy rachunków prawdopodobieństwa.
10% populacji ma 10 razy większą szanse na bycie wylosowanym (od pozostałych 90%) ponieważ 10 razy lepiej spełniają funkcje celu.
Więc prawdopodobieństwo że losując jednego osobnika trafimy na jednego z 10% wynosi 1010/(1010+901)=0.526 czyli ponad 50% szans.
Stąd szanse na wylosowanie dwóch z rzędu wynosi: 0.526
0.526=0.277 czyli ponad 25%.

wojtekN napisał(a)

Sorry, ale wróżką nie jestem i nie potrafię odgadywać Twoich "założeń", które często są nieczytelne z uwagi na Twój bardzo oszczędny tryb pisania...
A ty co czytasz co trzeci wiersz? Zawsze łatwiej zrozumieć jak coś jest zwięzłe napisano.

wojtekN napisał(a)

... żeby tak wylosować swoje wstępne zmienne, ale może mi coś podpowiesz?
Przecież jaśnie i wyraźnie napisałem że nie mówimy o wstępnych zmiennych tylko o jakimś kolejnym kroku. Jeżeli istnieje jakikolwiek minimum lokalny a do niego nie trafi (w jakimś kolejnym kroku) przynajmniej 10% populacji to znaczy cały AG jest napisany do bani. Więc założyłem tylko że istnieje minimum lokalny ze stromym zboczem.

wojtekN napisał(a)

... gdy najlepszy wynik funkcji f(x) =100 a najgorszy np. f(x) = 1000 to jakieś 50% wyników powinna być w pobliżu f(x) = 500.
Podstawy zrozumienia tekstu pisanego się kłaniają. Rozpatrzmy to co podałeś, czyli co będzie w następnej generacji tego twojego przykładu.
50% w pobliżu 100, drugie 50% w pobliżu 500 szanse na wylosowanie tych w okolice 100 jest 5 razy większa od tych w pobliżu 500.
Prawdopodobieństwo wylosowania: 505/(505+501)=0.833 (83%), szansa ze oba rodzice będą z tej grupy w okolicach 100: 0.8330.833=0.694
Czyli w następnym kroku w okolice 100 będzie 69% populacji.
Kolejne kroki:
695/(695+411)=0.894, 0.8940.894=0.799 (80%)
805/(805+201)=0.952, 0.9520.952=0.906 (90%)
905/(905+101)=0.978, 0.9780.978=0.956 (95%)

Wniosek jak tylko kilka osobników trafią w stromy minimum lokalny to błyskawicznie "wsysa" do siebie resztę populacji, eliminując szansę dotarcia do innego minima lokalnego (lub nawet globalnego). Jedyne rada na ten problem - mutacja.

0

zazwyczaj wyniki funkcji są rozłożone mniej więcej równomiernie tzn. gdy najlepszy wynik funkcji f(x) =100 a najgorszy np. f(x) = 1000 to jakieś 50% wyników powinna być w pobliżu f(x) = 500.
A nie w stylu 10 osobników jest w pobliżu f(x)=100 a 90 osobników f(x) w okolicach 1000 -> to jest wręcz śmieszne.

Śmieszne to jest co teraz napisałeś.
W podejsciu teoretycznym - wyobraz sobie szukanie ekstremum funkcji sinusoidalnej z lekko wyciagnietym jednym z wierzcholkow. Na bardzo duzym obszarze. Tak cieżko wpasc w jedno w niezliczonych minimow lokalnych?
W podejściu praktycznym - algorytmow genetycznych uzywa sie do problemow, ktorye potrafimy rozwiazac w jakis inny lepszy sposob. Często tez oznacza to, ze nie mozemy powiedziec absolutnie nic o rozkładzie danych w badanym obszarze.

0

Dlatego warto stosować niszowanie albo inne metody zapobiegające dążeniu całej populacji ku jednemu minimum.

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