TRƯỜNG ………………….
KHOA……………………….
Báo cáo tốt nghiệp
Đề tài:
PHƯƠNG PHÁP TỐI ƯU HOÁ ĐÀN KIẾN TÓM TẮT
Phương pháp tối ưu hóa đàn kiến (Ant Colony Optimization – ACO) là một
phương pháp mới mà ngày nay người ta rất quan tâm vì những hiệu quả nổi trội của nó
1.4.5. Điều chỉnh giữa sự học tăng cường và sự khám phá 23
1.4.6. Sử dụng giới hạn danh sách láng giềng 24
1.5. Các ứng dụng của ACO 25
CHƯƠNG 2. GIỚI THIỆU BÀI TOÁN DTSP 26
2.1. Bài toán DTSP 26
2.2. Các phương pháp giải bài toán DTSP 26
CHƯƠNG 3. SỬ DỤNG THUẬT TOÁN AS ĐỂ GIẢI QUYẾT BÀI TOÁN DTSP
28
3.1. Phân tích bài toán 28
3.2. Cải tiến AS cho phù hợp 29
CHƯƠNG 4. THỰC NGHIỆM VÀ ĐÁNH GIÁ 31
4.1. Thực nghiệm trên tsplib eil51 32
4.2. Nhận xét 34
PHẦN 5. KẾT LUẬN 37
THAM KHẢO 38
BẢNG TỪ VIẾT TẮT
Hiện nay có rất nhiều bài báo, luận văn, cũng như các công trình nghiên cứu đề
cập đến vấn đề tối ưu tổ hợp. Nhiều phương pháp mới mẻ đã được đưa ra và đạt hiệu
quả cao. Tuy nhiên phần lớn các bài toán tối ưu tổ hợp được giải từ trước tới nay đều
là các bài toán tĩnh. So với bài toán tĩnh thì bài toán động phức tạp hơn và ứng dụng
của nó trong thực tế là nhiều hơn. Chẳng hạn các ứng dụng trong định tuyến các gói
tin trên mạng internet, trong các tổng đài điện thoại. Một trong những cách tiếp cận có
hiệu quả đối với bài toán tối ưu tổ hợp tĩnh đó là phương pháp tối ưu hóa đàn kiến (Ant
Colony Optimization- ACO). ACO là một phương pháp metaheuristic mới và đang
được nhiều người quan tâm. Thuật toán ACO đầu tiên (1991) đã mang lại nhiều ý
tưởng và cảm hứng với mục đích cải tiến các thuật toán ACO để có thể áp dụng nó cho
nhiều bài toán khác nhau.
Luận văn này trình bày một cách khái quát về các thuật toán ACO và kiểm chứng
một phương pháp áp dụng ACO việc giải quyết bài toán ngươi chào hàng động
(Dynamic Travelling Salesman Problem- DTSP) một dạng bài toán tối ưu tổ hợp
động. DTSP thực chất là mở rộng của bài toán người chòa hàng (Travelling Salesman
Problem - TSP) nổi tiếng. Đồng thời luận văn cũng chỉ ra nhược điểm của thuật toán
và đề xuất một cải tiến cho thuật toán nhằm nâng cao hiệu quả khi phải giải quyết bài
toán có kích thước lớn. Các kết quả thực nghiệm sẽ được đưa ra làm rõ cho cho hiệu
quả của cải tiến thuật toán.
Luận văn gồm có 5 chương.
Chương 1 giới thiệu phương pháp tối ưu hóa đàn kiến: quá trình phát triển, các thuật
toán ACO áp dụng cho bài toán người chào hàng (Travelling Salesman Problem -
TSP), và một số ứng dụng của ACO.
Chương 2 luận văn giới thiệu về bài toán DTSP và các phương pháp để giải bài toán
này.
Chương 3 luận văn đề cập đến một phương pháp sử dụng thuật toán Hệ kiến (Ant
System - AS) là một thuật toán trong lớp các thuật toán ACO, để giải quyết bài toán
DTSP, chương này cũng đề cập đến một điều chỉnh thuật toán được đề xuất để cải tiến
hiệu quả thuật toán.
2
1.1. Giới thiệu
Phương pháp tối ưu hóa đàn kiến (Ant Colony Optimization - ACO) là một mô
hình để thiết kế các thuật toán metaheuristic cho việc giải quyết bài toán tối ưu hóa tổ
hợp (Combinatorial optimization problems).
Bài toán tối ưu hóa tổ hợp
Bài toán tối ưu hóa tổ hợp được định nghĩa như sau:
Cho một tập C = {c
1
, c
2
, c
n
}.
Một tập con S của C là một phương án để giải quyết bài toán.
Tập F
2
C
là tập tất cả các phương án có thể, vì thế S là một phương án khả thi
nếu S
F.
Một hàm giá trị z xác định như sau, z : 2
C
R, mục tiêu là tìm phương án khả
thi S* có giá trị nhỏ nhất: S*
F và z(S*)
metaheuristic là khung thuật toán tổng quát có thể áp dụng cho nhiều loại bài toán tối
ưu khác nhau tất nhiên là cùng với những điều chỉnh nho nhỏ để làm cho chúng trở
nên phù hợp với các bài toán cụ thể.
Tối ưu hóa đàn kiến (ACO)
ACO là một metaheuristic có thể áp dụng để giải quyết rất nhiều bài toán tối ưu
tổ hợp, thuật toán đầu tiên đã được phân loại trong lớp các thuật toán ACO được đưa ra
năm 1991(tham khảo [2], [3]) và kể từ đó nguyên tắc căn bản đã có nhiều thay đổi
khác nhau. Đặc điểm cơ bản của các thuật toán ACO là sự kết hợp giữa thông tin
heuristic dựa vào đặc điểm của phương án có nhiều hứa hẹn và thông tin nhận được
qua các phương án tốt đã tìm được ở bước trước. Các thuật toán metaheuristic là các
thuật toán để tránh hiện tượng tối ưu cục bộ, nó điều chỉnh các heuristic: hoặc là
heuristic tạo ra bắt đầu từ một phương án trống sau đó thêm các thành phần để nó trở
5
thành phương án hoàn chỉnh và tốt, hoặc là heuristic tìm kiếm cục bộ bắt đầu từ một
phương án hoàn chỉnh sau đó thay đổi lại một số thành phần để đạt được một phương
án tốt hơn.
ACO (tham khảo [5]) bao gồm một lớp các thuật toán trong đó thuật toán đầu tiên
là Ant System (AS) được đề xuất bởi Colorni, Dorigo và Maniezzo (tham khảo [2], [3],
[4]). Ý tưởng chính làm cơ sở của thuật toán là lấy cảm hứng từ hành vi của đàn kiến
trong tự nhiên, đó là quá trình tìm kiếm các lời giải song song dựa vào các dữ liệu cục
bộ và dựa vào cấu trúc động chứa các thông tin thu được qua các bược giải trước. Sự
tổng hợp các hành vi nổi trội từ quá trình giao tiếp giữa các phần tử trong quá trình tìm
kiếm của chúng thực sự là có hiệu quả trong việc giải quyết các bài toán tối ưu hóa tổ
hợp. Các con kiến đã giao tiếp với nhau như thế nào và làm sao để chúng lựa chọn
được con đường tốt hơn để đi. Qua các nghiên cứu người ta biết được rằng các con
kiến trong tự nhiên để lại một vết hóa chất (pheromone trail), chúng có khả năng ứ
đọng, bay hơi và có thể nhận biết bởi các con kiến khác, các vệt mùi chính là phương
tiện giao tiếp báo cho các con kiến khác thông tin về đường đi đó một cách gián tiếp.
thuật toán AS vẫn còn thua kém các thuật toán tốt nhất trong việc giải quyết bài toán
trên, tuy nhiên ý tưởng của nó thực sự là mới mẻ và tỏ ra có triển vọng. Về sau đã có
rất nhiều cải tiến của thuật toán này do chính Dorigo đề xuất, cũng như rất nhiều các
thuật toán ACO khác đều dựa trên ý tưởng của thuật toán AS song đã khắc phục được
một số nhược điểm của thuật toán này. Có thể kể tên 2 cải tiến nổi trội nhất của thuật
toán AS là thuật toán ACS và thuật toán MMAS mà ta sẽ trình bày sau.
Bảng 1. Một số các thuật toán ACO theo thứ tự xuất hiện
ACO algorithms Tác giả
Ant System Dorigo Maniezzo, & Colorni (1991)
Elitist AS Dorigo (1992); Dorigo, Maniezzo, &
Colorni (1996)
Ant-Q Gambardella & Dorigo (1995); Dorigo &
Gambardella (1996)
Ant Colony System Dorigo & Gambardella (1996)
Max-Min AS Stutzle & Hoos (1996, 2000); Stutzle (1999)
Rank-based AS Bullnheimer, Hartl, & Strauss (1997, 1999)
ANTS Maniezzo (1999)
7
Hyper-cube AS Blum, Roli, & Dorigo (2001); Blum &
Dorigo (2004)
Thí nghiệm cầu đôi
Hành vi tìm thức ăn của các con kiến là dựa trên giao tiếp gián tiếp qua các vết
mùi (chất pheromone). Khi di chuyển từ nguồn thức ăn trở về tổ các con kiến để lại
mùi trên mặt đất, các con kiến có thể cảm nhận được mùi và chúng có khuynh hướng
chọn theo xác suất các con đường mà được đánh dấu tập trung nhiều mùi nhất.
Một số nghiên cứu để tìm hiểu hành vi của loài kiến đã được tiến hành mà một
trong những thí nghiệm nổi tiếng nhất là thí nghiệm của Deneubourg và các cộng sự
chọn ngẫu nhiên với cùng một xác suất bất kì nhánh nào trong 2 nhánh. Còn nữa, vì
các con kiến để lại mùi khi di chuyển, nên nhánh nào có số lượng lớn hơn các con kiến
thì sẽ có lượng mùi để lại lớn hơn. Đồng thời với lượng mùi lớn hơn thì nhánh đó cũng
thu hút nhiều hơn các con kiến chọn nó. Và cuối cùng các con kiến sẽ gần như chỉ kéo
về một nhánh duy nhất.
Quá trình trên là một quá trình nội bộ, tự vận động là một ví dụ của hành vi tự tổ
chức (self-organizing) của loài kiến. Quá trình lựa chọn một đường đi duy nhất của
loài kiến thể hiện hành vi mang tính tập thể của chúng dựa trên cơ sở các tương tác cục
bộ giữa các con kiến đơn lẻ trong đàn. Đây cũng là một ví dụ của loại giao tiếp
stigmergy: các con kiến thay đổi hành động của chúng sử dụng giao tiếp gián tiếp bằng
cách thay đổi môi trường trong khi di chuyển. Thuật ngữ stigmergy được đưa ra bởi
9
Grasse để mô tả hình thức giao tiếp gián tiếp bằng cách thay đổi môi trường cái mà
ông đã quan sát được trong khi nghiên cứu sự phân cấp trong xã hội của 2 loài mối.
Trong thí nghiệm thứ 2 tỉ số giữa độ dài của 2 nhánh được thay đổi r=2. Trong
trường hợp này, ở phần lớn các lần thử thì sau 1 thời gian tất cả các con kiến chỉ chọn
nhánh ngắn hơn (xem sơ đồ 2b). Cũng như trong thí nghiệm đầu các con kiến sẽ phải
lựa chọn một trong 2 nhánh để đi. Khi bắt đầu thì cả 2 nhánh đối với các con kiến là
như nhau và chúng sẽ chọn ngẫu nhiên. Vì thế xét trung bình thì một nửa số kiến sẽ
chọn nhánh ngắn và nửa còn lại chọn nhánh dài. Ở thí nghiệm này ta sẽ thấy một sự
khác biệt lớn so với thí nghiệm trước. Vì một nhánh ngắn hơn nhánh kia do đó các con
kiến chọn nhánh ngắn hơn sẽ đến nguồn thức ăn trước và chúng sẽ bắt đầu trở về tổ.
Tuy nhiên chúng sẽ phải chọn giữa nhánh ngắn và nhánh dài, mức nồng độ mùi cao
hơn ở nhánh ngắn sẽ làm cho quyết định của kiến lệch về phía chúng. Vì thế mùi sẽ
bắt đầu tích lũy nhanh hơn trên nhánh ngắn, cuối cùng hầu hết các con kiến sẽ chọn
nhánh này theo như sự tương tác giữa các con kiến được mô tả ở thí nghiệm trước.
Điều thú vị quan sát được là thậm chí khi một nhánh dài gấp đôi nhánh kia thì
không phải tất cả các con kiến sử dụng nhánh ngắn hơn mà có một lượng nhỏ kiến
chọn nhánh dài hơn. Đây là cách để kiến có thể khám phá được những con đường
Bài toán TSP có thể phát biểu dưới dạng đồ thị như sau: 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ố d
ij
để 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
d
ij
= d
ji
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 d
ij
≠ d
ji
. Đố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.
Hình sau đây (hình 2.a và 2.b) đưa ra 2 ví dụ về bài toán TSP, được lấy từ
TSPLIB website (xem [14]).
11
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/ d
ij
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:
(1.1)
trong đó cường độ vệt mùi τ
ij
(t) và thông tin heuristic η
ij
ta đã giới thiệu ở trên.
ngược lại
k
i
Nj
13
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.
N
i
k
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
Lji
),(
(1.2)
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
14
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:
)()()1(
1
ttt
k
ij
m
k
ijij
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 đượ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ả.
15
Vì thế, thực tế là các nghiên cứu về ACO ngày nay tập trung vào việc làm thế nào
để cải tiến AS.
1.3.3. 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.
một lượng theo công thức :
best
ijijij
(1.5)
Với
best
best
ij
C
1
, với C
best
hoặc là độ dài của tuyến đường tốt nhất tại vòng
lặp hiện tại, hoặc là độ dài của tuyến đường tốt nhất từ khi bắt đầu thuật toán.
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 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 (τ
17
1.3.4. Ant Colony System (ACS)
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:
elseJ
qqif
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. 18 Cập nhật mùi toàn cục:(global pheromone trail update)
Cập nhật mùi toàn cục: 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:
bs
ijijij
)1(
(1.7)
Với
bs
bs
ij
C
1
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
<1) và
0
là hai tham số
19
giá trị
0
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 cho
, còn một giá trị
tốt cho
0
là 1/nC
nn
với n là số lượng các 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
1
)1(
ijij
(13) 20
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 :
2
)1(
ijij
(14)
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 2 qui tắc cập
nhật mùi (13) và (14) 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ì 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
.
1.4. Các nguyên tắc khi áp dụng tối ưu đàn kiến
Các chú ý sau đây làm tăng khả năng cho thuật toán ACO khi áp dụng vào các
bài toán khác nhau. Có nhiều vấn đề cần quan tâm khi ta áp dụng các thuật toán ACO
để giải quyết một bài toán, chẳng hạn lựa chọn số lượng kiến, lựa chọn các tham số
khác, xác định các vết mùi, xác định các thông tin heuristic và sử dụng tìm kết hợp
toán này ta chọn định nghĩa các vệt mùi
ij
là khả năng đường đi từ thành phố i đến
thành phố j có thuộc đường đi các con kiến lựa chọn hay không, tức là mức độ ưu tiên
của đoạn đường này.
Việc định nghĩa các vệt mùi ảnh hưởng rất nhiều đến hiệu quả của thuật toán, nếu
đưa ra một lựa chọn không tốt thì thuật toán có thể trở nên rất là xấu. Với phần nhiều
các bài toán ứng dụng của ACO các lựa chọn dựa trên trực quan mà người ta nhận thấy
ngay thường đưa lại hiệu quả tốt.
Copyright: Tài liệu đại học ©