Fusion of Neural Networks, Fuzzy Systems and Genetic Algorithms: Industrial Applications Fusion of Neural Networks, Fuzzy Systems and Genetic Algorithms: Industrial Applications
by Lakhmi C. Jain; N.M. Martin
CRC Press, CRC Press LLC
ISBN: 0849398045   Pub Date: 11/01/98
  

Previous Table of Contents Next


3. Neural Networks

Artificial neural networks (ANNs) are inspired by nature in the sense that they are composed of elements or units that perform in a manner that is analogous to neurons in the human brain. These units are richly interconnected through weighted connections: a signal is sent from one unit to another along a connection and is modulated by the associated weight (which stands for the strength or efficiency of the connection). Although superficially related to their biological counterpart, ANNs possess characteristics associated with human cognition. In particular, they can learn from experience and induce general concepts from specific examples; when presented with a set of inputs, they self-adjust to produce the desired response.

Neural networks were originally designed for tasks well adapted to human intelligence and where traditional computation has proven inadequate, such as speech understanding, artificial vision, and handwritten character recognition. Starting with the pioneering work of Hopfield and Tank [17], they have recently been applied to combinatorial optimization problems as well. For instance, applications of the Hopfield model [16], elastic net [7], and self-organizing map [19] for the TSP are well documented, although it is fair to say that the results are not yet competitive with those reported in the operations research community [18].

Although neural network models can handle spatial relationships among vertices to find good routes, they cannot easily handle side constraints, such as capacity constraints and time windows, that often break the geographic or geometric interpretation of the problem. Accordingly, the literature on the application of neural networks to vehicle routing problems is rather scant. Different variants of the self-organizing map were recently applied to the capacitated VRP [10, 11, 12, 22, 32]. The work of Ghaziri will be used in the following to illustrate how this model can be applied to an academic problem. Then, we discuss the application of a feedforward neural network model with backpropagation learning for a real-world dispatching application found in a courier service [33].

3.1 Self-Organizing Maps

Self-organizing maps are instances of the so-called competitive neural network models [19]. They are composed of a layer of input units fully connected to a layer of output units, the latter units being organized in a particular topology, such as a ring structure. These models “self-organize” (without any external supervision) through an iterative adjustment of their connection weights to find some regularity or structure in the input data. They are typically used to categorize or cluster data. In Figure 2, T11 and T21 denote the weights on the connections from the two input units I1 and I2 to output unit 1, and T1 = (T11, T21) is the weight vector associated with output unit 1.

Assuming an ordered set of n input vectors of dimension p and a self-organizing map with p input units and q output units on a ring, the algorithm for adjusting the connection weights can be summarized as follows.

Step 1. (Initialization). Set the connection weights to some initial values.
Step 2. (Competition). Consider the next input vector I. If all input vectors are done, start again from the first input vector. Compute the output value oj of each output unit as the weighted sum of its inputs, namely,

where Tij is the connection weight between input unit i and output unit j. The winning output unit j* is the unit with maximum output value.
Step 3. (Weight adjustment). Modify the connection weights of each output unit, as follows:

where Tj = (Tij)i=1,...,p is the weight vector of output unit j, and f is a function of j and j*.
Step 4. Repeat Step 2 and Step 3 until the weight vectors stabilize. At the end, each input vector is assigned to the output unit that maximizes the weighted sum in Step 2.


Figure 2  A self-organizing map with two input units and a ring of three output units

This algorithm deserves some additional comments. In Step 3, f is typically a decreasing function of the lateral distance between units j and j* on the ring (i.e., if there are k units on the ring between the two units, the lateral distance is k+1) and its range is the interval [0,1]. Thus, the weight vector of the winning unit j* and the weight vectors of units that are close to j* on the ring move towards the input vector I, but with decreasing intensity as the lateral distance to the winning unit increases. Typically, function f is modified as the learning algorithm unfolds to gradually reduce the magnitude of the weight adjustment. At the start, all units that are close to the winning unit on the ring “follow” that unit in order to move into a neighboring area. At the end, only the weight vector of the winning unit significantly moves toward the current input vector, to fix the assignment.

Self-organizing maps produce topological mappings from high-dimensional input spaces to low-dimensional output spaces. In the case of a ring structure, the p-dimensional input vectors are associated with the position of the winning unit on the ring. The mapping is such that two input vectors that are close in the input space are assigned to units that are close on the ring.


Previous Table of Contents Next

Copyright © CRC Press LLC