Abstract
Since McCulloch and Pitts’ seminal work (McCulloch & Pitts, 1943), several models of discrete neural networks have been proposed, many of them presenting the ability of assigning a discrete value (other than unipolar or bipolar) to the output of a single neuron. These models have focused on a wide variety of applications. One of the most important models was developed by J. Hopfield in (Hopfield, 1982), which has been successfully applied in fields such as pattern and image recognition and reconstruction (Sun et al., 1995), design of analogdigital circuits (Tank & Hopfield, 1986), and, above all, in combinatorial optimization (Hopfield & Tank, 1985) (Takefuji, 1992) (Takefuji & Wang, 1996), among others. The purpose of this work is to review some applications of multivalued neural models to combinatorial optimization problems, focusing specifically on the neural model MREM, since it includes many of the multivalued models in the specialized literature.
TopBackground
In 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:
where
N is the number of neurons of the network,
wi,j is the synaptic weight between neurons
j and
i, and θ
i is the threshold or bias of the neuron
i.
In the discrete version of Hopfield’s model, component si of the state vector S = (s1,...,sN) can take values in 
(constituting the bipolar model) or in 
(unipolar model). In the continuous version, 
or 
. This continuous version, although it has been traditionally the most used for optimization problems, presents certain inconveniences:
- •
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 S belong to {–1, 1} or {0,1}.
- •
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.
Key Terms in this Chapter
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.