Tóm tắt Luận văn Bài toán thuê xe du lịch có hạn ngạch

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ HÀ NỘI Đinh Thị Thủy BÀI TOÁN THUÊ XE DU LỊCH CÓ HẠN NGẠCH Ngành: Công nghệ thông tin Chuyên ngành: Khoa học máy tính Mã số: 64080101 TÓM TẮT LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN Hà Nội - 2018 Chương 1 Bài toán thuê xe du lịch có hạn ngạch 1.1. Quy hoạch nguyên 1.1.1. Dạng tổng quát của bài toán Bài toán quy hoạch nguyên tổng quát được biểu diễn dưới dạng: f (x) = cTx → min(max) với các điều kiện: Ax ≤ b x ≥ 0 x ∈ Zn 1.1.2. Ứng dụng của bài toán Ứng dụng của bài toán được phát triển dựa vào các biến thể là bài toán quy hoạch nguyên hỗn hợp và bài toán quy hoạch nguyên 0-1. Lập kế hoạch sản xuất Bài toán lập lịch Mạng di động 1.1.3. Các phương pháp tiếp cận giải bài toán quy hoạch nguyên Sử dụng tổng số đơn modulo Thuật toán chính xác Phương pháp Heuristic 2 1.2. Bài toán người chào hàng(Traveling Salesman Prob- lem - TSP) Bài toán được phát biểu như sau: Có một người giao hàng cần đi giao hàng tại n thành phố(hoặc điểm tiêu thụ) C = {c1, c2, ..., cn} độ dài đường đi trực tiếp từ ci đến cj là dij . Anh ta xuất phát từ một thành phố nào đó, đi qua các thành phố khác để giao hàng và trở về thành phố ban đầu, mỗi thành phố chỉ đến một lần. Hãy tìm một chu trình (một đường đi khép kín thỏa mãn điều kiện trên) sao cho tổng độ dài các cạnh là nhỏ nhất. 1.3. Bài toán thuê xe du lịch có hạn ngạch(q-CaRS) Bài toán xuất phát từ những nhu cầu thực tiễn của người du lịch. Khi người du lịch đi tham quan một khu vực, họ thường đặt ra các mục tiêu về sự hấp dẫn của địa điểm. Tuy nhiên vì một số lý do tài chính và thời gian họ không thể tham quan được tất cả. Do đó mục tiêu đặt ra là thỏa mãn về mức độ hài lòng đồng thời chi phí tiết kiệm nhất. Bài toán được đặt ra trong nghiên cứu này không đề cập đến thời gian di chuyển mà tập trung vào mức độ hấp dẫn của những địa điểm tham quan và chi phí di chuyển. Bài toán có một số ràng buộc sau: -Một chiếc xe không thể bị thuê nhiều hơn 1 lần. -Một ràng buộc được gán với mỗi thành phố được gọi là mức độ hấp dẫn. -Tour du lịch bắt đàu và kết thúc trong thành phố với nơi đầu tiên bắt đầu, còn gọi là cơ sở. Mô hình toán học của bài toán: Đây là một bài toán biến thể của bài toán TSP Input: -C: tập các xe để cho thuê -V: tập các các thành phố -A: tập các cạnh (đường đi nối giữa hai thành phố)) - Một ràng buộc qi, i = 1, ..., n, được gán với thành phố i ∈ V và ω là tổng ràng buộc tối thiểu cần thiết thu được trong suốt tour du lịch. -Giá để thuê c ∈ C trên canh (i, j) ∈ A là dcij -Số tiền bổ sung γcij phải được trả nếu c được thuê tại thành phố j và di chuyển đến thành phố i với i 6= j, giá trị này tương ứng với thuế phải trả để chuyển c về j Các biến số: 3 - f cij có giá trị 1 khi xe c di chuyển trên cạnh (i, j) từ i tới j và có giá trị 0 trong những trường hợp khác. -wcij có giá trị 1 khi xe c được thuê ở j và được chuyển tới i. -aci nhận giá trị 1 khi c được thuê ở i. -eci có giá trị 1 khi xe c được chuyển tới i. - Giá trị nguyên ui định nghĩa vị trí của đỉnh i trong tour. Đỉnh 1 gọi là thành phố cơ sở. Các ràng buộc: -Tour bắt đầu và kết thúc tại thành phố 1 ∑ c∈C ∑ j∈V f c1j = ∑ c∈C ∑ i∈V f c1j = 1 (1.3.1) -Mỗi đỉnh chỉ được đến thăm một lần duy nhất và nếu một chiếc xe đến đỉnh i thì sau đó phải có 1 chiếc xe khác rời khỏi đỉnh i. sumc∈C ∑ i∈V f cih = ∑ c∈C ∑ j∈V f chj ≤ 1∀h ∈ V (1.3.2) -Các cặp biến aci và f c ij biểu diễn rằng nếu xe c được thuê ở thành phố i, (i 6= j) thì xe c sẽ được sử dụng để di chuyển từ i đến thành phố j và sẽ có xe c ′ đi đến thành phố i từ thành phố h. aci = ( ∑ j∈V f cij ) ∑ c′∈C,c′ 6=C ∑ h∈V f c ′ hi∀c ∈ C, i ∈ V, i > 1  (1.3.3) -Tương tự điều kiện [1.3.3], các biến eci và f c ij eci = ( ∑ j∈V f cij ) ∑ c′∈C,c′ 6=C ∑ h∈V f c ′ ih∀c ∈ C, i ∈ V, i > 1  (1.3.4) - Các cặp biến wcij, a c i , e c i . omegacij = a c j .e c i∀c ∈ C, ∀i, j ∈ V (1.3.5) -Có 1 xe thuê ở đỉnh 1 ∑ c∈C ac1 = 1 (1.3.6) -Mỗi xe chỉ được thuê một lần ∑ i∈V ac1 ≤ 1∀c ∈ C (1.3.7) 4 -Nếu xe c được thuê thì sau đó nó sẽ được trả lại. ∑ i∈V ac1 = ∑ i∈V ec1∀c ∈ C (1.3.8) -Phải đảm bảo được mức độ hài lòng. ∑ i∈V (( ∑ c∈C ∑ j∈V f cij ) qi ) ≥ ω (1.3.9) -Không có các tour du lịch con 2 ≤ ui ≤ n∀i = 2, ..., n (1.3.10) ui − uj + 1 ≤ (n− 1)(1− ∑ c∈C f ci j)∀i, j = 2, ..., n (1.3.11) -Các biến đều là nhị phân và biến ui là số nguyên dương. f cij,ω c ij, a c ij, e c ij ∈ [0, 1] (1.3.12) ui ∈ N (1.3.13) Hàm mục tiêu Chi phí cho chuyến đi đảm bảo là thấp nhất min ∑ c∈C ∑ j∈V dcij. f c ij + ∑ c∈C ∑ j∈V γcij.ω c ij (1.3.14) 5 Chương 2 Các phương pháp metaheuristic 2.1. Thuật giải di truyền 2.1.1. Thuật toán di truyền cổ điển GA cổ điển được Holland (1975) giới thiệu để tối ưu hoá bài toán: max{ f (x)/x ∈ M ⊂ Rn} (2.1.1) nhờ biểu diễn gene dạng nhị phân, ở đây M là hình hộp ⊔n i=1[ai, bi] trong không gian véc tơ thực n chiều Rn, f nhận các giá trị dương trên M. Để thực hiện thủ tục GA, trước hết cần mã hóa các phần tử của tập M. Mỗi x trong M được mã hoá bởi một xâu nhị phân độ dài m z = (z1, z2, ..., zm) gọi là nhiễm sắc thể hay một cá thể, mỗi zi được gọi là một gene. Phương pháp mã hoá và giải mã Mã hóa Giả sử ta cần tìm cực đại hàm f với sai số mỗi biến xi là 10−p . Ta chia mỗi đoạn [ai, bi] thành (bi − ai)10p đoạn bằng nhau và ký hiệu mi là số tự nhiên nhỏ nhất thoả mãn: (bi − ai)10p 6 2mi − 1 Khi đó nếu x = (x1, ..., xi, ..., xn) và xi thuộc đoạn thứ k thì xi được mã hoá bởi xâu nhị phân độ dài mi có dạng sao cho sẽ thoã mãn yêu cầu về độ chính xác và x được biễu diễn bởi xâu nhị phân có độ dài . Giải mã Với mỗi đoạn gene (bmi−1, ..., b0) ta xác định ki theo hệ số 10 : 6 ki = ∑ mi−1 j=0 (bj2 j)10 và có xi = ai + ki (bi−ai) 2mi−1 Hay là xi = ai +∑ mi−1 j=0 (bj2 j)10 (bi−ai) 2mi−1 . Mô tả lược đồ GA Hình 2.1: Cấu trúc tổng quát của thuật toán di truyền Các bước cơ bản để xây dựng chương trình tiến hóa Đối với một bài toán cần giải P, để xây dựng một chương trình tiến hoá giải nó, người ta thường tiến hành theo năm bước cơ bản sau: • Bước 1. Chọn cấu trúc nhiễm sắc thể / kiểu gene biễu diễn lời giải tiềm năng của bài toán sao cho nó chứa đủ các thông tin quan trọng và dễ làm việc. Tuy nhiên không có sự hướng dẫn nào về cách chọn này. Thiết kế chương trình mã hóa và giải mã • Bước 2. Khởi tạo tập lời giải ban đầu. Việc khởi tạo là ngẫu nhiên hay có thể áp dụng một vài thuật toán heuristic, nhưng phải đảm bảo sao cho các ràng buộc của bài toán được đảm bảo. • Bước 3. Chọn hàm đánh giá mức độ tốt của lời giải (để đánh giá các cá thể trong quần thể lời giải theo độ thích nghi của chúng ). • Bước 4. Thiết kế các toán tử di truyền. Các toán tử này được thiết kế nên dựa trên kiểu gene/ nhiễm sắc thể , đặc điểm bài toán và các ràng buộc của nó. 7 • Bước 5: Xác định các tham số cho bài toán. Các tham số này có thể không thay đổi trong quá trình tiến hoá hoặc có thể tự điều chỉnh tham số theo thời gian. 2.2. Phương pháp tối ưu hóa đàn kiến 2.2.1. Cách tìm đường đi của kiến tự nhiên Hình 2.2: Phân bố của đàn kiến trên đường đi từ tổ tới nguồn thức ăn 2.2.2. Kiến nhân tạo Thực nghiệm cây cầu đôi cho thấy đàn kiến tự nhiên có thể sử dụng luật di chuyển theo xác suất, dựa trên thông tin địa phương để tìm được đường đi ngắn nhất giữa hai địa điểm. Vết mùi của đàn kiến cho phép liên tưởng tới cách học tăng cường (reinforcement learning) trong bài toán chọn tác động tối ưu, gợi mở mô hình mô phỏng cho bài toán tìm đường đingắn nhất giữa hai nút (tương ứng là tổ và nguồn thức ăn) trên đồ thị, trong đó các tác tử (agent) là đàn kiến nhân tạo. 8 2.2.3. Phương pháp ACO tổng quát Thuật toán tổng quát Với bài toán tổng quát trên, về lý thuyết ta cú thể áp dụng thủ tục mở rộng để xây dựng X∗ và chọn lời giải tốt nhất bằng phương pháp vét cạn, nhưng trên thực tế, do bùng nổ tổ hợp thì khi số phần tử n của C lớn ta không thực hiện được đối với bài toán thuộc loại NP-khó. Để giải bài toán người ta đưa nó về bài toán tìm đường đi tối ưu trên đồ thị cấu trúc sao cho mỗi lời giải chấp nhận được s ứng với đường đi , trong đó xi thuộc tập đỉnh (thành phần C) của đồ thị, x1 thuộc tập đỉnh C0 (tham khảo phương pháp constructive heuristics). Đồ thị cấu trúc thường là đồ thị đầy đủ có trọng số G = (V, E,H, τ) trong đó V là tập đỉnh tương ứng với tập thành phần C ở trên, E là tập các cạnh, H là vectơ các trọng số heuristic của cạnh/đỉnh tương ứng, còn τ là vectơ vết mùi tích lũy được ban đầu với khởi tạo bằng τ0 . Thông tin heuristic và vết mùi có thể để ở đỉnh hoặc các cạnh của đồ thị tùy theo đặc điểm bài toán dùng để định hướng tìm kiếm heuristic ngẫu nhiên khi xây dựng lời nhờ mở rộng tuần tự từ một đỉnh trong C0 theo đặc điểm thứ 3 của bài toán tổng quát. Dựa trên đồ thị cấu trúc này, ta xây dựng thủ tục bước bước tuần tự tìm lời giải cho các kiến nhân tạo. Thông thường ta có thể đã có các phương pháp heuristic để tim lời giải đủ tốt cho bài toán. Các thuật toán ACO kết hợp thông tin heuristic này với phương pháp học tăng cường nhờ mô phỏng hành vi của đàn kiến để tìm lời giải tốt hơn. Với quy tắc cập nhật mùi, các tham số, số kiến và điều kiện dừng (thường là số lần lặp Nc định trước) đã được chọn các thuật toán được mô tả hình thức trong hình 2.3. Hình 2.3: Lược đồ thuật toán ACO tổng quát 9 Chương 3 Thuật giải di truyền cho bài toán q-CaRS 3.1. Biểu diễn quần thể Trong bài toán này ta sẽ biểu diễn nhiễm sắc thể dạng nguyên. Mỗi nhiễm sắc thể là một mảng hai chiều với một hàng là tập tuần tự các thành phố đến thăm và một hàng là tập các xe được sử dụng. Hình 3.1: Nhiễm sắc thể Thuật toán láng giềng gần nhất được sử dụng để xây dựng đường dẫn giữa 2 thành phố theo chi phí cạnh của chiếc xe gắn liền với con đường đó. Tour bắt đầu tại thành phố 1. Xe c1 được chọn ngẫu nhiên để di chuyển từ thành phố 1 tới thành phố ngẫu nhiên i (c1 được trả lại ở i). Nếu giá trị ràng buộc tối thiểu không được thu thập, thành phố i sẽ là điểm khởi tạo trong phần tiếp theo của tour. Một xe mới c2 và một thành phố chưa đến thăm j sẽ được chọn ngẫu nhiên. Một đường dẫn sẽ được tạo ra giữa thành phố i và j bằng việc chỉ xem xét đến các thành phố chưa đến thăm. Tiến trình sẽ tiếp diễn cho đến khi thu được giá trị ràng buộc nhỏ nhất. Chu trình sẽ được đóng với một cạnh từ thành phố cuối cùng trong tour đi đến thành phố 1. Bài toán biến thể được xem xét đến trong nghiên cứu này không cho phép một xe có thể được thuê nhiều hơn 1 lần, vậy nên nếu không còn xe mới nào được thêm thì chiếc xe cuối cùng sẽ được sử dụng dể di chuyển đến các thành phố 10 khác cho đến khi thu được giá trị rằng buộc tối thiểu . 3.2. Quá trình tái tạo Quá trình tái tạo được thực hiện dựa vào toán tử di truyền và biến dị. Toán tử tương giao chéo: Khi khởi tạo quần thể, một tập các cá thể tốt nhất sẽ được chọn ra gọi là tập elite. Trong mỗi lần tái tạo ta sẽ chọn ngẫu nhiên một cá thể trong quần thể và một cá thể trong tập các cá thể tốt nhất để tương giáo chéo với điểm tương giao chéo là ngẫu nhiên. Sau khi tái tạo tập các cá thể tốt nhất được cập nhật lại. Toán tử biến dị: Toán tử biến dị ở đây chính là một đoạn plasmid là đoạn gen được chọn ra từ tập elite. Một đoạn gen trong cá thể được chọn lọc để tái tạo sẽ được thay thể tương ứng với plasmid. Hình 3.2: Plasmid Ví dụ trong hình 3.2 một cá thể sol được chọn ra từ quần thể và cá thể sol’ được chọn ra từ tập elite. Một đoạn plasmid được chọn ra từ sol’. Tương tự ta loại bỏ 1 đoạn gen ngẫu nhiên có kích thước bằng với plasmid từ sol cho kết quả là sol". Thay thể đoạn gen bị loại bỏ bằng plasmid ta có kết quả là sol”’. 11 3.3. Thủ tục tìm kiếm địa phương Để tăng cường chất lượng của lời giải "sol" ta có thủ tục tìm kiếm địa phương multiOperatorsSearch với 6 thủ tục: -removeSaving -invertSol -replaceSavingCity -insertSavingCity -replaceSavingCar - 2-opt 3.4. Thuật toán MemPlas Mã giả của thuật toán MemPlas được biểu diễn trong (thuật toán 1) . Đầu vào của thuật toán có 5 tham số: số lượng quần thể (sizePop), kích thước của plasmid (sizePlas), tỉ lệ tái tổ hợp (#cross), kích thước của các lớp (#elite) và số lần lặp tối đa (limitIter). Tâp giá trị elite sẽ chứa những #elite tốt nhất từ quần thể. Plasmid bao gồm những đoạn gen thu được trong tập elite. Trong 9 lần lặp, nhiễm sắc thể sẽ được tái tổ hợp. Trong lần lặp cuối cùng, một plasmid sẽ được sử dụng để thay đổi nhiễm sắc thể đã chọn. Hình 3.3: Thuật toán MemPlas 12 3.5. Kết quả thực nghiệm 3.5.1. Bộ dữ liệu chuẩn Trong phần này sẽ giới thiệu kết quả của việc tính toán thực nghiệm dựa trên 40 trường hợp q-CaRS. Dữ liệu được lấy từ Các thông số trong mỗi file: DIMENSION: Số lượng thành phố. CARS_NUMBER: Số lượng xe để thuê. NODE_COORD_SECTION: Tọa độ thành phố . EDGE_WEIGHT_SECTION: Giá thuê xe tại mỗi thành phố. RETURN_RATE_SECTION: Giá thuế trả lại xe tại mỗi thành phố. Chí phí di chuyển từ thành phố i đến thành phố j với chiếc xe c được tính theo công thức như sau: dcij = 2Lc[i] + 3Lc[j] 3 + d[i][j] (3.5.1) Mức độ hài lòng tại mỗi thành phố được tạo ngẫu nhiên trong khoảng(0, 100); 3.5.2. Tiến hành chạy thực nghiệm 3.5.3. Kết quả thực nghiệm Phần này thực hiện với hai bộ tham số khác nhau để đánh giá về mức độ ảnh hưởng khi thay đổi các tham số đầu vào Tiến hành thực nghiệm với các tham số Tham số Giá trị Số lượng quần thể( sizePop) 150 Số lượng vòng lặp 10 Tỉ lệ tái tổ hợp(#cross) 0.4 Tỉ lệ chọn các cá thể tối ưu ( #elite) 0.3 Kích thước của plasmid(sizePlas) [3, 0.4s] với s là kích thước cá thể chứa plasmid 13 Hình 3.4: Kết quả thực nghiệm 1 của GA 14 Tiến hành thực nghiệm với các tham số Tham số Giá trị Số lượng quần thể( sizePop) 150 Số lượng vòng lặp 10 Tỉ lệ tái tổ hợp(#cross) 0.5 Tỉ lệ chọn các cá thể tối ưu ( #elite) 0.5 Kích thước của plasmid(sizePlas) [3, 0.4s] với s là kích thước cá thể chứa plasmid Hình 3.5: Kết quả thực nghiệm 2 của GA Bảng trên thống kê kết quả sau 10 lần chạy thực nghiệm đối vởi cả 35 bộ dữ. Trong đó mỗi hàng thể hiện cho một bộ dữ liệu. Kết quả trung bình là kết quả chạy trung bình của 10 lần chạy, kết quả tốt nhất là kết quả tốt nhất trong 10 lần chạy. Tương ứng là thời gian chạy với các kết quả. 15 Chương 4 Thuật toán ACO giải bài toán q-CaRS 4.1. Đồ thị cấu trúc Giải bài toán tối ưu tổ hợp bằng thuật toán ACO việc quan trọng nhất là xây dựng cấu trúc đồ thị. Ta có: A = a1, a2, ..., an là tập các thành phố. C = c1, c2, ..., cm là tâp các xe để di chuyển. Đồ thị cấu trúc của bài toán G = {V, E} được xây dựng như sau: Đồ thị bao gồm l tầng như hình 4.1 . Mỗi đỉnh bao gồm thành phố xuất phát và chiếc xe để di chuyển đến thành phố tiếp theo : vci = (i, c) : i ∈ A, c ∈ C. Các cạnh của đồ thị ei j = (vci , v c′ j ) : vi, vj ∈ A, i < j, c, c′ ∈ C nối các đỉnh đồ thị. Thông tin heuristic được đặt trên các cạnh của đồ thị kí hiệu là τ(vci , v c′ j ). Quy tắc cập nhật vết mùi được áp dụng theo thuật toán SMMAS[??]. 16 Hình 4.1: Đồ thị cấu trúc Thuật toán được xây dựng như dưới đây: Bước 1. Khởi tạo ma trận vết mùi, và tập K gồm k kiến. Bước 2. Thực hiện lặp trong khi chưa thoả mãn điều kiện dừng Với mỗi kiến ta tiến hành các bước sau: 2.1. Khởi tạo đỉnh xuất phát vci bằng cách chọn thành phố cơ sở và chiếc xe di chuyển c thuộc C. Cập nhật lại A = A− i . 2.2 Thực hiện lặp với t >= 2. Chọn đỉnh tiếp theo vc ′ j = (j, c ′) với xác suất Pvci vc ′ j = [τ vci v c′ j ]α[η vci v c′ j ]β ∑l∈A,c′∈C[τvci vc ′ l ]α[η vci v c′ l ]β .Cập nhật lại A = A − i . Nếu đỉnh trước đó được chọn có xe c 6= c′ ta cập nhật lại C = C− c 2.3. Thực hiện tìm kiếm cục bộ trên lời giải tốt nhất do các kiến tìm được để cải thiện chất lượng lời giải. 2.4. Cập nhật lại lời giải tốt nhất. 2.4. Cập nhật vết mùi theo quy tắc SMMAS dựa trên lời giải tốt nhất. Bước 3. Lưu lại lời giải tốt nhất. Sơ đồ thuật toán của việc xây dựng một lời giải pi bởi một con kiến được phác thảo dưới đây: 17 Hình 4.2: Xây dựng lời giải của kiến 4.2. Vết mùi và thông tin heuristic Vết mùi τ(vci , v c′ j ) trên cạnh τ(v c i , v c′ j ) được khởi tạo bằng τmax và được cập nhật lại theo mỗi vòng theo công thức. Thông tin heuristic đươc tính theo công thức: ηvci v c′ j = 1 dcij + γ c ij (4.2.1) trong đó dcij là chi phí di chuyển từ thành phố i đến thành phố j và γ c ij là chi phí trả lại chiếc xe nếu tại j xe c không được thuê . 4.3. Quy tắc cập nhật mùi Sau khi tất cả các kiến đã xây dựng lời giải, lời giải của kiến tốt nhất được áp dụng thủ tục tìm kiếm cục bộ để tăng chất lượng lời giải. Lời giải tốt nhất này được sử dụng để cập nhật vết mùi trên các cạnh theo quy tắc cập nhật mùi SMMAS: τ(vci , v c′ j ) = (1− ρ)τ(vci , vc ′ j ) + ∆vci ,vc ′ j (4.3.2) 18 trong đó: ∆vci ,vc ′ j = ρτmax nếu(vci , vc ′ j ) ∈ bestsolution ρτmin nếu (vci , v c′ j ) /∈ bestsolution (4.3.3) Trong đó τmax và τmin là các tham số được cho trước, ρ ∈ (0, 1) là tham số bay hơi cho trước quy định 2 thuộc tính, ρ nhỏ thể hiện việc tìm kiếm quanh thông tin học tăng cường, ρ lớn thể hiện tính khám phá. 4.4. Thủ tục tìm kiếm cục bộ Để tăng cường chất lượng lời giải, ta sử dụng thêm thủ tục tìm kiếmđịa phương. Thục tục tìm kiếm cục bộ trong phần này được áp dụng hàmmultiOperatorsSearch như trong thuật toán GA ở phần trên. 4.5. Kết quả thực nghiệm Thực nghiệm được tiến hành để so sánh với thuật toán GA nên sử dụng bộ dữ liệu chuẩn như trong GA với cấu hình máy tương tự. Vì ACO là lớp thuật toán meta-heuristic nên mỗi lần chạy sẽ cho các kết quả cụ thể là khác nhau, nên tôi tiến hành chạy chương trình 10 lần trên mỗi bộ dữ liệu, thống kê kết quả thu được, so sánh thông qua 2 tiêu trí là kết quả tốt nhất, kết quả xấu nhất và kết quả trung bình của 10 lần chạy đó. Để so sánh với thuật toán GA ta sẽ chạy thực nghiệm của ACO với cùng số lời giải. Như giới thiệu ở trên, GA sử dụng số lượng quần thể là 150 và số vòng lặp là 10, do đó trong ACO ta sử dụng 10 kiến và đẩy số lượng vòng lặp là 150. 4.6. Kết quả thực nghiệm và đánh giá Tương tự với thuật toán GA ta cũng thực nghiệm với hai bộ tham số khác nhau để đánh giá mức độ ảnh hưởng của các tham số 19 Tiến hành thực nghiệm với các tham số Tham số Giá trị Tham số bay hơi( ρ) 0.03 α 2 β 6 Số kiến ban đầu 10 Số vòng lắp 150 τmax 0.1 τmin 0.008 Kết quả chạy: Hình 4.3: Kết quả thực nghiệm 1 của ACO 20 Tiến hành thực nghiệm với các tham số Tham số Giá trị Tham số bay hơi( ρ) 0.03 α 2 β 6 Số kiến ban đầu 10 Số vòng lắp 150 τmax 0.1 τmin 0.008 Kết quả chạy: 21 Hình 4.4: Kết quả thực nghiệm 2 của ACO Bảng trên thống kê kết quả sau 10 lần chạy thực nghiệm đối vởi cả 35 bộ dữ. Trong đó mỗi hàng thể hiện cho một bộ dữ liệu. Kết quả trung bình là kết quả chạy trung bình của 10 lần chạy, kết quả tốt nhất là kết quả tốt nhất của 10 lần chạy. Tương ứng là thời gian chạy với các kết quả. Kết quả cho thấy khi tham số bay hơi nhỏ thì thực nghiệm tốt hơn. Điều này cho thấy việc học tăng cường trong bài toán này là quan trọng hơn. 22 So sánh với kết quả thực nghiệm của thuật toán GA Trong phần này ta sẽ so sánh kết quả của hai thuật toán GA và ACO với bộ tham số cho kết quả tốt nhất. Hình 4.5: So sánh kết quả thực nghiệm của ACO và GA Từ bảng so sánh ta thấy thuật toán ACO cho kết quả tốt hơn GA rất nhiều cả về chất lượng và thời gian chạy trong nhiều trường hợp. Chỉ có 4 trường hợp được in đậm trên tổng số 35 trường hợp tức là khoảng 11.5% kết quả cho thấy GA tốt hơn. Như vậy tùy từng yêu cầu của bài toán về thời gian và chất lượng, nếu yêu cầu thời gian chạy thấp ta có thể hoàn toàn sử dụng ACO để tìm kiếm lời giải.Tuy nhiên mức độ ảnh hưởng của các tham số là khá lớn, vì vậy cần linh hoạt trong bước lựa chọn tham số. 23