Paper Info
Title
Improved differential evolution algorithms for solving generalized assignment problem
Abstract
DE is first designed to solve generalized assignment problem (GAP).The possibility of using new local search in DE for GAP is designed in order to get better solution.The computational results revealed that the proposed heuristic lies among the best algorithms found in the literature. This paper presents algorithms based on differential evolution (DE) to solve the generalized assignment problem (GAP) with the objective to minimize the assignment cost under the limitation of the agent capacity. Three local search techniques: shifting, exchange, and k-variable move algorithms are added to the DE algorithm in order to improve the solutions. Eight DE-based algorithms are presented, each of which uses DE with a different combination of local search techniques. The experiments are carried out using published standard instances from the literature. The best proposed algorithm using shifting and k-variable move as the local search (DE-SK) techniques was used to compare its performance with those of Bee algorithm (BEE) and Tabu search algorithm (TABU). The computational results revealed that the BEE and DE-SK are not significantly different while the DE-SK outperforms the TABU algorithm. However, even though the statistical test shows that DE-SK is not significantly different compared with the BEE algorithm, the DE-SK is able to obtain more optimal solutions (87.5%) compared to the BEE algorithm that can obtain only 12.5% optimal solutions. This is because the DE-SK is designed to enhance the search capability by improving the diversification using the DE's operators and the k-variable moves added to the DE can improve the intensification. Hence, the proposed algorithms, especially the DE-SK, can be used to solve various practical cases of GAP and other combinatorial optimization problems by enhancing the solution quality, while still maintaining fast computational time.
Year
DOI
Venue
2016
10.1016/j.eswa.2015.10.009
Expert Systems with Applications
Keywords
Field
DocType
Generalized assignment problem,Differential evolution algorithm,Shifting procedure,Exchange procedure
Search algorithm,Guided Local Search,Computer science,Generalized assignment problem,Artificial intelligence,Statistical hypothesis testing,Mathematical optimization,Heuristic,Algorithm,Differential evolution,Local search (optimization),Machine learning,Tabu search
Journal
Volume
Issue
ISSN
45
C
0957-4174
Citations 
PageRank 
References 
6
0.44
43
Authors
2
Name
Order
Citations
PageRank
Kanchana Sethanan1606.49
Rapeepan Pitakaso2323.85