Discrete Bird Swarm Algorithm Based on Information Entropy Matrix for Traveling Salesman Problem
Joint Authors
Zhong, Yiwen
Lin, Juan
Lin, Min
Lin, Xiaoyu
Source
Mathematical Problems in Engineering
Issue
Vol. 2018, Issue 2018 (31 Dec. 2018), pp.1-15, 15 p.
Publisher
Hindawi Publishing Corporation
Publication Date
2018-10-30
Country of Publication
Egypt
No. of Pages
15
Main Subjects
Abstract EN
Although bird swarm optimization (BSA) algorithm shows excellent performance in solving continuous optimization problems, it is not an easy task to apply it solving the combination optimization problem such as traveling salesman problem (TSP).
Therefore, this paper proposed a novel discrete BSA based on information entropy matrix (DBSA) for TSP.
Firstly, in the DBSA algorithm, the information entropy matrix is constructed as a guide for generating new solutions.
Each element of the information entropy matrix denotes the information entropy from city i to city j.
The higher the information entropy, the larger the probability that a city will be visited.
Secondly, each TSP path is represented as an array, and each element of the array represents a city index.
Then according to the needs of the minus function proposed in this paper, each TSP path is transformed into a Boolean matrix which represents the relationship of edges.
Third, the minus function is designed to evaluate the difference between two Boolean matrices.
Based on the minus function and information entropy matrix, the birds’ position updating equations are redesigned to update the information entropy matrix without changing the original features.
Then three TSP operators are proposed to generate new solutions according to the updated information entropy matrix.
Finally, the performance of DBSA algorithm was tested on a large number of benchmark TSP instances.
Experimental results show that DBSA algorithm is better or competitively outperforms many state-of-the-art metaheuristic algorithms.
American Psychological Association (APA)
Lin, Min& Zhong, Yiwen& Lin, Juan& Lin, Xiaoyu. 2018. Discrete Bird Swarm Algorithm Based on Information Entropy Matrix for Traveling Salesman Problem. Mathematical Problems in Engineering،Vol. 2018, no. 2018, pp.1-15.
https://search.emarefa.net/detail/BIM-1209662
Modern Language Association (MLA)
Lin, Min…[et al.]. Discrete Bird Swarm Algorithm Based on Information Entropy Matrix for Traveling Salesman Problem. Mathematical Problems in Engineering No. 2018 (2018), pp.1-15.
https://search.emarefa.net/detail/BIM-1209662
American Medical Association (AMA)
Lin, Min& Zhong, Yiwen& Lin, Juan& Lin, Xiaoyu. Discrete Bird Swarm Algorithm Based on Information Entropy Matrix for Traveling Salesman Problem. Mathematical Problems in Engineering. 2018. Vol. 2018, no. 2018, pp.1-15.
https://search.emarefa.net/detail/BIM-1209662
Data Type
Journal Articles
Language
English
Notes
Includes bibliographical references
Record ID
BIM-1209662