본문 바로가기
  • Home

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

  • Journal of The Korea Society of Computer and Information
  • Abbr : JKSCI
  • 2020, 25(12), pp.55-61
  • DOI : 10.9708/jksci.2020.25.12.055
  • Publisher : The Korean Society Of Computer And Information
  • Research Area : Engineering > Computer Science
  • Received : September 23, 2020
  • Accepted : December 9, 2020
  • Published : December 31, 2020

Yoon, Hoijin 1

1협성대학교

Accredited

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.

Citation status

* References for papers published after 2022 are currently being built.

This paper was written with support from the National Research Foundation of Korea.