Cải tiến giải thuật đàn ong nhân tạo để lập lịch đường đi cho robot di động

Bài viết Cải tiến giải thuật đàn ong nhân tạo để lập lịch đường đi cho robot di động trình bày việc cải tiến giải thuật bầy ong nhân tạo (Improved Artificial Bee Colony Algorithm viết tắt, IABC) để tìm ra một hay nhiều tuyến đường khả thi và ngắn nhất cho robot di động di chuyển từ một điểm đầu đến một điểm đích không va chạm, trong môi trường tĩnh 2D có chướng ngại vật.
Nội dung trích xuất từ tài liệu:
Cải tiến giải thuật đàn ong nhân tạo để lập lịch đường đi cho robot di động Tuyển tập Hội nghị Khoa học thường niên năm 2021. ISBN: 978-604-82-5957-0 CẢI TIẾN GIẢI THUẬT ĐÀN ONG NHÂN TẠO ĐỂ LẬP LỊCH ĐƯỜNG ĐI CHO ROBOT DI ĐỘNG Trần Thị Cẩm Giang Trường Đại học Thủy lợi, email: giangttc@tlu.edu.vn 1. GIỚI THIỆU trong môi trường, để xây dựng một đồ thị đỉnh mới hỗ trợ việc tạo đường đi không va Robot di động đang được sử dụng rộng rãi chạm với chướng ngại vật [2]. Đồ thị này trong nhiều lĩnh vực thay thế con người như được xây dựng bằng cách sử dụng trung điểm trong nông nghiệp, công nghiệp, cứu hộ cứu các đường liên kết tự do (Hình 1a). Các điểm nạn, thăm dò, khai phá vũ trụ. Bài toán lập này tương ứng với nút (đỉnh) trong đồ thị và lịch đường đi cho robot di động tìm ra một đường nối giữa chúng là các cung trong đồ hay nhiều tuyến đường khả thi, an toàn và thị (Hình 1b). ngắn để tối ưu hóa sự tiêu thụ năng lượng vẫn là vấn đề then chốt. Mục tiêu đặt ra là tối ưu hóa tiêu thụ nặng lượng và chi phí sử dụng, cũng như tối đa hóa lợi nhuận, hiệu năng và tính chính xác cho robot [1, 2, 3]. Các thuật toán tìm kiếm cổ điển không thể giải quyết được các bài toán này trong thời gian giới hạn, môi trường có chướng ngại a) b) vật. Khi đó việc sử dụng các thuật toán xấp xỉ là một lựa chọn phù hợp để tìm thấy các lời Hình 1. Đồ thị Maklink giải gần tối ưu. Bài báo này cải tiến giải thuật 2.2. Giải thuật tối ưu hóa đàn ong nhân tạo bầy ong nhân tạo (Improved Artificial Bee Colony Algorithm viết tắt, IABC) để tìm ra Thuật toán được đề xuất bởi Karaboga vào một hay nhiều tuyến đường khả thi và ngắn năm 2005 [1]. Ý tưởng của thuật toán là các nhất cho robot di động di chuyển từ một điểm nguồn thức ăn, trong quá trình tìm kiếm, đầu đến một điểm đích không va chạm, trong những con ong sẽ thay đổi vị trí nguồn thức môi trường tĩnh 2D có chướng ngại vật. Hiệu ăn thành vị trí nguồn thức ăn tốt nhất. Giải quả của giải thuật IABC được so sánh với thuật ABC có ba loại ong: ong làm việc, ong giải thuật trước đó ABC dưới nền tảng sử giám sát và ong trinh sát. Những con ong làm dụng phân rã bản đồ bằng giải thuật Maklink. việc sẽ tìm kiếm các nguồn thức ăn, nếu tìm Các kết quả thực nghiệm đã chứng tỏ hiệu được thức ăn thì các chú sẽ chia sẻ thông tin quả của giải thuật đề xuất IABC tốt hơn giải về nguồn thức ăn đó cho ong giám sát. Ở tổ thuật ABC cơ bản [1]. ong giám sát đang chờ thông báo về vị trí và số mật của nguồn thức ăn nó vừa tìm được. 2. KIẾN THỨC NỀN TẢNG Ong quan sát sẽ chọn nguồn thức ăn tốt từ những nguồn thức ăn được tìm thấy. Nguồn 2.1. Đồ thị Maklink thức ăn tốt hơn thì sẽ được ong quan sát lựa Phương pháp mô hình hóa môi trường chọn hơn. Ong trinh sát có nhiệm vụ loại bỏ Maklink là một phương pháp tiếp cận theo nguồn thức ăn không thể cải tiến và tìm kiếm không gian trống giữa các chướng ngại vật nguồn thức ăn mới [1]. 68 Tuyển tập Hội nghị Khoa học thường niên năm 2021. ISBN: 978-604-82-5957-0 Hàm đánh giá của mỗi nguồn thức ăn được Những điểm cải tiến: tính như sau:  Tìm n đường đi ngẫu nhiên từ điểm đầu  Tìm nguồn thức ăn mới: đến điểm kết thúc. Tính độ dài đường đi, tính vij = xij + Øij(xij – kij) fitness cho mỗi đường đi  Tính xác suất của mỗi đường đi.  Đưa ra các giải pháp mới cho các ong fit trinh sát. So sánh độ dài đường đi và lưu lại Probi = nguồn thức ăn tốt nhất. fit  Tìm đường đi 4. KẾT QUẢ THỰC NGHIỆM xij= minj + α(maxj – minj)  Tính giá trị hàm đánh giá: Bài báo thực hiện ba thực nghiệm sau để  1 phân tích hiệu quả của giải thuật ABC và 1  fi ( fi  0 ) IABC dựa vào độ đo thời gian chạy trung  fiti=  bình của giải thuật (Ttb), độ dài trung bình  1 ( fi  0 ) (Ttb) và tỉ lệ thành công trung bình (Tltb): 1 | fi | Thực nghiệm 1: Phân tích sự ảnh hưởng Trong đó: của hình dạng chướng ngại vật. xij: đường đi được chọn để thay đổi; Thực nghiệm 2: Phân tích sự ảnh hưởng kij: điểm lân cận; của mật độ con ong. Ø: giá trị ngẫu nhiên trong khoảng [-1,1]; 4.1. Ảnh hưởng hình dạng chướng ngại vật fi: chi phí hàm của mục tiêu; Có 5 bộ dữ liệu khác nhau được sự dụng fiti: giá trị fitness của nguồn thức ăn thứ i; trong thực nghiệm này. Tuy nhiên, môi maxj và minj : ràng buộc trê ...