Witam,
od pewnego czasu zacząłem interesować się algorytmami genetycznymi i ich zastosowaniem do znajdywania minimum funkcji celu. Cały proces wydaje się być banalnie prosty jednak zastanawiam się nad jedną rzeczą, której nigdzie nie wyczytałem - jak długi jest kod chromosomu w praktyce? Do tej pory spotkałem się na przykładach np. z 5-7 znaków binarnych natomiast wydaje mi się, że żeby miało to sens powinno być minimum około 30 znaków zero-jedynkowych... - czy dobrze mi się wydaje. Chodzi mi głównie dokładność miejsc po przecinku - im krótszy kod tym mniejsza dokładość...
No i pytanie jak wy używaliście tych algorytmów to jak długie były wasze chromosomy? Gdzieś spotkałem się z opinią, że przy zbyt długich chromosomach algorytm przestaje efektywnie pracować (czy jakoś tak) i zaleca się nie przesadzanie z ich długością...
Pozdrawiam i dzięki za wszelką pomoc
no tak na logikę, im dłuży tym gorzej. </quote>
Karolaq napisał(a)
no tak na logikę, im dłuży tym gorzej.
</quote>
a niby dlaczego? przecież równie dobrze można powiedzieć im krótszy tym również gorzej... przecież ten kod to zakodowana jakaś liczba. Jak dasz zbyt krótki chromosom to wyjdzie Ci np. liczba z dwoma miejscami po przecinku a przy optymalizacji funkcji najlepiej, żeby parametry były wyznaczane jak najdokładniej (np. z dokładnością 10 miejsc po przecinku)... I teraz trzeba jedynie wybrać co gorsze - dokładność parametru czy długość chromosomu? Ja właśnie nie wiem jak w praktyce jest to stosowane - jakiej długości chromosomy są najczęściej stosowane - chodzi mi o średnią długość a nie o optymalną bo nie ma czegoś takiego...
hmm... nie wiem za bardzo o co chodzi z tym linkiem (niewiele ma on wspólnego z algorytmem i jego wykorzystaniem)... Czy mogę prosić o jakąś konkretną odpowiedź :/ - coś praktycznego co pozwoli mi rozwiać moje wątpliwości...
Jak masz tam budowe chromosomu, trzeba wiedziec jakie pierwiastki i czasteczki tworza chromosom i po co ci w ogole ten chromosom do czego on jest wykorzystywany i przez co (jaki zwiazek itp.) bo po co ci jakis algorytm genetyczny
i pewnie pomylilem pojecia ale ludzie dziwnie nazywaja algorytmy nie zwiazane z genetyka,
ja uwazam za algorytm genetyczny takie cos: mamy zwirtualne ziarenko marihuany i sobie rosnie i rosnie i rosnie i daje topy _
Komorkowy_dzony, nie wiem co palisz, ale zmień dealera albo pal połowę...
proponuję przejrzeć następujące pozycje
- Arabas J. :Wykłady z algorytmów ewolucyjnych, WNT Warszawa 2001
- Michalewicz Z., Algorytmy genetyczne + struktury danych = Programy ewolucyjne. Wydawnictwa
Naukowo Techniczne Warszawa 2003. - Goldberg D. E. Algorytmy genetyczne i ich zastosowania. Wydawnictwa Naukowo Techniczne Warszawa
2003
Dla problemów inżynierskich pojedynczy fenotyp najczęściej kodujemy za pomocą 8 bitów.
Przy dużej ilości zmiennych chromosom jest długi (np. dla 10 zmiennych ma 80 bitów)
i przy tak długim chromosomie AG z kodowaniem binarnym jest mało efektywny, dlatego lepiej stosować kodowanie rzeczywisto-liczbowe (zmiennoprzecinkowe) jest cały rozdział na ten temat u Michalewicza [2]
hi ho,
dzięki za odpowiedź :)
mam jeszcze jedno pytanie:
w algorytmach genetycznych mamy coś takiego jak krzyżowanie i najpierw losujemy miejsce w chromosomie od którego mamy zmieniać/krzyżować kod. Pytanie tylko czy zawsze zmieniamy kod od wylosowanego miejsca w prawo, czy również losujemy, czy zmieniamy lewą stronę lub prawą? jest to o tyle istotne, że gdy mamy więcej zmiennych i tworzymy jeden gigantyczny ciąg binarny to w przypadku zmiany tylko prawej części lewa będzie rzadziej zmieniana...
Pozdrawiam
Jak krzyżujemy to wymieniamy informacje, więc nie ma czegoś takiego że lewa część będzie rzadziej zmieniana.
Przykładowo przy krzyżowaniu jednopunktowym dla chromosomu kodującym 3 zmienne każda po 8 bitów wygląda to tak jak niżej.
Punkt krzyżowania jest jednakowo prawdopodobny dla każdej pozycji.
Potomek 1 odziedziczy wartość zmiennej x po pierwszym rodzicu i z po drugim
oraz bardziej znaczące bity po pierwszym i mniej znaczące po drugim zmiennej y.
Zmienna y pierwszego potomka będzie nową wartością, ale w sensie metryki bliższa pierwszemu rodzicowi.
x y z x y z
V V
- 1010101010 11110000 10101010 -> 1010101010 11111111 01010101
- 0101010101 00111111 01010101 -> 0101010101 00110000 10101010
rodzice potomkowie
Można oczywiście stosować krzyżowanie wielopunktowe.
Jak pisałem wcześniej lepiej kodować rzeczywisto liczbowo wtedy krzyżujemy np. tak
x y z x y z
V V
-
20.123 7.1277 101.01 -> 20.123 4.1234 150.55
-
15.312 4.1234 150.55 -> 15.312 7.1277 101.01
rodzice potomkowie
ale można też uśredniająco czyli otrzymujemy u potomków wartości pomiędzy każdym z rodziców
z jakimś prawdopodobieństwem.x y z x y z
-
20.123 7.1277 101.01 -> 19.772 4.9122 120.01
-
15.312 4.1234 150.55 -> 16.383 7.0111 140.77
rodzice potomkowie
Jest to wierzchołek "góry lodowej", gdyż operatorów krzyżowania jest bardzo dużo.
Więcej jest tu http://www.tomaszgwiazda.pl/books_a.htm
Dzięki Adam za kolejną odpowiedź i za ciekawy przykład. Jednak analizując pierwszy przykład można zauważyć, iż potomkowie X są tacy sami jak ich rodzice a to znaczy, że ta zmienna się nie zmieniła... Zmieniła się jedynie częściowo Y i w całości Z. Nie chcę się rozwodzić na przykłady bardziej zaawansowane (zmiennoprzecinkowe) póki nie zrozumiem tych podstaw... Dlatego bardzo proszę jeszcze o wyjaśnienie jak w końcu jest z tym krzyżowaniem...
Przykładowo: mając te 3 zmienne X,Y,Z najczęściej będzie zmieniana Z, potem Y a X rzadko kiedy... Czy nie powinno być tak (moje skromne spostrzeżenie) że w każdej zmiennej powinno zmieniać się jakąś część kodu losując jaką część? - tak tylko głośno myślę :P - a ciągle mnie to męczy :(
W tym przykładzie potomek jest punktem w przestrzeni trójwymiarowej P(x,y,z) więc jeśli zmienimy choć jedną współrzędną to zmienimy jego położenie.
Jeśli chodzi o ostatnie spostrzeżenie to masz prosty dowód na to że takie krzyżowanie ma pewne wady.
Dlatego we współczesnych algorytmach genetycznych wykorzystujemy bardziej zaawansowane operatory krzyżowania. Podany przeze mnie przykład krzyżowania ma na dzień dzisiejszy charakter czysto akademicki. Chociaż algorytm z takim operatorem krzyżowania również osiągnie cel. Mamy jeszcze operator mutacji !!!. Jeszcze raz odsyłam do linku z 22.09
Adam45 napisał(a)
W tym przykładzie potomek jest punktem w przestrzeni trójwymiarowej P(x,y,z) więc jeśli zmienimy choć jedną współrzędną to zmienimy jego położenie.
No właśnie mnie martwi to, że przy takim krzyżowaniu szukamy optimum częściej na pewnych osiach przestrzeni niż na innych, czyli jakby analogicznie zrobić przykład z dwiema zmiennymi (przestrzeń dwuwymiarowa) i zobrazować to w sposób, że stoimy na jakiejś łące i szukamy najwyższego/najniższego punktu to częściej będziemy chodzić np na boki niż do przodu i do tyłu - taki własny przykład :P.
Czyli jesteśmy tak naprawdę bardziej uzależnieni od pierwszego pokolenia, gdzie były losowane pierwsze zmienne :/ a potem jedynie staramy się szukać optimum zmieniając głównie położenie na innych osiach (czy jakoś tak :) ). Mnie martwi m.in. to, że jak jakieś dwie zmienne będą bardziej skorelowane ze sobą to takie rozwiązanie będzie mało efektywne... - chociaż muszę nad tym jeszcze pomyśleć :P. No i oczywiście przeanalizować inne warianty krzyżowania :D.
No nic, bardzo dziękuję za odpowiedź i za pomoc! Resztę chyba będę musiał doczytać z książek które mi podałeś.
Pozdrawiam
Ciekawa strona o Algorytmach Genetycznych - http://www.marcin-jaworski.cba.pl/index.php?option=com_content&view=category&layout=blog&id=34&Itemid=56</url>
Czy ja wiem, czy ciekawa. Skupia się tylko na algorytmach genetycznych, nie wspominając nic o programowaniu ewolucyjnym czy strategiach ewolucyjnych... A i w samych algorytmach genetycznych przegląd technik jest niekompletny (u nas prof. Kraśniewski jest zdania, że prace przeglądowe winni pisać profesorowie, a nie studenci). Dobre jako wprowadzenie, ale nie należy na tym poprzestawać.
Myślę, że zdecydowanie lepiej poczytać jakąś książkę np. tę Arabasa. Całkiem niezły przegląd różnych technik ewolucyjnych jest też na angielskiej Wikipedii.