×

Interactive evolutionary multi-objective optimization for quasi-concave preference functions. (English) Zbl 1188.90211

Summary: We present a new hybrid approach to interactive evolutionary multi-objective optimization that uses a partial preference order to act as the fitness function in a customized genetic algorithm. We periodically send solutions to the decision maker (DM) for her evaluation and use the resulting preference information to form preference cones consisting of inferior solutions. The cones allow us to implicitly rank solutions that the DM has not considered. This technique avoids assuming an exact form for the preference function, but does assume that the preference function is quasi-concave. This paper describes the genetic algorithm and demonstrates its performance on the multi-objective knapsack problem.

MSC:

90C27 Combinatorial optimization
90C59 Approximation methods and heuristics in mathematical programming
90C29 Multi-objective and goal programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ahuja, Ravindra; Orlin, James; Tiwari, Ashish, A greedy genetic algorithm for the quadratic assignment problem, Computers and Operations Research, 27, 917-934 (2000) · Zbl 0970.90067
[2] Branke, J., Deb, Kalyanmoy, 2004. Integrating user preferences into evolutionary multi-objective optimization. KanGal Report, Indian Institute of Technology, Kanpur, India.; Branke, J., Deb, Kalyanmoy, 2004. Integrating user preferences into evolutionary multi-objective optimization. KanGal Report, Indian Institute of Technology, Kanpur, India.
[3] Caballero, R.; Luque, M.; Molina, M.; Ruiz, F., Promoin: An interactive system for multiobjective programming, International Journal of Information Technology and Decision Making, 1, 635-656 (2002)
[4] Coello Coello, Carlos A., 2000. Handling preferences in evolutionary multiobjective optimization: A survey. In: Proceedings of the 2000 Congress on Evolutionary Computation, pp. 30-37.; Coello Coello, Carlos A., 2000. Handling preferences in evolutionary multiobjective optimization: A survey. In: Proceedings of the 2000 Congress on Evolutionary Computation, pp. 30-37. · Zbl 1066.01025
[5] Cvetkovic, Dragan; Parmee, Ian C., Preferences and their application in evolutionary multiobjective optimization, IEEE Transactions on Evolutionary Computation, 6, 42-57 (2002)
[6] Deb, Kalyanmoy, Multi-Objective Optimization Using Evolutionary Algorithms (2001), Wiley: Wiley Chichester · Zbl 0970.90091
[7] Deb, Kalyanmoy; Pratap, Amrit; Agarwal, Sameer; Meyarivan, T., A fast and elitist multiobjective genetic algorithm: Nsga-ii, IEEE Transactions on Evolutionary Computation, 6, 182-197 (2002)
[8] Deb, Kalyanmoy, Sundar, J., Uday, B.R.N., 2005. Reference point based multi-objective optimization using evolutionary algorithms. KanGal Report, Indian Institute of Technology, Kanpur, India.; Deb, Kalyanmoy, Sundar, J., Uday, B.R.N., 2005. Reference point based multi-objective optimization using evolutionary algorithms. KanGal Report, Indian Institute of Technology, Kanpur, India.
[9] Dyer, James; Fishburn, Peter; Steuer, Ralph; Wallenius, Jyrki; Zionts, Stanley, Multiple criteria decision making, multiattribute utility theory: The next ten years, Management Science, 38, 645-654 (1992) · Zbl 0825.90620
[10] Fonseca, C.M., Fleming, P.J., 1993. Genetic algorithms for multiobjective optimization: Formulation, discussion, and generalization. In: Proceedings of the Fifth International Conference on Genetic Algorithms, pp. 416-423.; Fonseca, C.M., Fleming, P.J., 1993. Genetic algorithms for multiobjective optimization: Formulation, discussion, and generalization. In: Proceedings of the Fifth International Conference on Genetic Algorithms, pp. 416-423.
[11] Fonseca, C. M.; Fleming, P. J., Multiobjective optimization and multiple constraint handling with evolutionary algorithms. Part II: Application example, IEEE Transactions on Systems, Man and Cybernetics, Part A: Systems and Humans, 28, 38-47 (1998)
[12] Geoffrion, A. M.; Dyer, J. S.; Feinberg, A., An interactive approach for multicriterion optimization, with an application to the operation of an academic department, Management Science, 19, 683-694 (1972) · Zbl 0247.90069
[13] Hanne, T., Interactive decision support based on multiobjective evolutionary algorithms, Operations Research Proceedings (GOR), 761-766 (2005)
[14] Horn, J., Nafploitis, N., Goldberg, D., 1995. A niched pareto genetic algorithm for multi-objective optimization. In: Proceedings of the First IEEE Conference on Evolutionary Computation, pp. 82-87.; Horn, J., Nafploitis, N., Goldberg, D., 1995. A niched pareto genetic algorithm for multi-objective optimization. In: Proceedings of the First IEEE Conference on Evolutionary Computation, pp. 82-87.
[15] Kamalian, R., Takagi, H., Agogino, A., 2004. Optimized design of MEMS by evolutionary multi-objective optimization with interactive evolutionary computation. In: Genetic and Evolutionary Computation Conference (GECCO), pp. 1030-1041.; Kamalian, R., Takagi, H., Agogino, A., 2004. Optimized design of MEMS by evolutionary multi-objective optimization with interactive evolutionary computation. In: Genetic and Evolutionary Computation Conference (GECCO), pp. 1030-1041.
[16] Köksalan, Murat; Phelps, Selcen (Pamuk), An evolutionary metaheuristic for approximating preference-nondominated solutions, INFORMS Journal on Computing, 19, 291-301 (2007) · Zbl 1241.90114
[17] Kondakci, S.; Azizoglu, M.; Köksalan, M., Note: Bicriteria scheduling minimizing flowtime and maximum tardiness, Naval Research Logistics, 43, 929-936 (1996) · Zbl 0858.90077
[18] Korhonen, Pekka; Wallenius, Jyrki; Zionts, Stanley, Solving the discrete multiple criteria problem using convex cones, Management Science, 30, 1336-1345 (1984) · Zbl 0557.90090
[19] Michalewicz, Zbigniew, Genetic Algorithms+Data Structures=Evolution Algorithms (1996), Springer: Springer Berlin, Heidelberg, and New York · Zbl 0841.68047
[20] Miettinen, Kaisa, Nonlinear Multiobjective Optimization (1999), Kluwer Academic Publishers.: Kluwer Academic Publishers. Boston, London, and Dordrecht · Zbl 0949.90082
[21] Miller, George A., The magical number seven, plus or minus two: Some limits on our capacity for processing information, The Psychological Review, 63, 81-97 (1956)
[22] Molina, J.; Santana, L. V.; Hernandez-Diaz, A. G.; Coello Coello, C. A.; Caballero, R., G-dominance: Reference point based dominance for multiobjective metaheuristics, European Journal of Operational Research, 197, 685-692 (2009) · Zbl 1159.90424
[23] Myers, Raymond; Montgomery, Douglas, Response Surface Methodology: Process and Product Optimization Using Designed Experiments (2002), Wiley: Wiley New York · Zbl 1161.62393
[24] Parmee, I. C.; Cvetkovic, D.; Bonham, C. R.; Packahm, I. S., Introducing prototype interactive evolutionary systems for ill-defined multi-objective design environments, Advances in Engineering Software, 32, 429-441 (2001) · Zbl 1003.68579
[25] Phelps, Selcen (Pamuk); Köksalan, Murat, An interactive evolutionary metaheuristic for multiobjective combinatorial optimization, Management Science, 49, 1726-1738 (2003) · Zbl 1232.90330
[26] Poles, S., Vassileva, M., Sasaki, D., 2006. Multiobjective optimization software. In: Branke, J., Deb, K., Miettinen, K., Slowinski, R. (Eds.), Published as a Chapter in Springer State-of-the-Art Survey LNCS 5252 Multiobjective Optimization: Interactive and Evolutionary Approaches.; Poles, S., Vassileva, M., Sasaki, D., 2006. Multiobjective optimization software. In: Branke, J., Deb, K., Miettinen, K., Slowinski, R. (Eds.), Published as a Chapter in Springer State-of-the-Art Survey LNCS 5252 Multiobjective Optimization: Interactive and Evolutionary Approaches.
[27] Schaffer, J.D., 1984. Some experiments in machine learning using vector evaluated genetic algorithms. Ph.D. Thesis, Vanderbilt University, Nashville, Tennessee.; Schaffer, J.D., 1984. Some experiments in machine learning using vector evaluated genetic algorithms. Ph.D. Thesis, Vanderbilt University, Nashville, Tennessee.
[28] Srinivas, N.; Deb, K., Multi-objective function optimization using non-dominated sorting genetic algorithms, Evolutionary Computation Journal, 2, 221-248 (1994)
[29] Wall, Matthew, 1995. Massachusetts Institute of Technology’s GAlib Library. <http://web.mit.edu/galib/www/GAlib.html; Wall, Matthew, 1995. Massachusetts Institute of Technology’s GAlib Library. <http://web.mit.edu/galib/www/GAlib.html
[30] Wallenius, J.; Dyer, J. S.; Fishburn, P. C.; Steuer, R. E.; Zionts, S.; Deb, K., Multiple criteria decision making/multiattribute utility theory: Recent accomplishments and what lies ahead, Management Science, 54, 1336-1349 (2008) · Zbl 1232.90228
[31] Zionts, S.; Wallenius, J., An interactive programming method for solving the multiple criteria problem, Management Science, 22, 652-663 (1976) · Zbl 0318.90053
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.