ÁP DỤNG THUẬT GIẢI DI TRUYỀN VỚI THÔNG TIN THỐNG KÊ XÁC SUẤT GIẢI QUYẾT BÀI TOÁN TÌM CHU TRÌNH HAMILTON

 

Nguyễn Thanh Hùng^*, Hoàng Kiếm^**

* Trường Phổ thông Năng Khiếu - ÐHQG tp.HCM

** Trung tâm phát triển công nghệ thông tin - ÐHQG tp.HCM

 

Tóm tắt:

 

Bài toán tìm kiếm chu trình Hamilton là một trong số những bài toán quan trọng nhất trong tập bài toán NP đầy đủ. Ðã có rất nhiều nghiên cứu tập trung vào tìm kiếm lời giải cho bài toán, đặc biệt là lời giải gần đúng, để áp dụng vào các tình huống cụ thể trong thực tế.

Chúng tôi đề xuất trong bài báo này là một hướng tiếp cận mới cho bài toán này, sử dụng thuật toán Genetics kết hợp với thông tin thống kê của tần suất các cung sẽ xuất hiện trong chu trình tối ưu. Chu trình tốt nhất sẽ được tổng hợp từ thông tin thu lượm từ các thế hệ qua cả quát trình biến đổi của quần thể. Chúng tôi đánh giá cách tiếp cận mới với nhiều bài toán cụ thể khác nhau và so sánh với những cách tiếp cận đã được nghiên cứu. Kết quả thực nghiệm cho thấy cách tiếp cận này hiểu quả hơn với cách tiếp cận chỉ dùng thuật toán Genetics, từ đó mở ra một hướng mới để giải quyết các bài toán tìm kiếm gần đúng chu trình Hamilton tối ưu.

 

 

APPLYING GENETICS ALGORITHM AND STATISTICAL PROBABILITY RESULTS TO SOLVE HAMILTON CYCLE PROBLEM

 

Nguyen Thanh Hung^*, Hoang Kiem^**

* High School for the gifted students - VNU-HCM

** Center of Information Technology Development - VNU-HCM

Abstract:

 

Finding Hamilton cycle is one of the most important NP-complete problems. Several studies, used in real problems, have been conducted to solve it, especially in heuristic solutions. In this paper, we propose a new approach that combines Genetics algorithm and appearance probabilities of edges in the optimal cycle. The final solution will be selected from results of generations gained in the whole population evolution. Our proposal is evaluated in various practical problems and compared with previous works. The experiment results prove that our approach is more efficient than those using either Genetics algorithm or statistical probability results. Hence, it proposes a new approach to solve heuristically problems of finding optimal Hamilton cycle.

          Keywords: Travelling Salesman Problem, Hamilton cycle, Genetics algorithm, statistical probability