Problem difficulty analysis for particle swarm optimization

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Problem difficulty analysis for particle swarm optimization: deception and modality

Full text

Pdf (1.27 MB)

Source

ACM/SIGEVO Summit on Genetic and Evolutionary Computation archive
Proceedings of the first ACM/SIGEVO Summit on Genetic and Evolutionary Computation table of contents

Shanghai, China

SESSION: Full papers table of contents

Pages 623-630

Year of Publication: 2009

ISBN:978-1-60558-326-6

Authors

Bin Xin	Department of Automatic Control, Beijing Institute of Technology, Beijing, China
Jie Chen	Department of Automatic Control, Beijing Institute of Technology, Beijing, China
Feng Pan	Department of Automatic Control, Beijing Institute of Technology, Beijing, China

Sponsors

SIGEVO: ACM Special Interest Group on Genetic and Evolutionary Computation
ACM: Association for Computing Machinery

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 12, Downloads (12 Months): 51, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1543834.1543919 What is a DOI?

ABSTRACT

This paper studies the problem difficulty for a popular optimization method - particle swarm optimization (PSO), particularly for the PSO variant PSO-cf (PSO with constriction factor), and analyzes its predictive measures. Some previous measures and related issues about other optimizers, mainly including deception and modality, are checked for PSO. It is observed that deception is mainly the combination of three factors - the measure ratios of attraction basins, the relative distance of attractors and the relative difference of attractors' altitudes. Multimodality and multi-funnel are proved not to be the essential factors contributing to the problem difficulty for PSO. The counterexamples and comparative experiments in this paper can be taken as a reference for further researches on novel comprehensive predictive measures of problem difficulty for PSO.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	J. Kennedy and R. C. Eberhart. Particle swarm optimization. in Proc. IEEE Int. Conf. Neural Netw., Perth, Australia, 1995, pages.1942--1948.
	2	K. E. Parsopoulos and M. N. Vrahatis. On the computation of all global minimizers through particle swarm optimization. IEEE Trans. Evol. Comput., 8(3): 211--224, 2004.
	3	C. A. C. Coello, G. T. Pulido and M. S. Lechuga. Handling multiple objectives with particle swarm optimization. IEEE Trans. Evol. Comput., 8(3): 259--276, 2004.
	4	J. J. Liang, A. K. Qin, P. N. Suganthan and S. Baskar. Comprehensive learning particle swarm optimizer for global optimization of multimodal functions. IEEE Trans. Evol. Comput., 10(3): 281--295, 2006.
	5	D. Parrott and X. Li. Locating and tracking multiple dynamic optima by a particle swarm model using speciation. IEEE Trans. Evol. Comput., 10(4): 440--458, 2006.
	6	H. Pan, L. Wang and B. Liu. Particle swarm optimization for function optimization in noisy environment. Appl. Math. Comput., 181(2): 908--919, 2006.
	7	David E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
	8	R. C. Eberhart and Y. Shi. Comparing inertia weights and constriction factors in particle swarm optimization. in Proc. IEEE Cong. Evol. Comput., La Jolla, California, USA, 2000, pages. 84--88.
	9	Yuhui Shi , Russell C. Eberhart, Parameter Selection in Particle Swarm Optimization, Proceedings of the 7th International Conference on Evolutionary Programming VII, p.591-600, March 25-27, 1998
	10	A. Ratnaweera, S. K. Halgamuge and H. C. Watson. Self-organizing hierarchical particle swarm optimizer with time-varying acceleration coefficients. IEEE Trans. Evol. Comput., 8(3): 240--255, 2004.
	11	R. Mendes, J. Kennedy and J. Neves. The fully informed particle swarm: simpler, maybe better. IEEE Trans. Evol., Comput., 8(3): 204--210, 2004.
	12	X. Chen and Y. Li. A modified PSO structure resulting in high exploration ability with convergence guaranteed. IEEE Trans. Syst,. Man, Cybern. B, Cybern., 37(5): 1271--1289, 2007.
	13	D. H. Wolpert and W. G. Macready. No free lunch theorems for optimization. IEEE Trans. Evol. Comput., 1(1): 67--82, 1997.
	14	Y. Shi and R. C. Eberhart. A modified particle swarm optimizer. in Proc. IEEE Int. Conf. Evol. Comput., Anchorage, AK, USA, 1998, pages. 69--73.
	15	S. Janson and M. Middendorf. A hierarchical particle swarm optimizer and its adaptive variant. IEEE Trans. Syst,. Man, Cybern. B, Cybern., 35(6): 1272--1282, 2005.
	16	J. Kennedy and R. Mendes. Neighborhood topologies in fully informed and best-of-neighborhood particle swarms. IEEE Trans. Syst,. Man, Cybern. C, App., Rev., 36(4): 515--519, 2006.
	17	P. Angeline. Using selection to improve particle swarm optimization. in Proc. IEEE Cong. Evol. Comput., Anchorage, AK, USA, 1998, pages. 84--89.
	18	Y. P. Chen, W. C. Peng and M. C. Jian. Particle swarm optimization with recombination and dynamic linkage discovery. IEEE Trans. Syst,. Man, Cybern. B, Cybern., 37(6): 1460--1470, 2007.
	19	F. van den Bergh and A. P. Engelbrecht. A cooperative approach to particle swarm optimization. IEEE Trans. Evol. Comput., 8(3): 225--239, 2004.
	20	J. Riget and J. S. Vesterstrøem. A diversity-guided particle swarm optimizer-the ARPSO. Technical Report No. 2002-02, Dept. of Computer Science, University of Aarhus, EVALife.
	21	M. Clerc and J. Kennedy. The particle swarm: explosion, stability and convergence in a multi-dimensional complex space. IEEE Trans. Evol. Comput., 6(1): 58--73, 2002.
	22	William G. Macready , David H. Wolpert, What makes an optimization problem hard?, Complexity, v.1 n.5, p.40-46, 1995/1996
	23	S. W. Wilson. GA-easy does not imply steepest--ascent optimizable. in Proc. 4th Int. Conf. Genetic Algorithms, R. K. Belew and L. B. Booker, Eds., San Mateo, CA: Morgan Kaufmann, 1991, pages.85--89.
	24	D. E. Goldberg. Making genetic algorithms fly: a lesson from the Wright brothers. Adv. Technol. Developers, 2: 1--8, 1993
	25	J. J. Grefenstette. Deception considered harmful. in Foundations of Genetic Algorithms II, L. D. Whitley, Ed., San Mateo, CA: Morgan Kaufmann, 1993, pages.75--92.
	26	S. Forrest and M. Mitchell. Relative building-block fitness and the building-block hypothesis. in Foundations of Genetic Algorithms II, L. D. Whitley, Ed., San Mateo, CA: Morgan Kaufmann, 1993, pages.109--126.
	27	J. Horn and D. E. Goldberg. Genetic algorithms difficulty and the modality of fitness landscapes. in Foundations of Genetic Algorithms III, L. D. Whitley et al., Eds., San Mateo, CA: Morgan Kaufmann, 1995, pages.243--269.
	28	Stephanie Forrest , Melanie Mitchell, What Makes a Problem Hard for a Genetic Algorithm? Some Anomalous Results and Their Explanation, Machine Learning, v.13 n.2-3, p.285-319, Nov./Dec. 1993 [doi>10.1007/BF00993046]
	29	Terry Jones , Stephanie Forrest, Fitness Distance Correlation as a Measure of Problem Difficulty for Genetic Algorithms, Proceedings of the 6th International Conference on Genetic Algorithms, p.184-192, July 15-19, 1995
	30	Y. Davidor. Epistasis variance: a viewpoint on GA-hardness. in Foundations of Genetic Algorithms, G. J. E. Rawlins, Ed., San Mateo, CA: Morgan Kaufmann, 1991, pages.23--35.
	31	B. Manderick, M. de Weger and P. Spiessens. The genetic algorithm and the structure of the fitness landscape. in Proc. 4th Int. Conf. Genetic Algorithms, R. K. Belew et al. Eds., San Mateo, CA: Morgan Kaufmann, 1991, pages. 143--150.
	32	N. J. Radcliffe and P. D. Surry. Fitness variance of formulae and performance prediction. in Foundations of Genetic Algorithms III, L. D. Whitley et al. Eds., San Mateo, CA: Morgan Kaufmann, 1995, pages. 51--72.
	33	L. Darrell Whitley , Keith E. Mathias , Larry D. Pyeatt, Hyperplane Ranking in Simple Genetic Algorithms, Proceedings of the 6th International Conference on Genetic Algorithms, p.231-238, July 15-19, 1995
	34	B. Naudts. Measuring GA-hardness. Ph.D. dissertion, University of Antwerp, Belgium, 1998.
	35	B. Naudts and L. Kallel. A comparison of predictive measures of problem difficulty in evolutionary algorithms. IEEE Trans. Evol. Comput., 4(1): 1--15, 2000.
	36	Y. Borenstein and R. Poli, Kolmogorov complexity, optimization and hardness. in Proc. IEEE Cong. Evol. Comput., Vancouver, BC, Canada, 2006, pages. 112--119.
	37	W. B. Langdon and R. Poli. Evolving problems to learn about particle swarm optimizers and other search algorithms. IEEE Trans Evol. Comput., 11(5): 561--578, 2007.
	38	Andrew M. Sutton , Darrell Whitley , Monte Lunacek , Adele Howe, PSO and multi-funnel landscapes: how cooperation might limit exploration, Proceedings of the 8th annual conference on Genetic and evolutionary computation, July 08-12, 2006, Seattle, Washington, USA [doi>10.1145/1143997.1144008]
	39	Y. Shi and R. C. Eberhart. Empirical study of particle swarm optimization. in Proc. IEEE Cong. Evol. Comput., Washington, DC, USA, 1999, pages. 1945--1949.
	40	W. B. Langdon and R. Poli. Finding social landscapes for PSOs via kernels. in Proc. IEEE Cong. Evol. Comput., Vancouver, BC, Canada, 2006, pages.1654--1661.
	41	L. Kallel and B. Naudts. Candidate long paths for the simple genetic algorithm. in Foundations of Genetic Algorithms V, W. Banzhaf et al., Eds., San Mateo, CA: Morgan Kaufmann, 1999.