tailieunhanh - Báo cáo khoa học: " ỨNG DỤNG GIẢI THUẬT META-HEURISTIC TRONG BÀI TOÁN TÌM ĐƯỜNG ĐI NGẮN NHẤT"

Bài toán tìm kiếm được xem là bài toán được nhiều người quan tâm, đặc biệt là tìm kiếm tối ưu toàn cục. Một thuật toán được xem là lý thuyết vững chắc trong việc giải các bài toán tìm kiếm tối ưu toàn cục đã có nhiều ứng dụng thực tế như: tìm kiếm các trang web cần tìm trên mạng, kế hoạch sắp xếp thời khóa biểu cho các y tá trong bệnh viện, tìm kiếm đường đi tối ưu cho những người lái xe hơi đấy là thuật toán kiến (ACS – Ant Colony Search hoặc. | TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ ĐẠI HỌC ĐÀ NẴNG - SỐ 5 40 .2010 ỨNG DỤNG GIẢI THUẬT META-HEURISTIC TRONG BÀI TOÁN TÌM ĐƯỜNG ĐI NGẮN NHẤT APPLICATION OF META-HEURISTIC ALGORITHM FOR A SEARCH OF SHORTEST PATH Đoàn Duy Bình Trường Đại học Sư phạm Đại học Đà Nang TÓM TẮT Bài toán tìm kiếm được xem là bài toán được nhiều người quan tâm đặc biệt là tìm kiếm tối ưu toàn cục. Một thuật toán được xem là lý thuyết vững chắc trong việc giải các bài toán tìm kiếm tối ưu toàn cục đã có nhiều ứng dụng thực tế như tìm kiếm các trang web cần tìm trên mạng kế hoạch sắp xếp thời khóa biểu cho các y tá trong bệnh viện tìm kiếm đường đi tối ưu cho những người lái xe hơi. đấy là thuật toán kiến ACS - Ant Colony Search hoặc ACO - Ant Colony Optimization . Trong bài báo này chúng tôi giải thuật Meta-Heuristic và đặc biệt là thuật toán kiến để thực hiện bài toán tìm kiếm. Thuật toán kiến mô phỏng hành vi của đàn kiến trong tự nhiên nhằm tìm kiếm đường đi ngắn nhất giữa tổ kiến và nguồn thức ăn dựa trên mật độ mùi - Pheromone mà các con kiến để lại trên đường đi. ABSTRACT Search problem is a problem that concerns many people especially in the field of global optimal search. An algorithm is considered to be a well-established theory in solving problems of globally optimal search and it has many practical applications such as searching for pages needed to be found on the web planning a schedule for the nurses in hospitals finding an optimal way for people to drive etc. That is an ant algorithm ACS - Ant Colony Search or ACO - Ant Colony Optimization . In this paper we introduce the Meta-Heuristic algorithm especially ACO to make search problems. The Ant Algorithm describes the behaviour of natural ants to find the shortest way between food sources and density based on the pheromone that the ants left on the road. 1. Giới thiệu về ACO ANT COLONY OPTIMIZATION Các lĩnh vực nghiên cứu thuật toán kiến đã thu được từ những quan sát mô hình hành vi thực tế của loài kiến và sử dụng các mô hình này như