TAILIEUCHUNG - Giải thuật meta-heuristic giải bài toán người du lịch

Bài viết Giải thuật meta-heuristic giải bài toán người du lịch đề xuất một giải thuật meta-heuristic sử dụng ý tưởng tìm kiếm địa phương để giải bài toán người du lịch. Giải thuật đã được cài đặt, thử nghiệm trên bộ dữ liệu chuẩn lấy từ TSPLIB và thu được những kết quả khá tốt. | TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ ĐẠI HỌC ĐÀ NẴNG - SỐ 12 73 .2013 Quyển 2 GIẢI THUẬT META-HEURISTIC GIẢI BÀI TOÁN NGƯỜI DU LỊCH META-HEURISTIC ALGORITHM FOR SOLVING TRAVELLING SALESMAN PROBLEM Võ Khánh Trung Đặng Đại Thọ Trường Đại học Bách khoa Hà Nội Trường Cao đẳng Công nghệ Thông tin Email trungvokhanh@ Đại học Đà Nẵng Email TÓM TẮT Bài toán người du lịch là một bài toán NP-khó thuộc thể loại tối ưu rời rạc hay tổ hợp được nghiên cứu trong vận trù học hoặc lý thuyết khoa học máy tính. Bài toán được phát biểu như sau cho trước một danh sách các thành phố và khoảng cách giữa chúng tìm chu trình ngắn nhất thăm mỗi thành phố đúng một lần. Hiện nay chưa có giải thuật chính xác nào để giải quyết bài toán này trong trường hợp tổng quát. Vì vậy các giải thuật gần đúng đặc biệt được quan tâm. Trong bài báo này chúng tôi đề xuất một giải thuật meta-heuristic sử dụng ý tưởng tìm kiếm địa phương để giải bài toán người du lịch. Giải thuật đã được cài đặt thử nghiệm trên bộ dữ liệu chuẩn lấy từ TSPLIB và thu được những kết quả khá tốt. Từ khóa bài toán người du lịch NP-khó giải thuật meta-heuristic tìm kiếm cục bộ tối ưu hóa tổ hợp ABSTRACT The travelling salesman problem TSP is an NP-hard problem in combinatorial optimization important in operations research and theoretical computer science. It asks the following question given a list of cities and the distances between each pair of cities what is the shortest possible route that visits each city exactly once and returns to the origin city Hower today there are not exact algorithms to solve it in general case. Therefore heuristic and approximation algorithms are especially interested. This paper proposes a new meta-heuristic algorithm based on local search for solving traveling salesman problem. This algorithm has been installed tested on standard data sets taken from TSPLIB and obtained with quite good results. Key words travelling salesman problem TSP NP-hard problem meta-heuristic algorithm .

• Du lịch
• Bài toán người du lịch
• Giải thuật meta heuristic
• Tối ưu hóa tổ hợp
• Giải thuật tìm kiếm cục bộ
• Lý thuyết khoa học máy tính
• Tóm tắt luận văn Thạc sĩ Kỹ thuật
• Tìm hiểu bài toán người du lịch
• Thuật toán tối ưu đàn kiến ACO
• Luận văn Thạc sĩ Kỹ thuật
• Thuật toán ACO vào bài toán người du lịch
• Bài giảng Toán rời rạc
• Toán rời rạc
• Tài liệu Toán rời rạc
• Phân tích bài toán người du lịch
• Người du lịch
• Bài toán tối ưu tổ hợp
• Chu trình Hamilton
• Đường Hamilton
• Thuật toán nhánh cận giải TSP
• Bài toán người du lịch và thuật toán nhánh cận
• Bài toán tối ưu liên quan đến đường Hamilton
• Phân tích thuật toán
• Thiết kế thuật toán
• Giải thuật toán
• Bài tập giải thuật
• Cài đặt thuật toán
• Thuật toán di truyền
• Giải thuật di truyền
• Công nghệ thông tin
• Ứng dụng thuật toán di truyền
• Khoa học máy tính
• Giải thuật toán di truyền
• Giải thuật toán tối ưu hóa
• Thuật toán tìm kiếm
• Giải thuật tìm kiếm
• Giải thuật di truyền
• Davis' Order Crossover
• Giải quyết bài toán TSP
• Thiết kế vi mạch
• Bài toán tối ưu
• Bài toán tổng quát
• Bài toán cái túi
• Bài toán đóng thùng
• Bài giảng Bài toán tối ưu tổ hợp
• Thuật toán Johnson
• Toán kinh tế
• Phân tích thiết kế giải thuật
• Thuật toán tham lam
• Bài toán đường đi ngắn nhất
• Bài toán cây bao trùm nhỏ nhất
• Bài toán tô màu
• Bài toán các khoảng không giao nhau
• Phương pháp nhánh cận
• Bài toán về Phương pháp nhánh cận
• Meta heuristic
• khoa học điều khiển
• hệ thống kỹ thuật
• điều khiển học
• nghiên cứu tin học
• Lý thuyết thuật toán
• tự động học
• Nguyên lý heuristic
• tài liệu về heuristic
• ứng dụng heuristic
• bài toán phân công công việc
• Trí tuệ nhân tạo
• Lập trình tiến hóa
• Cấu trúc dữ liệu
• Thuật giải di truyền
• Tối ưu số
• Tối ưu tổ hợp