A novel differential evolution mapping technique for generic combinatorial optimization problems

Ismail Ali

doi:10.1016/j.asoc.2019.04.017

2019-07-01

PRE

Ismail Ali *

Daryl Essam

Kathryn Kasmarik

DOI：10.1016/j.asoc.2019.04.017

原文链接

原文求助

摘要

En 中文

Differential evolution is primarily designed and used to solve continuous optimization problems. Therefore, it has not been widely considered as applicable for real-world problems that are characterized by permutation-based combinatorial domains. Many algorithms for solving discrete problems using differential evolution have been proposed, some of which have achieved promising results. However, to enhance their performance, they require improvements in many aspects, such as their convergence speeds, computational times and capabilities to solve large discrete problems. In this paper, we present a new mapping method that may be used with differential evolution to solve combinatorial optimization problems. This paper focuses specifically on the mapping component and its effect on the performance of differential evolution. Our method maps continuous variables to discrete ones, while at the same time, it directs the discrete solutions produced towards optimality, by using the best solution in each generation as a guide. To judge its performance, its solutions for instances of well-known discrete problems, namely: 0/1 knapsack, traveling salesman and traveling thief problems, are compared with those obtained by 8 other state-of-the-art mapping techniques. To do this, all mapping techniques are used with the same differential evolution settings. The results demonstrated that our technique significantly outperforms the other mapping methods in terms of the average error from the best-known solution for the traveling salesman problems, and achieves promising results for both the 0/1 knapsack and the traveling thief problems. (C) 2019 Elsevier B.V. All rights reserved.

Keyword:

Discrete differential evolution

Combinatorial optimization problems

0/1 knapsack problems

Traveling salesman problems

Traveling thief problems

AI总结

对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。

期刊

Applied Soft Computing

IF:

6.6

论文数:

1.4W

被引数:

4.8W

机构

暂无机构信息

引用论文

A hybrid cuckoo search via Levy flights for the permutation flow shop scheduling problem

INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH

IF7.3

2013-08-01

PREAI

Li, Xiangtao; Yin, Minghao

5 a day for better health: A new research initiative

Journal of the American Dietetic Association

IF0

1994-01-01

PREAI

Stephen Havas; Jerianne Heimendinger; Kim Reynolds; Tom Baranowski; Theresa A Nicklas; Donald Bishop; David Buller; Glorian Sorensen; Shirley A.A Beresford; Arnette Cowan; Dorothy Damron

Bi-Velocity Discrete Particle Swarm Optimization and Its Application to Multicast Routing Problem in Communication Networks

IEEE TRANSACTIONS ON INDUSTRIAL ELECTRONICS

IF7.2

2014-12-01