Characterising continuous optimisation problems for particle swarm optimisation performance prediction
dc.contributor.advisor | Engelbrecht, Andries P. | |
dc.contributor.email | kmalan@cs.up.ac.za | |
dc.contributor.postgraduate | Malan, Katherine Mary | |
dc.date.accessioned | 2014-03-19T07:18:58Z | |
dc.date.available | 2014-03-19T07:18:58Z | |
dc.date.created | 2014 | |
dc.date.issued | 2014 | |
dc.description | Thesis (PhD (Computer Science))--University of Pretoria, 2014. | en_US |
dc.description.abstract | English: Real-world optimisation problems are often very complex. Population-based metaheuristics, such as evolutionary algorithms and particle swarm optimisation (PSO) algorithms, have been successful in solving many of these problems, but it is well known that they sometimes fail. Over the last few decades the focus of research in the field has been largely on the algorithmic side with relatively little attention being paid to the study of the problems. Questions such as ‘Which algorithm will most accurately solve my problem?’ or ‘Which algorithm will most quickly produce a reasonable answer to my problem?’ remain unanswered. This thesis contributes to the understanding of optimisation problems and what makes them hard for algorithms, in particular PSO algorithms. Fitness landscape analysis techniques are developed to characterise continuous optimisation problems and it is shown that this characterisation can be used to predict PSO failure. An essential feature of this approach is that multiple problem characteristics are analysed together, moving away from the idea of a single measure of problem hardness. The resulting prediction models not only lead to a better understanding of the algorithms themselves, but also takes the field a step closer towards the goal of informed decision-making where the most appropriate algorithm is chosen to solve any new complex problem. isiZulu: Izinkinga zangempela zokuthola isixazululo esingcono kakhulu zivamise ukuba nkimbinkimbi kakhulu. Amazinga aphezulu okuthola izixazululo ezicish'ukufana asuselwe enanini labantu, njengezindlela zokwenza eziphenduka ngokwemvelo nezindlela zokwenza zenhlayiya yoluquqaba yokuthola isixazululo esingcono kakhulu, sezibe yimpumelelo ekuxazululeni iningi lalezi zinkinga, kodwa kuyaziwa ukuthi kwesinye isikhathi kazibi yimpumelelo. Esikhathini seminyaka elishumi edlule ukugxila kocwaningo kulo mkhakha bekukakhulu ngasohlangothini lwendlela yokwenza kukuncane kakhulu ukunakwa kocwaningo lwezinkinga. Imibuzo enjengokuthi 'Yiyiphi indlela yokwenza ezokwazi nakanjani ukuxazulula inkinga yami?' noma 'Yiyiphi indlela yokwenza ezokhiqiza ngokushesha impendulo enengqondo enkingeni yami?' ihlala ingaphenduliwe. Lo mbhalo wocwaningo unomthelela ekuqondeni izinkinga zokuthola isixazululo esingcono kakhulu nasekutheni yini eyenza zibe nzima ezindleleni zokwenza, ikakhulukazi izindlela zokwenza zenhlayiya yoluquqaba yokuthola isixazululo esingcono kakhulu. Amasu ohlaziyo lokufaneleka ngokwendawo athuthukisiwe ukuchaza izinkinga eziqhubekayo zokuthola isixazululo esingcono kakhulu futhi kukhonjisiwe ukuthi lokhu kuchaza kungasetshenziswa ukubikezela ukwahluleka kwenhlayiya yoluquqaba yokuthola isixazululo esingcono kakhulu. Isici esisemqoka sale ndlela ngukuthi izici eziningi zenkinga zihlaziywa ndawonye, kuqhelwa emqondweni wesikali esisodwa senkinga enzima. Imifanekiso yesibikezelo ephumayo ayigcini kuphela ngokuholela ekuqondeni kangcono izindlela zokwenza uqobo, kodwa iphinde isondeze umkhakha emgomeni wokuthathwa kwezinqumo okunengqondo lapho indlela yokwenza okuyiyona efanele kakhulu ikhethwa ukuxazulula noma iyiphi inkinga entsha enkimbinkimbi. Afrikaans: Werklike optimiseringsprobleme is dikwels baie kompleks. Bevolkingsgebaseerde metaheuristiek, soos evolusionêre algoritmes en deeltjieswermoptimisering- (PSO) algoritmes, het baie van hierdie probleme suksesvol opgelos, maar dit is welbekend dat dit soms misluk. Oor die laaste paar dekades was die navorsingsfokus in die veld hoofsaaklik op die algoritmiese kant, met relatief min aandag wat aan die studie van die probleme geskenk is. Vrae soos 'Watter algoritme sal my probleem die akkuraatste oplos?' of 'Watter algoritme sal die vinnigste 'n redelike antwoord vir my probleem lewer?' bly onbeantwoord. Hierdie proefskrif dra by tot die begrip van optimiseringsprobleme en wat dit moeilik maak vir algoritmes, veral PSO-algoritmes. Fiksheidlandskapontledingstegnieke word ontwikkel om deurlopende optimiseringsprobleme te karakteriseer en dit word gewys dat hierdie karakterisering gebruik kan word om PSO mislukking te voorspel. n Noodsaaklike kenmerk van hierdie benadering is dat veelvuldige probleemkenmerke saam ontleed word, wat wegbeweeg van die idee van 'n enkele maatstaf van probleemkompleksiteit. Die gevolglike voorspellingsmodelle lei tot 'n beter begrip van die algoritmes en neem die veld 'n stap nader aan die doelwit van ingeligte besluitneming, waar die mees geskikte algoritme gekies word om enige nuwe komplekse probleem op te los. Sepedi: Mathata a kgonthe a go dira gore dilo di šome gabotse gantši a raragane kudu. Metaheuristics yeo e theilwego setšhabeng, go swana le di-algorithm tša tlhagelelo le di-algorithm tša go dira gore dikarolwana tša sehlopha tše šomago gabotse (PSO), di atlegile go rarolla bontši bja mathata a, eupša go tsebja gabotse gore ka dinako tše dingwe di a palelwa. Mo mengwaga šomeng ye mmalwa ya go feta nepo ya nyakišišo mo lefapheng e bile kudu ka lehlakoreng la algorithmic ka šedi ye nnyane yeo e filwego go thuto ya mathata. Dipotšišo tše bjalo ka ‘Ke algoritheme efe yeo e tlago go rarolla bothata bja-ka ka mo go nepagetšego kudu?’ goba ‘Ke algorithm efe yeo e tlago go tšweletša karabo e kwagalago ya bothata bja-ka ka pela?’ ga se di arabje. Thesese ye e tlaleletša kwešišong ya mathata a go dira gore dilo di šome gabotse le seo se dirago gore go be thata go dialgorithemo, kudukudu dialgorithemo tša PSO. Dithekniki tša tshekatsheko ya tikologo ya go swanelega di hlamilwe go hlatha mathata a go dira gore dilo di tšwelele go se šome gabotse gomme go bontšhwa gore go hlaola mo go ka šomišwa go bonela pele go palelwa ga PSO. Sebopego sa bohlokwa sa mokgwa wo ke gore dimelo tše dintši tša mathata di sekasekwa mmogo, di tloga kgopolong ya tekanyo e tee ya go thatafala ga bothata. Dikao tša ponelopele tšeo di tšweletšwago ga di lebiše fela go kwešišo ye kaone ya dialgoritmo ka botšona, eupša gape di tšea tšhemo kgato kgauswi go ya pakaneng ya go tšea diphetho tše di nago le tsebo moo algorithm ye e swanetšego kudu e kgethwago go rarolla bothata bjo bongwe le bjo bongwe bjo bo raraganego bjo bofsa | en_US |
dc.description.availability | unrestricted | en_US |
dc.description.department | Computer Science | en_US |
dc.identifier.citation | Malan, KM 2014, Characterising continuous optimisation problems for particle swarm optimisation performance prediction, PhD thesis, University of Pretoria, Pretoria, viewed yymmdd<http://hdl.handle.net/2263/37128> | en_US |
dc.identifier.other | B14/4/56/gm | |
dc.identifier.uri | http://hdl.handle.net/2263/37128 | |
dc.language.iso | en | en_US |
dc.publisher | University of Pretoria | en_ZA |
dc.rights | © 2014 University of Pretoria. All rights reserved. The copyright in this work vests in the University of Pretoria. No part of this work may be reproduced or transmitted in any form or by any means, without the prior written permission of the University of Pretoria. | en_US |
dc.subject | Particle swarm optimization (PSO) | en_US |
dc.subject | Fitness landscape analysis | |
dc.subject | Problem hardness measures | |
dc.subject | UCTD | en_US |
dc.title | Characterising continuous optimisation problems for particle swarm optimisation performance prediction | en_US |
dc.type | Thesis | en_US |