Czy programowanie genetyczne jest obecnie w stanie przekształcić jeden typ algorytmu wyszukiwania w inny? Na przykład, w dowolnym eksperymencie kiedykolwiek wyhodowano/zmutowano BubbleSort z QuickSort (zobacz http://en.wikipedia.org/wiki/Sorting_algorithm)Genetyczne algorytmy programowania i wyszukiwania
Nie jestem tego świadomy, a konkretny kierunek, który sugerujesz w swoim przykładzie wydaje się mało prawdopodobny; wymagałoby to czegoś w rodzaju perwersyjnej funkcji fitness, ponieważ sortowanie bąbelków jest gorsze od quicksort. Nie jest wykluczone, że może się to zdarzyć, ale generalnie po dobrze zrozumiałym algorytmie jest już całkiem sprawnie - przejście na inny prawdopodobnie wymaga dokonania gorszych wyborów.
Uwięzienie w lokalnych minimach nie jest nieznanym problemem w przypadku większości strategii wyszukiwania.
Charlie, tylko ciekawy, jak wyhodować następne pokolenie? Nie mogę uchwycić faktu przejścia przez sortowanie
To naprawdę jest kluczowy problem. Pamiętaj, że w centrum uwagi GA robi postępy, dokonując wielu losowych zmian i szukając czegoś, co jest "lepsze" dzięki funkcji fitness. Ten sam problem występuje w ewolucji biologicznej - możesz ewoluować od ryby do ptaka, ale wszystko, co zabiera cię znacznie bliżej ptaka, utopi się, zanim się rozmnoży. –
Kolejnym dobrym przykładem jest panda: bardzo dobrze nadaje się do dwóch rzeczy - jedzenia bambusa i bycia słodkim. Cicha nisza bambusowego lasu odchodzi, więc są zagrożone. Z drugiej strony może być tak, że "bycie słodkim" jest cechą zapewniającą przetrwanie. –
Nie ma powodu, dla którego GP nie mógłby ewoluować, np. albo dowolny typ algorytmu. Nie jestem pewien, czy naprawdę ma sens myślenie o ewolucji jednego "na" drugiego. GP po prostu rozwinie program, który coraz bardziej zbliża się do zdefiniowanej przez ciebie funkcji fitness.
Jeśli twoja funkcja fitness patrzy tylko na poprawność sortowania (i zakładając, że masz odpowiednie elementy konstrukcyjne do wykorzystania przez lekarza ogólnego), może bardzo dobrze rozwinąć zarówno BubbleSort, jak i QuickSort. Jeśli uwzględnisz także efektywność jako miarę sprawności, to może to wpłynąć na to, które z nich zostanie uznane za lepsze rozwiązanie.
Możesz zasiać w GP np. QuickSort i gdybyś miał odpowiednią funkcję fitness, to z pewnością mógłby wymyślić BubbleSort - ale mógłby wymyślić wszystko, co jest sprawniejsze niż QuickSort.
Teraz, jak długo trwa silnik GP zrobić tę ewolucję, to inna kwestia ...
Czasami warto spojrzeć na dzieła W. Daniel Hillis od lat 80-tych. Spędził dużo czasu tworząc sieci sortowania poprzez programowanie genetyczne. Podczas gdy był bardziej zainteresowany rozwiązywaniem problemu sortowania stałej liczby obiektów (16-obiektowe sieci sortujące były głównym problemem akademickim od prawie dekady), dobrze byłoby zapoznać się z jego pracą, jeśli jesteś naprawdę interesuje się algorytmami sortowania genetycznego.
W ewolucji algorytmu do sortowania listy o dowolnej długości można również zapoznać się z koncepcją koewolucji. Zbudowałem system koewolucyjny, w którym przedtem chodziło o to, by jeden algorytm genetyczny rozwijał algorytmy sortowania, podczas gdy inny GA rozwijał niesortowane listy liczb. Zdolność sortownika to jego dokładność (plus premia za mniej porównań, jeśli jest w 100% dokładna), a przydatność generatora list to liczba algorytmów sortowania błędów w sortowaniu listy.
Aby odpowiedzieć na twoje pytanie, czy bańka kiedykolwiek wyewoluowała z szybkiego, muszę powiedzieć, że będę poważnie w to wątpił, chyba że funkcja programisty jest zarówno bardzo szczegółowa, jak i nierozsądna. Tak, bańka jest bardzo prosta, więc być może GP, którego funkcja fitness była dokładna, plus rozmiar programu, ostatecznie znajdzie bańkę. Jednak dlaczego programista wybrałby rozmiar zamiast liczby porównań jako funkcję fitness, gdy to drugie określa czas wykonania?
Pytając, czy GP może rozwinąć jeden algorytm na drugi, zastanawiam się, czy jesteś całkowicie pewien, co to jest GP. Idealnie, każdy unikalny chromosom definiuje unikalny rodzaj. Populacja 200 chromosomów reprezentuje 200 różnych algorytmów. Tak, szybkie i bańka może gdzieś tam być, ale tak samo jest z 198 innymi, potencjalnie nienazwanymi metodami.
możesz chcieć rzucić okiem na to pytanie, aby porozmawiać o tym, co programowanie genetyczne może lub nie może zrobić -> http: // stackoverflow.com/questions/5732917/code-generation-by-genetic-algorithms – JohnIdol