An Evolutionary Algorithm for the Multi-objective Multiple Knapsack Problem

Date

2009-06-26

Author

SOYLU, Banu
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

247
views

0
downloads

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 carry Out experiments on test data for MMKP given in the literature and compare the performance of the algorithm with several leading algorithms

Subject Keywords

Evolutionary algorithms, Multiple knapsack problem

URI

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

DOI

https://doi.org/10.1007/978-3-642-02298-2_1

Collections

Department of Industrial Engineering, Conference / Seminar

Suggestions

OpenMETU
Core

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...
A hybrid genetic algorithm for the discrete time-cost trade-off problem Sönmez, Rifat (2012-10-01) In this paper we present a hybrid strategy developed using genetic algorithms (GAs), simulated annealing (SA), and quantum simulated annealing techniques (QSA) for the discrete time-cost trade-off problem (DTCTP). In the hybrid algorithm (HA), SA is used to improve hill-climbing ability of GA. In addition to SA, the hybrid strategy includes QSA to achieve enhanced local search capability. The HA and a sole GA have been coded in Visual C++ on a personal computer. Ten benchmark test problems with a range of 1...
An evolutionary algorithm for multiple criteria problems Soylu, Banu; Köksalan, Murat; Department of Industrial Engineering (2007) In this thesis, we develop an evolutionary algorithm for approximating the Pareto frontier of multi-objective continuous and combinatorial optimization problems. The algorithm tries to evolve the population of solutions towards the Pareto frontier and distribute it over the frontier in order to maintain a well-spread representation. The fitness score of each solution is computed with a Tchebycheff distance function and non-dominating sorting approach. Each solution chooses its own favorable weights accordin...
Interactive evolutionary multi-objective optimization for quasi-concave preference functions Fowler, John W.; Gel, Esma S.; Köksalan, Mustafa Murat; Korhonen, Pekka; Marquis, Jon L.; Wallenius, Jyrki (2010-10-16) 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 its to implicitly rank solutions that the DM has not considered. This technique avoids assuming an exact form for the pref...
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

B. SOYLU and M. M. Köksalan, “An Evolutionary Algorithm for the Multi-objective Multiple Knapsack Problem,” 2009, vol. 35, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/51136.