Particle swarm optimisation: an algorithm using support vector classification based constraint approximations.
Date
2019-04
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Stellenbosch : Stellenbosch University
Abstract
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.
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.
Description
Thesis (MEng)--Stellenbosch University, 2019.
Keywords
Particle swarm optimisation (PSO), Support vector machines, Constrained optimisation, Engineering design, UCTD