The co-adaptive neural network approach to the Euclidean Travelling Salesman Problem

In this paper we consider the Euclidean Travelling Salesman Problem (ETSP). This is the problem of finding the shortest tour around a number of cities where the cities correspond to points in the Euclidean plane and the distances between cities are given by the usual Euclidean distance metric. We present a review of the literature with respect to neural network (NN) approaches for the ETSP, and the computational results that have been reported. Based upon this review we highlight two areas that are, in our judgement, currently neglected/lacking in the literature. These are: failure to make significant use of publicly available ETSP test problems in computational work, failure to address co-operation between neurons. Drawing upon our literature survey this paper presents a new Self-Organising NN approach, called the Co-Adaptive Net, which involves not just unsupervised learning to train neurons, but also allows neurons to co-operate and compete amongst themselves depending on their situation. Our Co-Adaptive Net algorithm also includes a number of algorithmic mechanisms that, based upon our literature review, we consider to have contributed to the computational success of previous algorithms. Results for 91 publicly available standard ETSP's are presented in this paper. The largest of these problems involves 85,900 cities. This paper presents: the most extensive computational evaluation of any NN approach on publicly available ETSP test problems that has been made to date in the literature, a NN approach that performs better, with respect to solution quality and/or computation time, than other NN approaches given previously in the literature. Drawing upon computational results produced as a result of the DIMACS TSP Challenge, we highlight the fact that none of the current NN approaches for the ETSP can compete with state of the art Operations Research heuristics. We discuss why we consider continuing to study and develop NN approaches for the ETSP to be of value.

A semi-localized elastic net for surface reconstruction of objects from multislice images

The traveling salesman problem (TSP) is a prototypical problem of combinatorial optimization and, as such, it has received considerable attention from neural-network researchers seeking quick, heuristic solutions. An early stage in many computer vision tasks is the extraction of object shape from an image consisting of noisy candidate edge points. Since the desired shape will often be a closed contour, this problem can be viewed as a version of the TSP in which we wish to link only a subset of the points/cities (i.e. the "noisefree" ones). None of the extant neural techniques for solving the TSP can deal directly with this case. In this paper, we present a simple but effective modification to the (analog) elastic net of Durbin and Willshaw which shifts emphasis from global to local behavior during convergence, so allowing the net to ignore some image points. Unlike the original elastic net, this semi-localized version is shown to tolerate considerable amounts of noise. As an example practical application, we describe the extraction of "pseudo-3D" human lung outlines from multiple preprocessed magnetic resonance images of the torso. An effectiveness measure (ideally zero) quantifies the difference between the extracted shape and some idealized shape exemplar. Our method produces average effectiveness scores of 0.06 for lung shapes extracted from initial semi-automatic segmentations which define the noisefree case. This deteriorates to 0.1 when extraction is from a noisy edge-point image obtained fully-automatically using a feedforward neural network.