平成24年度 電気関係学会四国支部連合大会

161-16

Genetic Algorithm with Virus Infection
for Traveling Salesman Problem
Takuya INOUE, Yudai SHIRASAKI,
Yoko UWATE and Yoshifumi NISHIO(Tokushima University)

1. Introduction
Traveling Salesman Problem (TSP) is known as one of
the combinatorial optimization problems. The Genetic Algorithm (GA) [1] is popular method to solve the TSP. However, the GA has characteristic that convergence speed isslow.
In this study, we propose Genetic Algorithm with Virus
Infection (GAVI). One of the characteristics of the virus
infection [2] is to be spread out around at once. This characteristic seems to be useful to ﬁnd the optimum solution
quickly. Therefore, we consider that the virus will help
to solve the TSP. We carry out computer simulations forvarious parameter values and conﬁrm that the proposed algorithm achieves better performance than the conventional
GA.

2. Flow of GAVI
Selection, Crossover and M utation are the main functions of the GA. GAVI is a method that incorporate thestandard GA with virus characteristic. GAVI algorithm isindicated the following Step1-7. Step2 from Step7 is repeated until the set number of Crossover times.

Step1 (Random route selection)
The number of Random route selection is the same as thenumber of cities. For example, in the case of 16 cities,Random route selection makes 16 routes at random.

Step2 (Evaluation)
Evaluation is deﬁned by the following formula,1
fi =(1)
diwhere di is total distance of each route and fi is evaluation value.

Step3 (Selection)
Route is selected with a probability of pi .
fi(2)pi = ∑nfi=1 iwhere n is the number of cities. Selection is the methodof tends to be chosen high evaluation route.

Step4 (Crossover)
Crossover is to be mated the two routes.

Step5 (Inf ection)
It deﬁnes Virus that the shortest distance between thecities in route. For example, 1 from 6 is route numbers and between adjacent elements is deﬁned distance.
3, 5 is a virus and has infected the route of 1, 6, 3, 5, 2, 4in Fig. 1(a). The route replace to 2, 3 1, 4. We call it
Inf ection. Inf ection is incorporating partial optimum solution

Step6 (Destruction)
We calculate the longest distance between the cities inroute in every generation. For example, 6, 1 is the longest
distance between the cities in route of 3, 6, 1, 4, 2, 5 inFig. 1(b) and swap the order of the route. The longest
distance disappear in this route. We call it Destruction.
Destruction is avoiding partial bad solution.

Step7 (M utation)
M utation is to change the route with a certain probability
and less likely to fall into local minimum.

3. Experimental Results
In order to compare the performance of GAVI and GA,
we apply GAVI and GA to a TSP such as ulysses16(16Powered by TCPDF (www.tcpdf.org)

Virus353614Choose a place
to infect
3614225Replace the 1 and 45361425InfectionDestruction

16352436(a)4125(b)Figure 1: The mechanism of two functions.
(a) Infection (b) Destructioncities). Table1 shows simulation result for ulysses16. In
this study, the number of generation is 5000 times, thenumber of simulation is 100 times and error rate is deﬁned
by the following formula.
(obtain) − (optimum)
error rate[%] =∗ 100(3)(optimum)
where obtain is minimum solution. optimum is optimumsolution. In Table1, Ave is the average, Max is the maximum value and Min is the minimum value in the resultsof simulation 100 times.
GAVI obtains better result than GA in Table1. GAVI
can ﬁnd a good solution by Inf ection and Destruction.
We assume that Inf ection and Destruction were eﬀective processes to escape from local minimum similar withM utation.

Table 1: The result for ulysses16
algorithm
typeGA
GAVI

Mutation
rate
0.02
0.05
0.10
0.02
0.05
0.10

Max
55.26757.79466.84428.347
34.50341.190error rate[%]MinAve14.40437.251
4.395
30.38618.10939.5063.852
10.8582.204
11.9372.818
10.972

4. Conclusion
We proposed GAVI for TSP and applied it to lead approximate solutions. From the result, GAVI was valuable
in convergence of the solution. In future work, we would
like to study the mechanism of Inf ection and Destruction
in detail. It is also our future work to investigate leading
approximate solution for large number of cities in TSP.

References[1] Jean-Yves Potvin,“Genetic algorithms for the travelingsalesman problem,” Annals of Operations Research 63,
pp.339-370, 1996.
[2] Naoshi Nakaya, Akinori Kanasugi and Kunio Kondo,“An Evolutionary Algorithm Based on the Virus Theory of Evolution,” Information Processing Society ofJapan Vol.40, No.5, 1999.