IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v227y2013i2p331-342.html
   My bibliography  Save this article

On the structure of multiobjective combinatorial search space: MNK-landscapes with correlated objectives

Author

Listed:
  • Verel, Sébastien
  • Liefooghe, Arnaud
  • Jourdan, Laetitia
  • Dhaenens, Clarisse

Abstract

The structure of the search space explains the behavior of multiobjective search algorithms, and helps to design well-performing approaches. In this work, we analyze the properties of multiobjective combinatorial search spaces, and we pay a particular attention to the correlation between the objective functions. To do so, we extend the multiobjective NK-landscapes in order to take the objective correlation into account. We study the co-influence of the problem dimension, the degree of non-linearity, the number of objectives, and the objective correlation on the structure of the Pareto optimal set, in terms of cardinality and number of supported solutions, as well as on the number of Pareto local optima. This work concludes with guidelines for the design of multiobjective local search algorithms, based on the main fitness landscape features.

Suggested Citation

  • Verel, Sébastien & Liefooghe, Arnaud & Jourdan, Laetitia & Dhaenens, Clarisse, 2013. "On the structure of multiobjective combinatorial search space: MNK-landscapes with correlated objectives," European Journal of Operational Research, Elsevier, vol. 227(2), pages 331-342.
    • Handle: RePEc:eee:ejores:v:227:y:2013:i:2:p:331-342
    DOI: 10.1016/j.ejor.2012.12.019
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221712009630
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2012.12.019?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Aguirre, Hernan E. & Tanaka, Kiyoshi, 2007. "Working principles, behavior, and performance of MOEAs on MNK-landscapes," European Journal of Operational Research, Elsevier, vol. 181(3), pages 1670-1690, September.
    2. Paquete, Luis & Stutzle, Thomas, 2006. "A study of stochastic local search algorithms for the biobjective QAP with correlated flow matrices," European Journal of Operational Research, Elsevier, vol. 169(3), pages 943-959, March.
    3. Mote, John & Murthy, Ishwar & Olson, David L., 1991. "A parametric approach to solving bicriterion shortest path problems," European Journal of Operational Research, Elsevier, vol. 53(1), pages 81-92, July.
    4. Matthias Ehrgott & Xavier Gandibleux, 2004. "Approximative solution methods for multiobjective combinatorial optimization," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 12(1), pages 1-63, June.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Dubois-Lacoste, Jérémie & López-Ibáñez, Manuel & Stützle, Thomas, 2015. "Anytime Pareto local search," European Journal of Operational Research, Elsevier, vol. 243(2), pages 369-385.
    2. Madalina M. Drugan, 2019. "Random walk’s correlation function for multi-objective NK landscapes and quadratic assignment problem," Journal of Combinatorial Optimization, Springer, vol. 38(4), pages 1213-1262, November.
    3. Ravshanbek Khodzhimatov & Stephan Leitner & Friederike Wall, 2022. "Controlling replication via the belief system in multi-unit organizations," Papers 2206.03786, arXiv.org.
    4. Joop van de Heijning & Stephan Leitner & Alexandra Rausch, 2020. "On the Effectiveness of Minisum Approval Voting in an Open Strategy Setting: An Agent-Based Approach," Papers 2009.04912, arXiv.org, revised Sep 2020.
    5. Ravshanbek Khodzhimatov & Stephan Leitner & Friederike Wall, 2021. "Interactions between social norms and incentive mechanisms in organizations," Papers 2102.12309, arXiv.org.
    6. Cosson, Raphaël & Santana, Roberto & Derbel, Bilel & Liefooghe, Arnaud, 2024. "On bi-objective combinatorial optimization with heterogeneous objectives," European Journal of Operational Research, Elsevier, vol. 319(1), pages 89-101.
    7. Derbel, Bilel & Humeau, Jérémie & Liefooghe, Arnaud & Verel, Sébastien, 2014. "Distributed localized bi-objective search," European Journal of Operational Research, Elsevier, vol. 239(3), pages 731-743.
    8. Ravshanbek Khodzhimatov & Stephan Leitner & Friederike Wall, 2021. "On the effect of social norms on performance in teams with distributed decision makers," Papers 2104.05993, arXiv.org, revised Apr 2021.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Luis Paquete & Tommaso Schiavinotto & Thomas Stützle, 2007. "On local optima in multiobjective combinatorial optimization problems," Annals of Operations Research, Springer, vol. 156(1), pages 83-97, December.
    2. Dubois-Lacoste, Jérémie & López-Ibáñez, Manuel & Stützle, Thomas, 2015. "Anytime Pareto local search," European Journal of Operational Research, Elsevier, vol. 243(2), pages 369-385.
    3. Mădălina M. Drugan, 2018. "Scaling-up many-objective combinatorial optimization with Cartesian products of scalarization functions," Journal of Heuristics, Springer, vol. 24(2), pages 135-172, April.
    4. Aritra Pal & Hadi Charkhgard, 2019. "A Feasibility Pump and Local Search Based Heuristic for Bi-Objective Pure Integer Linear Programming," INFORMS Journal on Computing, INFORMS, vol. 31(1), pages 115-133, February.
    5. Dunker, Thomas & Radons, Gunter & Westkamper, Engelbert, 2005. "Combining evolutionary computation and dynamic programming for solving a dynamic facility layout problem," European Journal of Operational Research, Elsevier, vol. 165(1), pages 55-69, August.
    6. Madalina M. Drugan, 2019. "Random walk’s correlation function for multi-objective NK landscapes and quadratic assignment problem," Journal of Combinatorial Optimization, Springer, vol. 38(4), pages 1213-1262, November.
    7. T. Gómez & M. Hernández & J. Molina & M. León & E. Aldana & R. Caballero, 2011. "A multiobjective model for forest planning with adjacency constraints," Annals of Operations Research, Springer, vol. 190(1), pages 75-92, October.
    8. M. Ehrgott & J. Puerto & A. M. Rodríguez-Chía, 2007. "Primal-Dual Simplex Method for Multiobjective Linear Programming," Journal of Optimization Theory and Applications, Springer, vol. 134(3), pages 483-497, September.
    9. Tobias Kuhn & Stefan Ruzika, 2017. "A coverage-based Box-Algorithm to compute a representation for optimization problems with three objective functions," Journal of Global Optimization, Springer, vol. 67(3), pages 581-600, March.
    10. Derbel, Bilel & Humeau, Jérémie & Liefooghe, Arnaud & Verel, Sébastien, 2014. "Distributed localized bi-objective search," European Journal of Operational Research, Elsevier, vol. 239(3), pages 731-743.
    11. Delorme, Xavier & Gandibleux, Xavier & Degoutin, Fabien, 2010. "Evolutionary, constructive and hybrid procedures for the bi-objective set packing problem," European Journal of Operational Research, Elsevier, vol. 204(2), pages 206-217, July.
    12. Suvrajeet Sen & Rekha Pillai & Shirish Joshi & Ajay K. Rathi, 2001. "A Mean-Variance Model for Route Guidance in Advanced Traveler Information Systems," Transportation Science, INFORMS, vol. 35(1), pages 37-49, February.
    13. Andrea Raith & Judith Wang & Matthias Ehrgott & Stuart Mitchell, 2014. "Solving multi-objective traffic assignment," Annals of Operations Research, Springer, vol. 222(1), pages 483-516, November.
    14. Granat, Janusz & Guerriero, Francesca, 2003. "The interactive analysis of the multicriteria shortest path problem by the reference point method," European Journal of Operational Research, Elsevier, vol. 151(1), pages 103-118, November.
    15. Herbert Dawid & Reinhold Decker & Thomas Hermann & Hermann Jahnke & Wilhelm Klat & Rolf König & Christian Stummer, 2017. "Management science in the era of smart consumer products: challenges and research perspectives," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 25(1), pages 203-230, March.
    16. Andrzej Jaszkiewicz & Thibaut Lust, 2017. "Proper balance between search towards and along Pareto front: biobjective TSP case study," Annals of Operations Research, Springer, vol. 254(1), pages 111-130, July.
    17. Hanne, Thomas, 2007. "A multiobjective evolutionary algorithm for approximating the efficient set," European Journal of Operational Research, Elsevier, vol. 176(3), pages 1723-1734, February.
    18. Perny, Patrice & Spanjaard, Olivier, 2005. "A preference-based approach to spanning trees and shortest paths problems***," European Journal of Operational Research, Elsevier, vol. 162(3), pages 584-601, May.
    19. Francis Sourd & Olivier Spanjaard, 2008. "A Multiobjective Branch-and-Bound Framework: Application to the Biobjective Spanning Tree Problem," INFORMS Journal on Computing, INFORMS, vol. 20(3), pages 472-484, August.
    20. Sedeño-noda, Antonio & Colebrook, Marcos, 2019. "A biobjective Dijkstra algorithm," European Journal of Operational Research, Elsevier, vol. 276(1), pages 106-118.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:ejores:v:227:y:2013:i:2:p:331-342. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.