Algorytm genetyczny - krzyżowanie chromosomów czy genotypów?

0

Hej!
Mam drobne pytanie dotyczące algorytmu genetycznego.
Znam ogólną zasadę działania algorytmu, ale czasem zastanawiam się nad pojedynczymi elementami.
Z tego co znalazłem w literaturze - często myli się pojęcia, np. genotyp, fenotyp czy też chromosom, czasem nawet używa się ich zamiennie.
Dlatego też, wedle mojej wiedzy:
Genotyp - zbiór chromosomów osobnika populacji (a więc zbiór poszukiwanych zmiennych).
Chromosom - jedna z poszukiwanych zmiennych.
Jeśli oczywiście się nie mylę - algorytm genetyczny poszukuje zbioru zmiennych będących rozwiązaniem zadania optymalizacji (np x1, x2, x3, x4), przy czym każda ze zmiennych jest pojedynczym chromosomem (mamy więc 4 chromosomy). Genotyp jest to ciąg chromosomów poukładanych jeden przy drugim w stałej niezmiennej kolejności.

A teraz pytanie:
Czy w przypadku operacji krzyżowania należy krzyżować całe genotypy osobników czy może wybrać jeden z chromosomów krzyżowanych osobników i wykonać krzyżowanie tylko na określonym chromosomie (np. wyłącznie x1 osobnika 1 z x1 osobnika natomiast pozostałe chromosomy (x2, x3, x4) zostają bez zmian)
Wydaje mi się, że podczas operacji krzyżowania krzyżuje się genotypy osobników a nie pojedyncze chromosomy, ale może się mylę?

Pozdrawiam!

0

Hej,
w algorytmach genetycznych często sposób tworzenia tego typu algorytmu zależy od rozwiązywanego problemu obliczeniowego (żeby było jasne, nie znam się za bardzo): https://pl.wikipedia.org/wiki/Algorytm_genetyczny

1

Tak w kwestii formalnej: chromosom to tylko rodzaj "kontenera" zawierający fragment genomu, zaś jednostką dziedziczenia określonej cechy jest gen. Biologicznie gen jest kodowany na różnej długości łańcuchach par zasad. W algorytmach genetycznych możesz każdy z nich sprowadzić po prostu do jednej zmiennej czy nawet pojedynczego bitu. W praktyce to wszystko może być bardziej skomplikowane, bo możesz mieć geny dominujące i recesywne, ew. powiązane ze sobą w bardziej złożony sposób.

O ile wiem, rekombinuje się całe genotypy. Tak też wygląda to u rozdzielnopłciowych organizmów żywych. Bakterie potrafią wymieniać się drobniejszymi fragmentami genomu. Wirusy potrafią przenosić fragmenty genomu nawet pomiędzy różnymi gatunkami. No i pamiętaj o mutacjach.

0
hurgadion napisał(a):

Hej,
w algorytmach genetycznych często sposób tworzenia tego typu algorytmu zależy od rozwiązywanego problemu obliczeniowego (żeby było jasne, nie znam się za bardzo): https://pl.wikipedia.org/wiki/Algorytm_genetyczny

No nie no, wikipedia to trochę słabe źródło informacji w takich sprawach xD

Freja Draco napisał(a):

Tak w kwestii formalnej: chromosom to tylko rodzaj "kontenera" zawierający fragment genomu, zaś jednostką dziedziczenia określonej cechy jest gen. Biologicznie gen jest kodowany na różnej długości łańcuchach par zasad. W algorytmach genetycznych możesz każdy z nich sprowadzić po prostu do jednej zmiennej czy nawet pojedynczego bitu. W praktyce to wszystko może być bardziej skomplikowane, bo możesz mieć geny dominujące i recesywne, ew. powiązane ze sobą w bardziej złożony sposób.

O ile wiem, rekombinuje się całe genotypy. Tak też wygląda to u rozdzielnopłciowych organizmów żywych. Bakterie potrafią wymieniać się drobniejszymi fragmentami genomu. Wirusy potrafią przenosić fragmenty genomu nawet pomiędzy różnymi gatunkami. No i pamiętaj o mutacjach.

A więc, jeśli mam trzy poszukiwane wartości, x1,x2,x3 to x1 nie jest chromosomem? Wydawało mi się że każdy chromosom odpowiada zmiennej, przy czym chromosom składa się ze zbioru genów. Tak jak np dla zmiennej o wartości 250 mamy chromosom: 1111 1010, a każda z jedynek lub zer to pojedynczy gen.
A z tego co napisałeś, zmienną x1 jest pojedynczy gen, przy czym taki gen może zostać zapisany w postaci jeno lub wielobitowej.Co prezentuje w takim razie chromosom, dowolny fragment genomu? Skoro pełny zbiór genów (czyli genów wszystkich osobników) to genotyp?

0

Człowiek posiada tylko 23 pary chromosomów, a cech różnicujących osobniki jakby jednak trochę więcej ;)
Istnienie chromosomów X i Y pozwala na zapisanie w ramach jednego "pakietu" informacji potrzebnych do określenia płci osobnika i wszystkich związanych z tym cech. W przypadku pozostałych 22 par, podejrzewam, że taka organizacja w osobne paczki ułatwia po protu ich przetwarzanie, coś jak architektura wieloprocesorowa. No i pewnie ułatwia też samo krzyżowanie, bo wystarczy przeciąć i skleić:
title

0

Dobrze, czy tylko nie zagłębiamy się zbytnio w biologię a odchodzimy od rozwiązań stosowanych w informatyce?
Z tego co wiem, że tak napiszę "algorytmy genetyczne" w obu dziedzinach troszkę się różnią.

0

Generalnie sposób kodowanie ma wpływu na działanie AG.
Na tym polega siła tej metody.

Tym samym: operacje krzyżowania, jak i mutacji, nie mogą dotyczyć wybranych zmiennych, które sobie tu kodujemy.
Sam algorytm nie ma pojęcia co i jak sobie kodujemy w tych... no, genotypach chyba, bo to są zwyczajne ciągi bitów, albo innych symboli - jak to woli.

0
exp6 napisał(a):

Generalnie sposób kodowanie ma wpływu na działanie AG.
ma być:
Generalnie sposób kodowania zmiennych nie ma wpływu na działanie AG.

0

Krzyżujesz chromosomy. Chromosom jest nośnikiem pełnego rozwiązania, a nie pojedynczej zmiennej i jedyne co robisz, to szukasz optymalnego chromosomu. Fakt, że czasami chromosomy nazywa się genotypami, ale właściwie to bez znaczenia.

0

Nie ma żadnego algorytmu genetycznego, ale patrząc ogólnie na całe społeczeństwo to ono istnieje.
Teoretycznie i wymyślnie.

Ludzie łącząc się z innymi losowo przekazując swoje geny.

Giną w środowisku czyli nie przekazują dalej swoich genów czyli teoretycznie zadziałał algorytm genetyczny, którego funkcją jest przetrwanie.
Nie wykluczając w ten sposób, bo każdy jest wykluczony jedynie nie przekazuje się dalej genów.

W programowaniu jednak chodzi o samą idee tego, nie dosłownie o fenotypy i inne biologiczne stwory.

Coś co się dopasowuje do ram zostaje, a wszystko powstaje z losowości i chaosu.

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