Particle swarm optimisation: an algorithm using support vector classification based constraint approximations.

Malan, Maria Magdalena (2019-04)

Thesis (MA)--Stellenbosch University, 2019.

Thesis

ENGLISH ABSTRACT: Particle swarm optimisation (PSO) is by its nature an unconstrained global optimisation method, which must be, and has been, adapted in order to be capable of solving constrained optimisation problems. PSO, along with other similar metaheuristics, struggles when the global optimum is located on the boundary of the feasible region, which is common in most real-world problems, and when there are equality constraints. The aim was to develop a method for improving PSO’s ability to solve these types of constrained optimisation problems. The view that was taken was that the problem with finding global optima on the boundary is the lack of knowledge about the boundary and that deliberately encouraging the exploration of the boundary is critical for having the swarm discover these optima or having the swarm discover them in fewer iterations. To address the lack of knowledge of the boundary, support vector classification (SVC) and the data points that are already evaluated by the swarm were used to create models of the feasibility boundary. The new knowledge that these SVC models provide is used to encourage the particles’ exploration of the boundary, in order to increase the likelihood of locating the global optimum. A thorough literature review is presented to place the concepts into their proper context, present related or similar work and provide the necessary background knowledge. The reasoning behind the concepts that were created and their implementation is laid out. Four concepts with several variations were designed and evaluated through testing on a large set of test problems. The concepts were considered to be additions to a baseline PSO algorithm, and the impact their addition had was evaluated relative to it. The concepts were assessed while mimicking the SVC’s predictions, thus assuming 100% model accuracy, and then with the full classifier attached. Overall, several of the concepts provided significant reductions in the number of iterations that were required on many of the test problems. There were also clear improvements on some of the simpler equality constrained problems. Some problems or challenges are explained, and suggestions are made for improving any future implementations. The most generally promising concept algorithm shifts particles for which the position rule’s new position would entail a move from feasible to infeasible region, back to the approximate point the particle would have to cross the feasibility boundary. The intended application is to optimisation problems where the evaluation of the objective function and constraints significantly dominates the computation time, as in larger engineering design problems with simulations. For these problems the computational overhead that is introduced by the creation and automated tuning of the SVC models could potentially be negligible relative to the overall decrease associated with the reduction in the number of function evaluations required.

AFRIKAANSE OPSOMMING: Deeltjie swerm optimering (DSO) is volgens sy aard ’n onbeperkte globale optimeringsmetode wat aangepas moet word ten einde beperkte optimeringsprobleme te kan oplos. DSO, saam met ander soortgelyke metaheuristieke, sukkel wanneer die globale optimum op die grens van die toelaatbare streek geleë is, wat algemeen gebeur in regte-wêreld probleme, en asook wanneer daar gelykheidsbeperkings is. Die doel was om ’n metode te ontwikkel om DSO se vermoë om hierdie tipe beperkte optimeringsprobleme op te los, te verbeter. Die siening was dat die probleem met die vind van globale optima op die grens die gebrek aan kennis oor die grens is en dat die verkenning van die grens gebied doelbewus aangemoedig moet word, ten einde die swerm in staat te stel om hierdie optima te ontdek of dit in minder iterasies te ontdek. Om die gebrek aan kennis van die grens aan te spreek, word ondersteuningsvektor klassifikasie (OVK) en die data punte wat reeds deur die swerm geëvalueer is gebruik om modelle van die toelaatbaarheidsgrens te skep. Die nuwe kennis wat hierdie OVK-modelle bied, word aangewend om die deeltjies se verkenning van die grens aan te moedig ten einde die waarskynlikheid van die vind van die globale optimum te verhoog. ’n Deeglike literatuurstudie word aangebied ten einde die konsepte in hul wyer konteks te plaas, om verwante of soortgelyke werk voor te lê en die nodige agtergrondkennis aan die leser te verskaf. Die redenasie agter die konsepte wat ontwerp is en die implementering daarvan word uitgelê. Vier konsepte met verskeie variasies is ontwerp en geëvalueer deur toetse op ’n groot aantal toetsprobleme. Die konsepte word beskou as byvoegings tot ’n basislyn DSO-algoritme, en die impak wat hul toevoeging het, is relatief daaraan geëvalueer. Die konsepte is geassesseer terwyl die klassifiseerder se voorspellings nageboots word, wat dus 100% akkurate OVK-modelle verteenwoordig, en dan met die volledige klassifiseerder aangeheg. Oor die algemeen het verskeie van die konsepte beduidende afnames getoon in die aantal iterasies wat benodig word op baie van die toetsprobleme. Daar was ook duidelike verbeteringe op sommige van die gelykheidsbeperkte probleme. Sommige probleme of uitdagings wat ervaar was word verduidelik, en voorstelle word gemaak vir die verbetering van enige toekomstige implementasies. Die mees algemeen belowende konsep se algoritme skuif deeltjies waarvoor die posisiereël se nuwe posisie ’n skuif van die toelaatbare gebied tot die ontoelaatbare gebied sou behels, terug na die benaderde punt waar die partikel die grens sou moet oorsteek. Die beoogde toepassing is tot optimeringsprobleme waar die evaluering van die doelfunksie en beperkings die berekeningstydperk aansienlik oorheers, soos in groter ingenieursontwerpsprobleme met simulasies. Vir sulke probleme sal die berekeningsbokoste wat deur die bou en outomatiese verstelling van die OVK-modelle bygevoeg word, meeswaarskynlik weglaatbaar beskou kan word relatief tot afname in berekeningskoste verkry uit die vermindering in die aantal funksie evaluasies wat benodig word.

Please refer to this item in SUNScholar by using the following persistent URL: http://hdl.handle.net/10019.1/106086
This item appears in the following collections: