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, takie jak choćby homo sapiens. W rzeczywistości Karol Darwin, gdyby przyszło mu żyć w naszych czasach, byłby zdumiony szerokim spektrum zastosowań jego idei. Dziś wykorzystując darwinowskie koncepcje “nieinteligentnego projektu”, tworzymy rozwiązania w niemal każdej dziedzinie życia: inżynierii, technice wojskowej, medycynie itp. 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.
Komputer i… ewolucja gazociągów
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 (ówczesnym doktorantem) 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 formalnie losowym zmianom, jednak każda taka zmiana indukowana 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 układy, 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.
Kod, który zmienia kod
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.
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.
Maszyna dostaje patent
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.
John Koza (na zdj.)
Konstrukcja zbudowana przez zespół doktora Kozy została ochrzczona mianem “Invention machine” (z ang. maszyna wynalazca). 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. Niektóre przykłady z zakresu elektroniki zamieściliśmy w ramce “Wynalazki maszyn”. 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”, co ma oznaczać nie tylko to, że nie zostały w pełni opracowane przez człowieka, ale też to, że 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.
Darwin w maszynie
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 różnych 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 istotną 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.
Skuteczna niedorzeczność
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ą one swoje zadania w zakresie zgodnym z wstępną specyfikacją. 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, czyli mówiąc inaczej, układów FPGA (Field Programmable Gate Array). Układy FPGA wyróżniają się tym, że mogą być wielokrotnie przeprogramowywane po tym, jak już zostaną fizycznie skonstruowane. Zadaniem, które postawił swoim “osobnikom”, czyli układom FPGA modyfikowanym ewolucyjnie (Thompson użył układów Xilinx XC6216 FPGA wyposażonych w zaledwie 100 bramek logicznych), 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, doznał niemal szoku, stwierdzając, że “cyfrowa ewolucja” układu uzyskała założony rezultat, wykorzystując zaledwie 37 proc. dostępnych bramek logicznych układu, przy czym powstałe połączenia były kompletnie niezrozumiałe i wydawały się sprzeczne z logiką, a wiele elementów wydawało się kompletnie niepotrzebnych. Mimo to całość działała wręcz perfekcyjnie.
Ewolucja ponad inwencją
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ę (w skład misji wchodziły trzy mikrosatelity
o masie ok. 25 kg każdy) 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 ewolucyjnie wyhodowana antena wyglądała dziwnie, wręcz niedorzecznie. Ale po sprawdzeniu i zasymulowaniu spodziewanych warunków pracy na niskiej orbicie ów niedorzeczny, wydawałoby się, 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.
Hodowla programów
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. Generalnie podstawowym założeniem czy raczej trendem przewodnim w programowaniu genetycznym jest to, żeby określić 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.