Study of the Fractal decomposition based metaheuristic on low-dimensional Black-Box optimization problems

2025-05-02 0 0 4.32MB 14 页 10玖币

侵权投诉

Study of the Fractal decomposition based

metaheuristic on low-dimensional Black-Box

optimization problems

Arcadi Llanza, Nadiya Shvai, Amir Nakib

Université Paris Est Créteil, Laboratoire LISSI, Vitry Sur Seine, France

Vinci autoroutes, Cyclope.ai, Paris, France

October 28, 2022

Abstract

This paper analyzes the performance of the Fractal Decomposition Al-

gorithm (FDA) metaheuristic applied to low-dimensional continuous opti-

mization problems. This algorithm was originally developed speciﬁcally to

deal eﬃciently with high-dimensional continuous optimization problems

by building a fractal-based search tree with a branching factor linearly

proportional to the number of dimensions. Here, we aim to answer the

question of whether FDA could be equally eﬀective for low-dimensional

problems. For this purpose, we evaluate the performance of FDA on the

Black Box Optimization Benchmark (BBOB) for dimensions 2, 3, 5, 10,

20, and 40. The experimental results show that overall the FDA in its

current form does not perform well enough. Among diﬀerent function

groups, FDA shows its best performance on Misc. moderate and Weak

structure functions.

1 Introduction

The general form of an optimization problem considered in this paper is deﬁned

by Eq. 1:

Minf(~x), s.t. ~

Bl≤~x ≤~

Bu(1)

where f(~x)denotes the function to be minimize. It is assumed to be con-

tinuous. ~x = (x1, x2, ..., xD)is the variable vector in RD. Here, ~x is a given

parameter. Moreover, the function is constrained by ~

Bl= (Bl1, Bl2, ..., BlD)as

the lower boundary and ~

Bu= (Bu1, Bu2, ..., BuD)as the upper boundary.

The Fractal Decomposition Algorithm (FDA) is a deterministic metaheuris-

tic method that has been shown to solve large scale (50 up to 1000 dimensions)

continuous optimization problems with high-performance [11], [12]. This re-

search aims to benchmark, for the ﬁrst time, FDA in a low-dimensional (5 up

to 40 dimensions) constrained continuous optimization problem such as Black

Box Optimization Benchmark (BBOB) [6].

In this paper, the Black Box optimization refers to the design and analysis

of algorithms for problems where the structure of the objective function is un-

known and unexploitable. The rest of the paper is organized as follows. First,

arXiv:2210.15489v1 [cs.NE] 16 Oct 2022

Section 2 reviews the related work. Then, Section 3 examines the foundations

of the proposed method DFDA. Afterwards, Section 4 describes the used bench-

mark. Section 5 presents the experiments and results. Finally, in Section ??

the conclusion and further research directions are presented.

2 Related work

To our knowledge, no other study has been previously done on FDA perfor-

mance for low-dimensional continuous optimization problems. In the original

FDA paper [11], the benchmark considered was SOCO2011. The problem di-

mension was set to a range of values from 50 to 1000. FDA ranked ﬁrst for each

considered.

An overview of state-of-the-art (SOTA) methods for the BBOB benchmark

is provided. The methods are reported in order of their average performance

from best to worst. In the case of noiseless BBOB, generally, it is Evolu-

tionary Algorithms (EAs) that perform better. Nevertheless, Local Searches

(LS) and other hybrid methods are competitive as well. Hansen et al. pro-

posed in [5] a multistart BI-population CMA-ES with equal budgets for two

interlaced restart strategies, one with increasing population size and one with

varying small population sizes. In [2], Bosman et al. introduced the Adapted

Maximum-Likelihood Gaussian Model Iterated Density-Estimation Evolution-

ary Algorithm (AMaLGaM-IDEA). AMaLGaM-IDEA is a parameter-free algo-

rithm with incremental model building (iaMaLGaM IDEA). MA-LS-Chain [10]

was proposed by Molina et al.. It uses a memetic algorithm with continuous lo-

cal search. The Variable Neighbourhood Search (VNS) was suggested by Garcia

et al. in [3]. IPOP-SEP-CMA-ES [15] is an algorithm with a multistart strategy

with increasing population size introduced by Ros et al.

The Age-Layered Population Structure (ALPS) Evolutionary Algorithm (EA)

is a method presented by Hornby et al. in [7]. ALPS claims to avoid premature

convergence than other EAs methods.

The Prototype Optimization with Evolved Improvement Steps (POEMS)

was introduced by Kubalik et al. in [9]. POEMS is a stochastic local search-

based algorithm.

The restarted estimation of distribution algorithm (EDA) with Cauchy dis-

tribution (Cauchy-EDA) probabilistic model was suggested by Povsik et al. in

[13]. Cauchy-EDA claims to be usable for many ﬁtness landscapes. On the

contrary, EDA with Gaussian distribution tends to converge prematurely.

The Diﬀerential Ant-Stigmergy Algorithm (DASA) was presented in [8] by

Korovsec et al. DASA is a stigmergy-based algorithm for solving optimization

problems with continuous variables.

Hansen et al. analysed the Nelder-Mead downhill simplex method [5]. Nelder-

Mead is a multistart strategy applied on local and global levels. On the one

hand, at the local level, ten restarts are conducted with a small number of iter-

ations and reshaped simplex. On other hand, at the global level, independent

restarts are launched until 105D function evaluations are exceeded.

3 The Fractal decomposition based Algorithm

Nakib et al. introduced a fractal decomposition [11] based on hyperspheres to

solve high dimensional continuous optimization problems with low complexity.

FDA [11] uses two components to ﬁnd the optimain the landscape: the First

component, called fractal decomposition, is used as an exploration technique.

Then, the second component, called Intensive Local Search (ILS), is used as

the exploitation technique to search in the local regions previously identiﬁed as

promising regions. The basic pattern used in the fractal decomposition is a hy-

persphere because when scaled into a high dimensional space, its computational

complexity is low. FDA covers the space with few hyperspheres allowing it to

obtain a good performance in its exploratory phase. An inﬂation procedure is

applied to the hyperspheres (see Fig. 1) to ensure that all space is covered.

Figure 1: Hypersphere fractal decomposition at 4 levels of depth [11].

The following subsection is dedicated to the diﬀerent FDA components.

3.1 Exploration component

At this phase, promising regions are searched for by conveniently subdividing

the search space into smaller regions that might contain a good solution. The

partition of space is modeled after a form of a hypersphere. This shape is a

suitable representation that allows FDA to be extremely competitive in large-

scale spaces.

Given a center Ckof a hypersphere with radius rthe centers of its decom-

position can be obtained as in Eq. 2:

k+1 =Ck+ (−1)i·((r−r0)e[i+1

2])(2)

Then, the quality of each generated hypersphere is evaluated based on two

points −→

s1and −→

s2originated based on Eq. 3.

−→

s1=−→

Cl+αrl

√D×−→

ed,for d= 1,2, . . . , D

−→

s2=−→

Cl−αrl

√D×−→

ed,for d= 1,2, . . . , D (3)

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

StudyoftheFractaldecompositionbasedmetaheuristiconlow-dimensionalBlack-BoxoptimizationproblemsArcadiLlanza,NadiyaShvai,AmirNakibUniversitéParisEstCréteil,LaboratoireLISSI,VitrySurSeine,FranceVinciautoroutes,Cyclope.ai,Paris,FranceOctober28,2022AbstractThispaperanalyzestheperformanceoftheFractalDecom...

展开>> 收起<<

Study of the Fractal decomposition based metaheuristic on low-dimensional Black-Box optimization problems.pdf

共14页,预览3页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

Study of the Fractal decomposition based metaheuristic on low-dimensional Black-Box optimization problems

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: