Algorytmy genetyczne i procesy ewolucyjne

Wykład 2 – Implementacja algorytmu genetycznego

Jacek Bieganowski

Instytut Informatyki i Elektroniki

Uniwersytet Zielonogórski

email: [e-mail]

09.03.2009

Implementacja algorytmu genetycznego – W2

Jak zakodować parametry

Liniowe odwzorowanie zdekodowanej liczby z przedziału [0, 2

l

−

1]

w zadany przedział [U

min

, U

max

]

. Dokładność takiego

odwzorowania wynosi:

ε =

U

max

− U

min

2

l

−

1

kod wartość
00

U

min

01

U

1

10

U

2

11

U

max

U

min

U

1

U

2

U

max

Implementacja algorytmu genetycznego – W2

Algorytm genetyczny [Holland]

procedure

SGA

begin

t := 0

inicjacja

P

0

ocena

P

0

while

(

not

warunek stopu)

do

begin

T

t

:= reprodukcja

P

t

O

t

:= krzy˙

zowanie i mutacja

T

t

ocena

O

t

P

t+1

:=

O

t

t := t + 1

end

end

Implementacja algorytmu genetycznego – W2

Selekcja proporcjonalna

procedure

SELEKCJA PROPORCJONALNA

begin

for

i:=1

to

popsize

do

begin

a := random()

j := 1

partsum := 0

repeat

partsum := partsum +

p

r

(X

j

)

j := j + 1

until

(partsum

>= a)

or

(j = popsize)

Z

i

:=

P

j

end

end

Implementacja algorytmu genetycznego – W2

Krzyżowanie jednopunktowe

procedure

KRZYZOWANIE JEDNOPUNKTOWE

begin

for

i:=1

to

popsize/2

do begin

a := random()

if

(a

< pp

c

)

then

begin

p

c

= (random

∗ CHROM SIZE−2) + 2

for

j:=1

to

p

c

do begin

Y

i

j

=

Z

i

j

Y

i +popsize/2

j

=

Z

i +popsize/2

j

end

for

j:=

p

c

+1

to

CHROM SIZE

do begin

Y

i

j

=

Z

i +popsize/2

j

Y

i +popsize/2

j

=

Z

i

j

end

end

end

end

Implementacja algorytmu genetycznego – W2

Mutacja

procedure

MUTACJA

begin

for

i:=1

to

popsize

do

begin

for

j:=1

to

CHROM SIZE

−1

do

begin

a := random()

if

(a

< pp

m

)

then

begin

Y

i

j

:=

not

Y

i

j

end

end

end

end

Implementacja algorytmu genetycznego – W2