×

An efficient genetic algorithm for optimization problems with time-consuming fitness evaluation. (English) Zbl 1359.90157

Summary: In classical genetic algorithm, fitness evaluations are often very expensive or highly time-consuming, especially for some engineering optimization problems. We present an efficient genetic algorithm (GA) by combining clustering methods with an empirical fitness estimating formula. The new individuals are clustered at first, and then only the cluster representatives are really evaluated by its original time-consuming fitness computing processes, and other individuals undergo high efficient fitness evaluating processes by using the empirical fitness estimating formula. To further improve the accuracy of fitness estimations, we present a schema discovery strategy by extracting the common encoding characters from both high-fitness individual group and low-fitness individual group, and then adjust the estimated fitness for each individual based on the matching with the discovered schema. Experiments show that the schema discovery strategy contributes remarkably to the accuracy of fitness estimation. Numerical experiments of some well-known benchmark problems and a practical engineering problem demonstrate that the proposed method could improve the efficiency by over 30% in terms of the times of real fitness evaluations at the similar optimization accuracy of classical genetic algorithm.

MSC:

90C59 Approximation methods and heuristics in mathematical programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] J. Branke and C. Schmidt, Soft Comput. 9(1), 13 (2005). genRefLink(16, ’rf1’, ’10.1007
[2] K. Chellapilla, IEEE Trans. Evolut. Comput. 2(3), 91 (1998). genRefLink(16, ’rf2’, ’10.1109
[3] De Jong, K. [1975] An Analysis of the Behavior of a Class of Genetic Adaptive Systems, PhD thesis, University of Michigan. Available at http://hdl.handle.net/2027.42/ 4507 .
[4] C. H. Du, J. Visual Commun. Image Represent 20(8), 608 (2009). genRefLink(16, ’rf4’, ’10.1016
[5] C. Fang and L. Wang, Comput. Oper. Res. 39(5), 890 (2012). genRefLink(16, ’rf5’, ’10.1016
[6] Y. X. Feng and K. L. Pheng , Expert Syst. Appl. 38 , 8538 ( 2011 ) . genRefLink(16, ’rf6’, ’10.1016
[7] D. B. Fogel , System Identification Through Simulated Evolution: A Machine Learning Approach to Modeling ( Ginn Press , MA , 1991 ) .
[8] S. Forrest and M. Mitchel, Foundations of Genetic Algorithms 2, ed. D. Whitley (Morgan Kaufmann, San Mateo, CA, 1993) pp. 109-126.
[9] B. J. Frey and D. Dueck, Science 315(5814), 972 (2007). genRefLink(16, ’rf9’, ’10.1126
[10] D. E. Goldberg , Genetic Algorithms in Search, Optimization, and Machine Learning ( Addisin-Westly Publishing Company, Inc. , Boston, USA , 1989 ) . · Zbl 0721.68056
[11] J. J. Grefenstette and J. M. Fitzpatrick, Genetic search with approximate function evaluations, Proc. Int. Conf. Genetic Algorithms and Their Applications (1985) pp. 112-120. · Zbl 0679.68161
[12] S. He , BioSystems 78 , 135 ( 2004 ) . genRefLink(16, ’rf12’, ’10.1016
[13] S. Jia, Y. T. Qian and Z. Ji, Band selection for hyperspectral imagery using affinity propagation, Proc. 2008 Digital Image Computing: Techniques and Applications Table of Contents (2008) pp. 137-141.
[14] Y. Jin, Soft Comput. 9(1), 3 (2005). genRefLink(16, ’rf14’, ’10.1007
[15] F. Kang , J. J. Li and Z. Y. Ma , Inform. Sci. 181 , 3508 ( 2011 ) . genRefLink(16, ’rf15’, ’10.1016
[16] S. J. Kiddle, Bioinformatics 26(3), 355 (2010). genRefLink(16, ’rf16’, ’10.1093
[17] H. S. Kim and S. B. Cho, An efficient genetic algorithm with less fitness evaluation by clustering, Proc. IEEE Congress on Evolutionary Computation (2001) pp. 887-894.
[18] J. J. Liang, IEEE Trans. Evolut. Comput 10(3), 281 (2006). genRefLink(16, ’rf18’, ’10.1109
[19] C. J. Liao, Y. L. Tsai and C. W. Chao, Appl. Soft Comput. 11(8), 4521 (2011). genRefLink(16, ’rf19’, ’10.1016
[20] M. Salami and T. Hendtlass, A fitness estimation strategy for genetic algorithms, Proc. 15th Int. Conf. Industrial and Engineering Applications of Artificial Intelligence and Expert Systems: Developments in Applied Artificial Intelligence, IEA/AIE 20022358, LNAI, eds. T. Hendtlass and M. Ali (2002) pp. 502-513. · Zbl 1045.68899
[21] R. Salomon, Lecture Notes in Computer Science 1447 (1998) pp. 113-122.
[22] K. Sastry, D. E. Goldberg and M. Pelikan, Don’t evaluate, inherit, Genetic and Evolutionary Computation Conference, eds. L. Spector (Morgan Kaufmann, San Francisco, USA, 2001) pp. 551-558.
[23] X. H. Shi, Inform. Process. Lett 93(5), 255 (2005). genRefLink(16, ’rf23’, ’10.1016
[24] R. E. Smith, B. A. Dike and S. A. Stegmann, Fitness inheritance in genetic algorithms, Proc. ACM Symp. Applied Computing (1995) pp. 345-350.
[25] P. Vasant, Int. J. Comput. Meth 7(2), 279 (2010). [Abstract] genRefLink(128, ’rf25’, ’000278422700005’);
[26] F. Yang , Evolut. Bioinform. 5 , 137 ( 2009 ) . genRefLink(128, ’rf26’, ’000273813500001’);
[27] X. Yao, Y. Liu and G. Lin, IEEE Trans. Evolut. Comput 3(2), 82 (1999). genRefLink(16, ’rf27’, ’10.1109
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.