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 - Bùi Thị Thủy

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