Metaheuristics Set
coordinated by
Nicolas Monmarché and Patrick Siarry
Volume 9
First published 2017 in Great Britain and the United States by ISTE Ltd and John Wiley & Sons, Inc.
Apart from any fair dealing for the purposes of research or private study, or criticism or review, as permitted under the Copyright, Designs and Patents Act 1988, this publication may only be reproduced, stored or transmitted, in any form or by any means, with the prior permission in writing of the publishers, or in the case of reprographic reproduction in accordance with the terms and licenses issued by the CLA. Enquiries concerning reproduction outside these terms should be sent to the publishers at the undermentioned address:
ISTE Ltd
27-37 St George’s Road
London SW19 4EU
UK
www.iste.co.uk
John Wiley & Sons, Inc.
111 River Street
Hoboken, NJ 07030
USA
www.wiley.com
© ISTE Ltd 2017
The rights of Alain Pétrowski and Sana Ben-Hamida to be identified as the authors of this work have been asserted by them in accordance with the Copyright, Designs and Patents Act 1988.
Library of Congress Control Number: 2017931831
British Library Cataloguing-in-Publication Data
A CIP record for this book is available from the British Library
ISBN 978-1-84821-804-8
Evolutionary algorithms are expected to provide non-optimal but good quality solutions to problems whose resolution is impracticable by exact methods. They are inspired by Darwin’s theory of natural selection.
This book is intended for readers who wish to acquire the essential knowledge required to efficiently implement evolutionary algorithms. The vision offered by this book is essentially algorithmic and empirical. Indeed, the theoretical contributions in this field are still too incomplete to provide significant help in solving the problems for which these algorithms are used.
Chapter 1 describes a generic evolutionary algorithm as well as the basic operators that compose it. The main concepts presented in the other chapters are introduced here. This chapter also presents the binary representation and introduces Genetic Algorithms.
Chapter 2 is devoted to the solving of continuous optimization problems, without constraint. Real representation is introduced as well as basic variation operators able to deal with it. Three efficient approaches are then described: Covariance matrix Adaptation Evolution Strategies, Differential Evolution and Particle Swarm Optimization, which are well suited for continuous optimization. The chapter ends with comparisons between these approaches on a set of test functions.
Chapter 3 supplements Chapter 2 by adding constraints to an objective function defined in a continuous search space. The different approaches to taking constraints into account are presented with their main variants. Some methods are related to multi-objective optimization, which is presented in Chapter 5.
Chapter 4 is related to combinatorial optimization. These problems are extremely varied and often very difficult. From examples of resolution, it is difficult or even impossible to deduce information that is generalizable to other cases. Thus, we have decided to present a catalog of variation operators able to deal with the constraints associated with order-based problems. This class of problems has been chosen because they are often parts of real-world problems. For this reason, they have been the subject of an important research effort for several decades.
Chapter 5 first presents the basic notions necessary to understand the issue of multi-objective optimization. It then describes the NSGA-II method, which is one of the best known and most effective in the field. But NSGA-II, like the other algorithms based on Pareto dominance, is efficient when there are less than 4 objectives. So, the chapter ends with a presentation of a range of approaches to solve problems with many objectives, i.e. 4 or more.
Chapter 6 is devoted to the description of different approaches of genetic programming used in the context of machine learning. Two classes of applications are presented: symbolic regression and symbolic classification. Genetic programming is the subject of a special chapter to emphasize the ability of evolutionary algorithms to discover good solutions in an ill-defined search space, whose size is not fixed during an evolution.
We warmly thank Professors Patrick Siarry and Nicolas Monmarché for inviting us to contribute to the “Metaheuristics” set of books. Professor Michalewicz agreed to give us valuable advice when we developed the contents of this book. We are indebted to him for his help and we thank him with gratitude.
Alain PÉTROWSKI
Sana BEN-HAMIDA
February 2017