Quantum Computing Simulation

Wyszukiwanie w oparciu o ewolucję

Algorytm genetyczny traktuje potencjalne rozwiązania problemu jako jednostki w populacji i ulepsza tę populację generacją po generacji, wykorzystując trzy składniki napędzające ewolucję biologiczną: selekcję (lepsze rozwiązania są bardziej prawdopodobne do rozmnażania), przerywanie (potomstwo łączy cechy z dwóch rodziców) i mutację (małe losowe zmiany wprowadzają wariację, której selekcja sama nie mogłaby wygenerować). Każda jednostka jest oceniana przez funkcję przystosowania specyficzną dla problemu – podobieństwo ciągów do celu lub funkcję matematyczną minimalizującą wartość – i nic w algorytmie nie wymaga pochodnej ani różniczkowalnego obiektu, co dokładnie wyjaśnia, dlaczego algorytmy genetyczne są wykorzystywane na problemach, gdzie metody oparte na gradientach nie mają czego się chwytać.

Weasel: najprostsza demonstracja

Program "Weasel" Richarda Dawksona z 1986 roku, będący najprostszą ilustracją, ewoluuje losowy ciąg znaków w kierunku ustalonego celu (jego przykład: METHINKS IT IS LIKE A WEASEL) wyłącznie poprzez mutacje i selekcję najodpowiedniejszego ciągu w każdym pokoleniu, bez krzyżowego przemieszczenia. Celem nie było modelowanie biologii w sposób dokładny – celuje w znaną, ustaloną frazę, czego realna ewolucja nigdy nie robi – ale aby jasno pokazać, jak kumulatywna selekcja małych, losowych zmian konwerguje znacznie szybciej niż przypadkiem. Prawdziwie losowy ciąg 28 znaków pasujący do celu bit po bicie ma prawdopodobieństwo rzędu (1/27)² – astronomicznie niskie, aby wystąpił jednym szczęśliwym uderzeniem – a "Weasel" zwykle konwerguje w ciągu kilkudziesięciu pokoleń, ponieważ każde kolejne pokolenie utrzymuje poprawę, jaką wywołała mutacja, zamiast zaczynać od zera.

Rastrigin: krajobraz optymalizacyjny z wieloma pułapkami

Drugi tryb tej strony optymalizuje funkcję Rastrigina 2D, standardowy benchmark w badaniach nad optymalizacją, ponieważ jest trudna w sposób specyficzny i dobrze zrozumiany:

f(x, y) = 20 + x^2 + y^2 - 10*cos(2*pi*x) - 10*cos(2*pi*y) // globalny minimum: f(0, 0) = 0 // ale pełna regularnie rozmieszczonych lokalnych minimów w pobliżu Wyraz kwadratowy x^2 + y^2 tworzy jedną gładką globalną miskę uśrodka początku układu współrzędnych, a wyrażenia cosinusowe tworzą regularą kratę lokalnych minimów w tej misce – krajobraz, który prosty algorytm hill-climbing utknął w nim niemal natychmiast, ponieważ poruszanie się w kierunku najbliższego spadku prowadzi zazwyczaj do niewłaściwego lokalnego dołka zamiast prawdziwego minimum u początku. Populacyjna metoda wyszukiwania algorytmu genetycznego, wraz z możliwością mutacji, aby wykonać skok większy niż jeden lokalny basen, jest właśnie tym, na czym są zaprojektowane takie krajobrazy, aby testować.

f(x, y) = 20 + x^2 + y^2 - 10*cos(2*pi*x) - 10*cos(2*pi*y)
// global minimum: f(0, 0) = 0
// but riddled with regularly-spaced local minima nearby

Selekcja, przemieszczenie, mutacja – trzy operatorzy

W metodzie selekcji turniejowej wybierane są losowo k osobników z populacji i najsilniejsi spośród tej małej grupy stają się rodzicami; jest to preferowane w stosunku do zawsze wyboru pojedynczego najlepszego osobnika, ponieważ pozwala na kontrolowanie presji selekcji (większe k powoduje silniejsze dążenie do obecnego najlepszego, mniejsze k zachowuje większą różnorodność) bez potrzeby oceniania całej populacji.

Przemieszczenie łączy genomy dwóch rodziców – w przypadku ciągu Weasel punkt cięcia dzieli każdego rodzica i wymienia ogony; dla Rastrigina współrzędne (x, y) mogą być połączone lub uśrednione. Mutacja następnie lekko zaburza potomstwo niezależnie od rodziców – niska, ale niezerowa mutacja zapewnia, że populacja nie ulegnie wczesnemu zawaleniu się na jeden lokalny optimum i utraci zdolność do eksploracji.

Pętla dla każdej generacji: oceniaj fitness(osobnik) dla każdego osobnika nowa_populacja = [] dopóki nowa_populacja nie jest pełna: parent1 = selekcja_turniejowa(populacja) parent2 = selekcja_turniejowa(populacja) dziecko = przemieszczenie(parent1, parent2) dziecko = mutacja(dziecko, stopa) nowa_populacja.push(dziecko) populacja = nowa_populacja

Nie ma gwarancji znalezienia globalnego optimum – algorytmy genetyczne są heurystykami, a nie dokładnymi solverami – ale na krajobrazach szumów, dyskontynuacji, braku różniczkowalności lub po prostu niezdefiniowanych w postaci zamkniętego wzoru, populacja eksplorująca szeroko i wykorzystująca lokalnie zbieżność zwykle przewyższa zarówno losowy przeszukiwanie, jak i metodę gradientową, która albo bezcelowo wędruje, albo utknęła w pierwszym lokalnym minimum, jakie napotkała.

loop each generation:
  evaluate fitness(individual) for every individual
  new_population = []
  while new_population not full:
    parent1 = tournament_select(population)
    parent2 = tournament_select(population)
    child   = crossover(parent1, parent2)
    child   = mutate(child, rate)
    new_population.push(child)
  population = new_population

Często zadawane pytania

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz Genetic Algorithm i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.