IDEAS home Printed from https://ideas.repec.org/a/inm/ormnsc/v49y2003i12p1726-1738.html
   My bibliography  Save this article

An Interactive Evolutionary Metaheuristic for Multiobjective Combinatorial Optimization

Author

Listed:
  • Selcen (Pamuk) Phelps

    (Industrial Engineering Department, Middle East Technical University, 06531 Ankara, Turkey)

  • Murat Köksalan

    (Industrial Engineering Department, Middle East Technical University, 06531 Ankara, Turkey)

Abstract

We propose an evolutionary metaheuristic for multiobjective combinatorial optimization problems that interacts with the decision maker (DM) to guide the search effort toward his or her preferred solutions. Solutions are presented to the DM, whose pairwise comparisons are then used to estimate the desirability or fitness of newly generated solutions. The evolutionary algorithm comprising the skeleton of the metaheuristic makes use of selection strategies specifically designed to address the multiobjective nature of the problem. Interactions with the DM are triggered by a probabilistic evaluation of estimated fitnesses, while memory structures with indifference thresholds restrict the presentation of solutions resembling those that have already been rejected. The algorithm has been tested on a number of random instances of the Multiobjective Knapsack Problem (MOKP) and the Multiobjective Spanning Tree Problem (MOST). Simulation results indicate that the algorithm requires only a small number of comparisons to be made for satisfactory solutions to be found.

Suggested Citation

  • Selcen (Pamuk) Phelps & Murat Köksalan, 2003. "An Interactive Evolutionary Metaheuristic for Multiobjective Combinatorial Optimization," Management Science, INFORMS, vol. 49(12), pages 1726-1738, December.
    • Handle: RePEc:inm:ormnsc:v:49:y:2003:i:12:p:1726-1738
    DOI: 10.1287/mnsc.49.12.1726.25117
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/mnsc.49.12.1726.25117
    Download Restriction: no
    File URL: https://libkey.io/10.1287/mnsc.49.12.1726.25117?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
    ---><---

    References listed on IDEAS

    as
    1. Hapke, Maciej & Jaszkiewicz, Andrzej & Slowinski, Roman, 1998. "Interactive analysis of multiple-criteria project scheduling problems," European Journal of Operational Research, Elsevier, vol. 107(2), pages 315-324, June.
    2. Zhou, Gengui & Gen, Mitsuo, 1999. "Genetic algorithm approach on multi-criteria minimum spanning tree problem," European Journal of Operational Research, Elsevier, vol. 114(1), pages 141-152, April.
    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. Jyrki Wallenius & James S. Dyer & Peter C. Fishburn & Ralph E. Steuer & Stanley Zionts & Kalyanmoy Deb, 2008. "Multiple Criteria Decision Making, Multiattribute Utility Theory: Recent Accomplishments and What Lies Ahead," Management Science, INFORMS, vol. 54(7), pages 1336-1349, July.
    2. M. K. Pandey & M. K. Tiwari & M. J. Zuo, 2007. "Interactive enhanced particle swarm optimization: A multi-objective reliability application," Journal of Risk and Reliability, , vol. 221(3), pages 177-191, September.
    3. Sinha, Ankur & Korhonen, Pekka & Wallenius, Jyrki & Deb, Kalyanmoy, 2014. "An interactive evolutionary multi-objective optimization algorithm with a limited number of decision maker calls," European Journal of Operational Research, Elsevier, vol. 233(3), pages 674-688.
    4. Wang, Rui & Purshouse, Robin C. & Giagkiozis, Ioannis & Fleming, Peter J., 2015. "The iPICEA-g: a new hybrid evolutionary multi-criteria decision making approach using the brushing technique," European Journal of Operational Research, Elsevier, vol. 243(2), pages 442-453.
    5. Korhonen, Pekka J. & Silvennoinen, Kari & Wallenius, Jyrki & Öörni, Anssi, 2012. "Can a linear value function explain choices? An experimental study," European Journal of Operational Research, Elsevier, vol. 219(2), pages 360-367.
    6. Miłosz Kadziński & Michał K. Tomczyk, 2017. "Interactive Evolutionary Multiple Objective Optimization for Group Decision Incorporating Value-based Preference Disaggregation Methods," Group Decision and Negotiation, Springer, vol. 26(4), pages 693-728, July.
    7. Özgür Özpeynirci & Murat Köksalan, 2010. "An Exact Algorithm for Finding Extreme Supported Nondominated Points of Multiobjective Mixed Integer Programs," Management Science, INFORMS, vol. 56(12), pages 2302-2315, December.
    8. Branke, Juergen & Corrente, Salvatore & Greco, Salvatore & Słowiński, Roman & Zielniewicz, Piotr, 2016. "Using Choquet integral as preference model in interactive evolutionary multiobjective optimization," European Journal of Operational Research, Elsevier, vol. 250(3), pages 884-901.
    9. João Claro & Jorge Sousa, 2010. "A multiobjective metaheuristic for a mean-risk static stochastic knapsack problem," Computational Optimization and Applications, Springer, vol. 46(3), pages 427-450, July.
    10. Fowler, John W. & Gel, Esma S. & Köksalan, Murat M. & Korhonen, Pekka & Marquis, Jon L. & Wallenius, Jyrki, 2010. "Interactive evolutionary multi-objective optimization for quasi-concave preference functions," European Journal of Operational Research, Elsevier, vol. 206(2), pages 417-425, October.
    11. Murat Köksalan & Selcen (Pamuk) Phelps, 2007. "An Evolutionary Metaheuristic for Approximating Preference-Nondominated Solutions," INFORMS Journal on Computing, INFORMS, vol. 19(2), pages 291-301, May.
    12. Molina, Julin & Santana, Luis V. & Hernandez-Daz, Alfredo G. & Coello Coello, Carlos A. & Caballero, Rafael, 2009. "g-dominance: Reference point based dominance for multiobjective metaheuristics," European Journal of Operational Research, Elsevier, vol. 197(2), pages 685-692, September.
    13. Kaliszewski, Ignacy & Miroforidis, Janusz & Podkopaev, Dmitry, 2012. "Interactive Multiple Criteria Decision Making based on preference driven Evolutionary Multiobjective Optimization with controllable accuracy," European Journal of Operational Research, Elsevier, vol. 216(1), pages 188-199.
    14. Barbati, Maria & Corrente, Salvatore & Greco, Salvatore, 2020. "A general space-time model for combinatorial optimization problems (and not only)," Omega, Elsevier, vol. 96(C).
    15. Corrente, Salvatore & Greco, Salvatore & Matarazzo, Benedetto & Słowiński, Roman, 2024. "Explainable interactive evolutionary multiobjective optimization," Omega, Elsevier, vol. 122(C).
    16. Banu Lokman & Murat Köksalan, 2013. "Finding all nondominated points of multi-objective integer programs," Journal of Global Optimization, Springer, vol. 57(2), pages 347-365, October.

    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. Lacour, Renaud, 2014. "Approches de résolution exacte et approchée en optimisation combinatoire multi-objectif, application au problème de l'arbre couvrant de poids minimal," Economics Thesis from University Paris Dauphine, Paris Dauphine University, number 123456789/14806 edited by Vanderpooten, Daniel.
    2. Drexl, Andreas & Nikulin, Yury, 2006. "Fuzzy multicriteria flight gate assignment," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 605, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    3. 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.
    4. Viana, Ana & Pinho de Sousa, Jorge, 2000. "Using metaheuristics in multiobjective resource constrained project scheduling," European Journal of Operational Research, Elsevier, vol. 120(2), pages 359-374, January.
    5. Yukang He & Tao Jia & Weibo Zheng, 2024. "Simulated annealing for centralised resource-constrained multiproject scheduling to minimise the maximal cash flow gap under different payment patterns," Annals of Operations Research, Springer, vol. 338(1), pages 115-149, July.
    6. Juan Villegas & Fernando Palacios & Andrés Medaglia, 2006. "Solution methods for the bi-objective (cost-coverage) unconstrained facility location problem with an illustrative example," Annals of Operations Research, Springer, vol. 147(1), pages 109-141, October.
    7. 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.
    8. Zhou, Gengui & Min, Hokey & Gen, Mitsuo, 2003. "A genetic algorithm approach to the bi-criteria allocation of customers to warehouses," International Journal of Production Economics, Elsevier, vol. 86(1), pages 35-45, October.
    9. Wen, Hao & Sang, Song & Qiu, Chenhui & Du, Xiangrui & Zhu, Xiao & Shi, Qian, 2019. "A new optimization method of wind turbine airfoil performance based on Bessel equation and GABP artificial neural network," Energy, Elsevier, vol. 187(C).
    10. 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.
    11. Zhengwen He & Nengmin Wang & Pengxiang Li, 2014. "Simulated annealing for financing cost distribution based project payment scheduling from a joint perspective," Annals of Operations Research, Springer, vol. 213(1), pages 203-220, February.
    12. Knowles, Joshua D. & Corne, David W., 2002. "Enumeration of Pareto optimal multi-criteria spanning trees - a proof of the incorrectness of Zhou and Gen's proposed algorithm," European Journal of Operational Research, Elsevier, vol. 143(3), pages 543-547, December.
    13. Diabat, Ali & Kannan, Devika & Kaliyan, Mathiyazhagan & Svetinovic, Davor, 2013. "An optimization model for product returns using genetic algorithms and artificial immune system," Resources, Conservation & Recycling, Elsevier, vol. 74(C), pages 156-169.
    14. Dali Jiang & Haitao Li & Tinghong Yang & De Li, 2016. "Genetic algorithm for inventory positioning problem with general acyclic supply chain networks," European Journal of Industrial Engineering, Inderscience Enterprises Ltd, vol. 10(3), pages 367-384.
    15. Mak, Brenda & Blanning, Robert & Ho, Susanna, 2006. "Genetic algorithms in logic tree decision modeling," European Journal of Operational Research, Elsevier, vol. 170(2), pages 597-612, April.
    16. Molina, Julin & Santana, Luis V. & Hernandez-Daz, Alfredo G. & Coello Coello, Carlos A. & Caballero, Rafael, 2009. "g-dominance: Reference point based dominance for multiobjective metaheuristics," European Journal of Operational Research, Elsevier, vol. 197(2), pages 685-692, September.
    17. Andréa Santos & Diego Lima & Dario Aloise, 2014. "Modeling and solving the bi-objective minimum diameter-cost spanning tree problem," Journal of Global Optimization, Springer, vol. 60(2), pages 195-216, October.
    18. Kolisch, R. & Padman, R., 2001. "An integrated survey of deterministic project scheduling," Omega, Elsevier, vol. 29(3), pages 249-272, June.
    19. Drexl, Andreas & Nikulin, Yuri, 2005. "Multicriteria time window-constrained project scheduling with applications to airport gate assignment. Part I: Methodology," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 595, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    20. Shahryar Monghasemi & Mohammad Reza Nikoo & Mohammad Ali Khaksar Fasaee & Jan Adamowski, 2017. "A Hybrid of Genetic Algorithm and Evidential Reasoning for Optimal Design of Project Scheduling: A Systematic Negotiation Framework for Multiple Decision-Makers," International Journal of Information Technology & Decision Making (IJITDM), World Scientific Publishing Co. Pte. Ltd., vol. 16(02), pages 389-420, March.

    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:inm:ormnsc:v:49:y:2003:i:12:p:1726-1738. 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: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    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.