Summary

Proceedings of the 2013 International Symposium on Nonlinear Theory and its Applications

2013

Session Number:A3L-C

Session:

Number:102

Consideration of Diverse Solutions Genetic Algorithm with Virus Infection for Traveling Salesman Problem

Takuya Inoue,  Yoko Uwate,  Yoshifumi Nishio,  

pp.102-105

Publication Date:

Online ISSN:2188-5079

DOI:10.15248/proc.2.102

PDF download (540.5KB)

Genetic Algorithm (GA) is known as one of method to solve Traveling Salesman Problem (TSP). However, GA needs amount of time for finding approximate solution. In our previous study, we have proposed Genetic Algorithm with Virus Infection (GAVI). GAVI algorithm is used Virus Theory of Evolution (VTE) to be based on GA. Characteristic of VTE is effective for finding approximate solution. Thus, GAVI obtains more effective result than GA. However, GAVI does not make consideration of diverse solutions. In this study, we propose new algorithm to make consideration of diverse solutions. This proposed algorithm is named Consideration of Diverse Solutions Genetic Algorithm with Virus Infection (DS-GAVI). We apply DS-GAVI to TSP and confirm that DS-GAVI obtains effective solutions for leading approximate solution.

[1] Little J, Murty K, Sweeney D, Karel C, “An algorithm for the traveling salesman problem,” Operations Research 11:972-89, 1963.

[2] Jean-Yves Potvin, “Genetic algorithms for the traveling salesman problem,” Annals of Operations Research 63, pp.339-370, 1996.

[3] Kitano H ed., “ldenteki Algorithm [Genetic Algorithm],” 1st ed.Sangyo Tosyo Kabushiki Kaisya, 1993.

[4] Takuya I, Yudai S, Yoko U and Yoshifumi N, “Consideration of Genetic Algorithm with Virus Infection Solving Traveling Salesman Problem” Proceedings of RISP International Workshop on Nonlinear Circuits, Communications and Signal Processing (NCSP' 13), pp289-292, 2013.

[5] Fang G, Hongwei L, Qiang Z, Gang C, “A Genetic Algorithm with a Mixed Region Search for the Asymmetric Traveling Salesman Problem,” Computers and Operations Research 30(5), 773-786, 2003.

[6] Naoshi N, Akinori K and Kunio K, “An Evolutionary Algorithm Based on the Virus Theory of Evolution,” Infonnation Processing Society of Japan Vol.40, No.5, 1999.

[7] Gao F, Liu H, Zhao Q, Cui G, “Virus-evolutionary particle swarm optimization algorithm,” vol 4222. Springer, Berlin, pp 156-165, 2006.

[8] Hideomi N, Takashi S and Takashi F, “Virus theory of evolution,” Bulletin of Yamanashi Medical University Vol.3, pp.14-18, 1986.

[9] Zhaxybayeva 0, Doolittle W F, “Lateral gene transfer,” Curr. Biol. 21, R242-246 2011.