An Efficiency Analysis on Mutation Operation with TSP solved in Genetic Algorithm

Yoon, Hoijin

doi:https://doi.org/10.9708/jksci.2020.25.12.055

Journal of The Korea Society of Computer and Information

Abbr : JKSCI
2020, 25(12), pp.55-61
DOI :https://doi.org/10.9708/jksci.2020.25.12.055
Publisher : The Korean Society Of Computer And Information
Research Area : Computer Science

Yoon, Hoijin ¹

¹ 협성대학교

ABSTRACT

Genetic Algorithm(GA) is applied to a problem that could not figure out its solution in a straightway. It is called as NP-hard problem. GA requires a high-performance system to be run on since the high-cost operations are needed such as crossover, selection, and mutation. Moreover, the scale of the problem domain is normally huge. That is why the straightway cannot be applied. To reduce the drawback of high-cost requirements, we try to answer if all the operations including mutation are necessary for all cases. In the experiment, we set up two cases of with/without mutation operations and gather the number of generations and the fitness of a solution. The subject in the experiment is Travelling Salesman Problem(TSP), which is one of the popular problems solved by GA. As a result, the cases with mutation operation are not faster and the solution is fitter than the case with mutation operation. From the result, the conclusion is that mutation operation does not always need for a better solution in a faster way.
KEYWORDS

Mutation Operation , Genetic Algorithm , Travelling Salesman Problem , Efficiency , Fitness
REFERENCES (12)

[book] Holland, J.H. / 1992 / Adaptation in Natural and Artificial Systems : An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence / MIT Press : 89~120

[book] M. Mitchell / 1999 / An Introduction to Genetic Algorithms / MIT Press : 128~130

[journal] H. Yoon / 2020 / Fitness-Orientated Mutation Operators in Genetic Algorithm / IJITEE 9 (4) : 1769~1772 / 10.35940/jijtee.D1692.029420

[confproc] Alan T Piszcz / 2006 / A Survey of Mutation Techniques in Genetic Programming / Proceedings of the 8th annual conference on Genetic and evolutionary computation : 951~952

[journal] E. Osaba / 2014 / Crossover versus Mutation : A Comparative Analysis of the Evolutionary Strategy of Genetic Algorithms Applied to Combinatorial Optimization Problems / The Scientific World Journal 2014 / 10.1155/2014/154676

[confproc] Hee-Su Kim / 2001 / An efficient genetic algorithm with less fitness evaluation by clustering / Proceedings of the 2001IEEE Congress on Evolutionary Computation : 887~894

[confproc] L. Wang / 2007 / An Improved Genetic Algorithm for TSP / Proceedings of 2007 International Conference on Machine Learning and Cybernetics : 925~928

[book] Clinton Sheppard / 2016 / Genetic Algorithms with Python / CreateSpace Independent Publishing : 169~186

[book] Giancarlo Zaccone / 2019 / Natural Computing with Python / bpb publications : 85~118

[confproc] J. Lu / 2007 / An Improved Immune-Genetic Algorithm for the Traveling Salesman Problem / Proceedings of 3rd International Conference on Natural Computation (ICNC 2007) : 297~301

[confproc] Y. Liu / 2008 / A Novel Genetic Algorithm and Its Application in TSP / Proceedings of 2008 IFIP International Conference on Network and Parallel Computing : 263~266

[confproc] B. H. Hasan / 2011 / Comparative Study of Mutation Operators on the Behavior of Genetic Algorithms Applied to Non-deterministic Polynomial (NP) Problems / Proceedings of 2011 Second International Conference on Intelligent Systems, Modelling and Simulation : 7~12
KCI Citation (0)

KJC Korea
Journal Central

Statistics

Tools