An evolutionary metaheuristic for approximating preference-nondominated solutions

Download

index.pdf

Date

2007-03-01

Author

Koekalan, Murat
Phelps, Selcen (Pamuk)

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

139
views

0
downloads

We propose an evolutionary metaheuristic for approximating the preference-nondominated solutions of a decision maker in multiobjective combinatorial problems. The method starts out with some partial preference information provided by the decision maker, and utilizes an individualized fitness function to converge toward a representative set of solutions favored by the information at hand. The breadth of the set depends on the precision of the partial information available on the decision maker's preferences. The algorithm simultaneously evolves the population of solutions out toward the efficient frontier, focuses the population on those segments of the efficient frontier that will appeal to the decision maker, and disperses it over these segments to have an adequate representation. Simulation runs carried out on randomly generated instances of the multiobjective knapsack problem and the multiobjective spanning-tree problem have found the algorithm to yield highly satisfactory results.

Subject Keywords

Evolutionary heuristic, Combinatorial optimization, Multiple criteria

URI

https://hdl.handle.net/11511/65735

Journal

INFORMS JOURNAL ON COMPUTING

DOI

https://doi.org/10.1287/ijoc.1050.0170

Collections

Department of Industrial Engineering, Article

Suggestions

OpenMETU
Core

An interactive evolutionary metaheuristic for multiobjective combinatorial optimization Phelps, S; Köksalan, Mustafa Murat (2003-12-01) 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 na...
An interactive approach for placing alternatives in preference classes Köksalan, Mustafa Murat; Ulu, C (2003-01-16) In this paper, we consider the multiple criteria decision making problem of partitioning alternatives into preference classes. We develop an interactive procedure based on the assumption that the decision maker (DM) has a linear utility function. The approach requires the DM to place an alternative in a preference class from time to time. Based on the preference information derived from the DM's placement as well as from dominance and linearity, we try to place other alternatives. We present results on the ...
An interactive genetic algorithm applied to the multiobjective knapsack problem Pamuk, S; Köksalan, Mustafa Murat (2001-01-01) Multiobjective combinatorial problems are commonly encountered in practice and would benefit from the development of metaheuristics where the search effort is interactively guided towards the solutions favored by the decision maker. The present study introduces such an Interactive Genetic Algorithm designed for a general multiobjective combinatorial framework and discusses its behavior in simulations on the Multiobjective Knapsack Problem. The evolution strategies being employed reflect the multiobjective n...
An Evolutionary Algorithm for the Multi-objective Multiple Knapsack Problem SOYLU, Banu; Köksalan, Mustafa Murat (2009-06-26) In this study, we consider the multi-objective multiple knapsack problem (MMKP) and we adapt our favorable weight based evolutionary algorithm (FWEA) to approximate the efficient frontier of MMKP. The algorithm assigns fitness to solutions based on their relative strengths as well as their non-dominated frontiers. The relative strength is measured based on a weighted Tchebycheff distance from the ideal point where each Solution chooses its own weights that minimize its distance from the ideal point. We carr...
An interactive ranking-based multi-criteria choice algorithm with filtering: Applications to university selection Karakaya, Gülşah (Orta Doğu Teknik Üniversitesi (Ankara, Turkey), 2019-6) In this study, we develop an interactive algorithm to converge to the most preferred alternative of a decision maker (DM) among a set of discrete alternatives. The algorithm presents a limited number of alternatives to the DM and collects preference ranking of them iteratively. The preferences are modeled by a flexible and realistic preference function. To improve the performance, the alternatives presented are determined by a filtering method. We compare our algorithm with benchmark algorithms on nume...

Citation Formats

M. Koekalan and S. (. Phelps, “An evolutionary metaheuristic for approximating preference-nondominated solutions,” INFORMS JOURNAL ON COMPUTING, pp. 291–301, 2007, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/65735.