Cześć, książkowy przykład, algorytm genetyczny szukający maximum funkcji liniowej f(x) = x w zakresie 0-15, kodowanie binarne na 4 bitach, rozwiązaniem osobnik 1111. Na tym niestety kończą się proste przykłady w materiałach które znalazłem. Mnie zastanawia sytuacja gdy szukamy w zakresie np 0-10 a zostanie stworzony osobnik 1100. Jego przystosowanie wynosi 12 z tym że jest spoza interesującej nas przestrzeni rozwiązań. Jak w takiej i podobnych sytuacjach powinien zachować się algorytm? Albo jak zapobiegać powstaniu takich osobników?
- Rejestracja:ponad 9 lat
- Ostatnio:prawie 3 lata
- Postów:38
- Rejestracja:prawie 7 lat
- Ostatnio:dzień
- Lokalizacja:Kraków
- Postów:1999
1
Jeżeli rozwiązania dopuszczalne mieszczą się w przedziale <a, b> i chcesz zakodować rozwiązanie na n bitach, musisz zakodować wartości funkcji w ten sposób, że:
- a kodujesz liczbą 0 (00000...)
- b kodujesz liczbą 2n-1 (11111...)
- dla dowolnej liczby zakodowanej binarnie 0 < x2 < 2n-1 wartość dziesiętna x10 wynosi:
Ewentualnie jeżeli zależy Ci na konkretnej dokładności wyniku (powiedzmy, że chcesz aby osobniki były rozmieszczone akurat co 1/1000 a nie 1/1024) albo masz kilka wymiarów i obszar rozwiązań dopuszczalnych nie da się opisać prostymi ograniczeniami a1 ≤ x1 ≤ b1, a2 ≤ x2 ≤ b2... itd. możesz wykorzystać funkcje kary - do podstawowej funkcji celu możesz dodać jakąś inną, która będzie nakładana, jeśli któreś ograniczenie będzie naruszone (funkcja kary zewnętrznej). Jeśli np. powstanie osobnik 1100 to odpowiednio dobrana funkcja kary sprawi, że będzie miał znacznie mniejsze szanse na przeżycie, niż dowolny "dozwolony" osobnik.
edytowany 3x, ostatnio: superdurszlak
- Rejestracja:ponad 9 lat
- Ostatnio:prawie 3 lata
- Postów:38
0
Zależy mi aby osobniki były liczbami całkowitymi nieujemnymi. W takim wypadku posługując się twoim wzorem 0001 = 0,(6) i 0010 = 1,(3) dekodowane były by do postaci dziesiętnej jako 1 poprzez zaokrąglenie. Czy takie zaokrąglanie jest zgodne z założeniami AG? I nawet jeśli tak to poprawniejsze jest zaokrąglanie czy użycie funkcji kary?
edytowany 1x, ostatnio: Foka
- Rejestracja:prawie 7 lat
- Ostatnio:dzień
- Lokalizacja:Kraków
- Postów:1999
1
Foka napisał(a):
Zależy mi aby osobniki były liczbami całkowitymi nieujemnymi. W takim wypadku posługując się twoim wzorem 0001 = 0,(6) i 0010 = 1,(3) dekodowany były by do postaci dziesiętnej jako 1 poprzez zaokrąglenie. Czy takie zaokrąglanie jest zgodne z założeniami AG? I nawet jeśli tak to poprawniejsze jest zaokrąglanie czy użycie funkcji kary?
Wydaje mi się, że już lepiej użyć funkcję kary. Zaokrąglając spowodujesz, że ileś różnych osobników może w praktyce reprezentować jedną i tę samą liczbę, poza tym będziesz musiał majstrować przy zakresie, by 10 też mogło zostać wylosowane (w przeciwnym razie przez błędy zaokrągleń może się okazać nieosiągnalne) i pewnie koniec końców powychodzą głupoty.. Szkoda zachodu, a umienie w funkcje kary może Ci się przydać ;)
- Rejestracja:ponad 9 lat
- Ostatnio:prawie 3 lata
- Postów:38
0
A jednak nie, no bo w przypadku w którym osobnik ma 3 chromosomy, gdzie każdy chromosom to pozycja na innej osi. Przykładowy osobnik 1011 1001 1100 w takiej sytuacji prawdopodobieństwo że któryś z chromosomów będzie spoza zakresu jest dosyć duża, tak naprawdę im więcej chromosomów tym większe szanse. Czy w takiej sytuacji ze względu na jeden chromosom spoza zakresu należy użyć na osobniku funkcji kary? Funkcja kary powinna brać pod uwagę ilość chromosomów spoza zakresu i ich "odchylenie" od zakresu?
- Rejestracja:prawie 7 lat
- Ostatnio:dzień
- Lokalizacja:Kraków
- Postów:1999
0
Foka napisał(a):
A jednak nie, no bo w przypadku w którym osobnik ma 3 chromosomy, gdzie każdy chromosom to pozycja na innej osi. Przykładowy osobnik 1011 1001 1100 w takiej sytuacji prawdopodobieństwo że któryś z chromosomów będzie spoza zakresu jest dosyć duża, tak naprawdę im więcej chromosomów tym większe szanse. Czy w takiej sytuacji ze względu na jeden chromosom spoza zakresu należy użyć na osobniku funkcji kary? Funkcja kary powinna brać pod uwagę ilość chromosomów spoza zakresu i ich "odchylenie" od zakresu?
Masz nałożone ileś ograniczeń, niekoniecznie na pojedyncze zmienne - możesz mieć np. coś takiego:
co możesz zapisać tak:
warunkiem będzie:
Trochę problematyczne jest to, że dokonujesz tu maksymalizacji (nie da się zadać jakieś baardzo dużej kary, bo byłaby... nagrodą), a w algorytmach genetycznych generalnie wartości funkcji celu powinny być dodatnie (bo wtedy możesz wprost stosować np. metodę koła ruletki do losowania osobników bez przekształcania funkcji) - więc odjęcie w ciemno jakiejś baaardzo dużej, ujemnej wartości w ramach kary może być kłopotliwe, bo też wyjdą jaja.
Możesz próbować przekształcić sobie funkcję celu f(x) tak, żeby zawsze być w stanie nałożyć jakąś karę gorszą, niż najgorsze rozwiązanie dopuszczalne (u Ciebie wartość 0):
edytowany 1x, ostatnio: superdurszlak
- Rejestracja:ponad 13 lat
- Ostatnio:prawie 3 lata
0
Jak już musisz zezwalać na potworki spoza zakresu, to dawaj kary "gładkie" - proporcjonalne do wady.
Czyli przy zakresie (a, b) skorygowana funkcja celu f(x) wynosi:
c = (a+b)/2 >> centrum przedziału
d = abs(f(x) - c) >> odległość od centrum przedziału
e = (b-a)/2 >> połowa przedziału
F(x) = f(x) * (b - a)/(1 + d) jeśli d > e
F(x) = f(x) jeśli d <= e