Thuật toán di truyền lai ghép thuật toán đàn kiến giải bài toán cực tiểu hóa độ trễ

, 12] đều đưa ra lời giải tốt hơn rất nhiều so với lời giải tìm được bởi
các thuật toán gần đúng với cận tỷ lệ.
292 BAN HÀ BẰNG, NGUYỄN ĐỨC NGHĨA
Trong hướng tiếp cận meta-heuristic, các thuật toán trong [10, 12] xuất phát từ một lời
giải ban đầu (hay một điểm trong không gian lời giải) và dựa trên thuật toán đa láng giềng
(Variable Neighborhood Search-VNS) để tìm lời giải tốt hơn cho bài toán MLP. Tuy nhiên,
khi bài toán tối ưu có không gian lời giải lớn, thì hướng tiếp cận đơn lời giải thường chỉ khai
thác một phần không gian lời giải của bài toán. Do đó, các thuật toán này dễ rơi vào cực trị
địa phương. Để khắc phục nhược điểm của cách tiếp cận đơn lời giải, thuật toán theo hướng
tiếp cận đa lời giải có thể được sử dụng. Các thuật toán này có thể đồng thời tìm kiếm từ
nhiều điểm trong không gian lời giải của bài toán. Bởi vậy, không gian tìm kiếm lời giải của
các thuật toán này được mở rộng hơn. Kết quả là, chúng có nhiều cơ hội thoát khỏi cực trị địa
phương hơn so với các thuật toán đơn lời giải. Thuật toán di truyền trong [3] và thuật toán
đề xuất trong bài báo là thuật toán theo hướng tiếp cận đa lời giải, trong đó, mỗi cá thể đóng
vai trò như một lời giải. Tuy nhiên, thuật toán di truyền trong [3] gặp vấn đề hội tụ sớm do
mất đi sự đa dạng của quần thể sau khi thực hiện một số vòng lặp. Đó là lý do chính dẫn đến
chất lượng lời giải thu được bởi thuật toán là chưa cao. Để khắc phục tình trạng này, chúng
tôi đề xuất thuật toán kế thừa ưu điểm của thuật toán di truyền và thuật toán đàn kiến để
cân bằng giữa hai đặc tính khai phá (exploration) không gian tìm kiếm lời giải mới và khai
thác (exploitation) không gian lời giải đã có. Cụ thể, thuật toán đàn kiến đóng vai trò khởi
tạo quần thể đa dạng cho thuật toán di truyền bằng việc duy trì ba loại kiến như đã trình
bày. Ngược lại, thông tin di truyền từ thuật toán di truyền đóng vai trò định hướng cho đàn
kiến đến không gian lời giải tiềm năng trong lần khởi tạo quần thể kế tiếp. Tuy nhiên, các
thuật toán theo hướng tiếp cận đa lời giải có khối lượng tính toán lớn khi chúng phải tính
toán đồng thời trên nhiều lời giải. Do đó, thời gian chạy của các thuật toán này thường lớn
hơn so với các thuật toán đơn lời giải.
4. KẾT QUẢ THỰC NGHIỆM
Thuật toán đề xuất được cài đặt trên C++ và thực nghiệm được tiến hành trên máy tính
cá nhân với bộ xử lý Intel Pentium core 2 duo 2.13Ghz và 4GB bộ nhớ. Dữ liệu thực nghiệm
bao gồm bộ dữ liệu TSPLIB [16] và ba bộ dữ liệu ngẫu nhiên. Tất cả các bộ dữ liệu đều thỏa
mãn điều kiện metric. Bộ dữ liệu TSPLIB là một thư mục các file dữ liệu. Mỗi file lưu trữ tọa
độ của các đỉnh. Bộ dữ liệu này được sử dụng trong nhiều công trình nghiên cứu liên quan
[1, 3, 10, 12]. Trong ba bộ dữ liệu ngẫu nhiên, bộ dữ liệu đầu tiên là do A. Salehipour et al.
[10] cung cấp. Bộ dữ liệu này được A. Salehipour et al. và được M. Silva et al. sử dụng trong
các thực nghiệm được trình bày trong các công trình [10, 12]. Để đánh giá chính xác hiệu quả
của thuật toán, ta xét thêm hai bộ dữ liệu ngẫu nhiên với kích thước nhỏ mà lời giải tối ưu
của chúng tìm được nhờ sử dụng thuật toán giải đúng [4].
Để đánh giá hiệu quả của thuật toán, hai thực nghiệm được tiến hành. Dữ liệu trong thực
nghiệm đầu tiên bao gồm bộ dữ liệu TSPLIB và các bộ dữ liệu ngẫu nhiên của A. Salehipour
et al. Trong thực nghiệm này, chúng ta so sánh kết quả thu được từ thuật toán ACO-GA với
các kết quả từ các công trình nghiên cứu liên quan [3, 10, 12]. Do lời giải tối ưu của các bộ dữ
liệu này chưa được biết (ngoại trừ lời giải tối ưu cho bộ dữ liệu ngẫu nhiên của A. Salehipour
et al. khi n = 50 được lấy từ [10]), cho nên hiệu quả của các thuật toán chỉ được đánh giá
một cách tương đối. Thực nghiệm thứ hai được thực thi trên các bộ dữ liệu ngẫu nhiên mà
lời giải tối ưu của chúng tìm được nhờ sử dụng thuật toán giải đúng trong [4]. Khi biết lời
giải tối ưu, ta có thể đánh giá một cách chính xác hiệu quả của thuật toán đề xuất. Trong
các thực nghiệm, ta lựa chọn giá trị cho các tham số trong thuật toán ACO-GA như sau:
m = 10, Sp = 300, NG = 5, P c = 0.7, Pm = 0.2, l = 5, βτ = 1, βµ = 5, βg = 5, τ =
THUẬT TOÁN DI TRUYỀN LAI GHÉP THUẬT TOÁN ĐÀN KIẾN 293
10, τ0 = 10, g0 = 1, p = 0.3 và Np = 20.
Bảng 1. Kết quả thực nghiệm các thuật toán cho bộ dữ liệu của A. Salehipour et al.
(n = 50)
File dữ liệu OPT M. Silva et al. GA ACO−GA 
 Best sol Best sol Aver Sol T Best sol Aver Sol Gap[%] T 
TRP-50-R1 12198 12198 12709 12709 3.0 12198 12198 0.00 0.50 
TRP-50-R2 11621 11621 12845 12921 3.2 11621 11674 0.00 0.52 
TRP-50-R3 12139 12139 12904 12904 3.5 12139 12139 0.00 0.51 
TRP-50-R4 13071 13071 13925 13925 3.6 13071 13071 0.00 0.48 
TRP-50-R5 12126 12126 12726 12726 2.9 12126 12284 0.00 0.47 
TRP-50-R6 12684 12684 13245 13245 3.1 12684 12684 0.00 0.50 
TRP-50-R7 11176 11176 11991 11991 3.2 11176 11176 0.00 0.51 
TRP-50-R8 12910 12910 13558 13754 3.1 12910 12945 0.00 0.52 
TRP-50-R9 13149 13149 13845 13845 3.3 13149 13149 0.00 0.48 
TRP-50-R10 12892 12892 13740 13740 2.9 12892 12892 0.00 0.47 
TRP-50-R11 12103 12103 12565 12565 2.8 12103 12181 0.00 0.45 
TRP-50-R12 10633 10633 11657 11657 2.9 10633 10633 0.00 0.47 
TRP-50-R13 12115 12115 12870 12870 3.0 12115 12115 0.00 0.40 
TRP-50-R14 13117 13117 13659 13721 3.1 13117 13117 0.00 0.50 
TRP-50-R15 11986 11986 12793 12793 3.2 11986 11986 0.00 0.51 
TRP-50-R16 12138 12138 12803 12803 3.3 12138 12138 0.00 0.43 
TRP-50-R17 12176 12176 13387 13387 3.4 12176 12176 0.00 0.42 
TRP-50-R18 13357 13357 13988 13988 3.5 13357 13357 0.00 0.44 
TRP-50-R19 11430 11430 11911 12012 3.0 11430 11430 0.00 0.47 
TRP-50-R20 11935 11935 12409 12409 3.0 11935 11935 0.00 0.42 
Trung bình 3.1 0.00 0.47 
A.Salehipour et al. M. Silva et al. 
Best Sol Best Sol Aver Sol Best Sol Aver Sol Gap[%] 
R1 35334 32779 35334 35334 6.2 32779 32779 0.00 1.12
R2 38442 33435 36773 36773 6.4 33435 33435 0.00 1.21
R3 37642 32390 35150 35320 7.1 32390 32390 0.00 0.84
R4 37508 34733 37508 37751 7.3 34733 34733 0.00 0.92
R5 37215 32598 35254 5254 6.7 32598 32598 0.00 1.04
R6 40422 34159 36988 36988 6.5 34212 34212 0.16 1.25
R7 37367 33375 36897 36941 6.3 33375 33375 0.00 0.81
R8 38086 31780 35408 35510 6.4 31780 31780 0.00 0.91
R9 36000 34167 36415 36574 6.8 34167 34167 0.00 0.72
R10 37761 31605 34018 34018 7.0 31812 31812 0.65 0.84
R11 37220 34188 37006 37006 7.1 34188 35534 0.00 0.85
R12 34785 32146 35437 35437 6.5 32899 32899 2.34 0.77
R13 37863 32604 35239 35512 6.7 31989 31989 1.89 0.81
R14 36362 32433 34869 34869 6.8 33601 33601 3.60 0.92
R15 39381 32574 35640 35640 7.0 32574 32574 0.00 0.81
R16 39823 33566 37083 37083 6.9 34818 34818 3.73 0.85
R17 41824 34198 37058 37421 7.1 36297 36297 6.14 0.91
R18 39091 31929 35109 35109 7.2 31929 31929 0.00 0.84
R19 39941 33463 36457 36457 6.4 33463 33463 0.00 0.87
R20 39888 33632 35998 35998 6.3 33632 33632 0.00 0.82
Trung bình 6.5 0.74 0.91
Bảng 2. Kết quả thực nghiệm các thuật toán cho bộ dữ liệu của A. Salehipour et al.
(n = 100)
File dữ liệu 
A.Salehipour et al. M. Silva et al. GA ACO−GA 
Best Sol Best Sol Best Sol Aver Sol T Best Sol Aver Sol Gap[%] T 
TRP-100- 1 35334 32779 35334 35334 6.2 32779 32779 0.00 1.12 
TRP-100- 2 38442 33435 36773 36773 6.4 33435 33435 0.00 1.21 
TRP-100- 3 37642 32390 35150 35320 7.1 32390 32390 0.00 0.84 
TRP-100- 4 37508 34733 37508 37751 7.3 34733 34733 0.00 0.92 
TRP-100- 5 37215 32598 35254 35254 6.7 32598 32598 0.00 1.04 
TRP-100- 6 40422 34159 36988 36988 6.5 34212 34212 0.16 1.25 
TRP-100- 7 37367 33375 36897 36941 6.3 33375 33375 0.00 0.81 
TRP-100- 8 38086 31780 35408 35510 6.4 31780 31780 0.00 0.91 
TRP-100- 9 36000 34167 36415 36574 6.8 34167 34167 0.00 0.72 
TRP-100- 10 37761 31605 34018 34018 7.0 31812 31812 0.65 0.84 
TRP-100- 11 37220 34188 37006 37006 7.1 34188 35534 0.00 0.85 
TRP-100- 12 34785 32146 35437 35437 6.5 32899 32899 2.34 0.77 
TRP-100- 13 37863 32604 35239 35512 6.7 31989 31989 -1.89 0.81 
TRP-100- 14 36362 32433 34869 34869 6.8 33601 33601 3.60 0.92 
TRP-100- 15 39381 32574 35640 35640 7.0 32574 32574 0.00 0.81 
TRP-100- 16 39823 33566 37083 37083 6.9 34818 34818 3.73 0.85 
TRP-100- 17 41824 34198 37058 37421 7.1 36297 36297 6.14 0.91 
TRP-100- 18 39091 31929 35109 35109 7.2 31929 31929 0.00 0.84 
TRP-100-R19 39941 33463 36457 36457 6.4 33463 33463 .00 .87 
TRP-100-R20 39888 33632 35998 35998 6.3 33632 33632 0.00 0.82 
Trung bình 6.5 0.74 0.91 
294 BAN HÀ BẰNG, NGUYỄN ĐỨC NGHĨA
4.1. Thực nghiệm 1
Trong thực nghiệm này, thuật toán ACO-GA thực thi trên bộ dữ liệu TSPLIB và bộ dữ
liệu ngẫu nhiên của A. Salehipour et al. [10]. Mỗi bộ dữ liệu bao gồm các file dữ liệu thực
nghiệm. Mỗi file lưu trữ tọa độ của các đỉnh. Ta thực thi thuật toán 10 lần trên mỗi file dữ
liệu. Kết quả thực nghiệm được trình bày trong các Bảng từ 1 đến 3. Trong các bảng này, cột
Best Sol, Aver Sol lần lượt là kết quả tốt nhất và kết quả trung bình thu được sau 10 lần chạy
các thuật toán. Cột gap[%] ghi nhận giá trị gap[%] =
(UB2 − UB1)
UB1
100%, trong đó UB2 và
UB1 lần lượt là lời giải tốt nhất thu được từ thuật toán ACO-GA và thuật toán của M. Silva
et al. Cột T¯ là thời gian chạy trung bình của thuật toán tính bằng phút. Trong Bảng 1, cột
OPT tương ứng với giá trị tối ưu. Trong Bảng 3, kết quả thực nghiệm thuật toán của Archer
et al. được lấy từ [1]. Dấu “-” nghĩa là không có kết quả thực nghiệm với thuật toán tương
ứng.
Kết quả thực nghiệm trình bày trong các Bảng từ 1 đến 3 chứng tỏ thuật toán ACO-GA
hiệu quả hơn thuật toán di truyền GA [3] cả về chất lượng lời giải và thời gian chạy. So với lời
giải tối ưu có được trong Bảng 1, thuật toán ACO-GA đưa ra được lời giải tối ưu cho tất cả
các file dữ liệu. Kết quả thực nghiệm cũng cho thấy, thuật toán ACO-GA cho lời giải tốt hơn
thuật toán của Archer et al. và A. Salehipour et al. ở tất cả các file dữ liệu. Trong các bộ dữ
liệu ngẫu nhiên ACO-GA cho lời giải với chất lượng rất sát với chất lượng lời giải được đưa
ra bởi thuật toán của M. Silva et al. Cụ thể, gap[%] trung bình trong Bảng 1 và 2 lần lượt
là 0.00% và 0.74%. Đặc biệt, đối với file dữ liệu TPR-S100-13, thuật toán ACO-GA đưa ra
lời giải tốt hơn so với thuật toán của M.Silva et al. Đối với các bộ dữ liệu trong TSPLIB, kết
quả thực nghiệm trong Bảng 3 cho thấy thuật toán ACO-GA đưa ra lời giải với chất lượng
Bảng 3. Kết quả thực nghiệm các thuật toán cho bộ dữ liệu TSPLIB
File dữ liệu 
Archer et al. A.Salehipour et al. M. Silva et al. GA ACO-GA 
Best Sol Best Sol Best Sol Best Sol T Best Sol T 
st70 26384 19553 19215 19893 4.20 19215 0.61 
rat195 280900 213371 210191 245412 9.10 210191 4.30 
kroD100 1297932 976830 949594 976830 6.00 948325 1.50 
pr226 10421449 7226554 7100308 7212541 10.1 7100308 4.12 
lin105 780662 585823 585823 598375 6.15 585823 1.56 
pr107 2205490 1983475 1980767 21750029 6.17 1973726 1.62 
lin318 7475822 5876537 5560679 5876537 13.2 5560679 9.25 
pr439 24126010 18567170 17688561 18567170 20.0 17688561 13.1 
att532 - 18448435 5581240 18448435 23.0 18448435 18.5 
rat99 75048 56994 54984 58327 5.5 57896 1.41 
eil101 38582 - - 30235 6.0 29123 1.48 
eil76 26128 - - 18243 4.3 18023 0.65 
eil51 14683 - - 10281 3.0 9952 1.51 
kroE100 1345314 - - 984759 5.8 955272 1.41 
kroA200 3387616 - - 2962453 8.7 2845318 4.12 
kroB200 3731218 - - 3000409 8.5 2939494 4.23 
rd100 458419 - - 370645 5.7 355985 1.43 
tsp225 537080 - - 463666 9.4 454714 4.62 
d198 1380470 - - 1309819 9.1 1204997 4.12 
u159 3837650 - - 3169661 6.7 2836575 3.25 
bier127 5929120 - - 5011031 7.8 4768611 1.81 
gil262 393641 - - 327534 11.5 325679 4.23 
THUẬT TOÁN DI TRUYỀN LAI GHÉP THUẬT TOÁN ĐÀN KIẾN 295
tốt hơn so với các thuật toán còn lại ở hầu hết các file dữ liệu (ngoại trừ đối với hai file dữ
liệu att532 và rat99, thuật toán đưa ra lời giải với chất lượng kém hơn so với thuật toán của
M. Silva et al.). Tuy nhiên, thời gian chạy của thuật toán ACO-GA lớn hơn thời gian chạy
của thuật toán M.Silva et al.
Bảng 4. Kết quả thực nghiệm các thuật toán cho các bộ dữ liệu ngẫu nhiên (n = 40)
File dữ liệu OPT 
GA ACO−GA 
Best Sol Aver Sol Gap[%] T Best Sol Aver Sol Gap[%] T 
eil51 6140 6140 6140 0.00 2.5 6140 6140 0.00 0.30 
eil76 5894 5894 5894 0.00 2.6 5894 5894 0.00 0.25 
st70 7801 7801 7801 0.00 2.5 7801 7801 0.00 0.24 
rat195 18058 18265 18285 1.15 2.7 18058 18058 0.00 0.21 
kroA100 239680 241012 241741 0.56 2.6 239680 239854 0.00 0.20 
kroB100 245999 247541 248041 0.63 2.5 245999 24612 0.00 0.21 
kroC100 1122890 1145124 1147815 1.98 2.8 1122890 1122890 0.00 0.22 
berlin52 1372572 1372572 1372952 0.00 2.9 1372572 1372854 0.00 0.24 
pr76 1122891 1123541 1123654 0.06 2.7 1122891 1122301 0.00 0.21 
tsp225 27523 27523 27618 0.00 2.8 27523 27523 0.00 0.22 
tss225 1138068 1138068 1138230 0.00 2.7 1138068 1138068 0.00 0.24 
lin105 140450 140450 1405412 0.00 2.8 140450 140450 0.00 0.21 
test 1 8105 8105 8105 0.00 2.7 8105 8105 0.00 0.24 
test 2 9248 9248 9248 0.00 2.8 9248 9248 0.00 0.22 
test 3 8584 8630 8658 0.54 2.7 8584 8584 0.00 0.25 
test 4 9240 9263 9267 0.25 2.6 9240 9278 0.00 0.24 
test 5 8097 8097 8097 0.00 2.7 8097 8138 0.00 0.23 
test 6 9490 9506 9519 0.17 2.8 9490 9490 0.00 0.24 
test 7 8450 8517 8564 0.79 2.7 8450 8450 0.00 0.25 
test 8 8426 8426 8426 0.00 3.0 8426 8426 0.00 0.25 
test 9 8987 9018 9023 0.34 2.7 8987 8987 0.00 0.24 
test 10 9705 9713 9719 0.08 2.8 9705 9705 0.00 0.23 
test 11 9526 9526 9556 0.00 2.7 9526 9545 0.00 0.22 
test 12 8827 8838 8872 0.12 2.5 8827 8827 0.00 0.21 
test 13 9440 9450 9475 0.11 2.6 9440 9440 0.00 0.20 
test 14 8539 8539 8539 0.00 2.7 8539 8562 0.00 0.27 
test 15 8321 8321 8321 0.00 2.7 8321 8321 0.00 0.24 
test 16 8327 8434 8457 1.28 2.6 8327 8327 0.00 0.26 
test 17 8300 8302 8302 0.02 2.5 8300 8300 0.00 0.24 
test 18 9520 9520 9520 0.00 2.7 9520 9520 0.00 0.22 
test 19 9759 9769 9792 0.10 2.8 9759 9759 0.00 0.21 
test 20 8782 8785 8813 0.03 2.7 8782 8782 0.00 0.22 
Trung bình 0.26 2.69 0.00 0.23 
4.2. Thực nghiệm 2
Hai bộ dữ liệu ngẫu nhiên được sử dụng là một bộ dữ liệu Euclid và một bộ dữ liệu phi
Euclid. Mỗi bộ dữ liệu bao gồm các file dữ liệu có kích thước nhỏ (số đỉnh của đồ thị trong
mỗi file dữ liệu n ≤ 40). Trong bộ dữ liệu ngẫu nhiên phi Euclid, các file dữ liệu được tạo ngẫu
nhiên với chi phí cạnh là các số nguyên từ 1 đến 100. Trong bộ dữ liệu ngẫu nhiên Euclid,
tọa độ các đỉnh trong mỗi file dữ liệu được tạo ngẫu nhiên trong hình vuông 200 × 200 đơn
vị. Chi phí cạnh được tính theo khoảng cách Euclid giữa hai đỉnh. Đối với mỗi bộ dữ liệu, ta
296 BAN HÀ BẰNG, NGUYỄN ĐỨC NGHĨA
tạo ra mười file dữ liệu khác nhau có kích thước bằng 40 đỉnh. Ngoài ra, để có thêm nhiều
file dữ liệu với kích thước nhỏ, có thể trích chọn ngẫu nhiên 40 đỉnh từ các file dữ liệu có
kích thước lớn hơn trong TSPLIB. Như đã biết, bộ dữ liệu TSPLIB gồm các file dữ liệu. Mỗi
file dữ liệu lưu trữ toạ độ của các đỉnh. Gọi Xmax, Ymax là hoành độ và tung độ lớn nhất,
Xmin, Ymin là hoành độ và tung độ nhỏ nhất trong một file dữ liệu. Gọi ∆x =
Xmax−Xmin
n và
∆y = Ymax−Yminn . Ta chia bộ dữ liệu trên thành ba nhóm khác nhau dựa trên giá trị ∆x,∆y.
Nhóm 1 với ∆x,∆y nhỏ (∆x,∆y ≤ 3, các đỉnh được phân bố gần nhau). Nhóm 2 với ∆x,∆y
lớn (∆x,∆y ≥ 9, các đỉnh được phân bố thưa). Nhóm 3 các đỉnh được phân bố đặc biệt
(chẳng hạn, nhiều đỉnh cách đều nhau hoặc nằm trên một đường thẳng). Chia các file dữ liệu
trong TSPLIB trên thành ba nhóm. Trong mỗi nhóm, chọn ra bốn file dữ liệu làm đại diện
và thực hiện trích chọn ngẫu nhiên 40 đỉnh từ các file dữ liệu trong nhóm đó. Cụ thể, nhóm
1 gồm các file dữ liệu được trích chọn từ eil51, st70, eil76 và rat195. Nhóm 2 gồm các file dữ
liệu được trích chọn từ kroA100, kroB100, KroC100 và Berlin52. Cuối cùng, các file dữ liệu
được trích chọn từ tsp225, tss225, pr76 và lin105 thuộc về nhóm 3. Kết quả thực nghiệm được
trình bày trong Bảng 4.
Trong Bảng 4, cột OPT , Best Sol (UB) và Aver Sol lần lượt là giá trị tối ưu, kết quả tốt
nhất và kết quả trung bình thu được từ các thuật toán sau 10 lần chạy. Cột gap[%] vẫn ghi
giá trị gap[%] =
(UB −OPT )
OPT
100% như trong ba bảng trước và cột T¯ là thời gian chạy trung
bình của các thuật toán tính bằng phút.
Kết quả thực nghiệm trong Bảng 4 cho thấy thuật toán ACO-GA hiệu quả hơn thuật toán
di truyền GA [3] cả về chất lượng lời giải và thời gian chạy thuật toán. Hơn nữa, đối với tất
cả các bộ dữ liệu kích thước nhỏ này, thuật toán ACO-GA luôn tìm được lời giải tối ưu.
5. KẾT LUẬN
Bài báo đã đề xuất thuật toán di truyền lai ghép với thuật toán đàn kiến giải bài toán
MLP, trong đó thuật toán đàn kiến có vai trò khởi tạo quần thể cho thuật toán di truyền, còn
thuật toán di truyền có vai trò định hướng cho đàn kiến lựa chọn đường đi. Thuật toán được
chạy thử nghiệm trên các bộ dữ liệu chuẩn để so sánh hiệu quả với các thuật toán hiện biết.
Đối với bộ dữ liệu ngẫu nhiên, thuật toán đề xuất cho lời giải tốt hơn các thuật toán tốt nhất
hiện biết trên nhiều bộ dữ liệu. Đối với bộ dữ liệu TSPLIB, thuật toán tỏ ra hiệu quả hơn khi
luôn đưa ra lời giải tốt hơn hoặc không thua kém các thuật toán tốt nhất. Tuy nhiên, thời
gian chạy của thuật toán vẫn cần được cải thiện để đáp ứng được các yêu cầu thực tiễn. Một
trong những hướng để giải quyết vấn đề này là thực hiện song song hóa thuật toán đề xuất.
Đó là vấn đề sẽ tiếp tục nghiên cứu trong thời gian tới.
TÀI LIỆU THAM KHẢO
[1] A. Archer, A. Levin, and D. Williamson, A faster, better approximation algorithm for the min-
imum latency problem, SIAM Journal on Computing 37 (1) (2007) 1472–1498.
[2] S. Arora, and G. Karakostas, Approximation schemes for minimum latency problems, SIAM
Journal on Computing 32 (2) (1999) 688–693.
[3] H.B. Ban, and D.N. Nguyen, Improved genetic algorithm for minimum latency problem, Pro-
ceedings of ACM SOICT, Hanoi, Vietnam, 2010 (9–15).
THUẬT TOÁN DI TRUYỀN LAI GHÉP THUẬT TOÁN ĐÀN KIẾN 297
[4] H.B. Ban, K. Nguyen, M.C. Ngo, and D.N. Nguyen, An efficient exact algorithm for minimum
latency problem, Journal on Progress of Informatics (10) (2013) 1–8.
[5] A. Blum, P. Chalasani, D. Coppersmith, W. Pulleyblank, P. Raghavan, and M. Sudan, The
minimum latency problem, Proceedings of ACM Symposium on the Theory of Computing,
Quebec, Canada, 1994 (163–171).
[6] K. Chaudhuri, B. Goldfrey, S. Rao, and K. Talwar, Path, Tree and minimum latency tour,
Proceedings of IEEE Foundations of Computer Science, MA, USA, 2003 (36–45).
[7] M. Dorigo, and T. Stutzle, Ant Colony Optimization, Bradford Books, London, 2004.
[8] M. Goemans, and J. Kleinberg, An improved approximation ratio for the minimum latency
problem, Proceedings of ACM-SIAM Symposium on Discrete Algorithms, MA, USA, 1996
(152–158).
[9] H. Hasegawa, Optimization of GROUP behavior, Japan Ethological Society Newsletter (43)
(2004) 22-–23.
[10] A. Salehipour, K. Sorensen, P. Goos, and O.Braysy, Efficient GRASP+VND and GRASP+VNS
metaheuristics for the traveling repairman problem, Journal on Operations Research 9 (2)
(2011) 189-–209.
[11] S. Sahni, and T. Gonzalez, P -complete approximation problem, Journal on ACM 23 (3)
(1976) 555–565.
[12] M. Silva, A. Subramanian, T. Vidal, and L. Ochi, A simple and effective metaheuristic for the
Minimum Latency Problem, Journal on Operations Research 221 (3) (2012) 513-–520.
[13] S. Shimomura, M. Sugimotoy, T. Haraguchiy, H. Matsushitaz, and Y. Nishioy, Ant colony op-
timization with intelligent and dull ants, Proceedings of Symposium on Nonlinear Theory
and its Applications, Krakow, Poland, 2010 (504–507).
[14] D. S. Johnson, and L. A. McGeoch, The traveling salesman problem: A case study in local
optimization, Local Search in Combinatorial Optimization, E. Aarts and J. K. Lenstra, eds,
Wiley, 215–310, 1997.
[15] B.Y. Wu, Z.N. Huang, and F.J. Zhan, Exact algorithms for the minimum latency problem,
Journal on Inf. Process. Lett. 92 (6) (2004) 303–309.
[16] 
Ngày nhận bài 01 - 3 - 2013
Nhận lại sau sửa ngày 10 - 8 - 2013