zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Luận Văn - Báo Cáo

» Báo cáo khoa học

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"

Chia sẻ: Nguyễn Phương Hà Linh Nguyễn Phương Hà Linh | Ngày: | Loại File: PDF | Số trang:8

Báo xấu

256
lượt xem 32
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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"

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 Đà Nẵng 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ư là một nguồn cảm hứng cho việc thiết kế các thuật toán cho các giải pháp tối ưu hóa và phân phối kiểm soát các vấn đề. Các ý tưởng chính là việc tự tổ chức phối hợp giữa các nguyên tắc cho phép với hành vi thực sự của loài kiến có thể được triển khai để giải quyết vấn đề về máy tính. Một số khía cạnh khác nhau ở các hành vi ứng xử của các đàn kiến có cảm hứng cho các thuật toán kiến khác nhau. 9
TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, ĐẠI HỌC ĐÀ NẴNG - SỐ 5(40).2010 2. Khám phá hành vi của đàn kiến và sự tối ưu hoá Những hình ảnh nhận thức đặc biệt của đàn kiến chỉ đơn giản là sự phát triển và hoàn toàn mò mẫm. Trong thực tế, một điều quan trọng trong nghiên cứu về loài kiến là hành vi liên lạc giữa các con kiến, hoặc giữa các cá nhân với môi trường, được dựa trên việc sử dụng các sản phẩm hóa chất của các loài kiến. Các hóa chất đó được gọi là pheromones. a. Thí nghiệm chiếc cầu đôi Sự gửi vết mùi pheromones và hành vi của một số loài kiến đã được điều tra kiểm soát trong các thử nghiệm của một số nhà nghiên cứu. Một trong những thí nghiệm nổi bật nhất là thí nghiệm được thiết kế và đi vào hoạt động của Deneubourg và các đồng nghiệp của ông [1], người mà đã sử dụng một cây cầu nối tổ của đàn kiến với nguồn thức ăn. Họ chạy các thử nghiệm với tỉ lệ r = l l / l s giữa độ dài hai nhánh của cây cầu, ll là độ dài của nhánh dài và l s là độ dài của nhánh ngắn hơn. Trong thử nghiệm đầu tiên với cây cầu có hai nhánh chiều dài bằng nhau (r = 1; xem hình 1.1a). 15cm 600 Tổ kiến Thức ăn (a ) Tổ kiến Thức ăn 1 2 . (b) Hình 1. Thí nghiệm chiếc cầu đôi. (a) Hai nhánh có kích thước bằng nhau, (b) Một nhánh có kích thước gấp đôi nhánh kia Khi bắt đầu, trên 2 nhánh của cây cầu đều chưa có pheromones. Do đó, các con kiến có thể chọn một trong các nhánh với cùng một xác suất. Tuy nhiên, do sự lựa chọn là ngẫu nhiên lên sau một thời gian số lượng kiến đi trên những chi nhánh sẽ là khác nhau. Bởi vì loài kiến sẽ gửi pheromones trong khi di chuyển, dần dần số lượng pheromones trên những nhánh cũng sẽ khác nhau, điều này càng kích thích thêm đàn kiến sẽ lựa chọn nhánh có lượng mùi pheromones lớn, và như vậy đến một thời gian nào đó tất cả đàn kiến sẽ hội tụ về cùng một nhánh. 10
TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, ĐẠI HỌC ĐÀ NẴNG - SỐ 5(40).2010 b. Một mô hình ngẫu nhiên Trong mô hình này, ψ là mỗi giây đàn kiến băng qua cầu trong mỗi hướng ở một tốc độ hằng số v (cm/s), một trong những đơn vị gửi pheromones trên các nhánh. Cho dộ dài ll và l s (cm) trong các nhánh dài và ngắn, một con kiến chọn nhánh ngắn sẽ đi ngang qua nó trong khoảng thời gian là ts = ls / v (giây), trong khi kiến lựa chọn Chi nhánh dài sẽ sử dụng r.ts giây, với r=ll /ls . Xác suất pia(t) là xác xuất tại điểm i (i Є {1,2}) (xem hình 1.1b) kiến chọn nhánh a (a Є {s,l}), trong đó s, l là các chi nhánh ngắn và dài tương ứng, tại thời điểm t tổng số lượng pheromones φia(t) được thiết lập trên các chi nhánh, là tổng lượng pheromones mà các loài kiến để lại trên các chi nhánh cho đến thời gian t đó. Trong mô hình này đàn kiến gửi lại vết mùi pheromones của họ trên cả hai đường đi: từ tổ đến nguồn thức ăn và quay trở lại tổ. Sự di chuyển này là một hành vi ứng xử cần thiết để có được sự hội tụ của đàn kiến hướng về nhánh ngắn. 2. Đàn kiến nhân tạo Qua thử nghiệm chiếc cầu đôi cho thấy rõ ràng có khả năng xây dựng được tối ưu hóa đàn kiến: Thông tin để tìm ra con đường ngắn nhất giữa 2 điểm có thể dựa vào quy tắc xác xuất. Có 2 khía cạnh bất đồng quan trọng: - Phạm vi xem xét các hành vi của hệ thống là trung bình, và không phải những hành vi ứng xử tuân theo biến thiên ngẫu nhiên của đàn kiến là duy nhất. - Đây là thí nghiệm trên những thời gian không liên tục, trong khi trước đó mô hình xét trong một thời gian liên tục. 3. Kiến nhân tạo và chi phí tối thiểu trên đường đi Những hành vi là: 1. Giải pháp xây dựng theo hướng xác xuất bởi vết mùi pheromones, với sự cập nhật pheromones nhanh 2. Thuyết tiền định con đường quay trở lại với việc loại bỏ vòng lặp và sự cập nhật pheromones 3. Đánh giá về chất lượng của các giải pháp tạo ra và sử dụng các giải pháp chất lượng trong việc xác định số lượng pheromones đã gửi lại. Xác xuất chọn đỉnh tiếp theo của đàn kiến và giải pháp xây dựng. S-ACO đàn kiến có hai phương thức hoạt động: chuyển tiếp và quay trở lại. Thuyết tiền định về hành vi quay trở về tổ của đàn kiến và sự cập nhật pheromones. Việc sử dụng một bộ nhớ rõ ràng cho phép một con kiến có thể trở lại con đường mà nó đã đi trong khi tìm kiếm đến đỉnh đích. Cơ sở giải pháp hiệu quả của sự cập nhập pheromones. Trong S-ACO đàn kiến nhớ các đỉnh mà nó đi qua trong quá trình tìm nguồn thức ăn, cũng như các chi phí trên các cạnh đã qua nếu biểu đồ có trọng số. 11
TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, ĐẠI HỌC ĐÀ NẴNG - SỐ 5(40).2010 Sự bay hơi của Pheromones. Trong đàn kiến thực, lượng pheromone giảm theo thời gian vì có sự bay hơi. Để biểu diễn mỗi cạnh (i,j) của đồ thị G =(N,A) chúng tôi dùng một biến gọi là τij gọi là vết mùi nhân tạo, để rút ngắn lượng mùi pheromones trong thời gian tiếp theo. Vết mùi pheromones được tạo và cập nhập bởi đàn kiến. Ở những phương thức tính số lượng vết mùi pheromones trên các cạnh chỉ được tính theo tỷ lệ, ước tính của đàn kiến. Hành vi tìm kiếm đường đi của đàn kiến Mỗi kiến, bắt đầu từ một đỉnh, một giải pháp cho vấn đề ứng dụng từng bước được giải quyết. Một con kiến k tại một đỉnh i bất kì sử dụng vết mùi pheromones τ ij để tính xác suất chọn đỉnh j như sau: τα ⎧ ij ⎪∑ , if j∈ Ν k (1.8) α i k p ij = ⎨ k τ il l∈ N i ⎪ 0, ⎩ if j∉ Ν k i Trong đó N Ik là vùng lân cận của kiến k ở đỉnh i trong S-ACO vùng lân cận của đỉnh i là tất cả các đỉnh kết nối trực tiếp đến đỉnh i trong đồ thị G =(N,A), ngoại trừ tất cả các đỉnh trước (ví dụ, các đỉnh trước khi di chuyển đến đỉnh i của kiến). Đường đi về tổ và sự cập nhập vết mùi. Khi đạt tới đỉnh đích, kiến thực hiện quá trình quay về tổ trên cùng con đường đến nguồn thực phẩm. Bổ sung tính năng này là, trước khi bắt đầu quá trình quay về tổ, kiến sẽ loại bỏ những đường đi rơi vào tình trạng vòng lặp mà nó đã gặp phải trên đường đi tìm đến nguồn thức ăn. Trong thời gian quay trở về tổ con kiến thứ k sẽ để lại một lượng ∆τk pheromones trên các cạnh mà nó đi qua. Trong đó, nếu kiến thứ k quay trở về tổ trên cạnh (i,j), thì giá trị τ ij pheromones sẽ thay đổi như sau: τ ij ← τ ij + ∆τ k (1.9) Một khía cạnh quan trọng vẫn là sự lựa chọn của ∆τk . Trong những trường hợp đơn giản nhất, giá trị của ∆τk là một hằng số cho tất cả các loài kiến. Sự bay hơi của vết mùi pheromones.Vết mùi pheromones bay hơi có thể được coi như là một kỹ thuật thăm dò nhanh chóng của đàn kiến tìm điểm cực thuận tốt trên đường đi. Sau đó mỗi kiến thứ k di chuyển đến một đỉnh kế tiếp nào đó tuỳ theo hành vi tìm kiếm của kiến đã được mô tả ở trên, lượng bay hơi của pheromones được áp dụng theo công thức sau đây với tất cả các cung: τij =(1- ρ)τij , □ (i,j) ∈ A , p ∈ (0,1) ( 1.10) 12
TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, ĐẠI HỌC ĐÀ NẴNG - SỐ 5(40).2010 Trong đó tham số ρ(0,1]. Sau khi sự bay hơi pheromones đã được áp dụng cho tất cả các cạnh, số lượng pheromones ∆τk sẽ được thêm vào các cạnh. 2. Các ACO METAHEURISTIC 2.1. Trình bày vấn đề Chúng tôi xem xét các vấn đề cực tiểu hoá ( S , f , Ω ). Trong đó S là nơi tập hợp các giải pháp được xét, f là mục tiêu của chức năng quan trọng, trong đó quy định giá trị của chức năng đó là một hằng số f ( s, t ) của mỗi giải pháp s ∈ S và Ω(t ) là một tập hợp các khó khăn (sự bắt ép, sự đè nén). 2.2. Hành vi của đàn kiến Đó là giải pháp xây dựng dựa vào di chuyển có thể được trên đồ thị GC = (C , L) trong đó , C: Là các nút trên đồ thị, L là tập hợp đầy đủ các thành phần kết nối của C. Các vấn đề có điều kiện Ω(t) được đàn kiến tìm kiếm xây dựng lên. Các thành phần ci ∈ C và các kết nối lij ∈ L có thể lên kết với nhau ở vết mùi pheromones τ . 3. Phân tích giải thuật Thật sự, một thuật toán ACO có thể được hình dung như sự tác động của ba thủ [2] tục : ConstructAntsSolutions, UpdatePheromones, và DaemonActions. ConstructAntsSolutions (Giải pháp xây dựng các loài kiến) là quản lý một đàn kiến xảy ra đồng thời và không đồng bộ của các vấn đề cần xem xét của đàn kiến, bằng cách di chuyển qua các đỉnh bên cạnh của đồ thị GC. UpdatePheromones (Cập nhật pheromones) là quá trình mà vết mùi pheromones được sửa đổi. . DaemonActions (Những hành động) thủ tục được sử dụng để thực hiện những hành động tập trung mà điều này không thể thực hiện bởi những con kiến riêng lẻ. Procedure ACOMetaheuristic ScheduleActivities ConstructAntsSolutions UpdatePheromones DaemonActions % optionnal End-ScheduleActivities End-procedure. 13
TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, ĐẠI HỌC ĐÀ NẴNG - SỐ 5(40).2010 Sơ đồ thuật toán ACO cho bài toán TSP B ắ t đầ u Định vị kiến ngẫu nhiên trong những thành phố trên lưới và cất thành phố hiện thời trong danh sách visited Xác định xác suất có thể như là đến thành Sai phố nào tiếp theo Số vòng lặp tối đa đã được thực Di chuyển tới thành hiện Đúng phố tiếp theo và đặt thành phố này trong danh sách visited Kết thúc Tất cả các thành Sai phố đã được ghé thăm Đúng Ghi lại độ dài của cuộc hành Xác định hành trình ngắn trình và xoá danh sách nhất từ trước đến nay và visited cập nhật pheromone Hình 3. Sơ đồ thuật toán ACO cho bài toán TSP 4. Đề xuất ứng dụng Bài toán người du lịch (TSP) là một trong những bài toán kinh điển và được đầu tư nghiên cứu trong một thời gian dài. Nó góp phần quan trọng vào việc nghiên cứu giải thuật ACO: Các giải thuật ACO nguyên thủy và những cải tiến của giải thuật này về sau đều được áp dụng mô phỏng bởi bài toán người du lịch. 5. Triển khai ứng dụng Bài toán người di lịch có thể được biểu diễn khái quát bằng một đồ thị có trọng số G(N,A) với N là tâp hợp các nút mô tả cho các thành phố, A là tập hợp các cung mô tả đoạn đường giữa hai thành phố. 14
TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, ĐẠI HỌC ĐÀ NẴNG - SỐ 5(40).2010 Mỗi cung (i,j) thuộc A được gán một giá trị dij mô tả chiều dài của đường đi giữa hai đỉnh i, j với i, j thuộc N. Mục đích cuối cùng của bài toán người di lịch chính là tìm ra chu trình Hamilton ngắn nhất của đồ thị G có n đỉnh với n là số thành phố mà người di lịch phải đi qua. Như vậy, kết quả tốt nhất của bài toán chính là một hoán vị π của các đỉnh {1, 2,…, n}, sao cho chiều dài f(π) là nhỏ nhất. f(π) được tính theo công thức sau: 5.1. Giải thuật ACO cho bài toán người di lịch Việc xây dựng một đồ thị G=(C, L) tương ứng với việc xây dựng đồ thị G(N,A) ở trên với C=N và L=A. Trong đó tập hợp các đường đi của đồ thị tương ứng với tập hợp các hành trình từng phần có thể có và giá trị Ω nhằm ràng buộc rằng con kiến chỉ tìm những đường đi tương ứng với các hoán vị của các thành phố. Ở đây bài toán tìm đường đi ngắn nhất qua tất cả các đỉnh của đồ thị mỗi đỉnh một lần có mối liên hệ mật thiết với bài toán tìm đường đi ngắn nhất của con kiến. Hình 3. Một con kiến đang ở thành phố i muốn đến thành phố tiếp theo sẽ dựa trên giá trị dấu τij và giá trị Heuristic ηij trên cung nối thành phố i với thành phố j mà con kiến chưa đến. ACO Metaheuristic tĩnh procedure ACOMetaheuristicStatic set parameters, initialize pheromone trails while (termination condition not met) do ConstructAntsSolutions ApplyLocalSearch % tùychọn UpdatePheromones end end 5.2. Hệ thông kiến (Ant System – AS) và những cải tiến Khả năng mà con kiến k có thể đi từ thành phố hiện tại i đến thành phố j được tính theo công thức như sau[3]: k nếu j ∈ Ν i 15
TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, ĐẠI HỌC ĐÀ NẴNG - SỐ 5(40).2010 với ηij=1/ d ij là giá trị Heuristic có thể có, α và β là hai tham số quyết định sự ảnh hưởng lẫn nhau của các pheromones trên các hành trình được xây dựng và các thông tin Heuristic. Nik là những thành phố mà con kiến k có thể đi đến, từ vị trí hiện tại là thành phố i ( Đây là các thành phố mà con kiến này chưa viếng thăm bao giờ). Với tập luật như trên, khả năng lựa chọn một cung (i,j) tỉ lệ thuận với giá trị của các pheromones có liên quan τij và của giá trị heuristic ηij. Sau khi tất cá các hành trình được xây dựng, các pheromone bắt đầu được cập nhật. Việc cập nhật được thực hiện bằng cách giảm mật độ pheromone trên tất cả các cung của đồ thị, sau đó thêm pheromone trên các hành trình mà con kiến đã đi qua. Việc xóa các dấu được thực hiện như sau: τij ← (1-ρ)τij, □(i,j) ∈ L (3.3) với 0

CÓ THỂ BẠN MUỐN DOWNLOAD

LV.01: Bộ Luận Văn Thạc Sĩ Quản Trị Kinh Doanh MBA

165 tài liệu

2073 lượt tải

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.