Chromosom (algorytm genetyczny) - Chromosome (genetic algorithm)

W algorytmów genetycznych , A chromosomie (czasami nazywany genotyp ) jest zestaw parametrów, które określają z proponowanych rozwiązań tego problemu, że algorytm genetyczny stara się rozwiązać. Zbiór wszystkich rozwiązań nazywany jest populacją . Chromosom jest często reprezentowany jako ciąg binarny , chociaż wykorzystuje się również wiele innych struktur danych .

Projekt chromosomu

Konstrukcja chromosomu i jego parametrów jest z konieczności specyficzna dla problemu, który ma zostać rozwiązany. Tradycyjnie chromosomy są reprezentowane binarnie jako ciągi zer i jedynek, jednak możliwe są również inne kodowania; Można zastosować prawie każdą reprezentację, która pozwala na przedstawienie rozwiązania jako łańcucha o skończonej długości. Znalezienie odpowiedniej reprezentacji domeny problemowej dla chromosomu jest ważną kwestią, ponieważ dobra reprezentacja ułatwi wyszukiwanie poprzez ograniczenie przestrzeni poszukiwań; podobnie gorsza reprezentacja pozwoli na większą przestrzeń wyszukiwania. Mutacja operatora i zwrotnica operatora stosowane przez algorytm genetyczny należy również wziąć pod uwagę konstrukcję chromosomami.

Przykład 1: reprezentacja binarna

Załóżmy, że problem polega na znalezieniu liczby całkowitej z zakresu od 0 do 255, która zapewnia maksymalny wynik dla . Możliwymi rozwiązaniami tego problemu są liczby całkowite od 0 do 255, które mogą być reprezentowane jako 8-cyfrowe ciągi binarne. W ten sposób możemy użyć 8-cyfrowego ciągu binarnego jako naszego chromosomu. Jeśli dany chromosom w populacji reprezentuje wartość 155, jego chromosomem będzie . 10011011

Zauważ, że nie jest to typ problemu, który normalnie jest rozwiązywany przez algorytm genetyczny, ponieważ można go rozwiązać za pomocą metod numerycznych; służy jedynie jako prosty przykład.

Przykład 2: reprezentacja ciągów

Bardziej realistycznym problemem, który możemy chcieć rozwiązać, jest problem komiwojażera . W tym problemie szukamy uporządkowanej listy miast, która skutkuje najkrótszą podróżą dla sprzedawcy. Załóżmy, że istnieje sześć miast, które nazwiemy A, B, C, D, E i F. Dobrym projektem dla naszego chromosomu może być uporządkowana lista, którą chcemy wypróbować. Przykładowym chromosomem, który możemy napotkać w populacji, może być DFABEC.

Selekcja, crossover i mutacja

W każdym pokoleniu algorytmu genetycznego dwa chromosomy rodzicielskie są wybierane na podstawie ich wartości dopasowania; chromosomy te są wykorzystywane przez operatorów mutacji i krzyżowania do wytworzenia dwóch chromosomów potomnych dla nowej populacji.

Bibliografia