Algorytmy mrówkoweWykład poświęcony jest algorytmom mrówkowym - zrandomizowanej metodzie optymalizacji, inspirowanej obserwacjami przyrodniczymi. Drugi temat obejmuje metodę nietypową, bo realizowaną sprzętowo: jest to technologia wykorzystująca mechanizmy biochemiczne (cząsteczki DNA) do rozwiązywania problemów kombinatorycznych.
Algorytmy mrówkoweObserwacje biologiczne będące inspiracją powstania algorytmów mrówkowych (rozpowszechnionych od lat 90-tych) dotyczą społecznego zachowania mrówek i ich "inteligencji zespołowej": gdy wysłane na poszukiwanie pożywienia mrówki znajdą pokarm, w krótkim czasie wskazują innym mrówkom drogę do niego. Tworzą się ścieżki łączące pożywnienie z mrowiskiem, przy czym spośród wielu początkowych ścieżek po pewnym czasie pozostaje tylko najkrótsza.
Przyczyną takiej optymalizacji jest mechanizm komunikowania się mrówek. Mrówki wykorzystują do komunikacji feromony, czyli substancje zapachowe wyznaczające m.in. ścieżki prowadzące do pożywienia. Mrówki podążają śladem tych, którym się powiodło w poszukiwaniach, czasem (losowo) zbaczając z drogi i szukając nowych możliwości. Optymalizacja długości ścieżki wynika z tego, że krótsza droga do pożywienia oznacza częstsze odkładanie się feromonu (więcej mrówek zdąży nią przejść), co z kolei powoduje zwabienie jeszcze większej liczby mrówek itd. Krótkie ścieżki ulegają więc wzmocnieniu.
Algorytm mrówkowy wzorowany na powyższym zjawisku działa nastepująco:
Populacja niezależnych "agentów" buduje rozwiązanie (każdy swoje) w kolejnych, losowych krokach, w sposób przypominający algorytm zachłanny. Rozwiązania są oceniane, po czym wszystkie elementy ścieżki prowadzącej do danego rozwiązania są oznaczane "feromonem" (zwiększamy ich wagę) proporcjonalnie do jakości rozwiązania. Kolejne pokolenia agentów wybierają daną ścieżkę tym chętniej, im więcej jest na niej feromonu. Realizowane jest to poprzez zwiększenia prawdopodobieństwa losowego wybrania wyżej ocenianej ścieżki.
Przykład: Problem komiwojażera.
Głównym obszarem praktycznego zastosowania algorytmów mrówkowych są problemy zbliżone do problemu komiwojażera - wszelkiego rodzaju optymalizacje związane z transportem. Zasada działania algorytmu to błądzenie losowe połączone ze sprężeniem zwrotnym (wzmocnieniem części rozwiązań, które okazały się udane). Przyjmujemy tu milczące założenie, że części dobrego rozwiązania mogą być w przyszłości wykorzystane w jeszcze lepszych rozwiązaniach.
Obliczenia na DNAObliczenia na DNA są nowatorską techniką sprzętowo-algorytmiczną pozwalającą na wykorzystanie pewnych wygodnych własności nici DNA do przeprowadzania obliczeń (rozwiązywania problemów kombinatorycznych). Przesłanką do eksperymentów z komputerami DNA jest fakt, że dzięki postępom biochemii jesteśmy w stanie wyprodukować w krótkim czasie cząstki DNA o dokładnie ustalonej sekwencji nukleotydów (w dodatku w makroskopowych ilościach - np. całą próbówkę). Cząstki DNA mają bardzo wygodne cechy obliczeniowe - mogą się łączyć ze sobą tylko według pewnych ścisłych reguł (nukleotydy A łączą się z T, a G łączą się z C). Dysponujemy również zaawansowanymi technologiami analitycznymi, pozwalającymi wykrywać cząstki o ustalonych cechach.
Załóżmy, że mamy problem kombinatoryczny, którego rozwiązanie wymaga przejrzenia wielkiej liczby możliwości w celu znalezienia rozwiązania o podanych cechach (np. ścieżki Hamiltona w grafie, czyli takiej ścieżki, która dokładnie raz przechodzi przez wszystkie wierzchołki grafu - sprawdzenie istnienia takiej ścieżki jest problemem NP-zupełnym). Zasada działania komputera DNA jest nastepująca:
Przykład: Sprawdzenie, czy w grafie istnieje ścieżka Hamiltona.
Kodujemy wierzchołki i krawędzie jako sekwencje specyficznych zasad, przy czym umożliwiamy łączenie się tylko tych sekwencji, które kodują wierzchołki połączone krawędzią (np. wierzchołki ACC-AAA oraz CAC-ACA mogą być połączone krawędzią TTT-GTG - por. schemat poniżej). Każda dłuższa nić koduje więc pewną ścieżkę w grafie - wystarczy teraz znaleźć nić właściwej długości.
Zasada działania obliczeń na DNA to masywna równoległość połączona z losowym przeszukiwaniem przestrzeni stanów. Entuzjaści obliczeń na DNA wskazują na (teoretycznie) ogromne moce obliczeniowe ukryte w niewielkich objętościowo i oszczędnych energetycznie urządzeniach, pesymiści wskazują na kłopotliwość przeprowadzania obliczeń i wymagany sprzęt dodatkowy. Faktem jest, że komputery DNA bardziej przypominają laboratorium biochemiczne, niż znane z codziennej pracy PC. Warto też podkreślić, że nawet powszechne stosowanie komputerów DNA nie będzie cudownym środkiem na wszelkie problemy obliczeniowe: problemy o wykładniczej złożoności nadal będą rosły szybciej, niż nasze możliwości sprzętowe.
Wykład omawia dwie techniki obliczeniowe inspirowane biologią. Pierwsza z nich opiera się na zasadzie wykorzystywanej przez kolonię mrówek do optymalizacji tras zbierania pokarmu. Jest to metoda wzmacniania tych części rozwiązania, które są fragmentami dobrze ocenianych rozwiązań (co powoduje dodatnie sprzężenie zwrotne i dalszą optymalizację rozwiązań).
Druga metoda wykorzystuje rzeczywiste (sztucznie wytworzone) cząstki DNA do rozwiązywania problemów kombinatorycznych. Obecnie eksperymentalne komputery DNA potrafią rozwiązywać zadania niewielkich rozmiarów (możliwe do dokładnego rozwiązania w sposób klasyczny).
Zalecana literatura:
Szczegółowe definicje znajdują się w treści wykładu (słowa kluczowe zaznaczone są na czerwono).
algorytmy mrówkowe - randomizowana metoda optymalizacji polegająca na stopniowym wzmacnianiu komponentów dobrych rozwiązań
komputery DNA - rozwiązania techniczne umożliwiające prowadzenie obliczeń na DNA
obliczenia na DNA - sprzętowo-algorytmiczna metoda obliczeniowa, wykorzystująca fizyczne własności DNA do rozwiązywania problemów kombinatorycznych
Strona uaktualizowana przez Sinh Hoa Nguyen, 2009