Identifying preferred solutions in multiobjective combinatorial optimization problems

We develop an evolutionary algorithm for multiobjective combinatorial optimization problems. The algorithmaims at converging the preferred solutions of a decision-maker. We test the performance of the algorithm on themultiobjective knapsack and multiobjective spanning tree problems. We generate the true nondominated solutions usingan exact algorithm and compare the results with those of the evolutionary algorithm. We observe that the evolutionaryalgorithm works well in approximating the solutions in the preferred regions.

PDF

___

[1] Ehrgott M, Gandibleux X. Approximative solution methods for multi-objective combinatorial optimization. Top 2004; 12 (1): 1-63. doi: 10.1007/BF02578918
[2] Deb K. Multiobjective Optimization Using Evolutionary Algorithms. New York, NY, USA: Wiley, 2001.
[3] Hansen MP. Tabu search for multiobjective optimization: MOTS. In: 13th International Conference on Multiple Criteria Decision Making; Cape Town, South Africa; 1997. pp. 574-586.
[4] Ulungu EL, Teghem J, Fortemps PH, Tuyttens D. MOSA method: A tool for solving multiobjective combinatorial optimization problems. Journal of Multi-Criteria Decision Analysis 1999; 8: 221-236.
[5] Ehrgott M, Gandibleux X. Hybrid metaheuristics for multi-objective combinatorial optimization. In: Blum C, Aguilera MJB, Roli A, Sampels M (editors). Studies in Computational Intelligence, Vol. 114. Berlin, Germany: Springer, 2008, pp. 221-259.
[6] Deb K, Köksalan M. Guest editorial: Special issue on preference-based multiobjective evolutionary algorithms. IEEE Transactions on Evolutionary Computation 2010; 14 (5): 669-670. doi: 10.1109/TEVC.2010.2070371
[7] Rachmawati L, Srinivasan D. Preference incorporation in multi-objective evolutionary algorithms: a survey. In: IEEE 2006 Congress on Evolutionary Computation; Vancouver, BC, Canada; 2006. pp. 3385-3391.
[8] Phelps S, Köksalan M. An interactive evolutionary metaheuristic for multiobjective combinatorial optimization. Management Science 2003; 49 (12): 1726-1738. doi: 10.1287/mnsc.49.12.1726.25117
[9] Köksalan M, Karahan İ. An interactive territory defining evolutionary algorithm: iTDEA. IEEE Transactions on Evolutionary Computation 2010; 14 (5): 702-722. doi: 10.1109/TEVC.2010.2070070
[10] Köksalan M, Phelps SP. An evolutionary metaheuristic for approximating preference-nondominated solutions. INFORMS Journal on Computing 2007; 19 (2): 291-301. doi: 10.1287/ijoc.1050.0170
[11] Chen J, Li J, Xin B. DMOEA-εC: decomposition-based multiobjective evolutionary algorithm with the ε-constraint framework. IEEE Transactions on Evolutionary Computation 2017; 21 (5): 714-730. doi: 10.1109/TEVC.2017.2671462
[12] Zhang H, Zhou A, Song S, Zhang Q, Gao XZ et al. A self-organizing multiobjective evolutionary algorithm. IEEE Transactions on Evolutionary Computation 2016; 20 (5): 792-806. doi: 10.1109/TEVC.2016.2521868
[13] Jaszkiewicz A. Genetic local search for multi-objective combinatorial optimization. European Journal of Operational Research 2002; 137: 50-71. doi: 10.1016/S0377-2217(01)00104-7
[14] Soylu B, Köksalan M. A favorable weight based evolutionary algorithm for multiple criteria problems. IEEE Transactions on Evolutionary Computation 2010; 14 (2): 191-205. doi: 10.1109/TEVC.2009.2027357
[15] Soylu B, Köksalan M. An evolutionary algorithm for the multi-objective multiple knapsack problem. In: Shi Y, Wang S, Peng Y, Li J, Zeng Y (editors). MCDM 2009: Cutting-Edge Research Topics on Multiple Criteria Decision Making. Communications in Computer and Information Science, Vol. 35. Berlin, Germany: Springer, 2009, pp. 1-8.
[16] Alves MJ, Almeida M. MOTGA: A multiobjective Tchebycheff based genetic algorithm for the multidimensional knapsack problem. Computers & Operations Research 2007; 34: 3458-3470. doi: 10.1016/j.cor.2006.02.008
[17] Arroyo JEC, Vieira PS, Vianna DS. A GRASP algorithm for the multi-criteria minimum spanning tree problem. Annals of Operations Research 2008; 159 (1): 125-133. doi: 10.1007/s10479-007-0263-4
[18] Chen G, Chen S, Guo W, Chen W. The multicriteria minimum spanning tree problem based genetic algorithm. Information Sciences 2007; 177 (22): 5050-5063. doi: 10.1016/j.ins.2007.06.005
[19] Zhou G, Gen M. Genetic algorithm approach on multi-criteria minimum spanning tree problem. European Journal of Operational Research 1999; 114: 141-152. doi: 10.1016/S0377-2217(98)00016-2
[20] Köksalan M. Multiobjective combinatorial optimization: some approaches. Journal of Multi-Criteria Decision Analysis 2009; 15: 69-78. doi: 10.1002/mcda.425
[21] Köksalan M, Lokman B. Approximating the nondominated frontiers of multi-objective combinatorial optimization problems. Naval Research Logistics 2009; 56: 191–198. doi: 10.1002/nav.20336
[22] Reeves CR. Genetic algorithms. In: Reeves CR (editor). Modern Heuristic Techniques for Combinatorial Problems. New York, NY, USA: Halsted Press, 1993. pp. 151-188.
[23] Steuer RE. Multiple Criteria Optimization: Theory, Computation, and Application. New York, NY, USA: Wiley, 1986.
[24] Lokman B, Köksalan M. Finding all nondominated points of multi-objective integer programs. Journal of Global Optimization 2013; 57 (2): 347-365. doi: 10.1007/s10898-012-9955-7
[25] Zitzler E, Brockhoff D, Thiele L. The hypervolume indicator revisited: on the design of Pareto-compliant indicators via weighted integration. In: Obayashi S, Deb K, Poloni C, Hiroyasu T, Murata T (editors). Conference on Evolutionary Multi-Criterion Optimization; Volume 4403 of LNCS. Berlin, Germany: Springer, 2007. pp. 862-876.
[26] Zitzler E, Thiele L, Laumanns M, Fonseca CM, Grunert da Fonseca V. Performance assessment of multiobjective optimizers: an analysis and review. IEEE Transactions on Evolutionary Computation 2003; 7 (2): 117–132. doi: 10.1109/TEVC.2003.810758