The simultaneous recurrent neural network for addressing the scaling problem in static optimization.

A trainable recurrent neural network, Simultaneous Recurrent Neural network, is proposed to address the scaling problem faced by neural network algorithms in static optimization. The proposed algorithm derives its computational power to address the scaling problem through its ability to "learn" compared to existing recurrent neural algorithms, which are not trainable. Recurrent backpropagation algorithm is employed to train the recurrent, relaxation-based neural network in order to associate fixed points of the network dynamics with locally optimal solutions of the static optimization problems. Performance of the algorithm is tested on the NP-hard Traveling Salesman Problem in the range of 100 to 600 cities. Simulation results indicate that the proposed algorithm is able to consistently locate high-quality solutions for all problem sizes tested. In other words, the proposed algorithm scales demonstrably well with the problem size with respect to quality of solutions and at the expense of increased computational cost for large problem sizes.     

Heuristic combinatorial optimization by simulated Darwinian evolution: a polynomial time algorithm for the Traveling Salesman Problem

A genetic algorithm simulating Darwinian evolution is proposed to yield near-optimal solutions to the Traveling Salesman Problem. Noting that Darwinian evolution is itself an optimization process, we propose a heuristic algorithm that incorporates the tenets of natural selection. The time complexity of this algorithm is equivalent to the fastest sorting scheme! Computer simulations indicate rapid convergence is maintained even with increasing problem complexity. This methodology can be adapted to tackle a host of other combinatorial problems.     

On problem solving with Hopfield neural networks

Hopfield and Tank have shown that neural networks can be used to solve certain computationally hard problems, in particular they studied the Traveling Salesman Problem (TSP). Based on network simulation results they conclude that analog VLSI neural nets can be promising in solving these problems. Recently, Wilson and Pawley presented the results of their simulations which contradict the original results and cast doubts on the usefulness of neural nets. In this paper we give the results of our simulations that clarify some of the discrepancies. We also investigate the scaling of TSP solutions found by neural nets as the size of the problem increases. Further, we consider the neural net solution of the Clustering Problem, also a computationally hard problem, and discuss the types of problems that appear to be well suited for a neural net approach.     

Optimization with neural networks: a recipe for improving convergence and solution quality

Artificial Neural Networks, particularly the Hopfield Network have been applied to the solution of a variety of tasks formulated as optimization problems. However, the network often converges to invalid solutions, which have been attributed to an improper choice of parameters and energy functions. In this letter, we propose a fundamental change of viewpoint. We assert that the problem is not due to the bad choice of parameters or the form of the energy function chosen. Instead, we show that the Hopfield Net essentially performs only one iteration of a Sequential Unconstrained Minimization Technique (SUMT). Thus, it is not surprising that unsatisfactory results are obtained. We present results on an SUMT-based formulation for the Travelling Salesman Problem, where we consistently obtained valid tours. We also show how shorter tours can be systematically obtained.     

Minimum energy configurations of the 2-dimensional HP-model of proteins by self-organizing networks.

We use self-organizing maps (SOM) as an efficient tool to find the minimum energy configurations of the 2-dimensional HP-models of proteins. The usage of the SOM for the protein folding problem is similar to that for the Traveling Salesman Problem. The lattice nodes represent the cities whereas the neurons in the network represent the amino acids moving towards the closest cities, subject to the HH interactions. The valid path that maximizes the HH contacts corresponds to the minimum energy configuration of the protein. We report promising results for the cases when the protein completely fills a lattice and discuss the current problems and possible extensions. In all the test sequences up to 36 amino acids, the algorithm was able to find the global minimum and its degeneracies.     

A study of the application of Kohonen-type neural networks to the Travelling Salesman Problem

It is observed that animals often have to resolve difficult tasks of optimization and that this process can be studied by applying the formal framework of neural networks to a simple problem such as the Travelling Salesman Problem. Existing work is reviewed with particular emphasis on recent studies using self-organizing networks. An algorithm is described in which general principles developed by Kohonen are applied to the Travelling Salesman Problem. Simulation results are given for problem sets of up to 10,000 cities. The routes generated are reported as being slightly longer than those produced by simulating annealing; compute time is lower and scales less than quadratically with problem size. It is suggested that the ability to perform optimization is an emergent computational property not just of the Kohonen model but of any mechanism capable of producing topology-preserving mappings, including mechanisms within the brain.     

An efficient harris hawk optimization algorithm for solving the travelling salesman problem

Cluster Computing - Travelling Salesman Problem (TSP) is an Np-Hard problem, for which various solutions have been offered so far. Using the Harris Hawk Optimization (HHO) algorithm, this paper...     

A neural network algorithm for the multiple traveling salesmen problem

We developed an efficient neural network algorithm for solving the Multiple Traveling Salesmen Problem (MTSP). A new transformation of the N-city M-salesmen MTSP to the standard Traveling Salesmen Problem (TSP) is introduced. The transformed problem is represented by an expanded version of Hopfield-Tank's neuromorphic city-position map with (N + M-1)-cities and a single fictitious salesmen. The dynamic model associated with the problem is based on the Basic Differential Multiplier Method (BDMM) [26] which evaluates Lagrange multipliers simultaneously with the problem's state variables. The algorithm was successfully tested on many problems with up to 30 cities and five salesmen. In all test cases, the algorithm always converged to valid solutions. The great advantage of this kind of algorithm is that it can provide solutions to complex decision making problems directly by solving a system of ordinary differential equations. No learning steps, logical if statements or adjusting of parameters are required during the computation. The algorithm can therefore be implemented in hardware to solve complex constraint satisfaction problems such as the MTSP at the speed of analog silicon VLSI devices or possibly future optical neural computers.     

Neural network modeling in optimisation of continuous fermentation processes

The capability of self-recurrent neural networks in dynamic modeling of continuous fermentation is investigated in this simulation study. In the past, feedforward neural networks have been successfully used as one-step-ahead predictors. However, in steady-state optimisation of continuous fermentations the neural network model has to be iterated to predict many time steps ahead into the future in order to get steady-state values of the variables involved in objective cost function, and this iteration may result in increasing errors. Therefore, as an alternative to classical feedforward neural network trained by using backpropagation method, self-recurrent multilayer neural net trained by backpropagation through time method was chosen in order to improve accuracy of long-term predictions. Prediction capabilities of the resulting neural network model is tested by implementing this into the Integrated System Optimisation and Parameter Estimation (ISOPE) optimisation algorithm. Maximisation of cellular productivity of the baker's yeast continuous fermentation was used as the goal of the proposed optimising control problem. The training and prediction results of proposed neural network and performances of resulting optimisation structure are demonstrated.     

Multi-Objective Ant Colony Optimization Based on the Physarum-Inspired Mathematical Model for Bi-Objective Traveling Salesman Problems

Bi-objective Traveling Salesman Problem (bTSP) is an important field in the operations research, its solutions can be widely applied in the real world. Many researches of Multi-objective Ant Colony Optimization (MOACOs) have been proposed to solve bTSPs. However, most of MOACOs suffer premature convergence. This paper proposes an optimization strategy for MOACOs by optimizing the initialization of pheromone matrix with the prior knowledge of Physarum-inspired Mathematical Model (PMM). PMM can find the shortest route between two nodes based on the positive feedback mechanism. The optimized algorithms, named as iPM-MOACOs, can enhance the pheromone in the short paths and promote the search ability of ants. A series of experiments are conducted and experimental results show that the proposed strategy can achieve a better compromise solution than the original MOACOs for solving bTSPs.     

演化计算的应用研究

介绍了演化计算的基本思想、特点及主要分支。在统一的枢架下给出了演化算法的设计方法和基本结构,并给出了演化计算在旅行商问题中的应用。最后讨论了演化计算的发展前景。     

Neural networks and linear programming for the satisfiability problem.

First a Linear Programming formulation is considered for the satisfiability problem, in particular for the satisfaction of a Conjunctive Normal Form in the Propositional Calculus and the Simplex algorithm for solving the optimization problem. The use of Recurrent Neural Networks is then described for choosing the best pivot positions and greatly improving the algorithm performance. The result of hard cases testing is reported and shows that the technique can be useful even if it requires a huge amount of size for the constraint array and Neural Network Data Input.     

Recurring discharge patterns in multiple spike trains

Neural networks are parallel processing structures that provide the capability to perform various pattern recognition tasks. A network is typically trained over a set of exemplars by adjusting the weights of the interconnections using a back propagation algorithm. This gradient search converges to locally optimal solutions which may be far removed from the global optimum. In this paper, evolutionary programming is analyzed as a technique for training a general neural network. This approach can yield faster, more efficient yet robust training procedures that accommodate arbitrary interconnections and neurons possessing additional processing capabilities.     

Artificial neural network based soft estimator for estimation of transducer static nonlinearity

In this work, the development of an Artificial Neural Network (ANN) based soft estimator is reported for the estimation of static-nonlinearity associated with the transducers. Under the realm of ANN based transducer modeling, only two neural models have been suggested to estimate the static-nonlinearity associated with the transducers with quite successful results. The first existing model is based on the concept of a functional link artificial neural network (FLANN) trained with mu-LMS (Least Mean Squares) learning algorithm. The second one is based on the architecture of a single layer linear ANN trained with alpha-LMS learning algorithm. However, both these models suffer from the problem of slow convergence (learning). In order to circumvent this problem, it is proposed to synthesize the direct model of transducers using the concept of a Polynomial-ANN (polynomial artificial neural network) trained with Levenberg-Marquardt (LM) learning algorithm. The proposed Polynomial-ANN oriented transducer model is implemented based on the topology of a single-layer feed-forward back-propagation-ANN. The proposed neural modeling technique provided an extremely fast convergence speed with increased accuracy for the estimation of transducer static nonlinearity. The results of convergence are very stimulating with the LM learning algorithm.     

Using traveling salesman problem algorithms for evolutionary tree construction

MOTIVATION: The construction of evolutionary trees is one of the major problems in computational biology, mainly due to its complexity. RESULTS: We present a new tree construction method that constructs a tree with minimum score for a given set of sequences, where the score is the amount of evolution measured in PAM distances. To do this, the problem of tree construction is reduced to the Traveling Salesman Problem (TSP). The input for the TSP algorithm are the pairwise distances of the sequences and the output is a circular tour through the optimal, unknown tree plus the minimum score of the tree. The circular order and the score can be used to construct the topology of the optimal tree. Our method can be used for any scoring function that correlates to the amount of changes along the branches of an evolutionary tree, for instance it could also be used for parsimony scores, but it cannot be used for least squares fit of distances. A TSP solution reduces the space of all possible trees to 2n. Using this order, we can guarantee that we reconstruct a correct evolutionary tree if the absolute value of the error for each distance measurement is smaller than f2.gif" BORDER="0">, where f3.gif" BORDER="0">is the length of the shortest edge in the tree. For data sets with large errors, a dynamic programming approach is used to reconstruct the tree. Finally simulations and experiments with real data are shown.     

Cascaded deep network systems with linked ensemble components for underwater fish detection in the wild

We propose a fish detection system based on deep network architectures to robustly detect and count fish objects under a variety of benthic background and illumination conditions. The algorithm consists of an ensemble of Region-based Convolutional Neural Networks that are linked in a cascade structure by Long Short-Term Memory networks. The proposed network is efficiently trained as all components are jointly trained by backpropagation. We train and test our system for a dataset of 18 videos taken in the wild. In our dataset, there are around 20 to 100 fish objects per frame with many fish objects having small pixel areas (less than 900 square pixels). From a series of experiments and ablation tests, the proposed system preserves detection accuracy despite multi-scale distortions, cropping and varying background environments. We present analysis that shows how object localization accuracy is increased by an automatic correction mechanism in the deep network's cascaded ensemble structure. The correction mechanism rectifies any errors in the predictions as information progresses through the network cascade. Our findings in this experiment regarding ensemble system architectures can be generalized to other object detection applications.     

Evaluation measures of multiple sequence alignments.

Multiple sequence alignments (MSAs) are frequently used in the study of families of protein sequences or DNA/RNA sequences. They are a fundamental tool for the understanding of the structure, functionality and, ultimately, the evolution of proteins. A new algorithm, the Circular Sum (CS) method, is presented for formally evaluating the quality of an MSA. It is based on the use of a solution to the Traveling Salesman Problem, which identifies a circular tour through an evolutionary tree connecting the sequences in a protein family. With this approach, the calculation of an evolutionary tree and the errors that it would introduce can be avoided altogether. The algorithm gives an upper bound, the best score that can possibly be achieved by any MSA for a given set of protein sequences. Alternatively, if presented with a specific MSA, the algorithm provides a formal score for the MSA, which serves as an absolute measure of the quality of the MSA. The CS measure yields a direct connection between an MSA and the associated evolutionary tree. The measure can be used as a tool for evaluating different methods for producing MSAs. A brief example of the last application is provided. Because it weights all evolutionary events on a tree identically, but does not require the reconstruction of a tree, the CS algorithm has advantages over the frequently used sum-of-pairs measures for scoring MSAs, which weight some evolutionary events more strongly than others. Compared to other weighted sum-of-pairs measures, it has the advantage that no evolutionary tree must be constructed, because we can find a circular tour without knowing the tree.     

A Computationally Inexpensive Optimal Guidance via Radial-Basis-Function Neural Network for Autonomous Soft Landing on Asteroids

Optimal guidance is essential for the soft landing task. However, due to its high computational complexities, it is hardly applied to the autonomous guidance. In this paper, a computationally inexpensive optimal guidance algorithm based on the radial basis function neural network (RBFNN) is proposed. The optimization problem of the trajectory for soft landing on asteroids is formulated and transformed into a two-point boundary value problem (TPBVP). Combining the database of initial states with the relative initial co-states, an RBFNN is trained offline. The optimal trajectory of the soft landing is determined rapidly by applying the trained network in the online guidance. The Monte Carlo simulations of soft landing on the Eros433 are performed to demonstrate the effectiveness of the proposed guidance algorithm.     

Recurrent neural networks of integrate-and-fire cells simulating short-term memory and wrist movement tasks derived from continuous dynamic networks

Dynamic recurrent neural networks composed of units with continuous activation functions provide a powerful tool for simulating a wide range of behaviors, since the requisite interconnections can be readily derived by gradient descent methods. However, it is not clear whether more realistic integrate-and-fire cells with comparable connection weights would perform the same functions. We therefore investigated methods to convert dynamic recurrent neural networks of continuous units into networks with integrate-and-fire cells. The transforms were tested on two recurrent networks derived by backpropagation. The first simulates a short-term memory task with units that mimic neural activity observed in cortex of monkeys performing instructed delay tasks. The network utilizes recurrent connections to generate sustained activity that codes the remembered value of a transient cue. The second network simulates patterns of neural activity observed in monkeys performing a step-tracking task with flexion/extension wrist movements. This more complicated network provides a working model of the interactions between multiple spinal and supraspinal centers controlling motoneurons. Our conversion algorithm replaced each continuous unit with multiple integrate-and-fire cells that interact through delayed "synaptic potentials". Successful transformation depends on obtaining an appropriate fit between the activation function of the continuous units and the input-output relation of the spiking cells. This fit can be achieved by adapting the parameters of the synaptic potentials to replicate the input-output behavior of a standard sigmoidal activation function (shown for the short-term memory network). Alternatively, a customized activation function can be derived from the input-output relation of the spiking cells for a chosen set of parameters (demonstrated for the wrist flexion/extension network). In both cases the resulting networks of spiking cells exhibited activity that replicated the activity of corresponding continuous units. This confirms that the network solutions obtained through backpropagation apply to spiking networks and provides a useful method for deriving recurrent spiking networks performing a wide range of functions.     

An efficient approach to the travelling salesman problem using self-organizing maps

This paper presents an approach to the well-known Travelling Salesman Problem (TSP) using Self-Organizing Maps (SOM). The SOM algorithm has interesting topological information about its neurons configuration on cartesian space, which can be used to solve optimization problems. Aspects of initialization, parameters adaptation, and complexity analysis of the proposed SOM based algorithm are discussed. The results show an average deviation of 3.7% from the optimal tour length for a set of 12 TSP instances.