Particle Swarm Optimization

by Clerc, Maurice

• ISBN13: 9781905209040
• ISBN10: 1905209045
• Edition: 1st
• Format: Hardcover
• Copyright: 2006-02-24
• Publisher: Wiley-ISTE

Summary

This is the first book devoted entirely to Particle Swarm Optimization (PSO), which is a non-specific algorithm, similar to evolutionary algorithms, such as taboo search and ant colonies.Since its original development in 1995, PSO has mainly been applied to continuous-discrete heterogeneous strongly non-linear numerical optimization and it is thus used almost everywhere in the world. Its convergence rate also makes it a preferred tool in dynamic optimization.

Author Biography

Maurice Clerc is a consultant for the eXtended Particle Swarm (XPS) project and a former France Telecom R&D engineer.

Table of Contents

Foreword	13	(4)
Introduction	17	(4)
Part I. Particle Swarm Optimization	21	(172)
What is a Difficult Problem?	23	(6)
An intrinsic definition	23	(2)
Estimation and practical measurement	25	(1)
For ``amatheurs'': some estimates of difficulty	26	(2)
Function DΣd=1 Xd	27	(1)
Function DΣd=1 X2d	27	(1)
Function DΣd=1 √Xd| sin (Xd)|	27	(1)
Traveling salesman on D cities	28	(1)
Summary	28	(1)
On a Table Corner	29	(8)
Apiarian metaphor	29	(1)
An aside on the spreading of a rumor	30	(1)
Abstract formulation	30	(4)
What is really transmitted	34	(1)
Cooperation versus competition	35	(1)
For ``amatheurs'': a simple calculation of propagation of rumor	35	(1)
Summary	36	(1)
First Formulations	37	(14)
Minimal version	37	(7)
Swarm size	37	(1)
Information links	38	(1)
Initialization	38	(1)
Equations of motion	39	(1)
Interval confinement	40	(2)
Proximity distributions	42	(2)
Two common errors	44	(1)
Principal drawbacks of this formulation	45	(3)
Distribution bias	45	(3)
Explosion and maximum velocity	48	(1)
Manual parameter setting	48	(1)
For ``amatheurs'': average number of informants	49	(1)
Summary	50	(1)
Benchmark Set	51	(8)
What is the purpose of test functions?	51	(1)
Six reference functions	52	(1)
Representations and comments	52	(4)
For ``amatheurs'': estimates of levels of difficulty	56	(2)
Theoretical difficulty	56	(1)
Tripod	56	(1)
Alpine 10D	57	(1)
Rosenbrock	57	(1)
Difficulty according to the search effort	58	(1)
Summary	58	(1)
Mistrusting Chance	59	(12)
Analysis of an anomaly	59	(2)
Computing randomness	61	(1)
Reproducibility	61	(1)
On numerical precision	62	(1)
The rare Kiss	62	(2)
Brief description	63	(1)
Test of Kiss	64	(1)
On the comparison of results	64	(1)
For ``amatheurs'': confidence in the estimate of a rate of failure	65	(3)
C programs	68	(1)
Summary	69	(2)
First Results	71	(16)
A simple program	71	(1)
Overall results	72	(1)
Robustness and performance maps	73	(7)
Theoretical difficulty and noted difficulty	80	(1)
Source code of OEP 0	80	(5)
Summary	85	(2)
Swarm: Memory and Graphs of Influence	87	(16)
Circular neighborhood of the historical PSO	87	(1)
Memory-swarm	88	(2)
Fixed topologies	90	(2)
Random variable topologies	92	(1)
Direct recruitment	92	(1)
Recruitment by common channel of communication	92	(1)
Influence of the number of informants	93	(2)
In fixed topology	93	(2)
In random variable topology	95	(1)
Influence of the number of memories	95	(2)
Reorganizations of the memory-swarm	97	(2)
Mixing of the memories	97	(1)
Queen and other centroids	98	(1)
Comparative results	98	(1)
For ``amatheurs'': temporal connectivity in random recruitment	99	(2)
Summary	101	(2)
Distributions of Proximity	103	(18)
The random possibilities	103	(1)
Review of rectangular distribution	104	(1)
Alternative distributions of possibilities	105	(8)
Ellipsoidal positive sectors	105	(1)
Independent Gaussians	106	(1)
Local by independent Gaussians	107	(1)
The class of one-dimensional distributions	107	(1)
Pivots	108	(4)
Adjusted ellipsoids	112	(1)
Some comparisons of results	113	(3)
For ``amatheurs''	116	(2)
Squaring of a hypersphere	116	(1)
From sphere to ellipsoid	117	(1)
Random volume for an adjusted ellipsoid	117	(1)
Uniform distribution in a D-sphere	118	(1)
C program of isotropic distribution	118	(1)
Summary	119	(2)
Optimal Parameter Settings	121	(8)
Defense of manual parameter setting	121	(1)
Better parameter settings for the benchmark set	122	(5)
Search space	122	(1)
To optimize the optimizer	123	(2)
Analysis of results	125	(1)
Rate of failure	125	(1)
Distribution	125	(1)
Topology and the number of informants	125	(1)
Informants K	125	(1)
Coefficient φ	126	(1)
Informants N and memories M	126	(1)
Towards adaptation	127	(1)
For ``amatheurs'': number of graphs of information	127	(1)
Summary	128	(1)
Adaptations	129	(10)
Demanding criteria	129	(1)
Criterion 1	129	(1)
Criterion 2	129	(1)
Rough sketches	130	(5)
Weighting with temporal decrease	130	(1)
Selection and replacement	131	(1)
Parametric adaptations	132	(1)
Nonparametric adaptations	133	(2)
For ``amatheurs''	135	(3)
Formulas of temporal decrease	135	(1)
Parametric adaptations	136	(1)
Case 1 (mi ≥ 0)	137	(1)
Case 2 (mi < 0)	137	(1)
Summary	138	(1)
Tribes or Cooperatin of Tribes	139	(12)
Towards an ultimate program	139	(2)
Description of Tribes	141	(6)
Tribes	141	(1)
The tribal relationships	141	(1)
Quality of a particle	141	(1)
Quality of a tribe	142	(1)
Evolution of the tribes	142	(1)
Removal of a particle	142	(2)
Generation of a particle	144	(1)
Strategies of displacement	145	(1)
Best informant	146	(1)
Direct comparison, general case	147	(1)
Comparison by pseudo-gradients, metric spaces	147	(1)
Results on the benchmark set	147	(2)
Summary	149	(2)
On the Constraints	151	(16)
Some preliminary reflections	151	(1)
Representation of the constraints	152	(1)
Imperative constraints and indicative constraints	153	(1)
Interval confinement	154	(1)
Discrete variable	154	(2)
Direct method	155	(1)
List not ordered (and not orderable)	155	(1)
Ordered list	155	(1)
Indirect method	155	(1)
Granularity confinement	156	(1)
``all different'' confinement	156	(1)
Confinement by dichotomy	157	(1)
Multicriterion treatment	158	(3)
Treatment by penalties	161	(1)
C source code. Dichotomic search in a list	162	(1)
For ``amatheurs''	162	(3)
Summary	165	(2)
Problems and Application	167	(22)
Ecological niche	167	(1)
Typology and choice of problems	168	(1)
Canonical representation of a problem of optimization	169	(1)
Knapsack	169	(1)
Magic squares	170	(1)
Quadratic assignment	171	(1)
Traveling salesman	172	(1)
Hybrid JM	173	(1)
Training of a neural network	174	(3)
Exclusive OR	175	(1)
Diabetes among Pima Indians	176	(1)
Servomechanism	176	(1)
Comparisons	176	(1)
Pressure vessel	177	(5)
Continuous relaxed form	179	(1)
Complete discrete form	180	(2)
Compression spring	182	(3)
Moving Peaks	185	(3)
For ``amatheurs'': the magic of squares	188	(1)
Summary	188	(1)
Conclusion	189	(4)
End of the beginning	189	(1)
Mono, poly, meta	189	(1)
The beginning of the end?	190	(3)
Part II. Outlines	193	(38)
On Parallelism	195	(6)
The short-sighted swarm	195	(1)
A parallel model	195	(1)
A counter-intuitive result	196	(1)
Qualitative explanation	197	(1)
For ``amatheurs'': probability of questioning an improved memory	198	(1)
Summary	199	(2)
Combinatorial Problems	201	(10)
Difficulty of chaos	201	(1)
Like a crystal	202	(1)
Confinement method	203	(1)
Canonical PSO	204	(6)
Summary	210	(1)
Dynamics of a Swarm	211	(14)
Motivations and tools	211	(1)
An example with the magnifying glass	212	(5)
One particle	212	(2)
Two particles	214	(3)
Energies	217	(3)
Definitions	217	(1)
Evolutions	218	(2)
For experienced ``amatheurs'': convergence and constriction	220	(4)
Criterion of convergence	220	(1)
Coefficients of constriction	221	(1)
Positive discriminant	222	(2)
Summary	224	(1)
Techniques and Alternatives	225	(6)
Reprise	225	(1)
Stop-restart/reset	226	(1)
A criterion of abandonment	226	(1)
Guided re-initialization	227	(1)
Multi-swarm	227	(1)
Dynamic optimization	228	(1)
For ``amatheurs''	229	(1)
Maximum flight and criterion of abandonment	229	(1)
Dilation	230	(1)
Summary	230	(1)
Further Information	231	(2)
Bibliography	233	(6)
Index	239