..

Hoàng sơn

bộ giáo dục và đào tạo
trường đại học bách khoa hà nội
---------------------------------------

luận văn thạc sĩ khoa học

công nghệ thông tin

ngành : công nghệ thông tin

GII THUT H KIN MAX MIN TRN
GII BI TON
P-MEDIAN Cể HN CH KH NNG

Hoàng sơn

2006 – 2008
Hµ Néi
2009

Hµ Néi 2009


Hoàng sơn

bộ giáo dục và đào tạo
trường đại học bách khoa hà nội

---------------------------------------

Hoàng sơn

công nghệ thông tin

GII THUT H KIN MAX MIN TRƠN
GIẢI BÀI TỐN P-MEDIAN CĨ HẠN CHẾ KHẢ NNG
luận văn thạc sĩ khoa học
ngành : công nghệ thông tin
NGƯỜI HƯỚNG DẪN KHOA HỌC:
PGS.TS. NGUYỄN ĐỨC NGHĨA

2006 – 2008
Hµ Néi
2009

Hµ Néi 2009


Lời cảm ơn
Với tất cả lịng kính trọng và biết ơn sâu sắc em xin gửi lời cảm ơn
chân thành tới thầy giáo PGS.TS. Nguyễn Đức Nghĩa người đã tận tình
hướng dẫn em trong suốt q trình hồn thành luận văn.
Xin chân thành cảm ơn.


Luận văn Cao học

2


CH 2006-2008

MỤC LỤC
Danh mục các từ viết tắt và thuật ngữ ...........................................................4
Danh mục hình .................................................................................................5
LỜI NĨI ĐẦU ..................................................................................................6
U

Chương 0...........................................................................................................7
ĐẶT VẤN ĐỀ ...................................................................................................7
Chương 1 .........................................................................................................11
LƯỢC SỬ PHÁT TRIỂN CỦA CÁC THUẬT TOÁN ACO ....................11
1.1/ Nguồn gốc sinh học của các thuật tốn kiến ....................................... 11
1.2/ Truyền thơng gián tiếp-stigmergy ....................................................... 14
1.3/ Quá trình phát triển của các thuật toán ACO ...................................... 14
1.3.1/ Hệ kiến (AS) và bài toán TSP....................................................... 15
1.3.2/ Hệ đàn kiến (ACS)........................................................................ 18
1.3.2/ Thuật toán hệ kiến Max-Min.......................................................... 20
Chương 2 .........................................................................................................22
PHƯƠNG PHÁP TỐI ƯU ĐÀN KIẾN ACO ..............................................22
2.1/ Một số heuristic ACO .......................................................................... 22
2.2/ Meta-heuristic tối ưu hoá đàn kiến (ACO metaheuristic) ................... 23
2.2.1/ Bài toán tổng quát ........................................................................ 23
2.2.2/ Thuật toán ACO tổng quát............................................................ 24
2.2.3/ Xây dựng lời giải .......................................................................... 27
2.2.3/ Cập nhật mùi ................................................................................. 27
2.3/ Đặc tính hội tụ của vết mùi ................................................................. 29
2.4/ Các thuật tốn trong ACOτmin ............................................................. 31
Chương 3 .........................................................................................................33

THUẬT TỐN HỆ KIẾN MAX-MIN ...........................................................33
3.1/ Thuật toán hệ kiến Max-Min ................................................................ 33
3.1.1/ Giới thiệu hệ kiến Max-Min........................................................... 33
3.1.2/ Cập nhật vết mùi ........................................................................... 33
3.1.3/ Giới hạn của vết mùi ..................................................................... 35
3.1.4/ Khởi tạo vết mùi............................................................................ 36
3.1.5/ Lựa chọn phương thức cập nhật mùi ............................................ 36
3.1.6/ Một số nguyên lý ứng dụng .......................................................... 36
3.1.7/ Hệ kiến MAX-MIN trơn................................................................. 42
3.2/ Các bước để áp dụng giải bài toán cụ thể............................................ 43
3.3/ Các dạng bài toán áp dụng thuật toán ACO ........................................ 44
Chương 4.........................................................................................................47
Giải thuật hệ kiến Max-min trơn giải bài tốn p-median có hạn chế khả năng


Luận văn Cao học

3

CH 2006-2008

THUẬT TOÁN MAX-MIN TRƠN GIẢI BÀI TỐN P-MEDIAN CĨ
HẠN CHẾ KHẢ NĂNG ................................................................................47
4.1/ Bài tốn p-median có hạn chế khả năng .............................................. 47
4.1.1/ Bài tốn p-median khơng hạn chế khả năng ................................. 47
4.1.2/ Bài tốn p-median có hạn chế khả năng ....................................... 48
4.1.3/ Mơ hình tốn học .......................................................................... 49
4.2/ Mơ tả thuật tốn Max-Min trơn giải bài toán CPMP ........................... 51
4.3/ Bàn về cài đặt thuật toán MMAS trơn ................................................ 52
4.3.1/ Khởi tạo các tham số:.................................................................... 52

4.3.2/ Điều kiện dừng của thuật toán ...................................................... 53
4.3.3/ Xây dựng lời giải .......................................................................... 53
4.3.4/ Cập nhật thông tin pheromone...................................................... 60
4.3.5/ Khởi tạo lại thông tin pheromone ................................................. 62
4.4/ Cải tiến cho thuật toán......................................................................... 62
4.4.1/ Location-Allocation Heuristic (LAH) .......................................... 62
4.4.2/ Interchange-Transfer Heuristic (ITH)........................................... 63
Chương 5.........................................................................................................65
CÀI ĐẶT THUẬT TOÁN VÀ THỬ NGHIỆM ..........................................65
5.1/ Cài đặt thuật tốn, xây dựng chương trình.......................................... 65
5.1.1/ Thiết kế chức năng........................................................................ 65
5.1.2/ Thiết kế Module ............................................................................ 66
5.1.2/ Thiết kế dữ liệu ............................................................................. 69
5.2/ Hướng dẫn sử dụng ............................................................................. 70
5.2.1/ Yêu cầu hệ thống........................................................................... 70
5.2.2/ Sử dụng chương trình.................................................................... 70
5.3/ Thử nghiệm dữ liệu bài tốn ............................................................... 75
5.3.1/ Nguồn gốc và cấu trúc dữ liệu ...................................................... 75
5.4/ Kết quả thực nghiệm ........................................................................... 77
5.4.1/ Chọn các tham số cho thuật toán .................................................. 77
5.4.2/ Các kết quả thực hiện thuật tốn................................................... 86
5.5/ Phân tích đánh giá kết quả thực nghiệm ............................................. 99
KẾT LUẬN ...................................................................................................101
TÀI LIỆU THAM KHẢO ...........................................................................103

Giải thuật hệ kiến Max-min trơn giải bài tốn p-median có hạn chế khả năng


Luận văn Cao học


4

CH 2006-2008

Danh mục các từ viết tắt và thuật ngữ
1. CPMP: Capacitated P-Median Problem. Bài toán p-median có hạn chế khả
năng. Ngồi ra một tên gọi cũng hay gặp là bài tốn k-median có hạn chế khả
năng.
2. ACO: Ant Colony Optimization. Gọi là thuật toán đàn kiến.
3. ACA: Ant Colony Algorithm. Là tên gọi khác của giải thuật đàn kiến.
4. MMAS: Max-Min Ant System. Là một thuật toán thuộc lớp các thuật toán đàn
kiến.
5. GA: Genetic Algorithm. Gọi là thuật toán di truyền.
6. SA: Simulated Annealing. Gọi là thuật tốn luyện kim.
7. TS: Tabu-Search: Giải thuật tìm kiếm Tabu.
8. Pheromone: Thơng tin mùi. Là một loại hóa chất và là phương tiện để các con
kiến trong đàn trao đổi thông tin với nhau.
9. Cluster: Gọi là vùng. Bao gồm một tâm phục vụ và các khách hàng được phục
vụ bởi tâm phục vụ đó.
10. AP: Bài tốn gán.
11. GAP: Generalize Assignment Problem. Gọi là bài toán gán tổng quát.
12. TSP: Bài toán người du lịch.

Giải thuật hệ kiến Max-min trơn giải bài tốn p-median có hạn chế khả năng


Luận văn Cao học

5


CH 2006-2008

Danh mục hình
Hình 1 – Minh họa đàn kiến tự nhiên .........................................................................8
Hình 2 – Cách tìm đường đi của kiến .......................................................................12
Hình 3 – Mơ hình thí nghiệm cầu đơi 2 nhánh dài bằng nhau..................................13
Hình 4 – Thí nghiệm cầu đơi....................................................................................13
Hình 5 – Sơ đồ thuật tốn ACO giải bài tốn CPMP................................................51
Hình 6 – Các Class trong chương trình.....................................................................66
Hình 7 – Màn hình chính ..........................................................................................70
Hình 8 – Đọc dữ liệu .................................................................................................71
Hình 9 – Chi tiết bài tốn ..........................................................................................72
Hình 10 – Thiết lập tham số thuật tốn.....................................................................72
Hình 11 – Thực hiện thuật tốn.................................................................................73
Hình 12 – Chi tiết lời giải..........................................................................................74
Hình 13 – Tạo mới dữ liệu ........................................................................................74
Hình 14a – Đánh giá tham số ρ.................................................................................81
Hình 14b – Đánh giá tham số ρ.................................................................................82
Hình 14c – Đánh giá tham số ρ.................................................................................82
Hình 15a – Đánh giá tham số cặp tham số (α, β)......................................................84
Hình 15b – Đánh giá tham số cặp tham số (α, β)......................................................85
Hình 15c – Đánh giá tham số cặp tham số (α, β)......................................................85
Hình 16 – Biểu đồ kết quả trên bộ dữ liệu OSMAN.................................................90
Hình 17 – Biểu đồ so sánh độ dao động kết quả trên bộ dữ liệu OSMAN...............91
Hình 18 – Biểu đồ so sánh kết quả trên bộ dữ liệu OSMAN....................................92
Hình 19 – Biểu đồ so sánh thời gian thực hiện trên bộ dữ liệu OSMAN .................93
Hình 20 – Biểu đồ kết quả trên bộ dữ liệu Lorena....................................................95
Hình 21 – Biểu đồ so sánh độ dao động kết quả trên bộ dữ liệu Lorena..................96
Hình 22 – Biểu đồ so sánh kết quả trên bộ dữ liệu Lorena.......................................97
Hình 23 – Biểu đồ so sánh thời gian thực hiện trên bộ dữ liệu Lorena ....................98

Hình 24 – Biểu đồ về thời gian thực hiện thuật toán MMAS ...................................99

Giải thuật hệ kiến Max-min trơn giải bài tốn p-median có hạn chế khả năng


Luận văn Cao học

6

CH 2006-2008

LỜI NÓI ĐẦU
Trong cuộc sống, việc đạt lợi nhuận cao hay thấp trong kinh doanh buôn bán, cung
cấp dịch vụ phụ thuộc rất nhiều yếu tố. Trong đó, có một yếu tố quan trọng đầu tiên,
đóng góp một phần rất lớn đó là xác định được địa điểm đặt dịch vụ thuận lợi – nơi
cung cấp dịch vụ. Có rất nhiều tiêu chí đặt ra khi chọn địa điểm: thuận tiện về giao
thông, là nơi tập trung đông dân cư, ... để làm sao thu được lợi nhuận cao nhất. Đặc
biệt, đối với các trường hợp khẩn cấp như cứu thương, cứu hỏa thì yêu cầu về
khoảng cách nhỏ nhất là vơ cùng quan trọng, có thể nói là quan trọng nhất trong các
yếu tố. Bài toán đặt ra là: đặt các trạm dịch vụ ở đâu để thời gian di chuyển bệnh
nhân từ nơi xa bệnh viện nhất (hoặc ngược lại, từ các trạm dịch vụ đến nơi bệnh
nhân xa nhất) là nhỏ nhất có thể. Còn với các dịch vụ phổ biến như trạm xăng,
thùng phiếu, bốt điện thoại, ... thì yêu cầu lại là tổng chi phí từ các khách hàng (hay
người có nhu cầu) đến địa điểm phục vụ gần khách hàng nhất là nhỏ nhất, bài toán
như trên là một ứng dụng thực tế của bài toán p-median được phát biểu trong lý
thuyết.
Với nhiều ứng dụng trong thực tế, bài toán p-median có hạn chế khả năng là bài
tốn thuộc lớp NP-Khó nghĩa là khơng có thuật tốn thời gian tính đa thức để giải.
Trong phạm vi của luận văn này tác giả bày một phương pháp được phát triển dựa
trên sơ đồ thuật toán bày kiến để giải quyết một cách có hiệu quả bài tốn p-median

có hạn chế khả năng. Luận văn sẽ bắt đầu từ việc giới thiệu lược sử phát triển của
thuật toán đàn kiến, tiếp đến trình bày sơ đồ tổng qt của thuật tốn bày kiến và
các cải tiến dựa trên nền tảng tư tưởng thuật toán này nhằm đưa ra những lời giải tốt
hơn. Trong các cải tiến của họ các thuật toán kiến, luận văn lựa chọn thuật toán
Max-Min (MMAS) và hiệu chỉnh của nó là Max-Min trơn là thuật tốn chính được
ứng dụng để giải bài tốn p-median có hạn chế khả năng.

Giải thuật hệ kiến Max-min trơn giải bài toán p-median có hạn chế khả năng


Luận văn Cao học

7

CH 2006-2008

Chương 0

ĐẶT VẤN ĐỀ
Giới thiệu đề tài
Trong vịng 10 năm gần đây, có nhiều bài tốn tối ưu tổ hợp được giải quyết
bằng họ các thuật tốn kiến (Ant Algorithm). Thuật tốn kiến mơ phỏng hành vi của
đàn kiến trong tự nhiên nhằm tìm kiếm đường đi ngắn nhất giữa tổ kiến và nguồn
thức ăn dựa trên mật độ mùi(Pheromone) mà các con kiến để lại trên đường đi. Hiệu
quả của thuật toán kiến đã được thể hiện khi so sánh với các thuật toán nổi tiếng
khác như GA, SA, Tabu-Search 1 . Người ta áp dụng rất thành cơng các thuật tốn
kiến trong các bài toán tối ưu như Bài toán người đưa thư, bài tốn gán, bài tốn tơ
mầu đồ thị, bài tốn lập lịch...
Và trong nội dung của đề tài này, tác giả xin được trình bày về thuật tốn đàn
kiến áp dụng giải bài tốn p-median có hạn chế khả năng.


Tư tưởng của thuật toán đàn kiến
Được đưa ra lần đầu tiên bởi Macro Dorigo năm 1992, là kết quả của việc
nghiên cứu về trí tuệ tính tốn (computational intelligence) áp dụng cho các bài toán
tổ hợp tối ưu (combinatorial optimization).
Đầu tiên thuật toán đàn kiến được áp dụng để giải bài toán người du lịch
(TSP). Sau này thuật toán được mở rộng và phát triển để giải nhiều bài toán tối ưu
tổ hợp khó hơn.
Thuật tốn được đưa ra và phát triển dựa trên các nghiên cứu, thí nghiệm về
q trình kiếm thức ăn của lồi kiến. Đó là khi mà tìm thấy nguồn thức ăn, ban đầu
đàn kiến sẽ tìm ra nhiều con đường để đi tới nguồn thức ăn từ tổ của mình. Tuy
nhiên sau một thời gian thơng qua trao đổi thơng tin đàn kiến sẽ tìm ra con đường
ngắn nhất và toàn bộ kiến trong đàn sẽ theo con đường này để đi từ tổ tới nguồn
thức ăn và ngược lại. Hình vẽ minh họa như sau:

1

Xem danh mục từ viết tắt của luận văn

Giải thuật hệ kiến Max-min trơn giải bài tốn p-median có hạn chế khả năng


8

Luận văn Cao học

CH 2006-2008

Hình 1 – Minh họa đàn kiến tự nhiên


Theo minh họa trên thấy rằng: Ở H.1 sau khi tìm thấy nguồn thức ăn và
khơng có chướng ngại vật trên đường đi thì đàn kiến đi theo con đường ngắn nhất
thẳng tới nguồn thức ăn. Ở H.2 khi bắt đầu đặt chướng ngại vật vào đường đi của
đàn kiến. Trên hình H.3 đàn kiến chia làm hai phần đi theo hai hướng khác nhau
vượt qua chướng ngại vật tới nguồn thức ăn. Sau một thời gian thông qua tương tác
và trao đổi thông tin giữa các con kiến trong đàn, cả đàn kiến thực hiện việc di
chuyển theo con đường ngắn hơn từ tổ tới nguồn thức ăn (H.4).
Việc cả đàn kiến sau một thời gian sẽ đi theo đường nhắn nhất từ tổ tới
nguồn thức ăn là cơ sở xuất phát cho các nghiên cứu về thuật tốn này, theo đó
thuật tốn dựa vào hình thức giao tiếp giữa các con kiến đó là để lại vệt mùi trên
đường đi.
Trên đây là tư tưởng hình thành nên họ các thuật tốn kiến sau này sẽ được
trình bày ở các phần tiếp theo của luận văn.

Nhiệm vụ của đề tài luận văn
™ Tên đề tài: “ Giải thuật hệ kiến Max-Min trơn giải bài tốn p-meidan có
hạn chế khả năng”.
™ Nhiệm vụ: Luận văn tập trung khảo cứu các thuật tốn tối ưu hóa sử dụng
phương pháp mô phỏng hành vi đàn kiến trong tự nhiên, nghiên cứu giải
thuật Max-Min trơn (Smooth MMAS) áp dụng giải bài tốn p-median có hạn
chế khả năng.
Giải thuật hệ kiến Max-min trơn giải bài tốn p-median có hạn chế khả năng


Luận văn Cao học

9

CH 2006-2008


Nội dung được tóm lược lại như sau:
9 Khảo cứu về lược sử hình thành và phát triển các thuật toán đàn kiến
9 Khảo cứu về các phương pháp tối ưu hóa đàn kiến ACO.
9 Nghiên cứu thuật tốn đàn kiến Max-Min.
9 Tìm hiểu bài tốn p-median có hạn chế khả năng.
9 Cài đặt giải thuật Max-Min trơn để giải bài tốn p-median có hạn chế
khả năng.
9 Xây dựng chương trình cài đặt.
9 Triển khai chương trình với hai bộ dữ liệu chuẩn của bài tốn pmedian đó là bộ dữ liệu OSMAN và bộ dữ liệu LORENA.
9 So sánh và đánh giá các kết quả đạt được.
9 Kết luận.

Phương pháp thực hiện
™ Luận văn áp dụng thống nhất phương pháp nghiên cứu trong cả quá trình
thực hiện. Tìm hiểu từ cơ sở nguồn gốc đến q trình phát triển và các cải
tiến của thuật tốn, dựa trên cơ sở đó đưa ra đề xuất phù hợp nhằm áp dụng
giải quyết bài toán cụ thể.
™ Luận văn xuất phát từ tư tưởng của thuật toán kiến, và khảo cứu về các
nghiên cứu khoa học về đàn kiến, các thuật tốn kiến để từ đó đưa ra phương
pháp giải quyết vấn đề áp dụng vào bài toán p-median có hạn chế khả năng.

Giới hạn vấn đề
Trong các thuật tốn tối ưu hóa đàn kiến (ACO) sẽ được tác giả trình bày ở
các phần tiếp theo, hệ kiến Max-Min (MMAS) tỏ ra đơn giản, thông dụng và được rất
nhiều người ưa dùng so với các thuật toán kiến trước đó như hệ kiến (Ant SystemAS), hệ đàn kiến (Ant Conoly System-ACS). Hệ kiến Max-Min là thuật toán đầu
tiên đề xuất cập nhật mùi theo tư tưởng giới hạn vết mùi Max-Min.
Luận văn trình bày khảo cứu về các thuật toán ACO ở mức độ tổng quát, đặc
biệt tập trung trình bày chi tiết về quy tắc cập nhật mùi Max-Min. Trên cơ sở đó tác
giả đề xuất cách cập nhật mùi mới cho đàn kiến và lấy tên là thuật toán hệ kiến MaxMin trơn (Smooth Max-Min Ant System) đồng thời áp dụng thuật toán vào giải bài
toán p-median có hạn chế khả năng. Kết quả thực nghiệm cho thấy hệ kiến Max-Min

trơn tác giả cài đặt có ưu điểm tốt trong bài toán được xét.
Giải thuật hệ kiến Max-min trơn giải bài tốn p-median có hạn chế khả năng


Luận văn Cao học

10

CH 2006-2008

Bố cục và tổ chức luận văn
Các chương tiếp theo của luận văn có cấu trúc như sau:
¾ Chương 1 trình bày về lược sử phát triển của các thuật tốn đàn kiến
ACO (Ant colony optimization)
¾ Chương 2 trình bày về phương pháp tối ưu hóa đàn kiến ACO.
¾ Chương 3 trình bày về thuật tốn đàn kiến Max-Min (MMAS)
¾ Chương 4 trình bày việc dùng thuật toán đàn kiến Max-Min trơn để giải
bài toán p-median có hạn chế khả năng.
¾ Chương 5 trình bày về việc cài đặt chương trình và các kết quả thực
nghiệm đạt được.

Giải thuật hệ kiến Max-min trơn giải bài toán p-median có hạn chế khả năng


Luận văn Cao học

11

CH 2006-2008


Chương 1

LƯỢC SỬ PHÁT TRIỂN CỦA CÁC THUẬT
TOÁN ACO
Chương này tác giả muốn giới thiệu về lược sử hình thành và phát triển của
các thuật tốn ACO 2 , bắt đầu từ các thí nghiệm sinh học về cách chọn đường đi của
đàn kiến thực, đến việc hình thành tư tưởng thuật tốn từ các thí nghiệm đó, tiếp
đến là sự ra đời của các thuật toán hệ kiến, hệ đàn kiến, hệ kiến Max-Min…
Các thuật tốn kiến có được nhờ sự quan sát cách chọn đường đi của các con
kiến thực. Các con kiến là các côn trùng sống trong các bầy đàn và sống thành xã
hội, chúng xuất hiện trên trái đất cách đây đã hơn 100 triệu năm, số lượng của
chúng khoảng 10 6 con (xem [2]). Sự tổ chức bầy đàn của các con kiến trong xã hội
kiến có cấu trúc cao đã thu hút nhiều nghiên cứu sinh học.
Trong xã hội kiến, các con kiến thợ thường xuyên tìm kiếm thức ăn đem về
tổ và đặc biệt là làm thế nào các con kiến có thể tìm được đường đi ngắn nhất từ tổ
của chúng tới nguồn thức ăn?

1.1/ Nguồn gốc sinh học của các thuật tốn kiến
Trong q trình đi từ tổ đến nguồn thức ăn và ngược lại, các con kiến rải
xuống đất một hoá chất gọi là mùi (tên khoa học là pheromone) và tạo nên các vết
mùi (pheromone trail). Các con kiến ngửi thấy mùi và chúng có khuynh hướng
chọn theo xác suất, các đường đi được đánh dấu bởi sự tập trung mùi mạnh. Vết
mùi cho phép các con kiến tìm ra đường quay lại của chúng tới nguồn thức ăn hoặc
tổ, nó cũng có thể được sử dụng bởi các con kiến khác để tìm ra vị trí nguồn thức
ăn.
Thực nghiệm cho thấy rằng, cách thức theo vết mùi (pheromone trail
following behavior) này là một phương pháp luận hiệu quả để tìm ra đường đi ngắn
nhất.

2


Xem danh mục các từ viết tắt

Giải thuật hệ kiến Max-min trơn giải bài tốn p-median có hạn chế khả năng


12

Luận văn Cao học

CH 2006-2008

Hình 2 – Cách tìm đường đi của kiến

Các con kiến thường để lại mùi (một chất hóa học đặc biệt mà chúng có thể
ngửi được) trên đường đi. Bằng cách để lại mùi như vậy, chúng sẽ tạo ra các vết
mùi để lại trên đường đi từ tổ đến nguồn thức ăn và ngược lại. Trong thực tế, bằng
cách cảm nhận những vết mùi như vậy những con kiến khác có thể tìm đường tới
các nguồn thức ăn do những con kiến trước đã tìm ra. Đồng thời, chúng có thể dựa
vào đó để tìm được đường đi ngắn nhất từ tổ đến các nguồn thức ăn.
Nhằm nghiên cứu các cách tìm đường đi của các con kiến trong điều kiện
quan sát được. J.L.Deneubourg [11] và các đồng nghiệp đã làm một thí nghiệm sử
dụng một cây cầu đôi nối từ tổ đến nguồn thức ăn, hình 2. Tổ của một đàn kiến với
nguồn thức ăn được ngăn bởi một các cầu đôi mà hai nhánh của nó bằng nhau để
nghiên cứu sự lưu lại các vệt mùi và hành vi của chúng. Tiếp đó các con kiến được
thả và tự do đi lại giữa tổ và nguồn thức ăn và phần trăm số kiến chọn nhánh nào để
đi được quan sát theo thời gian. Kết quả là sau một giai đoạn ban đầu có sự do dự,
trong chốc lát các con kiến có khuynh hướng chọn và hội tụ về cùng một đường đi.
Trong thí nghiệm trên, ban đầu khơng có mùi trên 2 nhánh, nên các nhánh
được chọn có cùng một xác suất. Tuy nhiên, do sự thăng giáng tự nhiên, sau một

giai đoạn ban đầu, nhánh trên được chọn nhiều hơn nhánh dưới. Bởi vì các con kiến
rải mùi trong khi đi, số kiến lớn hơn ở nhánh trên thì lượng mùi mạnh hơn, do đó
kích thích nhiều con kiến chọn nó hơn.

Giải thuật hệ kiến Max-min trơn giải bài toán p-median có hạn chế khả năng


Luận văn Cao học

13

CH 2006-2008

Nhánh trên

Thức ăn

Tổ kiến

Nhánh dưới
Hình 3 – Mơ hình thí nghiệm cầu đơi 2 nhánh dài bằng nhau

Tiếp đó họ thay đổi thí nghiệm trên tới trường hợp mà trong đó các nhánh có
chiều dài khác và thu được kết quả là theo thời gian dần dần hầu hết con kiến đều đi
vào nhánh ngắn hơn.
Kết quả được giải thích như sau: Do kỹ thuật rải mùi như nhau, khi thực
nghiệm bắt đầu, hai nhánh cầu đều khơng có mùi, như vậy lúc đầu các con kiến
chọn một trong hai nhánh theo xác suất là như nhau tức là một nửa số con kiến sẽ
chọn nhánh ngắn và nửa còn lại sẽ chọn nhánh dài. Trong quá trình tìm kiếm thức
ăn và đưa về tổ, con kiến luôn để lại vệt mùi trên hai nhánh cầu. Do nhánh ngắn

hơn, thời gian con kiến đi sẽ ít hơn (đồng nghĩa với số lần các con kiến đi lại nhiều
hơn), lượng mùi trên nhánh này sẽ nhiều hơn, nên theo thời gian các con kiến sẽ
chọn nhánh ngắn hơn để đi do cường độ vệt mùi trên nhánh này cao hơn, minh hoạ
trong hình 3.

Hình 4 – Thí nghiệm cầu đôi.

(a) Các con kiến bắt đầu khám phá chiếc cầu.
(b) Hầu hết các con kiến chọn đường đi ngắn nhất.
Giải thuật hệ kiến Max-min trơn giải bài toán p-median có hạn chế khả năng


Luận văn Cao học

14

CH 2006-2008

Trong các thuật toán kiến, cây cầu đơi ở thí nghiệm của Deneubourg được
thay bằng một đồ thị cấu trúc và các vết mùi của con kiến là những vết mùi nhân
tạo. Đồng thời khi muốn giải quyết những bài toán phức tạp hơn những bài toán của
con kiến thực, người ta cung cấp thêm cho con kiến nhân tạo một số khả năng đặc
biệt như bộ nhớ và khả năng để lại một lượng mùi tỷ lệ với hiệu quả của lời giải tìm
được (một hành vi tương tự như hành vi của con kiến thực khi chúng mang thức ăn
quay về tổ để lại một lượng mùi tỷ lệ với lượng thức ăn kiếm được).
Mỗi con kiến đơn lẻ chỉ có một sự đóng góp rất nhỏ trong q trình tìm
đường đi. Mặc dù một con kiến đơn lẻ về nguyên tắc có khả năng xây dựng một lời
giải (Ví dụ: tìm ra một đường đi giữa tổ và nguồn thức ăn), nhưng cả đàn kiến mới
là đối tượng biểu diễn cách thức "tìm đường đi ngắn nhất". Cách thức này là một
thuộc tính nổi bật (emergent) của đàn kiến. Cũng cần chú ý là các con kiến có thể

thực hiện cách thức riêng biệt này bằng cách sử dụng một dạng truyền thông gián
tiếp-stigmergy bằng cách rải mùi.

1.2/ Truyền thông gián tiếp-stigmergy
Dạng truyền thơng stigmergy được đưa ra trong cơng trình của Grassé [09]
(Bellicositermes Natalensis và Cubitermes), stigmergy là "Mô phỏng các thợ
(workers-một đẳng cấp trong các đàn mối) bởi hiệu suất mà chúng đạt được".
Mặc dù Grassé giới thiệu thuật ngữ stigmergy để giải thích các hành vi của
xã hội đàn mối, nhưng sau đó thuật ngữ này được dùng để mơ tả dạng truyền thông
gián tiếp bởi sự thay đổi môi trường có thể quan sát được ở xã hội cơn trùng.
Những đặc trưng của stigmergy:
- Tính vật lý tự nhiên của thông tin được sinh ra bởi các côn trùng truyền
thông, tương ứng với sự thay đổi các trạng thái môi trường vật lý mà được thăm bởi
các côn trùng.
- Tính cục bộ tự nhiên của thơng tin được sinh ra, chỉ có thể được truy cập
bởi các cơn trùng thăm trạng thái đó.
Vì vậy ta có thể nói truyền thông stigmergy là một dạng truyền thông gián
tiếp dựa vào thay đổi thông tin qua tác động vật lý làm thay đổi mơi trường.

1.3/ Q trình phát triển của các thuật toán ACO
Hệ kiến là thể hiện đầu tiên và điển hình của các thuật tốn ACO, hầu hết
các thuật toán ACO hiện dùng đều được phát triển từ thuật tốn này. Vì vậy, trước
Giải thuật hệ kiến Max-min trơn giải bài tốn p-median có hạn chế khả năng


Luận văn Cao học

15

CH 2006-2008


khi giới thiệu các thuật toán ACO, tác giả xin được giới thiệu về hệ kiến và các cải
tiến quan trọng của chúng là hệ đàn kiến và hệ kiến Max-Min 3 .

1.3.1/ Hệ kiến (AS) và bài toán TSP
Bài toán người chào hàng (TSP - Travelling Salesman Problem) một mẫu bài
toán tối ưu tổ hợp thu hút được rất nhiều những cố gắng nghiên cứu. Bài toán TSP
đồng thời là bài toán rất quan trọng trong lớp bài toán ACO, là bài toán đầu tiên
được áp dụng bởi thuật tốn AS và sau đó được coi là một bài toán chuẩn để kiểm
định những ý tưởng và những thuật toán đề xuất sau này.
Hệ kiến (Ant System-AS) được đề xuất từ cách ứng xử được đề cập ở trên của
các con kiến thực, là một thuật tốn mà trong đó một tập các con kiến nhân tạo hợp
tác với nhau để tìm lời giải của một bài tốn bằng việc trao đổi thơng tin thơng qua
mùi được rải trên các cạnh của một đồ thị.
Có nhiều thuật toán AS như ant-cycle, ant-density, và ant-quantity, ở đây tác
giả chỉ xét thuật toán ant-cycle. Do thuật toán ant-cycle có kết quả thực nghiệm tốt
hơn hai thuật tốn kia, nên sau này nó được gọi đơn giản là thuật tốn AS, trong khi
hai thuật tốn cịn lại về sau khơng cịn được nghiên cứu và phát triển nữa.
Hệ kiến hoạt động như sau: mỗi con kiến sinh ra một đường đi (tour) bằng
cách chọn những thành phố theo một qui tắc chọn thành phố mới (state transition
rule) ngẫu nhiên, những con kiến thích đi tới các thành phố mà nối với những cạnh
ngắn có lượng mùi cao. Khi tất cả các con kiến đã hoàn thành đường đi của nó, một
qui tắc cập nhật mùi tồn cục (global pheromone updating rule) được áp dụng:
i)

Một tỉ lệ mùi bị bốc hơi trên tất các các cạnh bởi một hệ số bay hơi
mùi cho trước (những cạnh không được làm tươi sẽ ít được con
kiến chú ý).

ii) Mỗi con kiến rải một lượng mùi lên các cạnh thuộc đường đi tương

xứng với chiều dài đường đi của nó (hay nói cách khác là các cạnh
thuộc về nhiều đường đi ngắn là những cạnh nhận lượng mùi lớn
hơn).
Tiến trình trên được lặp lại.

3

Nguồn: tham khảo [2], [3], [4]

Giải thuật hệ kiến Max-min trơn giải bài tốn p-median có hạn chế khả năng


16

Luận văn Cao học

CH 2006-2008

Để giải bài toán TSP, AS dùng biến vết mùi τi,j kết hợp với mỗi cạnh (i,j) và ban
đầu được khởi tạo bởi giá trị τ0. Có m con kiến nhân tạo, ở bước lặp t chúng thực
hiện các thủ tục xây dựng lời giải và cập nhật mùi như sau:
Xây dựng lời giải:
Ban đầu mỗi con kiến được đặt ngẫu nhiên tại các thành phố và thăm các
thành phố khác để xây dựng đường đi với thủ tục tuần tự theo quy tắc chuyển trạng
thái sau:
Quy tắc chuyển trạng thái: Qui tắc chọn thành phố mới, được gọi là qui tắc tỉ lệ
ngẫu nhiên (random-proportional rule), được cho bởi công thức (1.1), là công thức
đưa ra xác suất chọn thành phố j để di chuyển tới đối với kiến k khi đang ở thành
phố i.
Giả sử kiến k đang ở thành phố i, nó sẽ chọn thành phố j tiếp theo với xác suất:


⎧ τ iα, j (t )η iβ, j
⎪⎪
α
β
Pi ,kj (t ) = ⎨ ∑ τ i ,uη i ,u
⎪ u∈ J k ( i )
⎪⎩
0

j ∈ J k (i )
j ∉ J k (i )

(1.1)

Hai tham số α , β thể hiện: xác suất lựa chọn cạnh (i, j) tỷ lệ thuận với cường độ vết
mùi τ ij (t) tại bước lặp t đang xét. Jk(i) là tập các đỉnh chưa được con kiến k đi qua
khi nó ở đỉnh i (để làm lời giải khả thi).
Thông tin heuristic η ij = 1

d ij

là nghịch đảo của khoảng cách d(i, j), nếu α = 0 con

kiến sẽ lựa chọn đỉnh tiếp theo dựa vào chiến lược “tham lam”: Cạnh nào ngắn nhất
sẽ được ưu tiên chọn trước, nếu β = 0 sự lựa chọn chỉ phụ thuộc vào cường độ vết
mùi. Tiếp tục như vậy nó sẽ tìm được một chu trình chấp nhận được làm một lời
giải đủ tốt cho bài tốn.
Cập nhật mùi:
Trong AS, qui tắc cập nhật tồn cục được thực hiện như sau: Khi tất cả các

con kiến đã xây dựng xong đường đi của nó, mùi được cập nhật trên tất cả các cạnh
theo công thức (1.2).
m

τ ij (t + 1) = (1 − ρ )τ ij (t ) + ∑ Δτ ij k (t )

(1.2)

k =1

Trong đó ρ∈ (0,1) được gọi là hệ số bay hơi mùi
Giải thuật hệ kiến Max-min trơn giải bài toán p-median có hạn chế khả năng


17

Luận văn Cao học

CH 2006-2008

và
⎧⎪ 1 k
Δτ ij k (t ) = ⎨ L (t )
⎪⎩ 0

Nếu (i,j) thuộc chu trình của kiến k(1.3)

ngược lại
L (t) là chiều dài của đường đi được thực hiện bởi kiến k tại bước lặp t, còn m là số
k


các con kiến được sử dụng.
Tham số ρ được sử dụng để làm bay hơi các vết mùi trên các cạnh và cho phép
lãng quên những cạnh ít sử dụng (các cạnh khơng thuộc hành trình của con kiến nào
sẽ có cường độ mùi giảm rất nhanh theo hàm mũ của số vòng lặp). Với những cạnh
có con kiến đi qua, lượng mùi sẽ được tăng thêm một lượng là 1/Lk.
Ưu và nhược điểm của AS
AS có một số ưu điểm:
• Việc tìm kiếm ngẫu nhiên dựa trên các thơng tin heuristic làm cho
việc tìm kiếm linh hoạt và mềm dẻo trên khơng gian tìm kiếm rộng,
nó hơn phương pháp heuristic sẵn có, do đó cho ta lời giải tốt hơn và
có thể tìm được lời giải tối ưu.
• Sự kết hợp được việc học tăng cường (reinforcement learning), trong
đó những lời giải tốt sẽ được sự tăng cường cao hơn thông qua thông
tin về cường độ vết mùi, cho phép ta từng bước thu hẹp khơng gian
tìm kiếm mà vẫn khơng bỏ qua những lời giải tốt. Do đó nâng cao
chất lượng thuật tốn.
Nhược điểm:
Giả sử w*(t) là chu trình có độ dài ngắn nhất mà các con kiến tìm được đến
lần lặp t thì sau Nc lần lặp w*(Nc) cho ta lời giải đủ tốt. Mặc dù AS là hữu dụng cho
việc khám phá lời giải tốt hoặc tối ưu cho các bài toán TSP nhỏ (tới 30 thành phố),
thời gian cần để tìm những kết quả tốt như vậy trên những bài tốn lớn đối với AS
là khó đạt được. Khi số đỉnh lớn thì lượng mùi trên mỗi cạnh khơng thuộc lời giải
tốt nhanh chóng dần về khơng nên hệ AS kém hiệu quả. Chất lượng thuật toán phụ
thuộc nhiều vào chất lượng của thơng tin heuristic, mà điều này thì chúng ta rất khó
can thiệp vào.
Hệ đàn kiến sẽ đưa ra ba thay đổi chính để cải thiện hiệu suất của hệ kiến khi
áp dụng vào các bài toán lớn, được trình bày ở phần tiếp theo.
Giải thuật hệ kiến Max-min trơn giải bài tốn p-median có hạn chế khả năng



18

Luận văn Cao học

CH 2006-2008

1.3.2/ Hệ đàn kiến (ACS)
Hệ đàn kiến (Ant Colony System-ACS) là thuật toán được xây dựng trên AS
dựa tên ý tưởng tăng tầm quan trọng của các thơng tin được tích luỹ bởi các con
kiến trước nhằm cải thiện hiệu suất khi áp dụng cho các bài tốn TSP có hướng kích
thước lớn (trên 50 thành phố). So với AS, ACS có ba cải tiến sau:
i)

Qui tắc chọn thành phố mới cung cấp một cách thức cân
bằng giữa sự khám phá cạnh mới với sự khai thác độ ưu
tiên và thơng tin được tích luỹ về bài tốn.

ii)

Qui tắc cập nhật mùi tồn cục (global updating
pheromone rule) được áp dụng chỉ với các cạnh thuộc về
đường đi tốt nhất.

iii)

Qui tắc cập nhật mùi địa phương (local updating
pheromone rule), được áp dụng trong khi các con kiến xây
dựng một lời giải cho nó.


Trong ACS, ở bước lặp t các quy tắc chuyển trạng thái (1.1) và cập nhật mùi (1.2)
thay đổi như sau:
Quy tắc chuyển trạng thái:
Giả sử con kiến k đang ở đỉnh i, nó chọn đỉnh s tiếp theo nhờ quy tắc:

⎧argmax k {τ ij (t)ηij β }
j∈Ni
⎪
s = ⎨j
⎪
⎩

Nếu q≤q0 (Sự khai thác - exploitation)
trái lại (Sự khám phá - exploration)

(1.4)

Ở đây q là một số ngẫu nhiên phân phối đều trong [0, l], q0 là một tham số (0≤q0≤
1), còn j là đỉnh được chọn theo công thức (1.1) với α=1.
Qui tắc chọn thành phố theo công thức (1.1) và (1.4) được gọi là qui tắc tỉ lệ giả
ngẫu nhiên (pseudo-random proportional rule). Theo qui tắc chọn thành phố mới
này, hướng các con kiến di chuyển đến các nút được nối với cạnh ngắn có lượng
mùi lớn. Tham số q0 quyết định mức quan trọng tương quan giữa sự khai thác các
đường đi cũ đối với sự khám phá đường đi mới.
Việc chọn lựa này đảm bảo hai điều quan trọng trong quá trình xây dựng lời giải
của thuật tốn ACS. Một là, khai thác được thơng tin tìm kiếm trước khi chọn nút
có xác suất chọn lớn nhất. Hai là, lời giải xây dựng ngẫu nhiên để mở rộng khơng
gian tìm kiếm của thuật toán.
Giải thuật hệ kiến Max-min trơn giải bài tốn p-median có hạn chế khả năng



Luận văn Cao học

19

CH 2006-2008

Quy tắc cập nhật mùi :
Mùi sẽ được cập nhật theo cả hai quy tắc: Cập nhật địa phương và cập nhật toàn
cục.
Cập nhật mùi địa phương:
Trong khi đang xây dựng một lời giải (tức là đường đi) của mình, mỗi con
kiến sẽ cập nhật mùi cho cạnh (i, j) mà nó đi qua bằng cách áp dụng qui tắc cập nhật
địa phương của công thức (1.5).

τ ij ← (1 − ρ )τ ij + ρδτ (i, j )

(1.5)

Ở đây 0 < ρ < 1 gọi là tham số bay hơi mùi, δτ (i, j) có thể lấy một trong 2 giá trị
sau:
* δτ ( i, j) = τ0, ở đây τ0 là mùi khởi đầu.
* δτ (i, j) = 0
Luật này có tác dụng giúp các con kiến tránh hội tụ về cùng một đường đi,
điều này giải thích khơng khó: khi đặt τ0 = (nLnn-1) trong đó n là số đỉnh, Lnn là
chiều dài của một lời giải do một heulistic sinh ra từ trước (giai đoạn khởi tạo và do
δτ (i,j) ≤τ(i, j) ∀ (i, j) nên cứ sau mỗi lần cập nhật địa phương τi,j lại giảm đi một
lượng ρ(τ(i, j)- δτ (i, j)) làm giảm đi mức độ "hấp dẫn" của các cạnh được thăm
khiến cho các con kiến sẽ chú ý thăm các cạnh chưa bao giờ được thăm, tránh được
tình trạng hội tụ tới cùng một đường đi.

Ngồi ra ACS sử dụng một cấu trúc dữ liệu gọi là danh sách tuyển chọn
(candidate list-cl), cấu trúc này có nhiệm vụ cung cấp thêm thông tin heuristic cục
bộ cho thủ tục xây dựng lời giải. Với một thành phố cho trước, danh sách này sẽ
chứa hữu hạn cl thành phố lân cận được ưu tiên đến hơn (cl là một tham số của
thuật toán). Các con kiến khi đến một thành phố bất kì, nó sẽ đọc tuần tự danh sách
này từ đầu đến cuối (danh sách được sắp theo thứ tự tăng dần của khoảng cách nối
thành phố hiện lại với thành phố lân cận tương ứng) và chọn thành phố đầu tiên
chưa nằm trong đường đi của nó làm thành phố kế tiếp, khi khơng có thành phố nào
trong danh sách thỏa mãn tính chất này thì các thành phố bên ngoài danh sách chưa
được thăm sẽ được chọn theo luật chuyển trạng thái. Các kết quả khi chạy ACS trên
các bài toán chuẩn được đem so sánh với các siêu heuristic khác đã cho thấy ACS là
heuristic tốt nhất về chất lượng lời giải cũng như thời gian thực hiện (có thể khơng
Giải thuật hệ kiến Max-min trơn giải bài tốn p-median có hạn chế khả năng


20

Luận văn Cao học

CH 2006-2008

quan trọng vì các heuristic khác có thể thực hiện trên các máy khác nhau và được
viết mã chưa tối ưu…)
Cập nhật mùi toàn cục :
Trong ACS chỉ duy nhất con kiến toàn cục tốt nhất (là con kiến đã xây dựng
đường đi ngắn nhất trong các bước lặp) là được phép rải mùi. Sự chọn lựa này cùng
với việc sử dụng qui tắc tỉ lệ giả ngẫu nhiên nhằm mục đích làm cho việc tìm kiếm
thực tế hơn: Các con kiến tìm kiếm trong một lân cận của đường đi tốt nhất được
tìm thấy cho đến bước lặp hiện tại của thuật toán. Việc cập nhật toàn cục được thực
hiện sau khi tất cả các con kiến đã hoàn thành xong đường đi của chúng. Mùi được

cập nhật bởi qui tắc cập nhật toàn cục của cơng thức (1.6).
Cập nhật mùi tồn cục được áp dụng cho những cạnh (i, j) thuộc đường đi ngắn nhất
w*(t) theo công thức :
τ i , j ← (1 − ρ )τ i , j + 1

Lgl (t )

(1.6)

Trong đó Lgl (t) là độ dài đường đi ngắn nhất w*(t).

1.3.2/ Thuật toán hệ kiến Max-Min
Hệ kiến Max-Min (Max-Min Ant System-MMAS) được cải tiến từ AS bằng
cách chỉ cho phép một con kiến tốt nhất cập nhật mùi (con kiến có hành trình tốt
nhất w(t) kể từ khi bắt đầu thuật tốn hoặc con kiến có hành trình tốt nhất w(t) tại
bước lặp hiện tại). Để tránh hiện tượng tắc nghẽn (stagnation): do nồng độ mùi tập
trung ở một số cung quá cao nên các con kiến lựa chọn đi lựa chọn lại các cung đó,
MMAS đưa vào hai cận, cận trên ( τ max ) và cận dưới ( τ min ) để khống chế nồng độ
các vết mùi trên mỗi cung. Chính vì vậy thuật tốn được gọi là hệ kiến Max-Min về
sau các thuật tốn ACO có tính chất này cũng gọi là thuật tốn Max-Min.
MMAS khống chế nồng độ các vết mùi bằng cách sử dụng cận dưới τ min có
giá trị nhỏ nhất và cận trên có giá trị lớn nhất là τ max , nghĩa là tất cả các cạnh ít
được con kiến đi qua có xác suất nhỏ nhưng vẫn lớn hơn 0 nhiều lần và hạn chế lựa
chọn đi lựa chọn lại một cạnh tốt của các con kiến (cạnh này tập trung mùi mạnh).
Điều này làm cho thuật toán tránh được tình trạng tắc nghẽn trong quá trình tìm
kiếm, đặc biệt khi số vịng lặp lớn nó sẽ tăng khả năng khám phá cho những con
kiến. Các vết mùi khi khởi tạo ln có giá trị lớn nhất cho tất cả các cạnh làm cho

Giải thuật hệ kiến Max-min trơn giải bài tốn p-median có hạn chế khả năng



Luận văn Cao học

21

CH 2006-2008

ρ
Chỉ các cạnh thuộc lời giải tốt nhất toàn cục w*(t) mới được rải thêm một
lượng mùi do chính con kiến tìm ra lời giải đó thực hiện (trong thực nghiệm lời giải
tốt trong vòng lặp hiện tại được rải thêm mùi sẽ tốt hơn vì nó tăng khả năng khám
phá cho các con kiến). Nồng độ mùi trên các cạnh ít được sử dụng sẽ giảm chậm
nhưng trên các cạnh thuộc lời giải tốt vẫn được gia tăng nên các con kiến vẫn ưa
chọn nhiều hơn.
Trong hệ kiến Max-Min thủ tục xây dựng lời giải giống như trong AS còn
quy tắc cập nhật mùi thực hiện như sau:
Cập nhật mùi:

τ ij ← (1 − ρ )τ ij + Δ ij
ρL−1 ( w(t ))
⎪⎩max{τ min − (1 − ρ )τ ij ,0}

⎧
trong đó Δ ij = ⎪⎨

(1.7)
(i, j)∈ w(t)

(1.8)


ngược lại
Nhược điểm của thuật toán này là sẽ tập trung vào khai thác các lời giải tốt
tìm được mà không phân biệt được các cạnh không dùng được với các cạnh dùng
được nhưng không thuộc lời giải tốt. Do đó sẽ hạn chế khả năng khám phá nếu chọn

τ min bé, còn nếu chọn τ min lớn thì thuật tốn sẽ gần với tìm kiếm ngẫu nhiên dựa
trên thông tin heuristic, nhưng điều này lại giảm khả năng học tăng cường-một ưu
điểm trong các thuật toán kiến. Vì vậy chọn tỷ lệ giữa τ min và τ max ảnh hưởng rất
nhiều đến hiệu suất của thuật toán.
Đây là những đặc trưng quan trọng nhất của thuật toán hệ kiến Max-Min Chi tiết về
thuật toán này sẽ được trình bày cụ thể hơn trong chương 3 của luận văn.

Giải thuật hệ kiến Max-min trơn giải bài toán p-median có hạn chế khả năng


Luận văn Cao học

22

CH 2006-2008

Chương 2

PHƯƠNG PHÁP TỐI ƯU ĐÀN KIẾN ACO
2.1/ Một số heuristic ACO 4
Trước khi đi vào chi tiết, tác giả xin trình bày sơ qua về sự hình thành tên
gọi của một số heuristic ACO. Năm 1991 Marco Dorigo trong luận án tiến sĩ của
ông đã đề xuất thuật toán hệ kiến giải bài toán người chào hàng. Hầu hết các thuật
toán ACO sau này đều phát triển từ hệ kiến. Tuy nhiên, trong AS có một số nhược
điểm như: khơng có sự hợp tác giữa các con kiến, sau một thời gian chạy nồng độ

mùi trên các cạnh dần về 0. Để khắc phục các nhược điểm của AS, năm 1996
Dorigo cùng với V.Maniezzo và A. Colorni đã đề xuất thuật toán ACS cũng cho bài
toán TSP trên cơ sở mở rộng AS bằng cách thay đổi luật chuyển trạng thái và cách
cập nhật mùi, các cải tiến này đã cải thiện đáng kể hiệu suất của AS và với các kết
quả thực nghiệm đã cho thấy ACS tốt hơn hẳn các thuật toán khác như luyện kim,
di truyền, tiến hóa…tuy nhiên các vết mùi trong ACS vẫn dần về 0 mặc dù khả
năng hội tụ cao. Năm 1997, Thomas Stutzle và Holger H. Hoos đề xuất hệ kiến
Max-Min, là thuật toán đầu tiên sử dụng cận trên và cận dưới để khống chế vết mùi,
các vết mùi không bị dần về 0 do đã bị chặn dưới. Khi thử nghiệm hệ kiến MAXMIN các tác giả vẫn thu được các kết quả khả quan tương đương ACS, hệ MMAS
được ưa dùng hơn vì nó đơn giản, dễ sử dụng.
Nhằm mục đích đưa ra một lược đồ làm việc tổng quát cho các thuật toán
kiến, năm 1999 Marco Dorigo, Luca M. Gambardella và Gianni Di Cao đã đề xuất
phương pháp tối ưu hoá đàn kiến: ACO. ACO là một meta-heuristic, sẽ trình bày ở
phần tiếp theo. Với hệ kiến, hệ đàn kiến, hệ kiến Max-Min có những đặc điểm hồn
tồn khớp với ACO nên có thể xem chúng là những ứng dụng cụ thể của ACO.
Ở phần tiếp theo tác giả xin được trình bày phương pháp tối ưu đàn kiến cho
lớp bài toán ACOτmin nói trên đã được đề xuất bởi Marco Dorigo, Luca M.
Gambardella và Gianni Di Cao tiếp đến là cơ sở lý thuyết cho vết mùi của hệ MaxMin và đặc tính hội tụ của vết mùi theo quan điểm Max-Min trên hai thuật tốn có
hiệu suất tốt trong các thuật tốn ACO đó là: Hệ đàn kiến và hệ kiến Max-Min.
4

Các nội dung chương này được tác giả tham khảo và tổng hợp từ chương 2 của [3] (trang 25-40)

Giải thuật hệ kiến Max-min trơn giải bài tốn p-median có hạn chế khả năng


Luận văn Cao học

23


CH 2006-2008

2.2/ Meta-heuristic tối ưu hoá đàn kiến (ACO metaheuristic)
Các con kiến nhân tạo được sử dụng trong ACO hợp tác với nhau trong việc
tìm các lời giải tốt cho các bài toán tối ưu tổ hợp khó. Sự hợp tác là một thành phần
quan trọng của ACO: đó là sự chọn lựa để phân phối các tài ngun tính tốn cho
các con kiến nhân tạo. Các con kiến này truyền thông một cách gián tiếp bởi
stigmergy. Các lời giải tốt là một đặc tính nổi bật của sự tương tác (bằng cách hợp
tác) này.
Các con kiến nhân tạo có đặc tính 2 mặt: Mặt thứ nhất, chúng trừu tượng các
đặc điểm cách tìm đường của các con kiến mà gần như là mấu chốt của cách thức
tìm đường đi ngắn nhất được thấy trong các đàn kiến thực. Mặt kia, là những khả
năng mà không thể có ở các con kiến thực như có bộ nhớ, rải mùi theo tỷ lệ có thể
điều khiển được, các khả năng này được đưa thêm vào tùy thuộc đặc trưng của bài
tốn áp dụng nhằm mục đích là để ACO trở thành một cách tiếp cận kỹ thuật
(engineering) cho việc thiết kế và thực hiện các hệ thống phần mềm cho các bài
tốn tối ưu tổ hợp khó.

2.2.1/ Bài toán tổng quát
Các thuật toán ACO được áp dụng để giải các bài toán tối ưu tổ hợp, các đặc
trưng của lớp các bài toán tối ưu tổ hợp được phát biểu như sau:
Xét bài tốn cực tiểu hóa ( S , f , Ω ) , trong đó S là tập hợp hữu hạn trạng thái, f là
hàm mục tiêu xác định trên S (với s ∈ S có giá trị hàm mục tiêu là f(s)), còn Ω là
một tập các ràng buộc để xác định S qua các thành phần của tập hữu hạn C và các
liên kết của tập này. Mục tiêu của bài toán cực tiểu hố là tìm ra một trạng thái tối
ưu s*, một trạng thái có giá trị cực tiểu.
Bài tốn tối ưu tổ hợp ( S , f , Ω ) được ánh xạ thành một bài tốn có các đặc tính
sau:

1) Cho một tập hữu hạn gồm n thành phần C = {c1, c2, …, cn}. Ta ký hiệu X là

tập các dãy trong C độ dài không quá h:
X={<u0,...,uk>/ ui∈C ∀i ≤ k ≤ h}.

2) Tồn tại tập con X* ⊆ X và ánh xạ ϕ từ X* lên S sao cho ϕ −1 ( s) không rỗng
với mọi s ∈ S . X* có thể xây dựng được từ tập con C0 nào đó của C và X*
theo đặc tính 3.

3) Từ C0 mở rộng được thành X* theo thủ tục tuần tự:
Giải thuật hệ kiến Max-min trơn giải bài tốn p-median có hạn chế khả năng