Programowanie genetyczne: Ewolucja kodu

Zgodnie z ewolucją wszyscy na Ziemi jesteśmy produktem doboru
naturalnego działającego przez odpowiednio długi czas liczony
w miliardach lat. Podobne mechanizmy ewolucyjne możemy już zaadaptować do budowy systemów komputerowych - wyniki takich operacji czasami zaskakują samych twórców.

Ewolucja to pojęcie zwykle kojarzące się wyłącznie z biologią, z rozwojem organizmów żywych, począwszy od najprostszych, jednokomórkowych form, po te najbardziej złożone. Karol Darwin, gdyby przyszło mu żyć w naszych czasach, byłby zdumiony szerokim spektrum zastosowań jego idei. Dziś wykorzystując darwinowskie koncepcje tworzymy rozwiązania w niemal każdej dziedzinie życia: inżynierii, technice wojskowej, medycynie. Algorytmy genetyczne z powodzeniem stosuje się również do tworzenia oprogramowania, zarządzania sieciami neuronowymi czy projektowania złożonych obwodów elektrycznych. Brzmi jak science fiction. Tymczasem zastosowanie cyfrowych odpowiedników doboru naturalnego, przemiany pokoleń, mutacji i całego arsenału ewolucyjnego pozwala tworzyć rozwiązania, których wykonanie tradycyjnymi metodami byłoby trudniejsze bądź bardziej kosztowne.

Gdy mowa o algorytmach genetycznych, nie sposób pominąć nazwiska profesora Johna Henry’ego Hollanda, człowieka uznawanego za „ojca algorytmów genetycznych”. Ponad 30 lat temu, w 1980 r., profesor Holland wraz ze swoim byłym studentem Davidem Goldbergiem pracowali nad rozwiązaniem problemu: w jaki sposób wykorzystać komputery do optymalizacji przepustowości gazociągów? Pierwszym etapem rozwiązania było skonstruowanie wstępnego modelu reprezentującego optymalizowany rurociąg i uwzględniającego istotne parametry pracy układu: ciśnienie gazu, natężenie przepływu paliwa, harmonogram prac pomp itp. Następnie model poddano losowym zmianom. Każda z nich wywoływana była przez algorytm działający w oparciu o reguły doboru naturalnego. Modyfikacje stały się mutacjami, a każdy zmieniony układ – następną generacją.

Komputer po każdym cyklu mutacji analizował sprawność układu, eliminując egzemplarze najsłabsze, czyli takie, które w stosunku do poprzedniego pokolenia okazywały się mniej lub co najwyżej tak samo wydajne. Do dalszej puli cyfrowych genów dopuszczane były jedynie takie warianty, w których udało się uzyskać wyższą sprawność - choćby najdrobniejszego elementu układu. Już po około 30 pokoleniach model systemu gazociągów ewoluował na tyle, że efektem było rozwiązanie charakteryzujące się zauważalnie wyższą efektywnością niż model bazowy oparty na rzeczywistym układzie optymalizowanego rurociągu.

Za adaptację algorytmów genetycznych do nowej metody programowania, zwanej programowaniem genetycznym, odpowiadał głównie dr John Koza, współpracownik profesora Hollanda. Pytanie, które w 1987 r. zadał sobie Koza, było dość proste: skoro algorytmy genetyczne tak skutecznie pozwalają optymalizować pracę rurociągów, dlaczego nie wykorzystać ich do rozwijania samego kodu? Zamiast podawać komputerowi problem, a następnie poszukiwać rozwiązania za pomocą istniejących narzędzi, może lepiej będzie wyjść od problemu, a w dalszej kolejności ewolucyjnie wyhodować narzędzia (kod), które ów problem rozwiążą?

W październiku 1995 r. John Koza pracował nad różnymi projektami obwodów elektronicznych, oczywiście z zastosowaniem mechanizmów darwinowskiej ewolucji. Jednak – w przeciwieństwie do pomysłu Hollanda i Goldberga – Koza nie zaczął od ulepszania jakiejś istniejącej konstrukcji. Rozpoczął od stosu elementów składowych dowolnego układu elektronicznego: niezwiązanych ze sobą rezystorów, kondensatorów itp. Komputerowi postawił natomiast zadanie budowy z istniejących składników funkcjonalnego układu mającego spełniać wymogi założonej specyfikacji. Uzyskanym rezultatem „elektronicznej ewolucji” okazał się w pełni sprawny filtr dolnoprzepustowy.

To właśnie dr John Koza był pierwszym człowiekiem, który nie tyle odkrył, co na szeroką skalę spopularyzował programowanie genetyczne, prezentując je jako metodę tworzenia nowych aplikacji i użytecznego kodu. Już w 1992 roku opublikował on książkę pt. „Genetic Programming: On the Programming of Computers by Means of Natural Selection” (Programowanie genetyczne: programowanie komputerów za pomocą selekcji naturalnej), w której przekonywał, że ewolucyjnie generowany kod pozwala tworzyć programy rozwiązujące bardzo złożone problemy.

Koza nie poprzestał wyłącznie na głoszeniu teorii, wdrażając idee genetycznego programowania w rzeczywistych projektach. Cechą programowania genetycznego szczególnie odróżniającą ją od technik klasycznych jest to, że dzięki niemu możliwe stało się rozwiązywanie złożonych problemów praktycznie bez wsparcia człowieka. Wiele projektów, w których do ich realizacji wykorzystano algorytmy genetyczne, zaowocowało powstaniem nieoczekiwanych wzorów i zaskakujących rozwiązań, które jednak wykonywały postawione przed nimi zadania zadziwiająco efektywnie – lepiej niż rozwiązania analogicznych problemów proponowane przez ekspertów w swoich dziedzinach. Pachnie sztuczną inteligencją? Jeszcze stanowczo za wcześnie, by o tym mówić, niemniej potencjał rozwiązań opartych na darwinowskiej teorii ewolucji jest teoretycznie znany – w końcu jakkolwiek by patrzeć, jej wynikiem jesteśmy my – istoty inteligentne.

Skuteczne wykorzystanie algorytmów genetycznych w sztuce programowania wymaga zaangażowania sporych mocy obliczeniowych, i to w zakresie szybkiego, równoległego realizowania zadań. Rezultaty programowania są tym lepsze, im większa jest „populacja”. Reguły doboru naturalnego działają tym skuteczniej, im więcej „pokoleń” programów uda się wyhodować, otrzymując w efekcie „osobnika” optymalnie dopasowanego do otaczającego go środowiska, czyli w kontekście programu: rozwiązującego postawiony na wstępie problem. Dr Koza prowadził swoje badania nad programowaniem genetycznym, wykorzystując klaster typu Beowulf złożony z 1000 maszyn z procesorami Pentium II i DEC Alpha. Klastry typu Beowulf to projekty realizowane z założeniem uzyskania maksymalnej mocy obliczeniowej możliwie najniższym kosztem – w przeciwieństwie do wyspecjalizowanych centrów danych, konstruowanych na bazie komponentów od początku opracowywanych pod kątem pracy w serwerowniach, klastry Beowulf konstruuje się, łącząc nawet zwykłe masowo produkowane
komputery osobiste.

Konstrukcja zbudowana przez zespół doktora Kozy została ochrzczona mianem „Invention machine” (z ang. maszyna do wynalazków). Nazwa nie jest przypadkowa. Za pomocą zbudowanego klastra oraz przy użyciu techniki programowania genetycznego maszyna już w 2003 roku wygenerowała rozwiązanie z zakresu optymalizacji produkcji w niektórych fabrykach. Wygenerowany drogą cyfrowej ewolucji efekt działań „Invention machine” to chyba pierwszy przypadek w historii ludzkości, kiedy ochroną patentową zostaje objęty rezultat pracy maszyny, a nie człowieka. Innymi słowy pierwszy patent przyznany projektantowi niebędącemu człowiekiem.

Oczywiście ze względów prawnych patent dzierży John Koza, jednak to nie on zaprojektował opatentowane rozwiązanie, jego zespół jedynie zdefiniował wstępne założenia. Pisząc bardziej obrazowo, poinformował komputer (klaster), co ma być zrobione, a nie jak – resztę miały załatwić reguły ewolucji i udało się to im z zadziwiającą efektywnością. Dzisiaj liczba projektów w pełni zrealizowanych przez maszyny wykorzystujące reguły darwinowskiej ewolucji jest naprawdę pokaźna i cały czas rośnie.

Warto przy tym zaznaczyć istotną rzecz: układy elektroniczne bądź urządzenia, będące wynikiem użycia algorytmów i programowania genetycznego, wykonują te same zadania, co wcześniej opracowane i opatentowane przez człowieka odpowiedniki, ale niejednokrotnie potrafią działać lepiej i nie naruszają oryginalnych patentów, bo są zupełnie inaczej opracowane.

Niektórzy wręcz twierdzą, że rozwiązania powstałe z wykorzystaniem algorytmów ewolucyjnych, czy kod aplikacji będących wynikiem programowania genetycznego to twory „nieludzkie”. Według nich trudno wyobrazić sobie, by jakikolwiek człowiek właśnie w taki sposób wymyślił rozwiązanie jakiegoś problemu. Wielu ekspertów, obserwując efekty uzyskane w wyniku zastosowania reguł ewolucji, uznaje rezultat za tak zagmatwany, że wręcz niezrozumiały, a mimo to skutecznie realizujący zadanie, do którego dany projekt został powołany.

Doktor John Koza i jego współpracownicy to niejedyni pasjonaci zastosowania mechanizmów ewolucji w tworzeniu oprogramowania czy innego typu rozwiązań informatycznych. Co roku naukowcy, projektanci i programiści z całego świata prezentują swoje osiągnięcia uzyskane przy użyciu technik ewolucyjnych na międzynarodowej konferencji GECCO (Genetic and Evolutionary Computation Conference). Oprócz konkursów (np. na najszybszą wirtualną kreaturę powstałą w wyniku cyfrowej ewolucji) na konferencji pokazywane są również użyteczne rozwiązania.

Przykładem może być oprogramowanie KOJAC – zestaw klas języka Java przeznaczonych do projektowania i symulacji złożonych systemów optycznych i soczewek stosowanych w różnego typu obiektywach, lunetach itp. Kod KOJAC to wynik programowania genetycznego. Za pomocą tego kodu Lee Jones, jeden z współpracowników doktora Johna Kozy, opracował już w 2006 roku kompleksowy system soczewek przewyższający efektywnością opatentowane zaledwie sześć lat wcześniej rozwiązanie opracowane przez japońskich ekspertów: Noboru Koizumi i Naomi Watanabe. „Optyczny symulator” – jak go określa Jones – zaprojektował układ optyczny doskonalszy od wynalazku ekspertów, i to bez naruszania posiadanego przez nich patentu.

Jak działa KOJAC? Procedura jest teoretycznie prosta: zaczynamy od recepty, czyli numerycznego opisu grubości, krzywizny, rodzaju szkła i innych parametrów charakteryzujących elementy składowe projektowanego obiektywu. Po wprowadzeniu licznego zestawu zmiennych KOJAC jest w stanie wygenerować informacje na temat praktycznego działania danego układu optycznego w świecie rzeczywistym.

KOJAC stanowi jednak zaledwie część całego maszynowego procesu tworzenia. Najpierw „Invention machine”, czyli klaster obliczeniowy z odpowiednim oprogramowaniem, generuje 75 tysięcy zestawów parametrów układu optycznego. Następnie każdy z tych zestawów jest analizowany przez KOJAC, który przypisuje poszczególnym receptom oceny szacowane na podstawie tego, czy rezultat jest bliski temu, co określa z góry ustalona specyfikacja projektu. Każdy z tych 75 tysięcy obiektów jest w algorytmie genetycznym osobnikiem, poddawanym zasadom ewolucji: prokreacja, mutacje, przekazywanie informacji kolejnym pokoleniom, „wymieranie” egzemplarzy najmniej udanych i po wielu dziesiątkach, setkach czy nawet tysiącach pokoleń uzyskujemy efekt spełniający pierwotne założenia.

Techniki ewolucyjnego projektowania stosować można oczywiście nie tylko tak jak w przytoczonym przykładzie: do projektowania złożonych układów optycznych. Stosowanie zasad darwinowskiej ewolucji powinno przynieść wymierne rezultaty w każdym przypadku poszukiwania optymalnego rozwiązania złożone - go problemu, np. w projektowaniu możliwie najbardziej energooszczędnych układów elektronicznych wykorzystywanych przez smartfony, tablety czy laptopy.

-- CZYTAJ DALEJ --

Cechą rezultatów uzyskanych w wyniku zastosowania reguł ewolucji w projektowaniu komputerowym jest to, że często efekty wydają się absurdalne, niedorzeczne i sprzeczne z intuicją, a mimo to zwykle doskonale realizują swoje zadania. Dr Adrian Thompson, pracownik naukowy University of Sussex, jeszcze w latach 90. XX wieku eksperymentował z zastosowaniem reguł ewolucyjnych w stosunku do bezpośrednio programowalnych macierzy bramek - układów FPGA (Field Programmable Gate Array). Wyróżniają się one tym, że mogą być wielokrotnie przeprogramowywane.

Zadaniem, które postawił swoim „osobnikom”, czyli układom FPGA modyfikowanym ewolucyjnie, było precyzyjne rozróżnienie dwóch sygnałów dźwiękowych – o częstotliwości 1 kHz oraz 10 kHz. Początkowo rezultaty były dalekie od oczekiwań, ale już po około 1500 „pokoleniach” rozróżnialność założonych częstotliwości wejściowych sięgała 50 proc., a 3,5-tysięczna „generacja” zawierała układ FPGA znakomicie realizujący postawione przed nim zadanie. Gdy jednak Thompson zaczął analizować strukturę wygenerowanego ewolucyjnie tworu, okazało się, że „cyfrowa ewolucja” układu uzyskała założony rezultat, wykorzystując zaledwie 37 proc. dostępnych bramek logicznych układu. Powstałe połączenia były kompletnie niezrozumiałe i wydawały się sprzeczne z logiką, wiele elementów wydawało się kompletnie niepotrzebnych. Mimo to całość działała wręcz perfekcyjnie.

Innym przykładem rozwiązania powstałego z wykorzystaniem algorytmów ewolucyjnych i charakteryzującego się wyższą efektywnością od pomysłów najlepszych ludzkich ekspertów może być projekt zrealizowany przez NASA w ramach misji Space Technology 5. Podstawowym zadaniem misji NASA ST5 było przetestowanie nowych technologii, które mogą być użyte w przyszłych misjach kosmicznych. Chodziło przede wszystkim o miniaturyzację oraz optymalizację podsystemów łączności.

Anteny, w które wyposażono każdy z satelitów misji, zostały w całości zaprojektowane przez komputery - właśnie dzięki algorytmom genetycznym. Na użycie metod ewolucyjnych do projektowania anten wpadł jeden z pracowników NASA Ames Research Center – Jason D. Lohn. Zdefiniował on podstawowe wymagania wobec anteny, a następnie uruchomił program, którego zadaniem było ewolucyjne „wyhodowanie” projektu spełniającego narzucone przez specyfikację wymogi. To, co otrzymał kilkaset pokoleń później, na pierwszy rzut oka wyglądało jak poważny błąd lub co najmniej wielkie rozczarowanie. Komputer wygenerował antenę, która przypominała… spinacz biurowy.

Lohn nie miał doświadczenia w projektowaniu anten, ale miał doświadczenie w stosowaniu algorytmów genetycznych i był przygotowany na to, że rezultaty mogą być nieco dziwne. Ta przezorność uratowała pozornie nieudany projekt. Uzyskana konstrukcja nie przypominała w niczym żadnej znanej anteny. Wielu ekspertów, z którymi Lohn się konsultował, przyznawało, że wyglądała dziwnie, wręcz niedorzecznie. Ale po sprawdzeniu i zasymulowaniu spodziewanych warunków pracy na niskiej orbicie ów niedorzeczny twór okazał się fenomenalnie działającym produktem, znacznie sprawniejszym od dotychczas wymyślonych przez inżynierów NASA. „Ewolucyjny spinacz” czy raczej wygenerowana za pomocą genetycznych algorytmów antena niskoorbitalna funkcjonowała później bezawaryjnie przez całą misję NASA ST5.

Zastosowanie reguł ewolucyjnych do tworzenia oprogramowania w znacznym stopniu zmienia rolę programisty, ale w żadnym razie nie eliminuje go z procesu twórczego. Programista nie tworzy całego kodu, a jedynie definiuje problem i określa kierunek rozwoju poprzez przygotowanie wstępnych rozwiązań, które następnie podlegają typowo ewolucyjnej przemianie pokoleniowej. Kod jest w zasadzie losowo zmieniany (w ramach zaprojektowanego przez programistę „środowiska naturalnego”), powstają kolejne generacje rozwiązań konkurujących ze sobą, a całe to tasowanie trwa tak długo, aż po przeminięciu wielu „pokoleń” powstaje ulepszona, rozwinięta wersja kodu rozwiązująca postawiony na wstępie problem.

Podstawowym założeniem programowania genetycznego jest określenie komputerowi co ma być zrobione, a nie – jak. Inaczej rzecz ujmując, programowanie genetyczne to metoda automatycznego generowania rozwiązania problemu na podstawie jego opisu. Rozwiązaniem w takim przypadku jest wytworzony na drodze ewolucyjnej gotowy program komputerowy.

Warto zaznaczyć, że algorytmy genetyczne i programowanie genetyczne nie stanowią panaceum na wszystkie kłopoty współczesnego świata. Istnieje wiele problemów, które rozwiążemy szybciej za pomocą metod innych niż wskutek zastosowania algorytmów genetycznych. Przykładem zadania, w przypadku którego użycie algorytmu genetycznego (choć możliwe) jest mniej efektywne od tradycyjnego podejścia okazuje się sortowanie danych. Jednak w sytuacji, gdy celem jest np. znalezienie precyzyjnie działających leków najnowszej generacji, zastosowanie algorytmów genetycznych może przynieść ludzkości wymierne korzyści.