Evolution Strategy in Action
10 ESDemonstrations
presented on the
International Conference On
Evolutionary Computation
The Third Parallel Problem
Solving From Nature (PPSN III)
Jerusalem, Israel
October 914, 1994
Michael Herdy
Giannino Patone
Technical Report TR9405
October 1994
Technische Universität Berlin email: herdy@fb10.tuberlin.d400.de
Bionik und Evolutionstechnik fon: +493031472663
Ackerstr.7176, Sekr.Ack1 fax: +493031472658
D13355 Berlin
Germany
Introduction
The presented demonstration programs partly have a long history and they have been realized several times in our institute on different computer platforms. In the present form the programs have mainly been realized by MICHAEL HERDY and GIANNINO PATONE. The evolution of a plane frame bases on a program of HOLGER EGGERT and the evolution of RUBIK's Cube bases on a program of MARCUS THORMANN; they both realized their thesis for diploma in our institute.
We use the demonstration programs as teaching aid in our lectures in evolution strategy and bionics and as demonstration tool for the power of Evolution Strategy.
Some of the actual presented demonstration programs will be available from the end of October on our ftpserver. As well the other demonstration programs will be available one after the other. Any one time it will be announced in the GADigest.
The address of our ftpserver is
FTPBIONIK.FB10.TUBERLIN.DE
Contents
 Evolution of a Mixture of Colors 
the Cherry Brandy Experiment 15
 Evolution of Color and Shape 16
Evolution of a Prism Lens
By means of Evolution Strategy the shape of an initially cuboid lighttransmissive body is to be changed in such a way, that parallel falling rays of light are refracted into a single point P on a projection surface.
The object
The light transmissive body consists of a pile of n prism which form a polygonal lens. Therefore the thickness of this lens can be altered at (n+1) locations. The refraction numbers of the prism and the surrounding medium are r2 and r1 respective. The proportion r2/r1 of the refraction numbers is adjustable between 0.2 and 5.0. If it is smaller than one, the lens may be formed by an inclusion of air in a body of glass.
The quality function
Only the rays of light falling on the center of the prism are taken into account, the others are left out of consideration. Therefore the 'quality' of a lens results from the sum of the squared distances di between the target point P and the respective actual point where the rays strike the projection surface.
min
Further optimization goals
In addition to the goal, that the rays of light are being concentrated in a single point on the projection surface it may be demanded in the demonstration program, that the narrowest part of the lens is being adjusted as narrow as possible but not narrower than a given minimal value dmin. The quality function changes to
min
Examples:
The following two examples show the start, a middle situation
and the finish of an optimization with a (1, 30)ES and different proportions
of the refraction numbers.
Evolution of a convex lens
Proportion of the refraction numbers: r1/r2=1.6
Evolution of a concave lens
Proportion of the refraction numbers: r1/r2=0.4
Evolution of a System of Pipes ('Bloodnet')
= diameter of the ith pipe
= quantity of liquid per time
There are n final nodes in a system of pipes (bloodnet) to be supplied with a definite amount of liquid per time. The topology of the supply system, the position of the main node into which the whole liquid is feeded and the position of the final nodes are given and fixed. The diameter grading of the pipes is being calculated in accordance with laws of hydrodynamics. It is asked for the optimal position of the branching nodes under the condition, that the differences in pressure in the system of pipes and the total volume of the pipes are to become minimal and the pressure in all final nodes is to be equal.
The object
The quality function
= constant factors
= pressure at the ith final node
= mean pressure at the final nodes
= total volume of the system of pipes
Example
G=1 Q=134128 G=100 Q=124882
G=200 Q=118686 G=400 Q=111891
G=600 Q=107647 G=800 Q=104420
G=1000 Q=103751 G=2000 Q=103338Polynomial Approximation with the Evolution Strategy
To a set of datapoints in the twodimensional plane a polynomial is to be fitted in such a way, that all points are described by the polynomial with minimal error.
The object
The kind of polynomial (rational, fractional rational,
trigonometric) and its degree n can be chosen by the user.
Rational polynomial: Fractional rational polynomial:
Trigonometric polynomial:
The quality function
Two kinds of quality functions can be chosen:
Discrete Least Square Approximation:
min
Tschebyscheff Approximation:
min
Example
With a (1, 10)ES a fractional rational polynomial of degree six has been fitted to a noisy dataset.
Evolution of a Brachystochrone
This classical problem was posed by Johann Bernoulli to his professional colleagues in 1696. He asked for the track between the two points A and B, on which a movable point P slides frictionless in shortest time by means of his own gravity.
The object
The track is realized by a polygon. The location of the
two points A (Start) and B (Finish) depends on the difference in height
and width of the track chosen by the operator, they are fixed during the
optimization. They may be changed between 0 and 5000 mm. As a default width
and height of the track are set equal to 5000 mm. Between A and B
a number of n pillars is given. This number may be changed between 1 and
50. The position of these pillars is changed to optimal values during the
optimization. According to the chose type of pillar (equidistant x, equidistant
y, variable x and y) there are n or 2n variables.
The quality function
min
= time for sliding from one end of the ith part of the polygon to the other
Examples
The following examples demonstrate the effect of the three
different kinds of pillars. The height and width of the track is set to
5000 mm. The number of pillars is set to 10. All three examples are
performed with a (1, 10)ES.
Initial track for all three examples:
Generation: 0
Quality: 1.427843 s
Solutions of the three examples with the three different kinds of pillars (equidistant x, equidistant y, variable x and y):
Equidistant x, variable y  Variable x, Equidistant y  Variable x and y 
Generation: 300 Generation: 300 Generation: 6500
Quality: 1.310729 s Quality: 1.304830 s
Quality: 1.304057 s
Example of a run with a width of 5000 and a height of
1500. The kind of pillars is set to equivalent x and the number of pillars
to n=20. A (1, 10)ES has been used.
Generation: 0 Generation: 100 Generation: 200
Quality: 1.924501 s Quality: 1.611015 s
Quality: 1.427879 s
Generation: 300 Generation: 500 Generation: 900
Quality: 1.357969 s Quality: 1.338753 s
Quality: 1.335358 s
Evolution of a Plane Frame
The nodes of a plane frame with given topology and given static forces are to be positioned in such a way that the total weight of the frame becomes minimal.
The object
The frame consists of bars of circular cross section with full profile. The coordinates of the nodes, where the bars are jointed are the variables of the object. These nodes are positioned by means of the evolution strategy.
The quality function
To get the quality value of an offspring i.e. the weight of an offspring frame, some calculations are to be done before. At first the axial loads of the bars have to be determined. For this standard methods from technical mechanics exist. With the axial loads and the maximum stresses the cross sections of the bars are determined in such a way, that the maximum stress in all bars exists. Finally the weight of the frame results from the total volume of all bars multiplied by the specific weight of the used material.
Example
Optimization of a plane frame with a (6/6, 60)ES.
1. Parent (53248 kg) 5. Generation (27340 kg)
10. Generation (23483 kg) 15. Generation (20837 kg)
20. Generation (19663 kg) 150. Generation (17777 kg)
Evolution of Rubik's Cube
Rubik's Cube is a threedimensional logic game. The cube consists of 26 partialcubes, the 6 middlecubes, 12 bordercubes and 8 cornercubes. The state of the cube can be changed by turning any of the six faces. The visible faces of these partialcubes are labelled with little color tiles. It is the goal to alter the cube from a random initial state to such a configuration where all partialcubes are at their home position so that only monochromatic surfaces on the cube exist.
The object
The middlecubes cannot change their position relative to each other. With each turn of a cube face 4 cornercubes and 4 bordercubes change their position on the cube.
The quality function
Because the middle cubes are fixed relative to each other the goal color of each of the 6 surfaces of the cube is determined by the color of the middlecube.
The quality function Q=Q1+Q2+Q3 for the evaluation of the state of the cube consists of three parts combined by addition. With Q1, differences from the color of the middlecube are penalized for every surface of the cube. For every wrong color tile, Q1 is increased by 1. Q2 and Q3 penalize wrong positioned border or cornercubes. A bordercube is correctly positioned if it contains the two colors of the middlecubes it touches. For every wrongly positioned bordercube, Q3 is increased by 4. Similarly, a cornercube is correctly positioned if it contains the three colors of the middlecubes it touches. For every wrongly positioned cornercube, Q3 is increased by 6. In the case of correctly positioned but still wrongly turned border or cornercubes, Q2 or Q3 are not increased because these turnings are sufficiently taken into account by Q1. Each of the three quality parts Q1, Q2 and Q3 can take on a maximum value of 48 which means that Q can take on a maximum value of Q = 144.
The Mutation operators
For the variation of the cube, specific mutation operators were implemented each of them changing the quality only a little. It is, for example, not useful to take the turning of a cubeslice through 90° as a smallest variation operator because the quality changes in big steps and not continuously in small steps. The implemented mutation operators are twoborderturn, twocornerturn, threeborderswap, twoborder/twocornerswap, threecornerswap, doubleborderswap and doublecornerswap. The operators threeborderswap, threecornerswap and twoborder/twocornerswap are realized in two different directions so that there are 10 mutation operators available.
Examples
For a cube in a starting position with quality Q=118 with
a (1,50)ES the optimum was found in a mean of 38.7 generations. A mean
of only 1935 from more than 43 trillion possible cube positions were calculated.
Start Finish

Generation: 0 Generation: 21
Quality: 105 (43, 8, 5) Quality: 0 (0, 0, 0)
Evolution of Rubik's Cube: The "Ancestral portrait gallery"
The following pictures show the development of the cube
for different generations. The numbers under the heading 'quality' give
the total quality and in brackets the number of wrong color tiles, wrongly
positioned bordercubes and wrongly positioned cornercubes are given.
Generation: 0 Generation: 5
Quality: 105 (43,8,5) Quality: 54 (30, 6,
0)
Generation: 10 Generation: 15
Quality: 35 (15, 5, 0) Quality: 35 (15,
5, 0)
Generation: 20 Generation: 21
Quality: 4 (4, 0, 0) Quality: 0 (0, 0, 0)
Evolution of a True Magic Square
An example from number theory represents the discovery of a true magic square. On a square grid with n x n fields the numbers from 1 to n2 are being distributed at random. It is the aim to find such an arrangement where all sums of columns, all sums of rows and both sums of the diagonals yield the same value S, the magic sum. This arrangement is called a true magic square.
The quality function
The value S, the so called magic sum, results from S=0.5.n.(n2+1). For a magic square with n columns, n rows and 2 diagonals the quality of an offspring is calculated by adding the squared differences between the n sums of columns and S, the n sums of rows and S and the 2 diagonals and S.
The mutation operator
For the variation, one field is selected at random. Afterwards this field is interchanged with one whose numerical value is only a little different. In this way the smallest changes of quality are obtained. In this example an adaptive stepsize is definable as the maximum difference of the both numbers being interchanged.
Example
The example shows an 8 x 8 magic square developed with
the evolution strategy. All sums of columns, all sums of rows and both
sums of diagonals yield the same value S=260.. This magic square was found
with a (1,30)ES in 447 generations.
The Travelling Salesman Problem
A salesman has to visit n towns one after the other on a tour with minimum length. Every town may be visited only once and at the end of the tour the man has to return to the first town of his tour. This example deals only with symmetric TSP, i.e. the distance between two towns is independent of the direction.
Mutation and recombination operators
It is necessary to ensure by implementation of specific
mutation operators that the strong causality is valid, i.e. that small
changes of the tour lead to small changes of the costs. Four different
mutation operators are implemented: Inversion of a segment of the tour,
insertion of a town at another point of the tour, reciprocal exchange of
two towns and displacement of a segment of the tour. The following table
shows examples for the effect of the different operators on a given parent
tour. The order of the numbers represents the order in which the towns
are visited by the salesman. After visiting the last town (no.12) he returns
to the first town (no.1) again.
1 2 3 4 5 6 7 8 9 10 11 12  ParentsTour 
1 5 4 3 2 6 7 8 9 10 11 12  Inversion of the tour segment 2345 
1 3 4 5 2 6 7 8 9 10 11 12  Insertion of town no.2 between no.5 and no.6 
1 6 7 2 3 4 5 8 9 10 11 12  Displacement of the tour segment 2345 
1 5 3 4 2 6 7 8 9 10 11 12  Reciprocal Exchange of towns no.2 and no. 5 
The mutation operators for the TSP
If these operators are applied to any part of the tour, then strong causality is probably not fulfilled. Distances of towns from each other must be considered when applying the mutation operators. This means that, for example in the application of the inversion operator, only tour segments between adjacent towns may be inverted. In addition to the mutation operators a specific recombination operator was implemented in the TSP. This one is different to the recombination operators usually used in the Evolutionsstrategie because here it must be taken into consideration that the recombination may produce only valid tours. Therefore this operator does not have a completely random character; it also contains deterministic components:
One of the r parents being recombined is chosen as a starting parent at random. In the tour of this starting parent, a town is selected at random. This is the first town in the tour of the offspring (we can call the town A). For each of the r parents, the left and right neighbor of this town (A) are examined. The nearest in distance is selected from the total 2.r possibilities, and this becomes the second town (B) in the tour. The same process is applied to the neighbors of B to yield C and so on until the end of the tour. If the 2.r possible neighbors are already built into the tour of the offspring, the nearest town still available is taken.
The quality function
The quality function calculates the complete length of
the tour:
The term di,(i+1) stands for the distance between the i´th and the (i+1)´th town in the tour, dn,1 is the distance between the last town and the first town in the tour.
Example
This example shows the evolution of a tour with 25 towns of a travelling salesman. The left picture shows the map of the towns. The other pictures show the evolution of the tour. Starting out from a random tour finally the optimal tour is found in 22 generations for this problem by use of a (10/2,30)ES.
G=0 G=1 G=2 G=3 G=4
Q=1958.9 Q=1191.5 Q=1003.0 Q=881.8 Q=713.9
G=5 G=7 G=8 G=9 G=10
Q=644.0 Q=627.6 Q=624.1 Q=575.3 Q=554.6
G=11 G=12 G=15 G=16 G=22
Q=529.5.0 Q=512.7 Q=511.8 Q=487.5 Q=472.0
Evolution Strategy with subjective evaluation:
Evolution of a Mixture of Colors  the Cherry Brandy Experiment
With the three liquid primary colors blue, red and yellow and with clear water the mixture of the color of a liquid is to be found, which is identical in color with the liqueur Cherry Brandy (BOLS). This very popular experiment is performed with our students since 1980.
The strategy
The optimization initially starts with a random parent
mixture. With the computer the dispensing of l offspring mixtures
is generated. Each mixture is standardized to a quantity of 30 ml, the
volume of a standard testtube. Now each 'offspring'student takes his
testtube and produces the mixture according to the generated dispensing
of the computer. All offspring testtubes are now positioned in front of
an illuminated surface. Together the students decide, which offspring mixture
is the best and is taken as the parent mixture of the next generation.
They tell the computer the number of the best offspring and with this the
next generation begins. As an example the following figure shows the table
with the dispensings of the 5th
generation:
Generation: 5
Stepsize 
blue 
yellow 
red 
transparent 

Parent 
2.00 
4.67 
4.77 
6.69 
13.87 
Offspring 1 
1.33 
5.28 
4.74 
5.84 
14.14 
Offspring 2 
1.33 
5.59 
4.71 
6.72 
12.98 
Offspring 3 
1.33 
4.64 
4.85 
6.60 
13.91 
Offspring 4 
2.00 
4.55 
5.48 
7.11 
12.87 
Offspring 5 
2.00 
3.48 
5.97 
6.15 
14.40 
Offspring 6 
3.00 
3.90 
6.93 
6.82 
12.35 
Offspring 7 
3.00 
3.24 
6.98 
5.32 
14.47 
Offspring 8 
3.00 
4.55 
3.93 
7.55 
13.97 
Example
With 8 'offspring'students we found the desired mixture
in about 11 generations with a (1, 8)ES. The following figure shows
the course of the quantities of the different components.
Evolution of Color and Shape
By means of subjective evaluation a rectangle is to be found, which is identical in color and shape with a randomly generated rectangle on the screen of a computer. Of course it is as well possible to evolve a rectangle which corresponds to an imaginary one in mind.
The object
On the screen of the computer l offspring rectangles are presented to the operator according to the (m, l)ES used for the optimization. All offspring rectangles differ in color and shape and the operator has to select m from them to be parent rectangles of the next generation. This is easy to be done just by clicking with the mouse to the desired offspring field.
The quality function
It is assumed, that there exists no objective function with different numerical quality values for different parameter settings. It is decided by means of subjective evaluation, which offspring are closest to the target figure and become parents of the next generation.
Example
The 'ancestral portrait gallery'
Literature
Herdy, M. (1990). Die Evolutionsstrategie  ein universelles Optimierungswerkzeug. Grundlagen der Modellierung und Simulationstechnik. 19. Jahrestagung, Rostock, 18.20, Dezember 1990. Rostock: Univ. Rostock
Herdy, M. (1990). Application of the Evolutionsstrategie to Discrete Optimization Problems. In H.P. Schwefel and R. Männer (Eds.) Parallel Problem Solving from Nature. Lecture Notes in Computer Science (496). Berlin: Springer.
Rechenberg, I. (1989). Artificial evolution and artificial intelligence. In R. Forsyth (Ed.) Machine Learning. London: Chapman; S 83103
Rechenberg, I. (1989). Evolution strategy  nature's way of optimization. In H. W. Bergmann (Ed.) Optimization: Methods and applications, possibilities and limitations. DLR lecture notes in engineering 47. Berlin: Springer; S 106126.
Rechenberg, I. (1994). Evolutionsstrategie '94, Werkstatt Bionik und Evolutionstechnik, Band 1. StuttgartBad Cannstadt: frommannholzboog.
Zerbst, E.W. (1987). Bionik: biologische Funktionsprinzipien
und ihre technischen Anwendungen. Stuttgart: Teubner.