Natural Computing Series
Series Editors: G. Rozenberg
Th. Bäck A.E. Eiben J.N. Kok H.P. Spaink
Leiden Center for Natural Computing
Advisory Board: S. Amari G. Brassard K.A. De Jong
C.C.A.M. Gielen T. Head L. Kari L. Landweber T. Martinetz
Z. Michalewicz M.C. Mozer E. Oja G. Paun J. Reif H. Rubin
A. Salomaa M. Schoenauer H.-P. Schwefel C. Torras
D. Whitley E. Winfree J.M. Zurada
°
C
C
N
Kenneth V. Price · Rainer M. Storn
Jouni A. Lampinen
Differential Evolution
With 292 Figures, 48 Tables and CD-ROM
APractical Approach to Global Optimization
123
Library of Congress Control Number: 2005926508
ACM Computing Classification (1998): F.1–2, G.1.6, I.2.6, I.2.8, J.6
ISBN-10 3-540-20950-6 Springer Berlin Heidelberg New York
ISBN-13 978-3-540-20950-8 Springer Berlin Heidelberg New York
This work is subject to copyright. All rights are reserved, whether the whole or part of the material is
concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation, broadcasting,
reproduction on microfilm or in any other way, and storage in data banks. Duplication of this publication
or parts thereof is permitted only under the provisions of the German Copyright Law of September 9,
1965, in its current version, and permission for use must always be obtained from Springer. Violations
are liable for prosecution under the German Copyright Law.
The publisher and the authors accept no legal responsibility for any damage caused by improper
use of the instructions and programs contained in this book and the CD-ROM. Although the
software has been tested with extreme care, errors in the software cannot be excluded.
Springer is a part of Springer Science+Business Media
springer.com
© Springer-Verlag Berlin Heidelberg 2005
Printed in Germany
The use of general descriptive names, registered names, trademarks, etc. in this publication does not
imply, even in the absence of a specific statement, that such names are exempt from the relevant
protective laws and regulations and therefore free for general use.
Cover Design: KünkelLopka, Werbeagentur, Heidelberg
Typesetting: by the Authors
Production: LE-T
E
X Jelonek, Schmidt & Vöckler GbR, Leipzig
Printed on acid-free paper 45/3142/YL – 5 4 3 2 1 0
Authors
Kenneth V. Price
Owl Circle 836
Vacaville, CA 95687
USA
Rainer M. Storn
Rohde & Schwarz GmbH & Co.KG
Mühldorfstraße 15
81671 München
Germany
Jouni A. Lampinen
Lappeenranta University of Technology
Department of Information Technology
P.O.Box 20
53851 Lappeenranta
Finland
Series Editors
G. Rozenberg (Managing Editor)
rozenber@liacs.nl
Th. Bäck, J.N. Kok, H.P. Spaink
Leiden Center for Natural Computing
Leiden University
Niels Bohrweg 1
2333 CA Leiden,
The Netherlands
A.E. Eiben
Vrije Universiteit Amsterdam
KP: To my father
RS: To my ever-supportive parents, to my beloved wife, Marion, and to
my wonderful children, Maja and Robin
JL: To the memory of my little dog and best friend Tonique, for all the
happy countryside and city memories we shared
Preface
Optimization problems are ubiquitous in science and engineering. What
shape gives an airfoil maximum lift? Which polynomial best fits the given
data? Which configuration of lenses yields the sharpest image? Without
question, very many researchers need a robust optimization algorithm for
solving the problems that are fundamental to their daily work.
Ideally, solving a difficult optimization problem should not itself be dif-
ficult, e.g., a structural engineer with an expert knowledge of mechanical
principles should not also have to be an expert in optimization theory just
to improve his designs. In addition to being easy to use, a global optimiza-
tion algorithm should also be powerful enough to reliably converge to the
true optimum. Furthermore, the computer time spent searching for a solu-
tion should not be excessive. Thus, a genuinely useful global optimization
method should be simple to implement, easy to use, reliable and fast.
Differential Evolution (DE) is such a method. Since its inception in
1995, DE has earned a reputation as a very effective global optimizer.
While DE is not a panacea, its record of reliable and robust performance
demands that it belongs in every scientist and engineer’s “bag of tricks”.
DE originated with the Genetic Annealing algorithm developed by
Kenneth Price and published in the October 1994 issue of Dr. Dobb’s
Journal (DDJ), a popular programmer’s magazine. Genetic Annealing is a
population-based, combinatorial optimization algorithm that implements
an annealing criterion via thresholds. After the Genetic Annealing algo-
rithm appeared in DDJ, Ken was contacted by Dr. Rainer Storn, (then with
Siemens while at the International Computer Science Institute at the Uni-
versity of California at Berkeley; now at Rohde & Schwarz GmbH, Mu-
nich, Germany) about the possibility of using Genetic Annealing to solve
the Chebyshev polynomial fitting problem. Determining the coefficients of
the Chebyshev polynomials is considered by many to be a difficult task for
a general-purpose optimizer.
Ken eventually found the solution to the five-dimensional Chebyshev
problem with the Genetic Annealing algorithm, but convergence was very
slow and effective control parameters were hard to determine. After this
initial find, Ken began modifying the Genetic Annealing algorithm to use
floating-point instead of bit-string encoding and arithmetic operations in-
