• Articles • Previous Articles     Next Articles

Histogram-Based Estimation of Distribution Algorithm: A Competent Method for Continuous Optimization

Nan Ding1, Shu-De Zhou2, and Zeng-Qi Sun2   

  1. 1Department of Electronic Engineering, Tsinghua University, Beijing 100084, China 2Department of Computer Science and Technology, Tsinghua University, Beijing 100084, China
  • Revised:2007-11-06 Online:2008-01-15 Published:2008-01-10

Designing efficient estimation of distribution algorithms for optimizing complex continuous problems is still a challenging task. This paper utilizes histogram probabilistic model to describe the distribution of population and to generate promising solutions. The advantage of histogram model, its intrinsic multimodality, makes it proper to describe the solution distribution of complex and multimodal continuous problems. To make histogram model more efficiently explore and exploit the search space, several strategies are brought into the algorithms: the surrounding effect reduces the population size in estimating the model with a certain number of the bins and the shrinking strategy guarantees the accuracy of optimal solutions. Furthermore, this paper shows that histogram-based EDA (Estimation of distribution algorithm) can give comparable or even much better performance than those predominant EDAs based on Gaussian models.

Key words: multimedia; demand priority MAC protocol; simulation; performance; evaluation;

[1] Larra\~naga P, Lozano J A. Estimation of Distribution Algorithms: A New Tool for Evolutionary Computation. Kluwer Academic Publishers, 2002.

[2] Pelikan M. Hierarchical Bayesian Optimization Algorithm: Toward A New Generation of Evolutionary Algorithms. Springer-Verlag, 2005.

[3] O\v cen\'a\v sek J. Parallel estimation of distribution algorithms
[Dissertation]. Brno University of Technology, 2002.

[4] Larra\~naga P, Etxeberria R, Lozano J A, Pe\~na J M. Optimization by learning and simulation of Bayesian and Gaussian networks. Technical Report EHU-KZAA-IK-4/99, University of the Basque Country, 1999.

[5] Larra\~naga P, Etxeberria R, Lozano J A, Pe\v na J M. Optimization in continuous domains by learning and simulation of Gaussian networks. In -\it Proc. the Genetic and Evolutionary Computation Conference}, Las Vegas, Nevada, 2000, pp.201--204.

[6] Sebag M, Ducolombier A. Extending Population-Based Incremental Learning to Continuous Search Spaces. Parallel Problem Solving from Nature --PPSN V, Springer-Verlag, 1998, pp.418--427.

[7] Larra\~naga P, Lozano J A, Bengoetxea E. Estimation of Distribution Algorithms based on multivariate normal and Gaussian networks. Technical report KZZA-IK-1-01, University of the Basque Country, 2001.

[8] Bosman P, Thierens D. Expanding from Discrete to Continuous Estimation of Distribution Algorithms: IDEA. Parallel Problem Solving From Nature --PPSN VI, 2000, pp.767--776.

[9] Ahn C W. Real-coded Bayesian optimization algorithm. In -\it Proc. Advances in Evolutionary Algorithms: Theory, Design and Practice}, 2006, pp.85--124.

[10] Tsutsui S, Pelikan M, Goldberg D E. Evolutionary algorithm using marginal histogram models in continuous domain. In -\it Proc. the 2001 Genetic and Evolutionary Computation Conference Workshop}, San Francisco, CA, 2001, pp.230--233.

[11] Petri K, Petri M. Information-theoretically optimal histogram density estimation. HIIT Technical Reports 2006-2, Helsinki Institute for Information Technology, 2006.

[12] Pelikan M, David E G, Tsutsui S. Combining the strengths of the Bayesian optimization algorithm and adaptive evolution strategies. IlliGAL Report No. 2001023, 2001.

[13] Yuan B, Gallagher M. Playing in continuous spaces: Some analysis and extension of population-based incremental learning. In -\it Proc. IEEE Congress on Evolutionary Computation}, 2003, pp.443--450.

[14] Ding N, Zhou S, Sun Z. Optimizing continuous problems using estimation of distribution algorithms based on histogram model. In -\it Proc. the 6th Conference of Simulated Evolution and Learning}, Hefei, China, 2006, pp.545--552.

[15] Bosman P, Thierens D. Continuous iterated density estimation evolutionary algorithms within the IDEA framework. In -\it Proc. the Optimization by Building and Using Probabilistic Models OBUPM Workshop at GECCO-2000}, San Francisco, California, 2000, pp.197--200.

[16] Lu Q, Yao X. Clustering and learning Gaussian distribution for continuous optimization. -\it IEEE Transactions on Systems, Man and Cybernetics-Part C}, 2005, 35(2): 195--204.
[1] Louis Cianciullo and Hossein Ghodosi. Unconditionally Secure Oblivious Polynomial Evaluation: A Survey and New Results [J]. Journal of Computer Science and Technology, 2022, 37(2): 443-458.
[2] Zhou Zhang, Pei-Quan Jin, Xiao-Liang Wang, Yan-Qi Lv, Shou-Hong Wan, Xi-Ke Xie. COLIN: A Cache-Conscious Dynamic Learned Index with High Read/Write Performance [J]. Journal of Computer Science and Technology, 2021, 36(4): 721-740.
[3] Songjie Niu, Shimin Chen. TransGPerf: Exploiting Transfer Learning for Modeling Distributed Graph Computation Performance [J]. Journal of Computer Science and Technology, 2021, 36(4): 778-791.
[4] Reza Jafari Ziarani, Reza Ravanmehr. Serendipity in Recommender Systems: A Systematic Literature Review [J]. Journal of Computer Science and Technology, 2021, 36(2): 375-396.
[5] Jason Liu, Pedro Espina, Xian-He Sun. A Study on Modeling and Optimization of Memory Systems [J]. Journal of Computer Science and Technology, 2021, 36(1): 71-89.
[6] Heng Bu, Ming-Kai Dong, Ji-Fei Yi, Bin-Yu Zang, Hai-Bo Chen. Revisiting Persistent Indexing Structures on Intel Optane DC Persistent Memory [J]. Journal of Computer Science and Technology, 2021, 36(1): 140-157.
[7] Jian-Bin Fang, Xiang-Ke Liao, Chun Huang, De-Zun Dong. Performance Evaluation of Memory-Centric ARMv8 Many-Core Architectures:A Case Study with Phytium 2000+ [J]. Journal of Computer Science and Technology, 2021, 36(1): 33-43.
[8] Hui-Na Chao, Hua-Wei Li, Xiaoyu Song, Tian-Cheng Wang, Xiao-Wei Li. Evaluating and Constraining Hardware Assertions with Absent Scenarios [J]. Journal of Computer Science and Technology, 2020, 35(5): 1198-1216.
[9] Hua Wang, Xiao-Yu He, Liu-Yang Chen, Jun-Ru Yin, Li Han, Hui Liang, Fu-Bao Zhu, Rui-Jie Zhu, Zhi-Min Gao, Ming-Liang Xu. Cognition-Driven Traffic Simulation for Unstructured Road Networks [J]. Journal of Computer Science and Technology, 2020, 35(4): 875-888.
[10] Sven Pullwitt, Robert Hartung, Ulf Kulau, Lars Wolf. Towards Accurate Bit Error Simulation in Wireless Sensor Networks Including Environmental Influences [J]. Journal of Computer Science and Technology, 2020, 35(4): 809-824.
[11] Lan Huang, Da-Lin Li, Kang-Ping Wang, Teng Gao, Adriano Tavares. A Survey on Performance Optimization of High-Level Synthesis Tools [J]. Journal of Computer Science and Technology, 2020, 35(3): 697-720.
[12] Hong-Mei Wei, Jian Gao, Peng Qing, Kang Yu, Yan-Fei Fang, Ming-Lu Li. MPI-RCDD: A Framework for MPI Runtime Communication Deadlock Detection [J]. Journal of Computer Science and Technology, 2020, 35(2): 395-411.
[13] Wen-Yan Chen, Ke-Jiang Ye, Cheng-Zhi Lu, Dong-Dai Zhou, Cheng-Zhong Xu. Interference Analysis of Co-Located Container Workloads: A Perspective from Hardware Performance Counters [J]. Journal of Computer Science and Technology, 2020, 35(2): 412-417.
[14] Zheng-Hao Jin, Haiyang Shi, Ying-Xin Hu, Li Zha, Xiaoyi Lu. CirroData: Yet Another SQL-on-Hadoop Data Analytics Engine with High Performance [J]. Journal of Computer Science and Technology, 2020, 35(1): 194-208.
[15] Marc-André Vef, Nafiseh Moti, Tim Süß, Markus Tacke, Tommaso Tocci, Ramon Nou, Alberto Miranda, Toni Cortes, André Brinkmann. GekkoFS—A Temporary Burst Buffer File System for HPC Applications [J]. Journal of Computer Science and Technology, 2020, 35(1): 72-91.
Full text



[1] Liu Mingye; Hong Enyu;. Some Covering Problems and Their Solutions in Automatic Logic Synthesis Systems[J]. , 1986, 1(2): 83 -92 .
[2] Chen Shihua;. On the Structure of (Weak) Inverses of an (Weakly) Invertible Finite Automaton[J]. , 1986, 1(3): 92 -100 .
[3] Gao Qingshi; Zhang Xiang; Yang Shufan; Chen Shuqing;. Vector Computer 757[J]. , 1986, 1(3): 1 -14 .
[4] Chen Zhaoxiong; Gao Qingshi;. A Substitution Based Model for the Implementation of PROLOG——The Design and Implementation of LPROLOG[J]. , 1986, 1(4): 17 -26 .
[5] Huang Heyan;. A Parallel Implementation Model of HPARLOG[J]. , 1986, 1(4): 27 -38 .
[6] Min Yinghua; Han Zhide;. A Built-in Test Pattern Generator[J]. , 1986, 1(4): 62 -74 .
[7] Tang Tonggao; Zhao Zhaokeng;. Stack Method in Program Semantics[J]. , 1987, 2(1): 51 -63 .
[8] Min Yinghua;. Easy Test Generation PLAs[J]. , 1987, 2(1): 72 -80 .
[9] Zhu Hong;. Some Mathematical Properties of the Functional Programming Language FP[J]. , 1987, 2(3): 202 -216 .
[10] Li Minghui;. CAD System of Microprogrammed Digital Systems[J]. , 1987, 2(3): 226 -235 .

ISSN 1000-9000(Print)

CN 11-2296/TP

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