Solving the traveling salesman problem using genetic algorithm on Nvidia Cuda GPU

The Traveling Salesman Problem (TSP) is one of the most intensively studied problems in computational mathematics. TSP has been used as a benchmark for many new algorithm ideas and optimization methods. Exact method for solving TSP, which has practically acceptable running time, has not been found....

وصف كامل

محفوظ في:
التفاصيل البيبلوغرافية
المؤلف الرئيسي: Quang, Mau Bach.
مؤلفون آخرون: Low Yoke Hean, Malcolm
التنسيق: Final Year Project
اللغة:English
منشور في: 2011
الموضوعات:
الوصول للمادة أونلاين:http://hdl.handle.net/10356/44993
الوسوم: إضافة وسم
لا توجد وسوم, كن أول من يضع وسما على هذه التسجيلة!
الوصف
الملخص:The Traveling Salesman Problem (TSP) is one of the most intensively studied problems in computational mathematics. TSP has been used as a benchmark for many new algorithm ideas and optimization methods. Exact method for solving TSP, which has practically acceptable running time, has not been found. Therefore, various heuristics and approximation algorithms, which quickly yield good solutions, have been devised. Among those algorithms, the Genetic Algorithm (GA), modeled after the process of natural evolution, can be quickly implemented and deployed. However, GA does not utilize explicitly the knowledge of the problem on searching for the solutions. Consequently, hybrid methods that combine GA with other local search techniques have been attempted.