IEEE Transactions on Systems, Man, and Cybernetics - Part B: Cybernetics, ( ISI ), Volume (37), No (4), Year (2007-8) , Pages (754-770)

Title : A novel constructive-optimizer neural network for the traveling –salesman problem ( A Novel Constructive-Optimizer Neural Network for the Traveling Salesman Problem )

Authors: Mahdi Saadatmand , Morteza Khademi , Mohammad Reza Akbarzadeh Totonchi , Hamid Abrishami Moghaddam ,

Citation: BibTeX | EndNote

Abstract

In this paper, a novel constructive-optimizer neural network (CONN) is proposed for the traveling salesman problem (TSP). CONN uses a feedback structure similar to Hopfield-type neural networks and a competitive training algorithm similar to the Kohonen-type self-organizing maps (K-SOMs). Consequently, CONN is composed of a constructive part, which grows the tour and an optimizer part to optimize it. In the training algorithm, an initial tour is created first and introduced to CONN. Then, it is trained in the constructive phase for adding a number of cities to the tour. Next, the training algorithm switches to the optimizer phase for optimizing the current tour by displacing the tour cities. After convergence in this phase, the training algorithm switches to the constructive phase anew and is continued until all cities are added to the tour. Furthermore, we investigate a relationship between the number of TSP cities and the number of cities to be added in each constructive phase. CONN was tested on nine sets of benchmark TSPs from TSPLIB to demonstrate its performance and efficiency. It performed better than several typical Neural networks (NNs), including KNIES_TSP_Local, KNIES_TSP_Global, Budinich’s SOM, Co-Adaptive Net, and multivalued Hopfield network as wall as computationally comparable variants of the simulated annealing algorithm, in terms of both CPU time and accuracy. Furthermore, CONN converged considerably faster than expanding SOM and evolved integrated SOM and generated shorter tours compared to KNIES_DECOMPOSE. Although CONN is not yet comparable in terms of accuracy with some sophisticated computationally intensive algorithms, it converges significantly faster than they do. Generally speaking, CONN provides the best compromise between CPU time and accuracy among currently reported NNs for TSP.

Keywords

, Constructive-optimizer neural network (CONN), Hopfield-type neural networks (HNNs), Kohonen-type selforganizing maps (K-SOMs), traveling salesman problem (TSP).
برای دانلود از شناسه و رمز عبور پرتال پویا استفاده کنید.

@article{paperid:102388,
author = {Saadatmand, Mahdi and Khademi, Morteza and Akbarzadeh Totonchi, Mohammad Reza and Hamid Abrishami Moghaddam},
title = {A novel constructive-optimizer neural network for the traveling –salesman problem},
journal = {IEEE Transactions on Systems, Man, and Cybernetics - Part B: Cybernetics},
year = {2007},
volume = {37},
number = {4},
month = {August},
issn = {1083-4419},
pages = {754--770},
numpages = {16},
keywords = {Constructive-optimizer neural network (CONN); Hopfield-type neural networks (HNNs); Kohonen-type selforganizing maps (K-SOMs); traveling salesman problem (TSP).},
}

[Download]

%0 Journal Article
%T A novel constructive-optimizer neural network for the traveling –salesman problem
%A Saadatmand, Mahdi
%A Khademi, Morteza
%A Akbarzadeh Totonchi, Mohammad Reza
%A Hamid Abrishami Moghaddam
%J IEEE Transactions on Systems, Man, and Cybernetics - Part B: Cybernetics
%@ 1083-4419
%D 2007

[Download]