Information Technology Reference
In-Depth Information
general antibody to memory antibody as a diversity approach. Furthermore, in
our proposed model, the reactions between antibodies and memory antibody
promote the evolution individually, which is suitable for parallel computing in
further research. However, the reactions among antibodies (crossover operator)
are not considered here. In particular, through combing the advantages of the
hormonal regulation and enzymatic reaction, the EINET provides a good trade-
off between the diversity and convergence.
3 EINET-TSP Algorithm Design
In order to evaluate whether the proposed model, EINET for optimization, can
be directly extended to an effective algorithm capable of solving combinatorial
optimization problems, an approach based on EINET called EINET-TSP are
presented to solve TSP.
The TSP is a typical example of a very hard combinatorial optimization prob-
lemand can be simplified as: a search for the shortest closed tour that visits each
city at lease and only once. Considering a traveling salesman problem with k
cities to visit, the traveling salesman problem can be formulated as:
k−
1
min
{
d
j,j
+1
(
.
)+
d
k,
1
(
.
)
}
(4)
j
=1
where
d
j,j
+1
(
.
) is the distance between city
j
to city
j+1
.
Here, the EINET-TSP is incorporated with the necessary design to make it
applicable to TSP based on the given framework of EINET for optimization.
Details of the five operators of the EINET-TSP algorithm are discussed in the
following subsections.
3.1 Anity Evaluation
In the TSP, one feasible route through all the cities can be regarded as a can-
didate antibody. Then, the anity function defined by the objective function of
TSP (Eq.1) can be written as:
1
aff
(
Ab
i
)=
(5)
k−
1
j
=1
d
j,j
+1
(
Ab
i
)+
d
k,
1
(
Ab
i
)
As stated above, the antibody with max
aff
(
Ab
i
) is selected as the memory
antibody.
3.2 Difference Evaluation
Evaluate the difference value of each antibody is equal to calculate a distance
between the antibody route and the memory antibody route. Denote the route
of
Ab
i
as
Search WWH ::
Custom Search