Файл: Embedded Robotics (Thomas Braunl, 2 ed, 2006).pdf

Backpropagation

'win1,1 = diffhid 1 · o(nin 1)

= 0.077 · 1.0 = 0.077

'win2,1 = diffhid 1 · o(nin 2)

= 0.077 · 0.5 = 0.039

and so on for the remaining weights. The first two updated weights will therefore be:

w´in1,1 = win1,1 + 'win1,1 = 0.2 + 0.077 = 0.28 w´in2,1 = win2,1 + 'win2,1 = 0.3 + 0.039 = 0.34

The backpropagation procedure iterates until a certain termination criterion has been fulfilled. This could be a fixed number of iterations over all training patterns, or until sufficient convergence has been achieved, for example if the total output error over all training patterns falls below a certain threshold.

Bias neurons Program 19.2 demonstrates the implementation of the backpropagation process. Note that in order for backpropagation to work, we need one additional input neuron and one additional hidden neuron, called “bias neurons”. The activation levels of these two neurons are always fixed to 1. The weights of the connections to the bias neurons are required for the backpropagation procedure to converge (see Figure 19.7).

1

1

Figure 19.7: Bias neurons and connections for backpropagation

287

19 Neural Networks

19.4 Neural Network Example

Figure 19.8: Seven-segment digit representation

Figure 19.9 shows the decrease of total error values by applying the backpropagation procedure on the complete input data set for some 700 iterations. Eventually the goal of an error value below 0.1 is reached and the algorithm terminates. The weights stored in the neural net are now ready to take on previously unseen real data. In this example the trained network could e.g. be tested against 7-segment inputs with a single defective segment (always on or always off).

Figure 19.9: Error reduction for 7-segment example

288

19 Neural Networks

19.6 References

GURNEY, K. Neural Nets, UCL Press, London, 2002

KUBE, C., ZHANG, H., WANG, X. Controlling Collective Tasks with an ALN, IEEE/RSJ IROS, 1993, pp. 289-293 (5)

MINSKY, M., PAPERT, S. Perceptrons, MIT Press, Cambridge MA, 1969

ROSENBLATT, F. Principles of Neurodynamics. Spartan Books, Washington DC, 1962

RUMELHART, D., MCCLELLAND, J. (Eds.) Parallel Distributed Processing, 2 vols., MIT Press, Cambridge MA, 1986

SUTTON, R., BARTO, A. Reinforcement Learning: An Introduction, MIT Press, Cambridge MA, 1998

VERSHURE, P., WRAY, J., SPRONS, O., TONONI, G., EDELMAN, G. Multilevel

Analysis of Classical Conditioning in a Behaving Real World Artifact, Robotics and Autonomous Systems, vol. 16, 1995, pp. 247-265 (19)

ZAKNICH, A. Neural Networks for Intelligent Signal Processing, World Scientific, Singapore, 2003

290

GENETIC ALGORITHMS 20

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. .. .. .. . Evolutionary algorithms are a family of search and optimization tech-

niques that make use of principles from Darwin’s theory of evolution [Darwin 1859] to progress toward a solution. Genetic algorithms (GA) are a prominent part of this larger overall group. They operate by iteratively

evolving a solution from a history of potential solutions, which are manipulated by a number of biologically inspired operations. Although only an approximation to real biological evolutionary processes, they have been proven to provide a powerful and robust means of solving problems.

The utility of genetic algorithms is their ability to be applied to problems without a deterministic algorithmic solution. Certain satisfiability problems in robotic control fall into this category. For example, there is no known algorithm to deterministically develop an optimal walking gait for a particular robot. An approach to designing a gait using genetic algorithms is to evolve a set of parameters controlling a gait generator. The parameters completely control the type of gait that is produced by the generator. We can assume there exists a set of parameters that will produce a suitable walk for the robot and environment – the problem is to find such a set. Although we do not have a way to obtain these algorithmically, we can use a genetic algorithm in a simulated environment to incrementally test and evolve populations of parameters to produce a suitable gait.

It must be emphasized that the effectiveness of using a genetic algorithm to find a solution is dependent on the problem domain, the existence of an optimal solution to the problem at hand, and a suitable fitness function. Applying genetic algorithms to problems that may be solved algorithmically is decidedly inefficient. They are best used for solving tasks that are difficult to solve, such as NP-hard problems. NP-hard problems are characterized by the difficulty of finding a solution due to a large solution search space, but being easy to verify once a candidate solution has been obtained.

For further reading see [Goldberg 1989] and [Langton 1995].

291291

20 Genetic Algorithms

20.1 Genetic Algorithm Principles

Figure 20.1: Terminology

GA execution The basic operation of a genetic algorithm can be summarized as follows:

1.Randomly initialize a population of chromosomes.

2.While the terminating criteria have not been satisfied:

a.Evaluate the fitness of each chromosome:

i.Construct the phenotype (e.g. simulated robot) corresponding to the encoded genotype (chromosome).

ii.Evaluate the phenotype (e.g. measure the simulated robot’s walking abilities), in order to determine its fitness.

b.Remove chromosomes with low fitness.

c.Generate new chromosomes, using certain selection schemes and genetic operators.

The algorithm can start with either a set of random chromosomes, or ones that represent already approximate solutions to the given problem. The gene pool is evolved from generation to generation by a set of modifying operators and a selection scheme that depends on the fitness of each chromosome. The

292