Engelbrecht Andries P. Computational Intelligence: An Introduction

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

408 17. Ant Algorithms

(a) 2-opt

(b) 3-opt

Figure 17.4 2-opt and 3-opt Local Search Heuristic

n ≥ 25 cannot be solved exactly. This section discusses approaches to solve the QAP

using ACO algorithms.

Problem Deﬁnition

The main objective in QAPs is to assign facilities to locations such that the product

of the ﬂow among activities is minimized, under the constraint that all facilities must

be allocated to a location and each location can have only one facility assigned to it.

The solution is a permutation π of {1,...,n

},wheren

is the number of facilities

and locations. Formally, the objective function to be minimized is deﬁned as

f(π)=



i,j=1

π(i)π(j)

(17.107)

where d

is the Euclidean distance between locations i and j, f

characterizes the

ﬂow between facilities h and k,andπ(i) is the activity assigned to location i.

Problem Representation

The search space is represented by a graph, G =(V, E). Each node, v

∈ V,i =

1,...,n

, represents a location i. Associated with each link (i, j) ∈ E = {(i, j)|i, j ∈

V } is a distance d

. An assignment is a permutation π of {1,...,n

17.5 Applications 409

Solution Construction

Ants are randomly placed on the graph, and each ant constructs a permutation of

facilities incrementally. When in location i, the ant selects a facility from the set

of unallocated facilities and assigns that facility to location i. A complete solution

is found when all locations have been visited. Diﬀerent mechanisms can be used

to step through the graph of locations, for example, in sequential or random order

[557]. Dorigo et al. [216] used a diﬀerent approach where the objective function is

expressed as a combination of the potential vectors of distance and ﬂow matrices. If

D =[d

]

×n

is the distance matrix, and F =[f

]

×n

the ﬂow matrix, deﬁne the

potential vectors, D and F,as



j=1

,i=1,...,n

(17.108)



k=1

,h=1,...,n

(17.109)

The next location is deterministically chosen from the free locations as the location

with the lowest distance potential, D

For location i facility h (using the potential vectors approach), can be selected de-

terministically as the not yet assigned facility with the highest ﬂow potential. Al-

ternatively, selection can be made probabilistically using an appropriate transition

probability function. St¨utzle and Hoos [816] used the transition probability

(t)=



j∈N

(t)

if location i is still free

0otherwise

(17.110)

Maniezzo and Colorni [557] deﬁned the transition probability as

(t)=

ατ

(t)+(1−α)η



j∈N

(t)

ατ

(t)+(1−α)η

if location i is still free

0otherwise

(17.111)

Instead of using a constructive approach to solve the QAP, Gambardella et al. [304]

and Talbi et al. [835] used the hybrid AS (HAS) to modify approximate solutions. Each

ant receives a complete solution obtained from a nearest-neighbor heuristic and reﬁnes

the solution via a series of n

/3 swaps. For each swap, the ﬁrst location i is selected

randomly from {1, 2,...,n

}, and the second location, j, is selected according to the

rule: if U (0, 1) <r,thenj ∼ U{1,...,n

}\{i}; otherwise, j is selected according to

the probability,

(t)=

iπ

(j)

+ τ

jπ

(i)



l=1

l=i

(τ

iπ

(l)

+ τ

lπ

(i)

)

(17.112)

410 17. Ant Algorithms

Heuristic Desirability

Based on the potential vectors deﬁned in equation (17.108) and (17.109) [216],

(17.113)

where s

= D

∈ S = DF

gives the potential goodness of assigning facility h to

location i.

Constraint Satisfaction

The QAP deﬁnes two constraints:

• all facilities have to be assigned, and

• only one facility can be allocated per location.

To ensure that facilities are not assigned more than once, each ant maintains a facility

tabu list. When a new facility has to be assigned, selection is from the facilities not yet

assigned, i.e. {1,...,n

}\Υ

. Ants terminate solution construction when all nodes

(locations) have been visited, which ensures (together with the tabu list) that each

location contains one facility.

Local Search Heuristics

Gambardella et al. [304] consider all possible swaps in a random order. If a swap results

in an improved solution, that modiﬁcation is accepted. The diﬀerence in objective

function value due to swapping of facilities π(i)andπ(j) is calculated as

∆f(π, i, j, )=(d

− d

)(f

π(j)π(j)

− f

π(i)π(i)

)

+(d

− d

)(f

π(j)π(i)

− f

π(i)π(j)

)



l=1,l=i

l=j

[(d

− d

)(f

π(l)π(j)

− f

π(l)π(i)

) + (17.114)

+(d

− d

)(f

π(j)π(l)

− f

π(i)π(l)

)]

The modiﬁcation is accepted if ∆f(π, i,j) < 0.

St¨utzle and Hoos [816] proposed two strategies to decide if a swap is accepted:

• The first-improvement strategy accepts the ﬁrst improving move, similar to

standard hill-climbing search.

• The best-improvement strategy considers the entire neighborhood and ac-

cepts the move that gives the best improvement [557], similar to steepest ascent

hill-climbing search.

17.6 Assignments 411

While the ﬁrst-improvement strategy is computationally less expensive than the best-

improvement strategy, it may require more moves to reach a local optimum.

Roux et al. [743, 744] and Talbi et al. [835] used TS as local search method. Talbi

et al. used a recency-based memory, with the size of the tabu list selected randomly

between n/2and3n/2.

17.5.3 Other Applications

Ant algorithms have been applied to many problems. Some of these are summarized

in Table 17.2. Note that this table is not a complete list of applications, but just

provides a ﬂavor of diﬀerent applications.

17.6 Assignments

1. Consider the following situation: ant A

follows the shortest of two paths to the

food source, while ant A

follows the longer path. After A

reached the food

source, which path back to the nest has a higher probability of being selected by

? Justify your answer.

2. Discuss the importance of the forgetting factor in the pheromone trail depositing

equation.

3. Discuss the eﬀects of the α and β parameters in the transition rule of equation

(17.6).

4. Show how the ACO approach to solving the TSP satisﬁes all the constraints of

the TSP.

5. Comment on the following strategy: Let the amount of pheromone deposited be

a function of the best route. That is, the ant with the best route, deposits more

pheromone. Propose a pheromone update rule.

6. Comment on the similarities and diﬀerences between the ant colony approach to

clustering and SOMs.

7. For the ant clustering algorithm, explain why

(a) the 2D-grid should have more sites than number of ants;

(b) there should be more sites than data vectors.

8. Devise a dynamic forgetting factor for pheromone evaporation.

Part V

ARTIFICIAL IMMUNE

SYSTEMS

An artiﬁcial immune system (AIS) models the natural immune system’s ability to

detect cells foreign to the body. The result is a new computational paradigm with

powerful pattern recognition abilities, mainly applied to anomaly detection.

Diﬀerent views on how the natural immune system (NIS) functions have been devel-

oped, causing some debate among immunologists. These models include the classical

view of lymphocytes that are used to distinguish between self and non-self, the clonal

selection theory where stimulated B-Cells produce mutated clones, danger theory,

which postulates that the NIS has the ability to distinguish between dangerous and

non-dangerous foreign cells, and lastly, the network theory where it is assumed that

B-Cells form a network of detectors.

Computational models have been developed for all these views, and successfully ap-

plied to solve real-world problems. This part

aims to provide an introduction to these

computational models of the immune system. Chapter 18 provides an overview of the

natural immune system, while artiﬁcial immune systems are discussed in Chapter 19.

This part on artiﬁcial immune systems has been written by one of my PhD students, Attie

Graaﬀ. Herewith I extend my thanks to Attie for contributing this part to the book, making this a

very complete book on computational intelligence.

413

Chapter 18

Natural Immune System

The body has many defense mechanisms, which among others are the skin of the body,

the membrane that covers the hollow organs and vessels, and the adaptive immune

system. The adaptive immune system reacts to a speciﬁc foreign body material or

pathogenic material (referred to as antigen). During these reactions the adaptive

immune system adapts to better detect the encountered antigen and a ‘memory’ is

built up of regular encountered antigen. The obtained memory speeds up and improves

the reaction of the adaptive immune system to future exposure to the same antigen.

Due to this reason defense reactions are divided into three types: non-speciﬁc defense

reactions, inherited defense reactions and speciﬁc defense reactions [582]. The adaptive

immune system forms part of the speciﬁc defense reactions.

Diﬀerent theories exist in the study of immunology regarding the functioning and or-

ganizational behavior between lymphocytes in response to encountered antigen. These

theories include the classical view, clonal selection theory, network theory, and danger

theory. Since the clonal selection, danger theory and network theory are based on

concepts and elements within the classical view (see Section 18.1), the classical view

will ﬁrst be discussed in detail to form a bases onto which the other three theories will

be explained in Sections 18.5, 18.6 and 18.7.

18.1 Classical View

The classical view of the immune system is that the immune system distinguishes

between what is normal (self) and foreign (non-self or antigen) in the body. The

recognition of antigens leads to the creation of specialized activated cells, which in-

activate or destroy these antigens. The natural immune system mostly consists of

lymphocytes and lymphoid organs. These organs are the tonsils and adenoids, thy-

mus, lymph nodes, spleen, Peyer’s patches, appendix, lymphatic vessels, and bone

marrow. Lymphoid organs are responsible for the growth, development and deploy-

ment of the lymphocytes in the immune system. The lymphocytes are used to detect

any antigens in the body. The immune system works on the principle of a pattern

recognition system, recognizing non-self patterns from the self patterns [678].

The initial classical view was deﬁned by Burnet [96] as B-Cells and Killer-T-Cells

with antigen-speciﬁc receptors. Antigens triggered an immune response by interacting

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

2007 John Wiley & Sons, Ltd

415

416 18. Natural Immune System

with these receptors. This interaction is known as stimulation (or signal 1). It was

Bretscher and Cohn [87] who enhanced the initial classical view by introducing the

concept of a helper T-Cell (see Section 18.3.1). This is known as the help signal (or

signal 2). In later years, Laﬀerty and Cunningham added a co-stimulatory signal to the

helper T-Cell model of Bretscher and Cohn. Laﬀerty and Cunningham [497] proposed

that the helper T-Cell is co-stimulated with a signal from an antigen-presenting cell

(APC). The motivation for the co-stimulated model was that T-Cells in a body had a

stronger response to cells from the same species as the T-Cells in comparison to cells

from diﬀerent species than the T-Cells. Thus, the APC is species speciﬁc.

The rest of this chapter explains the development of the diﬀerent cell types in the

immune system, antigens and antibodies, immune reactions and immunity types and

the detection process of foreign body material as deﬁned by the diﬀerent theories.

18.2 Antibodies and Antigens

Within the natural immune system, antigens are material that can trigger immune

response. An immune response is the body’s reaction to antigens so that the antigens

are eliminated to prevent damage to the body. Antigens can be either bacteria, fungi,

parasites and/or viruses [762]. An antigen must be recognized as foreign (non-self).

Every cell has a huge variety of antigens in its surface membrane. The foreign antigen

is mostly present in the cell of micro-organisms and in the cell membrane of ‘donor

cells’. Donor cells are transplanted blood cells obtained through transplanted organs

or blood. The small segments on the surface of an antigen are called epitopes and the

small segments on antibodies are called paratopes (as shown in Figure 18.1). Epitopes

trigger a speciﬁc immune response and antibodies’ paratopes bind to these epitopes

with a certain binding strength, measured as aﬃnity [582].

Antibodies are chemical proteins. In contradiction to antigens, antibodies form part

of self and are produced when lymphocytes come into contact with antigen (non-

self). An antibody has a Y-shape (as shown Figure 18.1). Both arms of the Y consist

of two identical heavy and two identical light chains. The chains are distinct into

heavy and light since the heavy chain contains double the number of amino-acids than

the light chain. The tips of the arms are called the variable regions and vary from

one antibody to another [762]. The variable regions (paratopes) enable the antibody

to match antigen and bind to the epitopes of an antigen. After a binding between

an antibody and an antigen’s epitope, an antigen-antibody-complex is formed, which

results into the de-activation of the antigen [582]. There are ﬁve classes of antibodies:

IgM, IgG, IgA, IgE, IgD [582].

18.3 The White Cells

All cells in the body are created in the bone marrow (as illustrated in Figure 18.2).

Some of these cells develop into large cell- and particle-devouring white cells known

18.3 The White Cells 417

Antigen

Epitope

Variable region

Antibody

Light chain

Heavy chain

Figure 18.1 Antigen-Antibody-Complex

as phagocytes [762]. Phagocytes include monocytes, macrophages and neutrophils.

Macrophages are versatile cells that secrete powerful chemicals and play an impor-

tant role in T-Cell activation. Other cells develop into small white cells known as

lymphocytes.

18.3.1 The Lymphocytes

There are two types of lymphocytes: the T-Cell and B-Cell, both created in the bone

marrow. On the surface of the T-Cells and B-Cells are receptor molecules that bind

to other cells. The T-Cell binds only with molecules that are on the surface of other

cells. The T-Cell ﬁrst become mature in the thymus, whereas the B-Cell is already

mature after creation in the bone marrow. A T-Cell becomes mature if and only if it

does not have receptors that bind with molecules that represent self cells. It is there-

fore very important that the T-Cell can diﬀerentiate between self and non-self cells.

Thus lymphocytes have diﬀerent states: immature, mature, memory and annihilated

(Figure 18.3 illustrates the life cycle of lymphocytes). These states are discussed in

the subsections to follow below. Both T-Cells and B-Cells secrete lymphokines and

macrophages secrete monokines. Monokines and lymphokines are known as cytokines

and their function is to encourage cell growth, promote cell activation or destroy target

cells [762]. These molecules on the surface of a cell are named the major histocompati-

bility complex molecules (MHC-molecules). Their main function is to bring to light the