Engelbrecht Andries P. Computational Intelligence: An Introduction

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

548 REFERENCES

[939] Z-W. Ye and Z-B. Zheng. Research in the Conﬁguration of Parameter α, β, ρ

in Ant Algorithm Exempliﬁed by TSP. In Proceedings of the International

Conference on Machine Learning and Cybernetics, volume 4, pages 2106–2111,

2003.

[940] G.G. Yen and H. Lu. Dynamic Population Strategy Assisted Particle Swarm Op-

timization. In Proceedings of the IEEE International Symposium on Intelligent

Control, pages 697–702, 2003.

[941] H. Yoshida, Y. Fukuyama, S. Takayama, and Y Nakanishi. A Particle Swarm

Optimization for Reactive Power and Voltage Control in Electric Power Systems

Considering Voltage Security Assessment. In Proceedings of the IEEE Interna-

tional Conference on Systems, Man, and Cybernetics, volume 6, pages 497–502,

October 1999.

[942] X-H. Yu and G-A. Chen. Eﬃcient Backpropagation Learning using Optimal

Learning Rate and Momentum. Neural Networks, 10(3):517–527, 1997.

[943] J. Yuryevich and K.P. Wong. Evolutionary Programming Based Optimal Power

Flow Algorithm. IEEE Transactions on Power Systems, 14(4):1245–1250, 1999.

[944] L.A. Zadeh. Fuzzy Sets. Information and Control, 8:338–353, 1965.

[945] L.A. Zadeh. Fuzzy Algorithms. Information and Control, 12:94–102, 1968.

[946] L.A. Zadeh. The Concept of a Linguistic Variable and its Application to Ap-

proximate Reasoning, Parts 1 and 2. Information Sciences, pages 338–353, 1975.

[947] L.A. Zadeh. Soft Computing and Fuzzy Logic. IEEE Software, 11(6):48–56,

1994.

[948] B-T. Zhang. Accelerated Learning by Active Example Selection. International

Journal of Neural Systems, 5(1):67–75, 1994.

[949] C. Zhang and H. Shao. An ANN’s Evolved by a New Evolutionary System

and Its Application. In Proceedings of the Thirty-Ninth IEEE Conference on

Decision and Control, volume 4, pages 3563–3563, 2000.

[950] C. Zhang, H. Shao, and Y. Li. Particle Swarm Optimization for Evolving Arti-

ﬁcial Neural Network. In Proceedings of the IEEE International Conference on

Systems, Man, and Cybernetics, pages 2487–2490, 2000.

[951] F. Zhang and D. Xue. An Optimal Concurrent Design Model using Distributed

Product Development Life-Cycle Databases. In Sixth International Conference

on Computer Supported Cooperative Work in Design, pages 273–278, 2001.

[952] G. Zhang and Y. Zhang. Optimal Design of High Voltage Bushing Electrode

in Transformer with Evolution Strategy. IEEE Transactions on Magnetics,

35(3):1690–1693, 1999.

[953] J. Zhang and J. Xu. Evolutionary Programming Based on Uniform Design with

Application to Multiobjective Optimization. In Proceedings of the Fifth World

Congress on Intelligent Control and Automation, volume 3, pages 2298–2302,

2004.

[954] W-J. Zhang and X-F. Xie. DEPSO: Hybrid Particle Swarm with Diﬀerential

Evolution Operator. In Proceedings of the IEEE International Conference on

System, Man, and Cybernetics, volume 4, pages 3816–3821, 2003.

REFERENCES 549

[955] X. Zhang, L. Yu, Y. Zheng, Y. Shen, G. Zhou, L. Chen, L. Xi, T. Yuan, J. Zhang,

and B. Yang. Two-Stage Adaptive PMD Compensation in a 10 Gbit/s Optical

Communication System using Particle Swarm Optimization Algorithm. Optics

Communications, 231(1-6):233–242, 2004.

[956] Y. Zhang and S. Huang. Multiobjective Optimization using Distance-Based

Particle Swarm Optimization. In Proceedings of the International Conference

on Computational Intelligence, Robotics and Autonomous Systems, 2003.

[957] Y. Zhang and A. Kandel. Compensatory Genetic Fuzzy Neural Networks and

Their Applications. World Scientiﬁc, 1998.

[958] Y. Zheng, L. Ma, L. Zhang, and J. Qian. On the Convergence Analysis and

Parameter Selection in Particle Swarm Optimization. In Proceedings of the

International Conference on Machine Learning and Cybernetics, volume 3, pages

1802–1807, 2003.

[959] Y. Zheng, L. Ma, L. Zhang, and J. Qian. Robust PID Controller Design us-

ing Particle Swarm Optimization. In Proceedings of the IEEE International

Symposium on Intelligence Control, pages 974–979, 2003.

[960] Q. Zhou and Y. Li. Directed Variation in Evolution Strategies. IEEE Transac-

tions on Evolutionary Computation, 7(4):356–366, 2006.

[961] J. Zurada. Lambda Learning Rule for Feedforward Neural Networks. In Proceed-

ings of the IEEE International Joint Conference on Neural Networks,volume3,

pages 1808–1811, 1992.

[962] J.M. Zurada, A. Malinowski, and I. Cloete. Sensitivity Analysis for Minimization

of Input Data Dimension for Feedforward Neural Network. In Proceedings of

the IEEE International Symposium on Circuits and Systems, volume 6, pages

447–450, 1994.

Appendix A

Optimization Theory

Optimization algorithms are search methods, where the goal is to ﬁnd a solution to

an optimization problem, such that a given quantity is optimized, possibly subject to

a set of constraints. Although this deﬁnition is simple, it hides a number of complex

issues. For example, the solution may consist of a combination of diﬀerent data types,

nonlinear constraints may restrict the search area, the search space can be convoluted

with many candidate solutions, the characteristics of the problem may change over

time, or the quantity being optimized may have conﬂicting objectives. This is just

a short list of issues, given to illustrate some of the complexities an optimization

algorithm may have to face. This chapter provides a crisp summary of these issues,

and characterizes diﬀerent problem types.

Section A.1 summarizes the main ingredients of optimization problems. A classiﬁca-

tion of optimization problems is given in Section A.2. Section A.3 discusses optima

types. A list of optimization method classes is provided in Section A.4. Unconstrained

optimization problems are deﬁned and discussed in Section A.5, constrained optimiza-

tion in Section A.6, multi-solution problems in Section A.7, multi-objective problems

in Section A.8, and dynamic environments in Section A.9.

A.1 Basic Ingredients of Optimization Problems

Each optimization problem consists of the following basic ingredients:

• An objective function, which represents the quantity to be optimized, that is,

the quantity to be minimized or maximized. Let f denote the objective func-

tion. Then a maximum of f is a minimum of −f. Some problems, speciﬁcally

constraint-satisfaction problems (CSP), do not deﬁne an explicit objective func-

tion. Instead, the objective is to ﬁnd a solution that satisﬁes all of a set of

constraints.

• A set of unknowns or variables, which aﬀects the value of the objective

function. If x represents the unknowns, also referred to as the independent

variables, then f(x) quantiﬁes the quality of the candidate solution, x.

• A set of constraints, which restricts the values that can be assigned to the

unknowns. Most problems deﬁne at least a set of boundary constraints, which

Computational Intelligence: An Introduction, Second Edition A.P. Engelbrecht

2007 John Wiley & Sons, Ltd

551

552 A. Optimization Theory

deﬁne the domain of values for each variable. Constraints can, however, be

more complex, excluding certain candidate solutions from being considered as

solutions.

The goal of an optimization method is then to assign values, from the allowed domain,

to the unknowns such that the objective function is optimized and all constraints are

satisﬁed. To achieve this goal, the optimization algorithm searches for a solution in a

search space, S, of candidate solutions. In the case of constrained problems, a solution

is found in the feasible space, F⊆S.

A.2 Optimization Problem Classiﬁcations

Optimization problems are classiﬁed based on a number of characteristics:

• The number of variables that inﬂuences the objective function: A problem

with only one variable to be optimized is referred to as a univariate problem. If

more than one variable is considered, the problem is referred to as a multivariate

problem.

• The type of variables: A continuous problem has continuous-valued variables,

i.e. x

∈ R,foreachj =1,...,n

.Ifx

∈ Z, the problem is referred to

as an integer or discrete optimization problem. A mixed integer problem has

both continuous-valued and integer-valued variables. Problems where solutions

are permutations of integer-valued variables are referred to as combinatorial

optimization problems.

• The degree of nonlinearity of the objective function: Linear problems

have an objective function that is linear in the variables. Quadratic problems

use quadratic functions. When other nonlinear objective functions are used, the

problem is referred to as a nonlinear problem.

• The constraints used: A problem that uses only boundary constraints is re-

ferred to as an unconstrained problem. Constrained problems have additional

equality and/or inequality constraints.

• The number of optima: If there exists only one clear solution, the problem is

unimodal. If more than one optimum exists, the problem is multimodal. Some

problems may have false optima, in which case the problem is referred to as

being deceptive.

• The number of optimization criteria: If the quantity to be optimized is

expressed using only one objective function, the problem is referred to as a uni-

objective (or single-objective) problem. A multi-objective problem speciﬁes more

than one sub-objective, which need to be simultaneously optimized.

The optimization methods used to solve the above problem types diﬀer signiﬁcantly,

as will be illustrated in the parts that follow.

A.3 Optima Types 553

Weak local minimum

oba

l minim

Strong local minima

Figure A.1 Types of Optima for Unconstrained Problems

A.3 Optima Types

Solutions found by optimization algorithms are classiﬁed by the quality of the solution.

The main types of solutions are referred to as local optima or global optima. For the

purpose of this section, a minimization problem is assumed.

A global optimum (considering a minimization problem) is formally deﬁned as follows:

Definition A.1 Global minimum: The solution x

∗

∈F, is a global optimum of the

objective function, f,if

f(x

∗

) <f(x), ∀x ∈F (A.1)

where F⊆S.

The global optimum is therefore the best of a set of candidate solutions, as illustrated

in Figure A.1 for a minimization problem. As illustrated in Figure A.2, a problem

may have more than one global optimum.

A local minimum is deﬁned as follows (as illustrated in Figure A.1):

Definition A.2 Strong local minimum: The solution, x

∗

∈N⊆F,isastrong

local minimum of f,if

f(x

∗

) <f(x), ∀x ∈N (A.2)

where N⊆Fis a set of feasible points in the neighborhood of x

∗

554 A. Optimization Theory

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

0 0.2 0.4 0.6 0.8 1

f(x)

Figure A.2 Problem with Multiple Global Optima, with f(x)=sin

(5πx)

Definition A.3 Weak local minimum: The solution, x

∗

∈N⊆F,isaweaklocal

minimum of f ,if

f(x

∗

) ≤ f(x), ∀x ∈N (A.3)

where N⊆Fis a set of feasible points in the neighborhood of x

∗

A.4 Optimization Method Classes

An optimization algorithm searches for an optimum solution by iteratively transform-

ing a current candidate solution into a new, hopefully better, solution. Optimization

methods can be divided into two main classes, based on the type of solution that is

located. Local search algorithms use only local information of the search space sur-

rounding the current solution to produce a new solution. Since only local information

is used, local search algorithms locate local optima (which may be a global minimum).

A global search algorithm uses more information about the search space to locate a

global optimum. It is said that global search algorithms explore the entire search

space, while local search algorithms exploit neighborhoods. Optimization algorithms

are further classiﬁed into deterministic and stochastic methods. Stochastic methods

use random elements to transform one candidate solution into a new solution. The

new point can therefore not be predicted. Deterministic methods, on the other hand,

do not make use of random elements.

Based on the problem characteristics, optimization methods are grouped in the follow-

ing classes (within each of these classes further subdivision occurs based on whether

local or global optima are located, and based on whether random elements are used

to investigate new points in the search space):

A.5 Unconstrained Optimization 555

• unconstrained methods, used to optimize unconstrained problems;

• constrained methods, used to ﬁnd solutions in constrained search spaces;

• multi-objective optimization methods for problems with more than one

objective to optimize;

• multi-solution (niching) methods with the ability to locate more than one

solution; and

• dynamic methods with the ability to locate and track changing optima.

Subsequent sections discuss each of these optimization method classes.

A.5 Unconstrained Optimization

Except for boundary constraints, unconstrained optimization problems place no re-

strictions on the values that can be assigned to variables of the problem. The feasible

space is simply the entire search space. This chapter provides a formal deﬁnition of

unconstrained optimization problems in Section A.5.1. Section A.5.2 summarizes al-

gorithms used in later chapters, and Section A.5.3 gives a list of classical benchmark

problems.

A.5.1 Problem Deﬁnition

The general unconstrained optimization problem is deﬁned as

Definition A.4 Unconstrained optimization problem:

minimize f(x), x =(x

,...,x

)

subject to x

∈ dom(x

)(A.4)

where x ∈F= S, and dom(x

) is the domain of variable x

For a continuous problem, the domain of each variable is R, i.e. x

∈ R. For an integer

problem, x

∈ Z, while dom(x

) for a general discrete problem is a ﬁnite set of values.

Note that an integer problem is simply a special case of a discrete problem.

A.5.2 Optimization Algorithms

Many optimization algorithms have been developed to solve unconstrained problems.

This section summarizes only a few that support the material presented in this book.

The reader is referred to [201, 262, 263, 317, 806] for more detail.

556 A. Optimization Theory

General Local Search Procedure

Local search methods follow the same basic structure as given in Algorithm A.1. A

starting point, x(0), is selected, and its quality evaluated. Then, iteratively a search

direction is determined and a move is made in that direction.

Algorithm A.1 General Local Search Algorithm

Find starting point x(0) ∈S;

t =0;

repeat

Evaluate f(x(t));

Calculate a search direction, q(t);

Calculate step length η(t);

Set x(t +1)tox(t)+η(t)q(t);

t = t +1;

until stopping condition is true;

Return x(t) as the solution;

Search directions and step lengths can be determined using steepest gradient descent,

conjugate gradients, or Newton methods (amongst many others).

Beam Search

Beam search (BS) is a classical tree local search method [650]. The search method

allows the extension of partial, or approximate, solutions in a number of ways as

determined by tree branches. Each step of the algorithm extends a partial solution

from the set B (referred to as the beam) in at most n

possible ways. A newly

constructed solution is stored in the set of complete solutions, B

, if that solution

represents a complete solution. If not, the new partial solution is added to the set

of partial solutions. At the end of each iteration, a new beam, B,iscreatedby

selecting n

solutions from B

,wheren

is the beam width. BS uses a lower bound

on the objective function value to select partial solutions from B

. The lower bound

speciﬁes the minimum objective function value for any complete solution that can

be constructed from a partial solution. Partial solutions are usually extended using

a deterministic greedy policy, which is based on a weighting function that assigns

weights to all the possible extensions.

Tabu Search

Tabu search (TS) is an iterative neighborhood search algorithm [319, 362], where the

neighborhood changes dynamically. TS enhances local search by actively avoiding

points in the search space already visited. By avoiding already visited points, loops

in search trajectories are avoided and local optima can be escaped. The main feature

A.5 Unconstrained Optimization 557

of TS is the use of an explicit memory. A simple TS usually implements two forms of

memory:

• A frequency-based memory, which maintains information about how often

a search point has been visited (or how often a move has been made) during a

speciﬁed time interval.

• A recency-based memory, which maintains information about how recently a

search point has been visited (or how recently a move has been made). Recency

is based on the iteration at which the event occurred.

If, for example, the frequency count of a search point exceeds a given threshold, then

that point is classiﬁed as being tabu for the next cycle of iterations. Positions speciﬁed

in the tabu list are excluded from the neighborhood of candidate positions that can

be visited from the current position. Positions remain in the tabu list for a speciﬁed

time period.

The following may be used to terminate TS:

• the neighborhood is empty, i.e. all possible neighboring points have already been

visited, or

• when the number of iterations since the last improvement is larger than a spec-

iﬁed threshold.

Simulated Annealing

Annealing refers to the cooling process of a liquid or solid, and the analysis of the

behavior of substances as they cool [581]. As temperature reduces, the mobility of

molecules reduces, with the tendency that molecules may align themselves in a crys-

talline structure. The aligned structure is the minimum energy state for the system.

To ensure that this alignment is obtained, cooling must occur at a suﬃciently slow

rate. If the substance is cooled at a too rapid rate, an amorphous state may be reached.

Simulated annealing is an optimization process based on the physical process described

above. In the context of mathematical optimization, the minimum of an objective

function represents the minimum energy of the system. Simulated annealing is an

algorithmic implementation of the cooling process to ﬁnd the optimum of an objective

function [466, 467, 649, 806].

Simulated annealing (SA) uses a random search strategy, which not only accepts new

positions that decrease the objective function (assuming a minimization problem), but

also accepts positions that increase objective function values. The latter is accepted

probabilistically based on the Boltzmann–Gibbs distribution. If P

is the probability

of moving from point x

to x

,thenP

is calculated using

1iff(x

) <f(x

)

−

f(x

)−f(x

)

otherwise

(A.5)

where c

> 0 is the Boltzmann constant and T is the temperature of the system.