TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
VIỆN CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG
──────── * ───────
ĐỒ ÁN
TỐT NGHIỆP ĐẠI HỌC
NGÀNH CÔNG NGHỆ THÔNG TIN

NGHIÊN CỨU, CÀI ĐẶT THUẬT TOÁN
BẦY KIẾN DÙNG BOOST GIẢI BÀI TOÁN
TẬP HÀNH TRÌNH NHỎ NHẤT

Sinh viên thực hiện : Trần Đình Quang
Lớp CNTT1-K54
Giáo viên hướng dẫn : PGS.TS.
Huỳnh Quyết Thắng
HÀ NỘI 12-2013
PHIẾU GIAO NHIỆM VỤ ĐỒ ÁN TỐT NGHIỆP
1. Thông tin sinh viên
Họ và tên sinh viên: Trần Đình Quang
Điện thoại liên lạc: 01656120962 Email:
Lớp: CNTT1-K54 Hệ đào tạo: Kỹ sư công nghệ thông tin
Đồ án tốt nghiệp được thực hiện tại: Viện công nghệ thông tin & Truyền thông-
Trường đại học Bách Khoa Hà Nội
Thời gian làm đồ án: Từ 9/2013 đến 12/2013
2. Mục đích nội dung của đồ án tốt nghiệp
Mục đích của đồ án này là nghiên cứu giải thuật bầy kiến tối ưu, một số biến thể
của giải thuật bầy kiến tối ưu, đề xuất và ứng dụng giải thuật bầy kiến tối ưu để giải
quyết bài toán tập hành trình nhỏ nhất, nghiên cứu thư viện boost và sử dụng thư
viện boost hỗ trợ cài đặt thuật toán.
3. Các nhiệm vụ cụ thể của ĐATN
- Trình bày về giải thuật tối ưu bầy kiến, một số biến thể thông dụng của giải

Công nghệ thông tin & truyền thông và bộ môn Công nghệ phần mềm đã tận tâm dạy dỗ
chúng em trong suốt những năm học vừa qua. Chính nhờ công lao giảng dạy, chỉ bảo tận
tình của các thầy các cô mà chúng em, những sinh viên khoa Công nghệ thông tin mới có
được những kiến thức chuyên ngành về công nghệ thông tin để có thể vững bước thực hiện
tiếp chặng đường học tập, vận dụng và sáng tạo ra những sản phẩm công nghệ thông tin
hữu ích góp phần phục vụ các lĩnh vực khác nhau của cuộc sống.
Em xin bày tỏ lòng biết ơn sâu sắc tới thầy giáo, PGS.TS. Huỳnh Quyết Thắng, người
đã tận tình chỉ bảo, giúp đỡ, tạo điều kiện cho em trong suốt quá trình làm đồ án tốt nghiệp,
đồng thời cho em những lời khuyên quý báu để hoàn thành đồ án này.
Em xin chân thành cảm ơn sâu sắc tới Thầy giáo Ths.Ban Hà Bằng đã cùng em nghiên
cứu và hướng dẫn em thực hiện đồ án.
Tôi xin giửi lời cảm ơn tới các Anh/Chị các khóa trên và các bạn K54 lớp CNTT1 đã
chỉ dẫn cũng như cho những ý kiến quí báu cho đồ án này.
Cuối cùng con xin giửi tới Ông, Bà, Cha, Mẹ, cùng toàn thể Gia đình lòng biết ơn và
tình cảm yêu thương.

Hà Nội, ngày 16 tháng 12 năm 2013
Tác giả ĐATN

Trần Đình Quang
…………………………………………………………………………………………………………………
Sinh viên thực hiện: Trần Đình Quang-20093577-Lớp Công nghệ thông tin 1- K54 Trang 3
TÓM TẮT ĐỒ ÁN
Đồ án này được thực hiện nhằm giải quyết bài toán tối ưu “ Tập hành trình nhỏ nhất” .
Bài toán tập hành trình nhỏ nhất có nhiều ý nghĩa trong thực tế, đặc biệt là sắp xếp các
tuyến xe bus cho các thành phố lớn, hiện đại. Trong đồ án này, hướng giải quyết bài toán là
gần đúng, áp dụng thuật toán bầy kiến tối ưu song song để giải quyết vấn đề. Để cài đặt
thuật toán, trong đồ án này đã sử dụng thư viện boost cho mô hình lập trình song song. Các
kết quả đạt được của đồ án mang tính tương đối, do chưa có các kết quả tối ưu thực sự để
so sánh. Tuy nhiên, đồ án đã đạt được mục tiêu về các giải pháp cho bài toán tối ưu, các

Hình 10. Đồ thị mô tả biến thiên % sai số theo  ………………………… 54
Hình 11. Đồ thị mô tả biến thiên % sai số theo Δ ………………………… 55
Hình 12. Đồ thị mô tả sự biến thiên của Cost best theo ……………… 56
Hình 13. Đồ thị mô tả sự biến thiên của Time theo ………………… 57
…………………………………………………………………………………………………………………
Sinh viên thực hiện: Trần Đình Quang-20093577-Lớp Công nghệ thông tin 1- K54 Trang 5
DANH MỤC CÁC BẢNG
Bảng 1. Các thủ tục xây dựng trong thuật toán………………………………… 40
Bảng 2. Thống kê dữ liệu trong trường hợp  thay đổi……………………………52
Bảng 3. Thống kê dữ liệu trong trường hợp  thay đổi……………………………53
Bảng 4. Thống kê dữ liệu trong trường hợp  thay đổi……………………………54
Bảng 5. Thống kê dữ liệu trong trường hợp Δ thay đổi……………………………55
Bảng 6. Kết quả chạy thuật toán với 5 bộ dữ liệu ngẫu nhiên ………………… 56
Bảng 7. Kết quả chạy thuật toán với bộ dữ liệu thực nghiệm Budapest ……… 57
…………………………………………………………………………………………………………………
Sinh viên thực hiện: Trần Đình Quang-20093577-Lớp Công nghệ thông tin 1- K54 Trang 6
DANH MỤC CÁC TỪ VIẾT TẮT VÀ THUẬT NGỮ
Chữ Viết
tắt
Tiếng Anh Nghĩa Tiếng Việt
TSP Travelling Salesman Problem Bài toán người du lịch đưa hàng
ACO Ant Colony Optimial Thuật toán bầy kiến tối ưu
ACS Ant Colony System Hệ thống bầy kiến
AS Ant System Hệ thống kiến
MMAS Max-Min Ant System Hệ thống kiến lớn nhất- nhỏ nhất
…………………………………………………………………………………………………………………
Sinh viên thực hiện: Trần Đình Quang-20093577-Lớp Công nghệ thông tin 1- K54 Trang 7
QAP Quadratic Assignment Problem Bài toán phân bậc hai
RBAS Rank- Based Ant System Hệ thống xếp hạng kiến
BWAS Best- Worst Ant System Hệ thống kiến tồi nhất

là thuật toán bầy kiến tối ưu. Thuật toán bầy kiến tối ưu được đánh giá là có nhiều
ưu điểm trong việc giải quyết các bài toán tối ưu rời rạc về các phương diện như dễ
cài đặt, thời gian xử lý là chấp nhận được và các kết quả tìm được không sai khác
nhiều với các kết quả tối ưu đã tìm được trước đó và đã có nhiều công trình nghiên
cứu áp dụng thuật toán bầy kiến tối ưu thành công cho một lớp bài toán tối ưu rời
rạc như bài toán người du lịch đưa hàng (TSP). Từ đó thông qua phân tích bài toán
với các bài toán tối ưu đã được áp dụng thành công trước đó đã quyết định áp dụng
giải thuật bầy kiến tối ưu để giải quyết bài toán tập hành trình nhỏ nhất, thêm vào
đó sẽ có một số cải tiến như sử dụng mô hình song song để giảm thời gian xử lý của
thuật toán.

Trong đồ án này, em xin trình bày về thuật toán bầy kiến tối ưu và áp dụng thuật
toán bầy kiến tối ưu vào giải bài toán tập hành trình nhỏ nhất, trong phần cài đặt
theo mô hình song song sẽ được hỗ trợ bởi thư viện boost. Cụ thể và chi tiết sẽ được
trình bày trong các phần tiếp theo sau đây.
CHƯƠNG 1. CƠ SỞ LÝ THUYẾT VÀ CÔNG CỤ
1.1 Giải thuật bầy kiến tối ưu
Trong thế giới sinh vật hầu hết các loài vật đều sống tập trung theo từng bầy đàn
và điều đó giúp cho các loài vật tồn tại được trong thế giới. Không những thế, việc
sống theo bầy đàn và có sự trao đổi thông tin trong các loài vât giúp cho các loài vật
đó có thể kiếm được các nguồn thức ăn mới và tiêu hao năng lượng ít hơn. Loài
kiến là một trong những loài vật như vậy. Không những thế, loài kiến còn được xem
là một trong những loài vật thông minh về tìm kiếm các nguồn thức ăn mới một
cách nhanh nhất. Loài kiến với những biểu hiện hành vi mang tính xã hội bầy đàn
rất phức tạp và điều đó đã thu hút sự chú ý của con người từ rất lâu. Có lẽ một trong
các hành động đáng chú ý nhất của chúng đó là luôn đi theo hàng ngũ, di chuyển
…………………………………………………………………………………………………………………
Sinh viên thực hiện: Trần Đình Quang-20093577-Lớp Công nghệ thông tin 1- K54 Trang 9
theo từng đàn. Chắc hẳn ai trong chúng ta thời niên thiếu cũng đã từng giẫm chân
lên đàn kiến đang đi hoặc đặt vài viên đá, gạch để chặn đường đi của chúng hoặc

Metaheuristic là một tập các khái niệm về thuật toán được sử dụng để xác định các
phương thức tìm kiếm thích hợp cho một tập các vấn đề khác nhau. Hay nói cách
khác, một siêu tìm kiếm ( meta-heuristic) có thể coi là một phương thức tìm kiếm
đa năng.
ACO là một meta-heuristic, trong đó một tập các con kiến nhân tạo phối hợp tìm
kiếm các giải pháp tốt cho các vấn đề về tối ưu rời rạc. Sự phối hợp là yếu tố cối lõi
…………………………………………………………………………………………………………………
Sinh viên thực hiện: Trần Đình Quang-20093577-Lớp Công nghệ thông tin 1- K54 Trang 10
của các thuật toán ACO. Các con kiến nhân tạo liên lạc với nhau thông qua trung
gian mà ta thường gọi là mùi.
Các thuật toán ACO được sử dụng để giải quyết các vấn đề về tối ưu tổ hợp tĩnh
và động. Các vấn đề tĩnh là các vấn đề mà ở đó các đặc tính của vấn đề là không
thay đổi trong suốt quá trình giải quyết vấn đề. Còn các vấn đề động thì ngược lại là
một hàm các tham số mà giá trị của nó là động hay thay đổi trong quá trình giải
quyết vấn đề, ví dụ bài toán người đưa thư là một vấn đề dynamic problem
Hệ thống ACO lần đầu tiên được Marco Dorigo giới thiệu trong luận văn của mình
vào năm 1992, và được gọi là Hệ thống kiến (Ant System, hay AS). AS là kết quả
của việc nghiên cứu trên hướng tiếp cận trí tuệ máy tính nhằm tối ưu tổ hợp mà
Dorigo được hướng dẫn ở Politecnico di milano với sự hợp tác của Alberto Colorni
và Vittorio Maniezzo. AS ban đầu được áp dụng cho bài toán người du lịch (TSP)
và QAP
Cũng vào năm 1992, tại hội nghị sự sống nhân tạo lần đầu tiên ở châu Âu , Dorigo
và các cộng sự đã công bố bài: Sự tối ưu được phân bố bởi đàn kiến. Tiếp theo tại
hội nghị quốc tế thứ hai về giải quyết các vấn đề song song trong tự nhiên ở Hà Lan
(1992), ông và các cộng sự đã công bố bài: nghiên cứu về các đặc tính của một giải
thuật kiến.
Kể từ năm 1995 Dorigo, Gambardella và Stützle đã phát triển các sơ đồ AS khác
nhau. Dorigo và Gambardella đã đề xuất Hệ thống bầy kiến (Ant Colony System,
hay ACS) trong khi Stützle and Hoos đề xuất MAX-MIN Ant System (MMAS). Tất
cả đều áp dụng cho bài toán người du lịch đối xứng hay không đối xứng và cho kết

của kiến thật để giải quyết các bài toán tối ưu rời rạc.
1.1.1 Mô hình hóa hành vi của kiến trong thực tế
Bầy kiến, hay nói chính xác hơn là xã hội của loài kiến, là một loạt các hệ thống
phân tán thể hiện một hình thái cấu trúc tổ chức xã hội rất cao mặc dù mỗi con kiến
chỉ là một sinh vật nhỏ bé và đơn giản. Chính nhờ hệ thống tổ chức như vậy nên
bầy kiến có thể thực hiện được nhiều công việc phức tạp mà một cá thể bình thường
không thể làm được. Các nghiên cứu hiện nay về thuật toán mô phỏng mô hình kiến
đều dựa vào sự quan sát các đàn kiến trên thực tế và người ta đã sử dụng các kết quả
này để thiết kế các thuật toán cho một số bài toán tối ưu.
Ý tưởng chính của các thuật toán này đều nằm ở các cơ chế tự tổ chức( self-
organizing ) cho phép những hành vi của con kiến thật được mô phỏng chính xác
trên các con kiến nhân tạo nhằm xây dựng và đưa ra lời giải tối ưu cho các bài toán
tính toán. Trong các nghiên cứu hiện nay thì có một vài hành vi của bầy kiến đã
được sử dụng để làm ý tưởng cốt lõi cho một số thuật toán, ví dụ như tìm thức ăn,
phân chia lao động, phân loại trứng hay hợp tác vận chuyển. Trong tất cả các ví dụ
trên thì các con kiến đều điều hướng hoạt động của mình qua mùi, một cơ chế giao
tiếp gián tiếp thông qua việc tác động lên môi trường. Ví dụ một con kiến đi tìm
thức ăn sẽ tiết ra hóa chất trên mặt đất để nâng cao xác suất các con kiến khác cũng
sẽ đi theo lối đó. Các nhà sinh vật học đã chỉ ra rằng các loài côn trùng với hình thái
tổ chức xã hội cao cũng chỉ sử dụng các mô hình giao tiếp đơn giản là mùi mà thôi.
Và đó cũng chính là ý tưởng cơ bản đằng sau mọi thuật toán mô phỏng đàn kiến, sử
dụng mùi nhân tạo nhằm điều hướng cho các con kiến nhân tạo thực hiện hành vi
giống với kiến thật.
Các giác quan để cảm nhận hình ảnh của rất nhiều loài kiến mới chỉ ở những bước
đầu phát triển và thậm chí là có những loài kiến có thể nói là mù hoàn toàn. Trên
thực tế, điểm cốt lõi trong các nghiên cứu ban đầu về hành vi của kiến đó là hầu hết
sự giao tiếp giữa các cá thể với nhau hay giữa các cá thể với môi trường thì đều dựa
…………………………………………………………………………………………………………………
Sinh viên thực hiện: Trần Đình Quang-20093577-Lớp Công nghệ thông tin 1- K54 Trang 12
trên một hóa chất được tiết ra từ kiến. Các hóa chất này được gọi chung là mùi

dù ban đầu các con kiến được tự do chọn ngẫu nhiên hướng đi thì cuối cùng tất cả
các con kiến đều chỉ đi qua duy nhất 1 nhánh mà thôi. Khi thử nghiệm bắt đầu thì
không có vết mùi nào trên cả hai nhánh. Bởi vậy các con kiến sẽ không có ưu tiên
nào khi chọn đường và vì thế xác suất chọn 1 trong 2 nhánh là như nhau. Điều này
được lý giải là do dao động ngẫu nhiên của xác suất (gần với 50% chứ không hẳn là
50%) nên sẽ xảy ra trường hợp 1 nhánh có nhiều kiến đi qua hơn (có khi chỉ nhiều
hơn một vài con). Ta biết rằng kiến tiết mùi trên đường đi nên khi có sự chênh lệch
về số lượng thì sẽ dẫn đến một nhánh có nồng độ mùi lớn hơn. Nồng độ mùi lớn
…………………………………………………………………………………………………………………
Sinh viên thực hiện: Trần Đình Quang-20093577-Lớp Công nghệ thông tin 1- K54 Trang 13
hơn cũng có nghĩa là xác suất kiến chọn nhánh đó cũng sẽ lớn hơn. Và cứ như vậy
sẽ dẫn tới việc cuối cùng tất cả các con kiến đều chọn chung 1 nhánh để di chuyển.
Có thể thấy đây chính là ví dụ của giao tiếp qua mùi, các con kiến tự điều hướng
hoạt động của mình nhờ tận dụng hình thức giao tiếp gián tiếp thông qua việc tác
động lên môi trường ( tiết ra hóa chất lên đường đi).

Hình 1. Hai nhánh cầu có cùng độ dài
Hình 2. Kết quả thí nghiệm với 2 nhánh có cùng độ dài

Trong thí nghiệm số 2, tỉ lệ độ dài giữa 2 nhánh được đặt , tức là 1 nhánh sẽ có độ
dài gấp 2 lần độ dài nhánh còn lại ( Hình 3). Ở lần thí nghiệm này thì ở hầu hết các
lần thử, sau 1 khoảng thời gian thì tất cả các con kiến đều chọn di chuyển trên
…………………………………………………………………………………………………………………
Sinh viên thực hiện: Trần Đình Quang-20093577-Lớp Công nghệ thông tin 1- K54 Trang 14
nhánh ngắn hơn. Cũng giống như trong thí nghiệm đầu tiên, các con kiến đều rời tổ
đi tới ngã ba đường và tại đây chúng sẽ phải chọn đi theo 1 trong 2 nhánh. Bởi vì
ban đầu thì 2 nhánh đều giống nhau nên kiến sẽ chọn ngẫu nhiên 1 trong 2 nhánh.
Vì vậy mà chúng ta sẽ dự đoán rằng trung bình thì một nửa số kiến sẽ chọn nhánh
ngắn và 1 nửa còn lại sẽ chọn nhánh dài. Thực tế lại không phải như vậy, những con
kiến chọn nhánh ngắn sẽ tới đích (nguồn thức ăn) trước tiên và sẽ ngay lập tức lên


Algorithm : Function roulette_Wheel(
…………………………………………………………………………………………………………………
Sinh viên thực hiện: Trần Đình Quang-20093577-Lớp Công nghệ thông tin 1- K54 Trang 16
Input: , lần lượt là trạng thái hiện tại,tập các trạng thái có thể đến từ trạng thái hiện tại, tập
xác suất của các trạng thái trong
Output: Trạng thái chọn để đi tiếp
{
}
1.1.3 Thuật toán bầy kiến tối ưu( Ant colony Optimization –ACO)
Thuật toán ACO là một thuật toán tìm kiếm ngẫu nhiên dựa trên xác suất. Trọng
tâm của thuật toán là sử dụng mô hình vết mùi dựa trên mô hình vết mùi của kiến
trong tự nhiên. Dưới đây là mô hình thuật toán ACO để giải bài toán tối ưu rời rạc,
được định nghĩa như sau.
Một bài toán tối ưu rời rạc trong đó:
- là không gian tìm kiếm (lời giải) có thể có của bài toán
- là một tập hợp các ràng buộc giữa các biến
- là hàm mục tiêu cần tối ưu , cần tìm min của
Không gian tìm kiếm được định nghĩa như sau: Mỗi lời giải trong là một tập gồm
biến rời rạc với giá trị và thỏa mãn tập ràng buộc . Lời giải được gọi là lời giải tối
ưu nếu Tập các lời giải tối ưu gọi là . Ở đây, cần tìm một lời giải tối ưu
Mô hình bầy kiến tối ưu sẽ được áp dụng để giải bài toán trên. Mỗi biến sẽ nhận
một giá trị trong miền giá trị của biến đó là và là một thành phần của lời giải, ký
hiệu là . Khi đó mô hình bầy kiến sẽ áp dụng vết mùi cho bài toán bằng cách gán
vết mùi đối với mỗi lời giải thành phần , có nghĩa là mỗi lời giải thành phần sẽ có
một vết mùi là để tính xác suất trong lựa chọn. Tập tất cả các giá trị có thể của các
lời giải thành phần ký hiệu là . Tập tất cả các vết mùi cho tất cả các giá trị có thể
của các biến được ký hiệu là T.
Sơ đồ chung của ACO cho bài toán trên bao gồm các thủ tục sau:
1)Khởi tạo thông tin vết mùi

rằng việc có sử dụng thủ tục này có thể tối ưu thuật toán rất tốt.
4) Cập nhật vết mùi
ApplyPheromoneUpdate(T , ,): Thực hiện cập nhật thông tin vết mùi, thủ tục này sẽ
tăng giá trị vết mùi trên các lời giải thành phần của các lời giải trong tập lời giải sẽ
được cập nhật vết mùi . Thông thường các thuật toán đều áp dụng cập nhật thông tin
vết mùi như sau:
(1-2)
Với và ,là hệ số bay hơi vết mùi
: Tập các lời giải tìm được của thuật toán ( iter- iteraction). Ban đầu là rỗng, cứ mỗi
lần tìm được một lời giải thì sẽ bổ sung lời giải tìm được.
: là tập tất cả các lời giải sẽ sử dụng cập nhật thông tin mùi ( upd – update)
Trong công thức (1-2), chỉ mang tính chất để nghiên cứu toán học cho việc cập
nhật thông tin vết mùi, thường được chọn là một hằng số. Ví dụ, nếu thì
là một hàm thỏa mãn , là tập các lời giải khả thi của bài toán . Nghĩa là vết mùi
sẽ cộng thêm nhiều hơn cho lời giải có giá trị hàm mục tiêu nhỏ hơn.
Ở công thức (1) thì bay hơi vết mùi là cần thiết để giảm bớt khả năng thuật toán sẽ
hội tụ quá nhanh và dễ rơi vào cực trị địa phương, cần lựa chọn giá trị cho tham số
phù hợp để sự bay hơi vết mùi là hiệu quả.
Các ký hiệu:
(best solution): Lời giải tốt nhất
…………………………………………………………………………………………………………………
Sinh viên thực hiện: Trần Đình Quang-20093577-Lớp Công nghệ thông tin 1- K54 Trang 18
(number ants): Số lần thực hiện xây dựng lời giải với một tập vết mùi T, hay là số
kiến sẽ thực hiện xây dựng lời giải.
Algorithm: ACO – Ant colony optimization
Input: của bài toán tối ưu
Output: Lời giải tốt nhất tìm được
// Khởi tạo vết mùi
InitializePheromoneValues(T )
// Lời giải tốt nhất ban đầu

trên. Việc cập nhật thông tin mùi có thể được thực hiện sau khi ta thu được một
thành phần của lời giải hoặc là thu được cả một lời giải, với mỗi trường hợp đó thì
ta sẽ có một biến thể của ACO áp dụng cho bài toán mà ta cần giải quyết. Một biến
…………………………………………………………………………………………………………………
Sinh viên thực hiện: Trần Đình Quang-20093577-Lớp Công nghệ thông tin 1- K54 Trang 19
thể điển hình của giải thuật ACO ở trên là thực hiện cập nhật thông tin mùi cho tất
cả lời giải thu được sau một lần thực hiện, nghĩa là:

Việc thực hiện cập nhật thông tin mùi theo cách này còn gọi là cập nhật mùi AS
( Ant System)
Một biến thể điển hình khác của giải thuật ACO nêu trên là việc cập nhật thông tin
mùi chỉ được thực hiện với lời giải tốt nhất tìm được trong toàn bộ bước lặp

Việc thực hiện cập nhật thông tin theo cách này còn được gọi là cập nhật mùi IB
(iteraction best). Có thể thấy là việc cập nhật thông tin mùi theo cách này chỉ được
thực hiện với các thành phần của lời giải tốt nhất tìm được, như vậy trong biến thể
này của ACO thì thuật toán sẽ hội tụ rất nhanh và dẫn đến lời giải rơi vào cực trị địa
phương và không có khả năng cải thiện ở các lần tiếp theo, đây là một nhược điểm
lớn. Để khắc phục điều này, ta có thể sử dụng cách cập nhật thông tin mùi cho tất cả
các lời giải tốt nhất tìm được trong các bước lặp, cứ sau một bước lặp nếu được
cải thiện thì
Việc cập nhật theo cách này còn được gọi là cập nhật mùi BS ( Best so far
solution)
Trong thực tế, giải thuật ACO sử dụng cách cập nhật thông tin mùi IB hoặc BS
cùng với các cơ chế để tránh giải thuật hội tụ sớm đạt kết quả tốt hơn so với các giải
thuật sử dụng cách cập nhật thông tin mùi AS. Ví dụ như hệ thống đàn kiến ACS
( Ant Colony System) và hệ thống MMAS ( Max-Min Ant System) là một trong
những ví dụ thành công nhất của việc sử dụng các biến thể trên trong thực tế. Sau
đây sẽ giới thiệu một số biến thể thông dụng của ACO.
1) Giải thuật Ant System ( AS):

pheromone, lượng pheromone này là hàm của chất lượng lời giải mà con
kiến xây dựng.

, .
k
rs rs rs rs k
a S
τ τ τ
¬ +∆ ∀ ∈

Trong đó:

( )
( ) .
k
rs k
f C S
τ
∆ =

Ban đầu AS không sử dụng daemon action, tuy nhiên sẽ càng tốt hơn nếu thêm
vào đó một thủ tục tìm kiếm cục bộ để làm tăng chất lượng của lời giải. Còn
phương trình để xác định nút tiếp theo trong quá trình xây dựng lời giải của con
kiến như sau.

(1-3)
Tóm tắt về thuật toán này như sau:
Procedure new_ant (ant_id)
k = ant_id ; r = generate_initial_state ;
k

∈
=
∑
next_state = apply_ant_decision_policy (P ,
( )
k
N r
)
r = next_state ;
,
k k
S S r=< >

k k
L L r= ∪
…………………………………………………………………………………………………………………
Sinh viên thực hiện: Trần Đình Quang-20093577-Lớp Công nghệ thông tin 1- K54 Trang 21
end while
{ the pheromone_evaporation ( ) procedure triggers and
evaporates pheromone in every edge
( )
: 1 .
rs rs rs
a p
τ τ
= −
}
for each edge
rs k
a S∈

) :
(1-5)

 Việc cập nhật vết mùi thực hiện theo BS nghĩa là thực hiện việc cập nhật
pheromone chỉ duy nhất với lời giải tốt nhất . Cập nhật theo công thức
như sau: Sau mỗi bước xây dựng lời giải, sau khi mỗi thành phần lời giải được xác
định thì thực hiện cập nhật vết mùi cho thành phần đó.

0
(1 ). . .
rs rs
τ ϕ τ ϕ τ
¬ − +
Trong đó φ là một tham số để giảm pheromone thứ hai sau ρ. Còn được chọn là
một tham số rất bé (như là ngưỡng dưới của pheromone).
…………………………………………………………………………………………………………………
Sinh viên thực hiện: Trần Đình Quang-20093577-Lớp Công nghệ thông tin 1- K54 Trang 22
Tóm tắt về thuật toán này như sau:
Procedure new_ant (ant_id)
k = ant_id ; r = generate_initial_state ;
k
S r=

k
L r
=
while (current-state

( )
k
k
rs
rs
ru
u N r
b
p
b
∈
=
∑
next_state = apply_ant_decision_policy (P ,
( )
k
N r
)
end if
r = next_state ;
,
k k
S S r
=< >

0:
(1 ). .
rs rs
τ ϕ τ ϕ τ
= − +

−
,
global best
S
−
))

global best
S
−
=
current best
S
−
end if
for each edge
rs
a
∈

global best
S
−
do
{ the pheromone_evaporation ( ) procedure triggers and
evaporates pheromone in every edge
( )
: 1 .
rs rs rs
a p

cuối cùng.

…………………………………………………………………………………………………………………
Sinh viên thực hiện: Trần Đình Quang-20093577-Lớp Công nghệ thông tin 1- K54 Trang 24

Trong đó là lời giải tối ưu, bởi vì lời giải tối ưu không biết trước nên thông
thường được thay thế bởi trong tính toán.
Cách chọn cận dưới , thông thường người ta chọn để thỏa mãn theo tỷ lệ
giữa cận trên và cận dưới /= 2n.
Do đó tính = / 2n. Tỉ lệ này phải chọn không nên quá cao, bởi vì khi đó xác
suất để chọn đường đi có mức độ Pheromone thấp là quá nhỏ. Mặt khác
nếu chọn tỉ lệ này quá lớn thì xác suất chọn đường đi có Pheromone cao là
gần với xác suất chọn đường đi có mức độ Pheromone thấp.
 Khi khởi tạo thông tin pheromone cho các thành phần thì tất cả nhận
giá trị lớn nhất có thể của Pheromone là nhằm tăng cường việc khai phá
không gian tìm kiếm. Một chú ý trong hệ thống MMAS là khi xảy ra hội
tụ cục bộ thì có cơ chế khởi tạo lại thông tin pheromone cho các nút và
giá trị để khởi tạo lại là.
Hàm cập nhật Daemon action của thuật toán MMAS như sau:
Procedure daemon_actions
for each
k
S
do local_search (
k
S
)

current best
S

−
,
current best
S
−
)
for each edge
rs
a
∈

best
S
do

( )
( )
rs rs best
f C S
τ τ
= +
if (
min min
)
rs rs
τ τ τ τ
< =
end for
if (stagnation_condition)
for each edge