Patyra_Lukasz.pdf

PolitechnikaWrocławska

WydziałElektroniki

INFORMATYKASYSTEMÓW

AUTONOMICZNYCH

Heurystyka,cotojest,potencjalnezastosowania

Autor: Prowadz¡cyzaj¦cia:

ŁukaszPatyra drin».MarekPiasecki

indeks:133325

Ocenapracy:

Wrocław2007

Informatykasystemówautonomicznych Heurystyka,cotojest,potencjalnezastosowania

Spistre±ci

1Wst¦p 3

1.1Deﬁnicja..................................... 3

1.2Algorytmyheurystyczne............................ 3

1.3Potencjalnezastosowania............................ 3

2Zastosowaniepraktyczne 4

2.1Zało»eniawst¦pne................................ 4

2.2Okre±leniefunkcjicelu............................. 4

2.3Wybóralgorytmu................................ 5

2.3.1Algorytmgenetyczny.......................... 5

2.3.2Symulowanewy»arzanie........................ 6

2.4Projektprogramu—notacjaUML...................... 7

Literatura

PolitechnikaWrocławska—WydziałElektroniki

Informatykasystemówautonomicznych Heurystyka,cotojest,potencjalnezastosowania

1Wst¦p

1.1Deﬁnicja

Heurystyka(grec.heurisko—znajduj¦,odkrywam)—umiej¦tno±¢wykrywaniano-

wychfaktówizwi¡zkówmi¦dzyfaktami(azwłaszczastawianiahipotez).

Winformatyceheurystykatometodaznajdowaniarozwi¡za«,dlaktórejniemagwa-

rancjiznalezieniarozwi¡zaniaoptymalnego,acz¦stonawetprawidłowego.Rozwi¡za«tych

u»ywasi¦np.wtedy,gdypełnyalgorytmjestzprzyczyntechnicznychzbytkosztowny,

czasochłonny,lubgdyniejestnawetznany.Metod¦u»ywasi¦te»cz¦stodoznajdowania

rozwi¡za«przybli»onych,napodstawiektórychpó¹niejwyliczasi¦ostatecznyrezultat

pełnymalgorytmem.Toostatniezastosowanieszczególniedotyczyprzypadków,gdyheu-

rystykajestwykorzystywanadonakierowywaniapełnegoalgorytmukuoptymalnemuroz-

wi¡zaniu,abyzmniejszy¢czasdziałaniaprogramuwtypowymprzypadkubezpo±wi¦cania

jako±cirozwi¡zania.

1.2Algorytmyheurystyczne

Mianemalgorytmówheurystyczychs¡okre±lanealgorytmy,którepozwalaj¡nazna-

lezienieprzybli»onegorozwi¡zaniaproblemu(cz¦stoNP—trudnego),któryniemo»eby¢

rozwi¡zanywsposóboptymalnyzewzgl¦duna:

• brakalgorytmujegorozwi¡zania,

• zło»ono±¢obliczeniow¡algorytmuoptymalnegooraz(cobezpo±rednioztegowyni-

ka),

• nieopłacalniedługiczasdziałaniaczylirównie»wysokiekosztyotrzymaniaoptymal-

negowyniku.

1.3Potencjalnezastosowania

• szeregowaniezada«naprocesorach,

• rozpoznawanieznaków,

• generowanieplanuzaj¦¢dlagrupyosób,

• ...

PolitechnikaWrocławska—WydziałElektroniki

Informatykasystemówautonomicznych Heurystyka,cotojest,potencjalnezastosowania

2Zastosowaniepraktyczne

Jakoprzykładzastosowaniaalgorytmuheurystycznegowybrałemprogramasystenta

organizuj¡cegoczas/miejscespotka«osóbwdu»ychgrupachzawodowych/towarzyskich.

Dokładniejzaproponowałemsposóbrealizacjiprogramumaj¡cegonaceluwygenerowanie

planuzaj¦¢dlagrupystudentówwdanymsemestrze.

2.1Zało»eniawst¦pne

Programmapozwala¢nagenerowanieplanówzaj¦¢dlagrupystudentówzgodnie

zsiatk¡zaj¦¢okre±lon¡wkatalogukursów.Zaj¦ciab¦d¡generowanedlawybranejgru-

pystudentów(np.kierunek,specjalno±¢,proﬁldymplomowania)inaokre±lonysemestr

studiów.

2.2Okre±leniefunkcjicelu

Wcelugenerowaniaplanuzaj¦¢koniecznejestzdeﬁniowaniefunkcjicelu,którab¦dzie

okre±lałajako±¢planu.Wtymceluprzyj¡łemkryteriamówi¡ce»e:

1.planjestlepszy,je»elizaj¦cianiezaczynaj¡si¦wcze±nieranoinieko«cz¡pó¹nym

wieczorem.

2.planjesttymlepszy,immniejjestprzerwmi¦dzykolejnymizaj¦ciami,

Warto±¢funkcjiceludladanegoplanuzale»e¢zatemb¦dzieodwarto±ciobuztych

kryteriów.Chc¡cuwzg¦dni¢kryterium1przyporz¡dkowałemokre±lonewagidlazaj¦¢

rozpoczynaj¡cychsi¦ookre±łonejporze(tab.1):

Tabel a1:Wagiposzczególnychterminów zaj¦¢

godzinarozpocz¦ciazaj¦¢waga

przed9:003

od9:002

od11:001

od15:002

od18:003

Warto±¢kryterium1zapisałemwzorem:

P n i =1 W i

k 1 =

n n=liczbazaj¦¢wtygodniu (1)

PolitechnikaWrocławska—WydziałElektroniki

Informatykasystemówautonomicznych Heurystyka,cotojest,potencjalnezastosowania

Zkoleichc¡cuwzgl¦dni¢kryterium2zauwa»yłem,»eminimalizacjaliczbyprzerw

mi¦dzyzaj¦ciamitozpraktycznegopunktuwidzeniatosamo,cominimalizacjaczasujaki

studentsp¦dza(powiniensp¦dza¢)nauczelniwci¡gutygodnia.Mo»nazatemzapisa¢:

pt X

k 2 =

C d , gdzie: C d = C z − C o

(2)

d = pn

C o —czasrozpocz¦ciazaj¦¢wdanymdniu

C z —czaszako«czeniazaj¦¢wdanymdniu

Funkcjacelu,któr¡nale»yzoptymalizowa¢mo»emie¢posta¢:

F opt = min ( k 1 · k 2 )

(3)

2.3Wybóralgorytmu

Kolejnymkrokiembyłowybranieodpowiednegotypualgorytmu,którychciałbymu»y¢

dorozwi¡zaniazadania.Poniewa»dotychczasimplementowałemdwaalgorytmyheury-

styczne(algorytmgenetycznyorazsymulowanewy»arzanie),tote»najpierwrozpatrzyłem

mo»liwo±¢zastosowaniawła±niejednegoznich.

2.3.1Algorytmgenetyczny

Algorytmgenetycznypoleganaposzukiwaniumaksymalnejwarto±cifunkcjiprzysto-

sowaniaopartegonamechanizmachdoborunaturalnegoorazdziedziczno±cił¡cz¡cego

ewolucyjn¡zasad¦prze»ycianajlepiejprzystosowanychosobnikówzsystematyczn¡ipo

cz¦±cilosow¡wymian¡informacji.[1][2]

Kolejnekrokiogólnegoalgorytmugenetycznego:

1.Generacjapopulacjipocz¡tkowej,

2.Wyznaczeniefunkcjiprzystosowaniaosobników,

3.Wybórpulirodzicielskiej,

4.Krzy»owanie,

5.Mutacjanowychosobników,

6.Selekcjanowejpopulacji.

Stosuj¡calgorytmgenetycznyproblempojawiłbysi¦przykrzy»owaniuosobników,

poniewa»nawetje±likrzy»owaliby±mydwaosobniki,któreokre±laj¡dobryplan(zaj¦cia

nienachodz¡nasiebie)topotomekjakiegootrzymamymo»etegowarunkuniespełnia¢.

PolitechnikaWrocławska—WydziałElektroniki

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: