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.