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

Multi-objectivization, fitness landscape transformation and search performance: A case of study on the hp model for protein structure prediction

Author

Listed:
  • Garza-Fabre, Mario
  • Toscano-Pulido, Gregorio
  • Rodriguez-Tello, Eduardo

Abstract

Multi-objectivization represents a current and promising research direction which has led to the development of more competitive search mechanisms. This concept involves the restatement of a single-objective problem in an alternative multi-objective form, which can facilitate the process of finding a solution to the original problem. Recently, this transformation was applied with success to the HP model, a simplified yet challenging representation of the protein structure prediction problem. The use of alternative multi-objective formulations, based on the decomposition of the original objective function of the problem, has significantly increased the performance of search algorithms. The present study goes further on this topic. With the primary aim of understanding and quantifying the potential effects of multi-objectivization, a detailed analysis is first conducted to evaluate the extent to which this problem transformation impacts on an important characteristic of the fitness landscape, neutrality. To the authors’ knowledge, the effects of multi-objectivization have not been previously investigated by explicitly sampling and evaluating the neutrality of the fitness landscape. Although focused on the HP model, most of the findings of such an analysis can be extrapolated to other problem domains, contributing thus to the general understanding of multi-objectivization. Finally, this study presents a comparative analysis where the advantages of multi-objectivization are evaluated in terms of the performance of a basic evolutionary algorithm. Both the two- and three-dimensional variants of the HP model (based on the square and cubic lattices, respectively) are considered.

Suggested Citation

  • Garza-Fabre, Mario & Toscano-Pulido, Gregorio & Rodriguez-Tello, Eduardo, 2015. "Multi-objectivization, fitness landscape transformation and search performance: A case of study on the hp model for protein structure prediction," European Journal of Operational Research, Elsevier, vol. 243(2), pages 405-422.
  • Handle: RePEc:eee:ejores:v:243:y:2015:i:2:p:405-422
    DOI: 10.1016/j.ejor.2014.06.009
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221714004925
    Download Restriction: Full text for ScienceDirect subscribers only

    File URL: https://libkey.io/10.1016/j.ejor.2014.06.009?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. Jean-Paul Watson, 2010. "An Introduction to Fitness Landscape Analysis and Cost Models for Local Search," International Series in Operations Research & Management Science, in: Michel Gendreau & Jean-Yves Potvin (ed.), Handbook of Metaheuristics, chapter 0, pages 599-623, Springer.
    2. Helena R. Lourenço & Olivier C. Martin & Thomas Stützle, 2010. "Iterated Local Search: Framework and Applications," International Series in Operations Research & Management Science, in: Michel Gendreau & Jean-Yves Potvin (ed.), Handbook of Metaheuristics, chapter 0, pages 363-397, Springer.
    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. Carlos Segura & Carlos A. Coello Coello & Gara Miranda & Coromoto León, 2016. "Using multi-objective evolutionary algorithms for single-objective constrained and unconstrained optimization," Annals of Operations Research, Springer, vol. 240(1), pages 217-250, May.
    2. Rodriguez-Tello, Eduardo & Lardeux, Frédéric & Duarte, Abraham & Narvaez-Teran, Valentina, 2019. "Alternative evaluation functions for the cyclic bandwidth sum problem," European Journal of Operational Research, Elsevier, vol. 273(3), pages 904-919.

    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. Verbiest, Floor & Cornelissens, Trijntje & Springael, Johan, 2019. "A matheuristic approach for the design of multiproduct batch plants with parallel production lines," European Journal of Operational Research, Elsevier, vol. 273(3), pages 933-947.
    2. Cordeau, Jean-François & Dell’Amico, Mauro & Falavigna, Simone & Iori, Manuel, 2015. "A rolling horizon algorithm for auto-carrier transportation," Transportation Research Part B: Methodological, Elsevier, vol. 76(C), pages 68-80.
    3. David Wolfinger & Fabien Tricoire & Karl F. Doerner, 2019. "A matheuristic for a multimodal long haul routing problem," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 8(4), pages 397-433, December.
    4. Drexl, Michael & Schneider, Michael, 2015. "A survey of variants and extensions of the location-routing problem," European Journal of Operational Research, Elsevier, vol. 241(2), pages 283-308.
    5. Vansteenwegen, Pieter & Mateo, Manuel, 2014. "An iterated local search algorithm for the single-vehicle cyclic inventory routing problem," European Journal of Operational Research, Elsevier, vol. 237(3), pages 802-813.
    6. Pagnozzi, Federico & Stützle, Thomas, 2019. "Automatic design of hybrid stochastic local search algorithms for permutation flowshop problems," European Journal of Operational Research, Elsevier, vol. 276(2), pages 409-421.
    7. Andrés Martínez-Reyes & Carlos L. Quintero-Araújo & Elyn L. Solano-Charris, 2021. "Supplying Personal Protective Equipment to Intensive Care Units during the COVID-19 Outbreak in Colombia. A Simheuristic Approach Based on the Location-Routing Problem," Sustainability, MDPI, vol. 13(14), pages 1-16, July.
    8. Angel Juan & Javier Faulin & Albert Ferrer & Helena Lourenço & Barry Barrios, 2013. "MIRHA: multi-start biased randomization of heuristics with adaptive local search for solving non-smooth routing problems," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 21(1), pages 109-132, April.
    9. Rodriguez-Tello, Eduardo & Lardeux, Frédéric & Duarte, Abraham & Narvaez-Teran, Valentina, 2019. "Alternative evaluation functions for the cyclic bandwidth sum problem," European Journal of Operational Research, Elsevier, vol. 273(3), pages 904-919.
    10. Daniel Schubert & André Scholz & Gerhard Wäscher, 2017. "Integrated Order Picking and Vehicle Routing with Due Dates," FEMM Working Papers 170007, Otto-von-Guericke University Magdeburg, Faculty of Economics and Management.
    11. Janssens, Jochen & Talarico, Luca & Reniers, Genserik & Sörensen, Kenneth, 2015. "A decision model to allocate protective safety barriers and mitigate domino effects," Reliability Engineering and System Safety, Elsevier, vol. 143(C), pages 44-52.
    12. Zhang, Zizhen & Qin, Hu & Wang, Kai & He, Huang & Liu, Tian, 2017. "Manpower allocation and vehicle routing problem in non-emergency ambulance transfer service," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 106(C), pages 45-59.
    13. Mauro Dell’Amico & Simone Falavigna & Manuel Iori, 2015. "Optimization of a Real-World Auto-Carrier Transportation Problem," Transportation Science, INFORMS, vol. 49(2), pages 402-419, May.
    14. Huber, Sandra & Geiger, Martin Josef, 2017. "Order matters – A Variable Neighborhood Search for the Swap-Body Vehicle Routing Problem," European Journal of Operational Research, Elsevier, vol. 263(2), pages 419-445.
    15. Alfaro-Fernández, Pedro & Ruiz, Rubén & Pagnozzi, Federico & Stützle, Thomas, 2020. "Automatic Algorithm Design for Hybrid Flowshop Scheduling Problems," European Journal of Operational Research, Elsevier, vol. 282(3), pages 835-845.
    16. Julio C. Londoño & Rafael D. Tordecilla & Leandro do C. Martins & Angel A. Juan, 2021. "A biased-randomized iterated local search for the vehicle routing problem with optional backhauls," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 29(2), pages 387-416, July.
    17. TALARICO, Luca & SÖRENSEN, Kenneth & SPRINGAEL, Johan, 2013. "The risk constrained cash-in-transit vehicle routing problem with time windows," Working Papers 2013012, University of Antwerp, Faculty of Business and Economics.
    18. Vidal, Thibaut & Crainic, Teodor Gabriel & Gendreau, Michel & Prins, Christian, 2013. "Heuristics for multi-attribute vehicle routing problems: A survey and synthesis," European Journal of Operational Research, Elsevier, vol. 231(1), pages 1-21.
    19. Sabar, Nasser R. & Kendall, Graham, 2015. "An iterated local search with multiple perturbation operators and time varying perturbation strength for the aircraft landing problem," Omega, Elsevier, vol. 56(C), pages 88-98.
    20. Angel A. Juan & Helena Ramalhinho-Lourenço & Manuel Mateo & Quim Castellà & Barry B. Barrios, 2012. "ILS-ESP: An efficient, simple, and parameter-free algorithm for solving the permutation flow-shop problem," Economics Working Papers 1319, Department of Economics and Business, Universitat Pompeu Fabra.

    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:243:y:2015:i:2:p:405-422. 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.