Optimization by Estimation of Distribution with DEUM Framework Based on Markov Random Fields

Siddhartha Shakya; John McCall

doi:10.1007/s11633-007-0262-6

July 2007

Article Contents

Siddhartha Shakya and John McCall. Optimization by Estimation of Distribution with DEUM Framework Based on Markov Random Fields. International Journal of Automation and Computing, vol. 4, no. 3, pp. 262-272, 2007. doi: 10.1007/s11633-007-0262-6

Cite as: Siddhartha Shakya and John McCall. Optimization by Estimation of Distribution with DEUM Framework Based on Markov Random Fields. International Journal of Automation and Computing, vol. 4, no. 3, pp. 262-272, 2007. doi: 10.1007/s11633-007-0262-6

Optimization by Estimation of Distribution with DEUM Framework Based on Markov Random Fields

Siddhartha Shakya¹,
John McCall²

1.
Intelligent Systems Research Center, British Telicom, Adastral Park, Ipswich IP5 3RE, UK;
2.
School of Computing, The Robert Gordon University, Aberdeen AB25 1HG, UK

Received: 2007-03-05

Abstract

This paper presents a Markov random field (MRF) approach to estimating and sampling the probability distribution in populations of solutions.The approach is used to define a class of algorithms under the general heading distribution estimation using Markov random fields (DEUM).DEUM is a subclass of estimation of distribution algorithms (EDAs) where interaction between solution variables is represented as an undirected graph and the joint probability of a solution is factorized as a Gibbs distribution derived from the structure of the graph.The focus of this paper will be on describing the three main characteristics of DEUM framework,which distinguishes it from the traditional EDA.They are:1) use of MRF models,2) fitness modeling approach to estimating the parameter of the model and 3) Monte Carlo approach to sampling from the model.
- Estimation of distribution algorithms,
- evolutionary algorithms,
- fitness modeling,
- Markov random fields,
- Gibbs distribution

References

[1]	J.H.Holland.Adaptation in Natural and Artificial Systems,University of Michigan Press,Ann Arbor,MI,1975.
[2]	I.Rechenberg.Evolutionstrategie-optimierung Technischer Systeme nach Prinzipien der biologischen Evolution,Formman-Holzboog,Stuttgart,1973.
[3]	L.J.Fogel.Autonomous Automata.Industrial Research,vol.4,no.1,pp.14-19,1962.
[4]	H.Miihlenbein,G.Paafi.From Recombination of Genes to the Estimation of Distributions:Ⅰ.Binary Parameters.In Proceedings of the 4th International Conference on Parallel Problem Solving from Nature,Berlin,pp.178-187,1996.
[5]	P.Larranaga,J.A.Lozano.Estimation of Distribution Algorithms:a New Tool for Evolutionary Computation,Kluwer Academic Publishers,Boston,2002.
[6]	M.Pelikan,D.E.Goldberg.Hierarchical BOA Solves Ising Spin Glasses and MAXSAT.In Proceedings of the Genetic and Evolutionary Computation Conference,Springer Verlag,Chicago,IL,pp.1275-1286,2003.
[7]	J.A.Lozano,R.Sagarna,P.Larranaga.Solving Job Scheduling with Estimation of Distribution Algorithms.In Estimation of Distribution Algorithms.A New Tool for Evolutionary Computation,P.Larranaga and J.A.Lozano,(eds.),Kluwer Academis Publishers,Norwell,MA,pp.231-242,2001.
[8]	Q.Zhang,J.Sun,E.Tsang.An Evolutionary Algorithm with Guided Mutation for the Maximum Clique Problem.IEEE Transactions on Evolutionary Computation,vol.9,no.2,pp.192-200,2005.
[9]	S.K.Shakya,J.A.W.McCall,D.F.Brown.Updating the Probability Vector Using MRF Technique for a Uni-variate EDA.In Proceedings of the Second Starting AI Researchers' Symposium,Frontiers in Artificial Intelligence and Applications,IOS press,Valencia,Spain,vol.109,pp.15-25,2004.
[10]	R.Santana.Estimation of Distribution Algorithms with Kikuchi Approximation.Evolutonary Computation,vol.13,no.1,pp.67-98,2005.
[11]	R.Kikuchi.A Theory of Cooperative Phenomena.Physical Review,vol.81,no.6,pp.988-1003,1951.
[12]	P.Larranaga,R.Etxeberria,J.A.Lozano,B.Sierra,I.Inza,J.M.Pefia.A Review of the Cooperation between Evolutionary Computation and Probabilistic Graphical Models.In Proceedings of the Second Symposium on Artificial Intelligence,La Habana,pp.314-324,1999.
[13]	M.I.Jordan,editor.Learning in Graphical Models,NATO Science Series.Kluwer Academic Publishers,Dordrecht,1998.
[14]	J.Besag.Spatial Interaction and the Statistical Analysis of Lattice Systems.Journal of the Royal Statistical Society,vol.36,no.2,pp.192-236,1974.
[15]	S.Z.Li.Markov Random Field Modeling in Computer Vision,Springer-Verlag,London,UK,1995.
[16]	K.P.Murphy.Dynamic Bayesian Networks:Representation,Inference and Learning.Ph.D.dissertation,University of California,Berkeley,2002.
[17]	J.M.Hammersley,P.Clifford.Markov Fields on Finite Graphs and Lattices,Unpublished Manuscript,1971.
[18]	D.F.Brown,A.B.Garmendia-Doval,J.A.W.McCall.Markov Random Field Modelling of Royal Road Genetic Algorithms.Lecture Notes in Computer Science,Springer,January,vol.2310,pp.65-78,2002.
[19]	W.H.Press,S.A.Teukolsky,W.T.Vetterling,B.P.Flannery.Numerical Recipes in C:The Art of Scientific Computing,2nd edition,Cambridge University Press,Cambridge,UK,1992.
[20]	S.Shakya,J.McCall,D.Brown.Estimating the Distribution in an EDA.In Proceedings of the International Conference on Adaptive and Natural Computing Algorithms,Coimbra,Portugal,pp.202-205,2005.
[21]	S.Shakya,J.McCall,Brown D.Using a Markov Network Model in a Univariate EDA:An Emperical Cost-Benefit Analysis.In Proceedings of Genetic and Evolutionary Computation Conference,Washington D.C.,USA,pp.727-734,2005.
[22]	S.K.Shakya,J.A.W.McCall,D.F.Brown.Incorporating a Metropolis Method in a Distribution Estimation Using Markov Random Field Algorithm.In Proceedings of IEEE Congress on Evolutionary Computation,Edinburgh,UK,vol.3,pp.2576-2583,2005.
[23]	S.K.Shakya,J.A.W.McCall,D.F.Brown.Solving the Ising Spin Glass Problem Using a Bivariate EDA Based on Markov Random Fields.In Proceedings of IEEE Congress on Evolutionary Computation,Vancouver,Canada,pp.908-915,2006.
[24]	N.Metropolis,A.W.Rosenbluth,M.N.Rosenbluth,A.H.Teller,E Teller.Equations of State Calculations by Fast Computational Machine.Journal of Chemical Physics,vol.21,no.6,pp.1087-1091,1953.
[25]	S.Geman,D.Geman.Stochastic Relaxation,Gibbs Distributions and the Bayesian Restoration of Images.Readings in Computer Vision:Issues,Problems,Principles,and Paradigms,M.A.Fischler,O.Firschein,(eds.),Kaufmann,Los Altos,CA.,pp.564-584,1987.
[26]	M.Pelikan.Bayesian Optimization Algorithm:From Single Level to Hierarchy.Ph.D.dissertation,University of Illinois at Urbana-Champaign,Urbana,IL,2002.Also IlliGAL Report No.2002023.
[27]	S.Baluja.Population-based Incremental Learning:a Method for Integrating Genetic Search Based Function Optimization and Competitive Learning,Technical Report CMU-CS-94-163,Pittsburgh,PA,1994.
[28]	H.H.Hoos,T.Stutzle.Towards a Characterization of the Behaviour of Stochastic Local Search Algorithms for SAT.Artificial Inteiiigence,vol.112,no.1-2,pp.213-232,1999.
[29]	R.Santana.Probabilistic Modeling Based on Undirected Graphs in Estimation Distribution Algorithms.Ph.D.dissertation,Institute of Cybernetics,Mathematics and Physics,Havana,Cuba,2003.

Metrics

[1]	R. Bharathi, R. Selvarani. Hidden Markov Model Approach for Software Reliability Estimation with Logic Error . International Journal of Automation and Computing, 2020, 17(2): 305-320. doi: 10.1007/s11633-019-1214-7
[2]	Madhusmita Panda, Bikramaditya Das, Bidyadhar Subudhi, Bibhuti Bhusan Pati. A Comprehensive Review of Path Planning Algorithms for Autonomous Underwater Vehicles . International Journal of Automation and Computing, 2020, 17(3): 321-352. doi: 10.1007/s11633-019-1204-9
[3]	Khaled M. Goher, Sulaiman O. Fadlallah. Control of a Two-wheeled Machine with Two-directions Handling Mechanism Using PID and PD-FLC Algorithms . International Journal of Automation and Computing, 2019, 16(4): 511-533. doi: 10.1007/s11633-019-1172-0
[4]	Saber Krim, Souflen Gdaim, Abdellatif Mtibaa, Mohamed Faouzi Mimouni. Contribution of the FPGAs for Complex Control Algorithms: Sensorless DTFC with an EKF of an Induction Motor . International Journal of Automation and Computing, 2019, 16(2): 226-237. doi: 10.1007/s11633-016-1017-z
[5]	Yun-Zhi Jin, Hua Zhou, Hong-Ji Yang, Si-Jing Zhang, Ji-Dong Ge. An Approach to Locating Delayed Activities in Software Processes . International Journal of Automation and Computing, 2018, 15(1): 115-124. doi: 10.1007/s11633-017-1092-9
[6]	J. Gimenez, A. Amicarelli, J. M. Toibero, F. di Sciascio, R. Carelli. Iterated Conditional Modes to Solve Simultaneous Localization and Mapping in Markov Random Fields Context . International Journal of Automation and Computing, 2018, 15(3): 310-324. doi: 10.1007/s11633-017-1109-4
[7]	Imad Benacer, Zohir Dibi. Extracting Parameters of OFET Before and After Threshold Voltage Using Genetic Algorithms . International Journal of Automation and Computing, 2016, 13(4): 382-391. doi: 10.1007/s11633-015-0918-6
[8]	Zheng-Huan Zhang, Xiao-Fen Jiang, Hong-Sheng Xi. Optimal Content Placement and Request Dispatching for Cloud-based Video Distribution Services . International Journal of Automation and Computing, 2016, 13(6): 529-540. doi: 10.1007/s11633-016-1025-z
[9]	Slim Hachicha, Maher Kharrat, Abdessattar Chaari. N4SID and MOESP Algorithms to Highlight the Ill-conditioning into Subspace Identification . International Journal of Automation and Computing, 2014, 11(1): 30-38. doi: 10.1007/s11633-014-0763-z
[10]	Xiao-Jun Chen, Jing Zhang, Jun-Huai Li, Xiang Li. Resource Reconstruction Algorithms for On-demand Allocation in Virtual Computing Resource Pool . International Journal of Automation and Computing, 2012, 9(2): 142-154. doi: 10.1007/s11633-012-0627-3
[11]	Khalid Jebari, Abdelaziz Bouroumi, Aziz Ettouhami. Fuzzy Genetic Sharing for Dynamic Optimization . International Journal of Automation and Computing, 2012, 9(6): 616-626 . doi: 10.1007/s11633-012-0687-4
[12]	P. S. V. Nataraj, Shanta Sondur. Construction of Bode Envelopes Using REP Based Range Finding Algorithms . International Journal of Automation and Computing, 2011, 8(1): 112-121. doi: 10.1007/s11633-010-0562-0
[13]	. Further Results on Delay-distribution-dependent Robust Stability Criteria for Delayed Systems . International Journal of Automation and Computing, 2011, 8(1): 23-28. doi: 10.1007/s11633-010-0550-4
[14]	R. Saravanan, S. Ramabalan, C. Balamurugan, A. Subash. Evolutionary Trajectory Planning for an Industrial Robot . International Journal of Automation and Computing, 2010, 7(2): 190-198. doi: 10.1007/s11633-010-0190-8
[15]	Francisco Flórez-Revuelta, José Manuel Casado-Díaz, Lucas Martínez-Bernabeu. An Evolutionary Approach to the Delineation of Functional Areas Based on Travel-to-work Flows . International Journal of Automation and Computing, 2008, 5(1): 10-21. doi: 10.1007/s11633-008-0010-6
[16]	Fausto Pedro Garcia Márquez, Diego J. Pedregal. Applied RCM² Algorithms Based on Statistical Methods . International Journal of Automation and Computing, 2007, 4(2): 109-116. doi: 10.1007/s11633-007-0109-1
[17]	Shengxiang Yang, Renato Tinós. A Hybrid Immigrants Scheme for Genetic Algorithms in Dynamic Environments . International Journal of Automation and Computing, 2007, 4(3): 243-254. doi: 10.1007/s11633-007-0243-9
[18]	Qingfu Zhang, Jianyong Sun, Edward Tsang. Combinations of Estimation of Distribution Algorithms and Other Techniques . International Journal of Automation and Computing, 2007, 4(3): 273-280. doi: 10.1007/s11633-007-0273-3
[19]	Pietro S. Oliveto, Jun He, Xin Yao. Time Complexity of Evolutionary Algorithms for Combinatorial Optimization:A Decade of Results . International Journal of Automation and Computing, 2007, 4(3): 281-293. doi: 10.1007/s11633-007-0281-3
[20]	Mohammed Alamgir Hossain, Mohammad Osman Tokhi. Real-time Design Constraints in Implementing Active Vibration Control Algorithms . International Journal of Automation and Computing, 2006, 3(3): 252-262. doi: 10.1007/s11633-006-0252-0

通讯作者: 陈斌, bchen63@163.com

1.
沈阳化工大学材料科学与工程学院沈阳 110142

Cite This Article

PDF

XML

Entire Issue PDF

用微信扫码二维码

分享至好友和朋友圈

Metrics

Abstract Views (4083) PDF downloads (1761) Citations (0)

Related Articles

Optimization by Estimation of Distribution with DEUM Framework Based on Markov Random Fields

1. Intelligent Systems Research Center, British Telicom, Adastral Park, Ipswich IP5 3RE, UK;

2. School of Computing, The Robert Gordon University, Aberdeen AB25 1HG, UK

Received: 2007-03-05

Key words:

Abstract: This paper presents a Markov random field (MRF) approach to estimating and sampling the probability distribution in populations of solutions.The approach is used to define a class of algorithms under the general heading distribution estimation using Markov random fields (DEUM).DEUM is a subclass of estimation of distribution algorithms (EDAs) where interaction between solution variables is represented as an undirected graph and the joint probability of a solution is factorized as a Gibbs distribution derived from the structure of the graph.The focus of this paper will be on describing the three main characteristics of DEUM framework,which distinguishes it from the traditional EDA.They are:1) use of MRF models,2) fitness modeling approach to estimating the parameter of the model and 3) Monte Carlo approach to sampling from the model.

HTML

Reference (29)

[1]	J.H.Holland.Adaptation in Natural and Artificial Systems,University of Michigan Press,Ann Arbor,MI,1975.
[2]	I.Rechenberg.Evolutionstrategie-optimierung Technischer Systeme nach Prinzipien der biologischen Evolution,Formman-Holzboog,Stuttgart,1973.
[3]	L.J.Fogel.Autonomous Automata.Industrial Research,vol.4,no.1,pp.14-19,1962.
[4]	H.Miihlenbein,G.Paafi.From Recombination of Genes to the Estimation of Distributions:Ⅰ.Binary Parameters.In Proceedings of the 4th International Conference on Parallel Problem Solving from Nature,Berlin,pp.178-187,1996.
[5]	P.Larranaga,J.A.Lozano.Estimation of Distribution Algorithms:a New Tool for Evolutionary Computation,Kluwer Academic Publishers,Boston,2002.
[6]	M.Pelikan,D.E.Goldberg.Hierarchical BOA Solves Ising Spin Glasses and MAXSAT.In Proceedings of the Genetic and Evolutionary Computation Conference,Springer Verlag,Chicago,IL,pp.1275-1286,2003.
[7]	J.A.Lozano,R.Sagarna,P.Larranaga.Solving Job Scheduling with Estimation of Distribution Algorithms.In Estimation of Distribution Algorithms.A New Tool for Evolutionary Computation,P.Larranaga and J.A.Lozano,(eds.),Kluwer Academis Publishers,Norwell,MA,pp.231-242,2001.
[8]	Q.Zhang,J.Sun,E.Tsang.An Evolutionary Algorithm with Guided Mutation for the Maximum Clique Problem.IEEE Transactions on Evolutionary Computation,vol.9,no.2,pp.192-200,2005.
[9]	S.K.Shakya,J.A.W.McCall,D.F.Brown.Updating the Probability Vector Using MRF Technique for a Uni-variate EDA.In Proceedings of the Second Starting AI Researchers' Symposium,Frontiers in Artificial Intelligence and Applications,IOS press,Valencia,Spain,vol.109,pp.15-25,2004.
[10]	R.Santana.Estimation of Distribution Algorithms with Kikuchi Approximation.Evolutonary Computation,vol.13,no.1,pp.67-98,2005.
[11]	R.Kikuchi.A Theory of Cooperative Phenomena.Physical Review,vol.81,no.6,pp.988-1003,1951.
[12]	P.Larranaga,R.Etxeberria,J.A.Lozano,B.Sierra,I.Inza,J.M.Pefia.A Review of the Cooperation between Evolutionary Computation and Probabilistic Graphical Models.In Proceedings of the Second Symposium on Artificial Intelligence,La Habana,pp.314-324,1999.
[13]	M.I.Jordan,editor.Learning in Graphical Models,NATO Science Series.Kluwer Academic Publishers,Dordrecht,1998.
[14]	J.Besag.Spatial Interaction and the Statistical Analysis of Lattice Systems.Journal of the Royal Statistical Society,vol.36,no.2,pp.192-236,1974.
[15]	S.Z.Li.Markov Random Field Modeling in Computer Vision,Springer-Verlag,London,UK,1995.
[16]	K.P.Murphy.Dynamic Bayesian Networks:Representation,Inference and Learning.Ph.D.dissertation,University of California,Berkeley,2002.
[17]	J.M.Hammersley,P.Clifford.Markov Fields on Finite Graphs and Lattices,Unpublished Manuscript,1971.
[18]	D.F.Brown,A.B.Garmendia-Doval,J.A.W.McCall.Markov Random Field Modelling of Royal Road Genetic Algorithms.Lecture Notes in Computer Science,Springer,January,vol.2310,pp.65-78,2002.
[19]	W.H.Press,S.A.Teukolsky,W.T.Vetterling,B.P.Flannery.Numerical Recipes in C:The Art of Scientific Computing,2nd edition,Cambridge University Press,Cambridge,UK,1992.
[20]	S.Shakya,J.McCall,D.Brown.Estimating the Distribution in an EDA.In Proceedings of the International Conference on Adaptive and Natural Computing Algorithms,Coimbra,Portugal,pp.202-205,2005.
[21]	S.Shakya,J.McCall,Brown D.Using a Markov Network Model in a Univariate EDA:An Emperical Cost-Benefit Analysis.In Proceedings of Genetic and Evolutionary Computation Conference,Washington D.C.,USA,pp.727-734,2005.
[22]	S.K.Shakya,J.A.W.McCall,D.F.Brown.Incorporating a Metropolis Method in a Distribution Estimation Using Markov Random Field Algorithm.In Proceedings of IEEE Congress on Evolutionary Computation,Edinburgh,UK,vol.3,pp.2576-2583,2005.
[23]	S.K.Shakya,J.A.W.McCall,D.F.Brown.Solving the Ising Spin Glass Problem Using a Bivariate EDA Based on Markov Random Fields.In Proceedings of IEEE Congress on Evolutionary Computation,Vancouver,Canada,pp.908-915,2006.
[24]	N.Metropolis,A.W.Rosenbluth,M.N.Rosenbluth,A.H.Teller,E Teller.Equations of State Calculations by Fast Computational Machine.Journal of Chemical Physics,vol.21,no.6,pp.1087-1091,1953.
[25]	S.Geman,D.Geman.Stochastic Relaxation,Gibbs Distributions and the Bayesian Restoration of Images.Readings in Computer Vision:Issues,Problems,Principles,and Paradigms,M.A.Fischler,O.Firschein,(eds.),Kaufmann,Los Altos,CA.,pp.564-584,1987.
[26]	M.Pelikan.Bayesian Optimization Algorithm:From Single Level to Hierarchy.Ph.D.dissertation,University of Illinois at Urbana-Champaign,Urbana,IL,2002.Also IlliGAL Report No.2002023.
[27]	S.Baluja.Population-based Incremental Learning:a Method for Integrating Genetic Search Based Function Optimization and Competitive Learning,Technical Report CMU-CS-94-163,Pittsburgh,PA,1994.
[28]	H.H.Hoos,T.Stutzle.Towards a Characterization of the Behaviour of Stochastic Local Search Algorithms for SAT.Artificial Inteiiigence,vol.112,no.1-2,pp.213-232,1999.
[29]	R.Santana.Probabilistic Modeling Based on Undirected Graphs in Estimation Distribution Algorithms.Ph.D.dissertation,Institute of Cybernetics,Mathematics and Physics,Havana,Cuba,2003.

Optimization by Estimation of Distribution with DEUM Framework Based on Markov Random Fields

Abstract

References

Metrics

Related Articles

通讯作者: 陈斌, bchen63@163.com

Metrics