Przeskocz do treści

Delta mi!

Seks a informatyka

Wojciech Czerwiński

o artykule ...

  • Publikacja w Delcie: grudzień 2016
  • Publikacja elektroniczna: 30 listopada 2016
  • Autor: Wojciech Czerwiński
    Afiliacja: adiunkt, Instytut Informatyki, Uniwersytet Warszawski
  • Wersja do druku [application/pdf]: (32 KB)

Czy już naprawdę nawet w Delcie musi być o seksie? Sytuacja wygląda trochę jak rozprawa "Słoń a Polska", przy czym w XIX wieku niektórym wszystko kojarzyło się ze sprawą polską, a teraz z czymś nieco innym. Zaniepokojonych Czytelników spieszymy uspokoić, że rzeczy nie mają się aż tak źle, bo artykuł naprawdę dotyczy rozmnażania płciowego i informatyki.

Zacznijmy jednak od początku. Obserwując przyrodę, zauważamy, że istnieją w zasadzie dwa konkurencyjne sposoby pomnażania osobników danego gatunku: rozmnażanie bezpłciowe oraz rozmnażanie płciowe. Nietrudno jednak zauważyć, że organizmy bardziej skomplikowane, czy też można powiedzieć zaawansowane, stosują zazwyczaj metodę rozmnażania płciowego, więc logiczne byłoby wnioskowanie, że jest ono w pewnym sensie lepsze.

Przyjrzyjmy się tym dwóm taktykom i zobaczmy, że można je zinterpretować w kontekście informatyki. Ewolucję samą w sobie możemy bowiem traktować jako obliczenie. Obliczenie to przeszukuje pewien zbiór obiektów i poszukuje takiego o najwyższej funkcji celu. Można, upraszczając, powiedzieć, że w biologii zbiór ten to zbiór potencjalnych osobników danego gatunku, a funkcja celu to miara przystosowania osobnika do środowiska.

W przypadku rozmnażania bezpłciowego poszukiwanie zaczyna się od pewnego ustalonego obiektu i modyfikuje go nieznacznie (przez mutacje). Jeśli zmodyfikowany obiekt ma większą funkcję celu, to presja ewolucyjna powoduje, że właśnie tego obiektu i jemu podobnych będzie z czasem coraz więcej. Trwa to do momentu, gdy w populacji dominować będą osobniki, których właściwie nie da się poprawić przez mutację. To odpowiadałoby w informatyce przeszukiwaniu przestrzeni stanów w poszukiwaniu optimum lokalnego, tzn. przeglądaniu sąsiadów danego obiektu, porównywaniu funkcji celu i jeśli ta jest większa u sąsiada, to przeskakiwaniu do niego. Taki algorytm nie daje jeszcze dobrych rezultatów, ale jego stosunkowo niewielka modyfikacja już tak. Symulowane wyżarzanie pozwala na przeskakiwanie do sąsiadów o gorszej funkcji celu z pewnym prawdopodobieństwem (malejącym z czasem oraz z rosnącą różnicą między obiektami).

Rozmnażanie płciowe też stosunkowo łatwo zinterpretować jako obliczenie. Powstało wiele algorytmów genetycznych stosujących schemat wzięty żywcem z ewolucji organizmów rozmnażających się płciowo. Działają one następująco. Najpierw losowana jest pewna pula obiektów, jest to pierwsze pokolenie. Następnie w pętli realizowana jest procedura: (1) wybierz z populacji pewien odsetek obiektów o najlepszych wynikach, pozostałe usuń; (2) wylosuj z populacji dwa obiekty i skrzyżuj je, powtórz to tyle razy, ile ma być obiektów w nowym pokoleniu; (3) każdy z obiektów w nowym pokoleniu trochę zmodyfikuj z pewnym prawdopodobieństwem (odpowiednik mutacji); (4) usuń obiekty ze starego pokolenia.

Wydawałoby się, że podobnie jak w przyrodzie, tak i w informatyce algorytmy genetyczne powinny działać dużo lepiej niż algorytmy lokalnego przeszukiwania. I tu niespodzianka! Christos Papadimitriou, znana postać współczesnej informatyki, twierdzi, że w praktycznych zastosowaniach lokalne wyszukiwanie, a w szczególności symulowane wyżarzanie działają dobrze, podczas gdy algorytmy genetyczne nie radzą sobie. Niektórzy naukowcy twierdzą inaczej, nie będziemy się jednak starali rozwikłać tej zagadki, tylko pójdziemy tropem rozumowania Papadimitriou. A więc pytanie brzmi - dlaczego? Jak to możliwe, żeby w biologii ten sam mechanizm działał dobrze, a w informatyce źle?

Odpowiedź jest zupełnie zadziwiająca! A co, jeśli ewolucja w biologii ma co innego na celu niż algorytmy ewolucyjne w informatyce? Algorytm genetyczny dąży do znalezienia obiektu o najlepszym wyniku. Wielu sądzi, że ewolucja ma na celu stworzenie najlepiej przystosowanego do środowiska super-osobnika. Po chwili zastanowienia Czytelnicy zapewne zgodzą się, że ten utarty pogląd wcale nie jest oczywisty. Super-osobnik byłby bowiem idealny dla pewnego ustalonego środowiska, ale mógłby nie być odporny na jego zmiany. Co więc właściwie optymalizuje ewolucja? Wydaje się, że stara się stworzyć jakąś stabilną, odporną populację. Tylko co to konkretnie znaczy? To już zupełnie inna historia - i chyba jeszcze nie do końca zrozumiana przez naukę. I pewnie jeszcze daleko naukowcom (biologom, matematykom, informatykom), żeby dobrze zrozumieć, o co naprawdę chodzi w ewolucji.