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.
Nội dung trích xuất từ tài liệu:
Nghiên cứu khung thuật toán chung PSO để giải bài toán TSPTẠ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@husc.edu.vn 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ácbà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ứcnê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 đúngphả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ỏikhắ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 cứu và ứng dụng. Đểkhắc phục tình trạng này, người ta dùng tiếp cận đủ tốt để xây dựng các thuật toán tốiưu mềm[1]. 25Nghiên cứu khung thuật toán chung PSO để giải bài toán TSP Bài toán người du lịch (TSP: Traveling Salesman Problem) có thể biểu diễn thànhmột đồ thị, trong đó các thành phố là các đỉnh, các con đường đi lại giữa các thành phốlà các cạnh, đồng thời khoảng cách giữa các thành phố là trọng số tương ứng của cạnhnối chúng, nếu giữa hai thành phố không có đường đi trực tiếp mà phải thông qua mộtthành phố khác thì ta gán trọng số của cạnh đó là số lớn nhất có thể. Khi đó, bài toánngười du lịch trở thành bài toán tìm một chu trình Hamilton ngắn nhất, và lộ trình củangười du lịch chính là chu trình Hamilton ngắn nhất. Nếu dùng phương pháp vét cạn để giải bái toán TSP thì ta luôn cho ta một đápán tối ưu nhất, tuy nhiên độ phức tạp của nó là quá cao (O(n!)). Vì vậy, để giải bài toánnày người ta thường dùng các thuật toán tối ưu mềm. Năm 2017, tác giả Đỗ Như An [2] đã nghiên cứu thuật toán nhánh-cận để giải bàitoán TSP nhưng độ phức tạp thời gian tính toán dạng hàm mũ. Vì vậy, nếu đưa thuậttoán vào sử dụng cũng chưa đáp ứng được yêu cầu thực tế. Thuật toán di truyền [3] là thuật toán metaheuristic, metaheuristic là một cáchgọi chung cho các thuật toán heuristic trong việc giải quyết các bài toán tối ưu tổ hợp.Abid Hussain [4] và các đồng nghiệp đã cải tiến thuật toán GA để giải bài toán TSPnhưng bài báo chỉ tập trung vào đánh giá các phương pháp cải tiến chưa đưa ra được sốđỉnh tối đa và thời gian chạy của thuật toán. Omar [5] và các đồng nghệp đã cải tiếnthuật toán GA để giải bài toán TSP nhưng chỉ mô phỏng được tối đa 20 đỉnh. PSO (Particle Swarm Optimization) là khung thuật toán chung dựa trên kinhnghiệm của bầy đàn được đề xuất bởi bởi Kennedy và Eberhat [5]. Nó là một khungthuật toán thông minh dựa trên bầy đàn, mô phỏng lại hành vi xã hội của bầy chim hayđàn cá khi đi tìm nguồn thức ăn. Một cá thể (particle) được thể hiện trong PSO tương tự như một con chim hoặcmột con cá tìm kiếm thức ăn trong không gian tìm kiếm của nó. Sự di chuyển của mỗicá thể là sự kết hợp giữa vận tốc và hướng di chuyển. Vị trí của mỗi cá thể tại bất kỳthời điểm nào cũng bị ảnh hưởng bởi vị trí tốt nhất của nó và vị trí tốt nhất của cả bầyđàn. Hiệu quả đạt được của một cá thể được xác định bởi một giá trị thích nghi, giá trịnày được xác định phụ thuộc vào từng bài toán [5]. Trong PSO, quần thể bao gồm các cá thể trong không gian của bài toán. Các cáthể được khởi tạo một cách ngẫu nhiên. Mỗi cá thể sẽ có một giá trị thích nghi, giá trịnày được xác định bởi một hàm thích nghi để tối ưu trong mỗi thế hệ. Trong mỗi thế hệ,mỗi cá thể thay đổi vận tốc và thay đổi vị trí của nó theo thời gian. Dựa vào giá trị thíchnghi, mỗi cá thể tìm ra giải pháp tối ưu cục bộ trong không gian tìm kiếm nhiều chiều.Sau đó, giải pháp tối ưu cục bộ được so sánh với giải pháp tối ưu toàn cục của cả bầyđàn để cập nhật lại giá trị cho giải pháp tối ưu toàn cục. Dựa vào giải pháp tối ưu toàn ...