Wykład : Algorytmy genetyczne i

ewolucyjne

[e-mail]

Motywacje

●

Wszystkie organizmy żyją w pewnym

środowisku

●

Posiadają specyficzny materiał

genetyczny (geny)

●

Podczas reprodukcji powstaje nowy

organizm, który dziedziczy pewne cechy

po rodzicach

●

Podczas przekazywania cech dochodzi

do mutacji

●

Osobnik lepiej przystosowany do

otoczenia ma szanse na dłuższe życie

●

Osobnikowi źle przystosowanemu do

środowiska żyje się trudniej

Podstawowe pojęcia

●

Chromosom, genotyp

●

Fenotyp

●

Dopasowanie

●

Mutacja, krzyżówka (rekombinacja)

●

Populacja, populacja rodziców,

potomków

●

Pętla ewolucyjna, Generacja

Metafora Ewolucyjna

Fenotyp vs Genotyp

Pętla ewolucyjna (1)

Pętla ewolucyjna (2)

Krzyżowka bitowa

●

Poniżej jest pokazana 1-punktowa

krzyżowka bitowa

●

Są też krzyżowki n-punktowe i

jednorodne

Mutacja bitowa

●

Mutacja zamienia bit na odwrotny

●

Iteruj po wszystkich bitach, i za każdym

razem generuj pseudolosową liczbe

(0..1)

●

Gdy ta liczba jest mniejsza niż PM,

zamień bit

Selekcja Ruletkowa

●

Zwana tez proporcjonalną

●

Lepsze osobniki mają wiekszą szansę

zostać wybrane

Przyklad: Jedna iteracja pętli

ewolucyjnej

●

Problem: maksymalizuj f = x², dla x

{0, 1, ..., 31}

●

Reprezentacja: genotypy binarne,

np: 01101 = 13

●

Wielkość populacji: 4

●

Operatory: krzyżowanie 1-punktowe,

mutacja bitowa

●

Selekcja: ruletkowa

(proporcjonalna)

●

Inicjalizacja: losowa

Selekcja

Krzyżówka

Mutacja

Kodowanie liczb reczywistych

(1)

●

Problem: należy maksymalizować f(x1,

x2), gdzie x1 [0..10], a x2 [-3..5]

●

x1 należy optymalizować z dokładnością

do dwóch miejsc po przecinku, a x2 z

dokładnością do jednego miejsca po

przecinku

●

Ile bitów potrzeba na zakodowanie x1, a

ile na x2?

●

Ile bitów będzie miał genotyp?

Kodowanie liczb reczywistych

(2)

●

x1 [0..10], więc szerokość dziedziny

wynosi 10

●

Aby zachować dokładność do dwóch

miejsc po przecinku przedział o

szerokości jedności należy podzielić na

100 podprzedziałów

●

Jest więc 10 * 100 = 1000

podprzedziałów

●

Do zakodowania x1 wystarczy więc 10

bitów, bo 2^9 < 1000 < 2^10

Kodowanie liczb reczywistych

(3)

●

x2 [-3..5], więc szerokość dziedziny

wynosi 8

●

Aby zachować dokładność do jednego

miejsca po przecinku przedział o

szerokości jedności należy podzielić na

10 podprzedziałów

●

Jest więc 8 * 10 = 80 podprzedziałów

●

Do zakodowania x1 wystarczy więc 10

bitów, bo 2^6 < 80 < 2^7

●

Całkowita długość genotypu kodującego

x1 i x2 wynosi więc 10 + 7 = 17 bitów

Dekodowanie liczb

reczywistych (1)

●

Aby zdekodować genotyp:

01110101110011010 należy go

najpierw podzielić na części

odpowiadające za poszczególne

parametry

●

x1: 0111010111 x2: 0011010

●

Wartość łańcucha binarnego można

przedstawić w postaci dziesiętnej za

pomocą wzoru:

●

x = a + decimal(1011...0011) * (b – a) /

(2^n – 1), gdzie a to początek dziedziny

parametru, b to koniec dziedziny

parametru, a n to ilość bitów

reprezentacji.

Dekodowanie liczb

reczywistych (2)

●

x1 = 0 + decimal(0111010111) * 10 /

(2^10 – 1) = 471 * 10 / 1023 = 4,59

●

x2 = -3 + decimal(0011010) * 8 / (2^7 –

1) = -3 + 26 * 8 / 127 = -3 + 208 / 127

= -3 + 1,6 = -1,4

Implementacja selekcji

ruletkowej(1)

●

Wielkość populacji = 3

●

Genotyp 1: dopasowanie = 3,5

●

Genotyp 2: dopasowanie =1,9

●

Genotyp 3: dopasowanie = 4,8

●

Wylosowane liczby losowe to 0,2, 0,55 i

0,93

●

Jakie genotypy przejdą selekcje?

Implementacja selekcji

ruletkowej(2)

●

Policz sumę dopasowań wszystkich

genotypów

●

Oblicz prawdopodobieństwo selekcji

każdego genotypu

●

Policz dystrybuantę

●

Genotyp przejdzie selekcje, jeśli jego

dystrybuanta jest równa, bądź

minimalnie większa od liczby losowej

Implementacja selekcji

ruletkowej(3)

●

Suma dopasowań: 3,5 + 1,9 + 4,8 =

10,2

●

Prawdopodobieństwa selekcji to

odpowiednio: 0,343, 0,18 i 0,47

●

Dystrybuanta wynosi odpowiednio:

●

0,343, 0,523, 1

●

Liczby losowe to: 0,2, 0,55 i 0,93, więc

selekcje przejdą genotypy: 1, 3 i 3

Inne Zagadnienia

●

Selekcja: turniejowa, rankingowa,

według reszt

●

Selekcja: (mi, lambda), (mi + lambda)

●

Algorytmy ewolucyjne (nie-binarne)