Patyra_Lukasz.pdf
(
206 KB
)
Pobierz
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.1Definicja..................................... 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
10
PolitechnikaWrocławska—WydziałElektroniki
2
Informatykasystemówautonomicznych Heurystyka,cotojest,potencjalnezastosowania
1Wst¦p
1.1Definicja
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
3
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±¢,profildymplomowania)inaokre±lonysemestr
studiów.
2.2Okre±leniefunkcjicelu
Wcelugenerowaniaplanuzaj¦¢koniecznejestzdefiniowaniefunkcjicelu,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
4
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
5
Plik z chomika:
comp.prog1
Inne pliki z tego folderu:
pea.rar
(13525 KB)
PEAprojTabuSerh.7z
(5308 KB)
Adam+Tynski.pdf
(1158 KB)
INF_ogloszenie_studenci_2010.pdf
(38 KB)
kody.cpp
(12 KB)
Inne foldery tego chomika:
Laborka
PEAprojWyrzazanie
Zgłoś jeśli
naruszono regulamin