Algorytmy genetyczne i procesy ewolucyjne Wykład 5.pdf

Algorytmygenetyczneiprocesyewolucyjne

JacekBieganowski

InstytutInformatykiiElektroniki

UniwersytetZielonogórski

email:J.Bieganowski@iie.uz.zgora.pl

http://www.uz.zgora.pl/~jbiegano/agipe08

30marca2009

Algorytmygenetyczneiprocesyewolucyjne–W5

Problemplecakowy

Danyjestzbiórartykułów(rzeczy)wrazzichwarto±ciamii

rozmiarami.Nale»ywybra¢podzbiórrzeczy,takabysuma

rozmiarównieprzekroczyłazadanegoograniczania(pojemno±ci

plecaka)iabysumawarto±cibyłajaknajwi¦ksza.

Zadaniepoleganaokre±leniuwektorabinarnego X = h x 1 ,..., x n i

takiego,»e

n X

X i W i ¬ C

i = 1

idlaktórego

n X

Z =

X i P i

i = 1

jestmaksymalne.

W = [ 10 , 12 , 7 , 1 , 20 ]

P = [ 8 , 4 , 20 , 1 , 10 ]

X = [ 1 , 1 , 0 , 0 , 1 ]

C = 20 ; z ( X ) = 8 + 4 + 10 , w ( X ) = 10 + 12 + 20 = 42

Algorytmygenetyczneiprocesyewolucyjne–W5

Jakradzi¢sobiezograniczeniami?

Karanieosobników,któreniespełniaj¡ogranicze«przez

zmiejszenieprzystosowania(funkcjakary).Wskrajnym

przypadkumo»nazmniejszy¢przystosowaniedo0tzw.kara

±mierci.

Zastosowa¢metod¦naprawychromosomu,takaby

chromosomspełniałzało»eniazadania.

Opracowa¢specjalistyczneoperatorygenetyczne(oraz

proceduryinicjalizacji),któreniegeneruj¡rozwi¡za«

niedopuszczalnych.

Algorytmygenetyczneiprocesyewolucyjne–W5

Funkcjakarydlazadaniaplecakowego

Karanes¡tylkoosobnikiniespełniaj¡ceograniczeniaprzez

odj¦ciewarto±ci K ( X )

n X

X i P i − K ( X )

i = 1

Funkcjakarypowinnaby¢proporcjonalnadotegojakmocno

zostałoprzekroczoneograniczenie.

Liniowafunkcjakary K ( X ) = P n i = 1 X i P i − C ,

Kwadratowafunkcjakary K ( X ) = ( P n i = 1 X i P i − C ) 2 .

Algorytmygenetyczneiprocesyewolucyjne–W5

Algorytmynaprawydlaproblemuplecakowego

Naprawalosowapolegaj¡canausuni¦ciulosowychelementów

zplecaka,a»dospełnieniaograniczenia.

Naprawazachłannapolegajacanausuni¦ciuzplecaka

elementów,którychstosunekzyskudowagi( P / W )jest

najgorszy.

Algorytmygenetyczneiprocesyewolucyjne–W5

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: