Algorytmy genetyczne - tematy zaawansowane
W tej sekcji przedstawiamy kilka zaawansowanych tematów dotyczących algorytmów genetycznych. Czytelnik szukający jedynie wprowadzenia do AH może pominąć tę sekcję.
Ograniczone problemy optymalizacji
Ograniczone problemy optymalizacji to te problemy optymalizacyjne, w których musimy maksymalizować lub minimalizować daną wartość funkcji celu, która podlega pewnym ograniczeniom. Dlatego nie wszystkie wyniki w przestrzeni rozwiązań są wykonalne, a przestrzeń rozwiązań zawiera możliwe obszary, jak pokazano na poniższym rysunku.
W takim scenariuszu operatorzy krzyżowania i mutacji mogą dać nam rozwiązania, które są niewykonalne. W związku z tym w przypadku ograniczonych problemów optymalizacji należy zastosować dodatkowe mechanizmy w GA.
Niektóre z najczęstszych metod to -
Za pomocą penalty functions co zmniejsza przydatność niewykonalnych rozwiązań, najlepiej tak, aby przydatność była zmniejszana proporcjonalnie do liczby naruszonych ograniczeń lub odległości od wykonalnego obszaru.
Za pomocą repair functions które biorą niewykonalne rozwiązanie i modyfikują je tak, aby naruszone ograniczenia zostały spełnione.
Not allowing infeasible solutions w ogóle wejść do populacji.
Użyć special representation or decoder functions co zapewnia wykonalność rozwiązań.
Podstawy teoretyczne
W tej sekcji omówimy schemat i twierdzenie NFL wraz z hipotezą bloku konstrukcyjnego.
Twierdzenie o schemacie
Naukowcy próbowali zrozumieć matematykę stojącą za działaniem algorytmów genetycznych, a twierdzenie o schemacie Hollanda jest krokiem w tym kierunku. W ciągu roku wprowadzono różne ulepszenia i sugestie do twierdzenia o schemacie, aby uczynić je bardziej ogólnym.
W tej sekcji nie zagłębiamy się w matematykę twierdzenia o schemacie, a raczej staramy się wypracować podstawowe zrozumienie tego, czym jest twierdzenie o schemacie. Podstawowa terminologia, którą należy znać, jest następująca -
ZA Schemajest „szablonem”. Formalnie jest to ciąg nad alfabetem = {0,1, *},
gdzie * nie obchodzi i może mieć dowolną wartość.
Dlatego * 10 * 1 może oznaczać 01001, 01011, 11001 lub 11011
Z punktu widzenia geometrii schemat jest hiperpłaszczyzną w przestrzeni poszukiwań rozwiązań.
Order schematu to liczba określonych ustalonych pozycji w genie.
Defining length to odległość między dwoma najdalszymi stałymi symbolami w genie.
Twierdzenie o schemacie stwierdza, że ten schemat o ponadprzeciętnej sprawności, krótkiej długości definiowanej i niższym rzędzie ma większe szanse na przetrwanie krzyżowania i mutacji.
Hipoteza blokowa
Bloki konstrukcyjne to schematy niskiego rzędu, o małej długości definiującej, o podanej powyżej średniej sprawności. Hipoteza bloku budulcowego mówi, że takie bloki budulcowe służą jako podstawa sukcesu GA i adaptacji w GA w miarę ich postępu poprzez sukcesywną identyfikację i rekombinację takich „bloków budulcowych”.
Twierdzenie o braku darmowego lunchu (NFL)
Wolpert i Macready w 1997 roku opublikowali artykuł zatytułowany „No Free Lunch Theorems for Optimization”. Zasadniczo stwierdza się, że jeśli uśrednimy wszystkie możliwe problemy, to wszystkie nieodwiedzające algorytmy czarnej skrzynki będą wykazywać taką samą wydajność.
Oznacza to, że im lepiej rozumiemy problem, nasz AH staje się bardziej specyficzny dla problemu i daje lepszą wydajność, ale nadrabia to, słabo radząc sobie z innymi problemami.
Uczenie maszynowe oparte na GA
Algorytmy genetyczne znajdują również zastosowanie w uczeniu maszynowym. Classifier systems są formą genetics-based machine learning(GBML), które są często używane w dziedzinie uczenia maszynowego. Metody GBML to niszowe podejście do uczenia maszynowego.
Istnieją dwie kategorie systemów GBML -
The Pittsburg Approach - W tym podejściu jeden chromosom zakodował jedno rozwiązanie, więc rozwiązaniom przypisuje się dopasowanie.
The Michigan Approach - jedno rozwiązanie jest zwykle reprezentowane przez wiele chromosomów, więc dopasowanie jest przypisywane rozwiązaniom częściowym.
Należy pamiętać, że standardowe zagadnienia, takie jak crossover, mutation, lamarckian czy darwinian, są również obecne w systemach GBML.