A Survey on Accelerating Evolutionary Computation Approaches

Aus de_evolutionary_art_org
Wechseln zu: Navigation, Suche


Yan Pei and Hideyuki Takagi: A Survey on Accelerating Evolutionary Computation Approaches. 2nd International Conference of Soft Computing and Pattern Recognition (SoCPaR 2011), Dalian, China, pp.201-206 (Oct. 14-16, 2011).




In this paper, we review the research on acceleration convergence approaches of evolutionary computation (EC) and its concrete application in the academy and industry. Evolutionary computation uses iterative progress, which is often inspired by biological mechanisms of evolution, to solve the problems that are multi-modal, multi-objective, discontinuous, non-differential, noisy and not well-defined. In this survey, many acceleration approaches are summarized and clustered in recent two decades. Applications of the acceleration approaches are included. We propose three promising research directions and their concrete approaches. These include including search space landscape approximation, search space projection and search strategy study, and comprise the main further research directions to be implemented an efficient EC search. Finally, we discuss the future research on accelerating convergence approaches of EC, and motivate some new approaches.

Extended Abstract


Used References

Goldberg, D. E., "Genetic Algorithms in Search", Optimization & Machine Learning, Boston, MA: Addison-Wesley (1989).

Holland, J., "Adaptation in Natural and Artificial Systems", Ann Arbor: The University of Michigan Press (1975).

Michalewicz, Z., "Genetic Algorithms + Data Structures = Evolution Programs", Springer-Verlag (1996).

Schwefel, H. P., "Evolutions Strategie und Numerische Optimierung", Ph. D. thesis (1975).

Schwefel, H. P., "Numerical Optimization of Computer Models", Wiley Chichester (1981).

Schwefel, H. P., "Evolution Optimum Seeking", Sixth Generation Computer Technology Series, John Wiley and Sons (1995).

Fogel, L. J., "Autonomous Automata", Industrial Research, Vol. 4, pp. 14-19(1962).

Koza, J., "Genetic Programming", On the Programming of Computers by Means of Natural Selection, The MIT Press (1992). http://dx.doi.org/10.1007/0-387-28356-0_5

Fogel, D. B., "System Identification Trough Simulated Evolution", A Machine Learning Approach, USA: Ginn Press (1991).

Wong, K. P., Li A., and Law T. M. Y., "Advanced constrained genetic algorithm load flow method", Generation, Transmission and Distribution, IEE Proc., Vol. 146, No. 6, pp. 609-616(1999). http://dx.doi.org/10.1049/ip-gtd:19990638

Buchtala, O., Klimek, M., and Sick, B., "Evolutionary Optimization of Radial Basis Function Classifiers for Data Mining Applications", IEEE Trans. on Syst. Man, Cybern., Part B, Vol. 35, No. 5, pp. 928-947(2005). http://dx.doi.org/10.1109/TSMCB.2005.847743

Sheu S.-T. and Chuang Y.-R., "A Pipeline-Based Genetic Algorithm Accelerator for Time-Critical Processes in Real-Time Systems", IEEE Trans. on Computers, Vol. 55, No. 11, pp. 1435-1448(2006). http://dx.doi.org/10.1109/TC.2006.171

Wong K. P., Li A., and Law T. M. Y., "Development of Constrained-Genetic-Algorithm Load-Flow Method", IEE Proc., Generation, Transmission and Distribution, Vol. 144, pp. 91-99(1997). http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=591191&navigation=1

Song Y. H., and Chou C. S. V., "Advanced Engineered-Conditioning Genetic Approach to Power Economic Dispatch", IEE Proc., Gener. Transm. Distrib., Vol. 144, No. 3, pp. 285-292(1997). http://dx.doi.org/10.1049/ip-gtd:19970944

Potter W. D., Miller J. A., Tonn B. E., Gandham R. V., and Lapena C. N., "Improving the reliability of heuristic multiple fault diagnosis via the EC-based genetic algorithm", J. of Applied Intelligence, Vol. 2, pp. 5-23, Springer (1992). http://dx.doi.org/10.1007/BF00058573

Miller J. A., Potter W. D., Gandham R. V. and Lapena C. N., "An Evaluation of Local Improvement Operators for Genetic Algorithms", IEEE Trans. on Syst. Man, Cybern., Vol. 23 pp. 1340-1351(1993). http://dx.doi.org/10.1109/21.260665

David Edward Goldberg, "Genetic Algorithms in Search, Optimization, and Machine Learning", Reading MA: Addison-Wesley, (1989).

Kim J.-H., Chae H.-K., Jeon J.-Y., and Lee S.-W., "Identification and Control of Systems with Friction using Accelerated Evolutionary Programming", IEEE Control Systems Magazine, Vol. 16, pp 38-47(1996). http://dx.doi.org/10.1109/37.526914

Bhandaarl D., and Murthy C. A., "Genetic Algorithm with Elitist Model and Its Convergence", Int. J. Pattern Recognition and Artificial Intelligence, Vol. 10, No. 5, pp. 731-734(1996). http://dx.doi.org/10.1142/S0218001496000438

Zitzler E., Deb K., and Thiele L., "Comparison of Multiobjective Evolutionary Algorithms: Empirical Results" Evolutionary Computation, Vol. 8, No. 2, pp. 173-195(2000). http://dx.doi.org/10.1162/106365600568202

Cui S., Mohan A., and Weile D. S., "Pareto Optimal Design of Absorbers Using a Parallel Elitist Nondominated Sorting Genetic Algorithm and the Finite Element-Boundary Integral Method", IEEE Trans. on Antennas and Propagation, Vol. 53, No. 6, pp. 2099-2107(2005). http://dx.doi.org/10.1109/TAP.2005.848477

Carretero J. A., and Nahon M. A., "Solving Minimum Distance Problems with Convex or Concave Bodies Using Combinatorial Global Optimization Algorithms", IEEE Trans. on Syst. Man, Cybern., Part B, Vol. 35, No. 6, pp. 1144-1155(2005). http://dx.doi.org/10.1109/TSMCB.2005.850172

Mantawy A. H., Abdel-Magid Y. L. and Selim S. Z., "Integrating Genetic Algorithms, Tabu Search, and Simulated Annealing for the Unit Commitment Problem", IEEE Trans. on Power Systems, Vol. 14, No. 3, pp. 829-836(1999). http://dx.doi.org/10.1109/59.780892

Mehrdad Hakimi-Asiabara, Seyyed Hassan Ghodsypoura, and Reza Kerachianb, "Multi-Objective Genetic Local Search Algorithm Using Kohonen's Neural Map", Computers and Industrial Engineering, Vol. 56, No. 4, pp. 1566-1576(2009). http://dx.doi.org/10.1016/j.cie.2008.10.010

Lahiri A., and Chakravorti S., "Electrode-Spacer Contour Optimization by ANN Aided Genetic Algorithm", IEEE Trans. on Dielectrics and Electrical Insulation, Vol. 11, No. 6, pp. 964-975(2004). http://dx.doi.org/10.1109/TDEI.2004.1387819

Hajji O., Brisset S., and Brochet P., "A Stop criterion to Accelerate Magnetic Optimization Process Using Genetic Algorithms and Finite Element Analysis", IEEE Trans. on Magnetics, Vol. 39, No. 3, pp. 1297-1300(2003). http://dx.doi.org/10.1109/TMAG.2003.810209

Beasley D., Bull D. R., and Martin R. R., "An Overview of Genetic Algorithms, Part 1: Fundamentals", Univ. Comput., Vol. 15, pp. 58-69(1993).

Rudolph G., "Convergence Analysis of Canonical Genetic Algorithms", IEEE Trans. on Neural Networks, Vol. 5, pp. 96-101(1994). http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=265964&navigation=1

Grefenstette J., "Optimization of Control Parameters for Genetic Algorithms", IEEE Trans. on Syst. Man, Cybern., Vol. 16, pp. 122-128(1986). http://dx.doi.org/10.1109/TSMC.1986.289288

Zhou Z. Z., Ong Y. S., Nair P. B., Keane J. A., and Lum Y. K., "Combining Global and Local Surrogate Models to Accelerate Evolutionary Optimization", IEEE Trans. on Syst. Man, Cybern., Part C: Applications and Reviews, Vol. 37, No. 1, pp. 66-76(2007). http://dx.doi.org/10.1109/TSMCC.2005.855506

Wang Y., Cai Z. X., Guo G. Q., and Zhou Y. R., "Multiobjective Optimization and Hybrid Evolutionary Algorithm to Solve Constrained Optimization Problems", IEEE Trans. on Syst. Man, Cybern., Part B, Vol. 37, No. 3, pp. 560-575(2007). http://dx.doi.org/10.1109/TSMCB.2006.886164

Takagi H., Ingu T., and Ohnishi K., "Accelerating a GA Convergence by Fitting a Single-Peak Function", J. of Japan Society for Fuzzy Theory and Intelligent Informatics, vol. 15, no. 2, pp. 219-229(2003).

Goldberg D. E., Korb B., and Deb K., "Messy Genetic Algorithms: Motivation, Analysis, and First Result", Complex System, Vol. 3, 493-530(1988).

Whitley D., Mathias K., and Fitzhorn P., "Delta Coding: an Interative Search Strategy for Genetic Algorithms", Proc. Of 4th Int. Conf. on Genetic Algorithms, pp. 77-84, San Mateo, CA (1991).

Schraudolph N. N., and Belew R. K., "Dynamic Parameter Encoding for Genetic Algorithms", Machine Learning, Vol. 9, No. 1, pp. 9-22(1992). [CrossRef]

Eshelman L., and Shaffer J. D., "Real-coded Genetic Algorithms and Interval Schemata", In Whitley (Ed.), Foundations of Genetic Algorithm 2, Los Altos, CA, pp. 187-202, Morgan Kaufmann (1993).

Zadeh Lotfi A., "Fuzzy Logic, Neural Networks, and Soft Computing", Communications of the ACM, Vol. 37 No. 3, pp. 77-84(1994). http://dx.doi.org/10.1145/175247.175255

Hideyuki Takagi, "Introduction to fuzzy systems, neural networks, and genetic algorithms", in Intelligent Systems: Fuzzy Logic, Neural Networks, and Genetic Algorithms, Ch.1, pp. 1-33, edited by D. Ruan, Kluwer Academic Publishers (Norwell, Massachusetts, USA), (September, 1997). http://dx.doi.org/10.1007/978-1-4615-6191-0_1

Hideyuki Takagi, "Fusion Technology of Neural Networks and Fuzzy Systems: A Chronicled Progression from the Laboratory to Our Daily Lives", International Journal of Applied Mathematics and Computer Science, Vol. 10, No. 4, pp. 647-673(2000).

Pei Y. and Takagi, H., "Accelerating Evolutionary Computation with Elite Obtained in Projected One-Dimensional Spaces", 5th Int. Conf. on Genetic and Evolutionary Computing, Kimmen Taiwan (ICGEC2011), accepted (Aug. 29-Spt. 1, 2011). http://dx.doi.org/10.1109/ICGEC.2011.30


Full Text

[extern file]

intern file

Sonstige Links