/he International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences. Vol. XXXVII. Part B7. Beijing 2008
342
from nature immune system to solve complex problems
(Timmis, 2001).
The natural immune system consists of immune organs,
immune cells and immune molecules. Immune organs are
composed of central immune organs and peripheral immune
organs. Central immune organs are composed of bone marrow
and thymus, where lymphocytes and other immune cells
generate, differentiate and mutate. Peripheral immune organs
include lymphocytes, spleen, and catarrh tissues, where T-cell
and B-cell settle and proliferate, and where immune system
responds to antigen’s stimulation.
AIS provides new ideas for multi-objective optimization.
Chung et al (J.S.Chung, 1998) confirmed that immune
algorithm were superior to other algorithms in solving multi
objective optimization problems. Then the research on immune
algorithm has absorbed significant attention in recent years
(Zhang, 2006). Clonal selection algorithm is an excellent
immune algorithm in AIS, and has been tested useful in multi
objective optimization.
2.1 The clonal selection algorithm
In 1950s, the clonal selection theory was developed by Burnet
for the first time (Burnet, 1959). De Castro then proposed a
clonal selection algorithm (De Castro, 2002) which was based
on the clonal selection theory. The algorithm is mentioned
briefly as Figure 1.
Figure 2. Diagram of the clonal selection algorithm
Stepl: Produce original population S(Ab), which is a set of
antibodies.
Step2: Select n best individuals Sn from original population
through affinity estimation.
Step3: Clone these n best individuals, and generate temporary
population T(Ab). The clone size increases as the increasing of
the affinity.
Step4: A mutation operation is used to temporary population
T(Ab), and a mature mature population T*(Ab) is generated.
Step5: Select d best individuals from T*(Ab), and a set T* d is
composed.
Step6: Replace d worst individuals from original population
S(Ab) by T* d , and a clonal selection of S(Ab) is completed.
2.2 Immune algorithm in multi-objective optimization
2.2.1 The definition of multi-objective optimization
problem: Multi-objective optimization problem is that find the
decision variable which satisfies constrains and optimizes the
objective functions. A typical multi-objective optimization
problem with n decision variables, m constrains and p
objectives are described as formula (1).
minF(x) = [f\(x),f2(x),...,f P (x)] T
s.t. gj(x)<0,i = \,2,...,m (1)
X = {x\ g t (x) < 0,i = 1,2which is constrained domain
is said to the feasible domain of decision variables.
Pareto optimal solution: the optimal solution is always a set in
multi-objective optimization problems, so pareto optimal
solution is an important concept which is described as formula
(2).
X is a Pareto optimal solution if and only if there exist no other
variable X, which satisfies the expression as below when it does
not contravene the constrains:
Vie {1,2,...«}:/(X)£/(*•)a3
2.2.2 Immune algorithm in multi-objective optimization:
In multi-objective optimization problems, a feasible solution
could be treated as an antibody, and an object function could be
treated as an antigen. The affinity between antibody and antigen
could be described as the value of the object functions for
feasible solutions (Figure 2).
f A r A
Antibody
Solution
Antigen
Object function
Affinition
Value of function
Figure 2. The reference from immune system to multi-objective
optimization problem
Immune memory is contained in clonal selection algorithm. It
makes sure the fast convergence of global optimal solution. The
clonal proportion conforms to direct ratio with affinity. Then
through the mutation, it promotes or inhibits the antibodies. It
shows the self-adjustment ability of immune system. There are
two forms to calculate the affinity: one reflects the correlation
between antibodies and antigens (the matching degree between
solution and objects), and the other one reflects the correlation
between antibodies and antibodies, which ensures the diversity
of antibody in immune system (Zhai, 2006).