Uniwersytet Śląski w Katowicach
Wydział Informatyki i Nauki o Materiałach

Sztuczna Inteligencja

Temat:

Algorytmy ewolucyjne

Opracowali:

Piotr Gacek

Paulina Giereś

Ewelina Kania

Maciej Niewiński

Inżynieria biomedyczna rok III, OM1

Genetyka - uogólniając jest to nauka dziedziczności i zmienności organizmów, które są oparte
na informacji zawartej w podstawowych jednostkach dziedziczności czyli genach.


Zarys historyczny genetyki:

Pierwsze próby wyjaśnienia przyczyn dziedziczenia opierały się na teorii zapatrzenia dziś
uznawanej za błędną. Inne koncepcje wiązały dziedziczenie z krwią. Wiedza, iż istoty żywe
dziedziczą cechy po swoich rodzicach była stosowana od czasów prehistorycznych w celu
poprawy wielkości plonów oraz uzyskiwania lepszych odmian zwierząt poprzez hodowlę
selektywną.

Nowoczesna genetyka stara się zrozumieć proces dziedziczenia, a za jej prekursora uważa się
niemiecko-czeskiego zakonnika i naukowca Grzegorza Mendla, który w 1866 roku po raz
pierwszy opisał podstawowe prawa dziedziczenia cech. W swoich dokumentach "Versuche über
Pflanzenhybriden" ("Eksperymenty krzyżowania roślin") zaprezentowanych w 1865 roku
Stowarzyszeniu Badań Natury (Naturforscher Verein) w Brnie, Mendel naszkicował modele
dziedziczenia pewnych cech w oparciu o groch zwyczajny i opisał je matematycznie.

W czasach Mendla podstawową teorią dziedziczenia była teoria mieszanego dziedziczenia.
Polega ona na tym, że jednostki dziedziczą różny kompleks cech po swoich rodzicach. Prace
Mendla obaliły tą teorię pokazując, że cechy są raczej kombinacją różnych genów niż stałym
ich kompleksem. Inna teoria, która ówcześnie była dość popularna, mówiła o dziedziczeniu
przyswojonych cech, tj. jednostki dziedziczą cechy wzmocnione przez ich rodziców. Teoria ta
(zazwyczaj kojarzona z Jean-Baptiste de Lamarck) jest obecnie uważana za nieprawdziwą –
doświadczenia jednostek nie mają wpływu na geny, które dziedziczą ich dzieci. Inne teorie to
pangeneza Charlesa Darwina (która mówi o obu – nabytych i dziedziczonych cechach) i jej
ponowne ujęcie pangenezy Francisa Galtona.

Rezultaty prac Mendla nie były rozumiane do czasu jego śmierci, kiedy to inni naukowcy
pracujący nad podobnymi zagadnieniami ponownie odkryli jego badania. William Bateson
orędownik pracy Mendla wymyślił w 1905 roku słowo "genetyka". Spopularyzował on użycie
tego słowa, aby opisać badanie dziedziczenia w inauguracyjnej odezwie na Trzecią
Międzynarodową Konferencję Krzyżowania Roślin w Londynie (The Third International
conference on Plant Hybrydization in London) w 1906 roku. Po ponownym odkryciu prac
Mendla naukowcy starali się określić, które molekuły w komórkach były odpowiedzialne za
dziedziczenie. W 1910 roku Thomas Hunt Morgan, bazując na obserwacjach udowodnił, że
geny mają związek z chromosomami. W 1913 roku jego student Alfred Sturtevant użył
fenomenu genetycznego łączenia, aby pokazać, że geny są rozmieszczone liniowo na
chromosomach.

Algorytm genetyczny jest to rodzaj algorytmu, który przeszukuje przestrzeń alternatywnych

rozwiązań danego problemu po to,aby znaleźć najlepsze rozwiązanie. Sposób działania

algorytmów genetycznych nieprzypadkowo przypomina zjawisko ewolucji biologicznej,

ponieważ ich twórca John Henry Holland właśnie z biologii czerpał inspiracje do swoich prac.

Obecnie zalicza się go do grupy algorytmów ewolucyjnych. Zatem można stwierdzić, że

algorytmy genetyczne służą głównie do tego, żeby rozwiązywać zadania optymalizacji.

Najczęściej działanie algorytmu przebiega następująco:

▪

Losowana jest pewna populacja początkowa.

▪

Populacja poddawana jest ocenie (selekcja). Najlepiej przystosowane osobniki biorą

udział w procesie reprodukcji.

▪

Genotypy wybranych osobników poddawane są operatorom ewolucyjnym:

▪

są ze sobą kojarzone poprzez złączanie genotypów rodziców (krzyżowanie),

▪

przeprowadzana jest mutacja, czyli wprowadzenie drobnych losowych zmian.

▪

Rodzi się drugie (kolejne) pokolenie. Aby utrzymać stałą liczbę osobników w populacji

te najlepsze (według funkcji oceniającej fenotyp) są powielane, a najsłabsze usuwane.

Jeżeli nie znaleziono dostatecznie dobrego rozwiązania, algorytm powraca do kroku

drugiego. W przeciwnym wypadku wybieramy najlepszego osobnika z populacji - jego

genotyp to uzyskany wynik.

▪

Działanie algorytmu genetycznego obejmuje kilka zagadnień potrzebnych do ustalenia:

─

ustalenie genomu jako reprezentanta wyniku,

─

ustalenie funkcji przystosowania/dopasowania,

─

ustalenie operatorów przeszukiwania.

Zastosowanie algorytmów genetycznych:

▪

Rozwiązywanie problemów NP :
Algorytmy genetyczne znajdują zastosowanie tam, gdzie nie jest dobrze określony lub

poznany sposób rozwiązania problemu, ale znany jest sposób oceny jakości

rozwiązania. Przykładem jest np. problem komiwojażera, gdzie należy znaleźć

najkrótszą drogę łączącą wszystkie miasta, tak by przez każde miasto przejść tylko raz.

Ocena jakości proponowanej trasy jest błyskawiczna, natomiast znalezienie optymalnej

trasy kwalifikuje się do klasy problemów NP-trudnych. Przy zastosowaniu podejścia

ewolucyjnego dobre rozwiązanie można znaleźć bardzo szybko, ale oczywiście pewni

możemy być jedynie uzyskania rozwiązań sub-optymalnych, co wynika z formalnie

opisanej trudności problemów klasy NP. Algorytmy genetyczne równie dobrze radzą

sobie w znajdowaniu przybliżeń ekstremów funkcji, których nie da się obliczyć

analitycznie.

▪

Projektowanie genetyczne
Algorytmy genetyczne wykorzystywane są również do zarządzania populacją sieci

neuronowych. Projektowanie maszyn bądź obwodów elektrycznych jest doskonałym

polem dla wykazania się algorytmów genetycznych. Inżynierowi podczas tworzenia

nowych pomysłów nie chodzi o znalezienie najlepszego możliwego rozwiązania.

Wystarczy tylko przybliżone spełnienie granicznych warunków oraz optymalizacja

projektu. Algorytmy genetyczne w odróżnieniu od człowieka nie działają

schematycznie. Program nie zna wcześniejszych projektów i dlatego czasami wykazuje

się pewną inwencją. Co więcej człowiek często opiera się na bardzo przybliżonych

modelach, które dają fałszywy obraz problemu. Algorytm genetyczny może

przeanalizować złożony model / zagadnienie i znaleźć rozwiązanie, na które człowiek

by nie wpadł.

▪

Przeszukiwanie
Algorytmy genetyczne zapewniają skuteczne mechanizmy przeszukiwania dużych

przestrzeni rozwiązań. Ponieważ grupowanie należy do tej kategorii zadań to oczywiste

jest, że algorytmy genetyczne stosowane są w grupowaniu. Algorytmy genetyczne są

bardziej niezależne od wstępnej inicjalizacji oraz mniej skłonne do znajdowania

lokalnych rozwiązań w miejsce optymalnych. Przykładem może być zagadnienie

grupowania w którym w miejsce klasycznych algorytmów z powodzeniem stosuje się

algorytmy genetyczne.

▪

Projektowanie obwodów elektrycznych
Algorytmy genetyczne można wykorzystać do projektowania obwodów elektrycznych.

Ocena każdego osobnika opiera się na ilości elementów oraz własnościach

elektrycznych, które łatwo jest obliczyć. Główna różnica tkwi w algorytmie budowy

osobnika na podstawie genomu. Ma on postać instrukcji dla programu, który na jego

podstawie buduje obwód elektryczny. Najpierw mamy proste połączenie wejścia z

wyjściem. Następnie program dodaje i usuwa połączenia i elementy. Zbudowany tak

obwód jest oceniany na podstawie prostych zależności fizycznych. Podobny algorytm

genetyczny zbudował samodzielnie filtr drabinkowy.

Optymalizacja - wyznaczenie spośród dopuszczalnych rozwiązań danego problemu rozwiązania

najlepszego za względu na przyjęte kryterium (wskaźnik) jakości (np. koszt, zysk,

niezawodność).

Algorytm ewolucyjny - algorytm wzorowany na biologicznej ewolucji, stosowany do zadań

optymalizacyjnych i modelowania.

Podział:

▪

Algorytmy genetyczne

▪

Programowanie genetyczne

▪

Programowanie ewolucyjne

▪

Przeszukiwanie rozproszone

▪

Strategie ewolucyjne

▪

Neuroewolucje (Neuroevolution)

Strategie ewolucyjne to popularna metoda ewolucyjna. Główny obszar zastosowań to

optymalizacja

funkcji

rzeczywistych

wielowymiarowych.

W

przypadku

algorytmów

genetycznych zakodowanie parametrów liczbowych wymaga ustalenia liczby bitów, co

ogranicza nam dokładność obliczeń. W przypadku strategii ewolucyjnych kod genetyczny

składa się po prostu z liczb zmiennoprzecinkowych (o precyzji limitowanej tylko przez

używany język programowania), co znacznie ułatwia kodowanie problemu i poprawia

dokładność końcowego rozwiązania.

Heurystyka – 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*).

Dwie naczelne zasady heurystyki informacyjnej to:

● zasada wyczerpania (kompletności)
● zasada właściwego doboru materiału (relewantności)

Chromosom - miejsce przechowywania genotypu osobnika.

Fenotyp - ujawniające się “na zewnątrz” cechy danego osobnika. W przypadku algorytmów

ewolucyjnych są to te parametry (cechy) rozwiązania, które podlegają ocenie.

Genotyp - “plan konstrukcyjny”, kompletny i jednoznaczny opis osobnika zawarty w jego

genach. W przypadku algorytmów ewolucyjnych cechy rozwiązania (punktu z przestrzeni

stanów) kodowane są w określony sposób, np. za pomocą ciągów binarnych ustalonej długości

(odpowiednikiem genotypu osobnika jest w tym przypadku ciąg bitów).

Krzyżowanie wymiana części genotypu między dwoma osobnikami. Przykładowy sposób

zastosowania operatora krzyżowania:

Działanie operatora krzyżowania:
a) krzyżowanie jednopunktowe (one-point crossover),
b) krzyżowanie dwupunktowe (two-point crossover).

Mutacja - niewielka, losowa zmiana genotypu danego osobnika.


Działanie operatora mutacji:

Przykładowy sposób zastosowania operatora mutacji:

Locus– określony obszar chromosomu zajmowany przez gen. W obrębie chromosomu znajduje

się wiele różnych loci, stanowią one rodzaj logicznych pojemników na samodzielne,

strukturalizowane fragmenty informacji genetycznej, nazywane genami. W określonym locus

mogą się znaleźć różne warianty związanego z nim genu (różniące się sekwencją nukleotydów

w DNA); warianty te są nazywane allelami.

Gen to podstawowa jednostka dziedziczności determinująca powstanie jednej cząsteczki

białka

lub

kwasu

rybonukleinowego

zapisana

w

sekwencji

nukleotydów

kwasu

deoksyrybonukleinowego.