Evolution Strategy in Action

10 ES-Demonstrations


presented on the

International Conference On

Evolutionary Computation

The Third Parallel Problem

Solving From Nature (PPSN III)

Jerusalem, Israel

October 9-14, 1994


Michael Herdy

Giannino Patone

Technical Report TR-94-05

October 1994




Technische Universität Berlin email: herdy@fb10.tu-berlin.d400.de

Bionik und Evolutionstechnik fon: +49-30-31472663

Ackerstr.71-76, Sekr.Ack1 fax: +49-30-31472658

D-13355 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 ftp-server. As well the other demonstration programs will be available one after the other. Any one time it will be announced in the GA-Digest.

The address of our ftp-server is


FTP-BIONIK.FB10.TU-BERLIN.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 light-transmissive 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 two-dimensional 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.

Start Finish

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 three-dimensional logic game. The cube consists of 26 partial-cubes, the 6 middle-cubes, 12 border-cubes and 8 corner-cubes. The state of the cube can be changed by turning any of the six faces. The visible faces of these partial-cubes 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 partial-cubes are at their home position so that only monochromatic surfaces on the cube exist.

The object

The middle-cubes cannot change their position relative to each other. With each turn of a cube face 4 corner-cubes and 4 border-cubes 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 middle-cube.

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 middle-cube 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 corner-cubes. A border-cube is correctly positioned if it contains the two colors of the middle-cubes it touches. For every wrongly positioned border-cube, Q3 is increased by 4. Similarly, a corner-cube is correctly positioned if it contains the three colors of the middle-cubes it touches. For every wrongly positioned corner-cube, Q3 is increased by 6. In the case of correctly positioned but still wrongly turned border- or corner-cubes, 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 cube-slice 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 two-border-turn, two-corner-turn, three-border-swap, two-border/two-corner-swap, three-corner-swap, double-border-swap and double-corner-swap. The operators three-border-swap, three-corner-swap and two-border/two-corner-swap 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 border-cubes and wrongly positioned corner-cubes 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 Parents-Tour
1 5 4 3 2 6 7 8 9 10 11 12 Inversion of the tour segment 2-3-4-5
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 2-3-4-5
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 test-tube. Now each 'offspring'-student takes his test-tube and produces the mixture according to the generated dispensing of the computer. All offspring test-tubes 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 83-103

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 106-126.

Rechenberg, I. (1994). Evolutionsstrategie '94, Werkstatt Bionik und Evolutionstechnik, Band 1. Stuttgart-Bad Cannstadt: frommann-holzboog.

Zerbst, E.W. (1987). Bionik: biologische Funktionsprinzipien und ihre technischen Anwendungen. Stuttgart: Teubner.