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. Altannar Chinchuluun & Panos Pardalos, 2007. "A survey of recent developments in multiobjective optimization," Annals of Operations Research, Springer, vol. 154(1), pages 29-50, October.
    3. 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.
    4. Hartmann, Sönke & Briskorn, Dirk, 2010. "A survey of variants and extensions of the resource-constrained project scheduling problem," European Journal of Operational Research, Elsevier, vol. 207(1), pages 1-14, November.
    5. 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.
    6. 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.
    7. Abraham P. Punnen & Ruonan Zhang, 2011. "Quadratic bottleneck problems," Naval Research Logistics (NRL), John Wiley & Sons, vol. 58(2), pages 153-164, March.
    8. He, Zhengwen & Liu, Renjing & Jia, Tao, 2012. "Metaheuristics for multi-mode capital-constrained project payment scheduling," European Journal of Operational Research, Elsevier, vol. 223(3), pages 605-613.
    9. 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.
    10. 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.
    11. 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.
    12. 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).
    13. 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.
    14. Cerrone, C. & Cerulli, R. & Raiconi, A., 2014. "Relations, models and a memetic approach for three degree-dependent spanning tree problems," European Journal of Operational Research, Elsevier, vol. 232(3), pages 442-453.
    15. Bogumiła Krzeszowska, 2013. "Three step procedure for a multiple criteria problem of project portfolio scheduling," Operations Research and Decisions, Wroclaw University of Science and Technology, Faculty of Management, vol. 23(4), pages 55-74.
    16. 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.
    17. Witkowski Tadeusz & Antczak Paweł & Antczak Arkadiusz, 2009. "Project Realization Scheduling and its Multi Criteria Evaluation," Foundations of Management, Sciendo, vol. 1(2), pages 25-44, January.
    18. Neumann, Frank, 2007. "Expected runtimes of a simple evolutionary algorithm for the multi-objective minimum spanning tree problem," European Journal of Operational Research, Elsevier, vol. 181(3), pages 1620-1629, September.
    19. Hartmann, Sönke & Briskorn, Dirk, 2008. "A survey of variants and extensions of the resource-constrained project scheduling problem," Working Paper Series 02/2008, Hamburg School of Business Administration (HSBA).
    20. Renaud, J. & Thibault, J. & Lanouette, R. & Kiss, L.N. & Zaras, K. & Fonteix, C., 2007. "Comparison of two multicriteria decision aid methods: Net Flow and Rough Set Methods in a high yield pulping process," European Journal of Operational Research, Elsevier, vol. 177(3), pages 1418-1432, 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.