A Note on Multi-Funnel Functions for Expensive
Optimization Scenario
Ryoji Tanabe
Graduate School of Arts and Sciences
The University of TokyoTokyo, Japanrt.ryoji.tanabe@gmail.com
ABSTRACT

G.1.6 [Mathematics of Computing]: Optimization—Global optimization; I.2.8 [Artificial Intelligence]: Problem
Solving, Control Methods, and Search—Heuristic methods

The previous work [6] showed that CMA-ES struggle tosearch the optimal solution for multi-funnel functions forcheap scenario where EA can utilize a relatively large computational budget. In contrast, for expensive scenario where
only a small computational budget can be used for the search,
EA might be not able to obtain the local optimal solution
in a suboptimal basin and is not affected multi-funnel structure. Since the fraction of the search space that an EA canexplore depends on the available computational budget, theproblem characteristics might differ whether a budget scenario is an expensive scenario (e.g. MaxEvals = 102 ×D) or acheap scenario (e.g. MaxEvals = 104 × D). To clarify above
issues, this paper presents an empirical analysis of multifunnel functions for expensive/cheap computational budgets
scenario using Fitness Distance Correlation (FDC) [4].

1.

2. FITNESS DISTANCE CORRELATIONThis paper presents an characteristic analysis of multi-funnel
functions for expensive computational budgets. IPOP-CMAES is applied to three multi-funnel functions from the BBOB
benchmarks for two different budget scenarios. The experimental analysis using Fitness Distance Correlation (FDC)shows that search spaces of IPOP-CMA-ES in multi-funnel
functions significantly differ depending on the maximum number of fitness evaluations.

Categories and Subject Descriptors

INTRODUCTION

Some real-world applications of Evolutionary Algorithms(EA) require executing a very expensive simulations (up to10 minutes/run) in order to evaluate the fitness of a single
individual. Thus, in recent years, there has been much research on such expensive optimization problems, where onlya small computational budget can be used for the search.
The real parameter optimization benchmark problems forevaluating the search performance of EA for expensive optimization problem have recently been proposed. Typicalbenchmark suites are the BBOB benchmarks [3] for expensive scenario1 and the CEC2014 expensive optimization
benchmarks [5]. However, these benchmarks consist of thewidely used functions and maximum number of fitness evaluations (MaxEvals) is merely set to small limited number (e.g.
MaxEvals = 102 × D, where D is the benchmark problemdimensionality). Thus, an suitability of these benchmarks
might be open to question.
In this paper, we consider muti-funnel functions, whichhave a high deceptive structure and are considered as EAhard problems, for expensive computational budget scenario.
1

http://coco.gforge.inria.fr/doku.php?id=bbob-2013

Permission to make digital or hard copies of all or part of this work for personal orclassroom use is granted without fee provided that copies are not made or distributedfor profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others thanACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission
and/or a fee. Request permissions from permissions@acm.org.
GECCO’15, July 11-15, 2015, Madrid, Spain.
Copyright 2015 ACM TBA ...$15.00.

FDC [4] is a landscape analysis method which analyzes
the correlation between f (x), the fitness of a D-dimensional
solution vector x = (x1 , ..., xD ) and d(x, x∗ ), the distance
between x and the optimal solution vector x∗ . Euclidean
distance is a general distance metric d(·, ·) for real parameter
optimization problem. The global structure (e.g. singlefunnel or multi-funnel structure) of a given problem can beunderstood by analyzing the correlation between f (x) andd(x, x∗ ).
While the FDC can be visualized by using a 2-D plot off (x) (vertical axis) and d(x, x∗ ) (horizontal axis), as shownin Figure 1, following rFDC metric [4] isPused for a quantita¯tive analysis: rFDC = cF D , cF D = 1 n (fi − f¯)(di − d).
sF sD

ni=1

Where n is the number of sampled solution vectors {x1 , ...,xn }, fi and di are the fitness and distance (from x∗ ) of the i¯ sF , sD are the means andth vector xi (1 ≤ i ≤ n), and f¯, d,standard deviations of fitness values and distances, respectively. As rFDC approaches 1, the search space has a more
pronounced big valley structure, which is an easy problem
for EA. On the other hand, rFDC closes to 0 indicates thatthe global structure is a weak or none, and a negative valueof rFDC indicates a deceptive structure.

3. EXPERIMENT RESULTS
To analyze characteristics of multi-funnel functions, weapply IPOP-CMA-ES2 [1] to the 10-dimensional f21 , f22 andf24 from the BBOB benchmarks [3] for two different budged
2We conducted the same experiments for DE and PSO, but
the obtained results are very similar to the IPOP-CMA-ESresults shown in Figure 1.

MaxEvals = 104 × D

100rF DC = 0.9480Error values

80

Error values

MaxEvals = 102 × D

100rF DC = 0.21

60

4060

40

20

2000510150020

Euclidean Distances from xbsf

246810121416

Euclidean Distances from xbsf(a) f21100MaxEvals = 104 × D

100rF DC = 0.5880

Error values

Error values

8060402000MaxEvals = 102 × D

rF DC = 0.96

604. DISCUSSION AND CONCLUSION

4020510150020

Euclidean Distances from xbsf

2468101214

Euclidean Distances from xbsf(b) F22800

400rF DC = 0.69

350

600

Error values

Error values

700

MaxEvals = 104 × D

500
400
300
200
10000MaxEvals = 102 × D

rF DC = 0.82300
25020015010050

5101520

Euclidean Distances from xbsf

00

computational budget, IPOP-CMA-ES can only find a funnel on the result of f21 for expensive scenario. This result isalso shown in f24 having the double-funnel landscape. While
we can see clear two valleys of f24 for cheap scenario (Figure1(c) left), only a valley can be seen for expensive scenario(Figure 1(c) right).
The rF DC values for expensive scenario tend to be higher
than those for cheap scenario. Especially, the rF DC values
in f21 , f22 for expensive scenario are 0.94 and 0.96 respectively. This means that f21 and f22 are almost the same assingle funnel function having high fitness-distance correlation. This observation is significantly incompatible with theoriginal function properties of f21 and f22 .

24681012

Euclidean Distances from xbsf(c) f24
Figure 1: Figures (a) – (c) show the FDC for the 10-dimensional
f21 , f22 and f24 from the BBOB benchmarks respectively. Solutions generated by IPOP-CMA-ES and corresponding error values in the best run out of 25 runs are plotted. The medianrF DC values are also shown in the figures. The horizontal axis
represents the Euclidean distance between x and the best-so-far
solution xbsf , and the vertical axis represents the error valueof x (lower is better). Left and right figures show the results
for cheap scenario (MaxEvals= 104 × D) and expensive scenario(MaxEvals= 102 × D) respectively.

In Section 3, we confirmed that the search spaces of IPOPCMA-ES in multi-funnel functions significantly differ depending on the available computational budgets. This results demonstrate that the current BBOB benchmarks might
be inappropriate for evaluating the performance of EA for
solving expensive optimization problem. The search performance of IPOP-CMA-ES might be invariant whether agiven function has the single-funnel/multi-funnel structure
for expensive scenario. This misleads the compared results
among the different algorithms. Let us consider evaluating method A and method B for a single-funnel function(e.g. Rastrigin function) and a multi-funnel function (e.g.
Double-Rastrigin function) for expensive scenario. Due toabove reason, he/she might incorrectly conclude as: “Forexpensive scenario, the method A perform better than themethod B independent from the global structure”.
To avoid this incorrect conclusion, following two directions can be considered as our future works: (1) eliminating benchmark functions having unexpected rF DC values or
shapes such as f21 , f22 and f24 from a benchmark set, (2)designing new benchmark functions for expensive scenario.

Acknowledgments
This work was supported by JSPS KAKENHI Grants 269528.
We thank Alex Fukunaga for helpful discussions.

5. REFERENCES
2

scenarios: expensive scenario (MaxEvals = 10 × D) andcheap scenario (MaxEvals = 104 × D). f21 and f22 are generated by using MSG function generator [2] and have 101
and 21 peaks respectively. f24 is designed by using doublefunnel function generator proposed by Lunacek et al [6] andhas two funnels. For IPOP-CMA-ES, we used the control
parameter values that were suggested in [1]. On each problem, IPOP-CMA-ES is executed 25 times with same function
instance.
Figure 1 shows the FDC scatter plots and the rF DC values for IPOP-CMA-ES. Note that the best-so-far solution
xbsf is used for the FDC analysis instead of the optimal
solution x∗ since our interest is not problem itself such as
traditional landscape analysis studies, but search spaces ofEA. The shapes of their FDC scatter plots are significantly
different depending on budget scenario. For cheap scenario,
IPOP-CMA-ES can clearly find out the global structure. For
instance, three funnels can be seen on the result of f21 forcheap scenario (Figure 1(a) left). In contrast, due to a small[1] A. Auger and N. Hansen. A restart cma evolution
strategy with increasing population size. In IEEE CEC,pages 1769–1776, 2005.
[2] M. Gallagher and B. Yuan. A General-Purpose Tunable
Landscape Generator. IEEE Trans. Evol. Comput.,
10(5):590–603, 2006.
[3] N. Hansen, S. Finck, R. Ros, and A. Auger.
Real-parameter black-box optimization benchmarking
2009: Noiseless functions definitions. Technical Report
RR-6829, INRIA, 2009. Updated February 2010.
[4] T. Jones and S. Forrest. Fitness distance correlation asa measure of problem difficulty for genetic algorithms.
In ICGA, pages 184–192, 1995.
[5] B. Liu, Q. Chen, Q. Zhang, J. J. Liang, P. N.
Suganthan, and B. Y. Qu. Problem Definitions andEvaluation Criteria for Computational Expensive
Optimization. Technical report, 2014.
[6] M. Lunacek, D. Whitley, and A. Sutton. The impact ofglobal structure on search. In PPSN, pages 498–507,2008.