CULTURAL PARTICLE SWARM OPTIMIZATION MOAYED DANESHYARI Bachelor of Science Electrical Engineering Sharif University of Technology Tehran, Iran 1995 Master of Science Biomedical Engineering Iran University of Science and Technology Tehran, Iran 1998 Master of Science Physics Oklahoma State University Stillwater, Oklahoma 2007 Submitted to the Faculty of the Graduate College of the Oklahoma State University in partial fulfillment of the requirements for the Degree of DOCTOR OF PHILOSOPHY July 2010 CULTURAL PARTICLE SWARM OPTIMIZATION Dissertation Approved: Dr. Yen Dissertation Adviser Dr. Russell Rhinehart Dr. Gordon Emslie Dean of the Graduate College ii ACKNOWLEDGEMENTS I would like to first thank my academic advisor, Professor Gary G.
Yen, for his guidance, support and especially patience with all ups and downs during the years of studies that this dissertation was gradually constructed. If it were not with his flexibility with my different situations and his providing me the freedom to fully experience all aspects of academic research especially in the last two years, this academic research could never be completed. I would also like to extend my appreciation to the other committee members whose guidance, comments and review of the research work were of great importance for improving the quality of this document. My thanks also go to all my previous colleagues at the Intelligent Systems and Control Laboratory at Oklahoma State University that accompanied my progress throughout part of my research by offering me new ideas.
I should also mention my thankfulness to my colleagues in my current profession as Assistant Professor at Elizabeth City State University whose help and flexibility to give me more free time to focus on my Ph. research work was a great help. Finally, I would like to express my gratitude for my parents, Farideh and Ahmad and my sister Matin who have always supported me throughout my years of studies and provided the understanding only possible although living far from me. iii Last, but not least, I would like to specially thank my family, my wife, Lily and my little son, Ryan, for their understanding, help, support and providing appropriate environment for me to work on my research during years of studying for doctorate degree.
If it were not her verbal and spiritual support and his innocence and happiness to encourage me in working more, this study could never be accomplished. Moayed Daneshyari iv Table of Contents Chapter Page CHAPTER I INTRODUCTION. 1 CHAPTER II LITERATURE REVIEW. 12 CHAPTER III SOCIETTY AND CIVILIZAION FOR OPTIMIZATION .2 Social-based Algorithm for Optimization.
44 CHAPTER IV DIVERSITY-BASED INFORMATION EXCHANGE FOR PARTICLE SWARM OPTIMIZATION .2 Review of Related Work .3 Diversity-based Information Exchange among Swarms in PSO. 71 CHAPTER V CULTURAL-BASED MULTIOBJECTIVE PARTICLE SWARM OPTIMIZATION .2 Review of Literature .1 Related Works in Multiobjective PSO .2 Related Work in Cultural Algorithm for Multiobjective Optimization .3 Cultural-based Multiobjective Particle Swarm Optimization .1 Adapting Global Acceleration .2 Adapting Local Acceleration .5 Time-decaying Mutation Operator .4 Comparative Study and Sensitivity Analysis .2 Benchmark Test Functions .3 Qualitative Performance Comparisons .4 Quantitative Performance Evaluations. 136 CHAPTER VI CONSTRAINED CULTURAL-BASED OPTIMIZATION USING MULTIPLE SWARM PSO WITH INTER-SWARM COMMUNICAION .2 Review of Literature .1 Related Work in Constrained PSO .2 Related Works in Cultural Algorithm for Constrained Optimization .3 Cultural Constrained Optimization Using Multiple-Swarm PSO.1 Multi-Swarm Population Space .4 Inter-Swarm Communication Strategy .2 Benchmark Test Functions. 183 CHAPTER VII DYNAMIC OPTIMIZATION USING CULTURAL-BASED PARTICLE SWARM OPTIMIZATION .2 Review of Literature .1 Related Work in Dynamic PSO .2 Related Works in Cultural Algorithm for Dynamic Optimization .3 Cultural Particle Swarm for Dynamic Optimization .1 Multi Swarm Population Space .4 Diversity based Migration Driven by Change .1 Benchmark Test Problems.
232 CHAPTER VIII CONCLUSION. 241 APPENDIX A BENCHMARK TEST FUNCTIONS FOR MULTIOBJECTIVE OPTIMIZATION PROBLEMS. 262 APPENDIX B BENCHMARK TEST FUNCTIONS FOR CONSTRAINED OPTIMIZATION PROBLEMS. 265 APPENDIX C BENCHMARK TEST FUNCTIONS FOR DYNAMIC OPTIMIZATION PROBLEMS.
289 viii List of Figures Figures Page 3.1 Flowchart for social-based single objective optimization 34 3.2 Flowchart for identifying leaders 35 3.3 Flowchart on how to migrate individuals 38 3.4 Pseudocode for individuality importance in intrasociety migration 40 3.5 Schema for Spring Design problem 43 3.6 Comparison for best objective function for proposed modifications 44 4.1 Ring and random sequential migration 56 4.2 Main algorithm for diversity-based multiple PSO 56 4.3 Schema of swarm neighborhood 59 4.4 Main algorithm for diversity-based multiple PSO with neighborhood 60 4.5 Benchmark function F1 with five peaks and four valleys 65 4.6 Final best particles for F1 65 4.7 Benchmark function F2 with 10 peaks 66 4.8 Final best particles for F2 66 4.9 Benchmark function F3 with two peaks and one valley 67 4.10 Final best particles for F3 67 4.11 Benchmark function F4 with five peaks 68 4.12 Final best particles for F4 68 4.13 Benchmark function F5 with six peaks 69 4.14 Final best particles for F5 69 5.1 Schema of particle’s movement in MOPSO 76 ix 5.2 Pseudocode of the cultural MOPSO 81 5.3 Schema of the adopted cultural framework 82 5.4 Representation of situational knowledge 83 5.5 Schematic view of choosing the i-th element of situational knowledge 84 5.6 Representation of normative knowledge 85 5.7 Schema on how normative knowledge can be found and updated 88 5.8 Representation of knowledge in each cell 88 5.9 Example of cell representation 89 5.10 Schema of local grid for the personal archive 93 5.11 Method of selecting from topographical knowledge 96 5.12 selection procedure from personal archive 97 5.13 Pareto fronts comparison on test function ZDT1 105 5.14 Pareto fronts comparison on test function ZDT2 106 5.15 Pareto fronts comparison on test function ZDT3 107 5.16 Pareto fronts comparison on test function ZDT4 108 5.17 Pareto fronts comparison on test function DTLZ5 109 5.18 Pareto fronts comparison on test function DTLZ6 110 5.19 Box plot of hypervolume indicator for all test function 111 5.20 Box plot for additive binary epsilon indicator on test function ZDT1 115 5.21 Box plot for additive binary epsilon indicator on test function ZDT2 115 5.22 Box plot for additive binary epsilon indicator on test function ZDT3 116 5.23 Box plot for additive binary epsilon indicator on test function ZDT4 116 5.24 Box plot for additive binary epsilon indicator on test function DTLZ5 117 5.25 Box plot for additive binary epsilon indicator on test function DTLZ6 117 5.26 Sensitivity analyses with respect to minimum personal acceleration 123 5.27 Sensitivity analyses with respect to maximum personal acceleration 124 5.28 Sensitivity analyses with respect to minimum global acceleration 125 5.29 Sensitivity analyses with respect to maximum global acceleration 126 x 5.30 Sensitivity analyses with respect to minimum momentum 127 5.31 Sensitivity analyses with respect to maximum momentum 128 5.32 Sensitivity analyses with respect to grid size 129 5.33 Sensitivity analyses with respect to population size 130 5.34 Sensitivity analyses with respect to mutation rate 131 6.1 Pseudocode of the cultural constrained particle swarm optimization 148 6.2 Schema of the cultural framework adopted 151 6.3 Representation for normative knowledge 152 6.4 The schema to represent how the spatial knowledge is computed 154 6.5 Representation of spatial knowledge for each particle 155 6.6 Representation for situational knowledge 156 6.7 Representation for temporal knowledge 157 6.8 Convergence graphs for problems 174 6.9 Convergence graphs for problems 175 6.10 Convergence graphs for problems 176 6.11 Convergence graphs for problems 177 7.1 Pseudocode of the cultural-based dynamic PSO 198 7.2 Schema of the cultural framework adopted here 201 7.3 Representation for situational knowledge 203 7.4 Representation for temporal knowledge 203 7.5 Representation for the domain knowledge 206 7.6 Representation of normative knowledge 208 7.7 Representation for spatial knowledge 212 7.8 Sigmoid function to compute repulsion factor in spatial knowledge 213 7.9 Comparison of OEV as a function of elapsed iterations on function MP1 225 7.10 Comparison of OEV as a function of peak numbers on function MP1 225 xi 7.11 Comparison of OEV as a function of dimension on function MP1 226 xii List of Tables Tables Page 3.1 Comparison of results for Spring Design problem 44 4.1 Results for optimal found and mean best objective for F1, F2, F3 and F5 70 4.2 Mean best objectives for F6, F7, F8, and F9 71 5.1 Parameter settings for all MOPSOs 101 5.2 Testing of the distribution of IH values using Mann-Whitney test 112 5.3 Testing of the distribution of using Mann-Whitney test 118 5.4 Parameter selection for sensitivity analysis 119 5.5 Statistical test to check sensitivity to minimum personal acceleration 132 5.6 Statistical test to check sensitivity to maximum personal acceleration 132 5.7 Statistical test to check sensitivity to minimum global acceleration 133 5.8 Statistical test to check sensitivity to maximum global acceleration 133 5.9 Statistical test to check sensitivity to minimum momentum 134 5.10 Statistical test to check sensitivity to maximum momentum 134 5.11 Statistical test to check sensitivity to grid size 135 5.12 Statistical test to check sensitivity to population size 135 5.13 Statistical test to check sensitivity to mutation rate 136 6.1 Parameter settings for cultural CPSO 162 6.2 Summary of 24 benchmark test functions 165 6.3 Error values for different FEs on problems 166 6.4 Error values for different FEs on problems 167 xiii 6.5 Error values for different FEs on problems 168 6.6 Error values for different FEs on problems 169 6.7 Number of function evaluations to achieve the fixed accuracy level, Success Rate, Feasibility Rate, and Success Performance 171 6.8 Summary of statistical results found by cultural CPSO 173 6.10 Comparison of cultural CPSO with the state-of-the-art constrained optimization methods in terms of feasible rate 180 6.11 Comparison of cultural CPSO with the state-of-the-art constrained optimization methods in terms of success rate 181 6.12 Sensitivity analysis with respect to personal acceleration 182 6.13 Sensitivity analysis with respect to swarm acceleration 183 6.14 Sensitivity analysis with respect to global acceleration 184 6.15 Sensitivity analysis with respect to rate of information exchange 185 7.1 Parameter settings for different paradigms 221 7.2 OEV index after 500,000 FEs on test problem MP1 224 7.3 OEV index after 500,000 FEs on test problem DF2 227 7.4 OEV index after 500,000 FEs on test problem DF3 228 7.5 OEV index after 500,000 FEs on test problem DF4 228 7.6 OEV index after 500,000 FEs on test problem DF5 229 7.7 OEV index after 500,000 FEs on test problem DF6 231 7.8 P-values using Mann-Whitney rank-sum test 231 7.9 OEV index after 50,000 FEs using default parameters 232 B.1 Data set for test problem 282 B.2 Data set for test problem 283 xiv Nomenclature Number of decision variables; dimension of decision variables Number of particles; number of individuals; population size Number of constraints Number of objectives Number of swarms; number of societies Number of inequality constraints Tolerance for equality constraints Population of the i-th swarm, number of individuals in the i-th society Inequality constraint Equality constraint Personal best particle in PSO Global best particle in PSO Neighborhood best particle in PSO Swarm best particle in PSO xv Inequality constraint Equality constraint Personal acceleration in PSO Global acceleration in PSO Neighborhood acceleration in PSO Swarm acceleration in PSO Momentum in PSO xvi CHAPTER I INTRODUCTION Computational intelligence approaches based upon the psychosocial studies inspired from either the human or animal society have been the subject of the emerging research known as swarm intelligence. There has been some research in the area of swarm intelligence focused on optimization in the spirit of the particle swarm [1], ant colony system [2] and cultural algorithms [3]. While the population based heuristics adopted in swarm intelligence do not mathematically guarantee to always find the global optimum of the search space, they perform greatly well in different types of optimization problems. Particle swarm optimization (PSO) is an imitation of the collaborative behavior of the birds flying together with the means of their information exchange, while ant colony is based on the fact that individual ants interact with each other through their pheromone trails.