What Are Genetic Algorithms?

Over the last few years, there has been a terrific buzz around Artificial Intelligence (AI). Główne firmy, takie jak Google, Apple i Microsoft aktywnie pracują nad tym tematem. W rzeczywistości, AI jest parasolem, 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 jest metaheurystyczną techniką wyszukiwania i optymalizacji opartą na zasadach obecnych w naturalnej ewolucji. Należy do większej klasy algorytmów ewolucyjnych.

GA utrzymuje populację chromosomów – zbiór potencjalnych rozwiązań dla problemu. Idea jest taka, że “ewolucja” znajdzie optymalne rozwiązanie problemu po pewnej liczbie kolejnych pokoleń – podobnie jak w przypadku selekcji naturalnej.

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

Podobnie jak w przypadku selekcji naturalnej, centralnym pojęciem selekcji GA jest kondycja. Chromosomy, które są bardziej sprawne, mają większe szanse na przetrwanie. Fitness jest funkcją, która mierzy jakość rozwiązania reprezentowanego przez chromosom. W istocie, 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. Jak elementy są zakodowane w chromosomie to inny temat.

Podczas selekcji, chromosomy tworzą pary rodziców do hodowli. Każde dziecko bierze cechy od swoich rodziców. Zasadniczo, dziecko reprezentuje rekombinację cech od swoich rodziców: Część cech jest pobierana od jednego rodzica, a część od drugiego. Oprócz rekombinacji, niektóre z cech mogą mutować.

Ponieważ sprawne chromosomy produkują więcej dzieci, każde kolejne pokolenie będzie miało lepszą sprawność. W pewnym momencie pokolenie będzie zawierało chromosom, który będzie reprezentował wystarczająco dobre rozwiązanie dla naszego problemu.

GA jest potężna i ma szerokie zastosowanie dla złożonych problemów. Istnieje duża klasa problemów optymalizacyjnych, które są dość trudne do rozwiązania za pomocą konwencjonalnych technik optymalizacyjnych. Algorytmy genetyczne są efektywnymi algorytmami, których rozwiązanie jest w przybliżeniu optymalne. Znane zastosowania obejmują planowanie, transport, routing, technologie grupowe, projektowanie układów, trening sieci neuronowych i wiele innych.

Putting Things into Practice

Przykład, któremu się przyjrzymy, można uznać za “Hello World” GA. Przykład ten został pierwotnie podany przez J. Freemana w Simulating Neural Networks with Mathematica. Ja zaczerpnąłem go z Genetic Algorithms and Engineering Design autorstwa Mitsuo Gen i Runwei Cheng.

The Word-Matching Problem próbuje ewoluować wyrażenie za pomocą algorytmu genetycznego. Początkowo algorytm ma “odgadnąć” wyrażenie “to be or not to be” z losowo wygenerowanych list liter.

Ponieważ istnieje 26 możliwych liter dla każdego z 13 miejsc na liście, prawdopodobieństwo, że otrzymamy poprawne wyrażenie w czysto losowy sposób wynosi (1/26)^13=4.03038×10-19, czyli mniej więcej dwie szanse na (Gen & Chong, 1997).

Zdefiniujemy tu problem nieco szerzej, dzięki czemu rozwiązanie będzie jeszcze trudniejsze. Załóżmy, że nie jesteśmy ograniczeni do języka angielskiego czy konkretnej frazy. Możemy w końcu mieć do czynienia z dowolnym alfabetem, a nawet dowolnym zestawem symboli. Nie mamy żadnej wiedzy o języku. Nie wiemy nawet, czy w ogóle istnieje jakikolwiek język.

Powiedzmy, że nasz przeciwnik wymyślił dowolną frazę, włączając w to spacje. Znamy długość frazy i liczbę symboli w alfabecie. To jest jedyna wiedza, jaką posiadamy. Po każdym odgadnięciu, nasz przeciwnik mówi nam, ile liter jest na 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. Tak więc, na przykład, słowo “be” będzie reprezentowane jako .

Zademonstrujemy wszystkie kroki za pomocą wycinków kodu Java, ale znajomość Javy 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 mniej więcej składa się każdy GA. W kroku inicjalizacji generujemy początkową populację fraz. Wielkość populacji jest określona przez populationSize. Sposób generowania fraz zależy od implementacji supplier.

W kroku iteracji ewoluujemy populację do momentu spełnienia warunków zakończenia w ramach testu pętli while. Warunki zakończenia mogą obejmować zarówno liczbę pokoleń, jak i dokładne dopasowanie jednej z fraz w populacji. The termination encapsulates an exact implementation.

W ramach każdej iteracji wykonujemy typowe kroki GA:

1. Przeprowadź selekcję nad populacją w oparciu o fitness chromosomów.
2. Wytworzenie nowego “pokolenia” poprzez operację crossover.
3. Wykonanie rekombinacji niektórych liter w niektórych frazach.

Rdzeń algorytmu jest bardzo prosty i domenowo niezależny. Będzie on taki sam dla wszystkich problemów. To, co trzeba będzie dostroić, to implementacja operatorów genetycznych. Następnie przyjrzymy się każdemu z wcześniej wymienionych operatorów GA.

Selekcja

Jak już wiemy, selekcja jest procesem znajdowania następców bieżących chromosomów – chromosomów, które są bardziej odpowiednie dla naszego problemu. Podczas selekcji musimy zapewnić, że chromosomy o lepszej kondycji mają większą szansę na przetrwanie.

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; for (int i = 0; i < fitnesses.length; i++) { sum += fitnesses / totalFitness; probabilities = sum; } probabilities = 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());}

Pomysł stojący za tą implementacją jest następujący: Populacja jest reprezentowana jako zsekwencjonowane zakresy na osi liczbowej. Cała populacja mieści się w przedziale od 0 do 1.

Część przedziału, jaką zajmuje chromosom, jest proporcjonalna do jego kondycji. Powoduje to, że chromosom o lepszej kondycji dostaje większy kawałek. Następnie losowo zerkamy na liczbę pomiędzy 0 a 1 i znajdujemy zakres, który zawiera tę liczbę. Oczywiście, większe zakresy mają większe szanse na wybór, a zatem sprawniejsze chromosomy mają większe szanse na przetrwanie.

Ponieważ nie znamy szczegółów dotyczących funkcji fitness, musimy znormalizować wartości fitness. Funkcja fitness jest reprezentowana przez fitness, który przekształca chromosom w arbitralną liczbę podwójną, która reprezentuje fitness chromosomu.

W kodzie znajdujemy współczynniki fitness dla wszystkich chromosomów w populacji, a także znajdujemy fitness całkowity. W pętli for wykonujemy sumę kumulatywną nad prawdopodobieństwami skalowanymi w dół przez całkowitą sprawność. Z matematycznego punktu widzenia zmienna końcowa powinna mieć wartość 1. Z powodu nieprecyzyjności zmiennoprzecinkowej nie możemy tego zagwarantować, więc dla pewności ustawiamy ją na 1.

Na koniec, dla liczby razy równej liczbie chromosomów wejściowych, generujemy liczbę losową, znajdujemy zakres zawierający tę liczbę, a następnie wybieramy odpowiadający jej chromosom. Jak można zauważyć, ten sam chromosom może być wybrany wiele razy.

Krzyżowanie

Teraz musimy chromosomy “rozmnożyć”

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; final int index2 = indexes; 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 rozmnażania. Wybrani rodzice są tasowani, co pozwala na dowolne kombinacje. Bierzemy pary rodziców i stosujemy operator crossover. Stosujemy ten operator dwukrotnie dla każdej pary, ponieważ musimy utrzymać wielkość populacji na tym samym poziomie. Dzieci zastępują swoich rodziców w populacji.

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 zdefiniowana przez mutation.

Konfiguracja algorytmu specyficznego dla problemu

Przyjrzyjrzyjmy się teraz, jakiego typu parametry specyficzne dla problemu musimy przekazać naszej generycznej 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 te, odpowiednio, to:

1. Operator krzyżowania
2. Prawdopodobieństwo krzyżowania
3. Funkcja dopasowania
4. Operator mutacji
5. Prawdopodobieństwo mutacji
6. Rozmiar populacji
7. Dostawca chromosomów dla populacji początkowej
8. Funkcja terminacji

Oto konfiguracja dla 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 krzyżowania 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 krzyżowania wynosi 0.25, więc spodziewamy się, że średnio 25 procent chromosomów zostanie wybranych do krzyżowania. Wykonujemy prostą procedurę krzyżowania pary chromosomów. Generujemy liczbę losową n z przedziału , gdzie length jest długością chromosomu. Teraz kojarzymy wybraną parę, pobierając pierwsze n znaki z jednego chromosomu i pozostałe po nich z drugiego.

Funkcja fitness

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

Funkcja fitness po prostu liczy 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 = ALPHABET; } 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 zmutowane. Mutacja polega na wybraniu losowej pozycji literowej i zastąpieniu jej wartości losową literą z alfabetu. Robimy to dwa razy 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 = ALPHABET; } return result;}

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

Funkcja kończąca

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 jest albo dokładne dopasowanie, albo 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 uruchomienia kończą się sukcesem. 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 ulepszyć. Możesz grać z prawdopodobieństwami krzyżowania i mutacji.

Zmniejszenie liczby doprowadzi do stabilnego, ale powolnego rozwiązania. Mniejsza liczba chromosomów będzie poddana działaniu operatorów genetycznych, a co za tym idzie, do rozwiązania będzie potrzeba więcej iteracji.

Zwiększanie liczby przyspieszy działanie algorytmu, ale sprawi, że rozwiązanie będzie niestabilne. Dopasowane chromosomy będą nie tylko zachowane, ale również będą pod wpływem działania operatorów genetycznych. Dlatego stracą one swoje “dobre” geny.

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

Objęliśmy tu tylko wierzchołek góry lodowej. Wzięliśmy przykład, który ma tylko jedno wejście, a wejście może być łatwo przedstawione jako chromosom. Operatory genetyczne są zwykłe i proste.

Bardzo interesujące jest wzięcie rzeczywistego problemu i zastosowanie do niego algorytmu genetycznego. Odkryjesz różne podejścia w kodowaniu rzeczywistych danych wejściowych, jak również różne implementacje krzyżowania i mutacji.

Jeśli problem można wyrazić poprzez zestaw parametrów, które musimy odgadnąć, aby zoptymalizować metrykę, możemy szybko skonfigurować GA, który możemy wykorzystać do jego rozwiązania.

Jednym z najbardziej interesujących problemów jest uczenie sztucznych sieci neuronowych. Możemy ustawić optymalizowalne parametry jako siłę synaps, a metrykę kondycji jako procent danych wejściowych, 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 kierunku idealnego rozwiązania, którego pragniemy. Albo przynajmniej dopóki nie uzyskamy czegoś wystarczająco dobrego, ponieważ ewolucja wymaga czasu.