Genetic algorithm formulation and tuning with use of test functions_2

2025-04-29 0 0 687KB 10 页 10玖币

Genetic algorithm formulation and tuning with use of test functions

Tomasz Tarkowski

Chair of Complex Systems Modelling, Institute of Theoretical Physics,

Faculty of Physics, University of Warsaw, Pasteura 5, PL-02093 Warszawa, Poland

Abstract

This work discusses single-objective constrained genetic algorithm with ﬂoating-point, integer, binary and permutation representation.

Floating-point genetic algorithm tuning with use of test functions is done and leads to a parameterization with comparatively outstanding

Introduction

The idea of application of biological evolution [

] and genetic [

] principles to the optimization problems was ﬁrst sketched by Alan Turing in

his 1948 essay titled

Intelligent Machinery

[

] and later extended by himself [

] to a technique which is now called

genetic programming

[

These works were the very beginning of the

evolutionary computations

(EC)—ﬁeld of computer science devoted to the population-based,

trial-and-error methods of problem solving. One of the ﬁrst EC performed on a computer were done by Nils A. Barricelli in 1953 at the

Institute for Advanced Study at Princeton, NJ [

] on a machine built by John von Neumann’s group [

]. Nowadays, EC ﬁeld consists of many

subﬁelds—one of them is genetic algorithm (GA) approach [8], subject of this work.

1 Genetic algorithm

1.1 Genotype and its representation

Genotype g

is a ﬁnite polymorphic list of Boolean, real or integer values called

genes

[

]. More precisely,

g∈X0× ··· × Xc−1=Îc−1

i=0 Xi

where

is equal to

Â = {false,true}

or is bounded subset of set of real numbers

or integer numbers

. This work considers subsets of

kind of intervals of type

[a,b]

[a,b]Ú≡{k∈Ú|a≤k≤b}

. Despite the fact that

a priori

every gene in genotype can be of dierent

type, it is common practice to employ genotypes with pure

representation

binary

(

g∈Âc

ﬂoating-point

(

g∈Òc

) or

integer

(

g∈Úc

)

[10]. Otherwise, the representation is called mixed and is out of scope of this work.

Proper genotype for given optimization problem can have some additional constraints,

g∈G⊆Îc−1

i=0 Xi

. The

set can be arbitrary

subset of

Îc−1

i=0 Xi

, i.e. constraints imposed on dierent genes can be dierent and constraints for given gene can depend on values

of all other genes. However, if

G=Xc

, then genotype is called

uniform

. Moreover,

can be deﬁned as an extension of predicate

Q:Îc−1

i=0 Xi→Â

, i.e.

G={(x0, . . . , xc−1) ∈ Îc−1

i=0 Xi|Q(x0, . . . , xc−1)}

. One can deﬁne

permutation representation

, where

G={(x0, . . . , xc−1) ∈ {0, . . . , c−1}c|[i,j:xi,xj}, i.e. it is extension of permutation condition predicate.

Value

, i.e. domain dimension of

Îc−1

i=0 Xi

, is called

genotype length

(or

size

), while position in genotype is called

locus

(pl.

loci

), so if

genotype is of length cthen locus belongs to the set {0, . . . , c−1} ≡ ιc(notation inspired by the APL language [11]).

1.2 Population and sequence of populations

Sequence of genotypes of length µ:

(gi)µ−1

i=0 ∈ ιµ→

c−1

i=0

Xi!≡Pµ

X0,...,Xc−1⊂

+∞

µ=0

Pµ

X0,...,Xc−1≡P∗

X0,...,Xc−1(1)

is called

population

or, in context of evolutionary step,

generation

while

Pµ

X0,...,Xc−1

and

P∗

X0,...,Xc−1

are sets of all possible populations of

genotypes formulated basing on domain

Îc−1

i=0 Xi

with length

or arbitrary (including zero), respectively. Zero-length population is marked

with the symbol .

Notion of population is insucient to describe the evolutionary process, though—it is necessary to make one step further and deﬁne

sequence of populations:gi,jµ(j)−1

i=0 ν−1

j=0 ∈ιν→P∗

X0,...,Xc−1≡P∗ν

X0,...,Xc−1⊂∞

ν=0

P∗ν

X0,...,Xc−1≡P∗∗

X0,...,Xc−1(2)

gi,jµ−1

i=0 ν−1

j=0 ∈ιν→Pµ

X0,...,Xc−1≡Pµν

X0,...,Xc−1⊂∞

ν=0

Pµν

X0,...,Xc−1≡Pµ∗

X0,...,Xc−1(3)

Pµν

X0,...,Xc−1⊂P∗ν

X0,...,Xc−1(4)

Pµ∗

X0,...,Xc−1⊂P∗∗

X0,...,Xc−1(5)

arXiv:2210.03217v1 [cs.NE] 6 Oct 2022

where

Pµν

X0,...,Xc−1

is set of all possible sequences of length

of populations of length

. Replacement of

to the star symbol (

∗

) means

all possible values of given parameter, e.g. P∗ν

X0,...,Xc−1is set of all sequences of length νof populations of arbitrary length.

Notation

P∗

X0,...,Xc−1

and

P∗∗

X0,...,Xc−1

are inspired by Kleene closure, but it is not equivalent to it, because— according to Kleene algebra

[

]—double application of Kleene star is equivalent to single application and here

P∗

X0,...,Xc−1,P∗∗

X0,...,Xc−1

, i.e. population concatenation

does not occur automatically. To concatenate populations one can use ﬂatten (

ﬂat

, i.e. Italian

bemolle

)

[:P∗∗

X0,...,Xc−1→P∗

X0,...,Xc−1

function:

[gi,jµ(j)−1

i=0 ν−1

j=0

=g0,0, . . . , gµ(0)−1,0, . . . , . . . , . . . , g0,ν−1, . . . , gµ(ν−1)−1,ν−1(6)

1.3 Fitness function

Set of genotypes is by itself not very useful if there is no objective function to optimize over it, or—to put it dierently—if there is no

optimization problem to solve. In GA ﬁeld, the term

ﬁtness function

is used and common practice is to deﬁne the problem in such a way, that

this function is maximized. Fitness function, that is

f:G→Ò

, represents given maximization problem, but it does not need necessarily be

formulated explicitly and calculation of its values might be costly. Fitness function ensures gradual enhancement of population “quality” in

evolutionary process. In

multi-objective GA

the ﬁtness function is extended to the so-called

cost function G→Òd

, where

d∈Î+

and this

function is able to maximize many, often competing, parameters simultaneously and solution of such problem has form of set called

Pareto

frontier [13]. This work, however, is devoted to d= 1 case.

1.4 Variation operators

The essence of metaheuristics is intelligent search of space of potential solutions with intention of ﬁnding the best one. In order to achieve

that in GA approach the mechanism of exploitation of successful genotypes’ genes is applied. This mechanism includes variation operator

dependent on representation, which is a function

vn,m:Vn,m

X0,...,Xc−1

, where

Vn,m

X0,...,Xc−1≡Pn

X0,...,Xc−1→Pm

X0,...,Xc−1

. Variation

vn,m

applied on

parents (gi)n−1

i=0

results in

ospring (hi)m−1

i=0

, where every element is called

child

. Application of variation on population will be denoted

with vn,m(gi)n−1

i=0 or similar.

There are three main cases of variation:

mutation

(or

unary variation

)

v1,1

and two

recombinations

(or

binary variations

)—

v2,1

(one

child) and

v2,2

(two children). Variations of other kinds are less often used and are out of the scope of this work. Variations can be composed

and are often used that way. For case of recombination and mutation the canonical composition is to ﬁrst apply recombination and

then the mutation. Mutation is in that case, using term taken from functional programming,

mapped

on every child obtained from the

recombination process, i.e.

mapnv1,1◦v2,n

, where in special case of operations on populations

mapn:V1,1

X0,...,Xc−1→Vn,n

X0,...,Xc−1

, i.e.

mapµv1,1(gi)µ−1

i=0 =v1,1(gi)µ−1

i=0 .

1.5 Probability distributions

Variations are often based on drawing procedure from some probability distribution. In this work normal

, uniform

and special case of

Bernoulli distributions B will be used—their deﬁnitions can be easily found in literature. Normal distribution with mean

and standard

deviation

is marked here

N(µ,σ)

(contrary to conventional form

N(µ,σ2)

). Uniform distribution has continuous form

U(a,b)

for

a,b∈Ò

, where values are drawn from closed interval

[a,b]

, and discrete form

U{a,b}

for

a,b∈Ú

a,b∈Â

, where values are drawn

from set [a,b]Úor {a,b}⊂Â, respectively. Furthermore, the following notation for drawing from set Xis also assumed:

U(X)=U(a,b) ⇔ X=[a,b]

U{a,b} ⇔ X=[a,b]Ú∨X={a,b}⊂Â(7)

For Bernoulli distribution B

(1,p)

the probability of drawing value

(equivalent to

true ∈Â

) equals to

. Value

(equivalent to

false ∈Â

)

can be drawn with probability 1−p.

1.6 Examples of mutation operators

•Gaussian mutation

is a ﬂoating-point variation having two parameters:

σ∈Ò+

and

p∈ [0,1]

. Variation of each gene in a given

genotype occurs with probability

and consists of addition of a value

σ· N(0,1)

. In case where such mutation was to move

locus i

gene value out of constraints imposed by Xiset, the inf Xior sup Xivalue is used instead.

•Swap mutation

is an uniform genotype variation, where for genotype of size

it consists of swapping values of two genes with

loci

drawn from U(ιc).

•Random-reset mutation

is a binary, ﬂoating-point and integer variation having one parameter

p∈ [0,1]

. Each gene of a given

genotype is changed with probability p∈ [0,1]and variation of gene locus iconsists of assigning new value drawn from U(Xi).

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

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

10 玖币 0人已下载

立即下载

摘要：

GeneticalgorithmformulationandtuningwithuseoftestfunctionsTomaszTarkowskiChairofComplexSystemsModelling,InstituteofTheoreticalPhysics,FacultyofPhysics,UniversityofWarsaw,Pasteura5,PL-02093Warszawa,PolandAbstractThisworkdiscussessingle-objectiveconstrainedgeneticalgorithmwithoating-point,integer,bin...

展开>> 收起<<

Genetic algorithm formulation and tuning with use of test functions_2.pdf

共10页,预览2页

还剩页未读，继续阅读

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

Genetic algorithm formulation and tuning with use of test functions_2

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: