research-article

HMOBEDA: Hybrid Multi-objective Bayesian Estimation of Distribution Algorithm

Authors:

Marcella S.R. Martins,

Myriam R.B.S. Delgado,

Roberto Santana,

Ricardo Lüders,

Richard Aderbal Gonçalves,

Carolina Paula de AlmeidaAuthors Info & Claims

GECCO '16: Proceedings of the Genetic and Evolutionary Computation Conference 2016

Pages 357 - 364

https://doi.org/10.1145/2908812.2908826

Published: 20 July 2016 Publication History

Abstract

Probabilistic modeling of selected solutions and incorporation of local search methods are approaches that can notably improve the results of multi-objective evolutionary algorithms (MOEAs). In the past, these approaches have been jointly applied to multi-objective problems (MOPs) with excellent results. In this paper, we introduce for the first time a joint probabilistic modeling of (1) local search methods with (2) decision variables and (3) the objectives in a framework named HMOBEDA. The proposed approach is compared with six evolutionary methods (including a modified version of NSGA-III, adapted to solve combinatorial optimization) on instances of the multi-objective knapsack problem with 3, 4, and 5 objectives. Results show that HMOBEDA is a competitive approach. It outperforms the other methods according to the hypervolume indicator.

References

[1]

C. W. Ahn, E. Kim, H.-T. Kim, D.-H. Lim, and J. An. A hybrid multiobjective evolutionary algorithm: Striking a balance with local search. In Mathematical and Computer Modelling, volume 52, pages 2048--2059, 2010.

Digital Library

[2]

J. Arroyo, R. dos Santos Ottoni, and A. de Paiva Oliveira. Multi-objective variable neighborhood search algorithms for a single machine scheduling problem with distinct due windows. In Electronic Notes in Theoretical Computer Science, volume 281, pages 5--19, 2011.

Digital Library

[3]

G. Casella and R. L. Berger. Statistical Inference. Duxbury, USA, second edition, 2001.

[4]

T.-C. Chiang. nsga3cpp: A C+ implementation of NSGA-iii. http://web.ntnu.edu.tw/ tcchiang/publications/nsga3cpp/nsga3cpp.htm, 2014. Access date: 12 july.2015.

[5]

W. Conover. Practical Nonparametric Statistics. Wiley, third edition, 1999.

[6]

G. Cooper and E. Herskovits. A bayesian method for the induction of probabilistic networks from data. Machine Learning, 9(4):309--347, 1992.

[7]

K. Deb and H. Jain. An Evolutionary Many-Objective Optimization Algorithm Using Reference-Point-Based Nondominated Sorting Approach, Part I: Solving Problems With Box Constraints. IEEE Transactions on Evolutionary Computation, 18(4):577--601, 2014.

[8]

K. Deb, S.Agrawal, A. Pratab, and T. Meyarivan. A Fast and Elitist Multi-Objective Genetic Algorithm: NSGA-II. In IEEE Transactions on Evolutionary Computation, volume 6, pages 182--197, 2002.

Digital Library

[9]

D. Garrett and D. Dasgupta. An Empirical Comparison of Memetic Algorithm Strategies on the Multiobjective Quadratic Assignment Problem. In IEEE Symposium on Computational Intelligence in Multi-criteria Decision-Making, pages 80--87, Nashville, TN, 2009.

[10]

D. Heckerman, D. Geiger, and D. Chickering. Learning bayesian networks: the combination of knowledge and statistical data. Machine Learning, 20(3):197--243, 1995.

Digital Library

[11]

Y. Hochberg and A. C. Tamhane. Multiple Comparison Procedures. John Wiley and Sons, Hoboken, NJ, 1987.

Digital Library

[12]

H. Ishibuchi, N. Akedo, and Y. Nojima. Behavior of Multiobjective Evolutionary Algorithms on Many-Objective Knapsack Problems. IEEE Transactions on Evolutionary Computation, 19(2):264--283, 2015.

[13]

H. Ishibuchi, Y. Hitotsuyanagi, and Y. Nojima. Scalability of Multiobjective Genetic Local Search to Many-Objective Problems:Knapsack Problem Case Studies. In Evolutionary Computation, 2008. CEC 2008. (IEEE World Congress on Computational Intelligence), pages 3586--3593, June 2008.

[14]

H. Ishibuchi, Y. Hitotsuyanagi, N. Tsukamoto, and Y. Nojima. Implementation of Multiobjective Memetic Algorithms for Combinatorial Optimization problems: A Knapsack Problem Case Study. 171:27--49, 2009.

[15]

H. Jain and K. Deb. An evolutionary many-objective optimization algorithm using reference-point based nondominated sorting approach, part ii: Handling constraints and extending to an adaptive approach. IEEE Transactions on Evolutionary Computation, 18(4):602--622, Aug 2014.

[16]

H. Karshenas, R. Santana, C. Bielza, and P. Larra\ naga. Multiobjective Estimation of Distribution Algorithm Based on Joint Modeling of Objectives and Variables. 18:519--542, 2014.

[17]

N. Khan, D. E. Goldberg, and M. Pelikan. Multi-objective Bayesian optimization algorithm. IlliGAL Report No. 2002009, University of Illinois at Urbana-Champaign, Illinois Genetic Algorithms Laboratory, Urbana, IL, 2002.

[18]

K. B. Korb and A. E. Nicholson. Bayesian Artificial Intelligence. CRC Press, second edition, 2010.

Digital Library

[19]

N. Krasnogor, B. P. Blackburne, E. K. Burke, and J. D. Hirst. Multimeme algorithms for Protein Structure Prediction. In Parallel Problem Solving from Nature - PPSN VII, volume 2439 of Lecture Notes in Computer Science, pages 769--778, Spain, 2002.

Digital Library

[20]

N. Krasnogor and S. Gustafson. Toward truly "memetic" memetic algorithms: discussion and proof of concepts. In Advances in Nature-Inspired Computation: the PPSN VII Workshops, 2002.

[21]

P. Larranaga, H. Karshenas, C. Bielza, and R. Santana. A review on probabilistic graphical models in evolutionary computation. In Journal of Heuristics, volume 18, pages 795--819, 2012.

Digital Library

[22]

M. Laumanns and J. Ocenasek. Bayesian Optimization Algorithms for Multi-Objective Optimization. In Parallel Problem Solving from Nature-PPSN VII, volume 2439 of Lecture Notes in Computer Science, pages 298--307, 2002.

Digital Library

[23]

H. Li, Q. Zhang, E. Tsang, and J. A. Ford. Hybrid Estimation of Distribution Algorithm for Multiobjective Knapsack Problem. In Evolutionary Computation in Combinatorial Optimization, pages 145--154. Springer Berlin Heidelberg, 2004.

[24]

H. Muhlenbein and G. Paab. From Recombination of Genes to the Estimation of Distributions I. Binary parameters. In Parallel Problem Solving from Nature-PPSN IV, Lecture Notes in Computer Science 1411, pages 178--187, 1996.

Digital Library

[25]

J. Pearl. Probabilistic reasoning in intelligent systems: Networks of plausible inference. Morgan Kaufmann, San Mateo CA, 1988.

Digital Library

[26]

E. Perrier, S. Imoto, S. Miyano, and M. Chickering. Finding Optimal Bayesian Network Given a Super-Structure. Journal of Machine Learning Research, 9:2251--2286, 2008.

[27]

P.Larranaga and J. A. Lozano. Estimation of distribution algorithms: A new tool for evolutionary computation, volume 2. Springer, Netherlands, 2002.

Digital Library

[28]

S. J. Russel and P. Norvig. Artificial Intelligence: A Modern Approach. Prentice Hall, Upper Saddle River, New Jersey, second edition, 2003.

Digital Library

[29]

B. Samir, L. Yacine, and B. Mohamed. Local Search Heuristic for Multiple Knapsack Problem. International Journal of Intelligent Information Systems, 4(2):35--39, 2015.

[30]

R. Santana, P. Larranaga, and J. A. Lozano. Combining variable neighborhood search and estimation of distribution algorithms in the protein side chain placement problem. Journal of Heuristics, 14:519--547, 2008.

Digital Library

[31]

S.Bleuler, M. Laumanns, L.Thiele, and E.Zitzler. Pisa - A Platform and Programming Language Independent Interface for Search Algorithms. In Evolutionary multi-criterion optimization (EMO 2003), Lecture notes in computer science, pages 494--508, Berlin, 2003.

Digital Library

[32]

J. Schwarz and J. Ocenasek. Multiobjective Bayesian Optimization Algorithm for Combinatorial Problems: Theory and Practice. Neural Network World, 11(5):423--441, 2001.

[33]

J. Schwarz and J. Ocenasek. Pareto Bayesian Optimization Algorithm for the Multiobjective 0/1 Knapsack problem. In 7th International Mendel Conference on Soft Computing, pages 131--136, 2001.

[34]

A. Seshadri. Multi-Objective Optimization using Evolutionary Algorithm. http://www.mathworks.com/matlabcentral/\\fileexchange/10429-nsga-ii--a-multi-objective-optimization-algorithm, 2009. Access date: 2 feb.2016.

[35]

N. Srinivas and K. Deb. Multiobjective optimization using nondominated sorting in genetic algorithms. In Evolutionary Computation, volume 2, pages 221--248, 1994.

Digital Library

[36]

E.-G. Talbi. Metaheuristics: From Design to Implementation. Wiley Publishing, 2009.

Digital Library

[37]

Y. Tanigaki, K. Narukawa, Y. Nojima, and H. Ishibuchi. Preference-Based NSGA-II for Many-Objective Knapsack Problems. In 7th International Conference on Soft Computing and Intelligent Systems (SCIS) and Advanced Intelligent Systems (ISIS), pages 637--642, 2014.

[38]

I. Tsamardinos, L. E. Brown, and C. F. Aliferis. The Max-min Hill-climbing Bayesian Network Structure Learning Algorithm. Machine Learning, 65(1):31--78, 2006.

Digital Library

[39]

L. Wang, S. yao Wang, and Y. Xu. An effective hybrid EDA-based algorithm for solving multidimensional knapsack problem. In Expert Systems with Applications, volume 39, pages 5593--5599, 2012.

Digital Library

[40]

C. Yuan and B. Malone. Learning Optimal Bayesian Networks: A Shortest Path Perspective. Journal of Artificial Intelligence Research., 48(1):23--65, 2013.

Digital Library

[41]

Q. Zhang and H. Li. MOEA/D: A Multiobjective Evolutionary Algorithm Based on Decomposition. IEEE Transactions on Evolutionary Computation, 11(6):712--731, 2007.

Digital Library

[42]

Q. Zhang, J. Sun, and E. P. K. Tsang. Evolutionary algorithm with guided mutation for the maximum clique problem. IEEE Transactions on Evolutionary Computation, 9(2):192--200, 2005.

Digital Library

[43]

A. Zhou, J. Sun, and Q. Zhang. An Estimation of Distribution Algorithm with Cheap and Expensive Local Search. In IEEE Transactions on Evolutionary Computation, accepted, 2015.

[44]

E. Zitzler and L. Thiele. Multiple objective evolutionary algorithms: A comparative case study and the strength Pareto approach. In IEEE Transactions on Evolutionary Computation, volume 3, pages 257--271, 1999.

Digital Library

Cited By

Song ZLuo WXu PYe ZChen K(2024)An Indicator Based Evolutionary Algorithm for Multiparty Multiobjective Knapsack ProblemsIntelligent Information Processing XII10.1007/978-3-031-57808-3_17(233-246)Online publication date: 6-Apr-2024
https://doi.org/10.1007/978-3-031-57808-3_17
Oliva DMartins MHinojosa SElaziz Mdos Santos Pda Cruz GMousavirad S(2022)A hyper-heuristic guided by a probabilistic graphical model for single-objective real-parameter optimizationInternational Journal of Machine Learning and Cybernetics10.1007/s13042-022-01623-613:12(3743-3772)Online publication date: 6-Aug-2022
https://doi.org/10.1007/s13042-022-01623-6
Martins MYafrani MDelgado MLüders RSantana RSiqueira HAkcay HAhiod B(2021)Analysis of Bayesian Network Learning Techniques for a Hybrid Multi-objective Bayesian Estimation of Distribution Algorithm: a case study on MNK LandscapeJournal of Heuristics10.1007/s10732-021-09469-xOnline publication date: 6-Feb-2021
https://doi.org/10.1007/s10732-021-09469-x
Show More Cited By

Index Terms

HMOBEDA: Hybrid Multi-objective Bayesian Estimation of Distribution Algorithm
1. Computing methodologies
  1. Artificial intelligence
    1. Search methodologies
      1. Discrete space search
2. Mathematics of computing
  1. Discrete mathematics
    1. Combinatorics
      1. Combinatorial optimization

Recommendations

Hybrid multi-objective Bayesian estimation of distribution algorithm: a comparative analysis for the multi-objective knapsack problem

Nowadays, a number of metaheuristics have been developed for efficiently solving multi-objective optimization problems. Estimation of distribution algorithms are a special class of metaheuristic that intensively apply probabilistic modeling and, as well ...
Hybridization of NSGA-II with greedy re-assignment for variation tolerant logic mapping on nano-scale crossbar architectures
GECCO Comp '14: Proceedings of the Companion Publication of the 2014 Annual Conference on Genetic and Evolutionary Computation

There exit high variations among nano-devices in nano-electronic systems, owing to the extremely small size and the bottom-up self-assembly nanofabrication process. Therefore, it is important to develop logical function mapping techniques with the ...
Decomposition-Based Memetic Algorithm for Multiobjective Capacitated Arc Routing Problem

The capacitated arc routing problem (CARP) is a challenging combinatorial optimization problem with many real-world applications, e.g., salting route optimization and fleet management. There have been many attempts at solving CARP using heuristic and ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '16: Proceedings of the Genetic and Evolutionary Computation Conference 2016

July 2016

1196 pages

ISBN:9781450342063

DOI:10.1145/2908812

Editor:
Tobias Friedrich
Hasso Plattner Institute
,
General Chair:
Frank Neumann
University of Adelaide
,
Program Chair:
Andrew M. Sutton
Hasso Plattner Institute

Copyright © 2016 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGEVO: ACM Special Interest Group on Genetic and Evolutionary Computation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 20 July 2016

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Conference

GECCO '16

Sponsor:

SIGEVO

GECCO '16: Genetic and Evolutionary Computation Conference

July 20 - 24, 2016

Colorado, Denver, USA

Acceptance Rates

GECCO '16 Paper Acceptance Rate 137 of 381 submissions, 36%;

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
124
Total Downloads

Downloads (Last 12 months)4
Downloads (Last 6 weeks)1

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Song ZLuo WXu PYe ZChen K(2024)An Indicator Based Evolutionary Algorithm for Multiparty Multiobjective Knapsack ProblemsIntelligent Information Processing XII10.1007/978-3-031-57808-3_17(233-246)Online publication date: 6-Apr-2024
https://doi.org/10.1007/978-3-031-57808-3_17
Oliva DMartins MHinojosa SElaziz Mdos Santos Pda Cruz GMousavirad S(2022)A hyper-heuristic guided by a probabilistic graphical model for single-objective real-parameter optimizationInternational Journal of Machine Learning and Cybernetics10.1007/s13042-022-01623-613:12(3743-3772)Online publication date: 6-Aug-2022
https://doi.org/10.1007/s13042-022-01623-6
Martins MYafrani MDelgado MLüders RSantana RSiqueira HAkcay HAhiod B(2021)Analysis of Bayesian Network Learning Techniques for a Hybrid Multi-objective Bayesian Estimation of Distribution Algorithm: a case study on MNK LandscapeJournal of Heuristics10.1007/s10732-021-09469-xOnline publication date: 6-Feb-2021
https://doi.org/10.1007/s10732-021-09469-x
Oliva DMartins M(2019)A Bayesian based Hyper-Heuristic approach for global optimization2019 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC.2019.8790028(1766-1773)Online publication date: Jun-2019
https://doi.org/10.1109/CEC.2019.8790028
Martins MYafrani MSantana RDelgado MLuders RAhiod B(2018)On the Performance of Multi-Objective Estimation of Distribution Algorithms for Combinatorial Problems2018 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC.2018.8477970(1-8)Online publication date: Jul-2018
https://doi.org/10.1109/CEC.2018.8477970
Martins MDelgado MLuders RSantana RGoncalves Rde Almeida C(2017)Probabilistic Analysis of Pareto Front Approximation for a Hybrid Multi-objective Bayesian Estimation of Distribution Algorithm2017 Brazilian Conference on Intelligent Systems (BRACIS)10.1109/BRACIS.2017.32(384-389)Online publication date: Oct-2017
https://doi.org/10.1109/BRACIS.2017.32

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents