• Artykuły
  • Forum
  • Ciekawostki
  • Encyklopedia
  • Pożytki z naśladowania ewolucji

    09.08.2010. 17:59
    opublikowane przez: Jakub Juranek

    Algorytm genetyczny, naśladujący mechanizmy zachodzące w procesach ewolucji, pomógł naukowcom w doborze optymalnej formy aktywacji elektrycznej generowanej przez implanty stosowane w stymulacji układu nerwowego. Rozwiązanie to pozwoli w przyszłości na tworzenie bardziej energooszczędnych stymulatorów, co umożliwi zmniejszenie częstotliwości zabiegów operacyjnych związanych z koniecznością wymiany baterii w implantach.

    Implanty nerwowe w postaci stymulatorów, są urządzeniami pomagającymi w leczeniu szeregu chorób neurologicznych, w tym niektórych przypadków epilepsji i choroby Parkinsona. Pomimo nieocenionej roli, jaką pełnią one w polepszeniu funkcjonowania pacjentów dotkniętych tymi schorzeniami, obecnie stosowana w nich technologia nie jest pozbawiona wielu wad, z których jedną z najpoważniejszych jest, prozaiczna na pozór, kwestia wyczerpywania się źródeł zasilania. Wymiana baterii, lub - w niektórych przypadkach - całego urządzenia, wiąże się inwazyjnymi zabiegami operacyjnymi, których uciążliwość jest tym większa, im częściej muszą one mieć miejsce.

    Poszukując rozwiązania tego problemu Amorn Wongsarnpigoon i Warren Grill z Uniwersytetu Duke’a w Durham zastosowali oprogramowanie imitujące niektóre mechanizmy naturalnej ewolucji, którego użyli do wyboru kształtu optymalnego rodzaju elektrycznej stymulacji neuronów. Ich celem było odnalezienie rozwiązania pozostającego równie efektywnym w aktywacji komórek mózgowych, jak obecnie stosowane wzory, jednocześnie pozwalającego zoptymalizować zużycie energii przez stymulator, tym samym przedłużając żywotność jego baterii i wydłużając interwał pomiędzy kolejnymi operacjami ich wymiany.

    Dotychczas dobór amplitudy i czasu impulsacji implantów, oparty był na wzorcach, które wykorzystywały, niecałkowicie realistyczne, pasywne modele błony komórkowej. Wskazywały one, że najbardziej optymalna stymulacja ma kształt rosnącej wykładniczo fali. Badania, w których zastosowano bardziej realistyczne modele błon neuronalnych oraz badania na komórkach nerwowych in vivo, nie potwierdziły jednakże, że taki kształt stymulacji, jest w jakiś szczególny sposób bardziej energooszczędny i efektywny, od innych rozwiązań, przykładowo fali opadającej czy pulsacji o kształcie kwadratowym.

    Optymalizacja stymulacji przy użyciu modeli wykorzystujących realistyczną charakterystykę błony komórkowej, jest jednak znacznie trudniejszym zadaniem. Nie może być ona przeprowadzona analitycznie, ze względu na poziom komplikacji oraz nielinearność odpowiednich równań. Zastosowanie metody "prób i błędów" zaś, jest praktycznie wykluczone, ze względu na nieskończoną ilość kombinacji możliwego kształtu produkowanej aktywacji. W obliczu powyższych trudności, jednym z najlepszych sposobów poszukiwania odpowiedniego rozwiązania, okazują się algorytmy globalnej optymalizacji, z których, w tym konkretnym przypadku, zastosowano algorytm genetyczny.

    Na wzór procesów ewolucyjnych, kolejne kształty fal, potraktowane zostały jak organizmy, których szczegółowe parametry (w postaci amplitudy w danym momencie czasowym), służyły jako jednostki dziedziczenia, czyli swoiste "geny". Każde "pokolenie" rozwiązań, poczynając od pierwszego, wyłonionego losowo, testowane było przy użyciu tak zwanej funkcji kosztu, będącej sumą energii konsumowanej przez każdy kształt stymulacji, oraz funkcji kary, obliczanej, gdy stymulacja nie zdołała wywołać potencjału czynnościowego we włóknie nerwowym. Po każdorazowym teście, rozwiązania "kojarzyły" się ze sobą, co skutkowało wytworzeniem rozwiązań potomnych, łączących w sobie różne kombinacje parametrów, czyli "genów", rozwiązań rodzicielskich. Dodatkowo, w kolejnym pokoleniu pojawiały się pewne oryginalne cechy wynikające z mutacji, która także stanowiła część zaprogramowanego algorytmu. Kolejne testowane kohorty, składały się każdorazowo z 50 rozwiązań, z których 10 najlepszych przechodziło do kolejnego pokolenia, resztę zaś stanowiły wygenerowane rozwiązania potomne, które mogły pochodzić od każdego z rozwiązań poprzedzającego pokolenia, niezależnie od wartości funkcji kosztu, jaki ono uzyskało.

    Swoista "hodowla" najlepszego kształtu stymulacji nerwów, prowadzona była przez 10 000 pokoleń rozwiązań, w 5 niezależnych symulacjach, różniących się wygenerowanymi wyjściowymi kształtami impulsacji. Ostatecznie, proces ten doprowadził do wygenerowania jako optymalnej, formy stymulacji o kształcie zbliżonym do skróconej krzywej normalnej. Otrzymane rozwiązanie zostało przetestowane empirycznie, nie tylko przy użyciu oprogramowania symulującego nerwy, ale także in vivo, przy stymulacji nerwu kulszowego u kota, wykazując rzeczywistą przewagę nad rozwiązaniami proponowanymi przez inne modele.

    Chociaż testowane ukształtowanie impulsacji dotyczyło, na obecnym etapie, aktywacji peryferycznych włókien nerwowych, naukowcy mają nadzieję, że użyty przez nich algorytm genetyczny, oraz wypracowane przez niego rozwiązania znajdą zastosowanie także w urządzeniach do stymulacji innych części układu nerwowego, w tym także kory mózgowej. Według ich szacunków, użycie kształtów impulsacji elektrycznej wygenerowanych przez algorytm genetyczny, na przykład do głębokich implantów domózgowych, może wydłużyć czas ich funkcjonowania od 5 do 60 procent, co, biorąc pod uwagę ich obecny okres działania, może zwiększyć czas pracy tych urządzeń od 2 do 21 miesięcy, to z kolei, może zmniejszyć częstotliwość operacji wymiany baterii, w ciągu 30 lat, z obecnych 10, do zaledwie 5-6 razy, wydatnie obniżając ryzyko i dyskomfort jaki wiąże się z tego typu zabiegami dla pacjentów.

    Więcej informacji na ten temat (w języku angielskim) można znaleźć na stronie magazynu New Scientist, pod tym adresem: http://www.newscientist.com/article/dn19148-darwinian-algorithm-cuts-the-need-for-surgery.html

    Źródło:
    Wongsarnpigoon, A. i Grill, W. M. (2010). Energy-efficient waveform shapes for neural stimulation revealed with a genetic algorithm. Journal of Neural Engineering, 7. doi:10.1088/1741-2560/7/4/046009

    Czy wiesz ĹĽe...? (beta)
    Heurystyka (gr. heuresis – odnaleźć, odkryć, heureka – znalazłem) - w informatyce metoda znajdowania rozwiązań, dla której nie ma gwarancji znalezienia rozwiązania optymalnego, a często nawet prawidłowego. Rozwiązań tych używa się np. wtedy, gdy pełny algorytm jest z przyczyn technicznych zbyt kosztowny lub gdy jest nieznany (np. przy przewidywaniu pogody lub przy wykrywaniu niektórych zagrożeń komputerowych, takich jak wirusy lub robaki). Metody używa się też często do znajdowania rozwiązań przybliżonych, na podstawie których później wylicza się ostateczny rezultat pełnym algorytmem. To ostatnie zastosowanie szczególnie dotyczy przypadków, gdy heurystyka jest wykorzystywana do nakierowywania pełnego algorytmu ku optymalnemu rozwiązaniu, aby zmniejszyć czas działania programu w typowym przypadku bez poświęcania jakości rozwiązania (np. algorytm A*). Teoria perturbacji (nazywana też rachunkiem zaburzeń) jest zbiorem metod matematycznych, które są używane do znalezienia przybliżonego rozwiązania problemu, który nie może być rozwiązany w sposób ścisły, dostarczając bezpośrednie rozwiązanie problemu. Teoria perturbacji może być zastosowana do rozwiązania problemu, gdy można go przedstawić jako część dającą bezpośrednie rozwiązanie i stosunkowo mały człon zaburzający. Algorytm zachłanny (ang. greedy algorithm) – algorytm, który w celu wyznaczenia rozwiązania w każdym kroku dokonuje zachłannego, tj. najlepiej rokującego w danym momencie wyboru rozwiązania częściowego. Innymi słowy algorytm zachłanny nie dokonuje oceny czy w kolejnych krokach jest sens wykonywać dane działanie, dokonuje decyzji lokalnie optymalnej, dokonuje on wyboru wydającego się w danej chwili najlepszym, kontynuując rozwiązanie podproblemu wynikającego z podjętej decyzji. Typowe zadanie rozwiązywane metodą zachłanną ma charakter optymalizacyjny. W dziedzinie sztucznej inteligencji zachłanna odmiana przeszukiwania lokalnego jest nazywana "podchodzeniem pod wzgórze".

    Rozwiązania Mie - dokładne rozwiązanie problemu rozpraszania światła na sferycznych cząstkach w postaci nieskończonego, ale zbieżnego szeregu. Rozwiązania Mie dają informacje o ilości promieniowania zaabsorbowanego lub rozproszonego przez cząstkę. Właściwości rozproszeniowe cząstki obliczone zgodnie z tym rozwiązaniem noszą kolokwialną (ale nieprawidłową) nazwę rozpraszanie Mie. Algorytm genetyczny - rodzaj algorytmu przeszukującego przestrzeń alternatywnych rozwiązań problemu w celu wyszukania rozwiązań najlepszych.

    Mutacja - operator przeszukiwania przestrzeni rozwiązań za pomocą algorytmu ewolucyjnego. Polega na losowej zmianie wartości niektórych (lub wszystkich) genów reprezentujących osobnika. Ma ona za zadanie zwiększyć różnorodność osobników w populacji, czyli zapobiegać przedwczesnej zbieżności algorytmu oraz eksplorować przestrzeń rozwiązań. Mutacja zachodzi z pewnym przyjętym prawdopodobieństwem - zazwyczaj rzędu 1%. Jest ono niskie, ponieważ zbyt silna mutacja przynosi efekt odwrotny do zamierzonego: zamiast subtelnie różnicować dobre rozwiązania - niszczy je. Stąd w procesie ewolucji mutacja ma znaczenie drugorzędne, szczególnie w przypadku długich chromosomów. Może być zarówno operatorem lokalnym (jak w algorytmach genetycznych), jak i operatorem globalnym (jak w strategiach ewolucyjnych). Algorytm z nawrotami (ang. backtracking) – ogólny algorytm wyszukiwania wszystkich (lub kilku) rozwiązań niektórych problemów obliczeniowych, który stopniowo generuje kandydatów na rozwiązanie jednak, gdy stwierdzi, że znaleziony kandydat c nie może być poprawnym rozwiązaniem, nawraca (ang. "backtracks") do punktu, gdzie może podjąć inną decyzje związaną z jego budową.

    Programowanie zstępujące (projektowanie zstępujące) (ang. top-down design) - rozwiązanie programistyczne polegające na zdefiniowaniu problemu ogólnego poprzez podzielenie na podproblemy, które są dzielone na jeszcze mniejsze podproblemy aż do rozwiązań oczywistych, łatwych do zapisania. Następnie złożenie z rozwiązań podproblemów niższego rzędu rozwiązań problemów wyższego rzędu aż do całkowitego rozwiązania problemu. Negocjacje – dwustronny proces komunikowania się, którego celem jest osiągnięcie porozumienia, gdy przynajmniej jedna strona nie zgadza się z daną opinią lub z danym rozwiązaniem sytuacji. Negocjacje to sposób porozumienia się w celu rozwiązania konfliktu oraz dojścia do porozumienia obydwu stron, proces wzajemnego poszukiwania takiego rozwiązania, które satysfakcjonowałoby zaangażowane w konflikt strony.

    Poradnictwo obywatelskie – polega na informowaniu ludzi (w formie indywidualnej lub grupowej) o przysługujących im prawach oraz spoczywających na nich obowiązkach, w zakresie istotnym dla rozwiązania jego problemu oraz pomoc w wyborze optymalnego rozwiązania.

    Neurostymulator (ang. neurostimulator) – jest zasilanym przez baterię urządzeniem zaprojektowanym w celu elektrycznej stymulacji mózgu. Neurostymulatory są integralną częścią chirurgicznie wszczepianych układów takich jak urządzenie do głębokiej stymulacji mózgu (DBS) czy urządzenie do stymulacji nerwu błędnego (VNS), wykorzystywanych w leczeniu chorób układu nerwowego.

    Wzór użytkowy – nowe i użyteczne rozwiązanie o charakterze technicznym, dotyczące kształtu, budowy i zestawienia przedmiotu o trwałej postaci, przy czym użyteczność takiego rozwiązania wyraża się możliwością osiągnięcia celu mającego praktyczne znaczenie przy wytwarzaniu lub korzystaniu z wyrobu o cechach wzoru użytkowego. Własność optymalnej podstruktury – jest własnością problemów, które można rozwiązywać za pomocą algorytmów. Mówi się, że dany problem ma własność optymalnej podstruktury, jeżeli jego optymalne rozwiązanie jest funkcją optymalnych rozwiązań podproblemów.

    Metaheurystyka - ogólny algorytm (heurystyka) do rozwiązywania problemów obliczeniowych. Algorytm metaheurystyczny można używać do rozwiązywania dowolnego problemu, który można opisać za pomocą pewnych definiowaych przez ten algorytm pojęć. Najczęściej wykorzystywany jest jednak do rozwiązywania problemów optymalizacyjnych. Określenie powstało z połączenia słowa "meta" ("nad", tutaj w znaczeniu "wyższego poziomu") oraz słowa "heurystyka" (gr. heuriskein - szukać), co wynika z faktu, że algorytmy tego typu nie rozwiązują bezpośrednio żadnego problemu, a jedynie podają sposób na utworzenie odpowiedniego algorytmu. Termin "metaheurystyka" po raz pierwszy został użyty przez Freda Glovera w 1986 roku. Przeszukiwanie tabu: Procedura (algorytm) (Tabu search - TS) stosowana do rozwiązywania problemów optymalizacyjnych. Wykorzystywana do otrzymywania rozwiązań optymalnych lub niewiele różniących się od niego dla problemów z różnych dziedzin (np. planowanie, planowanie zadań). Podstawową ideą algorytmu jest przeszukiwanie przestrzeni, stworzonej ze wszystkich możliwych rozwiązań, za pomocą sekwencji ruchów. W sekwencji ruchów istnieją ruchy niedozwolone, ruchy tabu. Algorytm unika oscylacji wokół optimum lokalnego dzięki przechowywaniu informacji o sprawdzonych już rozwiązaniach w postaci listy tabu (TL). Twórcą algorytmu jest Fred Glover.

    Dodano: 09.08.2010. 17:59  


    Najnowsze