A N OVEL MULTI -OBJECTIVE VELOCITY -FREE BOOLEAN PARTICLE SWARM OPTIMIZATION Wei Quan

2025-04-27 0 0 549.54KB 10 页 10玖币

侵权投诉

A NOVEL MULTI-OBJECTIVE VELOCITY-FREE BOOLEAN

PARTICLE SWARM OPTIMIZATION

Wei Quan

Dept. of Computer Science

University College London

London, UK

erinquan0521@gmail.com

Denise Gorse

Dept. of Computer Science

University College London

London, UK

d.gorse@cs.ucl.ac.uk

ABSTRACT

This paper extends boolean particle swarm optimization to a multi-objective setting, to our knowledge

for the ﬁrst time in the literature. Our proposed new boolean algorithm, MBOnvPSO, is notably

simpliﬁed by the omission of a velocity update rule and has enhanced exploration ability due to

the inclusion of a “noise” term in the position update rule that prevents particles being trapped in

local optima. Our algorithm additionally makes use of an external archive to store non-dominated

solutions and implements crowding distance to encourage solution diversity. In benchmark tests,

MBOnvPSO produced high quality Pareto fronts, when compared to benchmarked alternatives, for

all of the multi-objective test functions considered, with competitive performance in search spaces

with up to 600 discrete dimensions.

Keywords Binary PSO ·Boolean PSO ·Multi-objective optimization ·Velocity-free

1 Introduction

There are many real-world discrete optimization problems in both single and multi-objective settings, for example in

electrical engineering [

] [

] and feature selection [

], and therefore a need for efﬁcient and versatile algorithms that

can solve such problems. Particle swarm optimization (PSO) [

] and genetic algorithms (GAs) are both biologically

inspired, effective algorithms, with discrete single and multi-objective variants; however, PSO has been shown to be less

computationally demanding than GAs [

]. In this work we propose MBOnvPSO, a new, boolean PSO for application to

multi-objective optimization problems such as feature selection [

], a boolean (natively binary) approach being both

efﬁcient (as noted in [

]) and of potential value in facilitating a hardware implementation. To our knowledge there have

been no previous presentations of multi-objective boolean PSOs. This will be the primary novel contribution of our

work.

Our second contribution will be to add to the evidence [

] [

] that PSOs operating in a discrete search space may ﬁnd

good solutions more easily without a traditional velocity update rule, particularly for multi-objective problems, as

evidenced in [

]. Velocity-free algorithms appear superior in this sense. Our MBOnvPSO algorithm, in which “nv”

denotes “no velocity”, was inspired by the velocity-free binary PSO of [

], though with substantial differences (in

addition to being boolean rather than binary) relating to how both integral and additional exploration are carried out. As

will be seen later, MBOnvPSO has proved very effective when compared to the benchmarked alternatives, including a

multi-objective variant of [7].

2 Background and related work

2.1 Continuous, binary, and boolean PSO

PSO was ﬁrst introduced in Kennedy and Eberhart [

]. It is a nature-inspired population-based search algorithm

modelled after the ﬂocking behavior of birds and other animals. The PSO optimization process, for the

th particle, is

arXiv:2210.05882v1 [cs.NE] 12 Oct 2022

A Novel Multi-Objective Velocity-Free Boolean Particle Swarm Optimization

guided by cognitive (via a personal best position vector,

and social (via a global best,

) inﬂuences, and deﬁned, for

an N-dimensional search space, by the velocity and position update rules

vt+1

i=wvt

i+c1r1(pt

i−xt

i) + c2r2(gt−xt

i),(1)

xt+1

i=xt

i+vt+1

i,(2)

in which

is the best parameter position found at time

by particle

the best position found by any particle,

and

are positive constants most often set to 2.0 [

and

are random numbers

∈[0,1]

, and

is a usually

iteration-decreasing “inertia weight” that controls the extent to which new search directions are pursued. It is also

usually recommended to clip the velocity to a maximum magnitude

Vmax

so that the search remains within useful

bounds.

The update equations (1), (2) assume a continuous search space. However, Kennedy and Eberhart also proposed a

binary PSO (BPSO) [

], in which to generate an updated binary position, velocities are transformed into

[0,1]

by a

sigmoid transfer function

sig()

, with

P rob(xij = 1) = sig(vij )

. The vast majority of later BPSOs have retained the

concept of velocity, as well as the use of a transfer function to generate the velocity update. However, simpler BPSOs,

without a velocity update rule, have proven to be equally, if not more, effective [

] [

], a central theme of this current

work.

An alternative to the use of BPSOs in a discrete space is the boolean PSO of [

], which eliminates problems such as the

velocity, in BPSO, not being associated with the likelihood of a change in position. Boolean PSO considers all variables

to be binary and all arithmetic operators to be logical operators, with velocity and position update equations

vt+1

i=w.vt

i+r1.(pt

i⊕xt

i) + r2.(gt⊕xt

i),(3)

xt+1

i=xt

i⊕vt+1

i,(4)

where “.” is the AND operator, “+” the OR operator, "

⊕

" the XOR operator (all operators being applied bitwise),

and where

P rob(r1= 1) = ρ1

P rob(r2= 1) = ρ2

P rob(w= 1) = ω

. We note that

Vmax

is now deﬁned as the

maximum number of velocity bits allowed to ﬂip from 0 to 1 or 1 to 0.

There have been a number of applications of boolean single-objective PSO in electrical engineering that demonstrate its

simplicity and computational efﬁciency, such as its application to antenna design in [

] and [

]. Outside of electrical

engineering, a single-objective boolean PSO was used in [

] for feature selection, with encouraging results that suggest

a multi-objective variant, such as we propose here, might be an effective way forward in this area.

2.2 Multi-objective optimization

Unlike single-objective problems, multi-objective problems have conﬂicting objectives [

]. It is therefore necessary to

obtain a non-dominated solution set, based on Pareto dominance, because no single solution can be considered ideal

with respect to all objectives. The non-dominated set of the entire solution space is termed the Pareto-optimal set, and

the boundary of this region is termed the Pareto-optimal front. Multi-objective PSO (MOPSO) was ﬁrst proposed in

[

], using Pareto dominance during the ﬁtness evaluation stage. MOPSO then stores the non-dominated solutions

produced by each particle in an external global best repository, the repository helping each particle to select a global

best guidance during the search process.

3 Benchmarked algorithms

This section will brieﬂy describe each of the algorithms used for benchmarking, summarized in Table 1. We note that

examples of binary MOPSOs are relatively few, and that examples of boolean MOPSOs are limited to the current work.

Hence, some benchmarks will be ﬁrst uses of the underlying single-objective PSO in a multi-objective setting.

3.1 Boolean benchmark

As previously noted, there have been no previous examples of a boolean multi-objective PSO in the literature. However,

it is possible to extend a single-objective boolean algorithm to the multi-objective domain. For this purpose, we choose

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

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

10 玖币 0人已下载

立即下载

摘要：

ANOVELMULTI-OBJECTIVEVELOCITY-FREEBOOLEANPARTICLESWARMOPTIMIZATIONWeiQuanDept.ofComputerScienceUniversityCollegeLondonLondon,UKerinquan0521@gmail.comDeniseGorseDept.ofComputerScienceUniversityCollegeLondonLondon,UKd.gorse@cs.ucl.ac.ukABSTRACTThispaperextendsbooleanparticleswarmoptimizationtoamulti-o...

展开>> 收起<<

A N OVEL MULTI -OBJECTIVE VELOCITY -FREE BOOLEAN PARTICLE SWARM OPTIMIZATION Wei Quan.pdf

共10页,预览2页

还剩页未读，继续阅读

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

A N OVEL MULTI -OBJECTIVE VELOCITY -FREE BOOLEAN PARTICLE SWARM OPTIMIZATION Wei Quan

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: