|
Article Information
|
Authors:
Ludwig De Bruin1
Elize M. Ehlers1
Affiliations:
1Academy for Information Technology, Universiy of Johannesburg, South Africa
Correspondence to:
Ludwig de Bruin
Email:
coldfusion.oneway@gmail.com
Postal Address:
PO Box 524, Auckland Park 2006, South Africa
How to cite this article:
De Bruin, L. & Ehlers, E.M., 2011, ‘Partikel-Swerm-Optimering (PSO) toetsbank vir globale wiskundige minimeringsprobleem’,
Suid-Afrikaanse Tydskrif vir Natuurwetenskap en Tegnologie 30(1), Art. #102, 2 pages.
http://dx.doi.org/10.4102/satnt.v30i1.102
Note:
This abstract was initially presented as a paper at the annual Natural Sciences Student Symposium, presented under the protection of the Suid-Afrikaanse
Akademie vir Wetenskap en Kuns. The symposium was held at the University of Pretoria on 05 November 2010.
The following members formed part of the committee that was responsible for arranging the symposium: Mr. R. Pretorius (Department of Geography, University of
South-Africa), Dr E. Snyders (NECSA), Dr M. Landman (Department of Chemistry, University of Pretoria) and Dr W. Meyer (Department of Physics, University of Pretoria).
Copyright Notice:
© 2011. The Authors. Licensee: AOSIS OpenJournals. This work is licensed under the Creative Commons Attribution License.
ISSN: 0254-3486 (print)
eISSN: 2222-4173 (online)
|
|
|
|
Partikel-Swerm-Optimering (PSO) toetsbank vir globale wiskundige minimeringsprobleme
|
|
In this Refereraatopsomming...
|
Open Access
|
• Opsomming
• Abstract
• Wiskundige optimering (Minimering)
• Partikel-Swerm-Optimering
• Die probleem
• Partikel-Swerm-Optimering toetsbank
• Algoritmes
• Algoritme-parameters
• Aanvanklike toestande en probleemopsporing
• Resultate
• Literatuurverwysings
|
|
’n Partikel-Swerm-Optimering (PSO) toetsbank is ontwikkel om verskillende algoritmes te vergelyk. Die toetsbank stel ons in staat om te bepaal watter tipe algoritmes verskillende probleme die beste oplos. Hierdie referaat sal eerstens wiskundige optimering definieer, kortliks PSO verduidelik, die toetsbankstelsel opsom en laastens na resultate verwys.
Particle Swarm Optimisation (PSO) test bench for global mathematical minimisation problems
A PSO test bench was developed with the aim of comparing various algorithms and their performance on a variety of domains. Techniques were employed to avoid the lost-diversity problem for domains with local minima, funnelled-precipitation being the author’s own algorithm to address this. Problems investigated include Rosenbrock’s valley, Rastrigin’s and Schwefel’s function.
|
Wiskundige optimering (Minimering)
|
|
Wiskundige optimering (minimering) verwys na probleme waar daarna gestreef word om ’n bepaalde wiskundige funksie, f, te minimeer deur toepaslike waardes uit ’n toelaatbare stel te kies.
Globale optimering (minimering) verwys na nie-linieêre probleme waar die doel is om die beste globale minimum uit verskeie lokale minima te vind. Hierdie probleme het gewoonlik betrekking op n-dimensionele modelle, en hul oplossing behels ’n globale soektog van die probleemdomein ten einde die minima te vind.
|
Partikel-Swerm-Optimering
|
|
Partkikel-Swerm-Optimering (PSO) is ’n optimeringstegniek gebaseer op swerm-intelligensie – geïnspireer deur die kollektiewe intelligensie sigbaar in swerms, byvoorbeeld in ’n swerm voëls of skool vis. Partikels beweeg in die n-dimensionele soekruimte van die probleemdomein op soek na moontlike oplossings. Elke partikel onthou sy persoonlike beste oplossing en evalueer dit teen die beste oplossing deur die swerm gevind, dit wil sê partikels gebruik sosiale interaksie (Kennedy & Eberhart 2001).
Partikels het snelhede wat hul toelaat om vanaf hul huidige posisies na ander te beweeg, soos deur ’n geskiktheidsfunksie bepaal. As gevolg hiervan sal die swerm ná ’n aantal iterasies van soektogte en evaluasies na die beste globale oplossing vir die probleem konvergeer (Di Chio, Poli & Langdon 2005).
Die bestaan van vele plaaslike minima veroorsaak dat partikels onbewus van oplossings in ander dele van die soekruimte bly – aangesien hulle hierdie oplossings nie kan bereik nie. Partikels is dikwels geneig om saam te bondel en vas te sit in die ‘valleie’ binne die soekruimte. Dit staan as die verlore-diversiteits-probleem bekend en lei tot ongewenste lokale minimum oplossings vir die probleem (Blackwell 2007).
|
Partikel-Swerm-Optimering toetsbank
|
|
Die volgende is ’n opsomming van die toetsbank:
Algoritmes
1. Globale-beste PSO: klassieke model waarin alle partikels van mekaar bewus is (Di Chio, Poli & Langdon 2005).
2. Lokale-beste PSO: partikels word in aparte omgewings in die domein geplaas vir diversiteit (Di Chio, Poli & Langdon 2005).
3. Atomies-gelaaide PSO: atoomfisika word gebruik om sommige partikels ’n lading (positief of negatief) te gee, wat hulle van mekaar wegstoot.
4. Getregterde-neerslag PSO: ontwikkel deur die outeur vir gebruik in soekruimtes met vele lokale minima en gebaseer op dieselfde beginsels as die presipitasie van reën (Murphy 2006).
Algoritme-parameters
Verseker dat algoritmes doeltreffend op verskeie probleme toegepas kan word.
1. Dinamiese traagheidsgewig: algoritmes kan verfyn word deurdat hulle met ’n globale soek-strategie begin om optimale gebiede te ontdek en later ’n lokale soek-strategie te gebruik om te konvergeer (Shi & Eberhart 1998).
2. Snelheid-vasklemming: om te verseker dat partikels optimale gebiede nie verbyskiet nie.
Aanvanklike toestande en probleemopsporing
Metodes om algoritmes die beste kans op sukses te gee:
1. Domein-verstrooings-inisialisering: logiese subverdeling van die soekruimte om partikels in gedeeltes te strooi.
2. Stagnasie: opsporing (partikels vasgevang in lokale minima).
3. Divergensie: opsporing (partikels wat wegbeweeg van minima).
4. Dinamiese swerm-herinisialisering: om stagnasie en divergensie te voorkom.
Vele interessante korrelasies is gemaak oor:
• optimale swermgrootte (25 partikels)
• domeinverstrooiingsgrootte (10–20 gedeeltes)
• traagheidsgewig en vasklemmings-konstantes.
Byna perfekte oplossings vir funksies soos Rosenbrock se vallei is in ongeveer 280 iterasies gevind en meer komplekse funksies soos Schwefel se funksie in omtrent 570 iterasies. Eenvoudige probleme word gewoonlik binne 10–50 iterasies opgelos.
Blackwell, T.M., 2007, ‘Particle Swarm Optimization in Dynamic Environments’, in Springerlink, viewed n.d., from
http://www.springerlink.com/content/u36w892m26240g7k/fulltext.pdf
Di Chio, C., Poli, R. & Langdon, W.B., 2005, Evolution of Force-Generating Equations for PSO using GP, viewed n.d., from
http://cswww.essex.ac.uk/staff/poli/papers/gsice2005.pdf
Kennedy, J. & Eberhart, R.C., 2001, Swarm Intelligence, Morgan Kaufmann Publishers, San Francisco.
Murphy, C., 2006, Effects of Swarm Size on Attractive-Repulsive Particle Swarm Optimisation, viewed n.d., from
http://ncra.ucd.ie/COMP40580/crc2006/murphy.pdf
Shi, Y. & Eberhart, R.C., 1998, ‘A modified Particle Swarm Optimizer’, proceedings of the IEEE Congress on Evolutionary Computation, 04–09 May.
|
|
Hide
Show all
Email this article (Login required)
Post a Comment (Login required)
