Information Technology Reference
In-Depth Information
Fig. 3. “Minimum spanning tree” for the worst-case
C ( m )= m sin( π
m )+ m 1
m 2 = m sin( π
m )+ 1
m .
Let m
→∞
,wehave
1)sin( m )+ m
m sin( m )+ m
C ( m ) = 2( m
C ( m )
lim
m→∞
=2 .
4 Hybrid Genetic Algorithm
In this section, we will improve the solution obtained by the proposed
2-approximation algorithm by hybrid genetic algorithm. Genetic algorithm (GA),
presented by Holland [18], belongs to heuristic search methods, which are very
useful when problems' search space is very large. It is not surprising that GA
and its modification have been applied to the TSP problem, see [19], [20].
Here we attempt to design a hybrid genetic algorithm: 1) the proposed 2-
approximation algorithm can be easily embedded into the HGA and the near
optimal solution obtained can be used as the basis for further search. 2) Local
search techniques in traditional TSP solution method is introduced to enhance
the local search capacity of GA. In this section, we first present an equivalent
formulation which is the basis for our HGA. Then we present the HGA based
on the 2-approximation algorithm and 2-opt exchange local search.
4.1 Reformulation of the Long Chain Model
One drawback of the formulation in Section 2 is that there are exponential
constrains in terms of n . Using the permutation matrix variable, we establish
Search WWH ::




Custom Search