Receive a 20% Discount on All Purchases Directly Through IGI Global's Online Bookstore

Enrique Mérida-Casermeiro (University of Málaga, Spain), Domingo López-Rodríguez (University of Málaga, Spain) and Juan M. Ortiz-de-Lazcano-Lobato (University of Málaga, Spain)

DOI: 10.4018/978-1-59904-849-9.ch163

Chapter Preview

TopIn Hopfield and Tank’s pioneering work (Hopfield & Tank, 1985), neural networks were applied for the first time to solve combinatorial optimization problems, concretely the well-known travelling salesman problem. They developed two types of networks, discrete and continuous, although the latter has been mostly chosen to solve optimization problems, adducing that it helps to escape more easily from local optima. Since then, the search for better neural algorithms, to face the diverse problems of combinatorial optimization (many of them belonging to the class of NPcomplete problems), has been the objective of researchers in this field.

This method of optimization consists of minimizing an energy function, whose parameters and constraints are obtained by means of identification with the objective function of the optimization problem. In this case, the energy function has the form:

whereIn the discrete version of Hopfield’s model, component *s _{i}* of the state vector

*•*Certain special mechanisms, maybe in form of constraints, should be contributed in order to get that, in the final state of the network, all the components of state vector

belong to {–1, 1} or {0,1}.*S**•*The traditional dynamics used in this model, implemented in a digital computer, does not guarantee the decrease of the energy function in every iteration, so it is not ensured that the final state is a minimum of the energy function (GalánMarín, 2000).

However, the biggest problem of this model (the discrete as well as the continuous one) is the possibility to converge to a non feasible state, or to a local (not global) minimum. Wilson and Pawley (1988) demonstrated, through massive simulations, that, for the travelling salesman problem of 10 cities, only 8% of the solutions were feasible, and most not good. Moreover, this proportion got worse when problem size was increased.

MaxCut Problem: Problem of finding a partition of the set of nodes of a weighted graph, such that the sum of the costs corresponding to edges, with end-points in different sets of the partition, is maximum.

2 Pages Graph Layout Problem: Problem of finding an ordering of the nodes of a graph on a straight line, and assigning, to each edge, a location in any of the two halfplanes induced by that line, such that the number of crossings between edges is minimum.

Travelling Salesman Problem: Problem of finding the shortest closed tour that visits a series of N cities. Each city must be visited exactly one time.

Multivalued Discrete Neural Model: A model of neural networks in which neuron outputs may take value in the set , instead of or .

Artificial Neural Network: Structure for distributed and parallel processing of information, formed by a series of units (which may possess a local memory and make local information processing operations), interconnected via one-way communication channels, called connections.

Energy Function: Objective function of the optimization problem solved by a neural model.

Computational Dynamics: Updating scheme of the neuron outputs in a neural model.

Search this Book:

Reset