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

Siddhartha Shakya; John McCall

doi:10.1007/s11633-007-0262-6

Volume 4 Issue 3

June. 2007

Turn off MathJax

Article Contents

Abstract

References

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

Citation:

PDF (2329 KB)

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

More Information

Received Date: March 04, 2007
Revised Date: May 23, 2007

Graphical Abstract

Abstract

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

FullText(HTML)

References (29)

References

J.H.Holland.Adaptation in Natural and Artificial Systems,University of Michigan Press,Ann Arbor,MI,1975.

I.Rechenberg.Evolutionstrategie-optimierung Technischer Systeme nach Prinzipien der biologischen Evolution,Formman-Holzboog,Stuttgart,1973.

L.J.Fogel.Autonomous Automata.Industrial Research,vol.4,no.1,pp.14-19,1962.

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.

P.Larranaga,J.A.Lozano.Estimation of Distribution Algorithms:a New Tool for Evolutionary Computation,Kluwer Academic Publishers,Boston,2002.

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.

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.

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.

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.

R.Santana.Estimation of Distribution Algorithms with Kikuchi Approximation.Evolutonary Computation,vol.13,no.1,pp.67-98,2005.

R.Kikuchi.A Theory of Cooperative Phenomena.Physical Review,vol.81,no.6,pp.988-1003,1951.

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.

M.I.Jordan,editor.Learning in Graphical Models,NATO Science Series.Kluwer Academic Publishers,Dordrecht,1998.

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.

S.Z.Li.Markov Random Field Modeling in Computer Vision,Springer-Verlag,London,UK,1995.

K.P.Murphy.Dynamic Bayesian Networks:Representation,Inference and Learning.Ph.D.dissertation,University of California,Berkeley,2002.

J.M.Hammersley,P.Clifford.Markov Fields on Finite Graphs and Lattices,Unpublished Manuscript,1971.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

R.Santana.Probabilistic Modeling Based on Undirected Graphs in Estimation Distribution Algorithms.Ph.D.dissertation,Institute of Cybernetics,Mathematics and Physics,Havana,Cuba,2003.

Supplements (0)

Cited By