Programowanie genetyczne, a programowanie ewolucyjne - różnice, cechy wspólne - prośba o weryfikacje

Witam, poszukuję odpowiedzi na pytanie zadane w temacie. Znalazłem na ten temat trochę informacji ale chciałbym się dowiedzieć czy przypadkiem czegoś nie przeoczyłem. O to cechy wspólne i różnice, które udało mi się znaleźć:

Cechy wspólne:

• Zarówno programowanie ewolucyjne jak i programowanie genetyczne są podzbiorami algorytmów ewolucyjnych.
• Nie gwarantują znalezienia najlepszego rozwiązania, ale w zamian otrzymujemy rozwiązanie bardzo dobre w rozsądnym czasie.
• W jednym i drugim wykorzystuje się mutacje oraz pewne techniki mające na celu ocenę poszczególnych osobników populacji.

Różnice:

• W programowaniu ewolucyjnym nie wykorzystuje się krzyżowania, natomiast w programowaniu genetycznym tak.
• Programowanie ewolucyjne jest wykorzystywane do rozwiązywania różnych problemów optymalizacyjnych, natomiast programowanie genetyczne wykorzystywane jest do generowania programów realizujących konkretne zadania.
• W programowaniu ewolucyjnym struktura osobników populacji może być różna w zależności od rozwiązywanego problemu natomiast w programowaniu genetycznym poszczególne programy (osobniki) reprezentowane są za pomocą drzew.
• W programowaniu ewolucyjnym osobniki oceniane są za pomocą funkcji przystosowania, natomiast w programowaniu genetycznym przydatność programów sprawdza się w pewnym środowisku testowym poprzez weryfikację czy rozwiązują zadany problem.
• W programowaniu genetycznym selekcja osobników odbywa się tak samo jak w algorytmach genetycznych (koło ruletki, ranking liniowy, turniej) natomiast w programowaniu ewolucyjnym może wystąpić etap selekcji, ale nie musi (populacja stała).

Tu nie chodzi o algorytmy ewolucyjne i algorytmy genetyczne. Tylko o programowanie genetyczne i programowanie ewolucyjne.

Według tego źródła algorytm ewolucyjny stanowi ogólne pojęcia w skład którego wchodzi m.in. programowanie genetyczne, algorytmy genetyczne, programowanie ewolucyjne, strategie ewolucyjne:
http://pl.wikipedia.org/wiki/Algorytm_ewolucyjny

W tym źródle przedstawiona jest różnica pomiędzy algorytmem genetycznym a programowaniem genetycznym:
http://www.k0pper.republika.pl/geny.htm
Czyli programowanie genetyczne stanowi pewien szczególny przypadek algorytmu genetycznego, w którym osobniki reprezentowane są za pomocą drzew i szukany jest program rozwiązujący dany problem.

Dodatkowo posiłkowałem się następującymi źródłami:
http://www.cleveralgorithms.com/nature-inspired/evolution/evolutionary_programming.html

The typical GA approach involves encoding the problem solutions as a string of representative tokens, the GENOME. In EP, the representation follows from the problem.

GA = Genetic Algorithm czyli algorytm genetyczny,
EP = Evolutionary Programming czyli programowanie ewolucyjne
Rozumiem że ten cytat dotyczy różnicy w reprezentowaniu osobnika w GA i EP. Natomiast w programowaniu genetycznym (GP = Genetic Programming) osobniki są reprezentowane jako drzewa.
Natomiast w EP osobniki są reprezentowane różnie w zależności od problemu. -> nie jestem pewny czy dobrze to interpretuje?

http://www.aip.de/~ast/EvolCompFAQ/Q1_2.htm

W tym źródle jest informacja o niestosowaniu krzyżowania w programowaniu ewolucyjnym:
http://pl.wikipedia.org/wiki/Programowanie_ewolucyjne

rydzu napisał(a):

Witam, poszukuję odpowiedzi na pytanie zadane w temacie. Znalazłem na ten temat trochę informacji ale chciałbym się dowiedzieć czy przypadkiem czegoś nie przeoczyłem. O to cechy wspólne i różnice, które udało mi się znaleźć:

Generalnie programowanie (czy tam algorytmy - na jedno wychodzi) genetyczne i ewolucyjne
to marketingowa ściema. Wszystkie one zaliczają się do odmian błądzenia bardziej lub
mnie zrandomizowanego. Jednak w pewnym momencie trudno było zrobić z tego samego
materiału doktorat, albo trudno było sprzedać program na bazie tego samego algorytmu,
więc wprowadzono pompatyczne nazwy, takie jak algorytm genetyczny czy ewolucyjny -
wielu się na to nabrało.

Istotną różnicą jaką autorzy dość zgodnie podkreślają pomiędzy AG a AE jest to, że w AG
ma dominować krzyżowanie, a w AE mutacja. W praktyce dużo dużo łatwiej jest
napisać "dobry" AE niż AG. Wynika to z tego faktu, że zaprojektowanie dobrych
operatorów krzyżowania (które mają dominować w AG) zwykle jest bardzo trudne.
Dlatego najczęściej stosuje się w praktyce naiwny algorytm genetyczny i zwykle
wypada on znacznie gorzej niż AE.

rydzu napisał(a):

• Zarówno programowanie ewolucyjne jak i programowanie genetyczne są podzbiorami algorytmów ewolucyjnych.

Nie widzę żadnego sensu precyzyjnego rozróżniania algorytmów na AG i AE, są
to po prostu odmiany losowych algorytmów optymalizacyjnych. Niemniej ciekawą
próbę usystematyzowania nazewnictwa można znaleźć w książce Arabasa. Jednak
co z tego, jeśli w praktyce algorytm dostosowuje się do zadania i znowu trudno
jest powiedzieć czy on jest bardziej ewolucyjny, czy bardziej genetyczny, a może
rojowy?

rydzu napisał(a):

• Nie gwarantują znalezienia najlepszego rozwiązania, ale w zamian otrzymujemy rozwiązanie bardzo dobre w rozsądnym czasie.

Zależy od trudności zadania. Algorytmy genetyczne czy tam ewolucyjne to ostateczna ostateczność - czyli
działają najgorzej i dają rozwiązania najgorsze, przy czym klasyczny algorytm genetyczny często działa jeszcze
gorzej niż zwykły algorytm losowy. Jeśli do danego zadania nie ma dobrego algorytmu, to wtedy stosujemy
rozwiązanie rozpaczy, może nim być algorytm ewolucyjny, genetyczny, rojowy, czy tam jakiś inny zrandomizowany.
Wystarczy dać proste zadanie takim algorytmom i widać jak szybko rośnie niezbędny czas obliczeń.

rydzu napisał(a):

• W jednym i drugim wykorzystuje się mutacje oraz pewne techniki mające na celu ocenę poszczególnych osobników populacji.

Tak.

rydzu napisał(a):

• W programowaniu ewolucyjnym nie wykorzystuje się krzyżowania, natomiast w programowaniu genetycznym tak.

Często spotyka się taką definicję, ale nie płyną z tego żadne wyraźnie korzyści dla praktycznego rozwiązywania
problemów. Nic nie stoi na przeszkodzie aby algorytmem ewolucyjnym wyhodować sobie 10 osobników a potem
je krzyżować.

rydzu napisał(a):

• Programowanie ewolucyjne jest wykorzystywane do rozwiązywania różnych problemów optymalizacyjnych, natomiast programowanie genetyczne wykorzystywane jest do generowania programów realizujących konkretne zadania.

Brzmi jak propaganda Gooldberga i Holanda :) W praktyce niestety AG nie może zrealizować tak trudnego zadania :)

rydzu napisał(a):

• W programowaniu ewolucyjnym struktura osobników populacji może być różna w zależności od rozwiązywanego problemu natomiast w programowaniu genetycznym poszczególne programy (osobniki) reprezentowane są za pomocą drzew.

Nie ma takich ograniczeń, można używać dowolnych reprezentacji osobników. Drzewiaste struktury
zdaje się że J. Koza zaproponował jako pierwszy, ale kod utajnił, a jego rzekome sukcesy są
co najmniej podejrzane.

rydzu napisał(a):

• W programowaniu ewolucyjnym osobniki oceniane są za pomocą funkcji przystosowania, natomiast w programowaniu genetycznym przydatność programów sprawdza się w pewnym środowisku testowym poprzez weryfikację czy rozwiązują zadany problem.

Niekoniecznie, w genetycznym też można używać funkcji oceniającej.

rydzu napisał(a):

• W programowaniu genetycznym selekcja osobników odbywa się tak samo jak w algorytmach genetycznych (koło ruletki, ranking liniowy, turniej) natomiast w programowaniu ewolucyjnym może wystąpić etap selekcji, ale nie musi (populacja stała).

Nie bardzo rozumiem o co tutaj chodzi. W jednym i w drugim algorytmie można przyjmować różne
techniki wypływające na przeżywalność osobników. Można stare uśmiercać, albo te o gorszej
funkcji przystosowania, albo można wybrać jakąś technikę kombinowaną. Zwykle gdy się
pisze AE to ma się na myśli ewolucję jednego osobnika ale nie koniecznie, bo i tam nie ma miejsca na selekcję - z
czego dokonać selekcji jeśli jest tylko jeden. Ale w gruncie rzeczy kto nam zabrania równolegle
uruchomić AE na 20 osobnikach i te które nie poprawiły swojej funkcji oceny od iluś tam iteracji
można zastępować lepszymi.

Pozwolę sobie na mały dodatek bez zajmowania się nazewnictwem. Dla rozwiązania jakiegoś prostego problemu będziemy losować pewne "statyczne" obiekty, mutować je, krzyżować i co tam kto jeszcze sobie zechce. Na przykład możemy programując przeciwnika w jakiejś wyścigowej grze wyewoluować mu zestaw parametrów. Z góry określamy, w jakich zakresach parametrów mamy się obracać, a ewolucji zostawiamy tylko dobór zestawu.

W zaawansowanych problemach, raczej naukowych niż w codziennej praktyce większości programistów, pozwolimy nie tylko na ewolucję z góry zadanych parametrów, ale i na ewolucję samych algorytmów. Granica między jednym a drugim może nie jest oczywista, ale czym innym jest obiekt z odgórnie zadanymi metodami i parametrami znalezionymi na skutek poszukiwań ewolucyjnych, a czym innym obiekt, którego metody zaprogramowały się same i mogą nie być przejrzyste dla programisty.

Myślę, że najlepiej zacząć to porównanie od tego, że te algorytmy są zaczerpnięte ze świata biologii, bo ta podstawa jakoś tu nie jest widoczna, a potem sobie jako przykład wziąć ewolucję człowieka i spojrzeć na to jak to wygląda w skali 1 poczęcia, 1 dnia, 1 epoki oraz jak to się ma do roli środowiska - ludzi i przyrody. Masz dużo nazw i cech, ale czy znasz dla każdej nazwy i cechy przykład z życia? To dobry sposób na weryfikację zgromadzonego materiału.