Cover Page

Difficulties increase the nearer we get to the goal.

- Johann Wolfgang von Goethe

There are much less difficulties in solving a problem than in defining it.

- Joseph de Maistre

Iterative Optimizers

Difficulty Measures and Benchmarks

Maurice Clerc

Wiley Logo

First published 2019 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 2019

The rights of Maurice Clerc to be identified as the author of this work have been asserted by him in accordance with the Copyright, Designs and Patents Act 1988.

Library of Congress Control Number: 2019930133

British Library Cataloguing-in-Publication Data
A CIP record for this book is available from the British Library
ISBN 978-1-78630-409-4

Preface

The Essentials

  • – Problems in a set of test cases can be classified according to several difficulty measures consistent with one another, in other words approximately giving the same ordering relation;
  • – these measures are valid for optimizers that explicitly or implicitly assume that “nearer is better”, in probability;
  • – some can be estimated using the Monte Carlo method, when the structure of the landscapes of the problems of the test case is unknown (basins of attraction, plateaus, local minima). Computations, however, can take a very long time;
  • – one of the measures presented requires an acceptable error threshold to be assumed, but its coding only takes a few lines. The other measure, somewhat more complex because it is based on position triplets, does not require an error threshold to be a priori defined, but is less reliable in the presence of plateaus;
  • – another difficulty indicator, δ0, is proposed based on the structure of the landscape of the problem. It is consistent with previous ones and can be quickly calculated, but it requires the basins of attraction and plateaus of the problem landscape to be known;
  • – since this information is rarely given and difficult to find in conventional test cases, the LandGener program is specifically designed to create known structure landscapes, upon which δ0 is easily computable;
  • – a typology of all possible landscapes is established, essentially in terms of modality and plateau ratio, with the estimate of the relative significance of each class;
  • – some conventional test cases are analyzed based on this typology. It is shown that they are biased in favor of certain types of problems, for example, unimodal ones or ones without plateaus. However, the application of a difficulty measure makes it possible to classify their problems, from the easiest to the more selective;
  • – rigorous definitions of the concepts of usage and exploration are given, making them measurable. The main types of evolution of their ratio (balance profiles) are studied.

Maurice CLERC

January 2019

Introduction

Every year, not to say every month, a new optimization algorithm is proposed, accompanied by the creator’s claim that it is superior to the previous ones. This type of assertion is based on test results achieved with test cases, more specifically a selection of problems to which the algorithm is applied.

In Guided Randomness in Optimization (Clerc 2015), I show that it is easy to choose a set of test cases and the way the results are addressed to seemingly “justify” this superiority.

For example, consider the test case of Table I.1, which was actually used in an article1. With such a set of problems, an algorithm has to be defined whose signature (see section A.3) is biased in favor of the center of the search space to obtain good results. At the extreme, if the algorithm is to be seen as a black box inside of which the test case is introduced and that offers a solution, there is a “magical” box that finds the perfect solution of each of the functions in a time almost equal to zero2.

Table I.1. A biased test case in a published article (see footnote 1). The names of the functions have been kept

Name

Equation

Sphere

images

Rosenbrock

images

Ellipsoid

images

Rastrigin

images

Ackley

images

Obviously, if users, impressed by the optimistic conclusions of the presentation of the algorithm, try to apply it to their own problems, they will almost surely get very bad results.

This lack of reliability is due to the fact that the test set is not representative of the problems that the user will have to solve.

Moreover, in practice, it is interesting that a test case contains problems of different levels of difficulty. In fact, this allows a better hierarchization of the algorithms tested with this test case, knowing that users will not necessarily prefer the algorithm capable of solving most difficult problems if theirs are not so much and that in addition, this algorithm is very expensive in terms of computing resources. A precise definition of the term “difficulty” is therefore necessary. This is far from being trivial, because, as shown in the small example above, the difficulty of an optimization depends on the optimizer being used.

Therefore, after reading this book, you should be able, in principle:

Reading guide

This book, short but dense (beware!), is actually a collection of studies related to the question “How can optimizers be reliably compared?”. As such, chapters can be read almost independently of each other. It is, however, advisable to start with the chapter of definitions, some not being completely conventional.

Based on your knowledge of the subject and your areas of interest, it is thus possible, for example, to directly consult Chapter 6, even if, for the very last section, it is necessary to have previously studied a difficulty measure presented in Chapter 2.

Similarly, if you are a practitioner especially curious to see how “customized” landscapes can be created, Chapter 4 on the LandGener program is right for you. On the contrary, the chapter on the typology of landscapes (Chapter 3), full of mathematical formulas, may appear to be rather boring and one could just browse the conclusions, or even ignore it completely.

And, of course, the various sections of the appendix are even more independent and non-essential, despite the fact that they can provide useful information, such as examples of deceptive functions and small codes sources. Regarding the latter, in fact, it should be noted that the main ones are not given here but may be downloaded (see www.iste.co.uk/clerc/iterative.zip).

More comprehensively, here are some observations on each chapter (Excluding the Appendix):

  • – Chapter 1: “Some definitions”. The most important ones are those concerning basins, plateaus and structures, but if readers intend to avoid Chapter 3, it is alternatively possible, as a first step, to skip this chapter and to merely consider intuitive notions.
  • – Chapter 2: “Difficulty of the difficulty”. The difficulty measures that will then be used almost everywhere are defined here. This is therefore a chapter to be almost necessarily read.
  • – Chapter 3: Landscape typology”. One to be skipped if the reader is allergic to combinatorial computations. Nonetheless, it might prove useful to take a look at the findings.
  • – Chapter 4: “LandGener”. It is essentially the presentation of principles allowing for the “customized” creation of landscapes – and, therefore, of test cases – with a few examples.
  • – Chapter 5: “Test cases”. Critical analysis of two sets of conventional test cases. It is made according to the typology seen in Chapter 3, but it is not really necessary to have read the latter if the reader trusts its conclusions!
  • – Chapter 6: “Difficulty vs dimension”. A small study around the notion, not always correct, that the difficulty increases with the dimension (the number of variables) of the problem.
  • – Chapter 7: “Exploitation and exploration vs difficulty”. In fact, this chapter and the next one form a whole. Exploitation and exploration concepts, often merely qualitative, are formally defined and measurable. The possible evolutions of their ratios (balance profiles) are studied.
  • – Chapter 8: “The Explo2 algorithm”. As an example, it is shown that it is possible to write a small optimizer explicitly using a predefined balance profile and that it is relatively effective despite being greedy in computational time. This is probably the chapter most likely to incur successful developments.
  • – Chapter 9: “Balance and perceived difficulty”. Slightly heterogeneous, but the two experimental studies that it contains are too short to justify specific chapters. One concerns the impact of the profile balance on performance, and the other makes it possible to insist on the fact that a difficulty measure only gives an ordering relation on a set of problems, without prejudice to quantitative differences between the difficulties actually collected by a given optimizer.