ĐẠI HỌC QUỐC GIA TP HỒ CHÍ MINH
ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
THUẬT TOÁN ĐÀN KIẾN VÀ ỨNG DỤNG
TRONG BÀI TOÁN TSP
GVHD: PGS.TS.Đỗ Văn Nhơn
Học viên : Vũ Thế Nhân – CH1301030
Thành phố Hồ Chí Minh , tháng 01 năm 2014
Mục lục
2
I. Thuật toán đàn kiến (ACO)
1. Giới thiệu
Từ những quan sát mô hình, hành vi thực tế của loài kiến, và sử dụng các mô hình
này như là một nguồn cảm hứng cho việc thiết kế các thuật toán cho các giải pháp
tối ưu hóa và phân phối kiểm soát các vấn đề.
Các ý tưởng chính là việc tự tổ chức phối hợp giữa các nguyên tắc cho phép với
hành vi thực sự của loài kiến có thể được triển khai để giải quyết vấn đề về máy
tính.
Một số khía cạnh khác nhau ở các hành vi ứng xử của các đàn kiến có cảm hứng
cho các thuật toán kiến khác nhau.
2. Hành vi của đàn kiến và tối ưu hóa
Nhận thức đặc biệt của đàn kiến chỉ đơn giản là sự phát triển và hoàn toàn mò
mẫm và một điều quan trọng trong nghiên cứu vềloài kiến là hành vi liên lạc giữa
các con kiến, hoặc giữa các cá nhân với môi trường, được dựa trên việc sử dụng
các sản phẩm hóa chất của các loài kiến. Các hóa chất đó được gọi là pheromones
a. Chiếc cầu đôi
Sử dụng một cây cầu nối tổ của đàn kiến với nguồn thức ăn và sử dụng các
thửnghiệm với tỉ lệ r = l
l
/ l
s
giữa độ dài hai nhánh của cây cầu, l

l
là độdài của
nhánh dài và l
s
là độdài của nhánh ngắn hơn. Trong thử nghiệm đầu tiên với
cây cầu có hai nhánh chiều dài bằng nhau (r = 1).
Khi bắt đầu, trên 2 nhánh của cây cầu đều chưa có pheromones. Do đó, các con
kiến có thể chọn một trong các nhánh với cùng một xác suất. Tuy nhiên, do sự
lựa chọn là ngẫu nhiên lên sau một thời gian số lượng kiến đi trên những chi
nhánh sẽ là khác nhau. Bởi vì loài kiến sẽ gửi pheromones trong khi di chuyển,
dần dần số lượng pheromones trên những nhánh cũng sẽ khác nhau, điều này
càng kích thích thêm đàn kiến sẽ lựa chọn nhánh có lượng mùi pheromones
lớn, và như vậy đến một thời gian nào đó tất cả đàn kiến sẽ hội tụ về cùng một
nhánh.
3
b. Mô hình ngẫu nhiên
Trong mô hình này, ψ là mỗi giây đàn kiến băng qua cầu trong mỗi hướng ở
một tốc độ hằng số v (cm/s), một trong những đơn vị gửi pheromones trên các
nhánh. Cho độ dài l
l
và l
s
(cm) trong các nhánh dài và ngắn, một con kiến chọn
nhánh ngắn sẽ đi ngang qua nó trong khoảng thời gian là t
s
= l
s
/ v (giây), trong
khi kiến lựa chọn Chi nhánh dài sẽ sử dụng r.t
s

giây, với r=l
l
/l
s
.
Xác suất p
ia
(t) là xác xuất tại điểm i (i Є{1,2}) (xem hình 1.1b) kiến chọn
nhánh a (a Є{s,l}), trong đó s, l là các chi nhánh ngắn và dài tương ứng, tại
thời điểm t tổng số lượng pheromones φ
ia
(t) được thiết lập trên các chi nhánh,
là tổng lượng pheromones mà các loài kiến đểlại trên các chi nhánh cho đến
thời gian t đó.
Trong mô hình này đàn kiến gửi lại vết mùi pheromones của họ trên cả hai
đường đi: từ tổ đến nguồn thức ăn và quay trở lại tổ. Sự di chuyển này là một
hành vi ứng xử cần thiết để có được sự hội tụ của đàn kiến hướng về nhánh
ngắn
3. Đàn kiến nhân tạo
Qua những thử nghiệm trên cho thấy rõ ràng có khả năng xây dựng được tối ưu
hóa đàn kiến: Thông tin để tìm ra con đường ngắn nhất giữa 2 điểm có thể dựa vào
quy tắc xác xuất.
Có 2 khía cạnh bất đồng quan trọng:
- Phạm vi xem xét các hành vi của hệthống là trung bình, và không phải những
hành vi ứng xửtuân theo biến thiên ngẫu nhiên của đàn kiến là duy nhất.
- Đây là thí nghiệm trên những thời gian không liên tục, trong khi trước đó mô
hình xét trong một thời gian liên tục.
4
4. Kiến nhân tạo và chi phí tối thiểu trên đường đi
Những hành vi là:

- Giải pháp xây dựng theo hướng xác xuất bởi vết mùi pheromones, với sự cập
nhật pheromones nhanh
- Thuyết tiền định con đường quay trở lại với việc loại bỏ vòng lặp và sự cập
nhật pheromones
- Đánh giá về chất lượng của các giải pháp tạo ra và sử dụng các giải pháp chất
lượng trong việc xác định số lượng pheromones đã gửi lại.
Xác xuất chọn đỉnh tiếp theo của đàn kiến và giải pháp xây dựng.S-ACO đàn kiến
có hai phương thức hoạt động: chuyển tiếp và quay trở lại.
Thuyết tiền định về hành vi quay trở về tổ của đàn kiến và sự cập nhật
pheromones.Việc sử dụng một bộ nhớ rõ ràng cho phép một con kiến có thể trở lại
con đường mà nó đã đi trong khi tìm kiếm đến đỉnh đích.
Cơ sở giải pháp hiệu quả của sự cập nhập pheromones.Trong S-ACO đàn kiến nhớ
các đỉnh mà nó đi qua trong quá trình tìm nguồn thức ăn, cũng như các chi phí trên
các cạnh đã qua nếu biểu đồ có trọng số.
Sự bay hơi của Pheromones: Trong đàn kiến thực, lượng pheromone giảm theo
thời gian vì có sự bay hơi.
Để biểu diễn mỗi cạnh (i,j) của đồthịG =(N,A) chúng tôi dùng một biến gọi là τ
ij

gọi là vết mùi nhân tạo, để rút ngắn lượng mùi pheromones trong thời gian tiếp
theo.
Vết mùi pheromones được tạo và cập nhập bởi đàn kiến. Ở những phương thức
tính số lượng vết mùi pheromones trên các cạnh chỉ được tính theo tỷ lệ, ước tính
của đàn kiến.
Hành vi tìm kiếm đường đi của đàn kiến: Mỗi kiến, bắt đầu từmột đỉnh, một
giải pháp cho vấn đề ứng dụng từng bước được giải quyết. Một con kiến k tại một
đỉnh i bất kì sửdụng vết mùi pheromones τ
ij
để tính xác suất chọn đỉnh j như sau
5

Trong đó N
l
k
là vùng lân cận của kiến k ở đỉnh i trong S-ACO vùng lân cận của
đỉnh i là tất cả các đỉnh kết nối trực tiếp đến đỉnh i trong đồthịG =(N,A), ngoại trừ
tất cả các đỉnh trước (ví dụ, các đỉnh trước khi di chuyển đến đỉnh i của kiến)
Đường đi về tổ và sự cập nhập vết mùi. Khi đạt tới đỉnh đích, kiến thực hiện quá
trình quay về tổ trên cùng con đường đến nguồn thực phẩm. Bổ sung tính năng
này là, trước khi bắt đầu quá trình quay về tổ, kiến sẽ loại bỏ những đường đi rơi
vào tình trạng vòng lặp mà nó đã gặp phải trên đường đi tìm đến nguồn thức ăn.
Trong thời gian quay trở về tổ con kiến thứ k sẽ để lại một lượng ∆
τ
k
pheromones
trên các cạnh mà nó đi qua. Trong đó, nếu kiến thứ k quay trởvềtổtrên cạnh (i,j),
thì giá trị τ
ij
pheromones sẽ thay đổi như sau:
Một khía cạnh quan trọng vẫn là sự lựa chọn của ∆
τ
k
. Trong những trường hợp đơn
giản nhất, giá trịcủa ∆
τ
k
là một hằng sốcho tất cả các loài kiến
Sự bay hơi của vết mùi pheromones.Vết mùi pheromones bay hơi có thể được
coi như là một kỹ thuật thăm dò nhanh chóng của đàn kiến tìm điểm cực thuận tốt
trên đường đi. Sau đó mỗi kiến thứk di chuyển đến một đỉnh kếtiếp nào đó tuỳtheo
hành vi tìm kiếm của kiến đã được mô tả ở trên, lượng bay hơi của pheromones

được áp dụng theo công thức sau đây với tất cả các cung:
τ
ij
=(1- ρ)τ
ij
, (i,j) ∈A , p ∈(0,1)
Trong đó tham số ρ(0,1]. Sau khi sựbay hơi pheromones đã được áp dụng cho tất
cả các cạnh, sốlượng pheromones ∆
τ
k
sẽ được thêm vào các cạnh.
II. Một số thuật toán ACO áp dụng cho bài toán TSP
1. Bài toán TSP
Cho G = (N, A,) là đồ thị có hướng đầy đủ có trọng số, trong đó N là tập hợp của n
= |N| nút (thành phố) , A = {(i,j)| (i,j) є VxV} là tập tất cả các cung của đồ thị. Mỗi
cung (i, j) được gán một trọng số dij để biểu diễn khoảng cách giữa 2 thành phố i
và j. Bài toán TSP trở thành bài toán tìm chu trình Hamilton có độ dài ngắn nhất
trên đồ thị G. Ta cần phân biệt hai loại TSP, symmetric TSP có khoảng cách giữa
các thành phố không phụ thuộc vào hướng dij = dji với mọi thành phố i, j và
asymmetric TSP – ATSP tồn tại ít nhất một cặp cạnh sao cho dij ≠ dji. Đối với đồ
thị không đối xứng có (n-1)! đường đi chấp nhận được còn đối với đồ thị đối xứng
có (n-1)!/2 đường đi có khả năng. Khi n lớn ta không thể tìm được lời giải tối ưu
bằng các thuật toán vét cạn, hướng đi giải quyết bài toán là tìm các lời giải xấp xỉ
tối ưu bằng các thuật toán heuristic, hoặc các thuật toán tiến hóa
6
2. Thuật toán Ant System (AS)
Phương pháp giải TSP bằng AS :
Đầu tiên là xây dựng đồ thị, n đỉnh biểu diễn cho n thành phố. Vệt mùi: mỗi cạnh
được (i, j) được gắn một vệt mùi τ
ij

. Thông tin heuristic: η
ij
là nghịch đảo khoảng
cách giữa hai thành phố (i, j) η
ij
= 1/ dij Trong phần lớn các thuật toán ACO cho
bài toán TSP người ta đều sử dụng thông tin heuristic như trên. Có hai quá trình
chính trong thuật toán AS là quá trình xây dựng lời giải và quá trình cập nhật các
vệt mùi.
Xây dựng lời giải: Có m con kiến nhân tạo được đặt khởi tạo ngẫu nhiên tại các
đỉnh, 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 lời giải riêng
của nó bằng cách chọn một đỉnh mà chúng chưa thăm để đi. Ban đầu các vệt mùi
được khởi tạo bởi giá trị τ
0
, mỗi con kiến được đặt ngẫu nhiên tại một đỉnh xuất
phát và lần lượt đi thăm các đỉnh còn lại để xây dựng đường đi với theo quy tắc
như sau (gọi là quy tắc random proportional), con kiến thứ k đang ở đỉnh i sẽ chọn
đỉnh j tiếp theo với xác suất:
trong đó cường độ vệt mùi τ
ij
(t) và thông tin heuristic η
ij
ta đã giới thiệu ở trên.
Hai tham số α và β là hai tham số xác định sự ảnh hưởng của vệt mùi và thông tin
heuristic : nếu α = 0 các thành phố gần nhất có nhiều khả năng được chọn, thuật
toán trở nên giống với thuật toán heuristic thông thường, nếu β = 0 chỉ có thông tin
về cường độ vệt mùi được sử dụng mà không hề có bất kỳ một thông tin heuristic
nào làm cho kết quả tìm kiếm được nghèo nàn và bài toán đễ rơi vào trường hợp
cực tiểu địa phương. Nik là các láng giềng có thể đi của con kiến k khi nó ở đỉnh
i, đó là tập các đỉnh chưa được con kiến thứ k đi qua (xác suất chọn một đỉnh nằm

ngoài N
i
k
là 0). Với luật xác suất này, thì xác suất để chọn một cạnh (i, j) tăng lên
khi mà mùi τij và thông tin heuristic η
ij
tương ứng của cạnh đó tăng. Mỗi con
kiến có một bộ nhớ M
k
chứa danh sách các thành phố mà chúng đã đến thăm theo
thứ tự. Nó được dùng để tính toán tập các láng giềng chưa thăm N
i
k
trong công
thức xác suất (1.1) ở trên. M
k
cũng cho phép các con kiến tính toán quãng đường
mà nó đã đi được và giúp kiến xác định được cạnh nó đi qua để cập nhật mùi. Chú
ý rằng trong khi xây dựng lời giải, có hai cách cài đặt nó: song song và tuần tự.
Với cách cài đặt song song, tại mỗi bước xây dựng lời giải tất cả các con kiến đều
di chuyển từ thành phố của chúng đến thành phố tiếp theo. Trong khi đó với
phương pháp cài đặt tuần tự thì sau khi một con kiến hoàn tất đường đi của nó, con
kiến tiếp theo mới bắt đầu xây dựng đường đi của nó. Đối với thuật toán AS thì cả
7
hai cách cài đặt trên là tương đương, tức là chúng không gây ra ảnh hưởng quan
trọng gì đến thuật toán. Sau này ta sẽ thấy với thuật toán AS thì không như thế
Cập nhật mùi Sau khi tất cả các con kiến xây dựng xong các lời giải của chúng,
các vệt mùi sẽ được cập nhật. Đây là hình thực cập nhật offline sẽ nói đến sau.
Đầu tiên tất cả các cạnh sẽ bị mất đi một lượng mùi (do bị bay hơi), sau đó những
cạnh mà có các con kiến đi qua sẽ được tăng cường thêm một lượng mùi. Công

thức thức bay hơi mùi:
trong đó 0 < ρ <= 1 là tỉ lệ bay hơi mùi, tham số ρ được dùng để tránh sự tích lũy
không có giới hạn của các vết mùi và nó làm cho thuật toán quên đi những quyết
định tồi ở bước trước. Nếu một cạnh không được chọn bởi bất kì con kiến nào thì
cường độ mùi của nó sẽ bị giảm theo hàm mũ của số vòng lặp. Sau khi bay hơi
mùi tất cả các con kiến sẽ tăng cường mùi cho những cạnh mà chúng đã đi qua
theo công thức
C
k
là độ dài của tuyến đường T
k
được xây dựng bởi con kiến k. Với công thức trên,
tuyến đường của những con kiến nào mà càng tốt hơn thì nó càng được tăng
cường thêm nhiều mùi. Nói tóm lại thì những cạnh mà được nhiều con kiến lựa
chọn thì sẽ nhận được nhiều mùi hơn và có nhiều khả năng hơn sẽ được lựa chọn
bởi các con kiến trong các vòng lặp tiếp theo của thuật toán.
Ưu điểm của AS: Việc tìm kiếm ngẫu nhiên dựa vào trên các thông tin heuristic
làm cho phép tìm kiếm linh hoạt và mềm dẻo trên không gian rộng 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 với học tăng cường (reinforcement learning) trong đó những lời
giải tốt hơn sẽ được sự tăng cường 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 và vẫn không loại bỏ các lời
giải tốt, do đó nâng cao chất lượng thuật toán.
Nhược điểm của AS: Hiệu suất của nó giảm đột ngộ so với nhiều thuật toán
metaheuristic khác khi mà kích thước của bài toán tăng lên. Bởi vì khi số đỉnh của
đồ thị lớn thì cường độ vệt mùi trên những cạnh không thuộc lời giải tốt (hoặc ít
8
được con kiến lựa chọn) sẽ nhanh chóng giảm dần về 0, làm cho cơ hội khám phá
hay tìm kiếm ngẫu nhiên của thuật toán sẽ giảm mà đây là một trong những điểm
mạnh của các thuật toán mô phỏng tiến hóa tự nhiên nên thuật toán hệ kiến AS

kém hiệu quả.
3. Thuật toán Max-Min Ant System (MMAS)
MMAS và một số thuật toán khác như Elitist AS, Rank-Based AS là các thuật
toán có được hiệu suất cao hơn nhiều so với thuật toán AS nhờ vào những thay đổi
nhỏ trong thuật toán AS, đây được coi là các thuật toán kế thừa trực tiếp từ thuật
toán AS vì chúng về cơ bản là không khác gì nhiều so với AS.
MMAS đưa ra bốn thay đổi chính đối với AS.
Thứ nhất, nó chú trọng nhiều vào những tuyến đường tốt nhất được tìm thấy :
MMAS, chỉ cho phép con kiến tốt nhất hoặc là tại vòng lặp hiện tại iteration-best ,
hoặc tính từ thời điểm bắt đầu best-so-far được phép cập nhật mùi. Tuy nhiên việc
này sẽ dẫn đến hiện tượng ứ đọng, tập trung (stagnation) quá nhiều khi mà tất cả
các con kiến đều cùng chọn một tuyến đường đi, do sự tăng lên quá thừa của
cường độ các vết mùi trên các cạnh tốt.
Để tránh hiện tượng trên một cải tiến thứ hai là MMAS giới hạn cường độ mùi
trong một khoảng cố định [τ
max
, τ
min
]. Tất cả vệt mùi trên các cạnh đều nằm trong
khoảng này.
Thứ ba, các vệt mùi được khởi tạo là cận trên của vệt mùi τmax , cùng với việc
một tỉ lệ bay hơi mùi nhỏ sẽ làm tăng khả năng khám phá cho các con kiến ngay từ
khi bắt đầu.
Cuối cùng, trong thuật toán MMAS các vệt mùi sẽ được khởi tạo lại nếu như hệ
thống rơi vào trạng thái stagnation, hoặc không thể cải thiện được tuyến đường đã
tạo ra sau một số lượng các vòng lặp liên tiếp. Cập nhật mùi Cũng như thuật toán
AS, sau khi tất cả các con kiến xây dựng xong lời giải của chúng tất cả các vết mùi
đều bay hơi một lượng phụ thuộc vào tham số bay hơi mùi
Sau đó cường độ mùi trên mỗi cạnh có con kiến tốt nhất đi qua được cập nhật một
lượng theo công thức

Khi ta sử dụng luật update best-so-far thì quá trình tìm kiếm sẽ tập trung nhanh
chóng vào tuyến đường tốt nhất từ đầu đến hiện tại. Còn khi sử dụng update
iteration-best thì số lượng các cạnh được tăng cường mùi là nhiều hơn và sự tìm
kiếm cũng phân tán hơn. Các kết quả thực nghiệm cho thấy rằng, với những bài
toán TSP nhỏ thì tốt nhất là chỉ sử dụng update iteration-best . Trong khi đó với
9
những bài toán TSP lớn khoảng vài trăm đỉnh thì hiệu suất tốt nhất đạt được với
việc sử dụng chú trọng đến update best-so-far.
Giới hạn vết mùi
MMAS sử dụng hai cận trên (τmax) và cận dưới (τmin) để khống chế nồng độ
mỗi mùi trên mỗi cạnh với mục đích tránh cho thuật toán khỏi hiện tượng tắc
nghẽn tìm kiếm. Cụ thể hơn, giới hạn của vệt mùi sẽ làm cho xác suất p
ij
của việc
chọn thành phố j khi kiến ở thành phố i bị giới hạn trong khoảng [p
min
, p
max
].
Nhược điểm của thuật toán này là sẽ tập trung tìm kiếm vào các cạnh thuộc lời
giải tốt nhất tìm được, vì vậy hạn chế khả năng khám phá nếu τmin chọn bé. Ngoài
ra khi chọn τmin bé thì gần như các thông tin heuristic được tận dụng triệt để, còn
các cường độ mùi sẽ bị giảm nhanh và không có tác dụng mấy. Còn nếu chọn τmin
lớn thì thuật toán sẽ gần với tìm kiếm ngẫu nhiên và ít phụ thuộc vào các thông tin
heuristic đồng thời khả năng học tăng cường cũng giảm theo
4. Thuật toán Ant Colony System
Trong khi MMAS là thuật toán chỉ thay đổi phần nhỏ từ thuật toán AS, thì các
thuật toán khác như ACS, Ant-Q , đạt được hiệu suất cao bằng cách đưa hẳn các
kỹ thuật hoàn toàn mới mà ý tưởng của nó không có trong thuật toán AS cơ bản.
Đây là những thuật toán mở rộng của AS.

Thuật toán ACS khác với AS ở ba điểm chính.
Thứ nhất, nó lợi dụng kinh nghiệm tích lũy được từ những con kiến hơn nhiều so
với thuật toán AS thông qua việc dùng một luật lựa chọn đỉnh linh hoạt hơn.
Thứ hai, sự tăng cường mùi và bay hơi mùi chỉ áp dụng trên những cạnh thuộc
tuyến đường đi tốt nhất từ trước tới hiện tại.
Thứ ba, mỗi khi một con kiến sử dụng một cạnh (i, j) để di chuyển từ thành phố i
sang j, nó sẽ lấy đi một ít mùi từ cạnh đó để tăng khả năng khám phá đường đi.
Sau đây là chi tiết của các cải tiến.
Xây dựng lời giải
Trong ACS giả sử con kiến k đang ở đỉnh i, nó sẽ chọn đỉnh j tiếp theo nhờ quy tắc
sau (pseudorandom proportional ) với công thức
trong đó q là giá trị ngẫu nhiên phân phối đều trong đoạn [0, 1]
q0 (0 <= q
0
<= 1) là một tham số
10
J là đỉnh ngẫu nhiên dựa vào phân phối xác suất theo công thức (1.1) với α = 1.
Như vậy với xác suất q0 các con kiến sẽ chọn đường đi tốt nhất có thể theo chỉ dẫn
của các thông tin heuristic và sự tích lũy mùi, trong khi với xác suất 1-q0 các con
kiến sẽ thiên về hướng khám phá bằng công thức phân phối xác suất. Sự điều
chỉnh tham số q0 cho phép điều chỉnh mức độ khám phá và lựa chọn hoặc tập
trung tìm kiếm xung quanh tuyến đường tốt nhất tính từ đầu (best-so-far solution)
hoặc khám phá các tuyến đường khác
Cập nhật mùi toàn cục:(global pheromone trail update) : chỉ cập nhật sau khi
các con kiến đã xây dựng xong lời giải của mình và chỉ cho phép một con kiến tốt
nhất (tính đến thời điểm hiện tại) được phép cập nhật mùi sau mỗi vòng lặp. Công
thức:
Trong đó C
bs
là độ dài của tuyến đường đi tốt nhất tính đến thời điểm hiện tại.

Một điểm quan trọng trong quá trình cập nhật mùi của ACS là cả bay hơi và tăng
cường mùi đều chỉ thực hiện trên những cạnh thuộc đường đi tốt nhất (best-so-far
tour) không phải trên tất cả các cạnh như AS. Điều này là quan trọng vì độ phức
tạp tính toán của cập nhật mùi tại mỗi vòng lặp giảm từ O(n
2
) xuống O(n) (với n là
số đỉnh của bài toán). Tham số ρ ở đây vẫn là tham số bay hơi mùi như trên.
Trong thực nghiệm người ta đã cân nhắc việc sử dụng đường đi tốt nhất tại vòng
lặp hiện tại (iteration-best) để cập nhật mùi. Mặc dù với những thí nghiệm với bài
toán TSP có kích thước nhỏ thì sự khác biệt giữa việc sử dụng hai cách cập nhật
mùi trên là không nhiều, nhưng với những bài toán có kích thước lớn khoảng hơn
100 thành phố trở lên thì việc sử dụng tuyến đường best-so-far cho kết quả tốt hơn
nhiều.
Cập nhật mùi địa phương (local pheromone trail update) Một sự cải tiến thêm
trong quá trình update mùi của thuật toán ACS là trong khi xây dựng lời giải của
mình, mỗi con kiến sẽ cập nhật mùi ngay lập tức cho cạnh (i,j) mà nó vừa đi qua
theo công thức (gọi là công thức cập nhật mùi địa phương)
giá trị τ
o
là giá trị khởi tạo cho các vệt mùi. Nhiều thực nghiệm đã tiến hành cho
thấy 0.1 là giá trị tốt, còn một giá trị tốt cho τ
o
là 1/nC
nn
với n là số lượng các
11
thành phố và C
nn
là độ dài của một nearest-neighbor tour. Quá trình local update
làm cho lượng mùi trên mỗi cạnh giảm đi một ít sau mỗi lẫn con kiến đi qua một

cạnh, làm cho kiến ít bị thu hút bởi các cạnh đó hơn. Hay nói cách khác local
update làm tăng khả năng khám phá các đường đi chưa được đến thăm, và trong
thực nghiệm việc này không gây ra hiện tượng ứ đọng các vết mùi (stagnation)
như trong thuật toán MMAS. Tới đây ta có thêm một chú ý đáng quan trọng là
trong các thuật toán ở trên không có chuyện gì xảy ra cho dù các con kiến xây
dựng đường đi của chúng hoặc là song song hoặc là tuần tự. Tuy nhiên với ACS
thì khác bởi do quá trình local update , trong phần lớn các cài đặt thuật toán ACS
người ta đều để cho các con kiến xây dựng các đường đi song song. Cuối cùng
thuật toán ACS cũng như MMAS cho thấy là kết quả thu được tốt hơn hẳn so với
AS.
5. Hệ kiến đa mức
Thuật toán hệ kiến MMAS đã làm rõ được khả năng học tăng cường và tìm kiếm
ngẫu nhiên của đàn kiến nhưng chưa thể hiện được khả năng điều chỉnh hai ưu
điểm này của các thuật toán đàn kiến, ý tưởng ở đây xuất phát từ việc không giữ
nguyên giá trị của hai cận τ
min
f(τ
0
) và τ
max
f(τ
2
) và thay đổi nó trong các vòng lặp
chạy để điều khiển sự học tăng cường và tìm kiếm ngẫu nhiên bằng cách tăng dần
cận τ
2
sau mỗi bước lặp. Lúc đó, quy tắc cập nhật mùi được thực hiện như sau
Cập nhật mùi online : một con kiến đang ở đỉnh i và đi đến đỉnh j thì cạnh (i, j)
được cập nhật mùi như sau
Cập nhật mùi offline : sau khi tất cả các con kiến tìm ra hành trình của mình thì

các cạnh thuộc hành trình của con kiến tốt nhất (i-best hoặc g-best) sẽ được cập
nhật mùi theo công thức như sau
Ban đầu các cạnh có cường độ mùi ijf được khởi tạo bằng 0f, trong quá trình chạy
hai cận τ
1
và τ
2
sẽ được điều chỉnh, khi τ
1
được tăng lên sẽ tiết kiệm được quá
trình bay hơi, còn τ
1
và τ
2
sẽ được tăng lên theo tỷ lệ điều khiển quá trình học tăng
cường và tìm kiếm ngẫu nhiên. Quá trình học tăng cường sẽ thực hiện khi τ
1
và τ
2

xích ra xa nhau còn ngược lại sẽ là quá trình tìm kiếm ngẫu nhiên, sở dĩ có được
điều này là do theo qui tắc cập nhật mùi thì các cạnh có con kiến đi qua sẽ tiến về
τ
1
còn các cạnh thuộc hành trình của con kiến tốt nhất sẽ tiến về τ
2
, và theo cách
cập nhật mùi này thì không cần quá trình bay hơi nữa vì trong mỗi vòng lặp hai
cận điều khiển được tăng lên như vậy các cạnh ít không thay đổi mà các cạnh
thuộc hành trình của con kiến hoặc các cạnh thuộc hành trình của con kiến tốt nhất

tiến về hai cận đó cho nên coi như là các cạnh ít sử dụng bị bay hơi. Ý tưởng thì
12
cải tiến này là rất hay nhưng lại cực kỳ gây khó khăn cho người làm thực nghiệm
khi phải điều chỉnh tỷ lệ thích hợp của việc tăng hay giảm tỷ lệ giữa τ
1
và τ
2
III. Tài liệu tham khảo
[1] D.A. Alexandrov and Y .A. Kochetov . The behavior of the ant colony
algorithm for the set covering problem. In K. Inderfurth, G. Schw ¨ odiauer,
W. Domschke, F . Juhnke, P . Kleinschmidt, and G. W¨ ascher, editors, Operations
Research Proceedings 1999, pages 255–260. Springer V erlag, 2000.
[2] A. Bauer, B. Bullnheimer, R. F . Hartl, and C. Strauss. An ant colony
optimization approach for the single machine total tardiness problem. In
Proceedings of the 1999 Congress on Evolutionary Computation (CEC’99), pages
1445–1450. IEEE Press, Piscataway , NJ, 1999.
[3] R. Beckers, J L. Deneubourg, and S. Goss. Modulation of trail laying in
the ant Lasius niger (hymenoptera: Formicidae) and its role in the collective
selection of a food source. Journal of Insect Behavior, 6(6):751–759, 1993.
[4] R. Bellman, A. O. Esogbue, and I. Nabeshima. Mathematical Aspects of
Scheduling and Applications. Pergamon Press, New Y ork, NJ, 1982.
[5] D. Bertsekas. Network Optimization: Continuous and Discrete Models.
Athena Scientific, Belmont, MA, 1998.
13