Giải thuật kiến song song giải bài toán cây khung nhỏ nhất có bậc bị chặn

JOURNAL OF SCIENCE OF HNUE DOI: 10.18173/2354-1075.2015-0052<br /> Educational Sci., 2015, Vol. 60, No. 7A, pp. 53-60<br /> This paper is available online at http://stdb.hnue.edu.vn<br /> <br /> <br /> <br /> <br /> GIẢI THUẬT KIẾN SONG SONG GIẢI BÀI TOÁN<br /> CÂY KHUNG NHỎ NHẤT CÓ BẬC BỊ CHẶN<br /> <br /> Bùi Thị Thủy, Phạm Thị Lan<br /> Khoa Công nghệ thông tin, Trường Đại học Sư phạm Hà Nội<br /> <br /> Tóm tắt. Cho một đồ thị G = (V, E) liên thông, có trọng số và một số nguyên dương d.<br /> Cây khung có bậc bị chặn của G là một cây khung trong đó các đỉnh của nó đều có bậc nhỏ<br /> hơn d. Bài toán tìm cây khung nhỏ nhất có bậc bị chặn của một đồ thị cho trước đã được<br /> chứng minh là bài toán NP - khó. Trong bài báo này, chúng tôi đề xuất giải thuật tối ưu hóa<br /> đàn kiến song song tìm cây khung nhỏ nhất có bậc bị chặn trên đồ thị có số đỉnh tương đối<br /> lớn.<br /> Từ khóa: Giải thuật kiến, cây khung tối ưu có bậc bị chặn, chiến lược song song, bài toán<br /> Np - khó, thuật toán song song.<br /> <br /> 1. Mở đầu<br /> Bài toán cây khung nhỏ nhất có bậc bị chặn (Degree – Constrained Minimum Spanning<br /> Tree (DCMST)) được nghiên cứu lần đầu tiên bởi 2 tác giả Deo và Hakimi [2]. Bài toán được phát<br /> biểu như sau:<br /> Input: Cho trước một đồ thị G = (V, E) với |V | = n, các cạnh được gán trọng số và một<br /> số nguyên dương d.<br /> Question: Có tồn tại hay không một cây khung nhỏ nhất T của G thỏa mãn điều kiện mọi<br /> đỉnh của T đều có bậc không vượt quá d.<br /> Có thể phát biểu lại bài toán dưới dạng tối ưu như sau:<br /> Cho đồ thị G = (V, E) có n đỉnh, m cạnh và cij > 0 là trọng số của mỗi cạnh eij .<br /> Giả sử<br /> (<br /> cij , eij ∈ E<br /> Xij = (1.1)<br /> 0, eij 6∈ E<br /> <br /> Với một số d nguyên dương, hãy xác định giá trị nhỏ nhất của biểu thức sau:<br /> X<br /> WT = cij Xij (1.2)<br /> i,j∈V,i6=j<br /> <br /> Ngày nhận bài: 20/7/2015. Ngày nhận đăng: 20/11/2015.<br /> Liên hệ: Bùi Thị Thủy, e-mail: btthuy@hnue.edu.vn<br /> <br /> <br /> <br /> <br /> 53<br />  Bùi Thị Thủy, Phạm Thị Lan<br /> <br /> <br /> Trong đó<br /> X<br /> Xij ≤ d với i ∈ V (1.3)<br /> j∈V,i6=j<br /> X<br /> Xij ≥ 1 với i ∈ V (1.4)<br /> j∈V,i6=j<br /> X<br /> Xij ≤ |N | − 1 với ∀N ⊆ V (1.5)<br /> i6=j<br /> <br /> <br /> Bài toán này có rất nhiều ứng dụng trong đời sống. Một số ứng dụng quan trọng của nó<br /> được kể đến như thiết kế tối ưu các mạng máy tính, viễn thông, thiết kế các mạch tích hợp, các<br /> mạng năng lượng, mạng lưới giao thông, thiết kế các hệ thống thủy lợi [3, 10].<br /> Xác định cây khung nhỏ nhất có bậc bị chặn được chứng minh là bài toán NP-khó [2, 13].<br /> Đã có nhiều giải thuật metaheuristic được giới thiệu để giải bài toán này như giải thuật tiến hóa<br /> [9], giải thuật di truyền [1], giải thuật đàn kiến [11, 12, 13]. . . Tuy giải thuật đàn kiến đã được sử<br /> dụng để giải quyết bài toán DCMST nhưng mới chỉ dừng lại ở thuật toán tuần tự, chưa có thuật<br /> toán song song. Trong bài báo này, chúng tôi sử dụng giải thuật tối ưu hóa đàn kiến để giải quyết<br /> bài toán theo hướng song song hóa với các mô hình song song khác nhau nhằm tối ưu hóa kết quả<br /> và tăng tốc trong tính toán.<br /> Để chứng tỏ hiệu quả của các thuật toán song song so với tuần tự, chúng tôi đã cài đặt thực<br /> nghiệm. Kết quả nhận được cho thấy mô hình song song hiệu quả hơn mô hình tuần tự.<br /> <br /> 2. Nội dung nghiên cứu<br /> 2.1. Giải thuật tối ưu hóa đàn kiến (Ant Colony Optimization - ACO)<br /> Trong khoa học máy tính, giải thuật tối ưu hóa đàn kiến (Ant Colony Optimization – ACO)<br /> là một mô hình cho việc thiết kế các giải thuật tìm kiếm siêu kinh nghiệm (metaheuristic) để giải<br /> quyết các bài toán tối ưu tổ hợp có thể quy về việc tìm kiếm đường đi tốt nhất trên đồ thị. Giải<br /> thuật này là một thành viên của họ các giải thuật đàn kiến trong các phương pháp tri thức bầy đàn<br /> (swarm intelligence). Phương pháp này là một hướng tiếp cận khá mới mẻ để giải quyết các bài<br /> toán dựa trên các hành xử xã hội của các loài vật, trong đó có loài kiến.<br /> Từ đàn kiến tự nhiên đến giải thuật ACO<br /> Kiến là loài côn trùng có tính chất xã hội. Chúng sống thành từng đàn trong tự nhiên và giữa<br /> chúng có tác động qua lại với nhau. Trong quá trình di chuyển từ tổ tới nguồn thức ăn, các con kiến<br /> có để lại trên mặt đất một chất hóa học tiết ra từ cơ thể của chúng. Chất hóa học này được gọi là<br /> mùi kiến (pheromone). Nếu không có mùi kiến sẵn có trên đường đi, các con kiến di chuyển ngẫu<br /> nhiên. Nhưng khi có mặt của mùi kiến, chúng có xu hướng di chuyển theo mùi đó. Trên thực tế<br /> các nghiên cứu của các nhà sinh học chỉ ra rằng theo thuyết tự nhiên, kiến thích những con đường<br /> được đánh dấu bởi nhiều mùi kiến. Con đường nào có nồng độ mùi càng cao thì xác suất được<br /> kiến chọn để đi qua càng lớn. Vì mùi kiến chỉ là một chất hóa học nên nó sẽ bị bay hơi theo thời<br /> gian [6]. Tuy nhiên, một số nhà nghiên cứu sinh học cũng chỉ ra rằng mùi là rất bền nên sự bay hơi<br /> của nó không ảnh hưởng nhiều đến đường đi ngắn nhất. Theo cơ chế này thì các con kiến sau một<br /> vài lần di chuyển sẽ tìm ra một con đường tốt nhất tới nguồn thức ăn. Con đường ngắn nhất là con<br /> đường có độ mùi lớn nhất và có nhiều kiến đi nhất.<br /> Dựa trên hoạt động tìm kiếm thức ăn của đàn kiến trong tự nhiên, Marco Dorigo đã xây<br /> dựng giải thuật đàn kiến. Trong giải thuật, đàn kiến tự nhiên được mô hình hóa thành một đàn kiến<br /> <br /> 54<br />  Giải thuật kiến song song giải bài toán cây khung nhỏ nhất có bậc bị chặn<br /> <br /> <br /> nhân tạo, mùi kiến tự nhiên được thay thế bằng mùi nhân tạo. Ý tưởng cơ bản của ACO là đàn kiến<br /> nhân tạo sẽ xây dựng lời giải cho bài toán bằng việc hoạt động trên một đồ thị. Mỗi cạnh của đồ thị<br /> được gắn thông tin cho phép dự đoán xem cạnh đó có được kiến lựa chọn để đi qua hay không [8].<br /> Thông tin đó gọi là thông tin hướng dẫn kiến di chuyển và bao gồm:<br /> • Thông tin kinh nghiệm: giới hạn kinh nghiệm di chuyển từ đỉnh i tới đỉnh j, gắn với cạnh<br /> eij kí hiệu là ηij . Thông tin kinh nghiệm không được thay đổi bởi các con kiến trong suốt<br /> quá trình chạy thuật toán.<br /> • Thông tin mùi kiến nhân tạo: kí hiệu là τij cho mỗi cạnh eij . Đây là mùi kiến nhân tạo ứng<br /> với mỗi kiến nhân tạo, có tác dụng trong việc tính xác suất để lựa chọn đường đi cho kiến.<br /> Thông tin này bị thay đổi trong suốt quá trình thực hiện giải thuật.<br /> Như vậy, từ đàn kiến tự nhiên đến giải thuật ACO là quá trình xây dựng mô hình giải thuật<br /> tìm kiếm đường đi tối ưu dựa trên hoạt động tìm kiếm thức ăn của đàn kiến. Nhân tố chính trong<br /> giải thuật ACO là đàn kiến nhân tạo cùng với các tham số về mùi kiến, sự bay hơi của mùi kiến và<br /> cơ chế lựa chọn đường đi dựa trên nồng độ mùi hương.<br /> Giải thuật ACO - Metaheuristic<br /> Giải thuật ACO hoạt động dựa trên sự tương tác lẫn nhau giữa ba thủ tục sau đây: xây dựng<br /> lời giải của các kiến (ConstructAntsSolutions), cập nhật vệt mùi (UpdatePheromones) và các hành<br /> động chung (daemon actions) [12].<br /> • ConstructAntsSolutions cho phép những con kiến nhân tạo di chuyển đồng thời nhưng không<br /> đồng bộ qua các trạng thái liền kề của bài toán. Sự di chuyển này theo một tập quy tắc dựa<br /> trên các thông tin kinh nghiệm và thông tin về mùi kiến để hướng dẫn tìm kiếm. Qua sự di<br /> chuyển trên đồ thị, kiến xây dựng được lời giải cho bài toán. Trong quá trình xây dựng lời<br /> giải, mỗi con kiến sẽ giải phóng mùi lại mỗi lần nó đi qua một cạnh. Mùi kiến này sẽ góp<br /> phần hướng dẫn tìm kiếm cho những con kiến đi sau.<br /> • UpdatePheromones là quá trình trong đó các vệt mùi bị thay đổi. Giá trị của vệt mùi cũng<br /> có thể tăng lên hoặc giảm đi. Vệt mùi tăng giá trị khi kiến để lại mùi trên các thành phần<br /> hoặc đường đi nó đi qua. Trường hợp ngược lại là do sự bay hơi của mùi kiến trong tự nhiên.<br /> Thực tế ta thấy, việc để lại mùi mới trên các đường kiến đi qua làm tăng thêm khả năng mà<br /> con đường đó có thể được lựa chọn bởi nhiều con kiến khác, và điều này có tác dụng tạo ra<br /> một con đường rất tốt có thể được sử dụng lại bởi các con kiến sau. Ngược lại, sự bay hơi<br /> của mùi kiến sẽ ngăn chặn sự hội tụ quá nhanh của giải thuật tới một vùng gần điểm cực<br /> thuận và cho phép kiến khảo sát không gian tìm kiếm mới.<br /> • Daemon actions được sử dụng để cài đặt các hoạt động chung, là những hoạt động không<br /> được thực thi bởi những con kiến riêng lẻ. Những hoạt động đó có thể là sự hoạt hóa một<br /> thủ tục tối ưu hóa cục bộ hay sự góp nhặt các thông tin cục bộ. . .<br /> Giải thuật ACO – metaheuristic có thể được viết bằng giả mã như sau:<br /> <br /> Procedure ACO – Metaheuristic;<br /> ScheduleActivities<br /> ConstructAntsSolutions;<br /> UpdatePheromones;<br /> DaemonActions;<br /> End – ScheduleActivities<br /> End – Procedure;<br /> <br /> <br /> 55<br />  Bùi Thị Thủy, Phạm Thị Lan<br /> <br /> <br /> Như vậy, ý tưởng chính của giải thuật ACO – Metaheuristic chính là sự lặp lại các mối quan<br /> hệ lẫn nhau giữa ba thành phần con bao gồm: hoạt động của đàn kiến, cập nhật vệt mùi và các hoạt<br /> động khác. Ngày nay, có nhiều cài đặt thành công giải thuật ACO và nó cũng được áp dụng để giải<br /> rất nhiều bài toán tối ưu tổ hợp khác nhau.<br /> <br /> 2.2. Giải thuật ACO giải bài toán cây khung nhỏ nhất có bậc bị chặn<br /> 2.2.1. Khung ACO tuần tự<br /> Ý tưởng của việc áp dụng ACO vào bài toán cây khung nhỏ nhất có bậc bị chặn (DCMST) có<br /> thể tóm tắt như sau: trước tiên xác định cây khung có bậc bị chặn (Degree – Constrained Spanning<br /> tree, d – ST), sau đó dựa trên những cây d – ST này, xác định cây khung nhỏ nhất có bậc bị chặn.<br /> Dựa trên ý tưởng đó, ta có khung ACO tuần tự được thiết kế như sau:<br /> Cho đồ thị liên thông, vô hướng, có trọng số G = (V, E). Một đàn kiến có số lượng kiến là<br /> m = |V |. Tại mỗi bước lặp của thuật toán, mỗi con kiến sẽ xây dựng cho riêng mình một cây d –<br /> ST. Trong quá trình xây dựng cây d – ST, các con kiến sẽ sử dụng tập cạnh E để phục vụ cho việc<br /> xây dựng lời giải. Hàm mục tiêu f trả về tổng trọng số của của một cây khung có bậc bị chặn Sk<br /> được tìm ra bởi con kiến k. Gọi wij là trọng số của cạnh eij và τij là nồng độ mùi trên cạnh eij .<br /> Giá trị khởi tạo cho nồng độ mùi trên mỗi cạnh là τ0 = 10−6 . Giải thuật ACO có thể được mô tả<br /> qua một số bước lặp sau:<br /> 1. Đàn kiến nhân tạo mAnts có số lượng là |V | được khởi tạo tại các đỉnh một cách ngẫu nhiên<br /> (mỗi con một đỉnh)<br /> 2. Mỗi con kiến k nào đó sẽ xây dựng một cây d – ST hợp lệ. Nó luôn chứa một danh sách Jk<br /> các cạnh mà nó có thể đi qua.<br /> 3. Tại bước r của vòng lặp thứ t, mỗi con kiến k sẽ lựa chọn cạnh mà nó chưa qua. Cạnh được<br /> chọn sẽ là cạnh liên thuộc với cây d – ST được xây dựng tại bước r − 1, tất nhiên khi thêm<br /> cạnh vào cây thì ta vẫn thu được cây d – ST hợp lệ. Xác suất lựa chọn cạnh như sau:<br />  α β<br />  P[τeij (t)] [ηeij ] , ∀l ∈ J (e ), η = 1<br /> <br /> α β k ij eij wij<br /> pkeij = l∈Jk [τel (t)] [ηel ] (2.1)<br /> 0, ngược lại<br /> <br /> <br /> Trong đó:<br /> (<br /> wij nếu wij > 0<br /> wij = (2.2)<br /> 0, nếuwij = 0<br /> <br /> Với α và β là hai tham số dương chi phối sự ảnh hưởng tương ứng của nồng độ mùi và trọng<br /> số của cạnh eij tới sự quyết định của kiến trong đó ηij = w1ij .<br /> 4. Sau khi mỗi con kiến hoàn thành một cây d – ST, giá trị mùi được cập nhật lại theo công<br /> thức sau:<br /> mAnts<br /> X<br /> τeij (t+1) = (1 − ρ)τeij (t) + △τek (2.3)<br /> ij<br /> k=1<br /> <br /> Trong đó:<br /> △τekij = ρτ0 cập nhật cục bộ (2.4)<br /> <br /> 56<br />  Giải thuật kiến song song giải bài toán cây khung nhỏ nhất có bậc bị chặn<br /> <br /> <br /> Hoặc<br /> Q<br /> (<br /> nếu eij ∈ d − ST bg<br /> △τekij = Lbg<br /> cập nhật toàn cục (2.5)<br /> 0, nếu ngược lại<br /> <br /> Với ρ là hệ số bay hơi, Lgb là trọng số của cây khung có bậc bị chặn nhỏ nhất toàn cục<br /> d − ST gb , Q là hằng số nguyên dương.<br /> Kí hiệu thuật toán ACO tuần tự là ACOSE .<br /> 2.2.2. Khung ACO song song<br /> <br /> <br /> <br /> <br /> Hình 1. Mô hình ACOR<br /> Về cơ bản, các bước trong<br /> khung giải thuật song song giống với<br /> khung tuần tự, nhưng khác ở chỗ: việc<br /> thực hiện giải thuật được tiến hành<br /> đồng thời trên các bộ xử lí khác nhau,<br /> ở đó các bộ xử lí giao tiếp với nhau<br /> qua mạng liên kết tạo thành hệ thống<br /> song song với bộ nhớ phân tán. Mỗi<br /> bộ xử lí sẽ đảm nhận công việc tìm<br /> kiếm cây khung nhỏ nhất có bậc bị<br /> chặn của một nhóm các con kiến (đàn<br /> kiến). Sau một số bước lặp nhất định,<br /> sẽ có sự hoán đổi lời giải tối ưu và ma<br /> trận mùi tương ứng với lời giải tối ưu<br /> đó giữa các bộ xử lí. Giả sử có n bộ<br /> xử lí, khi đó số kiến được phân phát<br /> trên mỗi bộ xử lí là [mAnts/n]. Ở<br /> đây, chúng tôi trình bày các mô hình<br /> giao tiếp trong mạng liên kết các bộ<br /> xử lí để hoán đổi thông tin như sau:<br /> Hình 2. Mô hình ACOMS<br /> Mô hình vòng (Hình 1):<br /> Trong mô hình này, n bộ xử lí (n đàn kiến) sẽ kết nối với nhau tạo thành một vòng một chiều.<br /> Sau khi n đàn kiến tìm xong lời giải tối ưu của riêng mình, việc hoán đổi lời giải được tiến hành<br /> như sau: bộ xử lí i sẽ gửi lời giải tối ưu của mình cho bộ xử lí thứ [(i + 1)mod n] và nhận lời giải<br /> tối ưu được gửi đến từ bộ xử lí thứ [(i − 1 + n)mod n]. Sau đó các bộ xử lí tiếp tục thực hiện việc<br /> tìm kiếm của mình. Kí hiệu thuật toán theo mô hình này là ACOR .<br /> <br /> 57<br />  Bùi Thị Thủy, Phạm Thị Lan<br /> <br /> <br /> Mô hình “Master - Slave” (Hình 2): Trong mô hình song song này, các bộ xử lí sẽ giao<br /> tiếp với nhau và cùng hợp tác để tìm lời giải tối ưu. Một bộ xử lí đóng vai trò Master và n − 1 bộ<br /> xử lí còn lại sẽ đóng vai trò là Slave. Nhiệm vụ của mỗi Slave là tìm kiếm lời giải tối ưu của riêng<br /> mình. Sau đó Master làm nhiệm vụ lọc ra lời giải tối ưu nhất trong n − 1 lời giải tối ưu của các<br /> Slave và quảng bá cho các Slave danh tính của Slave có lời giải tối ưu nhất đó để các Slave còn lại<br /> sao chép thông tin lời giải tối ưu nhất này hay nói khác đi là sao chép ma trận mùi hương. Sau đó<br /> các Slave tiếp tục tìm kiếm với trạng thái ma trận mùi vừa sao chép được. Kí hiệu thuật toán theo<br /> mô hình này là ACOMS .<br /> <br /> 2.3. Kết quả thực nghiệm<br /> Chương trình thực nghiệm được cài đặt bằng ngôn ngữ C++ và thực thi trên 04 máy tính<br /> có kết nối LAN. Do bài toán chưa có bộ test chuẩn nên các bộ dữ liệu thực nghiệm được sinh ngẫu<br /> nhiên trên các đồ thị có 40 đỉnh và có số cạnh thay đổi. Các kết quả khi thực hiện các thuật toán<br /> ACOSE , ACOMS và ACOR được thể hiện trong bảng 1 và 2.<br /> <br /> Bảng 1. Thời gian chạy của thuật toán Bảng 2. So sánh trọng số nhỏ nhất của<br /> tuần tự và song song cây tìm được khi thực hiện ACOSE , ACOMS , ACOR<br /> Bộ dữ Số Bộ dữ Số<br /> ACOSE ACOMS ACOR ACOSE ACOMS ACOR<br /> liệu cạnh liệu cạnh<br /> 1 410 18544 18235 18476 1 410 218 226 196<br /> 2 420 18725 18535 18691 2 420 198 202 174<br /> 3 430 18885 18720 18826 3 430 249 235 217<br /> 4 440 19124 18902 19103 4 440 185 201 167<br /> 5 450 20754 19928 20681 5 450 229 218 192<br /> 6 460 22438 20365 22452 6 460 206 213 189<br /> Từ các kết quả trên, chúng tôi có biểu đồ so sánh thời gian và giá trị hàm mục tiêu của bài<br /> toán khi thực thi các thuật toán ACOSE , ACOMS , ACOR như trong Hình 3 và Hình 4.<br /> <br /> <br /> <br /> <br /> Hình 3. Biểu đồ so sánh thời gian thực thi của các thuật toán ACOSE , ACOMS , ACOR<br /> <br /> 58<br />  Giải thuật kiến song song giải bài toán cây khung nhỏ nhất có bậc bị chặn<br /> <br /> <br /> <br /> <br /> Hình 4. Biểu đồ so sánh trọng số nhỏ nhất của cây tìm được<br /> khi thực hiện thuật toán ACOSE , ACOMS , ACOR<br /> <br /> Kết quả trên cho thấy, thuật toán kiến song song ACOMS và ACOR thực thi trong thời gian<br /> ít hơn so với thuật toán kiến tuần tự ACOSE , đồng thời chúng cho lời giải tối ưu hơn so với ACOSE .<br /> Thời gian thực hiện ACOMS là ngắn nhất do trong quá trình thực hiện các vòng lặp, công việc<br /> đã được chia sẻ cho các bộ xử lí Slave cùng thực hiện. ACOR có thời gian thực thi tiệm cận với<br /> ACOSE do mỗi bộ xử lí trong mô hình này thực thi công việc giống như trong ACOSE , chỉ khác là<br /> trong ACOSE chỉ có một bộ xử lí thực hiện thì trong ACOR có n bộ xử lí thực hiện và sau một số<br /> bước lặp nhất định, các bộ xử lí sẽ trao đổi thông tin cho nhau. Việc làm này sẽ làm tăng không<br /> gian lời giải tìm được, từ đó sẽ tìm được lời giải tối ưu hơn so với ACOSE và ACOMS . Như vậy, mô<br /> hình ACOMS sẽ phù hợp khi muốn tăng tốc thời gian giải bài toán, mô hình ACOR nên sử dụng<br /> khi muốn tìm kiếm lời giải tối ưu nhất của bài toán.<br /> <br /> 3. Kết luận<br /> Giải thuật tối ưu hóa đàn kiến (ACO) đã và đang được ứng dụng để giải các bài toán tối ưu<br /> tổ hợp trong đó có bài toán xác định cây khung nhỏ nhất có bậc bị chặn. Việc xây dựng các mô<br /> hình song song giải thuật đàn kiến giải bài toán này là cần thiết nhằm góp phần rút ngắn thời gian<br /> giải quyết cũng như tìm ra lời giải tốt nhất cho bài toán. Trong bài báo này, chúng tôi đã trình bày<br /> một cách tổng quan nhất về bài toán Cây khung nhỏ nhất có bậc bị chặn, giải thuật đàn kiến và<br /> hai chiến lược song song giải thuật đàn kiến để giải bài toán trên. Và kết quả thực nghiệm đã cho<br /> thấy hiệu quả của hai thuật toán song song đó. Trong thời gian tới, chúng tôi tiếp tục thử nghiệm<br /> thuật toán kiến theo các mô hình song song mới để giải bài toán này như mô hình thay thế lời giải<br /> tồi nhất, hoặc mô hình siêu khối, . . . Các mô hình này sẽ được cài đặt thực nghiệm trên hệ đa xử<br /> lí phân tán với số lượng các bộ xử lí lớn hơn 4 là 8, 16 bộ xử lí. Đồng thời, chúng tôi sẽ có sự cải<br /> tiến trong cách thức cập nhật ma trận mùi nhằm tăng tốc trong việc sinh lời giải và hội tụ tới lời<br /> giải tối ưu nhất.<br /> <br /> TÀI LIỆU THAM KHẢO<br /> <br /> [1] G.Zhou, M. Gen and T. Wu. A new approach to the DCMSTP using GA. Proceedings of the<br /> International Conference on System, Man and Cybernetics, Vol. 4, pp. 2683–2688, 1996.<br /> [2] N. Deo and S. L. Hakimi. The shortest generalized Hamiltonian tree. Proceeding of the 6th<br /> Annual Allerton Conference, pp. 879–888, 1968.<br /> <br /> 59<br />  Bùi Thị Thủy, Phạm Thị Lan<br /> <br /> <br /> [3] Narula and C. A. Ho . Degree Constrained Minimun Spanning Tree. Computer and<br /> Operations Research, pp. 239-249, 1980.<br /> [4] Marco Dorigo and V. Maniezzo, A. Colorni. Ant System: Optimization by a colony of<br /> cooperating agents. IEEE Transactions on Systems, Man, and Cybernetics – Part B, vol.<br /> 26, no. 1, pp. 29–41, 1996.<br /> [5] Marco Dorigo and Thomas Stutzle. The Ant Colony Optimization Metaheuristic: Algorithms,<br /> Applications, and Advances.Technical Report IRIDIA-2000-32, 2000.<br /> [6] Marco Dorigo and Thomas Stutzle. Ant Colony Optimization.The MIT Press, pages 278–285,<br /> 2004.<br /> [7] Max Manfrin, Mauro Birattari, Thomas Stutzle and Marco Dorigo. Parallel Ant Colony<br /> Optimization for the Traveling Salesman Problem. 5th International Workshop ANTS 2006<br /> proccedings, p224–234, 2006.<br /> [8] Marco Dorigo, Mauro Birattari and Thomas Stutzle. Ant Conlony Optimization: Artificial<br /> Ants as a Computational Intelligence Technique. Iridia - Technical report series, 2006.<br /> [9] R. Raide. Efficient evolution algorithm for the DCMSTP. Proceedings of the 2000 Congress<br /> on Evolutionary Computation, pp. 104–111, Vol.1, 2000.<br /> [10] Savelsbergh, M. and T. Volgenant. Edge exchanges in the Degree-Constrained minimum<br /> spanning tree. Computers and Operation Research, pp. 341–348, 1985.<br /> [11] Thang N.Bui, Catherine M. Zrncic. An ant-based algorithm for finding DCMST. Proceeding<br /> of the 8th annual conference on Genetic and evolution computation, pp.11–18, 2006.<br /> [12] Thang N.Bui. An improved ant-based algorithm for the DCMSTP. IEEE transactions on<br /> Evolutionary Computation, Vol. 16, Iss. 2, pp.266–278, 2011.<br /> [13] Yoon - Teck Bau, Chin - Kuan Ho and Hong - Tat Ewe. Ant Colony Optimization Approaches<br /> to the Degree - constrained minimum spanning tree. Journal of Information and Engineering<br /> 24, pp.1081–1094, 2008.<br /> <br /> ABSTRACT<br /> <br /> Parallel Ant Colony Optimization algorithm<br /> to solve Degree - constrained minimum spanning tree problem<br /> <br /> Let G = (V, E) denote the connected weighted undirected graph and a positive integer d. A<br /> degree-constrained spanning tree of graph G is a spanning tree where each vertex in the tree has a<br /> degree of at most d. The problem of finding the degree-constrained spanning tree of minimum cost<br /> in an weighted graph is called the degree-constrained minimum spanning tree (DCMST) known as<br /> NP-Hard. In this study, we propose a parallel Ant Colony Optimization (ACO) algorithm which<br /> finds solution for the DCMST problem in many instances.<br /> Keywords: Ant Colony Optimization, Degree - constrained minimum spanning tree,<br /> parallel strategies, NP-hard problem, parallel algorithm.<br /> <br /> <br /> <br /> <br /> 60<br />