Bakalauro darbai

Lokalių paieškos metodų efektyvumo tyrimas globalios optimizacijos uždaviniuose

10   (1 atsiliepimai)
Lokalių paieškos metodų efektyvumo tyrimas globalios optimizacijos uždaviniuose 1 puslapis
Lokalių paieškos metodų efektyvumo tyrimas globalios optimizacijos uždaviniuose 2 puslapis
Lokalių paieškos metodų efektyvumo tyrimas globalios optimizacijos uždaviniuose 3 puslapis
Lokalių paieškos metodų efektyvumo tyrimas globalios optimizacijos uždaviniuose 4 puslapis
Lokalių paieškos metodų efektyvumo tyrimas globalios optimizacijos uždaviniuose 5 puslapis
Lokalių paieškos metodų efektyvumo tyrimas globalios optimizacijos uždaviniuose 6 puslapis
Lokalių paieškos metodų efektyvumo tyrimas globalios optimizacijos uždaviniuose 7 puslapis
Lokalių paieškos metodų efektyvumo tyrimas globalios optimizacijos uždaviniuose 8 puslapis
Lokalių paieškos metodų efektyvumo tyrimas globalios optimizacijos uždaviniuose 9 puslapis
Lokalių paieškos metodų efektyvumo tyrimas globalios optimizacijos uždaviniuose 10 puslapis
Lokalių paieškos metodų efektyvumo tyrimas globalios optimizacijos uždaviniuose 11 puslapis
Lokalių paieškos metodų efektyvumo tyrimas globalios optimizacijos uždaviniuose 12 puslapis
Lokalių paieškos metodų efektyvumo tyrimas globalios optimizacijos uždaviniuose 13 puslapis
Lokalių paieškos metodų efektyvumo tyrimas globalios optimizacijos uždaviniuose 14 puslapis
Lokalių paieškos metodų efektyvumo tyrimas globalios optimizacijos uždaviniuose 15 puslapis
Lokalių paieškos metodų efektyvumo tyrimas globalios optimizacijos uždaviniuose 16 puslapis
Lokalių paieškos metodų efektyvumo tyrimas globalios optimizacijos uždaviniuose 17 puslapis
Lokalių paieškos metodų efektyvumo tyrimas globalios optimizacijos uždaviniuose 18 puslapis
Lokalių paieškos metodų efektyvumo tyrimas globalios optimizacijos uždaviniuose 19 puslapis
Lokalių paieškos metodų efektyvumo tyrimas globalios optimizacijos uždaviniuose 20 puslapis
www.nemoku.lt
www.nemoku.lt
Aukščiau pateiktos peržiūros nuotraukos yra sumažintos kokybės. Norėdami matyti visą darbą, spustelkite peržiūrėti darbą.
Ištrauka

ĮVADAS Optimalumo terminą 1710 metais įvedė Leibnicas (Gottfried Leibniz). Tačiau dar senieji graikai Euklidas (Euclid) ir Aleksandrijos Heronas (Heron), įrodinėdami, kad optinėse sistemose šviesa renkasi trumpiausią kelią, sprendė, ko gero, pirmąjį optimizavimo uždavinį. Plačiau praktinius optimizavimo uždavinius imta taikyti visai neseniai – tam daug įtakos turėjo kompiuterių pažanga. Šiuo metu sparčiai kaupiama praktinių optimizavimo uždavinių sprendimo patirtis ir vystomos optimizavimo metodų idėjos. Tam dažnai turi įtakos ir kitų mokslo bei praktikos sričių pasiekimai. Šiame bakalauro darbe nagrinėjami daugelio kintamųjų funkcijų minimizavimo be apribojimų uždaviniai. Praktiniai uždaviniai paprastai turi apribotą leistinąją sritį. Tačiau, uždavinių su apribojimais sprendimo metodai arba grindžiami optimizavimo be apribojimų metodų idėjomis, arba tie metodai tiesiogiai naudojami. Minimizavimo uždavinį toli gražu ne visada pavyksta išspręsti, todėl sukurta įvairių minimizavimo be apribojimų metodų. Savo darbe nagrinėsiu negradientinius paieškos metodus grindžiamus tik tikslo funkcijos reikšmių skaičiavimu. Paieškos metodai realizuoja įvairias skirtingas idėjas, todėl juos nelengva apibrėžti kaip metodų klasę. Labiausiai charakteringa paieškos metodų savybė yra ta, kad jiems pagrįsti nėra sudaromi kiekvieno žingsnio lokalūs tikslo funkcijos modeliai. Paieškos metodai pasižymi nelokaliu ieškojimo būdu, tai yra, jų randamas lokalusis sprendinys yra nebūtinai artimiausias pradiniam taškui. Tačiau ne visi paieškos metodai orientuoti globalaus minimumo paieškai. Tam skirta ištisa globalios minimizacijos metodų klasė. Globalioji optimizacija yra žymiai sudėtingesnė už lokaliąją. Nepaisant praktinio globaliosios optimizacijos uždavinių aktualumo, plačiai paplitusiuose komerciniuose optimizavimo paketuose nėra tam skirtų metodų, todėl tikimės, kad atlikti skaičiavimai bus naudingi visiems susipažinusiems su šiuo darbu. Diplominį darbą sudaro dvi pagrindinės dalys. I darbo dalyje aptariau optimizavimo uždavinio matematinį formulavimą, remdamasi [Dzemyda, G.; Šaltenis, V.; Tiešis, V. Optimizavimo metodai, 2007] knyga, suformulavau optimumo sąlygas, išnagrinėjau negradientinius paieškos metodus, aptariau jų algoritmus ir trumpai apžvelgiau pagal kokius kriterijus vertinami optimizavimo metodai. II eksperimentinėje darbo dalyje aptariau uždavinių sprendimo planą, pateikiau testinių funkcijų duomenis ir 3 skirtingus taškų išdėstymo atvejus, kuriais rėmiausi atlikdama skaičiavimus. Matlab aplinkoje realizavusi negradientinius lokalius paieškos metodus atlikau šių metodų tyrimą globalios optimizacijos uždaviniams spręsti. TIKSLAS IR UŽDAVINIAI Tikslas – ištirti lokalių negradientinių paieškos metodų efektyvumą globalios optimizacijos uždaviniams spręsti. Uždaviniai: • susipažinti su lokaliąja ir globaliąja optimizacija bei Monte Carlo metodais; • išnagrinėti lokalius negradientinius paieškos metodus; • išnagrinėti matematinio paketo Matlab galimybes optimizacijos uždaviniams spręsti, naudojant negradientinius metodus; • pateikti kaip įmanoma tolygesnį pseudo-atsitiktinį leistinosios srities taškų padengimą ir eksperimentiškai ištirti jo efektyvumą optimizuojant Monte Carlo metodu; • realizuoti kartotinių paieškų idėją pasirinktiems negradientiniams metodams; • eksperimentinius rezultatus palyginti naudojant optimumo radimo sėkmės bei laiko kriterijus. I DALIS 1. OPTIMIZAVIMO UŽDAVINIO MATEMATINIS FORMULAVIMAS Matematiškai formuluojant optimizavimo uždavinį turi būti duoti bent du dalykai – optimizuojamų elementų aibė ir tų elementų įvertis. Matematinis šio uždavinio modelis yra: , kur f (X) : D → Y yra tikslo funkcija, D yra optimizuojamų objektų aibė (dar vadinama leistinąja sritimi), opt yra geriausio elemento vertinimo būdas, o Y yra funkcijos reikšmių aibė. Funkcijos reikšmių aibė Y turi būti bent iš dalies sutvarkyta – jos elementai turi būti palyginami. Tai yra, aibėje Y turi būti apibrėžtas dviejų aibės elementų palyginimo santykis y1 1 ir naujas simpleksas išplečiamas; 3) jei , tai = ir naujas simpleksas suspaudžiamas; 4) jei , tai = ir naujas simpleksas suspaudžiamas. [Dzemyda, G.; Šaltenis, V.; Tiešis, V. Optimizavimo metodai. Vilnius: Mokslo aidai, 2007] Šis metodas jau yra realizuotas Matlab aplinkoje, todėl trumpai aprašysime tik šio metodo iškvietimo sintaksę, nesigilinant į realizacijos detales. Galimi keli metodo iškvietimo būdai: 1. x = fminsearch (fun, x0, options) – paieška pradedama nuo taško x0 ir randamas aprašytos fun funkcijos lokalus minimumo taškas. Parametre options galima nurodyti iteracijų skaičių, tikslumą ir pan. 2. [x, fval] = fminsearch (…) – grąžina x reikšmę ir funkcijos reikšmę taške x. Atliekant praktinius skaičiavimus naudosime šį programos iškvietimo būdą. 3.2. Atsitiktinės paieškos metodas ir jo algoritmas Tai pasyvus metodas, kai parenkant bandymų taškus visai neatsižvelgiama į anksčiau atliktų bandymų rezultatus. Tokia strategija gali būti pateisinama tik pradinėse optimizavimo stadijose, kai apie tikslo funkciją turime mažai informacijos. Bendra paieškos schema: leistinojoje srityje D parenkami bandymų taškai ir juose apskaičiuojamos tikslo funkcijos reikšmės . Apytiksliu uždavinio sprendiniu laikoma minimali gautoji tikslo funkcijos reikšmė ir atitinkamas minimumo taškas . [Dzemyda, G.; Šaltenis, V.; Tiešis, V. Optimizavimo metodai. Vilnius: Mokslo aidai, 2007] Algoritmas: 1 žingsnis: pasirenkame X0 ir iteracijų skaičių N, nustatome i=1; 2 žingsnis: kiekvienai iteracijai i, Si prilyginame atsitiktiniam vektoriui; 3 žingsnis: , nustatomas minimizuojant , , Jeigu i 0) xMinGlobVekt = [xMinGlobVekt, xminloc]; end end end 4 žingsnis: jei rastas taškas nėra globalus, tikriname ar šio lokalaus taško nebuvome radę anksčiau, taip pat tikriname ar taškas priklauso leistinajai sričiai D: arnaujaslokalus = 1; if (radomglobalu 0) if ((xminloc(1) >= a)&&(xminloc(1) = c)&&(xminloc(2) fun(x) fMin = fun(x); xMin = x; end hold on scatter(xMin(1),xMin(2),'sg') end end disp('Paieskos strategija: Kubinis tinklelis') disp(['Leistinoji sritis: [' num2str(a) ',' num2str(b) ']x[' num2str(c)... ',' num2str(d) ']']); hold on scatter(xMin(1),xMin(2),'sm') disp(['fMin = ' num2str(fMin)]); disp(['xMin = [' num2str(xMin) ']' ]); toc end Mano pasiūlyto taškų išdėstymo realizavimas function [xMin, fMin] = Originalus(fun, a, b,c,d) tic fMin=Inf; xMin = [a a]; zingsnis1=(b-a)/9; zingsnis2=(d-c)/9; for i=a:zingsnis1:b for j=c:zingsnis2:d x1=[i+j]; x2=[j-i]; hold on scatter(x1,x2,'.b') x=[x1,x2]; if fMin > fun(x) fMin = fun(x); xMin = x; end hold on scatter(xMin(1),xMin(2),'sm') end end scatter(xMin(1),xMin(2),'sg') disp('Paieskos strategija: Originalus') disp(['Leistinoji sritis: [' num2str(a) ',' num2str(b) ']x[' num2str(c)... ',' num2str(d) ']']); disp(['fMin = ' num2str(fMin)]); disp(['xMin = [' num2str(xMin) ']' ]); toc end 3 Priedas (P. Venkataraman programos) UpperBound programa Trumpas P. Venkataraman programėlės aprašymas **************************************************** % Apatinė riba yra žinoma tik tada, kai randama viršutinė riba % Ši procedūra bus naudojama Golden Section metode % Perduodama funkcija turi būti prieinama kaip funkcijos m.failas ir bus grąžinama funkcijos reikšmė sukonstruotam vektoriui Trumpas pagrindinių kintamųjų aprašymas % funkcijos vardas 'functname' % dabartinės pozicijos vektorius x % dabartinės paieškos krypties vektorius s % pradinis žingsnis a0 % prieaugio žingsnis da % sugretintų žingsnių skaičius ns ***************************************************** function ReturnValue = UpperBound_nVar(functname,x,s,a0,da,ns) format compact; if (ns ~= 0) ntrials = ns; else ntrials = 10; end if (da ~= 0) das = da; else das = 1; end for i = 1:ntrials; j = 0; dela = j*das; a00 = a0 + dela; dx0 = a00*s; x0 = x + dx0; f0 = feval(functname,x0); j = j+1; dela = j*das; a01 = a0 + dela; dx1 = a01*s; x1 = x + dx1; f1 = feval(functname,x1); f1s = f1; if f1 f1s ; ReturnValue = [a01 f1 x1]; end end ReturnValue = [a01 f1 x1]; else f1 >= f0; das = 0.5*das; end end ReturnValue =[a0 f0 x0]; Golden Section programa Trumpas P. Venkataraman programėlės aprašymas **************************************************** % Šis m.failas pritaikytas golden section metodui ir naudoja UpperBound_nVar.m % Perduodama funkcija turi būti prieinama kaip funkcijos m.failas; bus grąžinta vektoriaus eilutė susidedanti iš alpha(1),f(alpha1), kintamieji iš alpha(1) per paskutinę iteraciją Trumpas pagrindinių kintamųjų aprašymas % funkcijos vardas 'functname' % tolerancija 0.001 % kintamieji reikalingi UpperBound_nVar.m failui % dabartinės pozicijos vektorius x % dabartinės paieškos krypties vektorius s % pradinė žingsnio reikšmė lowbound % priaugio vertė intvl % nuskaitytų žingsnių skaičius ntrials ************************************************* function ReturnValue = ... GoldSection_nVar(functname,tol,x,s,lowbound,intvl,ntrials) format compact; upval = UpperBound_nVar(functname,x,s,lowbound,intvl,ntrials); au=upval(1); fau = upval(2); if (au = fa2; aL = a1; faL = fa1; a1 = a2; fa1 = fa2; a2 = tau*aL + (1 - tau)*au; x2 = x + a2*s; fa2 = feval(functname,x2); au = au; fau = fau; fprintf('\niteration '),disp(i) fprintf('alphal(low) alpha(1) alpha(2) alpha{up) \n') avec = [aL a1 a2 au;faL fa1 fa2 fau]; disp([avec]) else au = a2; fau = fa2; a2 = a1; fa2 = fa1; a1 = (1-tau)*aL + tau*au; x1 = x + a1*s; fa1 = feval(functname,x1); aL = aL; faL = faL; fprintf('\niteration '),disp(i) fprintf('alphal(low) alpha(1) alpha(2) alpha{up) \n') avec = [aL a1 a2 au;faL fa1 fa2 fau]; disp([avec]) end end fprintf('final \n') fprintf('alphal(low) alpha(1) alpha(2) alpha{up) \n') avec = [aL a1 a2 au;faL fa1 fa2 fau]; disp([avec]) ReturnValue =[a1 fa1 x1]; Atsitiktinės paieškos metodo programa Trumpas P. Venkataraman programėlės aprašymas **************************************************** % Šis m.failas pritaikytas atsitiktinės paieškos metodui ir naudoja UpperBound_nVar.m bei GoldSection_nVar.m programas. Bus grąžinamas sukonstruotas vektorius ir tikslo funkcija Trumpas pagrindinių kintamųjų aprašymas % funkcijos vardas 'functname' % pradinis vektorius dvar0 % iteracijų skaičius niter % tolerancija (GoldSection_nVar.m programai) tol % pradinė žingsnio reikšmė(UpperBound_nVar.m programai) lowbound % priaugio vertė (UpperBound_nVar.m programai) intvl % nuskaitytų žingsnių skaičius(UpperBound_nVar.m programai) ntrials *************************************************************** function ReturnValue = RandomWalk(functname,dvar0,a,b,c,d) format compact; niter=10; tol=0.1; lowbound=0; intvl=1; ntrials=1; clf; nvar = length(dvar0); if (nvar == 2) %************************* %Brėžiamas kontūras %************************* x1 = a:0.1:b; x2 = c:0.1:d; x1len = length(x1); x2len = length(x2); for i = 1:x1len for j = 1:x2len x1x2 =[x1(i) x2(j)]; fun(j,i) = feval(functname,x1x2); end end c1 = contour(x1,x2,fun,[3.1 3.25 3.5 4 6 10 15 20 25],'k'); clabel(c1); grid xlabel('x_1') ylabel('x_2') %************** % Baigiamas kontūro brėžimas %************** c1 = contour(x1,x2,fun,[ 3 5 10 25 50 100],'k'); end hstep = 0.001; xs(1,:) = dvar0; x = dvar0; fs(1) = feval(functname,x); as(1)=0; for i = 1:niter-1 s = rand(nvar,1)'; sign = rand(nvar,1)'; for j = 1:nvar if (sign(j)> 0.5) s(j) = -s(j); end end ss(i,:) = s; curx = x; nextx = curx + hstep*s; slope = (feval(functname,x+hstep*s)-feval(functname,x))/hstep); if(slope

Daugiau informacijos...

Šį darbą sudaro 6806 žodžiai, tikrai rasi tai, ko ieškai!

Turinys
  • ĮVADAS 3
  • TIKSLAS IR UŽDAVINIAI 4
  • I DALIS 5
  • 1. OPTIMIZAVIMO UŽDAVINIO MATEMATINIS FORMULAVIMAS 5
  • 2. OPTIMALUMO SĄLYGOS 6
  • 2.1. Būtinos optimumo sąlygos 6
  • 2.2. Pakankamos optimumo sąlygos 7
  • 3. NEGRADIENTINIAI PAIEŠKOS METODAI 8
  • 3.1. Deformuojamo simplekso metodas 8
  • 3.2. Atsitiktinės paieškos metodas ir jo algoritmas 9
  • 3.3. Koordinatinės paieškos metodas ir jo algoritmas 10
  • 4. KARTOTINĖS PAIEŠKOS 12
  • 5. OPTIMIZAVIMO METODŲ PALYGINIMAS 13
  • II DALIS 14
  • 1. NUO UŽDAVINIO FORMULAVIMO IKI REZULTATO 14
  • 2. TESTINĖS FUNKCIJOS 15
  • 3. ĮVAIRŪS TAŠKŲ IŠDĖSTYMAI 16
  • 3.1. Monte Carlo metodo rezultatų analizė 17
  • 3.2. Rezultatų grafinis vaizdavimas 20
  • 4. KARTOTINIŲ PAIEŠKŲ REALIZAVIMAS 21
  • 4.1. Deformuojamo simplekso kartotinės paieškos metodo realizavimas 21
  • 4.1.1. Deformuojamo simplekso kartotinių paieškų rezultatų analizė 23
  • 4.1.2. Rezultatų grafinis vaizdavimas 24
  • 4.2. Kartotinės atsitiktinės paieškos metodo realizavimas 25
  • 4.2.1. Kartotinės atsitiktinės paieškos rezultatų analizė 27
  • 4.2.2. Rezultatų grafinis vaizdavimas 28
  • 4.3. Kartotinės koordinatinės paieškos metodo realizavimas 29
  • 4.3.1. Kartotinės koordinatinės paieškos rezultatų analizė 30
  • 4.3.2. Rezultatų grafinis vaizdavimas 31
  • IŠVADOS 32
  • LITERATŪROS SĄRAŠAS 33
  • REZIUMĖ 34
  • SUMMARY 34
  • RAKTINIAI ŽODŽIAI (KEY WORDS) 35
  • PRIEDAI 36
  • 1 Priedas (testinių funkcijų grafikai) 36
  • 2 Priedas (taškų išdėstymo programos) 37
  • 3 Priedas (P. Venkataraman programos) 39

★ Klientai rekomenduoja


Šį rašto darbą rekomenduoja mūsų klientai. Ką tai reiškia?

Mūsų svetainėje pateikiama dešimtys tūkstančių skirtingų rašto darbų, kuriuos įkėlė daugybė moksleivių ir studentų su skirtingais gabumais. Būtent šis rašto darbas yra patikrintas specialistų ir rekomenduojamas kitų klientų, kurie po atsisiuntimo įvertino šį mokslo darbą teigiamai. Todėl galite būti tikri, kad šis pasirinkimas geriausias!

Detali informacija
Darbo tipas
Lygis
Universitetinis
Failo tipas
Word failas (.doc)
Apimtis
47 psl., (6806 ž.)
Darbo duomenys
  • Matematikos bakalauro darbas
  • 47 psl., (6806 ž.)
  • Word failas 2 MB
  • Lygis: Universitetinis
www.nemoku.lt Atsisiųsti šį bakalauro darbą
Privalumai
Pakeitimo garantija Darbo pakeitimo garantija

Atsisiuntei rašto darbą ir neradai jame reikalingos informacijos? Pakeisime jį kitu nemokamai.

Sutaupyk 25% pirkdamas daugiau Gauk 25% nuolaidą

Pirkdamas daugiau nei vieną darbą, nuo sekančių darbų gausi 25% nuolaidą.

Greitas aptarnavimas Greitas aptarnavimas

Išsirink norimus rašto darbus ir gauk juos akimirksniu po sėkmingo apmokėjimo!

Atsiliepimai
www.nemoku.lt
Dainius Studentas
Naudojuosi nuo pirmo kurso ir visad randu tai, ko reikia. O ypač smagu, kad įdėjęs darbą gaunu bet kurį nemokamai. Geras puslapis.
www.nemoku.lt
Aurimas Studentas
Puiki svetainė, refleksija pilnai pateisino visus lūkesčius.
www.nemoku.lt
Greta Moksleivė
Pirkau rašto darbą, viskas gerai.
www.nemoku.lt
Skaistė Studentė
Užmačiau šią svetainę kursiokės kompiuteryje. :D Ką galiu pasakyti, iš kitur ir nebesisiunčiu, kai čia yra viskas ko reikia.
Palaukite! Šį darbą galite atsisiųsti visiškai NEMOKAMAI! Įkelkite bet kokį savo turimą mokslo darbą ir už kiekvieną įkeltą darbą būsite apdovanoti - gausite dovanų kodus, skirtus nemokamai parsisiųsti jums reikalingus rašto darbus.
Vilkti dokumentus čia:

.doc, .docx, .pdf, .ppt, .pptx, .odt