›› 2013, Vol. 28 ›› Issue (4): 720-731.doi: 10.1007/s11390-013-1370-0

Special Issue: Artificial Intelligence and Pattern Recognition

• Artificial Intelligence and Pattern Recognition • Previous Articles     Next Articles

Parameter Control of Genetic Algorithms by Learning and Simulation of Bayesian Networks —— A Case Study for the Optimal Ordering of Tables

Concha Bielza, Member, IEEE, Juan A. Fernández del Pozo, and Pedro Larrañaga, Member, IEEE   

  1. Computational Intelligence Group, Department of Artificial Intelligence, Technical University of Madrid, 28660 Boadilla del Monte, Madrid, Spain
  • Received:2012-06-15 Revised:2013-05-27 Online:2013-07-05 Published:2013-07-05
  • Supported by:

    This work has been partially supported by the Spanish Ministry of Economy and Competitiveness under Grant No. TIN2010-20900-C04-04 and Cajal Blue Brain.

Parameter setting for evolutionary algorithms is still an important issue in evolutionary computation. There are two main approaches to parameter setting: parameter tuning and parameter control. In this paper, we introduce self-adaptive parameter control of a genetic algorithm based on Bayesian network learning and simulation. The nodes of this Bayesian network are genetic algorithm parameters to be controlled. Its structure captures probabilistic conditional (in)dependence relationships between the parameters. They are learned from the best individuals, i.e., the best configurations of the genetic algorithm. Individuals are evaluated by running the genetic algorithm for the respective parameter configuration. Since all these runs are time-consuming tasks, each genetic algorithm uses a small-sized population and is stopped before convergence. In this way promising individuals should not be lost. Experiments with an optimal search problem for simultaneous row and column orderings yield the same optima as state-of-the-art methods but with a sharp reduction in computational time. Moreover, our approach can cope with as yet unsolved high-dimensional problems.

[1] De Jong K A. An analysis of behavior of a class of geneticadaptive systems [Ph.D. Thesis]. University of Michigan,USA, 1975.

[2] Grefenstette J J. Optimization of control parameters for ge-netic algorithms. IEEE Transactions on Systems, Man andCybernetics, 1986, 16(1): 122-128.

[3] Wolpert D, Macready W. No free lunch theorems for opti-mization. IEEE Transactions on Evolutionary Computation,1997, 1(1): 67-82.

[4] Eiben A E, Michalewicz Z, Schoenauer M, Smith J E. Param-eter control in evolutionary algorithms. In Studies in Com-putational Intelligence 54, Lobo F G, Lina C F, MichalewiczZ et al. (eds.), Springer, 2007, pp.19-46.

[5] de Lima E B, Pappa G L, de Almeida J M et al. Tuninggenetic programming parameters with factorial designs. InProc. 2010 IEEE Congress on Evolutionary Computation,July 2010.

[6] Rojas I, González J, Pomares H et al. Statistical analysisof the main parameters involved in the design of a geneticalgorithm. IEEE Transactions on Systems, Man, and Cy-bernetics —— Part C, Applications and Reviews, 2002, 32(1):31-37.

[7] Czarn A, MacNish C, Vijayan K et al. Statistical exploratoryanalysis of genetic algorithms: The importance of interac-tion. IEEE Trans. Evolutionary Computation, 2004, 8(4):405-421.

[8] Smit S K, Eiben A E. Parameter tuning of evolutionary algo-rithms: Generalist vs. specialist. In Lecture Notes in Com-puter Science 6024, Di Chio C, Cagnoni S, Cotta C et al.(eds.), Springer, 2010, pp.542-551.

[9] Rechenberg I. Evolutionsstrategie: Optimierung Technis-cher Systeme nach Prinzipien der Biologischen Evolution.Stuttgart, Germany: Frommann-Holzboog, 1973. (In Ger-man)

[10] Santana R, Larrañaga P, Lozano J A. Adaptive estimationof distribution algorithms. In Studies in Computational In-telligence 136, Cotta C, Sevaux M, Sorensen K et al. (eds.),Springer, 2008, pp.177-197.

[11] Kramer O. Self-Adaptive Heuristics for Evolutionary Compu-tation. Berlin, Germany: Springer-Verlag, 2008.

[12] Angeline P J. Adaptive and self-adaptive evolutionary com-putation. In Computational Intelligence: A Dynamic SystemPerspective, Palaniswami Y, Attikiouzel R, Marks R et al.(eds.), IEEE, 1995, pp.152-161.

[13] Hinterding R, Michalewicz Z, Eiben A E. Adaptation in evo-lutionary computation: A survey. In Proc. the 4th IEEEConf. Evolutionary Computation, Apr. 1997, pp.65-69.

[14] Smith J. Self adaptation in evolutionary algorithms [Ph.D.Thesis]. University of the West of England, UK, 1997.

[15] Friesleben B, Hartfelder M. Optimisation of genetic algo-rithms by genetic algorithms. In Proc. Artificial Neural Net-works and Genetic Algorithms, Apr. 1993, pp.392-399.

[16] Back T. Evolutionary Algorithms in Theory and Practice:Evolution Strategies, Evolutionary Programming, Genetic Al-gorithms. New York, USA: Oxford University Press, 1996.

[17] Rechenberg I. Evolutionsstrategie'94. Stuttgart, Germany:Frommann-Holzboog, 1994.

[18] Larrañaga P, Lozano J A. Estimation of Distribution Algo-rithms: A New Tool for Evolutionary Computation. NewYork, USA: Kluwer Academic Publishers, 2002.

[19] Peña J M, Robles V, Larrañaga P et al. GA-EDA: Hybridevolutionary algorithm using genetic and estimation of distri-bution algorithms. In Proc. the 17th International Confer-ence on Industrial and Engineering Applications of ArtificialIntelligence and Expert Systems, May 2004, pp.361-371.

[20] Santana R, Larrañaga P, Lozano J A. Combining variableneighborhood search and estimation of distribution algo-rithms in the protein side chain placement problem. Journalof Heuristics, 2008, 14(5): 519-547.

[21] Sun J, Zhang Q, Tsang E. DE/EDA: A new evolutionary al-gorithm for global optimisation. Information Sciences, 2005,169(3/4): 249-262.

[22] Dong W, Yao X. NichingEDA: Utilizing the diversity insidea population of EDAs for continuous optimization. In Proc.the 2008 IEEE Congress on Evolutionary Computation, June2008, pp.1260-1267.

[23] Nannen V, Smit S K, Eiben A E. Costs and benefits of tun-ing parameters of evolutionary algorithms. In Proc. the 10thInt. Conf. Parallel Problem Solving from Nature, Sept. 2008,Vol.5199, pp.528-538.

[24] Bielza C, Fernández del Pozo J A, Larrañaga P et al. Mul-tidimensional statistical analysis of the parameterization of agenetic algorithm for the optimal ordering of tables. ExpertSystems with Applications, 2010, 37(1): 804-815.

[25] Etxeberria R, Larrañaga P. Global optimization usingBayesian networks. In Proc. the 2nd Symposium on Arti-ficial Intelligence, March 1999, pp.332-339.

[26] Pelikan M, Goldberg D E, Cantu-Paz E. BOA: The Bayesianoptimization algorithm. In Proc. the Genetic and Evolution-ary Computation Conference, July 1999, pp.525-532.

[27] Yuan B, Gallagher M. Combining meta-EAs and racing fordifficult EA parameter tuning tasks. In Studies in Compu-tational Intelligence 54, Lobo F J, Lima C F, Michalewicz Z(eds.), Springer, 2007, pp.121-142.

[28] Lobo F G, Lima C F. Adaptive population sizing schemes ingenetic algorithms. In Studies in Computational Intelligence54, Lobo F, Lima C F, Michalewicz Z (eds.), Springer, 2007,pp.185-204.

[29] Friedman N, Yakhini Z. On the sample complexity of learningBayesian networks. In Proc. the 12th Conference on Uncer-tainty in Artificial Intelligence, Aug. 1996, pp.274-282.

[30] Lam W, Bacchus F. Learning Bayesian belief networks: Anapproach based on the MDL principle. Computational Intel-ligence, 1994, 10(3): 269-293.

[31] Henrion M. Propagating uncertainty in Bayesian networks byprobabilistic logic sampling. In Proc. the 2nd Annual Conf.Uncertainty in Artificial Intelligence, Aug. 1986, pp.149-164.

[32] Bertin J. Graphics and Graphic Information Processing, UK:Walter de Gruyter & Co, 1981.

[33] Johnson D S, Papadimitriou C H. Computational complexity.In The Traveling Salesman Problem, Lawler E L, Lenstra JK, Rinnooy Kan A et al. (eds.), John Wiley & Sons, 1985,pp.37-85.

[34] Niermann S. Optimizing the ordering of tables with evolution-ary computation. The American Statistician, 2005, 59(1):41-46.

[35] Larrañaga P, Kuijpers C M H, Murga R H et al. Geneticalgorithms for the travelling salesman problem: A review ofrepresentations and operators. Artificial Intelligence Review,1999, 13(2): 129-170.

[36] Croes G A. A method for solving traveling-salesman prob-lems. Operations Research, 1958, 6(6): 791-812.

[37] Pearl J. Probabilistic Reasoning in Intelligent Systems: Net-works of Plausible Inference. San Francisco, USA: MorganKaufmann, 1988.
No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] Jin Lan; Yang Yuanyuan;. A Modified Version of Chordal Ring[J]. , 1986, 1(3): 15 -32 .
[2] Meng Liming; Xu Xiaofei; Chang Huiyou; Chen Guangxi; Hu Mingzeng; Li Sheng;. A Tree-Structured Database Machine for Large Relational Database Systems[J]. , 1987, 2(4): 265 -275 .
[3] Fan Zhihua;. Vectorization for Loops with Three-Forked Jumps[J]. , 1988, 3(3): 186 -202 .
[4] Guo Qingping; Y. Paker;. Communication Analysis and Granularity Assessment for a Transputer-Based System[J]. , 1990, 5(4): 347 -362 .
[5] Lin Shan;. Using a Student Model to Improve Explanation in an ITS[J]. , 1992, 7(1): 92 -96 .
[6] Shen Yidong;. Form alizing Incomplete Knowledge in Incomplete Databases[J]. , 1992, 7(4): 295 -304 .
[7] Jin Guohua; Yang Xuejun; Chen Fujie;. Loop Staggering,Loop Compacting:Restructuring Techniques for Thrashing Problem[J]. , 1993, 8(1): 49 -57 .
[8] Gu Junzhong;. An Object-Oriented Transaction Model[J]. , 1993, 8(4): 3 -20 .
[9] Zhou Yong; Tang Zesheng;. Constructing Isosurfaces from 3D Data Sets Taking Account of Depth Sorting of Polyhedra[J]. , 1994, 9(2): 117 -127 .
[10] Liao Lejian; Shi Zhongzhi;. Minimal Model Semantics for Sorted Constraint Representation[J]. , 1995, 10(5): 439 -446 .

ISSN 1000-9000(Print)

         1860-4749(Online)
CN 11-2296/TP

Home
Editorial Board
Author Guidelines
Subscription
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
Tel.:86-10-62610746
E-mail: jcst@ict.ac.cn
 
  Copyright ©2015 JCST, All Rights Reserved