Agata Kukwa: Obliczenia ewolucyjne – technologia czy biologia?

29.11.2012
Agata Kukwa: Obliczenia ewolucyjne – technologia czy biologia?

Jest takie miejsce, w którym spotykają się dwie, z pozoru całkowicie niezależne dziedziny nauki. Za pojęciem, o którym będzie dzisiaj mowa stoi coś znacznie więcej: idea.

Wszystko zaczęło się w 1964 roku, kiedy Lawrence Fogel napisał pierwszą w historii rozprawę doktorską z zakresu obliczeń ewolucyjnych. Właśnie wtedy utopijna wizja o sztucznej inteligencji zaczęła nabierać realnego kształtu. Powstała hipoteza, że ewolucja może przyczyniać się nie tylko do rozwoju organizmów żywych, ale również technologii. Jednak w tym drugim przypadku proces ewolucji byłby inicjowany przez człowieka.

Obliczenia ewolucyjne są tak naprawdę wynikiem połączenia zaawansowanych technik obliczeniowych, genetyki oraz matematyki. Mimo że u podłoża leży dążenie do stworzenia sztucznej inteligencji, nieustanne prace nad rozwojem metod ewolucyjnych doprowadziły do znalezienia zastosowań dla stworzonych algorytmów w różnych dziedzinach.

Symulacja procesu ewolucji w programowaniu polega na stworzeniu algorytmu, który pozwalałby na rozwiązanie danego problemu poprzez generowanie i modyfikowanie rozwiązań pośrednich. W przypadku ewolucji naturalnej cechy populacji zmieniane są dzięki procesowi doboru naturalnego. W programowaniu natomiast mamy do czynienia tylko z doborem sztucznym, którego parametry ustanawia programista. Automatyczne odrzucanie poszczególnych, niewystarczająco dobrych, czyli nie spełniających wszystkich kryteriów rozwiązań powoduje ewolucję grupy tych najlepszych.

Jedną z ciekawszych technik w ramach obliczeń ewolucyjnych jest programowanie genetyczne. Odzwierciedla ono, na poziomie inżynieryjnym, mechanizm dziedziczenia cech. W genetyce cechy te decydują o wyglądzie, rozmnażaniu czy zachowaniu organizmów żywych. Programiści natomiast tworzą w ten sposób programy, które właściwie piszą się same.

Jak to działa? Wyobraźmy sobie, że robimy projekt strony internetowej dla bardzo wymagającego klienta, któremu zależy, aby była maksymalnie dostosowana do potrzeb i wymagań przyszłych użytkowników. Przeprowadzenie wstępnych badań w tym zakresie zajęłoby kilka dobrych miesięcy, a i tak byłby to dopiero początek drogi. Algorytmy genetyczne pozwalają rozwiązywać tego typu problemy w tempie nieosiągalnym nigdy wcześniej.

Wyobraźmy sobie, że główna strona serwisu naszego klienta składa się z paska menu, paska bocznego oraz pola tekstowego. Każdy z elementów może zostać umiejscowiony w 10 różnych miejscach, co w sumie daje 1000 wersji wyglądu strony głównej tylko pod kątem rozmieszczenia trzech elementów. W pierwszym etapie respondenci otrzymują internetowe kwestionariusze, w których zostają im przedstawione poszczególne wersje, które następnie odrzucane są z całej puli lub oznaczane jako najlepsze, w zależności od zdania badanych. Kolejne kwestionariusze pozbawione są już odrzuconych wersji, a respondenci odpowiadają na pytania związane tylko z tymi, których jeszcze nikomu nie pokazano lub tymi, które dotychczas zostały uznane za najlepsze. W ten sposób, zupełnie jak na zasadzie doboru naturalnego w naturze, projekt ewoluuje na podstawie opinii i preferencji konsumentów. Efektem końcowym jest wygenerowanie, która najbardziej odpowiada wymaganiom respondentów. Przy wcześniej przygotowanej bazie uczestników, nasz klient może otrzymać wynik optymalizacji już po kilku dniach.

Wykorzystanie algorytmów genetycznych w marketingu ma jedną, bardzo ważną zaletę – pozwala zapytać samych klientów. Danone wykorzystał tę metodę, jako jedna z pierwszych firm, już 9 lat temu, kiedy seria jogurtów Light & Fit nie radziła sobie z konkurencją. Danone postanowił zapytać konsumentów czego właściwie oczekują w tym zakresie, a z pomocą przyszły algorytmy ewolucyjne. W badaniu wzięło udział 705 osób, których ocenie poddano 11,268 kombinacji nazwy, opakowania, wielkości i oznaczenia wartości odżywczych jogurtu dietetycznego. Nie trudno sobie wyobrazić, ile trwałyby badania, gdyby każda z osób musiała ocenić każdą z ponad 11 tysięcy opcji. Zastosowanie algorytmu genetycznego, już w pierwszych turach pytań, pozwoliło na odrzucanie kombinacji, które kompletnie nie odpowiadały preferencjom konsumentów dzięki czemu nie były pokazywane kolejnym badanym. W miarę, jak program zdobywał coraz więcej informacji od respondentów, mógł modyfikować koncepcje przedstawiając kolejnym osobom nowe i lepsze rozwiązanie. Krótko mówiąc, koncept przechodził mutację, tak jak przechodzą je organizmy żywe w procesie ewolucji, aby dostosować się do warunków środowiska naturalnego. Projekt opakowania jogurtu Danon musiał się natomiast dostosować do warunków stworzonych przez konsumentów.

Po 6 dniach Danone otrzymał informację zwrotną: jogurt powinien być sprzedawany w czerwonych kubeczkach o pojemności 4 uncji (ok. 113g) połączonych w cztero-paki. Respondenci uznali też, że produkt powinien nazywać się „Carb Control” (ang. carb – skrót od carbohydrates, czyli węglowodany), a informacje na opakowaniu powinny brzmieć: „80% mniej cukru” oraz „3g węglowodanów”. Po 6 miesiącach nowy Light & Fit był już na sklepowych półkach, a 52 tygodnie później firma liczyła już zyski ze sprzedaży przekraczające 70 milionów dolarów. To chyba najlepszy dowód na skuteczność tej metody. Dannone korzystał z niej również w późniejszym czasie, na przykład przy projektowaniu kampanii Actimela. Potęga algorytmów genetycznych skusiła również Coca Colę podczas odświeżania wyglądu Sprite’a.

Problem Komiwojażera – źródło: tuo.agh.edu.pl

Największą zaletą algorytmów genetycznych jest ilość danych, które mogą być analizowane w tym samym czasie bez konieczności wykorzystania najszybszych i najdroższych superkomputerów na świecie. Świetnym przykładem do pokazania potencjału tego rozwiązania jest Problem Komiwojażera. To typowy problem optymalizacyjny, a właściwie jego ilustracja. Komiwojażer jest wędrownym sprzedawcą, który musi odwiedzić określoną liczbę miast, a następnie wrócić do domu. Znamy odległości między nimi, czas i koszt podróży, a naszym zadaniem jest wyznaczenie najkrótszej, najszybszej i najtańszej trasy łączącej wszystkie miejscowości uwzględniając powrót do punktu wyjścia. Jeśli jesteśmy w posiadaniu komputera, który jest w stanie przetworzyć milion instrukcji na sekundę, trasa złożona z 10 miast powinna zostać opracowana w mniej więcej 3,6 sekundy. Jednak zwiększenie liczby miejscowości do 100 sprawiłoby, że do zakończenia obliczeń upłynęłoby więcej czasu niż od wielkiego wybuchu stanowiącego narodziny Wszechświata.

Mimo że u podłoża obliczeń ewolucyjnych leżą dążenia do stworzenia sztucznego życia, do tej pory jeszcze oficjalnie nikomu nie udało się tego zrobić. Pierwsze próby symulacji procesów życiowych podejmowano już w latach 70.. Wtedy na przykład John Conoway, brytyjski matematyk, stworzył najbardziej znaną grę symulującą zachowania żywych komórek. W Grze w życie człowiek ustala jedynie stan wyjściowy „komórek”, liczbę żywych i uśpionych, podczas gdy w późniejszym czasie wszystko już dzieje się na podstawie algorytmów.

„Conway’s Life” – źródło: wikipedia

Do dzisiaj wiele się zmieniło, mamy już sieci neuronowe, robotykę, zaawansowane rozwiązania techniczne, czyli teoretycznie wszystko czego potrzeba do stworzenia prawdziwej sztucznej inteligencji. Podobnie jak w Grze w życie, w tym przypadku również człowiek musiałby wprowadzić określony pakiet danych wejściowych, na których podstawie system mógłby później nadbudowywać swoje struktury. Niestety, a może na szczęście, ciągle nie jesteśmy w stanie określić, co jest właściwie potrzebne, aby program komputerowy mógł funkcjonować na tyle samodzielnie, aby uczył się i podejmował autonomiczne decyzje.

źródło grafiki głównej: flickr.com by ynse

Advertisement

Musisz przeczytać:

Dołącz do dyskusji

Advertisement
Advertisement