Reprezentacja genotypu

Jedną z najważniejszych decyzji, jakie należy podjąć podczas wdrażania algorytmu genetycznego, jest określenie reprezentacji, której będziemy używać do reprezentowania naszych rozwiązań. Zaobserwowano, że niewłaściwa reprezentacja może prowadzić do słabego działania AH.

Dlatego wybór właściwej reprezentacji, posiadanie właściwej definicji mapowań między fenotypem a przestrzeniami genotypów jest niezbędne dla sukcesu GA.

W tej sekcji przedstawiamy niektóre z najczęściej używanych reprezentacji algorytmów genetycznych. Jednak reprezentacja jest wysoce specyficzna dla problemu i czytelnik może uznać, że inna reprezentacja lub mieszanka przedstawień wymienionych tutaj może lepiej odpowiadać jego problemowi.

Reprezentacja binarna

Jest to jedna z najprostszych i najczęściej używanych reprezentacji w GA. W tego rodzaju reprezentacji genotyp składa się z ciągów bitów.

W przypadku niektórych problemów, gdy przestrzeń rozwiązań składa się z boolowskich zmiennych decyzyjnych - tak lub nie, reprezentacja binarna jest naturalna. Weźmy na przykład problem plecaka 0/1. Jeśli istnieje n elementów, możemy przedstawić rozwiązanie za pomocą łańcucha binarnego n elementów, gdzie x- ^ty element mówi, czy element x został wybrany (1), czy nie (0).

W przypadku innych problemów, szczególnie tych dotyczących liczb, możemy przedstawić liczby w ich binarnej reprezentacji. Problem z tym rodzajem kodowania polega na tym, że różne bity mają różne znaczenie, a zatem operatory mutacji i krzyżowania mogą mieć niepożądane konsekwencje. Do pewnego stopnia można to rozwiązać za pomocąGray Coding, ponieważ zmiana jednego bitu nie ma dużego wpływu na rozwiązanie.

Prawdziwie wyceniona reprezentacja

W przypadku problemów, w których chcemy zdefiniować geny za pomocą zmiennych ciągłych, a nie dyskretnych, reprezentacja o wartościach rzeczywistych jest najbardziej naturalna. Dokładność tych liczb rzeczywistych lub zmiennoprzecinkowych jest jednak ograniczona do komputera.

Reprezentacja liczby całkowitej

W przypadku genów o wartości dyskretnej nie zawsze możemy ograniczyć przestrzeń rozwiązań do binarnego „tak” lub „nie”. Na przykład, jeśli chcemy zakodować cztery odległości - północ, południe, wschód i zachód, możemy zakodować je jako{0,1,2,3}. W takich przypadkach reprezentacja liczb całkowitych jest pożądana.

Reprezentacja permutacji

W wielu problemach rozwiązanie jest reprezentowane przez kolejność elementów. W takich przypadkach najbardziej odpowiednia jest reprezentacja permutacyjna.

Klasycznym przykładem tego przedstawienia jest problem komiwojażera (TSP). W tym przypadku sprzedawca musi zwiedzić wszystkie miasta, odwiedzić każde z nich dokładnie raz i wrócić do miasta początkowego. Całkowity dystans wycieczki musi być zminimalizowany. Rozwiązaniem tego TSP jest oczywiście uporządkowanie lub permutacja wszystkich miast, dlatego użycie reprezentacji permutacji ma sens w przypadku tego problemu.