Ứng dụng giải thuật di truyền tìm đường đi tối ưu trong giao thông đường thủy tại tỉnh Vĩnh Long

Abstract

Giải thuật di truyền và bài toán đường đi ngắn nhất là một trong số các vấn đề mang tính thực tiễn cao trong toán học và tin học. Trong đó, giải thuật di truyền là phương pháp tìm kiếm mô phỏng quá trình sinh tồn, tiến hóa của tự nhiên. Đó là sự chọn lọc các cá thể có độ thích nghi cao, loại bỏ các cá thể có độ thích nghi thấp tiến tới sàng lọc ra các cá thể tốt nhất. Bài toán đường đi ngắn nhất là vấn đề tìm đường đi giữa hai đỉnh trong một đồ thị hay giữa hai địa điểm trong mạng giao thông với điều kiện chi phí là tối thiểu. Trên thực tế, vấn đề này đã được giải quyết bằng một số thuật toán cổ điển. Tuy nhiên, việc tìm đường đi giữa hai địa điểm với ràng buộc phải qua một số địa điểm khác các giải thuật cổ điển này chưa giải quyết được. Do đó, trong khuôn khổ luận văn này, tôi sẽ đề xuất giải thuật di truyền để giải quyết bài toán vừa nêu và ứng dụng vào thực tiễn tìm đường đi tối ưu trong mạng giao thông đường thủy tỉnh Vĩnh Long.