Reprezentacja genetyczna

W programowaniu komputerowym reprezentacja genetyczna jest sposobem przedstawiania rozwiązań/osobników w ewolucyjnych metodach obliczeniowych. Termin ten obejmuje zarówno konkretne struktury danych , jak i typy danych wykorzystywane do realizacji materiału genetycznego proponowanych rozwiązań w postaci genomu, a także relacje między przestrzenią poszukiwań a przestrzenią problemową. W najprostszym przypadku przestrzeń poszukiwań odpowiada przestrzeni problemowej (reprezentacja bezpośrednia). Wybór reprezentacji problemu jest powiązany z wyborem operatorów genetycznych , z których oba mają decydujący wpływ na efektywność optymalizacji. Reprezentacja genetyczna może kodować wygląd, zachowanie, cechy fizyczne jednostek. Różnica w reprezentacjach genetycznych jest jednym z głównych kryteriów wyznaczających granicę między znanymi klasami obliczeń ewolucyjnych.

Terminologia jest często analogiczna do genetyki naturalnej . Blok pamięci komputera, który reprezentuje jedno rozwiązanie kandydujące, nazywany jest jednostką. Dane w tym bloku nazywane są chromosomem . Każdy chromosom składa się z genów. Możliwe wartości określonego genu nazywane są allelami . Programista może reprezentować wszystkie osobniki populacji za pomocą kodowania binarnego , permutacyjnego , drzewiastego lub dowolnej z kilku innych reprezentacji.

Reprezentacje w niektórych popularnych algorytmach ewolucyjnych

Algorytmy genetyczne (GA) zazwyczaj reprezentacje liniowe; są one często, ale nie zawsze, binarne. Hollanda GA wykorzystywał tablice bitów . Tablice innych typów i struktur mogą być używane zasadniczo w ten sam sposób. Główną właściwością, która sprawia, że te reprezentacje genetyczne są wygodne, jest to, że ich części można łatwo dopasować ze względu na ich stały rozmiar. Ułatwia to prostą obsługę zwrotnicy. Reprezentacje o zmiennej długości były również badane w algorytmach genetycznych , ale implementacja krzyżowania jest w tym przypadku bardziej złożona.

Strategia ewolucji wykorzystuje liniowe reprezentacje o wartościach rzeczywistych, np. tablicę wartości rzeczywistych. Wykorzystuje głównie gaussowską i krzyżowanie mieszania/uśredniania.

Programowanie genetyczne (GP) zapoczątkowało reprezentacje przypominające drzewa i opracowało operatory genetyczne odpowiednie dla takich reprezentacji. Reprezentacje przypominające drzewa są używane w GP do reprezentowania i rozwijania programów funkcjonalnych o pożądanych właściwościach.

Algorytm genetyczny oparty na człowieku (HBGA) oferuje sposób na uniknięcie rozwiązywania problemów z twardą reprezentacją poprzez outsourcing wszystkich operatorów genetycznych do agentów zewnętrznych, w tym przypadku ludzi. Algorytm nie potrzebuje wiedzy o konkretnej ustalonej reprezentacji genetycznej, o ile istnieje wystarczająca liczba czynników zewnętrznych zdolnych do obsługi tych reprezentacji, co pozwala na dowolne i ewoluujące reprezentacje genetyczne.

Wspólne reprezentacje genetyczne

Rozróżnienie między przestrzenią poszukiwań a przestrzenią problemową

Analogicznie do biologii, algorytmy ewolucyjne (EA) rozróżniają przestrzeń problemową (odpowiadającą fenotypowi ) i przestrzeń poszukiwań (odpowiadającą genotypowi ). Przestrzeń problemu zawiera konkretne rozwiązania rozwiązywanego problemu, podczas gdy przestrzeń wyszukiwania zawiera zakodowane rozwiązania. Mapowanie do przestrzeni problemowej nazywa się mapowaniem genotyp-fenotyp . Operatory genetyczne są stosowane do elementów przestrzeni poszukiwań, a dla oceny elementy przestrzeni poszukiwań są odwzorowywane na elementy przestrzeni problemowej poprzez mapowanie genotyp-fenotyp.

Relacje między przestrzenią poszukiwań a przestrzenią problemową

Znaczenie odpowiedniego wyboru przestrzeni wyszukiwania dla sukcesu aplikacji EA zostało wcześnie rozpoznane. Odpowiedniej przestrzeni poszukiwań, a tym samym odpowiedniemu mapowaniu genotyp-fenotyp, można nałożyć następujące wymagania:

Kompletność

Wszystkie możliwe dopuszczalne rozwiązania muszą zawierać się w przestrzeni poszukiwań.

Nadmierność

Kiedy istnieje więcej możliwych genotypów niż fenotypów, genetyczna reprezentacja EA nazywana jest redundantną . W naturze nazywa się to zdegenerowanym kodem genetycznym . W przypadku reprezentacji redundantnej możliwe są mutacje neutralne . Są to mutacje, które zmieniają genotyp, ale nie wpływają na fenotyp. Tak więc, w zależności od zastosowania operatorów genetycznych , może istnieć fenotypowo niezmienione potomstwo, co może prowadzić między innymi do niepotrzebnych ustaleń dotyczących sprawności. Ponieważ ocena w rzeczywistych aplikacjach zwykle stanowi lwią część czasu obliczeń, może spowolnić optymalizacji . Ponadto może to spowodować, że populacja będzie miała większą różnorodność genotypową niż różnorodność fenotypowa, co może również utrudniać postęp ewolucyjny.

W biologii neutralna teoria ewolucji molekularnej stwierdza, że efekt ten odgrywa dominującą rolę w ewolucji naturalnej. To zmotywowało naukowców ze społeczności EA do zbadania, czy mutacje neutralne mogą poprawić funkcjonowanie EA, dając populacjom, które zbliżyły się do lokalnego optimum, sposób na ucieczkę od tego lokalnego optimum poprzez dryf genetyczny . Jest to dyskutowane kontrowersyjnie i nie ma rozstrzygających wyników dotyczących neutralności w EA. Z drugiej strony istnieją inne sprawdzone środki radzenia sobie z przedwczesną konwergencją .

Miejscowość

Lokalność reprezentacji genetycznej odpowiada stopniowi zachowania odległości w przestrzeni poszukiwań w przestrzeni problemowej po mapowaniu genotyp-fenotyp. Oznacza to, że reprezentacja ma wysoką lokalność dokładnie wtedy, gdy sąsiedzi w przestrzeni poszukiwań są również sąsiadami w przestrzeni problemowej. Aby udane schematy nie zostały zniszczone przez mapowanie genotyp-fenotyp po niewielkiej mutacji , lokalizacja reprezentacji musi być wysoka.

skalowanie

W mapowaniu genotyp-fenotyp elementy genotypu mogą być różnie skalowane (ważone). Najprostszym przypadkiem jest jednolite skalowanie: wszystkie elementy genotypu mają jednakową wagę w fenotypie. Typowe skalowanie jest wykładnicze. Jeśli liczby całkowite są kodowane binarnie, poszczególne cyfry wynikowej liczby binarnej mają wykładniczo różne wagi w reprezentowaniu fenotypu.

Przykład: Liczba 90 jest zapisywana binarnie (tj. o podstawie dwa) jako 1011010. Jeśli teraz jedna z przednich cyfr zostanie zmieniona w zapisie binarnym, ma to znacznie większy wpływ na zakodowaną liczbę niż jakakolwiek zmiana tylnych cyfr ( nacisk selekcyjny ma wykładniczy większy wpływ na przednie cyfry).

Z tego powodu skalowanie wykładnicze skutkuje losowym ustaleniem „tylnych” lokalizacji w genotypie, zanim populacja zbliży się wystarczająco do optimum, aby dostosować się do tych subtelności.

Hybrydyzacja i naprawa w mapowaniu genotyp-fenotyp

Podczas mapowania genotypu do ocenianego fenotypu można wykorzystać wiedzę specyficzną dla domeny, aby ulepszyć fenotyp i/lub upewnić się, że spełnione są ograniczenia. Jest to powszechnie stosowana metoda poprawy wydajności EA pod względem czasu działania i jakości rozwiązania. Poniżej przedstawiono dwa z trzech przykładów.

Przykłady

Przykład reprezentacji bezpośredniej

Oczywistym i powszechnie stosowanym kodowaniem problemu komiwojażera i związanych z nim zadań jest numerowanie kolejnych miast, które mają być odwiedzone, i przechowywanie ich jako liczb całkowitych w chromosomie . Operatory genetyczne muszą być odpowiednio przystosowane, aby zmieniały jedynie kolejność miast (genów) i nie powodowały delecji ani duplikacji. Zatem kolejność genów odpowiada kolejności miast i istnieje proste mapowanie jeden do jednego.

Przykład złożonego mapowania genotyp-fenotyp.

W zadaniu szeregowania z heterogenicznymi i częściowo alternatywnymi zasobami, które mają być przypisane do zbioru podzadań, genom musi zawierać wszystkie informacje niezbędne do poszczególnych operacji szeregowania lub musi być możliwe ich wyprowadzenie. Oprócz kolejności podzadań do wykonania, zawiera to informacje o wyborze zasobu. Fenotyp składa się następnie z listy podzadań wraz z ich czasem rozpoczęcia i przypisanymi zasobami. Aby móc to stworzyć, należy utworzyć tyle macierzy alokacji, ile zasobów można przydzielić maksymalnie do jednego podzadania. W najprostszym przypadku jest to jeden zasób, np. jedna maszyna, która może wykonać podzadanie. Macierz alokacji jest macierzą dwuwymiarową, w której jeden wymiar to dostępne jednostki czasu, a drugi to zasoby do alokacji. Puste komórki macierzy oznaczają dostępność, natomiast wpis wskazuje numer przypisanego podzadania. Tworzenie macierzy alokacji zapewnia po pierwsze, że nie ma niedopuszczalnych wielokrotnych alokacji. Po drugie, można z niego odczytać czasy rozpoczęcia podzadań oraz przydzielone zasoby.

Typowym ograniczeniem przy planowaniu zasobów do podzadań jest to, że zasób można przydzielić tylko raz na jednostkę czasu i że rezerwacja musi obejmować ciągły okres czasu. Aby osiągnąć to w odpowiednim czasie, co jest powszechnym celem optymalizacji, a nie ograniczeniem, można zastosować prostą heurystykę : Przydziel wymagane zasoby na żądany okres tak wcześnie, jak to możliwe, unikając podwójnych rezerwacji. Zaleta tej prostej procedury jest dwojaka: pozwala uniknąć ograniczeń i pomaga w optymalizacji.

Jeśli problem szeregowania zostanie zmodyfikowany do szeregowania przepływów pracy zamiast niezależnych podzadań, przynajmniej niektóre kroki robocze przepływu pracy muszą być wykonane w określonej kolejności. Jeśli wcześniej opisana heurystyka planowania określa teraz, że poprzednik kroku roboczego nie został ukończony, gdy powinien zostać uruchomiony, pomocny może być następujący mechanizm naprawczy: Odłóż planowanie tego etapu roboczego do czasu zakończenia wszystkich jego poprzedników. Ponieważ genotyp pozostaje niezmieniony, a naprawa jest wykonywana tylko na poziomie fenotypu, nazywana jest również naprawą fenotypową .

Przykład opartego na heurystyce mapowania genotyp-fenotyp

Poniższe zadanie planowania układu ma na celu zilustrowanie różnych zastosowań heurystyki w mapowaniu genotyp-fenotyp: Na prostokątnej powierzchni należy rozmieścić różne typy geometryczne obiektów w taki sposób, aby jak najmniejsza powierzchnia pozostała niewykorzystana. Obiekty można obracać, po umieszczeniu nie mogą na siebie nachodzić i muszą być ustawione całkowicie na powierzchni. Powiązanym zastosowaniem byłaby minimalizacja ilości odpadów podczas wycinania części z blachy stalowej lub tkaniny.

Za zmienne do wyznaczenia można uznać współrzędne środków obiektów oraz kąt obrotu sprowadzony do możliwych izomorfizmów geometrii obiektów. Jeśli zostanie to zrobione bezpośrednio przez EA, prawdopodobnie będzie wiele nakładek. Aby tego uniknąć, EA określa tylko kąt i współrzędną jednego boku prostokąta. Każdy obiekt jest teraz obracany i ustawiany na krawędzi tej strony, przesuwając go w razie potrzeby, tak aby znalazł się wewnątrz prostokąta, gdy zostanie następnie przesunięty. Następnie przesuwa się go równolegle na drugą stronę, aż dotknie innego przedmiotu. W ten sposób unika się nakładania się, a niewykorzystany obszar jest zmniejszany na każde umieszczenie, ale nie ogólnie, co pozostawia się optymalizacji.