An interactive genetic algorithm applied to the multiobjective knapsack problem

Date

2001-01-01

Author

Pamuk, S
Köksalan, Mustafa Murat

Metadata

Show full item record

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

Item Usage Stats

191
views

0
downloads

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 nature of the problem. The fitness of individuals in the population is estimated on the basis of preference information elicited from the decision maker, and continuously updated as the algorithm progresses. The presented results indicate that the algorithm performs well when simulated against decision makers with different underlying utility functions.

Subject Keywords

Multiobjective combinatorial optimization, Genetic algorithm, Knapsack

URI

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

Journal

MULTIPLE CRITERIA DECISION MAKING IN THE NEW MILLENNIUM

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 partitioning approach for multiobjective decision making under a general monotone utility function Karasakal, Esra (2013-09-01) We develop an interactive partitioning approach for solving the multiobjective decision making problem of a decision maker (DM) who has an implicit general monotone utility function. The approach reduces feasible solution space using the DM's preferences. Hypothetical solutions called partition ideals (PIs) that dominate portions of the efficient frontier are generated and those that are inferior to a feasible solution are used to eliminate the dominated regions. We investigate the issues in representation ...
An interactive preference based multiobjective evolutionary algorithm for the clustering problem Demirtaş, Kerem; Özdemirel, Nur Evin; Karasakal, Esra; Department of Industrial Engineering (2011) We propose an interactive preference-based evolutionary algorithm for the clustering problem. The problem is highly combinatorial and referred to as NP-Hard in the literature. The goal of the problem is putting similar items in the same cluster and dissimilar items into different clusters according to a certain similarity measure, while maintaining some internal objectives such as compactness, connectivity or spatial separation. However, using one of these objectives is often not sufficient to detect differ...
An interactive approach for biobjective integer programs under quasiconvex preference functions Ozturk, Diclehan Tezcaner; Köksalan, Mustafa Murat (2016-09-01) We develop an interactive algorithm for biobjective integer programs that finds the most preferred solution of a decision maker whose preferences are consistent with a quasiconvex preference function to be minimized. During the algorithm, preference information is elicited from the decision maker. Based on this preference information and the properties of the underlying quasiconvex preference function, the algorithm reduces the search region and converges to the most preferred solution progressively. Findin...
Identifying preferred solutions in multiobjective combinatorial optimization problems Lokman, Banu (2019-01-01) We develop an evolutionary algorithm for multiobjective combinatorial optimization problems. The algorithm aims at converging the preferred solutions of a decision-maker. We test the performance of the algorithm on the multiobjective knapsack and multiobjective spanning tree problems. We generate the true nondominated solutions using an exact algorithm and compare the results with those of the evolutionary algorithm. We observe that the evolutionary algorithm works well in approximating the solutions in the...

Citation Formats

S. Pamuk and M. M. Köksalan, “An interactive genetic algorithm applied to the multiobjective knapsack problem,” MULTIPLE CRITERIA DECISION MAKING IN THE NEW MILLENNIUM, pp. 265–272, 2001, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/54560.