Algorytmy genetyczne: wyszukiwanie i optymalizacja przez dobór naturalny

Czym są algorytmy genetyczne?

W ciągu ostatnich kilku lat sztuczna inteligencja (AI) wzbudziła ogromne zainteresowanie. Duże firmy, takie jak Google, Apple i Microsoft, aktywnie pracują nad tym tematem. W rzeczywistości sztuczna inteligencja to parasol, który obejmuje wiele celów, podejść, narzędzi i zastosowań. Algorytmy genetyczne (GA) to tylko jedno z narzędzi do inteligentnego przeszukiwania wielu możliwych rozwiązań.

GA to metaheurystyczna technika wyszukiwania i optymalizacji oparta na zasadach występujących w naturalnej ewolucji. Należy do większej klasy algorytmów ewolucyjnych.

GA utrzymuje populację chromosomów — zestaw potencjalnych rozwiązań problemu. Chodzi o to, że „ewolucja” znajdzie optymalne rozwiązanie problemu po kilku kolejnych pokoleniach — podobnie jak dobór naturalny.

GA naśladuje trzy procesy ewolucyjne: selekcję, krzyżowanie genów i mutację.

Podobnie jak w przypadku doboru naturalnego, centralną koncepcją doboru GA jest dopasowanie. Bardziej dopasowane chromosomy mają większą szansę na przeżycie. Sprawność to funkcja mierząca jakość rozwiązania reprezentowanego przez chromosom. Zasadniczo każdy chromosom w populacji reprezentuje parametry wejściowe. Na przykład, jeśli twój problem zawiera dwa parametry wejściowe, takie jak cena i wolumen w handlu, każdy chromosom będzie logicznie składał się z dwóch elementów. To, jak elementy są zakodowane w chromosomie, to inny temat.

Podczas selekcji chromosomy tworzą pary rodziców do rozmnażania . Każde dziecko czerpie cechy charakterystyczne od swoich rodziców. Zasadniczo dziecko reprezentuje rekombinację cech swoich rodziców: niektóre cechy pochodzą od jednego rodzica, a niektóre od drugiego. Oprócz rekombinacji niektóre cechy mogą ulec mutacji .

Ponieważ lepiej dopasowane chromosomy produkują więcej dzieci, każde kolejne pokolenie będzie lepiej przystosowane. W pewnym momencie pokolenie będzie zawierało chromosom, który będzie stanowił wystarczająco dobre rozwiązanie naszego problemu.

GA jest potężnym i szeroko stosowanym do złożonych problemów. Istnieje duża klasa problemów optymalizacyjnych, które są dość trudne do rozwiązania za pomocą konwencjonalnych technik optymalizacji. Algorytmy genetyczne to wydajne algorytmy, których rozwiązanie jest w przybliżeniu optymalne. Dobrze znane aplikacje obejmują planowanie, transport, routing, technologie grupowe, projektowanie układów, szkolenia sieci neuronowych i wiele innych.

Wprowadzanie rzeczy w praktykę

Przykład, na który się przyjrzymy, można uznać za „Hello World” AH. Ten przykład został początkowo podany przez J. Freemana w Simulating Networks with Mathematica . Wziąłem go z Genetic Algorithms and Engineering Design Mitsuo Gen i Runwei Cheng.

Problem dopasowania słów próbuje wyewoluować wyrażenie za pomocą algorytmu genetycznego. Początkowo algorytm ma „odgadywać” frazę „być albo nie być” z losowo generowanych list liter.

Ponieważ istnieje 26 możliwych liter dla każdej z 13 lokalizacji [z wyłączeniem spacji] na liście, prawdopodobieństwo, że otrzymamy poprawną frazę w czysto losowy sposób wynosi (1/26)^13=4.03038×10-19, czyli około dwie szanse na [kwintylion] (Gen & Chong, 1997).

Zdefiniujemy tutaj problem nieco szerzej, co jeszcze bardziej utrudni rozwiązanie. Załóżmy, że nie ograniczamy się do języka angielskiego czy konkretnej frazy. Możemy mieć do czynienia z dowolnym alfabetem, a nawet dowolnym zestawem symboli. Nie znamy języka. Nie wiemy nawet, czy w ogóle istnieje jakiś język.

Powiedzmy, że nasz przeciwnik wymyślił dowolną frazę, w tym spacje. Znamy długość frazy i liczbę symboli w alfabecie. To jedyna wiedza, jaką posiadamy. Po każdym odgadnięciu nasz przeciwnik mówi nam, ile liter jest na swoim miejscu.

Każdy chromosom jest sekwencją indeksów symboli w alfabecie. Jeśli mówimy o alfabecie angielskim, to „a” będzie reprezentowane przez 0, „b” przez 1, „c” przez 2 i tak dalej. Na przykład słowo „być” będzie reprezentowane jako [4, 1] .

Zademonstrujemy wszystkie kroki za pomocą fragmentów kodu Java, ale znajomość języka Java nie jest wymagana do zrozumienia każdego kroku.

Rdzeń algorytmu genetycznego

Możemy zacząć od ogólnej implementacji algorytmu genetycznego:

 public void find() { // Initialization List<T> population = Stream.generate(supplier) .limit(populationSize) .collect(toList()); // Iteration while (!termination.test(population)) { // Selection population = selection(population); // Crossover crossover(population); // Mutation mutation(population); } }

Jest to prosty zestaw kroków, z których składa się mniej więcej każde GA. Na etapie inicjalizacji generujemy początkową populację fraz. Wielkość populacji jest określana przez populationSize . Sposób generowania frazy zależy od wdrożenia supplier .

W kroku iteracji ewoluujemy populację, aż zostaną spełnione warunki zakończenia w teście pętli while . Warunki zakończenia mogą obejmować zarówno liczbę pokoleń, jak i dokładne dopasowanie jednej z fraz w populacji. termination zawiera dokładną implementację.

W ramach każdej iteracji wykonujemy typowe kroki GA:

1. Dokonaj selekcji w populacji na podstawie dopasowania chromosomów.
2. Wyprodukuj nową „generację” dzięki operacji crossover.
3. Wykonaj rekombinację niektórych liter w niektórych frazach.

Rdzeń algorytmu jest bardzo prosty i niezależny od domeny. Tak samo będzie ze wszystkimi problemami. To, co trzeba będzie dostroić, to wdrożenie operatorów genetycznych. Następnie przyjrzymy się bliżej każdemu z wymienionych wcześniej operatorów GA.

Wybór

Jak już wiemy, selekcja to proces znajdowania następców obecnych chromosomów — chromosomów, które lepiej pasują do naszego problemu. Podczas selekcji musimy zadbać o to, aby chromosomy o lepszym dopasowaniu miały większą szansę na przeżycie.

 private List<T> selection(List<T> population) { final double[] fitnesses = population.stream() .mapToDouble(fitness) .toArray(); final double totalFitness = DoubleStream.of(fitnesses).sum(); double sum = 0; final double[] probabilities = new double[fitnesses.length]; for (int i = 0; i < fitnesses.length; i++) { sum += fitnesses[i] / totalFitness; probabilities[i] = sum; } probabilities[probabilities.length - 1] = 1; return range(0, probabilities.length).mapToObj(i -> { int index = binarySearch(probabilities, random()); if (index < 0) { index = -(index + 1); } return population.get(index); }).collect(toList()); }

Idea tej implementacji jest następująca: Populacja jest reprezentowana jako kolejne zakresy na osi liczbowej. Cała populacja wynosi od 0 do 1.

Fragment zakresu, jaki zajmuje chromosom, jest proporcjonalny do jego dopasowania. Powoduje to, że lepiej dopasowany chromosom dostanie większy kawałek. Następnie losowo zerkamy na liczbę od 0 do 1 i znajdujemy zakres, który zawiera tę liczbę. Oczywiście większe zakresy mają większe szanse na wyselekcjonowanie, a zatem lepiej dopasowane chromosomy mają większą szansę na przeżycie.

Ponieważ nie znamy szczegółów funkcji fitness, musimy znormalizować wartości sprawności. Funkcja dopasowania jest reprezentowana przez fitness , które przekształca chromosom w arbitralną podwójną, która reprezentuje dopasowanie chromosomu.

W kodzie znajdujemy wskaźniki dopasowania dla wszystkich chromosomów w populacji, a także znajdujemy dopasowanie całkowite. W pętli for wykonujemy skumulowaną sumę prawdopodobieństw przeskalowanych w dół przez całkowitą sprawność. Matematycznie powinno to spowodować, że końcowa zmienna będzie miała wartość 1. Ze względu na niedokładność zmiennoprzecinkowej nie możemy tego zagwarantować, więc dla pewności ustawiamy ją na 1.

Na koniec, liczbę razy równą liczbie chromosomów wejściowych, generujemy liczbę losową, znajdujemy zakres zawierający liczbę, a następnie wybieramy odpowiedni chromosom. Jak możesz zauważyć, ten sam chromosom może być wybierany wielokrotnie.

Krzyżowanie

Teraz musimy chromosomy „rozmnażać”.

 private void crossover(List<T> population) { final int[] indexes = range(0, population.size()) .filter(i-> random() < crossoverProbability) .toArray(); shuffle(Arrays.asList(indexes)); for (int i = 0; i < indexes.length / 2; i++) { final int index1 = indexes[2 * i]; final int index2 = indexes[2 * i + 1]; final T value1 = population.get(index1); final T value2 = population.get(index2); population.set(index1, crossover.apply(value1, value2)); population.set(index2, crossover.apply(value2, value1)); } }

Z predefiniowanym prawdopodobieństwem crossoverProbability wybieramy rodziców do hodowli. Wybrani rodzice są przetasowani, co pozwala na dowolne kombinacje. Bierzemy pary rodziców i stosujemy operator crossover . Stosujemy operator dwa razy dla każdej pary, ponieważ musimy utrzymać tę samą wielkość populacji. Dzieci zastępują w populacji swoich rodziców.

Mutacja

Na koniec wykonujemy rekombinację cech.

 private void mutation(List<T> population) { for (int i = 0; i < population.size(); i++) { if (random() < mutationProbability) { population.set(i, mutation.apply(population.get(i))); } } }

Z predefiniowanym prawdopodobieństwem mutationProbability wykonujemy „mutację” na chromosomach. Sama mutacja jest definiowana przez mutation .

Konfiguracja algorytmu specyficznego dla problemu

Przyjrzyjmy się teraz, jakiego typu parametry specyficzne dla problemu musimy dostarczyć do naszej ogólnej implementacji.

 private BiFunction<T, T, T> crossover; private double crossoverProbability; private ToDoubleFunction<T> fitness; private Function<T, T> mutation; private double mutationProbability; private int populationSize = 100; private Supplier<T> supplier; private Predicate<Collection<T>> termination;

Parametry, odpowiednio, to:

1. Operator zwrotnicy
2. Prawdopodobieństwo krzyżowania
3. Sprawność fizyczna
4. Operator mutacji
5. Prawdopodobieństwo mutacji
6. Wielkość populacji
7. Dostawca chromosomów dla populacji początkowej
8. Funkcja zakończenia

Oto konfiguracja naszego problemu:

 new GeneticAlgorithm<char[]>() .setCrossover(this::crossover) .setCrossoverProbability(0.25) .setFitness(this::fitness) .setMutation(this::mutation) .setMutationProbability(0.05) .setPopulationSize(100) .setSupplier(() -> supplier(expected.length)) .setTermination(this::termination) .find()

Operator zwrotnicy i prawdopodobieństwo

 private char[] crossover(char[] value1, char[] value2) { final int i = (int) round(random() * value1.length); final char[] result = new char(value1.length); System.arraycopy(value1, 0, result, 0, i); System.arraycopy(value2, i, result, i, value2.length - i); return result; }

Prawdopodobieństwo skrzyżowania wynosi 0,25, więc spodziewamy się, że średnio 25 procent chromosomów zostanie wybranych do skrzyżowania. Wykonujemy prostą procedurę krzyżowania pary chromosomów. Generujemy losową liczbę n z zakresu [0..length] , gdzie length jest długością chromosomu. Teraz łączymy wybraną parę, pobierając pierwsze n znaków z jednego chromosomu i pozostałe znaki z drugiego chromosomu.

Sprawność fizyczna

 private double fitness(char[] value) { return range(0, value.length) .filter(i -> value[i] == expected[i]) .count(); }

Funkcja dopasowania po prostu zlicza liczbę dopasowań między frazą docelową a danym chromosomem.

Operator mutacji i prawdopodobieństwo

 private char[] mutation(char[] value) { final char[] result = Arrays.copyOf(value, value.length); for (int i = 0; i < 2; i++) { int letter = (int) round(random() * (ALPHABET.length - 1)); int location = (int) round(random() * (value.length - 1)); result[location] = ALPHABET[letter]; } return result; }

Operacja mutacji jest wykonywana niezależnie na każdym chromosomie. Prawdopodobieństwo mutacji wynosi 0,05, więc spodziewamy się, że średnio pięć procent populacji zostanie zmutowanych. Mutujemy, wybierając losową pozycję litery i zamieniając jej wartość na losową literę z alfabetu. Robimy to dwukrotnie dla każdego zmutowanego chromosomu.

Dostawca

 private char[] supplier(int length) { final char[] result = new char(length); for (int i = 0; i < length; i++) { int letter = (int) round(random() * (ALPHABET.length - 1)); result[i] = ALPHABET[letter]; } return result; }

Dostawca generuje losowe frazy, pobierając losowe litery z alfabetu. Każda fraza ma stałą predefiniowaną długość.

Funkcja zakończenia

 private boolean termination(Collection<char[]> chars) { count++; final Optional<char[]> result = chars.stream() .filter(value -> round(fitness(value)) == expected.length) .findAny(); if (result.isPresent()) { System.out.println("Count: " + count); System.out.println(result.get()); return true; } final boolean terminated = count == 3000; if (terminated) { chars.forEach(System.out::println); } return terminated; }

Funkcja kończąca zlicza liczbę wywołań i zwraca true , jeśli istnieje dokładne dopasowanie lub jeśli liczba generacji osiągnie 3000.

Wykonanie

Teraz jesteśmy gotowi do przetestowania naszego algorytmu. Jeśli uruchomisz go kilka razy, zauważysz, że nie wszystkie przebiegi są udane. Za każdym razem liczba iteracji będzie inna. Wynika to z probabilistycznej natury algorytmu. Algorytm ma kilka punktów, w których można go poprawić. Możesz grać z prawdopodobieństwami crossover i mutacji.

Obniżenie liczby doprowadzi do stabilnego, ale powolnego rozwiązania. Operatorzy genetyczni będą wpływać na mniejszą liczbę chromosomów, a zatem rozwiązanie będzie wymagało większej liczby iteracji.

Zwiększenie liczb przyspieszy działanie algorytmu, ale też sprawi, że rozwiązanie będzie niestabilne. Dopasowane chromosomy zostaną nie tylko zachowane, ale także będą miały wpływ operatory genetyczne. Dlatego stracą swoje „dobre” geny.

Ważne jest, aby znaleźć odpowiednią równowagę. Zwiększenie liczby iteracji da algorytmowi większe możliwości znalezienia rozwiązania, ale z drugiej strony zajmie więcej czasu. Możesz także zastosować różne metody krzyżowania i mutacji. Dobry wybór tych operatorów drastycznie poprawi jakość rozwiązania.

Co następne?

Omówiliśmy tutaj tylko wierzchołek góry lodowej. Wzięliśmy przykład, który ma tylko jeden sygnał wejściowy, który można łatwo przedstawić jako chromosom. Operatory genetyczne są jasne i proste.

Bardzo interesujące jest wziąć rzeczywisty problem i zastosować do niego algorytm genetyczny. Poznasz różne podejścia do kodowania rzeczywistych danych wejściowych, a także różne implementacje krzyżowania i mutacji.

Jeśli problem można wyrazić za pomocą zestawu parametrów, które musimy odgadnąć, aby zoptymalizować metrykę, możemy szybko skonfigurować GA, którego możemy użyć do jego rozwiązania.

Jednym z najciekawszych problemów jest uczenie sztucznych sieci neuronowych. Możemy ustawić parametry, które można zoptymalizować, jako siły synaps, a metrykę sprawności jako procent wejść, dla których nasza sieć neuronowa dała właściwą odpowiedź. Następnie możemy usiąść wygodnie i pozwolić naszej sieci neuronowej ewoluować w idealne rozwiązanie, którego pragniemy. A przynajmniej dopóki nie otrzymamy czegoś wystarczająco dobrego, ponieważ ewolucja wymaga czasu.