Jakie są dobre przykłady algorytmów genetycznych / rozwiązań programowania genetycznego? [Zamknięte]

Algorytmy genetyczne (GA) i programowanie genetyczne (GP) to interesujące obszary badań.

Chciałbym wiedzieć o konkretnych problemach, które rozwiązałeś za pomocą GA / GP i jakich bibliotek / frameworków użyłeś, jeśli nie stworzyłeś własnych.

Pytania:

• Jakie problemy wykorzystałeś do rozwiązania GA / GP?
• Z jakich bibliotek / frameworków korzystałeś?

Szukam doświadczeń z pierwszej ręki, więc proszę nie odpowiadać, chyba że masz to.

Nie praca domowa.

Moja pierwsza praca jako profesjonalnego programisty (1995) polegała na napisaniu zautomatyzowanego systemu transakcyjnego opartego na algorytmie genetycznym dla kontraktów terminowych S & P500. Aplikacja została napisana w języku Visual Basic 3 [!] I nie mam pojęcia, jak wtedy coś zrobiłem, ponieważ VB3 nawet nie miał klas.

Aplikacja rozpoczęła się od populacji losowo generowanych ciągów o stałej długości (część „genowa”), z których każda odpowiadała konkretnemu kształtowi w danych cenowych kontraktów terminowych S & P500 z minuty na minutę, a także określonym zamówieniu (kup lub sprzedaj) oraz kwoty stop-loss i stop-profit. Każdy ciąg (lub „gen”) został poddany ocenie wyników finansowych na podstawie 3-letnich danych historycznych; ilekroć określony „kształt” pasował do danych historycznych, przyjmowałem odpowiednie zamówienie kupna lub sprzedaży i oceniałem wynik transakcji. Dodałem zastrzeżenie, że każdy gen zaczynał od ustalonej kwoty pieniędzy i dlatego mógł potencjalnie ulec awarii i zostać całkowicie usunięty z puli genów.

Po każdej ocenie populacji osoby, które przeżyły, krzyżowano losowo (po prostu mieszając kawałki od dwojga rodziców), przy czym prawdopodobieństwo wyboru genu jako rodzica było proporcjonalne do wygenerowanego zysku. Dodałem także możliwość mutacji punktowych, aby trochę urozmaicić. Po kilkuset pokoleniach skończyłem z populacją genów, które mogłyby zmienić 5000 $ w średnio około 10000 $ bez szansy na śmierć / złamanie (oczywiście na podstawie danych historycznych).

Niestety, nigdy nie miałem okazji korzystać z tego systemu na żywo, ponieważ mój szef stracił prawie 100 000 $ w mniej niż 3 miesiące, handlując w tradycyjny sposób, a on stracił chęć kontynuowania projektu. Patrząc wstecz, myślę, że system przyniósłby ogromne zyski - nie dlatego, że koniecznie robiłem coś dobrze, ale dlatego, że populacja genów, które wytworzyłem, była tendencyjna w stosunku do zamówień kupna (w przeciwieństwie do zamówień sprzedaży) o około 5: 1 stosunek. Jak wiemy z perspektywy 20/20, rynek wzrósł nieco po 1995 roku.

Stworzyłem małe stworzenia, które żyły w tym małym świecie. Mieli mózg sieci neuronowej, który otrzymał pewne informacje ze świata, a dane wyjściowe były wektorem do przemieszczania się między innymi działaniami. Ich mózgi były „genami”.

Program rozpoczął się od losowej populacji zwierząt z przypadkowymi mózgami. Neurony wejściowe i wyjściowe były statyczne, ale między nimi nie było.

Środowisko zawierało żywność i niebezpieczeństwa. Jedzenie zwiększa energię, a gdy masz dość energii, możesz kopulować. Niebezpieczeństwa zmniejszyłyby energię, a gdyby energia wynosiła 0, zginęli.

W końcu stworzenia ewoluowały, aby poruszać się po świecie i znajdować żywność oraz unikać niebezpieczeństw.

Potem postanowiłem zrobić mały eksperyment. Dałem mózgowi istoty neuron wyjściowy o nazwie „usta” i neuron wejściowy o nazwie „ucho”. Zaczynałem od nowa i zdziwiłem się, gdy ewoluowali, aby zmaksymalizować przestrzeń, a każde stworzenie pozostawało w odpowiedniej części (jedzenie było umieszczane losowo). Nauczyli się współpracować ze sobą i nie wchodzić sobie w drogę. Zawsze były wyjątki.

Potem spróbowałem czegoś interesującego. Martwe stworzenia stałyby się pożywieniem. Spróbuj zgadnąć, co się stało! Wyewoluowały dwa rodzaje stworzeń, te, które atakowały jak roje i te, które były wysoce unikane.

Więc jaka jest lekcja tutaj? Komunikacja oznacza współpracę. Gdy tylko wprowadzisz element, w którym zranienie innego oznacza, że ​​coś zyskujesz, współpraca zostaje zniszczona.

Zastanawiam się, jak to odbija się na systemie wolnych rynków i kapitalizmu. Chodzi mi o to, że jeśli firmy mogą zranić swoją konkurencję i uciec jej , to jasne, że zrobią wszystko, co w ich mocy, aby zaszkodzić konkurencji.

Edytować:

Napisałem to w C ++ bez użycia frameworków. Napisałem własną sieć neuronową i kod GA. Eric, dziękuję, że powiedziałeś, że to prawdopodobne. Ludzie zwykle nie wierzą w moce GA (chociaż ograniczenia są oczywiste), dopóki się z nimi nie bawią. GA jest proste, ale nie uproszczone.

W przypadku wątpiących udowodniono, że sieci neuronowe są w stanie symulować dowolną funkcję, jeśli mają więcej niż jedną warstwę. GA jest dość prostym sposobem poruszania się po przestrzeni rozwiązań, znajdując lokalne i potencjalnie globalne minimum. Połącz GA z sieciami neuronowymi i masz całkiem dobry sposób na znalezienie funkcji, które znajdą przybliżone rozwiązania ogólnych problemów. Ponieważ używamy sieci neuronowych, optymalizujemy funkcję dla niektórych danych wejściowych, a nie niektórych danych wejściowych do funkcji, ponieważ inni używają GA

Oto kod demonstracyjny dla przykładu przetrwania: http://www.mempko.com/darcs/neural/demos/eaters/ Instrukcje budowania:

• Zainstaluj darcs, libboost, liballegro, gcc, cmake, make
• darcs clone --lazy http://www.mempko.com/darcs/neural/
• cd neural
• cmake .
• make
• cd demos/eaters
• ./eaters

W styczniu 2004 r. Skontaktował się ze mną Philips New Display Technologies, który tworzył elektronikę dla pierwszego komercyjnego e-atramentu, Sony Librie, który został wydany tylko w Japonii, na wiele lat przed Amazon Kindle i innymi, które trafiły na rynek w USA Europa.

Inżynierowie Philips mieli poważny problem. Kilka miesięcy przed tym, jak produkt miał wejść na rynek, ciągle zmieniały się strony na ekranie podczas zmiany stron. Problem polegał na tym, że 200 sterowników wytwarzało pole elektrostatyczne. Każdy z tych sterowników miał określone napięcie, które musiało być ustawione dokładnie od zera do 1000 mV lub coś takiego. Ale jeśli zmienisz jeden z nich, zmieni wszystko.

Zatem optymalizacja napięcia każdego sterownika osobno nie wchodziła w rachubę. Liczba możliwych kombinacji wartości była wyrażona w miliardach, a specjalna kamera zajęła około 1 minuty na ocenę pojedynczej kombinacji. Inżynierowie wypróbowali wiele standardowych technik optymalizacji, ale nic by się nie zbliżyło.

Główny inżynier skontaktował się ze mną, ponieważ wcześniej wydałem bibliotekę programowania genetycznego społeczności open source. Zapytał, czy lekarze pierwszego kontaktu / lekarze pomogą i czy mógłbym się zaangażować. Zrobiłem to i przez około miesiąc pracowaliśmy razem, pisząc i dostrajając bibliotekę GA, w sprawie danych syntetycznych, a on integruje ją z ich systemem. Pewnego weekendu pozwolili, by działało na żywo z prawdziwymi rzeczami.

W następny poniedziałek otrzymałem te świecące e-maile od niego i od ich projektanta sprzętu, o tym, jak nikt nie mógł uwierzyć w niesamowite wyniki, które znalazła GA. To było to. Później tego samego roku produkt trafił na rynek.

Nie dostałem za to ani centa, ale dostałem prawa do przechwalania się. Od początku mówili, że przekroczyli już budżet, więc zanim zacząłem nad tym pracować, wiedziałem, na czym polega umowa. To świetna historia dla aplikacji GA. :)

Użyłem GA do optymalizacji miejsc siedzących na moim przyjęciu weselnym. 80 gości na 10 stołach. Funkcja oceny polegała na utrzymywaniu ludzi z ich datami, łączeniu ludzi z czymś wspólnym i trzymaniu ludzi o skrajnie odmiennych poglądach przy osobnych stołach.

Uruchomiłem to kilka razy. Za każdym razem mam dziewięć dobrych stołów i jeden ze wszystkimi dziwnymi piłkami. W końcu moja żona zajęła się miejscami siedzącymi.

Mój podróżny optymalizator sprzedający zastosował nowatorskie mapowanie chromosomu na trasę, co sprawiło, że rozmnażanie i mutowanie chromosomów było banalne bez żadnego ryzyka generowania nieprawidłowych tras.

Aktualizacja : Ponieważ kilka osób zapytało, jak ...

Zacznij od szeregu gości (lub miast) w dowolnej, ale spójnej kolejności, np. Alfabetycznie. Nazwij to rozwiązaniem referencyjnym. Pomyśl o indeksie gościa jako o jego numerze miejsca.

Zamiast próbować zakodować tę kolejność bezpośrednio w chromosomie, kodujemy instrukcje dotyczące transformacji rozwiązania referencyjnego w nowe rozwiązanie. W szczególności traktujemy chromosomy jako listy indeksów w tablicy do zamiany. Aby uzyskać dekodowanie chromosomu, zaczynamy od rozwiązania referencyjnego i stosujemy wszystkie wymiany wskazane przez chromosom. Zamiana dwóch wpisów w tablicy zawsze daje prawidłowe rozwiązanie: każdy gość (lub miasto) wciąż pojawia się dokładnie raz.

W ten sposób chromosomy mogą być generowane losowo, mutowane i krzyżowane z innymi i zawsze dają prawidłowe rozwiązanie.

Użyłem algorytmów genetycznych (a także niektórych powiązanych technik), aby określić najlepsze ustawienia dla systemu zarządzania ryzykiem, który próbował powstrzymać hodowców złota przed użyciem skradzionych kart kredytowych do płacenia za MMO. System przeprowadziłby kilka tysięcy transakcji o „znanych” wartościach (oszustwo lub nie) i ustalił, jaka najlepsza kombinacja ustawień polegała na prawidłowej identyfikacji fałszywych transakcji bez zbyt wielu fałszywych wyników pozytywnych.

Mieliśmy dane dotyczące kilkudziesięciu (boolowskich) cech transakcji, z których każda otrzymała wartość i została zsumowana. Jeśli suma była wyższa niż próg, transakcja była oszustwem. GA utworzy dużą liczbę losowych zestawów wartości, oceni je na podstawie zbioru znanych danych, wybierze te, które uzyskały najlepszy wynik (zarówno w zakresie wykrywania oszustw, jak i ograniczenia liczby fałszywych wyników pozytywnych), a następnie krzyżuje najlepsze z z każdego pokolenia na nowe pokolenie kandydatów. Po pewnej liczbie pokoleń najlepszy zestaw punktacji wartości został uznany za zwycięzcę.

Tworzenie korpusu znanych danych do przetestowania było piętą achillesową systemu. Jeśli czekałeś na obciążenia zwrotne, byłeś kilka miesięcy za opóźnieniem, próbując odpowiedzieć na oszustów, więc ktoś musiałby ręcznie przejrzeć dużą liczbę transakcji, aby zgromadzić ten zbiór danych, bez konieczności zbyt długiego oczekiwania.

Skończyło się to identyfikacją zdecydowanej większości oszustw, które miały miejsce, ale nie było w stanie uzyskać poniżej 1% w przypadku najbardziej podatnych na oszustwa pozycji (biorąc pod uwagę, że 90% przychodzących transakcji może być oszustwem, co robiło całkiem dobrze).

Zrobiłem to wszystko za pomocą Perla. Uruchomienie jednego oprogramowania na dość starym urządzeniu z linuksem zajęłoby 1-2 godziny (20 minut na załadowanie danych przez łącze WAN, reszta czasu poświęcana na załamanie). Rozmiar dowolnej generacji był ograniczony dostępną pamięcią RAM. Ciągle go przeglądałem z niewielkimi zmianami parametrów, szukając szczególnie dobrego zestawu wyników.

W sumie uniknęło niektórych gaf, które pojawiły się przy ręcznej próbie poprawienia względnych wartości dziesiątek wskaźników oszustw i konsekwentnie wymyśliło lepsze rozwiązania, niż mogłem stworzyć ręcznie. AFAIK, wciąż jest w użyciu (około 3 lata po napisaniu).

Napiwki piłkarskie. Zbudowałem system GA, aby przewidzieć wyniki meczów w AFL (Aussie Rules Football) z tygodnia na tydzień.

Kilka lat temu znudziłem się standardową pracą w piłce nożnej, wszyscy po prostu wchodzili do Internetu i wybierali oferty z jakiegoś eksperta w prasie. Uznałem więc, że nie może być zbyt trudno pokonać kilka głównych kierunków dziennikarskich, prawda? Moją pierwszą myślą było wzięcie wyników z Oceny Massey, a następnie ujawnienie pod koniec sezonu mojej strategii po zdobyciu sławy i chwały. Jednak z powodów, których nigdy nie odkryłem, Massey nie śledzi AFL. Cynik we mnie wierzy, że tak jest, ponieważ wynik każdej gry AFL stał się w zasadzie losową szansą, ale moje skargi na ostatnie zmiany zasad należą do innego forum.

System zasadniczo rozważał siłę ofensywną, obronną, przewagę na boisku, poprawę z tygodnia na tydzień (lub jej brak) i szybkość zmian w każdym z nich. Stworzyło to zestaw równań wielomianowych dla każdej drużyny w ciągu sezonu. Można obliczyć zwycięzcę i wynik dla każdego meczu w danym dniu. Celem było znalezienie zestawu współczynników, które najbardziej pasowałyby do wyników wszystkich poprzednich gier i wykorzystanie tego zestawu do przewidywania nadchodzących tygodni gry.

W praktyce system znalazłby rozwiązania, które dokładnie przewidziały ponad 90% wyników poprzednich gier. Następnie z powodzeniem wybierze około 60–80% gier na nadchodzący tydzień (czyli tygodnia, którego nie ma w zestawie treningowym).

Wynik: tuż nad środkiem paczki. Żadnej dużej nagrody pieniężnej ani systemu, którego mógłbym użyć do pokonania Vegas. Ale było fajnie.

Zbudowałem wszystko od zera, bez żadnych ram.

Oprócz niektórych typowych problemów, takich jak Traveling Salesman i odmiana programu Mona Lisa Rogera Alsinga , napisałem również ewolucyjny solver Sudoku (który wymagał trochę bardziej oryginalnej myśli z mojej strony, niż tylko ponowne wdrożenie czyjś pomysł). Istnieją bardziej niezawodne algorytmy rozwiązywania Sudokusa, ale podejście ewolucyjne działa dość dobrze.

W ciągu ostatnich kilku dni bawiłem się programem ewolucyjnym, aby znaleźć „zimne talie” do pokera po przeczytaniu tego artykułu na Reddit. W tej chwili nie jest to w pełni satysfakcjonujące, ale myślę, że mogę to poprawić.

Mam własną strukturę , której używam do algorytmów ewolucyjnych.

Opracowałem domowy napar GA dla systemu profili powierzchni lasera 3D, który moja firma opracowała dla przemysłu towarowego w 1992 roku. System polegał na trójwymiarowej triangulacji i używał niestandardowego skanera linii laserowej, aparatu 512x512 (z niestandardowym sprzętem do przechwytywania). Odległość między aparatem a laserem nigdy nie była precyzyjna, a ogniskowej aparatów nie można było znaleźć w pozycji 256 256, której się spodziewałeś!

Koszmarem było próba wypracowania parametrów kalibracji przy użyciu standardowej geometrii i rozwiązywania równań w stylu symulacji wyżarzania.

Algorytm genetyczny został wymyślony wieczorem i stworzyłem kostkę kalibracyjną do przetestowania. Znałem wymiary kostki z dużą dokładnością, dlatego pomysł polegał na tym, że moja GA mogła opracować zestaw niestandardowych parametrów triangulacji dla każdej jednostki skanującej, które przezwyciężyłyby różnice produkcyjne.

Sztuczka zadziałała. Byłem oszołomiony co najmniej! W ciągu około 10 pokoleń moja „wirtualna” kostka (wygenerowana ze skanu surowego i odtworzona z parametrów kalibracyjnych) faktycznie wyglądała jak kostka! Po około 50 pokoleniach miałem kalibrację, której potrzebowałem.

Często trudno jest uzyskać dokładną kombinację kolorów, kiedy planujesz pomalować swój dom. Często masz na myśli jakiś kolor, ale nie jest to jeden z kolorów, który pokazuje ci sprzedawca.

Wczoraj mój profesor, który jest badaczem GA, wspomniał o prawdziwej historii w Niemczech (przepraszam, nie mam dalszych odniesień, tak, mogę ją znaleźć, jeśli ktoś o to poprosi). Ten facet (nazwijmy go facetem od koloru ) chodził od drzwi do drzwi, aby pomóc ludziom znaleźć dokładny kod koloru (w RGB ), który byłby szafą na to, co miał na myśli klient. Oto jak by to zrobił:

Kolor facet wykorzystane do przeprowadzenia z nim program komputerowy, który używany Ga. Zaczął od 4 różnych kolorów - każdy zakodowany jako kodowany chromosom (którego zdekodowana wartość byłaby wartością RGB). Konsument wybiera 1 z 4 kolorów (który jest najbliższy, o którym ma na myśli). Następnie program przypisuje maksymalną sprawność tej osobie i przechodzi do następnego pokolenia za pomocą mutacji / crossover . Powyższe kroki będą powtarzane, dopóki konsument nie znajdzie dokładnego koloru, a następnie facet od koloru powiedział mu kombinację RGB!

Przypisując maksymalną przydatność koloru do tego, co konsument ma na myśli, program kolorowego faceta zwiększa szanse na zbliżenie się do koloru, a konsument dokładnie o tym myśli. Uważam, że to niezła zabawa!

Teraz, gdy mam -1, jeśli planujesz więcej -1, proszę. wyjaśnij powód tego!

Kilka tygodni temu zasugerowałem rozwiązanie dotyczące SO przy użyciu algorytmów genetycznych w celu rozwiązania problemu z układem grafu. Jest to przykład ograniczonego problemu optymalizacji.

Również w obszarze uczenia maszynowego wdrożyłem od podstaw ramę klasyfikacji opartą na GA w c / c ++.
Użyłem GA w przykładowym projekcie do szkolenia sztucznych sieci neuronowych (ANN), w przeciwieństwie do słynnego algorytmu propagacji wstecznej .

Ponadto, w ramach moich badań podyplomowych, wykorzystałem GA w szkoleniu Ukrytych modeli Markowa jako dodatkowe podejście do opartego na EM algorytmu Baum-Welcha (ponownie w c / c ++).

W ramach mojego stopnia licencjata CompSci przydzielono nam problem znalezienia optymalnych flag jvm dla wirtualnej maszyny badawczej Jikes. Zostało to ocenione przy użyciu pakietu testów Dicappo, który zwraca czas do konsoli. Napisałem rozproszony alogirthm, który zamieniał te flagi, aby poprawić czas działania pakietu testów porównawczych, choć zajęło to kilka dni, aby zrekompensować zakłócenia sprzętowe wpływające na wyniki. Jedynym problemem było to, że nie poznałem właściwie teorii kompilatora (co było celem tego zadania).

Mógłbym zaszczepić początkową populację istniejącymi domyślnymi flagami, ale interesujące było to, że algorytm znalazł bardzo podobną konfigurację do poziomu optymalizacji O3 (ale w rzeczywistości był szybszy w wielu testach).

Edycja: Napisałem również własną strukturę algorytmu genetycznego w Pythonie do tego zadania i po prostu użyłem popen poleceń do uruchomienia różnych testów porównawczych, chociaż gdyby nie było to ocenione zadanie, spojrzałbym na pyEvolve.

Po pierwsze, „Programowanie genetyczne” Jonathana Kozy ( amazon ) to właściwie książka o genetycznych i ewolucyjnych algorytmach / technikach programowania, z wieloma przykładami. Gorąco polecam sprawdzenie.

Jeśli chodzi o własne wykorzystanie algorytmu genetycznego, użyłem algorytmu genetycznego (hodowanego w domu), aby rozwinąć algorytm roju w scenariuszu gromadzenia / niszczenia obiektów (praktycznym celem mogłoby być wyczyszczenie pola minowego). Oto link do artykułu . Najbardziej interesującą częścią tego, co zrobiłem, była wieloetapowa funkcja fitness, co było koniecznością, ponieważ proste funkcje fitness nie dostarczyły wystarczających informacji dla algorytmu genetycznego, aby wystarczająco rozróżnić członków populacji.

Należę do zespołu badającego wykorzystanie Evolutionary Computation (EC) do automatycznego usuwania błędów w istniejących programach. Z powodzeniem naprawiliśmy wiele prawdziwych błędów w projektach oprogramowania w świecie rzeczywistym (patrz strona główna tego projektu ).

Mamy dwie zastosowania tej techniki naprawy WE.

• Pierwsza (informacje o kodzie i reprodukcji dostępne na stronie projektu ) ewoluuje abstrakcyjne drzewa składniowe analizowane z istniejących programów C i jest implementowana w Ocaml przy użyciu naszego własnego silnika EC.

• Drugi (informacje o kodzie i reprodukcji dostępne na stronie projektu ), mój osobisty wkład w projekt, ewoluuje asembler x86 lub kod bajtu Java skompilowany z programów napisanych w wielu językach programowania. Ta aplikacja jest zaimplementowana w Clojure, a także korzysta z własnego, niestandardowego silnika EC.

Jednym z miłych aspektów Evolutionary Computation jest prostota techniki, która umożliwia pisanie własnych implementacji bez większych trudności. Dobry, swobodnie dostępny tekst wprowadzający na temat programowania genetycznego znajduje się w Przewodniku po programowaniu genetycznym .

Wspólnie ze współpracownikiem pracujemy nad rozwiązaniem do załadunku towarów na ciężarówki przy użyciu różnych kryteriów wymaganych przez naszą firmę. Pracowałem nad rozwiązaniem algorytmu genetycznego, gdy on używa odgałęzienia i agresywnego przycinania. Wciąż wdrażamy to rozwiązanie, ale jak dotąd osiągamy dobre wyniki.

Kilka lat temu użyłem ga do optymalizacji gramatyki asr (automatyczne rozpoznawanie mowy) w celu uzyskania lepszych wskaźników rozpoznawania. Zacząłem od dość prostych list wyborów (gdzie testowałem kombinacje możliwych terminów dla każdego automatu) i zacząłem pracować nad bardziej otwartymi i złożonymi gramatykami. Sprawność określono na podstawie pomiaru separacji między terminami / sekwencjami w rodzaju fonetycznej funkcji odległości. Eksperymentowałem również z tworzeniem słabo równoważnych odmian gramatyki, aby znaleźć taką, która skompilowała się do bardziej zwartej reprezentacji (ostatecznie zdecydowałem się na bezpośredni algorytm, który drastycznie zwiększył rozmiar „języka”, którego moglibyśmy użyć w aplikacjach) .

Niedawno wykorzystałem je jako domyślną hipotezę, w oparciu o którą testowano jakość rozwiązań generowanych z różnych algorytmów. W dużej mierze wiązało się to z kategoryzacją i różnego rodzaju problemami z dopasowaniem (tj. Stworzyć „regułę”, która wyjaśnia zestaw wyborów dokonywanych przez recenzentów nad zestawem danych).

Zrobiłem kompletny framework GA o nazwie „GALAB”, aby rozwiązać wiele problemów:

• lokalizowanie GSM ANT (BTS) w celu zmniejszenia nakładania się i pustych lokalizacji.
• Planowanie projektu z ograniczeniami zasobów.
• Ewolucyjne tworzenie obrazu. ( Evopic )
• Problem sprzedawcy podróży.
• Problemy z N-Queen i N-Color.
• Trasa rycerska i problemy z plecakiem.
• Puzzle Magic Square i Sudoku.
• kompresja łańcuchów oparta na problemie Superstring.
• Problem z pakowaniem 2D.
• Tiny APP sztucznego życia.
• Układanka Rubik.

Kiedyś użyłem GA do optymalizacji funkcji skrótu dla adresów pamięci. Adresy miały rozmiary stron 4K lub 8K, więc wykazywały pewną przewidywalność we wzorcu bitowym adresu (najmniej znaczące bity wszystkie zero; bity środkowe zwiększały się regularnie itp.) Oryginalna funkcja skrótu była „masywna” - miała tendencję do uderzeń w klaster na co trzecim wiadrze mieszającym. Ulepszony algorytm miał prawie idealny rozkład.

Nie wiem, czy praca domowa się liczy ...

Podczas moich studiów opracowaliśmy własny program rozwiązywania problemu Traveling Salesman.

Chodziło o porównanie kilku kryteriów (trudność odwzorowania problemu, wydajność itp.). Zastosowaliśmy także inne techniki, takie jak Symulowane wyżarzanie .

Działało całkiem dobrze, ale zajęło nam trochę czasu, aby zrozumieć, jak prawidłowo wykonać fazę „reprodukcji”: modelowanie problemu w coś odpowiedniego do programowania genetycznego naprawdę uderzyło mnie jako najtrudniejszą część ...

To był interesujący kurs, ponieważ zajmowaliśmy się także sieciami neuronowymi i tym podobnymi.

Chciałbym wiedzieć, czy ktoś używał tego rodzaju programowania w kodzie „produkcyjnym”.

Zbudowałem prosty GA do wydobywania użytecznych wzorców ze spektrum częstotliwości muzyki podczas jej odtwarzania. Dane wyjściowe wykorzystano do sterowania efektami graficznymi we wtyczce Winamp.

• Wejście: kilka ramek FFT (wyobraź sobie tablicę pływaków 2D)
• Wyjście: pojedyncza wartość zmiennoprzecinkowa (ważona suma danych wejściowych), progowana do 0,0 lub 1,0
• Geny: wagi wejściowe
• Funkcja fitness: połączenie cyklu pracy, szerokości impulsu i BPM w rozsądnym zakresie.

Miałem kilka GA dostrojonych do różnych części spektrum, a także różnych limitów BPM, więc nie miały tendencji do zbliżania się do tego samego wzoru. Dane wyjściowe z 4 najlepszych z każdej populacji zostały przesłane do mechanizmu renderowania.

Ciekawym efektem ubocznym było to, że średnia kondycja w całej populacji była dobrym wskaźnikiem zmian w muzyce, chociaż na ogół zajęło to 4-5 sekund.

W ramach mojej pracy napisałem ogólną platformę Java dla algorytmu optymalizacji wielozadaniowej mPOEMS (optymalizacja prototypu Multiobjective z ewoluowanymi krokami doskonalenia), która jest GA wykorzystującym koncepcje ewolucyjne. Ogólny sposób polega na tym, że wszystkie części niezależne od problemu zostały oddzielone od części zależnych od problemu, a interfejs jest przystosowany do korzystania z frameworka z dodawaniem tylko części zależnych od problemu. Dlatego ten, kto chce korzystać z algorytmu, nie musi zaczynać od zera, a to bardzo ułatwia pracę.

Możesz znaleźć kod tutaj .

Rozwiązania, które można znaleźć za pomocą tego algorytmu, zostały porównane w pracy naukowej z najnowocześniejszymi algorytmami SPEA-2 i NSGA, i udowodniono, że algorytm działa porównywalnie lub nawet lepiej, w zależności od metryk zmierzyć wydajność, a zwłaszcza w zależności od problemu optymalizacji, na który patrzysz.

Możesz go znaleźć tutaj .

Również w ramach mojej pracy magisterskiej i dowodu pracy zastosowałem te ramy do problemu wyboru projektów w zarządzaniu portfelem. Chodzi o wybór projektów, które wnoszą największą wartość do firmy, w największym stopniu wspierają strategię firmy lub wspierają wszelkie inne arbitralne cele. Np. Wybór określonej liczby projektów z określonej kategorii lub maksymalizacja synergii projektów, ...

Moja teza, która stosuje te ramy do problemu wyboru projektu: http://www.ub.tuwien.ac.at/dipl/2008/AC05038968.pdf

Następnie pracowałem w dziale zarządzania portfelem w jednym z fortune 500, gdzie korzystali z oprogramowania komercyjnego, które również stosowało GA do problemu wyboru projektu / optymalizacji portfela.

Dalsze zasoby:

Dokumentacja frameworka: http://thomaskremmel.com/mpoems/mpoems_in_java_documentation.pdf

Dokument prezentacyjny mPOEMS: http://portal.acm.org/citation.cfm?id=1792634.1792653

W rzeczywistości z odrobiną entuzjazmu każdy może łatwo dostosować kod ogólnej struktury do dowolnego problemu optymalizacji z wieloma celami.

W pracy miałem następujący problem: biorąc pod uwagę M zadań i N DSP, jaki był najlepszy sposób przypisania zadań do DSP? „Najlepszy” zdefiniowano jako „minimalizujący obciążenie najczęściej ładowanego DSP”. Były różne typy zadań, a różne typy zadań miały różne konsekwencje wydajnościowe w zależności od tego, gdzie zostały przypisane, więc kodowałem zestaw zadań do DSP jako „ciąg DNA”, a następnie użyłem algorytmu genetycznego do „rozmnażania” najlepszy ciąg przypisania, jaki mogłem.

Działa całkiem dobrze (znacznie lepiej niż moja poprzednia metoda, która polegała na ocenie każdej możliwej kombinacji ... przy nietypowych rozmiarach problemów zajęłoby lata!), Jedynym problemem było to, że nie było sposobu, aby powiedzieć czy osiągnięto optymalne rozwiązanie, czy nie. Możesz jedynie zdecydować, czy obecny „najlepszy wysiłek” był wystarczająco dobry, lub pozwolić mu działać dłużej, aby sprawdzić, czy da sobie radę.

Na codechef.com odbyła się konkurencja (nawiasem mówiąc, świetna strona, comiesięczne konkursy programistyczne), w której należało rozwiązać nierozwiązywalne sudoku (powinno być jak najbliżej, z jak najmniejszą liczbą błędnych kolumn / wierszy / itp.).

Chciałbym najpierw wygenerować idealne sudoku, a następnie zastąpić podane pola. Z tej dość dobrej podstawy wykorzystałem programowanie genetyczne, aby ulepszyć moje rozwiązanie.

W tym przypadku nie mogłem wymyślić deterministycznego podejścia, ponieważ sudoku miało wymiary 300 x 300, a wyszukiwanie trwałoby zbyt długo.

Użyłem prostego algorytmu genetycznego, aby zoptymalizować stosunek sygnału do szumu fali reprezentowanej jako ciąg binarny. Przerzucając bity na kilka sposobów przez kilka milionów pokoleń, byłem w stanie wyprodukować transformację, która spowodowała wyższy stosunek sygnału do szumu tej fali. Algorytm mógł być również „Symulowanym wyżarzaniem”, ale w tym przypadku nie został użyty. U ich podstaw algorytmy genetyczne są proste, a to był tak prosty przypadek użycia, jaki widziałem, więc nie użyłem ram do tworzenia i selekcji generacji - tylko losowe ziarno i stosunek sygnału do szumu funkcja pod ręką.

Podczas seminarium w szkole opracowujemy aplikację do generowania muzyki opartej na trybie muzycznym. Program został zbudowany w Javie, a wyjściem był plik midi z piosenką. Używamy różnych podejść GA do generowania muzyki. Myślę, że ten program może być przydatny do odkrywania nowych kompozycji.

w undergrad użyliśmy NERO (połączenie sieci neuronowej i algorytmu genetycznego), aby nauczyć robotów w grze podejmowania inteligentnych decyzji. To było całkiem fajne.

Opracowałem wielowątkową, opartą na huśtawce symulację nawigacji robota przez zestaw losowego terenu siatki źródeł żywności i kopalń, i opracowałem strategię opartą na algorytmie genetycznym, polegającą na badaniu optymalizacji zachowania robotów i przetrwania najsilniejszych genów dla robota chromosomowego. Dokonano tego za pomocą mapowania i mapowania każdego cyklu iteracji.

Od tego czasu opracowałem jeszcze więcej zachowań w grze. Przykładową aplikacją, którą niedawno zbudowałem dla siebie, był algorytm genetyczny służący do rozwiązania problemu podróżującego sprzedawcy w znalezieniu trasy w Wielkiej Brytanii, biorąc pod uwagę stany początkowe i docelowe, a także jeden / wiele punktów połączenia, opóźnienia, odwołania, prace budowlane, godzinę szczytu, strajki publiczne, rozważenie najszybszych i najtańszych tras. Następnie zapewnia zrównoważoną rekomendację dla trasy, którą należy obrać w danym dniu.

Ogólnie rzecz biorąc, moją strategią jest wykorzystanie reprezentacji genów opartej na POJO, następnie stosuję konkretne implementacje interfejsu do selekcji, mutacji, strategii krzyżowania i punktu kryteriów. Moja funkcja sprawności fizycznej staje się w zasadzie dość złożona w oparciu o strategię i kryteria, które muszę zastosować jako miarę heurystyczną.

Zastanawiałem się również nad zastosowaniem algorytmu genetycznego do automatycznego testowania w kodzie przy użyciu cyklicznych cyklów mutacji, w których algorytm rozumie logikę i próbuje ustalić raport o błędzie z zaleceniami dotyczącymi poprawek kodu. Zasadniczo sposób na zoptymalizowanie mojego kodu i dostarczenie zaleceń dotyczących ulepszeń, a także sposób automatyzacji odkrywania nowego kodu programowego. Próbowałem również zastosować algorytmy genetyczne do produkcji muzyki wśród innych aplikacji.

Ogólnie rzecz biorąc, uważam strategie ewolucyjne, takie jak większość metaheurystycznych / globalnych strategii optymalizacji, początkowo są one zbyt wolne, ale zaczynają się podnosić, gdy rozwiązania stają się coraz bliższe celu i pod warunkiem, że twoja funkcja fitness i heurystyka są dobrze dostosowane do produkcji ta zbieżność w przestrzeni wyszukiwania.

Raz próbowałem stworzyć komputerowego gracza do gry Go, opartego wyłącznie na programowaniu genetycznym. Każdy program byłby traktowany jako funkcja oceny sekwencji ruchów. Produkowane programy nie były jednak zbyt dobre, nawet na dość niewielkiej płycie 3x4.

Użyłem Perla i sam kodowałem wszystko. Dzisiaj zrobiłbym coś inaczej.

Po przeczytaniu The Blind Watchmaker zainteresowałem się programem pascal, który Dawkins powiedział, że opracował modele organizmów, które mogą ewoluować w czasie. Byłem wystarczająco zainteresowany, aby napisać własny przy użyciu Swarm . Nie zrobiłem wszystkich fantazyjnych stworzeń, które zrobił, ale moje „chromosomy” kontrolowały cechy, które wpływały na zdolność przetrwania organizmów. Żyli w prostym świecie i mogli walczyć z nim przeciwko sobie i swojemu otoczeniu.

Organizmy żyły lub umarły częściowo z powodu przypadku, ale także na podstawie tego, jak skutecznie przystosowały się do lokalnego środowiska, jak dobrze spożywały składniki odżywcze i jak skutecznie rozmnażały się. Było fajnie, ale także więcej dowodów dla mojej żony, że jestem maniakiem.

To było dawno temu, ale zwróciłem GA, aby rozwinąć jądra przetwarzające obraz w celu usunięcia śladów promieni kosmicznych z obrazów Teleskopu Kosmicznego Hubble'a (HST). Standardowym podejściem jest wykonywanie wielu ekspozycji za pomocą Hubble'a i zachowanie tylko tego samego na wszystkich zdjęciach. Ponieważ czas HST jest tak cenny, jestem miłośnikiem astronomii, a ostatnio uczestniczyłem w Kongresie Obliczeń Ewolucyjnych, pomyślałem o zastosowaniu GA do oczyszczenia pojedynczych ekspozycji.

Poszczególne osoby miały postać drzew, które jako dane wejściowe zajmowały obszar 3x3 pikseli, przeprowadziły obliczenia i podjęły decyzję o tym, czy i jak zmodyfikować środkowy piksel. Sprawność oceniono na podstawie porównania wyników z obrazem oczyszczonym w tradycyjny sposób (tj. Stosy ekspozycji).

W rzeczywistości zadziałało, ale nie wystarczająco dobrze, aby uzasadnić rezygnację z pierwotnego podejścia. Gdyby moja teza nie była ograniczona czasowo, mógłbym rozszerzyć pojemnik na części genetyczne dostępny dla algorytmu. Jestem pewien, że mogłem to znacznie poprawić.

Użyte biblioteki: Jeśli dobrze pamiętam, IRAF i cfitsio do przetwarzania danych obrazu astronomicznego i operacji we / wy.

W młodości eksperymentowałem z GA. Napisałem symulator w Pythonie, który działał w następujący sposób.

Geny zakodowały wagi sieci neuronowej.

Wejściami sieci neuronowej były „anteny”, które wykrywały dotyk. Wyższe wartości oznaczały bardzo blisko, a 0 oznaczało brak dotykania.

Wyjściami były dwa „koła”. Jeśli oba koła poszły do ​​przodu, facet poszedł do przodu. Jeśli koła były w przeciwnych kierunkach, facet się odwrócił. Moc wyjściowa determinowała prędkość obracania się koła.

Wygenerowano prosty labirynt. To było naprawdę proste - nawet głupie. Na dole ekranu był początek, a na górze bramka, z czterema ścianami pośrodku. Każda ściana miała losowo wybrane miejsce, więc zawsze była ścieżka.

Na początku założyłem przypadkowych facetów (myślałem o nich jak o błędach). Gdy tylko jeden facet osiągnął cel lub limit czasu został osiągnięty, sprawność została obliczona. W tym czasie był on odwrotnie proporcjonalny do odległości do bramki.

Następnie sparowałem je i „wyhodowałem”, aby stworzyć następne pokolenie. Prawdopodobieństwo wyboru do hodowli było proporcjonalne do jego przydatności. Czasami oznaczało to, że jeden był hodowany wielokrotnie sam, jeśli miał bardzo wysoką względną sprawność.

Myślałem, że rozwiną się „przytulanie do lewej ściany”, ale zawsze wydawało się, że podążają za czymś mniej optymalnym. W każdym eksperymencie błędy zbiegały się w spiralny wzór. Kręcą się na zewnątrz, aż dotkną ściany po prawej stronie. Będą za tym podążać, a potem, gdy dotrą do szczeliny, ruszą się spiralnie w dół (z dala od szczeliny) i wokół. Skręcaliby o 270 stopni w lewo, a następnie zwykle wchodzili w szczelinę. To prowadziłoby ich przez większość ścian, a często do celu.

Jedną z dodanych przeze mnie funkcji było wstawienie wektora kolorów do genów w celu śledzenia pokrewieństwa między osobnikami. Po kilku pokoleniach wszystkie będą miały ten sam kolor, co mówi mi, że powinienem mieć lepszą strategię hodowlaną.

Starałem się, aby opracowali lepszą strategię. Skomplikowałem sieć neuronową - dodając pamięć i wszystko. To nie pomogło. Zawsze widziałem tę samą strategię.

Próbowałem różnych rzeczy, takich jak oddzielne pule genów, które rekombinowały dopiero po 100 pokoleniach. Ale nic nie popchnę ich do lepszej strategii. Może to było niemożliwe.

Kolejną interesującą rzeczą jest wykres fitness w czasie. Istniały określone wzorce, takie jak maksymalna sprawność fizyczna, która spadała, zanim jeszcze wzrosła. Nigdy nie widziałem książki ewolucyjnej mówiącej o tej możliwości.