Chương 1. TONG QUAN 3 minh bay đàn Giải Thuật Tối Ưu Hóa Dan Kiến (Ant Colony Optimization, ACO) (4). Và sự kết hợp giữa thông minh bay đàn và tim kiếm cục bộ ACO++ (BI. Chagas va Wagner [3|] đã chi ra rang ACO++ vượt trội hon so với các thuật toán khác trong hơn 90% số lượng trường hợp (trường hợp đánh giá).
Dé đạt được những kết quả xuất sắc này, ACO++ trải qua quá trình điều chỉnh chỉ tiết dé xác định cấu hình siêu tham số phù hợp cho mỗi nhóm trường hợp trong benchmark (bộ đánh giá) của ThOP.4 Mục đích nghiên cứu Trong công trình này, chúng tôi đề xuất một thuật toán cải tiến dựa trên ACO++, Giải Thuật Đàn Kiến Tự Thích Ứng (Self-Adaptive Ant System, SAAS) có khả năng điều chỉnh động các tham số của mình theo đặc trưng của mỗi trường hợp và quá trình tìm kiếm. Sự cải tiễn này giúp giảm thiểu tính tốn thời gian và phi thực tế của việc điều chỉnh nhiều cấu hình siêu tham số. Thuật toán của chúng tôi sử dụng một cấu hình duy nhất cho toàn bộ trường hợp trong ThOP benchmark, đồng thời mang lại hiệu suất vượt tri. Đề cải tiến, chúng tôi tích hợp bốn kỹ thuật vào ACO++.
Hai cơ chế kiểm soát tham sé, tự thích ứng (self-adaptive) và thích ứng (adaptive), giúp cải thiện khả năng thích nghi của thuật toán. Hai kỹ thuật Bay hơi lười biếng và Phân cụm thứ bậc giúp giảm độ phức tạp về thời gian. Cơ chế tự thích ứng sử dụng chiến lược tiễn hóa (Evolution Strategy, ES), trong khi đó cơ chế thích ứng sử dụng thông tin sự đa dạng lợi nhuận đề điều chỉnh các tham số (Bảng B. Các tham số được điều chỉnh đồng thời với quá trình tìm kiếm lời giải.
Phân cụm phân cấp được sử dụng đề giảm chỉ phí xây dựng các tuyên đường. Bay hơi lười biếng được sử dụng để giảm thời gian cần thiết để bay hơi dấu vết pheromone của kiên. Chương 2 KIÊN THỨC NEN TANG Ở chương này, chúng tôi sẽ cung cấp các kiến thức được sử dụng xuyên suốt trong khóa luận này. 1) chúng tôi sẽ mô tả chỉ tiết bài toán mà chúng tôi giải quyết, bài toán Điều Hướng Thu Thập.
Chúng tôi sẽ trình bày thế nào là một bài toán tối ưu hóa đa thành phần, các bài toán con, các mục tiêu đặt ra khi giải quyết bài toán này.2, chúng tôi sẽ trình bày các kiến thức nền tảng về giải thuật tối ưu hóa đàn kiến và biến thể MAX-MIN ACO của nó, thuật toán mà chúng tôi sử dụng làm nền tang dé phát triển nên thuật toán chúng tôi đề xuất. Bên cạnh đó chúng tôi trình bày các kiến thức cơ sở của các phương pháp chúng tôi sử dụng để thích ứng các tham số (phan 2.5) và làm giảm độ phức tạp của thuật toán (phan 2.1 Bài toán Điều Hướng Thu Thập 2.1 Mô tả bài toán Bài toán chúng tôi giải quyết ở công trình này là bài toán Điều Hướng Thu Thập (Thief Orienteering Problem, ThOP), là một biến thê của bài toán Điều Hướng (Orienteering Problem) được lấy cảm hứng từ bài toán Người Thu Thập Du Lịch (Travelling Thief Problem, TTP). TTP được dé xuất bởi Bonyadi, Michalewicz va Barone (ii). Day là sự kết hop của hai bài toán kinh dién nỗi tiếng: bài toán Người Ban Hàng Du lich (Traveling Salesman Problem, TSP) và bài toán Ba Lô (Knapsack Problem, KP).
Điểm Chương 2. KIÊN THUC NEN TANG 5 chính mà tác giả trình bay dé đề xuất TTP là các thang đo của các bài toán NP-Hard kinh điển không phản ánh đúng các đặc điểm chính của các vấn đề thực tế, nên các thuật toán metaheuristics hiệu quả mà chúng ta có cho những thang đo đó không nhất thiết hiệu quả cho các vấn đề thực tế. Tác giả cho rằng sự phức tạp của các vấn đề thực tế không chỉ đến từ kích thước của chúng, mà chủ yêu là do chúng là sự kết hợp của hai hoặc nhiều vấn đề tối ưu hóa con, và vì những vấn đề con đó là tương phụ thuộc lẫn nhau. Điều này có nghĩa là việc giải quyết một vấn đề con ảnh hưởng đến chất lượng của việc giải quyết các van dé con khác, do đó chúng không nên được giải quyết độc lập.
Trong TTP, một người thu thập phải ghé thăm mỗi thành phố trong một tập hợp gồm n thành phó (bài toán con TSP) và trong quá trình ghé thăm có thé thu thập các vật phâm nam ở các thành phó đó dé đựng trong ba lô của mình (bài toán con KP). Tuy nhiên, khi các vật phâm được thu thập, balo trở nên nặng hơn và người thu thập đi chậm hơn. Ba lô của người thu thập thuê, và giá phải trả là tỉ lệ với thời gian thuê. Người thu thập sau đó phải tôi đa hóa tổng lợi nhuận của các vật phẩm đã thu thập và đồng thời giảm thiểu tổng thời gian của hành trình.
Tác giả chỉ ra rằng giải pháp tôi ưu của một trường hợp TTP có thé không bao gồm giải pháp tối ưu của bài toán con KP hoặc bài toán con TSP, chứng minh sự phụ thuộc lẫn nhau của các bài toán con trong đó. Lay cảm hứng từ TTP, Santos và Changas giới thiệu ở một bài toán đa thành phần mới, đó là bài toán Điều Hướng Thu Thập (ThOP), được xây dựng trên cơ sở của bài toán Điều Hướng (OP) thay vì bài toán Người Bán Hàng Du Lịch như TTP. Bài toán Điều Hướng dựa trên một trò chơi thể thao địa hình. Trong trò chơi, các đối thủ bắt đầu từ một điểm cho trước, đi qua một khu vực ghé thăm các điểm kiểm tra và phải quay lại một điểm kiêm soát trong một khoảng thời gian nhất định.
Họ có một bản đồ của khu vực và phải tự quyết định tuyến đường qua các điểm kiểm tra dựa trên kỹ năng định hình và cấp độ thể dục của họ. Trong OP, mỗi điểm kiểm tra có điểm Chương 2. KIÊN THUC NEN TANG 6 số, vì vậy mục tiêu là tìm ra tuyến đường tối đa hóa tong điểm sé, tức là tổng số điểm của các điểm kiểm tra đã ghé thăm là tối đa. Trong biến thé ThOP, một đối thủ hay chúng tôi gọi là người thu thập không ghi điểm chỉ bằng cách ghé thăm các điểm trên bản đồ, mà phải thu thập các vật phẩm tại các điểm và mang theo chúng đến điểm kết thúc.
Mỗi đối thủ có một ba lô với sức chứa giới hạn cho các vật phâm được thu thập. Hơn nữa, tốc độ của người thu thập bị ảnh hưởng trực tiếp bởi trọng lượng của ba lô. Như ở bài toán TTP, khi các vat phẩm được thu thập, ba lô sẽ nặng dần, và tốc độ của người thu thập sẽ giảm xuống. GỌI Umin, Umax là tốc độ tối thiêu và tốc độ tối đa mà người thu thập di chuyên tương ứng khi ba lô đạt sức chứa giới hạn W hoặc ba lô rỗng.
Tốc độ di chuyên v của người thu thập với ba lô có sức nặng w,0 < w < W được tính bằng v = Umax — W- (Omax— 0gữm„) /WsLuu y rang giá tri (Umax — Umin) /W la hang số và thé hiện độ giảm của tốc độ với một đơn vị cân nặng của ba lô. Mục tiêu của ThOP là cung cấp một đường đi từ thành phố bat đầu 1 đến thành phó kết thúc n, cũng như một tập các vật pham được chon từ các thành phố đã ghé thăm trong suốt hành trình đề tối đa hóa tổng lợi nhuận đã lấy, đồng thời đảm bảo rang sức chứa của balo không vượt quá sức chứa giới hạn W và tong thời gian di chuyển của người thu thập nằm trong giới hạn thời gian T. Người thu thập không cần phải ghé thăm tất cả các thành phô. Dé hiểu rõ bài toán Điều Hướng Thu Thập ThOP, chúng tôi minh họa trong hình một ví dụ nhỏ của một trường hợp ThOP liên quan đến 4 thành phó và 5 vật phẩm.
Lưu ý rang không có vật phẩm nao ở thành phó bat đầu (1) và thành phó kết thúc (4), các số vật phẩm có trọng lượng và lợi nhuận khác nhau được phân phối ở các thành phố khác (2 và 3). Các khoảng cach từ mỗi cặp thành phố được cho trong các cạnh. Dưới đây, chúng tôi trình bày chỉ tiết một số lời giải cho trường hợp này. Chúng tôi đặt các ràng buộc của ví dụ này như sau: Ø„„ = 0.
Chúng tôi biéu diễn một lời giải cho bài toán ThOP dưới dang hai phan (7r, 2). KIÊN THUC NEN TANG 7 Thành phố 2 vat pham lợinhuận khối lượng 1 20 2 : 5 2 20 3 : Thành phố 1 | ⁄ `L_[ Thành phó 4 8 Kết thúc ` vật phẩm lợi nhuận khối lượng 3 100 3 Thành phố 3 Hình 2.1: Minh họa một ví dụ của bài toán Điều Hướng Thu Thập bao gồm 4 thành phố, 5 vật phẩm. Phan đầu tiên bao gồm tuyên đường di chuyền của người thu thập 7r = (1, 712, 7L3,., 7, 1), một véc tơ chứa danh sách thành phó đã ghé thăm theo thứ tự di chuyển. Lưu ý rằng thành phố đầu tiên và cuối cùng được có định cho mọi lời giải hợp lệ.
Phan thứ hai là chiến lược thu thập vật phâm z = (z1,2Z2,.,Zm), một véc tơ nhị phân đại diện cho trạng thái của các vật phẩm (z; = 1 nếu vật phẩm¡ được lấy, và 0 nếu ngược lại). Theo biểu diễn nay, hãy xem xét các lời giải ThOP sau cho trường hợp đã mô tả Ở trên: * ((1,2,3,4), (1,0,0,1,0)): là một lời giải hợp lệ với tổng lợi nhuận là 20 + 40 = 60. Tổng khối lượng các vật phâm được thu thập là 3 và thời gian di chuyên là 75, thỏa mãn cả hai ràng buộc giới hạn sức chứa ba lô W và thời gian di chuyển T. Tổng thời gian di chuyền được tính như sau: — di chuyên từ thành phố bat đầu đến thành phó thứ 2 với tốc độ tối đa: thời gian đi chuyền là dyo/Umax = 5/1.
KIÊN THUC NEN TANG 8 — tại thành phố thứ 2, người thu thập lay vật phẩm 1: vận tốc giảm xuống ö =1.4 — đi chuyên từ thành phố thứ 2 sang thành phó thứ 3: tổng thời gian di chuyên là 5+ do3/v =5+8/0.4=5+20= 25 — tại thành phố thứ 3, vật phẩm thứ 4 được lay: vận tốc giảm xuống v = 1.1 — di chuyển từ thành phố thứ 3 đến thành phó kết thúc 4: tổng thời gian di chuyên là 5 + 20 + d34/v = 5 + 20 + 5/0.1 = 5 + 20 + 50 = 75 * ((1,3,2,4), (1,0,0,1,0)): là một lời giải không hợp lệ. Mặc dù chiến lược thu thập với lời giải ơ trên nhưng tông thời gian đi chuyển (83.