Its author applied a genetic algorithm to evolve/optimize the blade shape of a wind turbine. It reminded me of Professor Ingo Rechenberg's work on a similar task: The BERWIAN (Berliner-Windkraft-Anlage) in which his group applied another kind of evolutionary algorithm -- evolution strategies.
As we are talking about green/clean energy resources, don't miss the chance of reading an interesting post at Martin Pelikan's blog on the same poetical vein (solar panels).
I am astonished as I had never thought the interview could be published in an official newsletter of such an excellent lineage such as ACM SIGevolution.
If you would like to read the newsletter, see it here. Pier Luca made, as usual, a beautiful work and if I were you I would not miss a single issue of SIGevolution!
Thank you so much, Pier Luca, Professor Schwefel, Professor Eurípedes, and all the SIGevolution guys and gals, for this amazing opportunity!
Today, June 12th 2009, is the 45th anniversary of an evolutionary algorithm: Evolution strategies.
So, to celebrate this, somehow, important date to evolutionary computation, I have made a brief interview with Professor Hans-Paul Schwefel concerning what the "unofficial" Arbeitsgruppe Evolutionstechnik had to overcome during the creation of this new optimization procedure. The questions focused on the period before, during, and after the innovation process that brought evolution strategies into life and how he sees the contemporary approaches being used. Here you are the interview.
01. Could you tell us a little about growing up in post WWII Germany and your high school later years at Canisius College? What kind of student were you? Did your daily life orbit around school-home and home-school?
School went smooth without any problems and without highlights until October 4th, 1957 (launch of the first artificial earth satellite 'Sputnik 1'). From then on, I wanted to become astronaut and became one of the best pupils, especially in maths. I had also lessons in playing the violin, was member of the school orchestra and the school choir, but more important for me were the actions as a boy scout, where I was urged to play a leader's role, very soon - until I needed more time for studying. B.t.w. I needed 90 minutes each per day for the way to and from highschool (class 6 to 13).
02. Why did you choose aerospace technology engineering as your undergraduation degree? Did the brain drain Germany faced (e.g., Operation Paperclip) have any influence on your decision?
Why? - see above! I was not aware of the brain drain (at least I don't remember) and due to my family's financial situation studying away from home was unthinkable.
03. When you were admitted at TUB, during your initial semesters, you had any (at least the vaguest) idea of working with computers and simulation in general?
No, since there were only mechanical calculators operated by means of a rotatable handle, at that time. The first available computer (in the basement of the institute of mechanics) became 'mine' during night times for my diploma thesis' simulation experiments.
04. Before joining in TUB's Hermann Föttinger-Institute for Hydrodynamics (HFI), had you already heard of your evolution strategies fellows (Ingo Rechenberg and Peter Bienert)?
No. I became engaged by invitation from the Head of the institute, because I was his best student (two times best marks in written exams).
05. How did you end up working at TUB's Hermann Föttinger-Institute for Hydrodynamics (HFI)? What was the academic feeling/environment there?
Besides of my duties, i.e. preparing and controlling other students' experiments, I spent much time with Ingo Rechenberg and later also Peter Bienert in performing 'our' work - until all of us were relegated, being said: "Cybernetics as such will no longer be done at this institute".
06. Was the idea of experimental optimization a well known practical method during 1960s engineering Zeitgeist or was it seen as an exotic way of doing research? What did the well established professors at HFI think about that?
The traditional way - as we saw it - was a sequence of creating hypotheses from first principles and known facts plus experiments to prove or falsify the hypotheses. Iteratively improving facilities or processes systematically was rare, though there was some literature about the 'design and analysis of experiments'. Our first successes were highly accepted and even mentioned in the press, but the established experts in the field of hydrodynamics were skeptical or even hostile. Thus we were forced to go back to traditional work or to leave.
07. Can we say the 1960s optimization Zeitgeist was all about linear and non-linear programming? Was gradient-based methods the archetype optimization methods of that time?
Exactly! Optimization methods were a topic of numerical maths. Some opponent said: "We've got the optimal optimization method already..." (he meant steepest descent/ascent) "...and need no more".
08. What were your initial feelings after seeing the results of the experimentum crucis? At least in essence, does that experiment share some features with the modern evolution strategies? To whom the Arbeitsgruppe Evolutionstechnik reported the feedbacks got from that experiment? Could we consider the experimentum crucis the first evolvable hardware experiment ever made?
The first ES version operated with just one offspring per 'generation' because we did not have a population of objects to operate with. I termed it later (1+1)-ES in order to distinguish it from 'multimembered' versions. And we used discrete mutations in the vicinity of the parent's position. In my diploma thesis'(1964/65) work I demonstrated that such more or less local strategy can get stuck prematurely. Therefore I proposed to use probability density distributions like the gaussian one for continuous variables. But we were proud of having shown that the simple ES worked under noisy and (perhaps) multimodal conditions, whereas one-variable-at-a-time and gradient methods failed. And the simple ES was much more efficient (quick) than opponents had predicted. Their (sometimes even now maintained) misconception was to think of uniformly distributed mutations in the whole search space.
But: There was no proof of convergence nor any theory of the efficiency. Rechenberg's PhD. thesis from 1971 contained the first efficiency results, i.e. the local velocity of the (1+1)-ES in n dimensions of two fitness landscapes.
The first evolvable hardware was created with Peter Bienert's diploma thesis as FORO 1, the first research robot (FOrschungsROboter) able to handle several step motors calibrating e.g. potentiometers at some mechano-electric facility (actually a hybrid computer acting on a pneumatic control device). That was also around 1970.
After the relegation from the institute of hydrodynamics in 1966, I earned my money at industry until 1970 (where I did the nozzle experiments), whereas Ingo Rechenberg and Peter Bienert settled (without salaries) at another institute of the Technical University of Berlin There we met again after I got a grant from the German research foundation for work on comparing ES with other numerical optimization strategies on a digital computer. That money reached from 1970 to 1975 (I finished 'my book' in 1974, which was accepted as dissertation, the defense of which tool part only in 1975). Besides of both theses of ours there were no further publications between 1965 and 1971 since too much time went into writing grant proposals and struggle for survival (except an article of mine in my school's yearbook 1966 and the frequent technical reports for the grant giving authority, i.e. unpublished work).
09. Once I saw a Professor Rechenberg's PPT presentation (only the PPT) in which there was a Galton Box (or bean machine). Was that device used as the mutation operator for the experimentum crucis? Galton boxes may have different distribution/density probability functions (depending on the manner the user set it up), what was the distribution/density function of the box used by the "unofficial" Arbeitsgruppe Evolutionstechnik?
The Galton box was used for demonstration purposes only. Actually, we used some kind of children's playing chips with a plus sign on one side and a minus sign on the opposite side.
In the simplest case with two chips the result could be: ++ with probability 1/4 for changing a variable in positive direction, or; -- also with probability 1/4 for changing a variable in negative direction, or; +- (or -+) with probability 1/2 for no change.
With more chips one could of course produce broader binomial probability distributions.
10. What did the judge board think about your senior thesis (undegraduation final project)?
I got the highest mark for that work (I had written the task's requirement myself, which was accepted by the Head of the fluid dynamics institute). Ingo and me got our diplomas at the same time together with a prize from the German Association of Engineers (VDI) for the best 3 students of the year 1965 (Ingo being 6 years, or 12 semesters, older than me).
11. After graduating, you did not join in (right away) a MSc. course or something similar, but went to work repairing Lockheed Super Constellation aircrafts coming back from South America. Didn't you think it was a (somehow) "ungrateful" work compared to all the experimental optimization and computer simulation work you had performed at TUB some few years (months?) earlier?
To put things in right order, my times studying at the TU Berlin required not only at least 10 semesters of topical lectures and exercises with exams, but in addition to that 12 months of practical work (internships), 6 of which had to be completed before entering the first semester, the other 6 in between the following 11 terms, plus studies with exams in 4 non-technical domains like philosophy, laws and economics, arts and foreign languages. It was during the 6 months between the semesters that I joined Lufthansa's dockyards at Hamburg and had to do with Lockheed's SuperConstellations. I also joined a team of specialists concerned with oxygen/hydrogen rocket motors (later on used for Ariane missiles' position control motors) at Boelkow's company near Munich as well as a helicopter jet engines factory (Turboméca) in Southern France.
In Germany there was not such a sharp split between undergraduate and graduate studies. One had to pass a series of exams after about half of the time (the 'Vordiplom') but one could not yet get a job with only that part of the 'basic' studies, normally. For clarity, here is a schedule of mine: 1959 highschool ended, 6 months internship, beginning of studies (after I had in vain tried to get a pilot school place at Lufthansa - the school was closed that year, the only reason why I tried to bridge the gap by joining the university) 1959-1965 studies in aero- and space technology with emphasis on propulsion and further 6 months internships and 'humanistic' studies in between. 1965/1966 coworker at the institute of hydrodynamics (full paid work for studies in turbulent wall shear stress measurement techniques - together with Ingo Rechenberg ((ES things were done aside and not paid for)))
1967-1970 work at industry (AEG research group Berlin, concerned with work on some kind of liquid metal driven energy converter without rotating parts; the flashing nozzle being one essential part of it) 1970-1975 grants from the German research foundation (DFG) for self-defined work, two professors had to serve (better non-serve) as supervisors - a biologist and a control and measurement scientist (Ingo Rechenberg became professor himself by a transition rule in the reorganisation of the university, saying that all people with a high grade Ph.D. exam should be some kind of lower-grade professors; that was around 1973/74 when his dissertation became published as a book).
1976-1985 first 1/2 year on a grant from a research project at Hanover, for which I developed a model of non-genetic variance among cloned guinea pigs; then work in Juelich between Cologne and Aachen in the nuclear research centre (KFA) as systems analyst in a working group doing simulation models of the whole energy system (demand, conversion, consumption with all kinds of energy carriers) in Germany, the European Union and beyond.
1985... professor at a new chair of systems analysis (applied computer science) at the (now also Technical) University of Dortmund - gained for my experience in systems analysis, not evolutionary computation.
12. The two phase flashing nozzle experiment is an interesting example of evolutionary optimization, do you think it would be a practical idea to apply the same approach (or a computer assisted one) to larger nozzles, such as those employed in aerospace industry/research?
One-component one-phase nozzles are theoretically well established and can be designed easily by means of known physical laws. Two-component nozzles (e.g. gas and solid particles in the flow) are a bit more difficult to design due to the shear stresses between fast fluid and slower particles, but there is a lot of empirical knowledge, now.
The problem with 'my' one-component two-phase case suffers additionally from non equilibrium thermodynamics of the phase transition from liquid to a mix of steam (fast) and liquid droplets (slow, also tending to cluster on walls and thus losing their energy content). I think that even now nobody is able to simulate these processes with boiling delay and supersonic shocks in the divergent part of the nozzle in order to optimally design such a flashing nozzle by means of CFD (computational fluid dynamics). But hot water rocket users might make use of my experiences. I tried to correspond with them - they not even answered a line.
13. Basically, what was the core of your work at AEG and KFA Jülich? Were there many opportunities of applying evolutionary computation in their problems?
After my success with the nozzle I was urged to manage a larger project, so that I tried to escape from such non-scientific work as soon as possible. After work I met Ingo Rechenberg and Peter Bienert at their site (control and measurement institute) and hoped for success of my grant application.
14. What was the main subject of your PhD./Dr.-Ing, thesis?
Comparison of Evolution Strategy (ES) with traditional numerical optimization methods, including improvements of ES (e.g. self adaptation of internal parameters, which lead to the later standard (μ, λ) versions), and trying to enhance theoretical analyses.
15. We may consider the years of 1964-1970, at large, as an early developmental and test of concept period for evolution strategies. How would you qualify (for evolution strategies) the subsequent decade, that is, the 1970s? Could we say it was during this decade the self-adaptation mechanism took place?
Exactly. But in 1976 I turned away because such work did not pay, and I became some kind of futurologist at Juelich.
16. After being admitted at Dortmund University as a full professor, what was the main aim your group set up for further research in evolutionary computation and how do you evaluate the results achieved?
I smuggled evolutionry algorithms' ideas into the subchapter 'optimization' in my courses on systems analysis, not forgetting to mention my experiences. It took not long until one and then more and more of my students became interested in just that part of the general topic. For them I tried to get money from research grants, and after 15 years the team had grown up to more than 30 coworkers.
17. Do you consider the genetic algorithm researchers switching from the traditional binary string representation and well known evolutionary operators approach to the estimation of distribution algorithms a (somehow) step toward an ES-like approach, since there is a (somehow) similarity between those algorithms when it comes to probability density/distribution function parameter(s) adaptation?
As always, I argue that any idea improving robustness and/or efficiency (at best: both) of an optimization algorithms is welcome. But, my personal interest (and at least at the beginning also Ingo's) has been in understanding and making use of real nature's tricks, too.
That is why arithmetic tricks not resembling natural processes are of a bit lesser interest to me. Artificial immune systems, ant colony optimization, differential evolution and many other approaches will have their specific domains and a practitioner would be stupid not to have all of them - including traditional methods -in his toolbox.
My experience is that even in one successful run to an optimum it may be necessary to switch between methods and to set some parameters anew by hand, as well.
18. What is your view upon derandomization approaches? Wouldn't be better to keep some "noise" along the evolution optimization process rather than biasing it towards a "direction"?
All of that may be helpful or stupid depending on the specific situation. Noise hampers in 'easy' cases, but helps sometimes in more difficult ones. A good strategy adapts its internal parameters during the search, e.g. the main direction. I call these parameters 'internal model' of the corresponding individuals and found that it is important to maintain diversity of those internal models' within the population. I am dreaming of an evolutionary algorithm that comprises many more internal parameters self-adjusting during the search.
19. Along the history of evolution strategies we can see an addition process of new features (multi-individual population, self-adaptation, variances and covariances, and so on) and these features have became a standard in evolution strategies. When seeing others' approaches, such as genetic algorithms (and the almost forgotten evolutionary programming), we don't verify the same phenomenon, since the most applied genetic algorithm (elitist SGA) are practically the same one established by Kenneth De Jong during the early 1970s, even though there were and there have been well-intentioned works to add new features to genetic algorithm, but they have not became a GA standard. In your opinion, why did that happen in, for example, genetic algorithms' field?
In some cases simple versions are good enough, in some cases people are not even aware of traditional approaches. Sometimes people follow the advice of prophets without reading the bible, and prophets often simplify to spread their message.
The problem of problem solving is multifaceted: First, there is not enough theoretical foundation of the cause/effect relations in optimum seeking methods under various conditions. Second, black box situations (those for which evolutionary algorithms MAY be used) are not classified, perhaps not classifiable. Therefore unpredictability prevails, surprises are common, and convergence to the (a) global optimum within a manageable time cannot be guaranteed. In practice, being better than the competitors is sufficient - for a while.
Thus, even slight improvements towards a (perhaps moving) optimum are appreciated, only theoreticians remain dissatisfied.
20. After forty five years of evolution strategies, what are your impressions for the next forty five?
I cannot forecast. Curiosity prevails - and satisfaction.
I was unaware of this event, but the Illigal Blogging guys have brought to my attention the pointer to HollandFest 09. It's an event to celebrate the contributions professor John Holland has made to evolutionary computation, genetic algorithms, complex systems in general and emergence.
Professor David Goldberg has uploaded his presentation at HollandFest 09. It's about the further development of genetic algorithms from the late 1980s until nowadays, remembering some important lessons the lecturer has learnt along the time, giving emphasis to three ones he learnt from his former advisor. He is microblogging about it on Twitter.
So this year already begun so special to evolutionary computation. It's not only Darwin's 200th anniversary; nor 150 years since the publication of his seminal book; nor 45 years from the day two Germans students set up the experimentum crucis that would open one of the branches of evolutionary computation -- Ingo Rechenberg will celebrate his 75th anniversary in this year too!); nor the 20 years since the publication of Goldberg's book about genetic algorithms. But it's also on celebrating John Holland's 80th anniversary and all his contributions to the field he has helped to build.
This year, 2009, is full of nice dates to be celebrated!
Today is the birthday of Charles Darwin, the scientist who began evolutionary biology as we know it today. It's Darwin's 200th annivesary.
Also, this year it will be completed 150 years since the publication of a seminal book and one of the most influential along all the human history: On the Origin of Species.
Its contribution to our biological world understanding is tremendous, of course it left for a time so many gaps that Darwin was unable to give the correct and complete answers, but its merits overcast any imperfection it may have.
Another interesting date sends us back to 45 years ago: 1964. The destination is Germany and its beautiful capital city: Berlin. There, a seasoned senior student Ingo Rechenberg and a newbie Hans-Paul Schwefel are about to produce the first results that would pave the way for a branch of evolutionary computation: Evolution Strategies (or Evolutionsstrategie, in German). A crude, simple and -- why not? -- elegant experiment takes place. Its results would show both students the method could be worth to be worked on.
Now, let's jump 25 five years into the future. The year is 1989. An enthusiastic professor from the University of Alabama releases his first book which would set the stage in the near future for so many debates around evolutionary computation, evolutionary algorithms and, of course, genetic algorithms themselves. The book would become an evolutionary computation classic by its own merits, making the fine art of genetic algorithms reachable and, more important, understandable for the large wide audience out there. It was in this book that scientists, practioners, students, and professors had their first contacts with genetic algorithms and evolutionary computation, being hard to find nowadays someone who implemented a genetic algorithm without having heard and/or read the pages of Genetic Algorithms in Search, Optimization, and Machine Learning. Of course, it is impossible to publish something expecting everyone will agree with your ideas and that book has found so many readers along the time having each one a critique view about it. Be the critiques for praise or not, it is difficult not to tell the importance such a book (has) had inside evolutionary computation. But, something is very hard to deny: That is a great book to read. Despite some small imperfections the reader gets what the book promises: A nice introduction to genetic algorithms and enough understanding to code one in computer programming language.
The way Professor David Edward Goldberg teaches the reader is very instructive and clarifying. He even simulates by hand a simple step of a genetic algorithm.
This year is a year of celebration for all of us who had/have a contact with evolutionary ideas. Let's praise and thank all those persons who invested a nice amount of the time of their lives helping to build the fields in which so many researchers, students, and so on have followed since then.
The post below is a translation from a Spanish posting made by Carlos and put on-line at his blog (La Singularidad Desnuda). See here for the original post.
The text has to do with Professor Hans-Paul Schwefel talk at last EvoStar delivered earlier this year. I should have made the translation much before, but I was unaware of it until yesterday. Despite the delay, Carlos' text is a very good overview concerning what was said during the talk and a valuable one because reports what a person who lived all the development process of an evolutionary algorithm witnessed along that time. I added some date corrections and two pictures I got from Juan Julián Merelo GuervósFlickr album. Thank you for the pictures, JJ!
Thank you very much Carlos for permiting me translating your original text!
I hope you enjoy it!
----------------------------------------
One of the best moments during the last week EvoStar event was Professor Hans-Paul Schwefel talk. For an evolutionary computation outsider, it must be said that the three main evolutionary computation branches arose almost simutaneously and in three different places, the algorithms are the following: genetic algorithms (GA); evolutionary programming (EP); and evolution strategies (ES). These last ones were created in Germany during the middle 1960s. Professor Schwefel is one of the creators - together with Professor Ingo Rechenberg (Peter Bienert also contributed with mechanical experiments) - of the first evolution strategy version, the so called two membered elistist evolution strategy or (1 + 1)-ES - later, Professor Schwefel would add more features, such as the self-adaptation mechanism as we know it nowadays and the comma selection scheme. Professor Schwefel is one of the evolutionary computation field pioneers and the talk was named "A Pioneer's View Onto Evolutionary Computation". The talk was very valuable, not exactly by the technical aspects (which were not the main talk focus), but because of the personal perspective Professor Schwefel approached.
Below there is a picture of what the TUB evolution technique working group (Schwefel, Rechenberg, and Bienert) made during the evolution strategies' early years.
Such a talk must be structured through a temporal manner: Past, present, and future. That was the exact talk structure but taking into account an original variation: We begin with the future, going to the present, and finally reaching the past. The two initial parts were very brief. Upon the future, Professor Schwefel showed his hope of what evolutionary computation technology may achieve, however he was sensible not to make accurate predictions. After that, he clarified that part of the talk with some quotes which for some persons may sound embarrassing. The first quote was a comment made by a referee who reviewed Professor Schwefel's seminal evolution strategy work in 1970:
"There is no necessity for another optimization method [except the gradient technique]"
That is an example of a referee whose words are full of glory. The second quote came from an IBM spokesman in 1974:
"Parallel computing will not be available before the year 2000."
That is the way IBM has followed recently. Before the lights of such examples of vision of future, we only must claim that the coming years will have so many surprises concerning the capacity and application of evolutionary algorithms, mainly in hotbed fields facing problems of large complexity, such as biotechnology.
Below we see the cover of Professor Schwefel thesis Adaptive mechanismen in der Biologischen Evolution und ihr Einfluß auf die Evolutiongeschwindigkeit.
The talk session dealing with the present was very brief too, and it was limited to verifing the exponential growth of the evolutionary computation community and academic production. We enter, then, in the talk part dedicated to the past, where Professor Schwefel reported his experiences in first person since the beginning of evolution strategies, the challenges faced, and all the lessons learned. The first one was "expect the unexpected", and he got it from the experiments made to find the optimal design of a nozzle. That nozzle was conceived as two funnels facing each other: By one of the entrances was injected a fluid composed of gas and a liquid subjected to high velocities, which passed through a small aperture, and was expelled at the other entrance (the nozzle exit). The objective was to achieve the maximum thrust and for that some parameters should be adjusted, such as in which point the small aperture should be put between the two entrances. Professor Schwefel had one of his first "crazy ideas" when thinking that not necessarily the two-funnels design was the optimal design, but there would be two entrances could have another forms of configuration and between them the funnels design could undergo variations, having freedom to vary their forms in three dimmesions. Applying the incipient evolution strategy technology, the following (astonishing) result was got:
The animation shows the evolution of a nozzle design since its initial configuration until the final one. After achieving such a design it was a a little difficult understanding why the surprising design was good and a team of physicists and engineers gathered to provide an investigation aiming at devising some explanation for the final nozzle configuration. Professor Schwefel also investigated the algorithmic features of evolution strategies, what made possible different generalizations such as a surplus of offspring created, the use of non-elitist evolution strategies (the comma selection scheme), and the use of recombination beyond the well known mutation operator to generate the offpsring. The second part of the talk had to do with some topics Professor Schwefel had already approached at past evolutionary computation events, such as the gap between evolutionary computation and natural evolution (static objectives, just one optimization criterion, fixed codification, synchronous evolution, etc.). Among other aspects, Professor Schwefel told about evolution strategies holding spatial structure, using predator-prey models, different gender (male/female) introduction, and diploid codification.
In short, it was an amusement attending such a talk, as much for its content as for the lecturer, a humble and an affable person which is a pleasure to talk with. Talks like that are what makes a conference be remembered along the time.
I have decided to start a series of posts on the History of Evolutionary Computation (HEC). Therefore, I shall focus my attention to the three main branches of Evolutionary Computation (EC): Evolution Strategies (ES, from the German word Evolutionsstrategie); Evolutionary Programming (EP); and Genetic Algorithms (GA).
The inner core of this (somehow) difficult "endeavour" would be writing and reporting what the creators of those methods did to bring into life a new myriad of nature inspired algorithms which have setting up a whole new area of research, their insights and experiments that helped them to write their stories and, also, the history of a new field.
This post does not intend to claim one method is better (or even the best) than any other (a thunderous voice speaks: Thou Shalt Remember The NFL!), but just a humble try to understand what were the main ideas behind something new and that represented at its time an example of innovation, what could help contemporary researchers, engineers, achievers, innovators, and so on to build their own innovations. I think that the difficulties and necessities those pioneers faced and, more important, overcame are full of interesting lessons we may learn from and use them as a source of inspiration, or a manner to simply admire their works.
This first post deals with the pioneer work of three German students that performed early experiments on what would later develop into a new evolutionary algorithm: Evolution Strategies. Their first experiments happened during the Summer of 1964 at the Technische Universität Berlin (TUB, Technical University of Berlin). Below, the images of Ingo Rechenberg and Hans-Paul Schwefel.
Ingo Rechenberg (Der Bioniker):
Hans-Paul Schwefel (Der Evolutionsstratege):
The third student was Peter Bienert (it is a pity there is no picture of him on the Internet), responsible for an early evolvable hardware experiment: FORO 1 (FOrschungsROboter), the research robot.
When Ingo Rechenberg (born 1934) and Hans-Paul Schwefel (born 1940) were students at TUB, both of them had the opportunity to attend some lectures on the then growing field of cybernetics. Even though those lectures were not on a regular basis, they could listen to researchers such as Dr. Karl Steinbuch (1917-2005), a visionary who predicted the modern world of multimedia and an early designer of neural networks: The learnmatrix.
Professor Karl Steinbuch:
Another professor influenced them: Heinrich Hertel (1901-1982), a professor of aircraft construction and an instigating mentor who advised his pupils to look into nature as a source of inspiration for aerodynamics shapes and related subjects, and never missed a chance of comparing biological forms (dolphins, birds, fishes, and etc.) to the archetypical aerodynamical forms. It would be worthful noting that Schwefel almost became Eugen Sänger's (1905-1964) assistant, but Sänger died right before Schwefel accomplishing his diploma thesis. In such an environment, Rechenberg and Schwefel saw a close connection between cybernetics and any search strategy.
Professor Heinrich Hertel:
Professor Eugen Sänger and his wife, Irene Brendt:
Another historical figure along that time that was a default influence for any engineer was, with no doubt, the German rocket engineer Wernher von Braun:
Norbert Wiener can be considered as an early pioneer of cybernetics, the field that gave birth to a whole new generation of scientific investigations:
His seminal book on the same subject:
That was the spirit of the time (or the Zeitgeist) in which the evolution strategies (ES) came to this world. It seems that was a fruitful age for new ideas...
The first meeting of Rechenberg and Schwefel at TUB was not in 1964, as some evolutionary computation insiders think, but in November 1963. Schwefel was a coworker newbie student at TUB's Hermann Föttinger-Institute for Hydrodynamics (HFI) and Rechenberg was a seasoned student at the same institute. Both were studying aerospace technology engineering and their respective duties had nothing to do with cybernetics, bionics, or optimization methods. Rechenberg, being a more experient member of HFI, could use the wind tunnel during the afternoons -- when the main research assistants had already left. They started investigating wall shear stress measurements, a subject Rechenberg had been doing for some time. Later, they decided to work on their own subject: Cybernetic Research Strategy, specially for improving (or optimizing) forms of slender bodies (wings, airfoils, airplane bodies, etc.) under air flow. Schwefel main work during this time was (and for which he was paid for) organizing exercises for other students, particularly on measurement techniques in fluid dynamics.
Below there are Ingo Rechenberg (background) and Hans-Paul Schwefel (foreground) at TUB's wind tunnel:
Despite at that time there were well established methods (mainly gradient-based ones, Gauss-Seidel and etc.) to deal with problems holding continuous variables, Rechenberg and Schwefel had found out that the traditional approach of changing one variable at a time and the discrete gradient method did not work in experimental optimization, what was the first focus of their research toward evolution strategies (ES). This impracticality of using those methods is due to the nature of the optimization that takes place in that kind of experiment: Instead of optimizing the parameters of a problem through a computer, the investigator must optimize the real object itself -- without computers!
Experimental optimization means that you have a real physical, mechanical, electrical, optical, chemical, etc. object or some model, like physical, of the real object -- and absolutely no computer -- and you want to alter some of its properties (size, charge, temperature, pressure, etc.) in order to achieve an improved performance according to some criterion (criteria). Before the end of the 1960s Ingo Rechenberg and Hans-Paul Schwefel did not think of using this procedure (an early form of evolution strategy, but without computers) as a numerical method. Computers were not yet available in larger numbers, and if so, their power was rather weak. Let alone noisy measurements and multimodality.
However, unlike traditional approaches of that time, changing all variables at the same time in some random fashion (smaller changes more frequently than larger ones) could work a little better. This was the seed of what would later be a new evolutionary algorithm.
At this point almost everything had already been set up for applying their new method. But another idea came from a somehow strange source... A science fiction story by a not so well known writer: Insel der Krebse (The Island of the Crabs), by Anatolij Dnjeprow. That story has to do with artificial and synthetic evolution ocurring in an island and made by synthetic organisms which mutate themselves to generate new ones. Rechenberg states that this story (also) was his inspiration for using a "population" (it was just a (1 + 1)-ES, that is, one parent generating one offspring and both, later, struggling for survival to become the parent in the next generation/iteration) instead of just one point of search, as it was/is the agenda of traditional methods at the time.
The front cover of Insel der Krebse:
Even though Insel der Krebse literarily covered some of the fundamental ideas (trial and error, mutation and struggling for life) of what would later be evolution strategies (ES), there were some methods at the time that had some, even though loosely, similarities with ES, such as George E. P. BoxEVOP and the gradient method itself.
But trial and error experimentation with further selection of the best variatons (mutations) composed the core of what would be the (1 + 1)-ES (also known as The Survival of the Fittest or The Extinction of the Worst). First there is just one parent (μ = 1) generating, through random mutation, an offspring (λ = 1). Then, both of them struggles for survival and the best is taken as the parent of the next generation.
The basic skunk of evolution strategies was born with discrete binomially distributed mutations centered at the ancestor's position, and just one parent and one descendant per generation. Since there is only one parent the use of a recombination operator makes no sense. The absence of a recombination/crossover operator was due to the lack of, at TUB's Hermann Föttinger-Institute for Hydrodynamics (HFI), several objects (airfoils, kinked plates, nozzles, etc.) and several wind tunnels that could operate at same time. The reader should remember that the first evolution strategies experiments were not performed in computers. They were all about experimental optimization, using real world objects and optimizing directly into their features (charge, weight, drag, thrust and so on). Despite not using a recombination operator during early experimental optimization, some few years (1971) later, Rechenberg, in his PhD. dissertation, had demonstrated the advantage of such an evolutionary operator, although investigating the effects of crossover on a (μ + 1)-ES (extinction of the worst) and on a study concerning numerical optimization -- it was along this time he developed a simple self-adaptation mechanism to cope with numerical optimization (the so called 1/5 Success Rule). Moreover, doing some theory was much easier for mutation only. Therefore, this was done first. It is a common misconception in genetic algorithm community that evolution strategies emphasize mutation and neglect recombination, what is not true.
Now, having all the ingredients gathered, it was the crucial moment to test the concept of their new method. The Experimentum Crucis was done at TUB on June 12th, 1964: Six plane planks linked by five adjustable hinges. It is an aerodynamics problem and its optimum solution is trivial: All the plane planks must align horizontally (but the optimal configuration may change depending on the air flux direction). Before doing the experiment, Schwefel used a mechanical calculator with the sum of squares function on integers using binomial mutations to demonstrated the (1 + 1)-ES would work, at least in principle. The principal objective of that experimental optimization was minimizing the kinked plates' drag.
The Experimentum Crucis, an example of experimental optimization:
There are 515 (or 345 025 251) possible combinations for the five adjustable hinges.
The first series of tries on the experimentum crucis was made with random start conditions, later other initial conditions were taken into account, even turning out to be easier, requiring less mutations to reach a satisfactory solution, although the optimum solution was known and trivial. The idea behind using a problem holding a known solution was twofold:
A) Be able to prove convergence; B) Demonstrate that the experimental method devised by Rechenberg and Schwefel did not take too much iterations to reach the optimum (or a satisfactory solution).
Some critics at the time predicted that such a method would need years or even millions of years to find a reasonable solution. Today it is not uncommon finding out people who claim on the grounds of pure random search when it comes to natural evolution.
The problem set up for the experimentum crucis' (experimental) optimization was finding the best reachable solution for the kinked plates' aerodynamic configuration, optimizing, along the way, some variables, mainly the drag.
That experiment can be considered as a sort of OneMax for an experimental optimization task. OneMax is a well known fitness function applied to retrieve the initial feedbacks from a new evolutionary algorithm and/or optimization method. That function is just a bit counting problem in which the algorithm must find the a binary string that has the maximum number of bits one. Therefor, if a binary string has length 5 (5 bits):
S1 = B1 B2 B3 B4 B5
Then, the best (optimum) solution in that OneMax problem is the string in which all tge bits Bn are 1:
Soptimum = 1 1 1 1 1
The core procedure to find the best solution is simply summing up each bit in the string.
An OneMax optimized by an evolution strategy:
Rechenberg and Schwefel selected a simple problem (the kinked plates experimental optimization) because they could verify the initial behavior of their method during the optimization search and, thus, they could get the first impressions of their method. For solving the experimentum crucis problem, they used an early form of a simple (1 + 1)-ES with binomially distribution random changes in the current best kinked plates' shape. In a (1 + 1)-ES there is just one parent (μ = 1) generating a single offspring (λ = 1) through random mutation. The whole optimization was made without any computer aid and completely performed by hand. In the 1960s West Germany, computers were not available as they are today, let alone during that time computational power was weak. Not to mention the fact that Rechenberg and Schwefel did not think at all of using their method as a numerical optimization search technique until around 1970. The migration of the early evolution strategy from the experimental optimization realm to the numerical venue was Schwefel's "crazy" idea when he began looking for a competitive derivative-free numerical optimization method.
The mutation operator applied was some kind of children's playing chips with a plus sign on one side and a minus sign on the opposite side. In the simplest case with two chips the result could be:
1) ++ with probability 1/4 for changing a variable in positive direction, or; 2) -- also with probability 1/4 for changing a variable in negative direction, or; 3) +- (or -+) with probability 1/2 for no change.
With more chips one could of course produce broader binomial probability distributions. A Galton box was used too, but only for demonstration purposes (see the image below).
A Galton box and the experimentum crucis:
The amount of iteration (or generations) the simple two membered (1 + 1)-ES needed was not 200, but different amountd in two successive tries. The best solution found was not flat at all, because drag measurements were not exact enough to distinguish between what would be flat and nearly flat.
The experimental optimization's iterations for the experimentum crucis:
Schwefel's diploma thesis, finished in March 1965, revealed the simple two membered (1 + 1)-ES can get stuck in such a discrete environments and, henceforth, they decided to concentrate on continuous Gaussian mutations. For his diploma thesis, Schwefel simulated an evolution strategy on a ZUSE Z23 computer, a creation of the German computer pioneer Konrad Zuse. In the same year, another student, called H. J. Lichtfuß (Evolution eines Rohrkrümmers Diplomarbeit, Technische Universität Berlin, Deutschland, 1965), got good results optimizing bended pipes through evolution strategy made as an experimental optimization procedure.
Z23 computer data sheet:
The Z23 computer was applied on a wide range of areas, from contructional engineering to ballistics and electronics design. It was available with compilers for the German formula code and for ALGOL 60.
The Z23 console:
Konrad Zuse:
Schwefel programmed the first cotinuous and computer implemented evolution strategy in the Z23, writing the code in an assembly-like programming language named Freiburger Code. This language was designed for solving mathematical problems and in an easier manner than writing the code in pure machine language. He took 1000 random numbers from a book and stored them as an array. His continuous and computer implemented (1 + 1)-ES program was put on a punched tape. The objective (or fitness) function used was a simple two dimensional parabolic ridge with positive integer numbers for the two variables. He started his simulation on an evening and got the results the next morning.
When Schwefel got his results he got astonished about the patterns of failure the method revealed depending on the angle of inclination of that ridge and the pattern of the mutations (e.g. in the Moore neighborhood only) that method, the (1+1)-ES with binomially distributed mutations, could be stuck in solutions that even were not local optima. He found a theoretical explanation for that, finally, within his diploma thesis in 1965. Since he could easily see that the univariate (or Gauss-Seidel or one-variable-at-a-time or coordinate) strategy would have even more problems on the ridge and that problem would be too easy for a (continuous) gradient strategy, he did not test them explicitly.
Although the somehow good results Ingo Rechenberg and Hans-Paul Schwefel achieved using the simple (1 + 1)-ES, the German academic establishment at that time did not welcome their evolution strategy method in a good way. The establishment was, indeed, skeptical. Maybe, this reaction could be an expression of the 1960s optimization methods' Zeitgeist. Even there were optimization researchers claiming they did not need another search method except the gradient one (steepest ascent/descent). One of the main researchers at TUB's Hermann Föttinger-Institute for Hydrodynamics (HFI) went to the point of saying that "cybernetics as such will no longer be done at this institute". After this, Rechenberg and Schwefel had to come back to work in fluid dynamics or they would have to leave HFI and they decided to leave.
After getting away from HFI, Ingo Rechenberg started to investigate the theoretical aspects of the (1+ 1)-ES and Hans-Paul Schwefel got a job because he had married with his girlfriend, Ms. Antje Schulte-Sasse (now Ms. Antje Schwefel and the person behind the biennial report Blaues Heft) and got children some time after marrying. Then, Schwefel went to an industrial research facility at AEG (Allgemeine Elektrizitäts-Gesellschaft) and also maintened an academic connection with the Institute of Nuclear Technology of the Technical University of Berlin. At the AEG research laboratory, Klockgether and Schwefel made an interesting evolution strategy application: The optimization of a two-phase flashing nozzle. That was, again, made as an experimental optimization.
Even today, it is not possible to calculate what happens within such a nozzle: thermodynamically far away from equilibrium, drag between slow water droplets and fast steam, three-dimensional turbulent boundary layer with liquid sub-layer, supersonic behind nozzle throat, and etc. As someone could ask himself, that design principle behind that nozzle was never applied to real rocket propulsion, because, to do this, someone would need to do the experiments once more for bigger rockets.
At the time, there were some arguments against that nozzle design, being the principal one the non-optimal shape achieved and the strange design method employed. The first part of this argument seems strange because there was no a priori optimal solution known for the nozzle problem and there is no way of stating a speficic shape is the optimum.
Below, the intial and final nozzle designs:
The two-phase flashing nozzle video:
Despite achieving good results employing the new-born evolution strategy method, Rechenberg and Schwefel needed research grants to continue their investigations, but could not get finnancial support because both of them lacked a PhD. degree at the time. Even though, they made a request for finnancial support, but it was denied. Later, they tried to convince their professors, Professor Helmcke (a biologist) and Professor Gast, to undersign a research proposal on evolution strategies and employ them as research assistants. But, there were some negative recommendations coming from peer reviewers that analysed the proposal and there was someone who disliked the term "evolution strategy", what made the "wanna be" research assistants guessing it was made by some creationist.
It was a pity the research proposal was denied, because Rechenberg and Schwefel were thinking of new features for their method: Bigger populations; theoretical analysis; new mutation operators; real-valued variables; new computer implementations; and the contruction of an automaton (FORO 1, by Peter Bienert) operating under the rules of their method. Those features were only investigated some years later along the 1970s and expanded throughout the next 20 years.
But it all makes sense when viewed under the light of how important publications were and are. Without them, it is almost impossible of obtaining research grants. The only "publication" they got was a brief article in the popular magazine Der Spiegel.
Below, Ingo Rechenberg and the Der Spiegel article:
On the role of publications, Schwefel states:
Since we were foolishly underestimating the role of publications and spent no time for that (perhaps, we would not have been successful in trying to send papers to journals or conferences -- we were students first and even later had no higher academic degrees like PhDs), the community did not hear/read about our work. Those who heard about reacted in different ways: Students in other faculties of TUB tried to imitate our ES. Most professors took our ideas for nonsense, except for two: a biologist and Prof. Gast.
Ingo Rechenberg, Hans-Paul Schwefel and Peter Bienert would come back to work together, in the early 1970s, at the Institute of Measurement and Control Engineering. Schwefel's PhD. dissertation was not finished before 1974, but in the next year he got his PhD., while Rechenberg got his professorship at, ironically, Technical University of Berlin. It seems that Peter Bienert stayed at Rechenberg's new born group at TUB: Bionik und Evolutionstechnik. Schwefel's dissertation results demonstrated that the simple two membered (1 + 1)-ES behaved very similar to other local search methods, and he realized only multimemberd evolution strategy (an evolution strategy that has a population bigger than one or two) could do a satisfactory optimization job with some possitive probability.
Along the 1970s, Rechenberg began to more thoroughly study the theoretical aspects of evolution strategies. For this task, he used quite simple objective (or fitness) functions, such as the sphere model and the corridor. From these investigations, was born one of the early mechanisms to self-adapt the parameters of an evolution strategy: The so called 1/5 Success Rule.
The 1/5 rule states: If less than 20% of the generations are successful (i.e. offsprings better than parents), then decrease the step size for the next generation; if more than 20% are successful, then increase the step size in order to accelerate convergence.
It is an extremely simple rule and its robustness can be considered everything but weak. However, it was a fisrt step into the quest for a strong self-adaptation mechanism.
The cannonical self-adaptation mechanism was devised by Hans-Paul Schwefel in the second half of the 1970s. It uses a lognormal function and it is as follow:
The aforementioned self-adaptation mechanism distributes the Gaussian density function in the following way along the axes:
We can clearly see that the use of that mechanism spread the mutation distribution in a ellipsoidal fashion through the fitness landscape, but it can only follow directions that are aligned with the coordinate system and it has no capabilities for getting interdependence among objective (or fitness) function's variables. When dealing with problems of big dimensions, the ellipsoids become hyperellipsoids that can expand or contract along the axes directions only.
There is a simpler lognormal self-adaptation mechanism:
It also distributes the mutations in the same manner as the previous mechanism, but, instead of being ellipses, the shapes are circles:
It sees no interdependence among variables too and cannot expand or contract along the axes directions as the former mechanism does. For problems of high dimensions, the circles become hyperspheres.
The other mechanism is almost the same as those ones above, but this one can take into account the interdepence among the variables. It sees the interdepence through the calculation of the covariance matrix:
The alphas are rotation angles and the beta is a constant value chosen as 0.0873. Now, the mutation operator can spread an offspring along directions non-aligned with the coordinate system:
Now, there is an extra degree of freedom, since the ellipsoids now not only can contract and expand along axes directions, but they can also rotate toward directions that are not aligned with those axes.
Below, there is an example of a generic representation for an evolution strategy individual:
Those developments came from Schwefel's experiences with numerical optimization and he introduced in his PhD. thesis the well known evolution strategy nomenclature: The so called comma notation, (μ, λ)-ES; and the plus notation (μ + λ)-ES. Now, instead of using just one parent (μ = 1) and one offspring (λ = 1), there are μ parents generating λ offspring.
The main difference between the comma and the plus strategies has to do with the selection mechanism. The plus strategy works as follows: There are μ parents generating λ offspring and, then, both parents and offspring compose a temporary population from which the best μ individuals are selected to become parents in the next generation (or iteration). The comma strategy follows a similar fashion, that is, there are μ parents generating λ offspring too, but the selection takes place only in the offspring set from which the best μ individuals are selected to be parents in the next generation.
The plus strategy seems to work better when it comes to combinatorial problems and it can get stuck easily in local optima when performing continuous optimization. On the other hand, the comma approach is better suited to continuous/parametric optimization problems and one of its main advantages is exactly the selection mechanism which permits a temporary degradation of the best solution found so far to overcome local optima -- however, the comma approach can work poorly if ill configured, for example setting μ = λ, what is a simple random walk.
The inclusion of the crossover (or recombination) operator changed a little the "official" evolution strategy notation, adding a new parameter: The number of individuals involved in recombination, ρ. Then, the aforesaid notations would be: (μ/ρ, λ)-ES and (μ/ρ + λ)-ES, ρ can be set up to μ (ρ = μ), what permits multi-individual crossover.
There are two types of crossover: Intermediary and discrete. The first one is just a centroid calculation or the center of mass.
The intermediary crossover scheme:
The other scheme is a simple random selection following a coordinate wise procedure.
The discrete crossover scheme:
In a paper from 1995, Hans-Paul Schwefel and Günter Rudolph proposed what they called comtemporary evolution strategies and included another parameter into the notation: The lifespan, represented by κ. The new notation would be (μ/ρ, λ, κ)-ES. That new parameter is important because it would avoid a candidate solution of surviving forever and trapping the search in local optima.
Recently, the derandomization approach has been incorporated into evolution strategies, such as CMA-ES, but this is other long story.
Along the time Rechenberg and Schwefel were developing the evolution strategy, in the other side of Atlantic Ocean there was another community investigating a similar algorithm. The evolutionary computation communities in each side of the Atlantic Ocean would only meet in 1990, at PPSN I (Paralell Problem Solving from Nature, David Edward Goldberg helped to translate that conference name into English from the German Naturanaloge parallele Problemlösungs-Strategien). But there was an "unofficial" meeting before this date, in 1989 David E. Goldberg and Yuval Davidor met in Germany, what could be considered the first encounter of both communities. It is fair to say that when Rechenberg and Schwefel finished their respective PhD. dissertations, no one was aware of Professor John Holland's pioneer work on genetic algorithms, that was made almost concurrently with the German evolution strategies. The Germans even "missed" Holland's seminal book Adaptation in Natural and Artificial Systems when it was published for the first time, but, later, both of them got aware of Holland's work (Schwefel gave Holland's book as a birthday gift to Rechenberg). Around 1969-1970, Schwefel began to sistematically search for derivative free optimization methods and found interesting works that had, in essence, a similarity with evolutionary approaches:
Hans-Joachim Bremermann at Berkeley; Lawrence .J. Fogel at San Diego; Leonard A. Rastrigin at Riga (USSR); J. Matyas in Czechoslovakia; J. Born (Evolutionsstrategien zur numerischen Lösung von Adaptationsaufgaben, 1978) at Berlin, in the Eastern side of Berlin Wall; G. Rappl (Konvergenzraten von Random Search Verfahren zur global Optimierung, 1984) at Munich.
Schwefel tried to contact some of those researchers. He first got into contact with Rastrigin, in Riga (USSR) and with Matyas in CSR -- Rastrigin even sent him a copy of a book (monograph) about a random search method he developed in which trials were done on the surface of a hypersphere. Some years later, Schwefel got into contact with Bremermann, but was unable to maintain any academic connection due to the lack of Bremermman's address. Schwefel got some papers from and a copy of Lawrence J. Fogel's book Artificial Intelligence Through Simulated Evolution.
There were no important evelution strategy developments between 1976 and 1988. Schwefel began his professorship at University of Dortmund (now Technical University of Dortmund) in 1985 and evolutionary algorithms were just a minor topic inside the main branch named systems analysis. The first student interested in evolutionary algorithms appeared only in 1989, after hearing of genetic algorithms. In the next decade (1990s), evolution strategy and evolutionary computation researchers focused their attentions to theoretical and complexity analysis of evolutionary algorithms and from those investigation have arisen the first steps to formalize evolutionary algorithms, despite disagreements between researchers. The 1990s also saw the emergence of a new evolutionary based approach: Estimation of Distribution Algorithms.
The kind of work Ingo Rechenberg, Hans-Paul Schwefel and Peter Bienert made in the 1960s can be considered an achievement that rarely happens during a lifetime. After 45 years of hard work it is very beautiful to see their work has helped to establish a whole new research area and all the results investigators all around the world (and, alas, other planets) have got.
Nowadays, Ingo Rechenberg is the head of Bionik & Evolutionstechnik group at Technischen Universität Berlin. Peter Bienert works with him there.
Hans-Paul Schwefel is now retired from the former systems analysis chair (now algorithm engineering) at University of Dortmund. He is an emeritus professor at Dortmund.
All models are wrong, but some of them are useful. (G.E.P. Box)
Some Acknowledgements now:
I am very grateful to Professor Hans-Paul Schwefel, who made all the corrections in the previous text and also suggested some points to speak about. I thank Professor Schwefel, also, for replying me a very long list of questions (50!!! and another set concerning the 45 years of evolution strategies) about the first works in evolution strategies and for his patience to answer all the question set.
I would like to thank Ms. Antje Schwefel for delivering some texts of mine to her husband, Professor Schwefel, and, also, for replying me some questions about Chinese and Japanese languages. Thank you for translating my name into Chinese too.
Thank You, Professor David Edward Goldberg, for your correction about the "official" meeting of USA and German evolutionary computation communities.
