Teorie algorytmów genetycznych

Historia



Podstawowy algorytm

genetyczny został
wprowadzony przez Johna
Hollanda(Uniwersytet
Michigan) i rozwinięty dzięki
jego pracom z lat 60 i 70.

• Algorytmy genetyczne wykorzystują

mechanizmy naturalnej ewolucji
(selekcja,

przetrwanie osobników najlepiej

przystosowanych, reprodukcja)

• Idea krzyżowania i mutacji

chromosomów.

• W symulacjach ewolucji chromosomy

reprezentowane są przez ciągi binarne

Terminy genetyczne i ich
odpowiedniki w algorytmach
genetycznych

Genetyka

Algorytmy

genet.

chromosom

Ciąg kodowy

gen

Cecha,znak

allel

Wariant cechy

locus

pozycja

genotyp

struktura

fenotyp

Rozwiązanie,pu

nkt

Cele badania algorytmów
genetycznych:



-opisanie i wyjaśnienie w sposób
ścisły istoty procesów adaptacyjnych
występujących w świecie przyrody



-stworzenie na użytek systemów
konstruowanych przez człowieka
oprogramowania,które odtwarzałoby
podstawowe mechanizmy rządzące
systemami biologicznymi



ODPORNOŚĆ jako centralny temat w
badaniach dotyczących algorytmów
genetycznych



Kompromis między efektywnością a
skutecznością konieczną do przeżycia w
różnorodnych środowiskach



System odporny technicznie:

-zaoszczędzenie na kosztownych

przeróbkach

-lepsze i dłuższe funkcjonowanie systemów



Odporność,wydajność i łatwość
przystosowania się systemów
biologicznych



Zdolność do
regeneracji,samosterowania i
reprodukcji tylko w świecie
biologii,nieobecna w świecie techniki



Tam,gdzie odporność jest cechą
pożądaną,przyroda radzi sobie lepiej

Co to są algorytmy
ewolucyjne?



Algorytm genetyczny -

rodzaj algorytmu
przeszukującego przestrzeń
alternatywnych rozwiązań
problemu w celu wyszukania
rozwiązań najlepszych



Algorytmy genetyczne są to

algorytmy optymalizacyjne,
których zasady działania
oparte są na mech. znanych
już od stuleci a mianowicie na
mech. Doboru naturalnego i
dziedziczności.

Przykład



Chcemy kupić auto ale nie wiemy jakie.Mamy wiele
samochodów do wybrania, a każdy z nich ma wiele
parametrów i właściwości.Naszym celem jest kupno auta na
naszą kieszeń i mamy konkretne wymagania.

Przestrzeń poszukiwań

Co chcemy osiągnąć przez
optymalizację?

„Dążenie człowieka do perfekcji znajduje

swój wyraz w teorii optymalizacji.Zajmuje
się ona tym,jak opisać i osiągnąć
Najlepsze,gdy wiemy już,jak mierzyć i
zmieniać Dobre i Złe”

(Beightler,Philips,Wilde,1979)

Cel optymalizacji:
Zwiększenie efektywności aż do osiągnięcia

pewnego optimum

Idea algorytmu
genetycznego:



Zaczerpnięta z nauk przyrodniczych



Wykorzystuje zjawisko doboru

naturalnego i dziedziczenia



przetrwanie osobników najlepiej

dostosowanych w danym środowisku i
eliminacja osobników gorzej
przystosowanych



Przekazanie gamet i powstanie

pokolenia lepiej przystosowanego

Jak powstały pierwotne algorytmy
genetyczne?



Holland wykorzystał fakt iż
ewolucja zachodzi na
chromosomach a nie na żywych
istotach. Uważał że odpowiednio
wprowadzony algorytm może
dostarczyć techniki rozwiązania
trudnych problemów w sposób jaki
czyni to natura-poprzez ewolucje.



Zastosował ciąg bitów w zamian chromosomu i

dokonywał symulowanej ewolucji na populacjach

chromosomów



pierwotne algorytmy wykorzystywały mechanizmy

selekcji i reprodukcji podobnie jak w naturze



Algorytmy te znajdowały dobre chromosomy nic nie

wiedząc o naturze problemów, który mają rozwiązać



Jedynym kryterium pozwalającym osiągnąć takie

wyniki jest ocena każdego chromosomu pod

względem przystosowania. Gdy znamy Funkcję

przystosowania możemy korzystając z algorytmów

genetycznych znaleźć jej optima

Istota działania prostego
algorytmu genetycznego

• Nie przeszukujemy przestrzeni bezpośrednio
• Wybieramy losowo niewielką populację należących do
niej punktów
• Populacja jest modyfikowana zgodnie z zasadami
podobnymi do tych, jakie kierują procesem naturalnej
ewolucji
• W każdej iteracji algorytmu genetycznego,

przetwarzana

populacja rozwiązań staje się populacją coraz lepiej
przystosowanych osobników, reprezentujących
rozwiązania coraz bliższe optymalnemu

Skład algorytmu genetycznego:

1.inicjacja czyli wybór początkowej

populacji chromosomów

2.ocena przystosowania chromosomów
3.sprawdzenie warunku zatrzymania
4.selekcja chromosomów
5.zastosowanie operatorów genetycznych
6.utworzenie nowej populacji
7.wynik w postaci najlepszego osobnika

Inicjacja

czyli utworzenie populacji

początkowej polega na wyborze żądanej
liczby chromosomów reprezentowanych
przez ciągi binarne określonej długości

Pula chromosomów z której
będziemy wybierać

Losujemy określoną liczbę
chromosomów np.2

Ocena przystosowania
chromosomów w populacji

polega

na obliczeniu wartości funkcji
przystosowania dla każdego chromosomu
z tej populacji. Im większa jest wartość
tej funkcji tym lepsza jakość chromosomu

Sprawdzenie warunku
zatrzymania

.Określenie warunku

zatrzymania algorytmu genetycznego zależy od
konkretnego zastosowania tego algorytmu
genetycznego i może nastąpić w przypadkach
gdy:

1.uzyskamy wartość maksymalna znaną

wcześniej np.max.f

(x)

=999

2.nie poprawia się uzyskiwana wartość np. jeśli

przez 4 generacje wynik się nie zmienia

3. po określonej liczbie generowanych populacja

np. przetwarzanie ma trwać 6 generacji

Selekcja chromosomów

polega na,

wybraniu na podstawie obliczonych wartości
funkcji przystosowania, tych chromosomów
które będą brały udział w tworzeniu potomków
do następnego pokolenia czyli następnej
generacji.Najczęściej stosowana jest metoda
ruletki

Do operatorów genetycznych zaliczamy

krzyżowanie i mutację



Krzyżowanie polega na wymianie informacji
genetycznej (bitów) między parami chromosomów.



Mutacja polega na wymianie pojedynczego bitu w
chromosomie z bardzo małym
prawdopodobieństwem

Przed mutacją

Po mutacji

Utworzenie nowej populacji



Chromosomy otrzymane w wyniku działania
operatorów genetycznych na chromosomy
tymczasowej populacji rodzicielskiej wchodzą
w skład nowej populacji



Wyprowadzenie najlepszego chromosomu.
Jeżeli spełniony jest warunek zatrzymania
algorytmu genetycznego,należy wyprowadzić
wynik działania algorytmu w postaci
najlepszego chromosomu



1975-Holland-model dwuramiennego
bandyty z podziałem wypłaty:

-prawe ramię-wypłata 75 dolarów
-lewe ramię-wypłata-25 dolarów
-początkowo nie wiemy które ramię

zapewnia większą wypłatę

-mamy populację złożona ze 100

graczy(każdy z nich otrzymuje pełną
kwotę wygranej związaną z
ramieniem,które wybrał

-wprowadzamy modyfikację do gry:wygraną

dzielimy pomiędzy graczy z danej kolejki

-teraz osobnik ustawiony do praweg0o

ramienia otrzymuje 75/100=0,75 dolarów

-gdyby wszyscy gracze ustawili się do

lewego ramienia,każdy otrzymałby 25-

0,75=24,25

-punkt równowagi,w którym nikomu nie

opłaca się zmieniać kolejki:

f(prawe)/m(prawe)=f(prawe)/M-

m(lewe)=f(lewe)/m(lewe)

-całkowite wyrównanie wypłat

nastąpi gdy 75 graczy wybierze
prawe ramię,a 25 lewe(bo
75/75=25/25=1)

-jednak w rzeczywistym algorytmie

genet.mamy do czynienia z
wieloma ramionami

Zastosowanie algorytmów
genetycznych i
ewolucyjnych



Znajdują zastosowanie w matematyce,
medycynie, technice, ekonomii itp.



Główny, lecz nie jedyny, obszar ich
zastosowań stanowi optymalizacja



Praktyczne zastosowania: wytyczanie trasy
połączeń kablowych,

sterowania, zadania transportowe, optymalizacja

wag sieci neuronowych



Gry komputerowe. Już w 1967 roku Begley
opracował adaptacyjny

program do gry w 6 pionków.



•

Cavicchio w pracy doktorskiej, z 1970 roku, użył AG do

rozwiązania



dwóch problemów: wyboru podprogramu i rozpoznawania postaci

(ściślej



do zaprojektowania zestawu detektorów cech dla urządzenia



rozpoznającego)



• System analizy obrazów medycznych za pomocą cyfrowej

angiografii



różnicowej (Fitzpatrick, Grefenstette, Van Gucht)



• Planowanie optymalnej ścieżki robota z omijaniem przeszkód,

konstrukcja



ewolucyjnych robotów



• Zagadnienia kombinatoryczne (problem komiwojażera,

harmonogramy,



planowanie zakupów itp…)

Document Outline