Search

In this paper, we introduce the concept of fine-tuned learning which relies on the notion of data approximation followed by sequential data refinement. We seek to determine whether fine-tuned learning is a viable approach to use when trying to solve combinatorial optimization problems. In particular, we conduct an extensive computational experiment to study the performance of fine-tuned-learning-based heuristics for the traveling salesman problem (TSP). We provide important insight that reveals how fine-tuned learning works and why it works well, and conclude that it is a meritorious concept that deserves serious consideration by researchers solving difficult problems.

Efficient interprocessor duplicate pruning methods were developed. The methods were applied in parallel A* algorithms to obtain high speedup over sequential A* graph search. It was found that for graphical search spaces, duplicate pruning is essential for a good performance. A graph formulation of the search space was superior to a tree formulation since the formulation enables the detection and pruning of duplicates.

A parallel simulated annealing algorithm based on E.E. Witte, R.D. Chamberlain and M.A. Franklin's speculative computation approach is introduced. Unlike the original procedure, however, it has minimal communications traffic due to its problem independence. Its applicability and efficiency is illustrated in two examples, namely, the traveling salesman problem and a task scheduling problem.

How can a knight be moved on a chessboard so that the knight visits each square once and only once and goes back to the starting square? The earliest serious attempt to find a knight's tour on the chessboard was made by L. Euler in 1759. In this correspondence, a parallel algorithm based on the hysteresis McCulloch-Pitts neurons is proposed to solve the knight's tour problem. The relation between the traveling salesman problem and the knight's tour problem is also discussed. A large number of simulation runs were performed to investigate the behavior of the hysteresis McCulloch-Pitts neural model. The purpose of this correspondence is to present a case study - how to successfully represent the combinatorial optimization problems by means of neural network.

This paper describes a hybrid algorithm that combines an adaptive-type neural network algorithm and a nondeterministic iterative algorithm to solve the Euclidean traveling salesman problem (E-TSP). It begins with a brief introduction to the TSP and the E-TSP. Then, it presents the proposed algorithm with its two major components: the convex-elastic net (CEN) algorithm and the nondeterministic iterative improvement (NII) algorithm. These two algorithms are combined into the efficient convex-elastic net (ECEN) algorithm. The CEN algorithm integrates the convex-Hull property and elastic net algorithm to generate an initial tour for the E-TSP. The Nil algorithm uses two rearrangement operators to improve the initial tour given by the CEN algorithm. The paper presents simulation results for two instances of E-TSP: randomly generated tours and tours for well-known problems in the literature. Experimental results are given to show that the proposed algorithm can find the nearly optimal solution for the E-TSP that outperform many similar algorithms reported in the literature. The paper concludes with the advantages of the new algorithm and possible extensions. Index Terms - Neural network, optimization problems, traveling salesman problem (TSP).

In this paper, a distinction is drawn between research which assesses the suitability of the Hopfield network for solving the traveling salesman problem (TSP) and research which attempts to determine the effectiveness of the Hopfield network as an optimization technique. It is argued that the TSP is generally misused as a benchmark for the latter goal, with the existence of an alternative linear formulation giving rise to unreasonable comparisons.

It is well known that the Hopfield Model (HM) for neural networks to solve the Traveling Salesman Problem (TSP) suffers from three major drawbacks. 1) It can converge on nonoptimal locally minimum solutions. 2) It can converge on infeasible solutions. 3) Results are very sensitive to the careful tuning of its parameters. A number of methods have been proposed to overcome a) well. In contrast, work on b) and c) has not been sufficient; techniques have not been generalized to more general optimization problems. Thus this paper mathematically resolves b) and c) to such an extent that the resolution can be applied to solving with some general network continuous optimization problems including the Hopfield version of the TSP. It first constructs an Extended HM (E-HM) that overcomes both b) and c). Fundamental techniques of the E-HM lie in the addition of a synapse dynamical system cooperated with the current HM unit dynamical system. It is this synapse dynamical system that makes the TSP constraint hold at any final states for whatever choices of the HM parameters and an initial state. The paper then generalizes the E-HM further to a network that can solve a class of continuous optimization problems with a constraint equation where both of the objective function and the constraint function are nonnegative and continuously differentiable. Index Terms - Dynamical systems, feasible solutions, Hopfield model, optimization, traveling salesman problem.