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ễ

Tạp chí Tin học và Điểu khiển học, T.29, S.3 (2013), 285-297
THUẬT TOÁN DI TRUYEN lai ghép thuật toán đàn KIEN
GIẢI bài toán CỰC TIỂU HÓA độ tre
BAN HÀ BẰNG, NGUYỄN ĐỨC NGHĨA
Viện Công nghệ Thông tin và Truyền thông - Đại học Bách khoa Hà Nội
Email: (BangBH, NghiaND) soict.hut.edu.vn
Tóm tắt. Bài toán cực tiểu hóa độ trễ thuộc lóp bài toán tối ưu hóa tổ hợp có nhiều ứng dụng trong thực tiễn. Trong trường hợp tổng quát, bài toán được chứng minh thuộc lóp NP-khó và ngoại trừ P = NP, không tồn tại lược đồ xấp xỉ vói thời gian đa thức để giải nó. Bởi vậy, việc phát triển các thuật toán gần đúng là hưóng tiếp cận phù hợp để giải bài toán. Trong bài báo này sẽ trình bày một thuật toán meta-heuristic (ACO-GA) lai ghép giữa thuật toán di truyền (GA) và thuật toán đàn kiến (ACO). Thuật toán đàn kiến đóng vai trò khởi tạo quần thể cho thuật toán di truyền. Trong khi đó, thông tin di truyền từ thuật toán di truyền giúp định hưóng cá thể kiến chọn đường đi tốt hìn ở lần khởi tạo quần thể kế tiếp. Thêm vào đó, để duy trì tính đa dạng trong quần thể kiến, thuật toán sử dụng ba loại kiến vói các đặc tính tìm kiếm đường đi khác nhau. Thực nghiệm thuật toán đã được thực hiện trên các bộ dữ liệu chuẩn. Kết quả thực nghiệm cho thấy thuật toán đưa ra lời giải vói cận tỷ lệ tốt hìn so vói các thuật toán meta-heuristic hiện biết trên nhiều bộ dữ liệu.
Từ khóa. Bài toán cực tiểu hóa độ trễ-MLP, meta-heuristic, ACO, GA.
Abstract. Minimum Latency Problem is a class of combinatorial optimization problems that have many practical applications. In the general case, the problem is proven to be NP-hard. Therefore, using a meta-heuristic algorithm is a suitable approach for solving this problem. In this paper, we propose a meta-heuristic algorithm which combines Ant Colony (ACO) and Genetic Algorithm (GA). In our algorithm, ACO generates a population for GA. Meanwhile, the genetic information of GA helps ants to create a better population in the next step. In addition, to maintain the diversity of population, our algorithm uses three types of the ants which have different characteristics.We evaluate the algorithm on five benchmark datasets. The experimental results show that our algorithm gives a better solution than the state-of-the-art meta-heuristic algorithms on several instances of datasets.
Key words. Minimum Latency Problem-MLP, meta-heuristic, ACO, GA.
GIỚI THIÊU
Bài toán cực tiểu hóa độ trễ (MLP) là một dạng khác của bài toán thợ sửa chữa lưu động (Traveling Repairman Problem). Bài toán MLP có nhiều ứng dụng trong thực tế, chẳng hạn khi một máy chủ hay một người thợ phải lập lịch thực thi một tập các yêu cầu sao cho tổng (trung bình) thời gian chờ đợi của các yêu cầu là cực tiểu [5, 11]. Do có thể quy bài toán MLP tổng quát về bài toán MLP trong trường hợp metric nhờ sử dụng một phép biến đổi đon giản
(xem [15]), nên trong bài báo này, sẽ chỉ xét bài toán trong trường hợp metric. Bài toán MLP có thể phát biểu như sau: Cho đồ thị đầy đủ Kn với tập đỉnh V = {1, 2,..., ng và ma trận chi phí đối xứng không âm C = {Cj\i, j = 1, 2,..., ng, với cij là khoảng cách giữa hai đỉnh i và j. Giả sử T = v1,v2, ...,vn là một hành trình xuất phát từ v1 (đường đi xuất phát từ v1 đi qua mỗi đỉnh của đồ thị đúng một lần) trên Kn. Ký hiệu Path(v1, vk) là đoạn đường đi từ v1 đến Vk trên hành trình T. Ta gọi độ trễ của đỉnh Vk trên hành trình T, ký hiệu bởi lat(vk), là độ dài của đường đi Path(v1, vk)
k-1
lat(vk)	^2 c(vi, vi+1), k = 2,3,
i=1
Độ trễ của hành trình T, ký hiệu là L(T), được định nghĩa như tổng độ trễ của tất cả các đỉnh thuộc nó
n
L(T) = X lat(vk).
k=2
Giả sử v1 là đỉnh cho trước, bài toán MLP yêu cầu tìm hành trình xuất phát từ v1 với độ trễ là nhỏ nhất.
Trong trường hợp tổng quát, bài toán được chứng minh thuộc lớp NP-khó, và ngoại trừ P = NP, không tồn tại lược đồ xấp xỉ với thời gian đa thức để giải nó [11]. Hiện nay, hàng loạt thuật toán đã được đề xuất để giải bài toán MLP. Trong hướng tiếp cận giải đúng, các thuật toán trong [4, 13] có thể áp dụng giải bài toán MLP với kích thước nhỏ (đồ thị với ít hon 40 đỉnh). Trong không gian metric, nhiều thuật toán gần đúng cận tỷ lệ đã được đề xuất. Đầu tiên, Blum et al. [5] đưa ra thuật toán với cận tỷ lệ là 144, tiếp đến thuật toán của Goemans et al. [8] giảm cận tỷ lệ xuống còn 21.55. Công trình [2] của Arora et al. đề xuất thuật toán gần đúng với cận tỷ lệ 17.24. Thuật toán gần đúng của Archer et al. [1] có cận tỷ lệ 7.18 trong trường hợp metric và 3.01 trong bộ dữ liệu thực nghiệm TSPLIB. Gần đây, K.Chaudhuri et al. [6] đưa ra thuật toán gần đúng với cận tỷ lệ nhỏ nhất là 3.59. Trong hướng tiếp cận meta-heuristic, chúng tôi đề xuất một thuật toán dựa trên so đồ của thuật toán di truyền [3]. Kết quả thực nghiệm chỉ ra rằng chất lượng lời giải đạt được bởi thuật toán là tốt hon so với các thuật toán gần đúng cận tỷ lệ hiện biết trên bộ dữ liệu thực nghiệm TSPLIB [14]. Sau đó, các thuật toán meta-heuristic được xem xét trong các công trình của A. Salehipour et al. [10], M. Silva et al. [12]. Các kết quả thực nghiệm trong [3, 10, 12] cho thấy meta-heuristic là hướng tiếp cận tiềm năng cho bài toán MLP.
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 (ACO-GA) để giải bài toán MLP. Trong thuật toán này, thuật toán đàn kiến đóng vai trò khởi tạo quần thể cho thuật toán di truyền. Ngược lại, thuật toán di truyền đóng vai trò định hướng cho đàn kiến ở lần khởi tạo quần thể kế tiếp. Thuật toán sử dụng ba loại kiến. Loại kiến thứ nhất sẽ sử dụng vết mùi và thông tin di truyền để tìm đường đi. Trong khi đó, loại kiến thứ hai chỉ sử dụng vết mùi, còn loại kiến thứ ba thực hiện một cách ngẫu nhiên việc lựa chọn đường đi. Tiến hành thực nghiệm thuật toán ACO-GA trên các bộ dữ liệu chuẩn đã được nhiều tác giả sử dụng. Kết quả thực nghiệm chỉ ra rằng, thuật toán ACO-GA đưa ra được lời giải với chất lượng tốt hon so với các thuật toán hiện biết trên nhiều bộ dữ liệu.
Cấu trúc của bài báo gồm: Mục 2 trình bày thuật toán đề xuất. Thảo luận về thuật toán đề xuất được đề cập trong Mục 3 và kết quả thực nghiệm được trình bày ở Mục 4. Cuối cùng đưa ra các kết luận.
THUẬT TOÁN ĐE XUAT
Thuật toán di truyền áp dụng rất hiệu quả cho lớp bài toán tối ưu hóa tổ hợp. Tuy nhiên, một vấn đề mà các thuật toán di truyền thường gặp là thuật toán hội tụ sớm sau một số vòng lặp, khi quần thể mất đi tính đa dạng. Trong [3], chúng tôi áp dụng kỹ thuật hủy diệt (Social Disaster Technique) nhằm duy trì tính đa dạng của quần thể. Tuy nhiên, quần thể mới cũng không đảm bảo duy trì được tính đa dạng và thuật toán lại roi vào cực trị địa phưong sau một số thế hệ tiếp theo.
Thuật toán đàn kiến [7] mô phỏng hành vi của các đàn kiến trong thực tế. Khi di chuyển các con kiến để lại vết mùi trên đường đi giúp cho các con kiến theo sau lần theo vết mùi đó. Dựa vào nồng độ mùi do các con kiến đi trước để lại, các con kiến theo sau lựa chọn đi theo đường đi có nồng độ mùi cao hon. Tuy nhiên, một nghiên cứu về hành vi kiến [9] chỉ ra rằng có khoảng 20% số lượng kiến không có khả năng sử dụng vết mùi để tìm đường đi. Mặc dù vậy, chúng lại đóng một vai trò nhất định trong quần thể kiến. Các nhà nghiên cứu đã tiến hành thực nghiệm và thấy rằng loại kiến dựa theo vết mùi có vai trò mang thức ăn từ nguồn thức ăn tìm được về tổ. Tuy nhiên, chúng khó có khả năng tìm được nguồn thức ăn mới. Trong khi đó, loại kiến không có khả năng sử dụng vết mùi lại đóng vai trò như cá thể tìm nguồn thức ăn mới. Thực nghiệm về hành vi đàn kiến cho thấy, quần thể kiến chứa cả hai loại kiến có khả năng tìm kiếm nguồn thức ăn hiệu quả hon so với quần thể kiến chỉ chứa một loại kiến duy nhất. Trong [13], S. Shimomura cũng đã đề xuất thuật toán đàn kiến với hai loại kiến. Kết quả thực nghiệm cũng chỉ ra rằng, quần thể kiến chứa cả hai loại kiến hiệu quả hon so với quần thể kiến chỉ chứa một loại kiến.
Bài báo đề xuất thuật toán dựa trên co sỏ lai ghép thuật toán di truyền với thuật toán đàn kiến. Thuật toán đàn kiến được sử dụng để khỏi tạo quần thể ban đầu cho thuật toán di truyền. Trong khi đó, thông tin từ thuật toán di truyền đóng vai trò định hướng đường đi cho đàn kiến ỏ quần thể kế tiếp. Để có được quần thể đa dạng, thuật toán luôn duy trì ba loại kiến. Loại kiến thứ nhất sử dụng vết mùi và thông tin di truyền để tìm đường đi. Trong khi đó, loại kiến thứ hai chỉ sử dụng vết mùi, còn loại kiến thứ ba lựa chọn tìm đường đi một cách ngẫu nhiên. Như vậy, có thể xem loại kiến thứ ba giống như một toán tử đột biến giúp thuật toán thoát khỏi cực trị địa phưong. So đồ của thuật toán được trình bày ỏ Thuật toán 1.
Ta chuyển sang mô tả chi tiết việc thực hiện các thao tác chính của thuật toán ACO-GA.
Di chuyển của quần thể kiến: Quần thể kiến sẽ bao gồm Sp cá thể kiến, được đánh số bỏi 1, 2, ..., Sp. Bắt đầu từ cá thể kiến 1, trong quá trình thực hiện thuật toán các cá thể kiến lần lượt thực hiện di chuyển, cá thể kiến này di chuyển xong mới đến lượt cá thể kiến tiếp theo.
Mã hóa: Mỗi đường đi mà cá thể kiến tạo ra được mã hóa bỏi một danh sách có thứ tự gồm n đỉnh T = (v1,v2,..., Vị, ...,vn), trong đó Vị là đỉnh được đi qua thứ i trong đường đi. Ta cũng sẽ sử dụng ký hiệu T[i] để chỉ đỉnh thứ i trong danh sách T.
Khỏi tạo vết mùi và thông tin di truyền: Gọi Tk_1ij và gij là lượng mùi và thông tin di truyền có trên cạnh (vi, Vj) mà kiến thứ k sử dụng để lựa chọn cạnh di chuyển (k = 1, 2,..., Sp). Đối với quần thể kiến đầu tiên của ACO-GA, T0ij và gij được khỏi tạo là To và go tưong ứng, còn đối với những quần thể kiến tiếp theo, T0ij được khỏi tạo là tổng lượng mùi mà các cá thể kiến của quần thể kiến ỏ bước trước để lại, còn gij là tổng thông tin di truyền từ các cá thể kiến tốt nhất tìm được bỏi thuật toán GA ỏ các bước trước của thuật toán ACO-GA.
Chọn đỉnh tiếp theo: Giả sử, cá thể kiến thứ k đang ỏ đỉnh Vị và cần chọn đỉnh kế tiếp từ tập các đỉnh chưa thăm của cá thể kiến đó (ký hiệu tập đỉnh này là Nk) để di chuyển.
Algorithm 1. ACO-GA K Cj Sp, Tữ, go)	
Input: Kn, Cịị, Sp, T0, g0 tương ứng là đồ thị, ma trận chi phí, kích thước quần thế, giá trị khởi tạo vết mùi, thông tin di truyền.
Output: Cá thể tốt nhất tìm được Gk.
HKhởi tạo thông tin vết mùi và di truyền trên các cạnh P=<Z;//khm tạo quần thể rông for (i = 1; i < n; i++)
for ( = 1; j < n; j++)
y[i][/’] = To; g[i][/] = go;
while (điều kiện dừng của ACO-GA chưa thỏa) {k=0;
while (k < Sp)
{ rd = random(100);//rd là sâ ngâu nhiên €E (1, 1 00) Tk = {v1}; //khởi tạoTk gồm đỉnh xuất phát V1 vnext = v1; //khởi tạo đỉnh xuất phát vnext cho kiến while (|Tk| < n)
{	Đặt Nk = {Vj | Vj £Tỵ
//Chọn đỉnh kế tiếp nhờ roulette_Wheel vnext =roulette_Wheel(vnext, rd, Nk);
Tk = Tị,J {v1}; //bố sung đỉnh mới vào Tk
}//end of while (|Tk| < n)
HCập nhập thông tin vết mùi theo (2.4), (2.5) for (i = 1; i < n; i++) {
delta_r[Tk [i],Tk[i+1]] = ơ/ L(Tk);
T[Tk [i],Tk[i+1]] = (1-p)*T[Tk_[i],Tk[i+1]]^
+ delta_T [Tk [i],Tk[i+1]];
}//end of for (i = 1; i < n; i++)
k++;
P=P^{Tk};//bo sung cá thể kiến Tk vào quần thể P
}//end of while (k < Sp)
//Các bước của thuật toán di truyền
//Quần thể ban đầu P bao gồm các hành trình
//tạo được bởi các cá thể kiến
G* = cá thể tốt nhất trong quần thể P;
while (điều kiện dừng của thuật toán di truyền chưa thỏa)
{ Pad = 0; //khởi tạo tập các cá thế con
for (i = 1; i < Sp; i++) {
//Lựa chọn cá thể cha TP và cá thể mẹ TM
(TP, tM) = selectionOperator(P);
//hàm rand(1) trả lại số ngâu nhiên €E (0, 1) if (rand(1) < Pc) { //lai ghép cá thế cha mẹ TC = crossoVerOperator(TP, TM); if (random(1) < Pm) //đột biến cá thể con
TC = mutationOperator(TC);
TC=localSearch(TC); //tìm kiếm địa phương //cập nhập cá thế tốt nhất:
if (L(TC) < L(G*)) G* = TC;
Bố sung TC vào Pad;
}//end of if (rand(1) < Pc)
}//end of for (i = 1; i < Sp; i++)
P = tập gồm Sp cá thế tốt nhất trong P cPak, //Cập nhập thông tin di truyền theo (2.6), (2.7) for (i = 1; i < n; í++) {
delta_ g[G*[i],G*[i+1]] = ơ / L(G*);
g[G*[i],G*[i+1]] = g[G*[i],G*[i+1]] _
+ delta_ g[G*[i],G*[i+1]];
} //end of for (i = 1; i < n; i++)
}//end of while GA
}//end of while ACO-GA
return (cá thế tốt nhất tìm được bởi ACO-GA)
Algorithm 2. Function roulette_Wheel (vi, rd, Nk)	
Input: vi, rd, Nk tương ứng là đỉnh hiện tại, giá trị số trong khoảng 1 đến 100, tập các đỉnh chưa thăm trong Tk. Output: Đỉnh v được chọn đi kế tiếp vi.
sum_Prob = 0;
if (rd < 50) {
//loại kiến sử dụng vết mùi và thông tin di truyền for Vj£ Nk
sum_Prob = sum_Prob + pow(ĩ[i,j], p,)
*pow( 7 [i,/], PP) *pow(g[ij], Pg);
//lựa chọn đỉnh kế tiếp theo (2.1)
for Vj G.Nk
p[i,j} =	wpcVPỉ)*pow(^ j
*pow(g[ij], pg) / sum_Prob;
rd = random(sum_Prob); //0 < rd < sum_Prob for vj eNk{
sum_ wheel = sum_wheel + p[ij]; if (sum_wheel > rd) break;
}//end for vj €E Nk
,v = j	'
}//end if (rd < 50)
if (50 < rd < 80) {
//loại kiến chỉ sử dụng vết mùi
for Vj£ Nk
sum_Prob = sum_Prob + powipij], p,)
, *pow(^[ij], PP);
//chọn đỉnh kế tiếp theo (2.2)
for Vj£ Nk
p[ij\ = pow(T[ij],^)*pow(7 [i\/], PQ) /sum_Prob; rd = random(sum_Prob);
for VjeNk { sum_wheel = sum_wheel + p[i,j];
if (sum_wheel > rd) break;
}//end for vj G Nk
,v = vÁ
}//end if (50 < rd < 80)
if (rd > 80)///loại kiến ngâu nhiên
//chọn đỉnh kế tiếp theo (2.3) chọn ngẫu nhiên v e Nk;
return v;
Algorithm 3. Function selectionOperator(P)
Input: Quân thê P = {p[1], p[2], ..., p[Sp]}
Output: Cá thê cha TP ' và cá thê mẹ TM. '
//chọn một nhóm cá thể ngẫu nhiên từ quần thể P
IG=0; // Khởi tạo
for (i = 0; i < NG; i++) {
i = random(Sp);
IG= IGu {p[i]};
}//end of for (i = 0; i < NG; i++)
Sắp xếp các cá thể trong nhóm IG tăng dần theo độ trễ; //Chọn hai cá thể với độ trễ nhỏ nhất làm cá thể cha và mẹ TP = IG[0];
TM = IG[1];
return TP, TM;
Thuật toán ACO-GA duy trì ba loại kiến. Loại kiến đầu tiên sử dụng thông tin về vết mùi và thông tin về di truyền để lựa chọn đỉnh kế tiếp. Nếu cá thể kiến thứ k thuộc loại này, nó sẽ
di chuyển từ đỉnh Vj đến đỉnh Vj (Vj 2 Nk) với xác suất:
(2:1)
p1	[n-!ij I8- kfej Ị8’ [gij Ị8*
pkij P |rnijI8- ['gkijI8’ |9ijI8. •
Vj 2Nk
Loại kiến thứ hai chỉ sử dụng thông tin về vết mùi để lựa chọn đỉnh kế tiếp. Nếu cá thể kiến thứ k thuộc loại hai, thì nó sẽ di chuyển từ đỉnh vi đến đỉnh Vj với xác suất là:
p2 _	[Tfe-1ij|8- k/Ci.7]8’	(2 2)
Pkij = P k-iijI8-l^fcijI8’•	(:)
Vj 2Nk
Cuối cùng, loại kiến thứ ba không sử dụng bất cứ thông tin nào về mùi, cũng như thông tin di truyền. Nếu cá thể kiến thứ k thuộc loại này thì xác suất để nó di chuyển từ đỉnh vi đến đỉnh Vj là:
pkij = ĨNĨ •	(2:3)
ỏ đây 0T, và fig là các tham số, r//,.i; = 1/(pCị,j) (p là vị trí của cạnh (vi,Vj) trong đường đi của cá thể kiến thứ k). Công thức (2.1) và (2.2) được cải biên từ công thức có trong thuật toán ACO chuẩn của Marco Dorigo [7].
Số lượng kiến loại một, hai và ba sẽ được xác định một cách ngẫu nhiên với tỷ lệ tương ứng là 50%, 30% và 20% (theo nhận xét đã nêu ở trên, ta giữ 20% số lượng kiến không có khả năng sử dụng vết mùi để tìm đường đi). Để thực hiện điều này, khi cần xác định cá thể kiến hiện tại thuộc loại nào trong ba loại trên, ta gieo một số ngẫ ... á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ưong đố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,	Pc =	0.7,	Pm =	0.2,	l =	5 ,	=	1,	= 5,	fig	= 5, T =
10, To = 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
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-R1
35334
32779
35334
35334
6.2
32779
32779
0.00
1.12
TRP-100-R2
38442
33435
36773
36773
6.4
33435
33435
0.00
1.21
TRP-100-R3
37642
32390
35150
35320
7.1
32390
32390
0.00
0.84
TRP-100-R4
37508
34733
37508
37751
7.3
34733
34733
0.00
0.92
TRP-100-R5
37215
32598
35254
35254
6.7
32598
32598
0.00
1.04
TRP-100-R6
40422
34159
36988
36988
6.5
34212
34212
0.16
1.25
TRP-100-R7
37367
33375
36897
36941
6.3
33375
33375
0.00
0.81
TRP-100-R8
38086
31780
35408
35510
6.4
31780
31780
0.00
0.91
TRP-100-R9
36000
34167
36415
36574
6.8
34167
34167
0.00
0.72
TRP-100-R10
37761
31605
34018
34018
7.0
31812
31812
0.65
0.84
TRP-100-R11
37220
34188
37006
37006
7.1
34188
35534
0.00
0.85
TRP-100-R12
34785
32146
35437
35437
6.5
32899
32899
2.34
0.77
TRP-100-R13
37863
32604
35239
35512
6.7
31989
31989
-1.89
0.81
TRP-100-R14
36362
32433
34869
34869
6.8
33601
33601
3.60
0.92
TRP-100-R15
39381
32574
35640
35640
7.0
32574
32574
0.00
0.81
TRP-100-R16
39823
33566
37083
37083
6.9
34818
34818
3.73
0.85
TRP-100-R17
41824
34198
37058
37421
7.1
36297
36297
6.14
0.91
TRP-100-R18
39091
31929
35109
35109
7.2
31929
31929
0.00
0.84
TRP-100-R19
39941
33463
36457
36457
6.4
33463
33463
0.00
0.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
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 (UBọ U B\)
các thuật toán. Cột gap[%] ghi nhận giá tri gap\%] = 	2—	100%; trong đó UB2 và
U B1
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ưong ứng với giá tri 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ưong ứ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ả hon 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 hon 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 hon 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
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 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 (UB - OPT1	_	,	_	_ -
bình của các thuật toán tính bằng phút.
giá trị gap[%] =	OPT	-100% như trong ba bảng trước và cột T là thời gian chạy trung
Kết quả thực nghiệm trong Bảng 4 cho thấy thuật toán ACO-GA hiệu quả hon 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. Hon 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.
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 hon 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ả hon khi luôn đưa ra lời giải tốt hon 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
A. Archer, A. Levin, and D. Williamson, A faster, better approximation algorithm for the minimum latency problem, SIAM Journal on Computing 37 (1) (2007) 1472-1498.
S. Arora, and G. Karakostas, Approximation schemes for minimum latency problems, SIAM Journal on Computing 32 (2) (1999) 688-693.
H.B. Ban, and D.N. Nguyen, Improved genetic algorithm for minimum latency problem, Proceedings of ACM SOICT, Hanoi, Vietnam, 2010 (9-15).
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.
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).
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).
M. Dorigo, and T. Stutzle, Ant Colony Optimization, Bradford Books, London, 2004.
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).
H. Hasegawa, Optimization of GROUP behavior, Japan Ethological Society Newsletter (43) (2004) 22--23.
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.
S. Sahni, and T. Gonzalez, P-complete approximation problem, Journal on ACM 23 (3) (1976) 555-565.
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.
S. Shimomura, M. Sugimotoy, T. Haraguchiy, H. Matsushitaz, and Y. Nishioy, Ant colony optimization with intelligent and dull ants, Proceedings of Symposium on Nonlinear Theory and its Applications, Krakow, Poland, 2010 (504-507).
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.
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.
Ng ày nhận bài 01 - 3 - 2013
Nhận lại sau sửa ngày 10 - 8 - 2013