Tóm tắt Luận văn Bài toán thuê xe du lịch có hạn ngạch
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ố.
24 trang |
Chia sẻ: yenxoi77 | Lượt xem: 580 | Lượt tải: 0
Bạn đang xem trước 20 trang tài liệu Tóm tắt Luận văn Bài toán thuê xe du lịch có hạn ngạch, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
ĐẠ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
Các file đính kèm theo tài liệu này:
- tom_tat_luan_van_bai_toan_thue_xe_du_lich_co_han_ngach.pdf