Concurrent Societies Based on Genetic Algorithm and Particle Swarm Optimization
Hrvoje Markovic, Fangyan Dong, and Kaoru Hirota
Department of Computational Intelligence and Systems Science, Tokyo Institute of Technology, G3-49, 4259 Nagatsuta, Midori-ku, Yokohama 226-8502, Japan
A parallel multi-population based metaheuristic optimization framework, called Concurrent Societies, inspired by human intellectual evolution, is proposed. It uses population based metaheuristics to evolve its populations, and fitness function approximations as representations of knowledge. By utilizing iteratively refined approximations it reduces the number of required evaluations and, as a byproduct, it produces models of the fitness function. The proposed framework is implemented as two Concurrent Societies: one based on genetic algorithm and one based on particle swarm optimization both using k -nearest neighbor regression as fitness approximation. The performance is evaluated on 10 standard test problems and compared to other commonly used metaheuristics. Results show that the usage of the framework considerably increases efficiency (by a factor of 7.6 to 977) and effectiveness (absolute error reduced by more than few orders of magnitude). The proposed framework is intended for optimization problems with expensive fitness functions, such as optimization in design and interactive optimization.
-  R. Chelouah and P. Siarry, “A Continuous Genetic Algorithm Designed for the Global Optimization of Multimodal Functions,” J. of Heuristics, Vol.6, pp. 191-213, 2000.
-  S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, “Optimization by Simulated Annealing,” Science, New Series, Vol.220, No.4598, pp. 671-680, 1983.
-  J. Kennedy and R. C. Eberhart, “Swarm Intelligence,” Morgan Kaufmann, San Francisco, 2001.
-  K. V. Price, R. M. Storn, and J. A. Lampinen, “Differential Evolution: A practical approach to global optimization,” Springer, 2005.
-  H. Y. K. Lau and W. W. P. Tsang, “A Parallel Immune Optimization Algorithm for Numeric Function Optimization,” Evolutionary Intelligence, Vol.1, pp. 171-185, 2008.
-  C. Zang, J. Ning, S. Lu, D. Ouyang, and T. Ding, “A Novel Hybrid Differential Evolution and Particle Swarm Optimization Algorithm for Unconstrained Optimization,” Operations Research Letters, Vol.37, No.2, pp. 117-122, 2009.
-  A. H. Wright and J. N. Richter, “Strong Recombination, Weak Selection, and Mutation,” in Proc. 2006 Genetic and Evolutionary Computation Conf., 2006, pp. 1369-1376.
-  T. T. Nguyen and X. Yao, “An Experimental Study of Hybridizing Cultural Algorithms and Local Search,” Int. J. of Neural Systems, Vol.18, No.1, pp. 1-18, 2008.
-  J. J. Liang and P. N. Suganthan, “Dynamic Multi-Swarm Particle Swarm Optimizer with Local Search,” in Proc. 2005 IEEE Congress on Evolutionary Computation, 2005, pp. 522-528.
-  A. A. Guinta and L.T. Watson, “A Comparison of Approximation Modeling Techniques: Polynomial Versus Interpolating Models,” in Proc. 7th AIAA/USAF/NASA/ISSMO Symposium on Multidisciplinary Analysis and Optimization, 1998, pp. 1-13.
-  Z. Zhou, Y. S. Ong, P. B. Nair, A. J. Keane, and K. Y. Lum, “Combining Global and Local Surrogate Models to Accelerate Evolutionary Optimization,” IEEE Trans. on Systems, Man, and Cybernetics Part C, Vol.37, No.1, pp. 66-76, 2007.
-  A. Ratle, “Kriging as a Surrogate Fitness Landscape in Evolutionary Optimization,” Artificial Intelligence for Engineering Design Analysis and Manufacturing, Vol.15, No.1, pp. 37-49, 2001.
-  Y. Jin, M. Olhofer and B. Sendhoff, “A Framework for Evolutionary Optimization with Approximate Fitness Functions,” IEEE Trans. on Evolutionary Computation, Vol.6, No.5, pp. 481-494, 2002.
-  Y. Jin, “A Comprehensive Survey of Fitness Approximation in Evolutionary Computation,” Soft Computing, Vol.9, No.1, pp. 3-12, 2005.
-  Y. S. Ong, Z. Zhou, and D. Lim, “Curse and Blessing of Uncertainty in Evolutionary Algorithm Using Approximation,” in. Proc. 2006 IEEE Congress on Evolutionary Computation, 2006, pp. 2928-2935.
-  D. Eby, R. C. Averill, R. F. Punch, and E. D. Goodman, “Optimal Design of Flywheels Using an Injection Island Genetic Algorithm,” Artificial Intelligence for Engineering Design, Analysis and Manufacturing, Vol.13, No.5, pp. 327-340, 1999.
-  M. Sefrioui and J. Periaux, “A Hierarchical Genetic Algorithm Using Multiple Models for Optimization,” in Parallel Problem Solving from Nature, Lecture Notes in Computer Science, Vol.1917, pp. 879-888, 2000.
-  K. Socha and M. Dorigo, “Ant Colony Optimization for Continuous Domains,” European J. of Operational Research, Vol.185, No.3, pp. 1155-1173, 2008.
-  I. G. Tsoulosa and I. E. Lagaris, “MinFinder: Locating all the local minima of a function,” Computer Physics Communications, Vol.174, No.2, pp. 166-179, 2006.