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

Stworzyłem małe stworzenia, które żyły w tym małym świecie. Mieli sieć neuronową mózgu, który otrzymał kilka wejść od świata, a wyjście było wektorem ruchu wśród innych działań. Ich mózgi były "genami".

Program zaczął się od losowej populacji stworzeń z przypadkowymi mózgami. Neurony wejściowe i wyjściowe były statyczne, ale to, co było pomiędzy, nie było.

Postanowiłem zrobić mały eksperyment. Dałem mózgowi stworzenia neuron wyjściowy o nazwie "usta" i neuron wejściowy o nazwie "ucho". Zaczął od nowa i był zaskoczony, że ewoluowały, aby zmaksymalizować przestrzeń, a każde odpowiednie stworzenie pozostanie w swojej części (jedzenie było umieszczone losowo). Nauczyli się współpracować ze sobą i nie wchodzić sobie w drogę. Zawsze były wyjątki.

Więc jaka jest lekcja tutaj? Komunikacja oznacza współpracę. Jak tylko wprowadzasz element, w którym krzywdzenie drugiego oznacza, że coś zyskujesz, to współpraca zostaje zniszczona.

Edit:

Napisałem go w C++ nie używając frameworków. Napisałem własną sieć neuronową i kod GA. Eric, dziękuję, że powiedziałeś, że to wiarygodne. Ludzie zazwyczaj nie wierzą w moce GA (chociaż ograniczenia są oczywiste), dopóki nie zagrali z nim. GA jest proste, ale nie uproszczone.

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

W tym celu należy wykonać następujące czynności:]}
• darcs clone --lazy http://www.mempko.com/darcs/neural/
• cd neural
• cmake .
• make
• cd demos/eaters
• ./eaters

W styczniu 2004 roku skontaktował się ze mną Philips New Display Technologies, który tworzył elektronikę dla pierwszego w historii komercyjnego e-atramentu, Sony Librie, który został wydany tylko w Japonii, lata przed Amazon Kindle i inne trafiły na rynek w USA i Europie.

Inżynierowie Philipsa mieli poważny problem. Kilka miesięcy przed tym, jak produkt miał trafić na rynek, wciąż pojawiał się ghost na ekranie podczas zmiany stron. Problemem było 200 kierowców, którzy tworzyliśmy pole elektrostatyczne. Każdy z tych przetworników miał określone napięcie, które musiało być ustawione od zera do 1000 mV lub coś w tym stylu. Ale jeśli zmienisz jednego z nich, to zmieni wszystko.

Więc optymalizacja napięcia każdego kierowcy z osobna nie wchodzi w rachubę. Liczba możliwych kombinacji wartości była w miliardach, a ocena pojedynczej kombinacji zajęła około 1 minuty specjalnej kamerze. Inżynierowie próbowali wielu standardowych optymalizacji techniki, 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 GP/GA pomoże i czy mogę się zaangażować. Tak, i przez około miesiąc pracowaliśmy razem, ja pisząc i strojąc bibliotekę GA, na syntetycznych danych, a on integrując ją z ich systemem. Potem, pewnego weekendu pozwolili mu żyć z prawdziwą rzeczą.

W następny poniedziałek dostałem te świecące e-maile od niego i ich projektanta sprzętu, o tym, jak nikt nie mógł uwierzyć niesamowitym rezultatom znalezionym przez GA. To było to. W tym samym roku produkt trafił na rynek.

Nie dostałem za to ani centa, ale mam prawo się przechwalać. Od początku mówili, że już przekroczyli budżet, więc wiedziałem, o co chodzi, zanim zacząłem nad tym pracować. To świetna historia dla zastosowań gazu. :)

Użyłem GA, aby zoptymalizować przydział miejsc na moim przyjęciu weselnym. 80 gości na 10 stołach. Funkcja oceny opierała się na utrzymywaniu osób z ich datami, umieszczaniu osób z czymś wspólnym razem i utrzymywaniu osób o skrajnie przeciwnych poglądach przy oddzielnych stołach.

Sprawdziłam go kilka razy. Za każdym razem mam dziewięć dobrych stołów i jeden z dziwnymi piłkami. W końcu moja żona zajmowała się siedzeniami.

My traveling salesman optimizer used a novel mapowanie chromosomu do trasy, co sprawiło, że rozmnażanie i mutowanie chromosomów stało się banalne bez ryzyka generowania nieprawidłowych tras.

Update: ponieważ kilka osób zapytało jak ...

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

Zamiast próbować kodować ten rozkaz bezpośrednio w chromosomie, my kodowanie instrukcji przekształcania roztworu referencyjnego w nowe rozwiązanie. W szczególności traktujemy chromosomy jako listy indeksów w tablicy do wymiany. Aby uzyskać dekodowanie chromosomu, zaczynamy od rozwiązania referencyjnego i stosujemy wszystkie swapy wskazane przez chromosom. Zamiana dwóch wpisów w tablicy zawsze skutkuje poprawnym rozwiązaniem: każdy gość (lub miasto) nadal pojawia się dokładnie raz.

W ten sposób chromosomy mogą być losowo generowane, mutowane i krzyżowane z innymi i zawsze będzie produkować poprawne rozwiązanie.

Użyłem algorytmów genetycznych (a także niektórych pokrewnych technik), aby określić najlepsze ustawienia dla systemu zarządzania ryzykiem, który próbował powstrzymać rolników złota od używania kradzionych kart kredytowych do płacenia za MMO. System przeprowadzi kilka tysięcy transakcji o" znanych " wartościach (oszustwo lub nie) i wykona najlepszą kombinację ustawień, aby prawidłowo zidentyfikować oszukańcze transakcje bez zbyt wielu fałszywych alarmów.

Mieliśmy dane na kilkadziesiąt (boolean) cechy 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 stworzy dużą liczbę losowych zestawów wartości, oceni je na podstawie znanych danych, wybierze te, które uzyskały najlepsze wyniki (zarówno pod względem wykrywania oszustw, jak i ograniczania liczby fałszywych alarmów), a następnie przekaże kilka najlepszych z każdego pokolenia, aby wytworzyć nowe pokolenie kandydatów. Po pewnej liczbie za zwycięzcę uznano najlepiej punktujący zestaw wartości.

Tworzenie korpusu znanych danych do testowania było piętą achillesową systemu. Jeśli czekałeś na obciążenia zwrotne, byłeś kilka miesięcy w tyle, próbując odpowiedzieć na oszustów, więc ktoś musiałby ręcznie przejrzeć dużą liczbę transakcji, aby zbudować ten korpus danych bez konieczności czekania zbyt długo.

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

Zrobiłem to wszystko używając Perla. Jedno uruchomienie oprogramowania na dość starym Linuksie zajęłoby 1-2 godziny (20 minut na załadowanie danych przez łącze WAN, reszta czasu spędzonego na chrupaniu). Wielkość każdej generacji była ograniczona dostępną pamięcią RAM. W tej chwili można się spodziewać, że cena spadnie w dół. szczególnie dobry zestaw wyników.

W sumie uniknął niektórych gafów, które pojawiły się ręcznie, próbując dostosować względne wartości dziesiątek wskaźników oszustw i konsekwentnie wymyślił lepsze rozwiązania, niż mogłem stworzyć ręcznie. AFAIK, jest jeszcze w użyciu (jakieś 3 lata po tym jak go napisałem).

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

Kilka lat temu znudziła mi się standardowa praca w piłce nożnej, wszyscy po prostu wchodzili do sieci i brali typy od jakiegoś pundit w prasie. Więc, pomyślałem, że nie może być trudno pokonać kilka kierunków dziennikarskich, prawda? Najpierw pomyślałem, żeby wziąć wyniki z Massey Ratings , a następnie ujawnić pod koniec sezonu moje strategia po zdobyciu sławy i chwały. Jednak z powodów, których nigdy nie odkryłem, że Massey nie śledzi AFL. Cynik we mnie wierzy, że to dlatego, że wynik każdej gry AFL stał się w zasadzie przypadkową szansą, ale moje skargi na ostatnie zmiany zasad należą do innego forum.

System zasadniczo uwzględniał siłę ofensywną, siłę defensywną, przewagę własnego boiska, poprawę z tygodnia na tydzień (lub jej brak) i szybkość zmian w każdej z nich. Stworzyło to zestaw równania wielomianowe dla każdej drużyny w sezonie. Można obliczyć zwycięzcę i wynik dla każdego meczu w danym terminie. Celem było znalezienie zestawu współczynników, które najbardziej pasują do wyników wszystkich poprzednich gier i wykorzystanie go do przewidywania nadchodzącego meczu tygodni.

W praktyce system znajdowałby rozwiązania, które dokładnie przewidywały ponad 90% wcześniejszych wyników gry. Następnie z powodzeniem wybierze około 60-80% gier na nadchodzący tydzień (czyli tydzień nie w zestaw treningowy).

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

Wszystko zbudowałem od podstaw, bez użycia frameworka.

Oprócz niektórych typowych problemów, takich jak podróżny sprzedawca i wariacja na temat Programu Mona Lisa Rogera Alsinga, napisałem również ewolucyjny Rozwiązywacz Sudoku (który wymagał nieco bardziej oryginalnej myśli z mojej strony, a nie tylko ponownego wdrożenia czyjegoś pomysłu). Istnieją bardziej wiarygodne algorytmy do rozwiązywania Sudokus, ale podejście ewolucyjne działa dość dobrze.

W ostatnich dniach bawiłem się ewolucyjnym program do znajdowania "zimnych talii" do Pokera po obejrzeniu tego artykułu{[2] } na Reddicie. W tej chwili nie jest to całkiem zadowalające, ale myślę, że mogę to poprawić.

Mam własny framework, którego używam do algorytmów ewolucyjnych.

Opracowałem home brew GA dla laserowego systemu profili powierzchniowych 3D, który moja firma opracowała dla przemysłu towarowego w 1992 roku. System opierał się na trójwymiarowej triangulacji i wykorzystywał Niestandardowy laserowy skaner liniowy, kamerę 512x512 (z niestandardowym przechwytywaniem hw). Odległość między kamerą a laserem nigdy nie była precyzyjna, a ogniskowa kamer nie mogła znaleźć się w pozycji 256,256, jakiej się spodziewałeś!

To był koszmar, aby spróbować i wypracować parametry kalibracji przy użyciu standardowej geometrii i symulowanego rozwiązywania równań stylu wyżarzania.

Algorytm genetyczny został uruchomiony wieczorem i stworzyłem kostkę kalibracyjną, aby ją przetestować. Znałem wymiary sześcianu z dużą dokładnością i dlatego pomysł był taki, że mój GA mógł opracować zestaw niestandardowych parametrów triangulacji dla każdej jednostki skanującej, który przezwyciężyłby różnice produkcyjne.

Sztuczka zadziałała. Byłem trochę oszołomiony! W ciągu około 10 generacje 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, gdy planujesz pomalować swój dom. Często masz na myśli jakiś kolor, ale nie jest to jeden z kolorów, który pokazuje sprzedawca.

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

kolorowy facet nosił ze sobą program, który używał GA. Zaczynał od 4 różnych kolorów-każdy zakodowany jako kodowany chromosom (którego dekodowana wartość byłaby wartością RGB). Konsument wybiera 1 z 4 kolorów (który jest najbliższy, który ma na myśli). Program przypisałby wtedy maksymalną sprawność do tej jednostki i przejście do następnej generacji za pomocą mutacji/crossover. Powyższe kroki będą powtarzane, dopóki konsument nie znajdzie dokładnego koloru, a następnie color guy powiedział mu kombinację RGB!

Poprzez przypisanie maksymalnej przydatności do koloru zamyka się na to, co konsument ma na myśli, program color guy zwiększa szanse na zbieżność do koloru, konsument ma dokładnie na myśli. To było całkiem zabawne!

Teraz, gdy mam -1, jeśli planujesz więcej -1, pls. wyjaśnij powód takiego działania!

Kilka tygodni temu zaproponowałem Rozwiązanie Na SO używając algorytmów genetycznych do rozwiązania problemu układu grafu. Jest to przykład ograniczonego problemu optymalizacji.

Również w obszarze uczenia maszynowego zaimplementowałem od podstaw Framework klasyfikacji oparty na GA w c / c++.
Wykorzystałem również GA w przykładowym projekcie do szkolenia sztucznych sieci neuronowych (ANN) w przeciwieństwie do użycia słynnego algorytmu backpropagacji .

In dodatkowo, jako część moich badań magisterskich, wykorzystałem ga w szkoleniu Ukryte modele Markowa jako dodatkowe podejście do algorytmu Baum-Welch bazującego na EM (ponownie w c/C++).

W ramach mojego licencjackiego stopnia CompSci, przydzielono nam problem znalezienia optymalnych FLAG jvm dla maszyny wirtualnej Jikes research. Zostało to ocenione za pomocą pakietu dicappo benchmark suite, który zwraca czas na konsolę. Napisałem rozproszony gentic alogirthm, który zmienił te flagi, aby poprawić czas działania pakietu benchmark, chociaż uruchomienie zajęło kilka dni, aby zrekompensować jitter sprzętowy wpływający na wyniki. Jedynym problemem było to, że nie dowiedziałem się właściwie o teorii kompilatora (co było celem zadania).

Mogłem zasiać początkową populację z wyjściowymi domyślnymi flagami, ale co ciekawe, algorytm znalazł bardzo podobną konfigurację do poziomu optymalizacji O3 (ale w rzeczywistości był szybszy w wielu testach).

Edit: napisałem również własny Framework algorytmu genetycznego w Pythonie do przypisania, i po prostu użyłem poleceń popen do uruchomienia różnych benchmarków, chociaż jeśli nie był oceniany / align = "center" bgcolor = "# e0ffe0 " / cesarz chin / / align = center /

Po pierwsze," Programowanie genetyczne " Jonathana Kozy (na amazon ) jest w zasadzie książką o genetycznych i ewolucyjnych algorytmach / technikach programowania, z wieloma przykładami. Proponuję to sprawdzić.

Jeśli chodzi o własne użycie algorytmu genetycznego, użyłem (domowego) algorytmu genetycznego, aby wyewoluować algorytm roju dla scenariusza zbierania/niszczenia obiektów (praktycznym celem mogło być oczyszczenie pola minowego). Oto link do gazety . Najbardziej interesującą częścią tego, co zrobiłem, była wielostopniowa funkcja fitness, która była koniecznością, ponieważ proste funkcje fitness nie dostarczyły wystarczającej informacji dla algorytmu genetycznego, aby wystarczająco odróżnić członków populacji.

Jestem częścią zespołu badającego wykorzystanie obliczeń ewolucyjnych (EC) do automatycznego naprawiania błędów w istniejących programach. Udało nam się naprawić wiele błędów w rzeczywistych projektach oprogramowania (zobacz Strona główna tego projektu).

Mamy dwa zastosowania tej techniki naprawy EC.

• Pierwsze (informacje o kodzie i reprodukcji dostępne na stronie projektu ) ewoluuje abstrakcyjne drzewa składni przetwarzane z istniejącego C programy i jest realizowany w Ocaml przy użyciu naszego własnego custom EC engine.

• Drugi (kod i informacje o reprodukcji dostępne za pośrednictwem Strony Projektu ), mój osobisty wkład w projekt, ewoluuje x86 assembly lub Java kod bajtowy skompilowany z programów napisanych w wielu językach programowania. Aplikacja ta jest zaimplementowana w Clojure, a także wykorzystuje własny, niestandardowy silnik EC.

Jednym z ładnych aspektów obliczeń ewolucyjnych jest prostota techniki umożliwia pisanie własnych, niestandardowych implementacji bez większych trudności. Aby uzyskać dobry, swobodnie dostępny tekst wprowadzający na temat programowania genetycznego, zobacz Field Guide to Genetic Programming .

Razem ze współpracownikiem pracujemy nad rozwiązaniem do załadunku ładunków na samochody ciężarowe według różnych kryteriów, jakich wymaga nasza firma. Pracowałem nad rozwiązaniem algorytmu genetycznego, kiedy on używa gałęzi i jest związany z agresywnym przycinaniem. Wciąż jesteśmy w trakcie wdrażania tego rozwiązania, ale do tej pory osiągaliśmy dobre wyniki.

Kilka lat temu korzystałem z ga do optymalizacji gramatyki asr (automatic speech recognition) dla lepszego rozpoznawania. Zacząłem od dość prostych list wyborów (gdzie ga testował kombinacje możliwych terminów dla każdego gniazda) i pracowałem na drodze do bardziej otwartych i złożonych gramatyk. Sprawność określano poprzez pomiar separacji terminów/sekwencji w ramach pewnego rodzaju funkcji odległości fonetycznej. Eksperymentowałem również z tworzeniem słabo równoważnych odmian gramatyki, aby znaleźć to skompilowane do bardziej zwartej reprezentacji (w końcu poszedłem z bezpośrednim algorytmem, a to drastycznie zwiększyło rozmiar "języka", który możemy używać w aplikacjach).

Ostatnio używałem ich jako domyślnej hipotezy, na podstawie której sprawdzałem jakość rozwiązań generowanych z różnych algorytmów. To w dużej mierze wiązało się z kategoryzacją i różnymi rodzajami problemów z dopasowaniem (tj. stworzyć "regułę", która wyjaśnia zestaw wyborów dokonywanych przez recenzentów nad dataset (s)).

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

• lokalizowanie mrówek GSM (BTS), aby zmniejszyć nakładanie się i puste lokalizacje.
[[3]}Planowanie projektu ograniczenia zasobów.
• ewolucyjne tworzenie obrazu. (Evopic)
Problem z podróżnym sprzedawcą.
• N-Queen & N-Color problems.
• Knight ' s tour & Knapsack problems.
Magiczny kwadrat i łamigłówki Sudoku.
• kompresja strun, oparta na Superstringu problem.
• problem z opakowaniem 2D.
Mała aplikacja do sztucznego życia. Rubik puzzle.

Kiedyś użyłem GA do optymalizacji funkcji hash dla adresów pamięci. Adresy miały Rozmiar stron 4K lub 8K, więc wykazywały pewną przewidywalność w wzorze bitowym adresu (najmniej znaczące bity to zero; środkowe bity regularnie zwiększające się itp.) Oryginalna funkcja hash była "chunky" - miała tendencję do cluster hits na co trzecim wiadrze hash. Ulepszony algorytm miał prawie idealny rozkład.

Zbudowałem prosty GA do wydobywania użytecznych wzorców ze spektrum częstotliwości muzyki, gdy była odtwarzana. Wyjście zostało użyte do wyświetlania efektów graficznych w wtyczce Winampa.

W tym celu należy wykonać następujące czynności:]}
• Wyjście: pojedyncza wartość zmiennoprzecinkowa (ważona suma wejść), próg 0.0 lub 1.0
• geny: waga wejściowa
• Funkcja Fitness: połączenie cyklu pracy, szerokości impulsu i BPM w rozsądnym zakresie.

I miał kilka gazów dostrojonych do różnych części widma, a także różne limity BPM, więc nie miały tendencji do zbieżności w kierunku tego samego wzoru. Wyniki z pierwszej 4 z każdej populacji zostały wysłane do silnika renderującego.

Interesującym efektem ubocznym było to, że średnia sprawność w całej populacji była dobrym wskaźnikiem zmian w muzyce, chociaż zwykle zajęło to 4-5 sekund, aby to zrozumieć.

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

Podczas moich studiów zwijaliśmy nasz własny program, aby rozwiązać problem komiwojażera.

Chodziło o porównanie kilku kryteriów (trudności w mapowaniu problemu, wydajności itp.), a my również użyliśmy innych technik, takich jak symulowane wyżarzanie.

To działało całkiem dobrze, ale zajęło nam trochę czasu, aby zrozumieć, jak zrobić fazę "reprodukcji" poprawnie: modelowanie problemu pod ręką w coś odpowiedniego ponieważ Programowanie genetyczne naprawdę uderzyło mnie jako najtrudniejszą część...

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

Chciałbym się dowiedzieć, czy ktoś używał tego typu programowania w kodzie 'produkcyjnym'.

Użyłem prostego algorytmu genetycznego, aby zoptymalizować stosunek sygnału do szumu fali reprezentowanej jako ciąg binarny. Przez przerzucanie bitów na kilka milionów generacji udało mi się wytworzyć transformację, która zaowocowała wyższym stosunkiem sygnału do szumu tej fali. Algorytm mógł być również "symulowanym wyżarzaniem", ale nie został w tym przypadku użyty. W ich rdzeniu algorytmy genetyczne są proste, a to był tak prosty przypadek użycia, że widziałem, więc nie używałem frameworka do tworzenia i selekcji generacji-tylko losowe ziarno i funkcja stosunek sygnału Do Szumu pod ręką.

W ramach pracy napisałam generyczny framework Javy dla algorytmu optymalizacji wielu celów mPOEMS( Multiobjective prototype optimization with evolved improvement steps), który jest GA wykorzystującym koncepcje ewolucyjne. Jest to ogólne w taki sposób, że wszystkie części niezależne od problemów zostały oddzielone od części zależnych od problemów, a interfejs jest povided do korzystania z frameworku tylko dodanie części zależnych od problemów. Tym samym kto chce korzystać z algorytmu nie musi zacznij od zera, a to znacznie ułatwia pracę.

Kod znajdziesz 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, które przyjmujesz do pomiaru wydajności, a zwłaszcza w zależności od problemu optymalizacji, na który patrzysz.

Znajdziesz go tutaj .

Również w ramach pracy dyplomowej i proof of work zastosowałem ten framework do problemu wyboru projektów w zarządzaniu portfelem. Chodzi o wybór projektów, które dodają firmie największą wartość, wspierają najbardziej strategię firmy lub wspierają dowolny inny arbitralny cel. Np. wybór określonej liczby projektów z określonej kategorii lub maksymalizacja synergii projektowych ...

Moja praca, która stosuje ten framework do projektu problem z wyborem: http://www.ub.tuwien.ac.at/dipl/2008/AC05038968.pdf

Potem pracowałem w dziale zarządzania portfelem w jednym z fortune 500, gdzie używali komercyjnego oprogramowania, które również zastosowało GA do problemu wyboru projektu / optymalizacji portfela.

Dalsze zasoby:

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

Prezentacja MPOEMS papier: http://portal.acm.org/citation.cfm?id=1792634.1792653

Właściwie z odrobiną entuzjazmu każdy mógł łatwo dostosować kod generycznego frameworka do arbitralnego problemu optymalizacji wielu celów.

W pracy miałem następujący problem: biorąc pod uwagę zadania M I N DSP, jaki był najlepszy sposób przypisywania zadań do DSP? "Najlepszy" został zdefiniowany jako "minimalizacja obciążenia najbardziej obciążonego DSP". Były różne typy zadań, a różne typy zadań miały różne konsekwencje wydajności w zależności od tego, gdzie zostały przydzielone, więc zakodowałem zestaw zadań od zadania do DSP jako "ciąg DNA", a następnie użyłem algorytmu genetycznego ,aby "wyhodować" najlepszy ciąg zadań, jaki mogłem.

To działało uczciwie cóż (znacznie lepiej niż moja poprzednia metoda, która polegała na ocenie każdej możliwej kombinacji... w przypadku nietrywialnych rozmiarów problemów, ukończenie ich zajęłoby lata!), jedynym problemem było to, że nie było sposobu, aby stwierdzić, czy optymalne rozwiązanie zostało osiągnięte, czy nie. Można było tylko zdecydować, czy obecny "najlepszy wysiłek" był wystarczająco dobry, lub pozwolić działać dłużej, aby zobaczyć, czy może zrobić lepiej.

Odbył się konkurs na codechef.com (świetna strona przy okazji, comiesięczne konkursy programistyczne), gdzie należało rozwiązać nierozwiązywalne sudoku (należy podejść jak najbliżej z jak najmniej błędnych kolumnów / wierszy / etc).

To, co bym zrobił, to najpierw wygenerować idealne sudoku, a następnie nadpisać pola, które zostały podane. Z tej całkiem dobrej podstawy użyłem programowania genetycznego, aby poprawić moje rozwiązanie.

I couldn ' t think of a deterministyczne podejście w tym przypadku, ponieważ sudoku było 300x300 i wyszukiwanie zajęłoby zbyt długo.

Na seminarium w szkole rozwijamy aplikację do generowania muzyki w oparciu o tryb muzyczny. Program został zbudowany w Javie, a wyjściem był plik midi z utworem. Do generowania muzyki używamy charakterystyk ga. Myślę, że ten program może być przydatny do odkrywania nowych kompozycji.

W trakcie studiów wykorzystaliśmy NERO (połączenie sieci neuronowej i algorytmu genetycznego), aby nauczyć roboty w grze podejmowania inteligentnych decyzji. To było całkiem fajne.

Opracowałem wielowątkową symulację poruszania się robotów na podstawie zestawu randomizowanego terenu siatkowego źródeł żywności i kopalń oraz opracowałem strategię opartą na algorytmie genetycznym badającą optymalizację zachowań robotów i przetrwanie najsilniejszych genów dla robotycznego chromosomu. Dokonano tego za pomocą wykresów i mapowania każdego cyklu iteracji.

Od tego czasu rozwinąłem jeszcze więcej zachowań w grze. Przykładowa aplikacja, którą zbudowałem niedawno dla siebie, była genetyczną algorytm rozwiązywania problemu podróżujących sprzedawców w poszukiwaniu trasy w Wielkiej Brytanii, biorąc pod uwagę Stany startowe i cele, a także jeden / wiele punktów połączeń, opóźnienia, odwołania, roboty budowlane, godziny szczytu, strajki publiczne, rozważenie między najszybszymi a najtańszymi trasami. Następnie zapewnienie wyważonej rekomendacji dla trasy do podjęcia w danym dniu.

Ogólnie moją strategią jest użycie reprezentatora genów opartego na POJO, a następnie zastosowanie konkretnych implementacji interfejsu dla selekcja, mutacja, strategie crossover i punkt kryteriów. Moja funkcja fitness w zasadzie staje się dość złożona w oparciu o strategię i kryteria, które muszę zastosować jako środek heurystyczny.

Przyjrzałem się również zastosowaniu algorytmu genetycznego do zautomatyzowanych testów w kodzie przy użyciu systematycznych cykli mutacji, gdzie algorytm rozumie logikę i próbuje ustalić raport o błędzie z zaleceniami dotyczącymi poprawek kodu. Zasadniczo, sposób, aby zoptymalizować mój kod i zapewnić zalecenia dotyczące ulepszeń, a także sposób automatyzacji odkrywania nowego kodu programowego. Próbowałem również zastosować algorytmy genetyczne do produkcji muzyki między innymi.

Ogólnie rzecz biorąc, uważam strategie ewolucyjne jak większość strategii metaheurystycznych / globalnych optymalizacji, są one powoli uczyć się na początku, ale zaczynają podnosić jak rozwiązania stają się coraz bliżej stanu celu i tak długo, jak funkcja fitness i heurystyka są dobrze dopasowane do produkcji ta zbieżność w przestrzeni poszukiwań.

Kiedyś próbowałem stworzyć gracza komputerowego do gry Go, wyłącznie w oparciu o programowanie genetyczne. Każdy program będzie traktowany jako funkcja oceny sekwencji ruchów. Produkowane programy nie były jednak zbyt dobre, nawet na raczej malejącej płycie 3x4.

Użyłem Perla i sam wszystko zakodowałem. Dzisiaj zrobiłbym to inaczej.

Po przeczytaniu The Blind Watchmaker zainteresował mnie program Pascala, który Dawkins powiedział, że opracował, aby tworzyć modele organizmów, które mogą ewoluować w czasie. Byłem na tyle zainteresowany, aby napisać swój własny za pomocą Rój . Nie zrobiłem tych wszystkich fantazyjnych grafik, które zrobił, ale moje 'chromosomy' kontrolowały cechy, które wpływały na zdolność organizmów do przetrwania. Żyli w prostym świecie i mogli walczyć ze sobą i Swoim otoczeniem.

Organizmy żyły lub umierały częściowo dzięki przypadkowi, 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ę. To było zabawne, ale także dowód dla mojej żony, że jestem maniakiem.

To było jakiś czas temu, ale przewróciłem GA, aby ewoluować, co było w efekcie jąder przetwarzania obrazów, aby usunąć ślady promieniowania kosmicznego z obrazów Hubble Space Telescope (HST). Standardowym podejściem jest wykonywanie wielu ekspozycji za pomocą Hubble ' a i zachowywanie tylko tych rzeczy, które są takie same we wszystkich obrazach. Ponieważ czas HST jest tak cenny, jestem miłośnikiem astronomii i niedawno uczestniczyłem w Kongresie obliczeń ewolucyjnych, pomyślałem o użyciu GA do czyszczenia pojedynczych ekspozycji.

The osoby były w postaci drzew, które miały obszar pikseli 3x3 jako wejście, wykonały pewne obliczenia i podjęły decyzję o tym, czy i jak zmodyfikować środkowy piksel. Kondycję oceniano porównując wyjście z obrazem oczyszczonym w tradycyjny sposób(tj. układanie ekspozycji).

To faktycznie działa, ale nie na tyle dobrze, aby uzasadnić rezygnację z pierwotnego podejścia. Gdybym nie został ograniczony czasowo przez moją tezę, mógłbym rozszerzyć genetyczne części bin dostępne dla algorytmu. Jestem prawie pewien, że mogłem go znacznie poprawić.

Używane biblioteki: jeśli dobrze pamiętam, IRAF i cfitsio do przetwarzania danych astronomicznych i I/o.

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

Geny zakodowały masę sieci neuronowej.

Wejścia sieci neuronowej były "antenami", które wykrywały dotknięcia. Wyższe wartości oznaczały bardzo bliskie, a 0 nie dotykające.

Wyjścia były do dwóch "kół". Jeśli oba koła poszły do przodu, facet poszedł do przodu. Jeśli koła były w przeciwnych kierunkach, facet odwrócił się. Siła wyjściowa określała prędkość obrotu koła.

Powstał prosty labirynt. To było naprawdę proste, nawet głupie. Początek był na dole ekranu, a cel na górze, z czterema ścianami pomiędzy. Każda ściana miała miejsce losowo, więc zawsze była ścieżka.

Zacząłem przypadkowych facetów (myślałem o nich jak robaki) na początku. Jak tylko jeden facet osiągnął cel, lub limit czasu został osiągnięty, kondycja została obliczona. Była odwrotnie proporcjonalna do odległości do / align = "left" /

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

Myślałem, że rozwiną zachowanie "ściskania lewej ściany" , ale zawsze wydawało się, że podążają za czymś mniej optymalnym. W każdym eksperymencie robaki zbiegały się w spiralny wzór. Spirali Na Zewnątrz dopóki nie dotknęli ściany po prawej. Podążali za tym, a gdy dotarli do szczeliny, spirali w dół (z dala od szczeliny)i dookoła. Wykonują obrót o 270 stopni w lewo, a następnie zwykle wchodzą w lukę. Dzięki temu przebijali się przez większość murów, a często do celu.

Jedną z funkcji, którą dodałem, było wprowadzenie wektora koloru do genów, aby śledzić pokrewieństwo między osobnikami. Po kilku pokoleniach wszystkie byłyby w tym samym kolorze, co mówi mi, że powinnam mieć lepsza strategia hodowli.

Próbowałem nakłonić ich do opracowania lepszej strategii. Skomplikowałem sieć neuronową. dodałem pamięć i w ogóle. To nie pomogło. Zawsze widziałem tę samą strategię.

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

Kolejną ciekawą rzeczą jest wykresy sprawności w czasie. Były określone wzory, takie jak maksymalna sprawność spada, zanim pójdzie w górę. Nigdy nie widziałem książki o ewolucji mówiącej o tej możliwości.