On the Design of Hard mUBQP Instances
Pages 421 - 428
Abstract
This paper proposes a new method for the design and analysis of multi-objective unconstrained binary quadratic programming (mUBQP) instances, commonly used for testing discrete multi-objective evolutionary algorithms (MOEAs). These instances are usually generated considering the sparsity of the matrices and the correlation between objectives but randomly selecting the values for the matrix cells. Our hypothesis is that going beyond the use of objective correlations by considering different types of variables interactions in the generation of the instances can help to obtain more diverse problem benchmarks, comprising harder instances. We propose a parametric approach in which small building blocks of deceptive functions are planted into the matrices that define the mUBQP. The algorithm for creating the new instances is presented, and the difficulty of the functions is tested using variants of a decomposition-based MOEA. Our experimental results confirm that the instances generated by planting deceptive blocks require more function evaluations to be solved than instances generated using other methods.
References
[1]
H. E. Aguirre and K. Tanaka. Working principles, behavior, and performance of MOEAs on MNK-landscapes. European Journal of Operational Research, 181(3):1670--1690, 2007.
[2]
S. Baluja. Population-based incremental learning: A method for integrating genetic search based function optimization and competitive learning. Technical Report Carnegie Mellon University-CS-94--163, Carnegie Mellon University, Pittsburgh, PA, 1994.
[3]
C. C. Coello, G. Lamont, and D. van Veldhuizen. Evolutionary Algorithms for Solving Multi-Objective Problems. Genetic and Evolutionary Computation. Springer, Berlin, Heidelberg, 2nd edition, 2007.
[4]
M. Z. de Souza, R. Santana, A. T. R. Pozo, and A. Mendiburu. MOEA/D-GM: using probabilistic graphical models in MOEA/D for solving combinatorial optimization problems. CoRR, abs/1511.05625, 2015.
[5]
K. Deb, L. Thiele, M. Laumanns, and E. Zitzler. Scalable test problems for evolutionary multiobjective optimization. In Evolutionary Multiobjective Optimization, Advanced Information and Knowledge Processing, pages 105--145. Springer London, 2005.
[6]
B. Derbel, D. Brockhoff, A. Liefooghe, and S. Verel. On the impact of multiobjective scalarizing functions. In Parallel Problem Solving from Nature--PPSN XIII, pages 548--558. Springer, 2014.
[7]
D. E. Goldberg, K. Deb, and J. rey Horn. Massive multimodality, deception, and genetic algorithms. IlliGAL Report 92005, University of Illinois at Urbana-Champaign, Illinois Genetic Algorithms Laboratory, Urbana, IL, 1992.
[8]
S. Huband, P. Hingston, L. Barone, and L. While. A review of multiobjective test problems and a scalable test problem toolkit. Evolutionary Computation, IEEE Transactions on, 10(5):477--506, 2006.
[9]
J. Knowles and D. Corne. Instance generators and test suites for the multiobjective quadratic assignment problem. In Evolutionary Multi-criterion Optimization, pages 295--310. Springer, 2003.
[10]
G. Kochenberger, J.-K. Hao, F. Glover, M. Lewis, Z. Lü, H. Wang, and Y. Wang. The unconstrained binary quadratic programming problem: a survey. Journal of Combinatorial Optimization, 28(1):58--81, 2014.
[11]
A. Liefooghe, S. Verel, and J.-K. Hao. A hybrid metaheuristic for multiobjective unconstrained binary quadratic programming. Applications Soft Computing, 16:10--19, 2014.
[12]
A. Liefooghe, S. Verel, L. Paquete, and J.-K. Hao. Experiments on local search for bi-objective unconstrained binary quadratic programming. In Evolutionary Multi-Criterion Optimization, pages 171--186. Springer, 2015.
[13]
L. Lozada-Chang and R. Santana. Univariate marginal distribution algorithm dynamics for a class of parametric functions with unitation constraints. Information Sciences, 181(11):2340--2355, 2011.
[14]
G. Marquet, B. Derbel, A. Liefooghe, and T. El-Ghazali. Shake them all! rethinking selection and replacement in MOEA/D. In Parallel Problem Solving from Nature - PPSN XIII International Conference, volume 8672, pages 641--651, 2014.
[15]
J. P. Martins, A. H. M. Soares, D. V. Vargas, and A. C. B. Delbem. Multi-objective phylogenetic algorithm: Solving multi-objective decomposable deceptive problems. In Evolutionary Multi-Criterion Optimization, pages 285--297. Springer, 2011.
[16]
H. Mühlenbein. The equation for response to selection and its use for prediction. Evolutionary Computation, 5(3):303--346, 1997.
[17]
H. Mühlenbein, T. Mahnig, and A. Ochoa. Schemata, distributions and graphical models in evolutionary optimization. Journal of Heuristics, 5(2):213--247, 1999.
[18]
M. Pelikan, K. Sastry, and D. E. Goldberg. Multiobjective hBOA, clustering and scalability. IlliGAL Report No. 2005005, University of Illinois at Urbana-Champaign, Illinois Genetic Algorithms Laboratory, Urbana, IL, February 2005.
[19]
C. A. Rodrıguez Villalobos and C. A. Coello Coello. A new multi-objective evolutionary algorithm based on a performance assessment indicator. In Proceedings of the 14th annual conference on Genetic and evolutionary computation, pages 505--512. ACM, 2012.
[20]
R. Santana, A. Mendiburu, and J. A. Lozano. Computing factorized approximations of Pareto-fronts using mNM-landscapes and Boltzmann distributions. CoRR, abs/1512.03466, 2015.
[21]
R. Santana, A. Mendiburu, and J. A. Lozano. Evolving MNK-landscapes with structural constraints. In Proceedings of the IEEE Congress on Evolutionary Computation CEC 2015, pages 1364--1371, Sendai, Japan, 2015. IEEE press.
[22]
R. Santana, A. Ochoa, and M. R. Soto. Factorized Distribution Algorithms for functions with unitation constraints. In Evolutionary Computation and Probabilistic Graphical Models. Proceedings of the Third Symposium on Adaptive Systems, pages 158--165, 2001.
[23]
O. Schütze, X. Esquivel, A. Lara, and C. A. C. Coello. Using the averaged hausdorff distance as a performance measure in evolutionary multiobjective optimization. Evolutionary Computation, IEEE Transactions on, 16(4):504--522, 2012.
[24]
S. Verel, A. Liefooghe, L. Jourdan, and C. Dhaenens. Pareto local optima of multiobjective NK-landscapes with correlated objectives. In Evolutionary Computation in Combinatorial Optimization, pages 226--237. Springer, 2011.
[25]
S. Verel, A. Liefooghe, L. Jourdan, and C. Dhaenens. On the structure of multiobjective combinatorial search space:MNK-landscapes with correlated objectives. European Journal of Operational Research, 227(2):331--342, 2013.
[26]
D. Whitley. Mk landscapes, NK landscapes, MAX-kSAT: A proof that the only challenging problems are deceptive. In Proceedings of the 2015 on Genetic and Evolutionary Computation Conference, pages 927--934. ACM, 2015.
[27]
Q. Zhang and H. Li. MOEA/D: A multiobjective evolutionary algorithm based on decomposition. IEEE Transactions on Evolutionary Computation, 11(6):712--731, 2007.
[28]
E. Zitzler and L. Thiele. Multiobjective evolutionary algorithms: A comparative case study and the strength pareto approach. Evolutionary Computation, IEEE Transactions on, 3(4):257--271, 1999.
Index Terms
- On the Design of Hard mUBQP Instances
Recommendations
MOEA/D for Multiple Multi-objective Optimization
Evolutionary Multi-Criterion OptimizationAbstractThis paper defines a new multi-objective optimization problem, called multiple multi-objective optimization problem (MMOP). An MMOP is composed of several multi-objective optimization problems (MOPs) with different decision spaces and the same ...
An efficient algorithm for multi-objective structural optimization problems using an improved pbest-based differential evolution algorithm
Highlights- A novel multi-objective optimization method (MOEA/D-EpDE) is developed.
- Improved pbest-based differential evolution is implemented in MOEA/D_DRA framework.
- External storage is integrated to improve the Pareto front.
- MOEA/D-EpDE ...
AbstractMulti-objective optimization (MOO) for structural design is addressed. A new MOO algorithm, named MOEA/D-EpDE, which combines the advantages of a recently developed pbest-based differential evolution method (EpDE) and the multi-objective ...
A two-stage evolutionary strategy based MOEA/D to multi-objective problems
Highlights- A two-stage evolution strategy is proposed for solving multi-objective problem.
- The convergence and diversity should be balanced in multi-objective optimization.
- A local searching method can improve the diversity of solutions in ...
AbstractThe balance of convergence and diversity plays a significant role to the performance of multi-objective evolutionary algorithms (MOEAs). The MOEA/D is a very popular multi-objective optimization algorithm and has been used to solve various real ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
July 2016
1196 pages
ISBN:9781450342063
DOI:10.1145/2908812
- Editor:
- Tobias Friedrich,
- General Chair:
- Frank Neumann,
- Program Chair:
- Andrew M. Sutton
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
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 20 July 2016
Check for updates
Author Tags
Qualifiers
- Research-article
Funding Sources
- Coordenação de Aperfeiçoamento de Pessoal de Nível Superior
- CNPq
- Program Science Without Borders
- Ministerio de Ciencia e Innovación
- Eusko Jaurlaritza
Conference
GECCO '16
Sponsor:
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
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 50Total Downloads
- Downloads (Last 12 months)1
- Downloads (Last 6 weeks)1
Reflects downloads up to 08 Feb 2025
Other Metrics
Citations
Cited By
View allView Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in