Enhanced genetic algorithm with simulated annealing in solving travelling salesman problem

• 第一著者: Pang, Li Sim
• フォーマット: 学位論文
• 言語: 英語
• 出版事項: 2010
• 主題: QA75 Electronic computers. Computer science
• オンライン･アクセス: http://eprints.utm.my/16395/7/PangLiSimMFSKSM2010.pdf

Optimization is defined as a process of finding the best solution in the most effective way of a given problem. Generally, this means solving problems by choosing the values of real or integer variables from a given set of values in order to minimize or maximize a real function. Traveling Salesman Problem (TSP) is a one of the famous optimization problem in finding the shortest distance that passes through a given number of cities (each exactly once) and return to the starting point. This study proposed an enhanced Genetic Algorithm (GA) with Simulated Annealing (SA) which can be implemented and solve TSP. GA may have the advantages in finding a solution in a very short of time when dealing with small dataset. But, GA still needs to overcome its long computation time when handling large number datasets. Besides that, GA lacks in local search ability and sometimes it may have premature convergence. On the other hand, SA often used to find global solution but required a large computation time. The proposed algorithm can speed up the computation time while giving an optimum solution, which is the shortest distance compared to the conventional GA. The proposed method gives a better result in terms of shortest distance and smaller computation time when dealing five datasets from TSPLIB. The results have proved that the proposed method is convincing compared to other related method.