tailieunhanh - Nghiên cứu khung thuật toán chung PSO để giải bài toán TSP

Bài viết nghiên cứu khung thuật toán chung PSO (Particle Swarm Optimization), từ đó xây dựng mô hình toán học và áp dụng để giải bài toán TSP với số đỉnh của bài toán lớn và tối ưu thời gian thực hiện. | TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ Trường Đại học Khoa học ĐH Huế Tập 19 Số 1 2021 NGHIÊN CỨU KHUNG THUẬT TOÁN CHUNG PSO ĐỂ GIẢI BÀI TOÁN TSP Nguyễn Hoàng Hà Khoa Công nghệ thông tin Trường Đại học khoa học Đại học Huế Email nhha@ Ngày nhận bài 27 4 2021 ngày hoàn thành phản biện 12 5 2021 ngày duyệt đăng 02 11 2021 TÓM TẮT Bài toán người du lịch TSP là một bài toán tối ưu tổ hợp kinh điển. Nó thuộc lớp các bài toán NP-khó và không thể giải được trong thời gian đa thức. Trên thực tế người ta thường giải quyết các bài toán này bằng các phương pháp heuristic chúng cho ra nghiệm gần tối ưu. Các phương pháp heuristic bao gồm phương pháp nhánh cận heuristic ACO Ant Colony Optimization thuật toán GA Genetic Algorithm nhưng các phương pháp này chỉ áp dụng cho lớp các bài toán nhỏ khi kích cỡ bài toán lớn thì thời gian chạy của bài toán là rất lớn. Trong bài báo này chúng tôi nghiên cứu khung thuật toán chung PSO Particle Swarm Optimization từ đó xây dựng mô hình toán học và áp dụng để giải bài toán TSP với số đỉnh của bài toán lớn và tối ưu thời gian thực hiện Từ khóa TSP PSO bài toán người du lịch Metaheuristic PSO. 1. MỞ ĐẦU Bài toán tối ưu tổ hợp là bài toán tìm ra tổ hợp tốt nhất trong những tổ hợp có thể tạo ra thỏa mãn yêu cầu cho trước. Với các bài toán tối ưu tổ hợp NP-khó có cỡ nhỏ người ta có thể tìm lời giải tối ưu nhờ phương pháp tìm kiếm vét cạn. Tuy nhiên với các bài toán cỡ lớn thì đến nay chưa thể có thuật toán tìm lời giải đúng với thời gian đa thức nên chỉ có thể tìm lời giải gần đúng hay đủ tốt 1 . Theo cách tiếp cận truyền thống hay là tiếp cận cứng các thuật toán gần đúng phải được chứng minh tính hội tụ hoặc ước lượng được tỷ lệ tối ưu. Với việc đòi hỏi khắt khe về toán học như vậy làm hạn chế số lượng các thuật toán công bố không đáp ứng được nhu cầu ngày càng phong phú và đa dạng trong nghiên .

• Toán học
• Bài toán người du lịch
• Khung thuật toán chung PSO
• Bài toán TSP
• Phương pháp heuristic
• Ứng dụng thuật toán nhánh cận