Engelbrecht Andries P. Computational Intelligence: An Introduction

Подождите немного. Документ загружается.

568 A. Optimization Theory

In the evolutionary computation literature, multi-solution algorithms are referred to

as niching or speciation algorithms.

A.7.2 Niching Algorithm Categories

Niching algorithms can be categorized based on the way that niches are located. Three

categories are identiﬁed:

• Sequential niching (or temporal niching) develops niches over time. The pro-

cess iteratively locates a niche (or optimum), and removes any references to it

from the search space. Removal of references to niches usually involves mod-

iﬁcation of the search space. The search for, and removal of niches continues

sequentially until a convergence criterion is met, for example, no more niches

can be obtained over a number of generations.

• Parallel niching locates all niches in parallel. Individuals dynamically self-

organize, or speciate, on the locations of optima. In addition to locating niches,

parallel niching algorithms need to organize individuals such that they maintain

their positions around optimal locations over time. That is, once a niche is

found, individuals should keep grouping around the niche.

• Quasi-sequential niching locates niches sequentially, but does not change the

search space to remove the niche. Instead, the search for a new niche continues,

while the found niches are reﬁned and maintained in parallel.

Regardless of the way in which niches are located, a further categorization of niching

algorithms can be made according to speciation behavior [553]:

• Sympatric speciation, where individuals form species that coexist in the same

search space, but evolve to exploit diﬀerent resources. For example, diﬀerent

kinds of ﬁsh feed on diﬀerent food sources in the same environment.

• Allopatric speciation, where diﬀerentiation between individuals is based on

spatial isolation in the search space. There is no interspecies communication,

and subspecies can develop only through deviation from the available genetic

information (triggered by mutation). As an example, consider diﬀerent ﬁsh

species that live and play around their food sources, with no concern about the

existence of other species living in diﬀerent areas.

• Parapatric speciation, where development of new species is evolved as a result

of segregated species sharing a common border. Communication between the

original species may not have been encouraged or intended. For example, new

ﬁsh species may evolve based on the interaction with a small percentage of

diﬀerent schools of ﬁsh. The new species may have diﬀerent food requirements

and may eventually upset the environment’s stability.

A.8 Multi-Objective Optimization 569

A.7.3 Example Benchmark Problems

This section lists ﬁve easy functions to test niching algorithms. In addition to these,

any of the multi-modal functions listed in the previous chapters can be used.

Niching problem 1: Maximize

f(x)=sin

(5πx) (A.38)

for x ∈ [0, 1]. The solutions are located at x =0.1,x=0.3,x=0.5,x=0.7and

x =0.9.

Niching problem 2: Maximize

f(x)=



−2 log(2)×

(

x−0.1

0.8

)

× sin

(5πx) (A.39)

for x ∈ [0, 1]. The solutions are located at x =0.08,x=0.25,x=0.45,x=0.68

and x =0.93.

Niching problem 3: Maximize

f(x)=sin

(5π(x

3/4

− 0.05)) (A.40)

for x ∈ [0, 1]. The solutions are located at x =0.1,x=0.3,x=0.5,x=0.7and

x =0.9.

Niching problem 4: Maximize

f(x)=



−2 log(2)×

(

x−0.08

0.854

)

× sin

(5π(x

3/4

− 0.05)) (A.41)

for x ∈ [0, 1]. The solutions are located at x =0.08,x=0.25,x=0.45,x=0.68

and x =0.93.

Niching problem 5 (modified Himmelblau function): Maximize

f(x

) = 200 − (x

+ x

− 11)

− (x

+ x

− 7)

(A.42)

with x

∈ [−5, 5]. Maxima are located at (−2.81, 3.13), (3.0, 2.0),

(3.58, −1.85) and (−3.78, −3.28).

A.8 Multi-Objective Optimization

Many real-world problems require the simultaneous optimization of a number of ob-

jective functions. Some of these objectives may be in conﬂict with one another. For

example, consider ﬁnding optimal routes in data communications networks, where the

objectives may include to minimize routing cost, to minimize route length, to mini-

mize congestion, and to maximize utilization of physical infrastructure. There is an

important trade-oﬀ between the last two objectives: minimization of congestion is

570 A. Optimization Theory

achieved by reducing the utilization of links. A reduction in utilization, on the other

hand, means that infrastructure, for which high installation and maintenance costs

are incurred, is under-utilized.

This chapter provides a theoretical overview of multi-objective optimization (MOO),

focusing on deﬁnitions that are needed in later chapters. The objective of this chapter

is by no means to give a complete treatment of MOO. The reader can ﬁnd more

in-depth treatments in [150, 195]. Section A.8.1 deﬁnes the multi-objective problem

(MOP), and discusses the meaning of an optimum in terms of MOO. Section A.8.2

summarizes weight aggregation approaches to solve MOPs. Section A.8.3 provides

deﬁnitions of Pareto-optimality and dominance, and a lists a few example problems.

A.8.1 Multi-objective Problem

Let S⊆R

denote the n

-dimensional search space, and F⊆Sthe feasible space.

With no constraints, the feasible space is the same as the search space. Let x =

,...,x

) ∈S, referred to as a decision vector. A single objective function,

(x), is deﬁned as f

: R

→ R.Letf(x)=(f

(x),f

(x),...,f

(x)) ∈O⊆R

be an objective vector containing n

objective function evaluations; O is referred to as

the objective space. The search space, S is also referred to as the decision space.

Using the notation above, the multi-objective optimization problem is deﬁned as:

Definition A.10 Multi-objective problem:

minimize f(x )

subject to g

(x) ≤ 0,m=1,...,n

(x)=0,m= n

+1,...,n

+ n

x ∈ [x

min

, x

max

]

(A.43)

In equation (A.43), g

and h

are respectively the inequality and equality constraints,

while x ∈ [x

min

, x

max

] represents the boundary constraints. Solutions, x

∗

,totheMOP

are in the feasible space, i.e. all x

∗

∈F.

The meaning of an “optimum” has to be redeﬁned for MOO. In terms of uni-objective

optimization (UOO) where only one objective is optimized, a local optimum and global

optimum is as deﬁned in Section A.3. In terms of MOO, the deﬁnition of optimality

is not that simple. The main problem is the presence of conﬂicting objectives, where

improvement in one objective may cause a deterioration in another objective. For

example, maximization of the structural stability of a mechanical structure may cause

an increase in costs, working against the additional objective to minimize costs. Trade-

oﬀs exist between such conﬂicting objectives, and the task is to ﬁnd solutions that

balance these trade-oﬀs. Such a balance is achieved when a solution cannot improve

any objective without degrading one or more of the other objectives. These solutions

are referred to as non-dominated solutions, of which many may exist.

A.8 Multi-Objective Optimization 571

The objective when solving a MOP is therefore to produce a set of good compromises,

instead of a single solution. This set of solutions is referred to as the non-dominated

set,orthePareto-optimal set. The corresponding objective vectors in objective space

are referred to as the Pareto front. The concepts of dominance and Pareto-optimality

are deﬁned in the next section.

A.8.2 Weighted Aggregation Methods

One of the simplest approaches to deal with MOPs, is to deﬁne an aggregate objective

function as a weighted sum of the objectives. Uni-objective optimization algorithms

can then be applied, without any changes to the algorithm, to ﬁnd optimum solutions.

For aggregation methods, the MOP is redeﬁned as

minimize



k=1

(x)

subject to g

(x) ≤ 0,m=1,...,n

(x)=0,m= n

+1,...,n

+ n

x ∈ [x

min

, x

max

]

≥ 0,k =1,...,n

(A.44)

It is also usually assumed that



k=1

=1.

The aggregation approach does, however, have a number of problems:

• The algorithm has to be applied repeatedly to ﬁnd diﬀerent solutions if a single-

solution PSO is used. However, even for repeated applications, there is no guar-

antee that diﬀerent solutions will be found. Alternatively, a niching strategy can

be used to ﬁnd multiple solutions.

• Itisdiﬃculttogetthebestweightvalues,ω

, since these are problem-dependent.

• Aggregation methods can only be applied to generate members of the Pareto-

optimal set when the Pareto front is concave, regardless of the values of ω

[174, 422].

The second problem can be addressed by not using ﬁxed values, but to have these

weights change dynamically. The following two schemes can be used to dynamically

adjust the weights for two-objective problems [664, 665]:

• Bang-bang weighted aggregation:

(t) = sign(sin(2πt/τ))

(t)=1− ω

(t) (A.45)

where τ is the weights’ change frequency. Weights are changed abruptly due to

the use of sign in equation (A.45).

• Dynamic weighted aggregation:

(t)=|sin(2πt/τ)|

(t)=1− ω

(t) (A.46)

With this approach, weights change more gradually.

572 A. Optimization Theory

(x)

Dominated by f

Figure A.5 Illustration of Dominance

A.8.3 Pareto-Optimality

This section provides a number of deﬁnitions that are needed when talking about

MOO. Deﬁnitions include dominance, Pareto-optimal, Pareto-optimal front, and oth-

ers. These deﬁnitions assume minimization.

Definition A.11 Domination: A decision vector, x

dominates a decision vector,

(denoted by x

≺ x

), if and only if

• x

is not worse than x

in all objectives, i.e. f

) ≤ f

), ∀k =1,...,n

and

• x

is strictly better than x

in at least one objective, i.e. ∃k =1,...,n

: f

) <

Similarly, an objective vector, f

, dominates another objective vector, f

,iff

is not

worse than f

in all objective values, and f

is better than f

in at least one of the

objective values. Objective vector dominance is denoted by f

≺ f

From Deﬁnition A.11, solution x

is better than solution x

if x

≺ x

(i.e. x

dominates x

), which happens when f

≺ f

The concept of dominance is illustrated in Figure A.5, for a two-objective function,

f(x)=(f

(x),f

(x)). The striped area denotes the area of objective vectors dominated

by f.

Definition A.12 Weak domination: A decision vector, x

, weakly dominates a

decision vector, x

(denoted by x

 x

), if and only if

A.8 Multi-Objective Optimization 573

• x

is not worse that x

in all objectives, i.e. f

) ≤ f

), ∀k =1,...,n

Definition A.13 Pareto-optimal: A decision vector, x

∗

∈Fis Pareto-optimal

if there does not exist a decision vector, x = x

∗

∈Fthat dominates it. That is,

k : f

(x) <f

∗

). An objective vector, f

∗

(x), is Pareto-optimal if x is Pareto-

optimal.

The concept of Pareto-optimality is named after the mathematician Vilfredo Pareto,

who generalized this concept, ﬁrst introduced by Francis Ysidro Edgeworth.

Definition A.14 Pareto-optimal set: The set of all Pareto-optimal decision vectors

form the Pareto-optimal set, P

∗

. That is,

∗

= {x

∗

∈F| ∃x ∈F: x ≺ x

∗

} (A.47)

The Pareto-optimal set therefore contains the set of solutions, or balanced trade-oﬀs,

for the MOP. The corresponding objective vectors are referred to as the Pareto-optimal

front:

Definition A.15 Pareto-optimal front: Given the objective vector, f(x),andthe

Pareto-optimal solution set, P

∗

, then the Pareto-optimal front, PF

∗

⊆O, is defined

∗

= {f =(f

∗

),f

∗

),...,f

∗

))|x

∗

∈P} (A.48)

The Pareto front therefore contains all the objective vectors corresponding to decision

vectors that are not dominated by any other decision vector. An example Pareto front

is illustrated for the following functions in Figure A.6 [664, 665]:

• The convex, uniform Pareto front in Figure A.6(a) for MOP

f(x)=(f

(x),f

(x)) (A.49)

(x)=



j=1

(x)=



j=1

− 2)

• The convex, non-uniform Pareto front in Figure A.6(b) for MOP

f(x)=(f

(x),f

(x)) (A.50)

(x)=x

(x)=g(x)(1 −

(x)/g(x))

where

g(x)=1+

− 1



j=2

574 A. Optimization Theory

0.5

1.5

2.5

3.5

4.5

0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5

(a) Convex, Uniform Front for Equation

(A.49)

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

(b) Convex, Non-uniform Front for Equa-

tion (A.50)

-0.1

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1.1

-0.1 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 1.1

0.5

1.5

2.5

3.5

4.5

-36 -30 -24 -18 -12 -6 0

(d) Partially Convex, Partially Concave

Front for Equation (A.52)

-1

-0.5

0.5

1.5

2.5

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

(e) Discrete Convex Front for Equation

(A.53)

Figure A.6 Example Pareto-Optimal Fronts

A.9 Dynamic Optimization Problems 575

• The concave Pareto front in Figure A.6(c) for the MOP of Figure A.6(b), but

with

(x)=g(x)(1 − (f

(x)/g(x))

) (A.51)

• The partially concave and partially convex Pareto front in Figure A.6(d) for the

MOP of Figure A.6(b), but with

(x)=g(x)(1 −

(x)/g(x) −(f

(x)/g(x))

) (A.52)

• The discrete, convex Pareto front in Figure A.6(e) for the MOP of Figure A.6(b),

but with

(x)=g(x)(1 −

(x)/g(x) − (f

(x)/g(x)) sin(10πf

(x))) (A.53)

The objective when solving a MOP is to approximate the true Pareto-optimal front,

and then to select the solution that represents the best trade-oﬀ (for problems which,

in the end, require only one solution). To ﬁnd the exact true Pareto-optimal front (i.e.

to ﬁnd all the Pareto-optimal solutions in F) is usually computationally prohibitive.

The task is therefore reduced to ﬁnding an approximation to the true Pareto front

such that

• the distance to the Pareto front is minimized,

• the set of non-dominated solutions, i.e. the Pareto-optimal set, is as diverse as

possible, and

• already found non-dominated solutions are maintained.

The task of ﬁnding an approximation to the true Pareto front is therefore in itself a

MOP, where the ﬁrst objective ensures an accurate approximation, and the second

objective ensures that the entire Pareto front is covered.

A.9 Dynamic Optimization Problems

Dynamic optimization problems have objective functions that change over time. Such

changes in objective function cause changes in the position of optima, and the char-

acteristics of the search space. Existing optima may disappear while new optima

may appear. This chapter provides a formal deﬁnition of a dynamic problem in Sec-

tion A.9.1, and lists diﬀerent types of dynamic problems in Section A.9.2. Example

benchmark problems are given in Section A.9.3.

A.9.1 Deﬁnition

A dynamic optimization problem is formally deﬁned as

576 A. Optimization Theory

Definition A.16 Dynamic optimization problem:

minimize f(x,(t)), x =(x

,...,x

),(t)=(

(t),...,



)

subject to g

(x) ≤ 0,m=1,...,n

(x)=0,m= n

+1,...,n

+ n

∈ dom(x

) (A.54)

where (t) is a vector of time-dependent objective function control parameters. The

objective is to find

∗

(t)=min

f(x,(t)) (A.55)

where x

∗

(t) is the optimum found at time step t.

The goal of an optimization algorithm for dynamic environments is then to locate an

optimum and to track its trajectory as closely as possible.

A.9.2 Dynamic Environment Types

In order to track the optimum over time, the optimization algorithm needs to detect

and track changes. The environment may change on any timescale, referred to as

temporal severity. Changes can be continuously spread over time, at irregular time

intervals or periodically. Due to these changes, the position of an optimum may change

by any amount, referred to as spatial severity.

Eberhart et al. deﬁnes three types of dynamic environments [228, 385]:

• Type I environments, where the location of the optimum in problem space

is subject to change. The change in the optimum, x

∗

(t) is quantiﬁed by the

severity parameter, ζ, which measures the jump in location of the optimum.

• Type II environments, where the location of the optimum remains the same,

but the value, f(x

∗

(t)), of the optimum changes.

• Type III environments, where both the location of the optimum and its value

changes.

The changes in the environment, as caused by the control parameters, can be in one

or more of the dimensions of the problem. If the change is in all the dimensions, then

for type I environments, the change in optimum is quantiﬁed by ζI,whereI is the

unit vector.

Examples of these types of dynamic environments are illustrated in Figures A.7 and

A.8. Figure A.7 illustrates the dynamic function,

f(x,(t)) =



j=1

− 

(t))

+ 

(t) (A.56)

for n

= 2. Figure A.7(a) illustrates the static function with both control parameters

set to zero. A type I environment is illustrated in A.7(b) with 

=3and

=0.

A.9 Dynamic Optimization Problems 577

f(x1,x2)

-10

-5

-10

-5

100

120

140

160

180

200

f(x1,x2)

(a) Static function, 

= 

f(x1,x2)

-10

-5

-10

-5

100

150

200

250

300

350

f(x1,x2)

(b) Type I environment, 

=3,

f(x1,x2)

-10

-5

-10

-5

100

120

140

160

180

200

220

240

260

f(x1,x2)

=0,

=50

f(x1,x2)

-10

-5

-10

-5

100

150

200

250

300

350

400

f(x1,x2)

(d) Type III environment, 

=3,

=50

Figure A.7 Dynamic Parabola Objective Function