Luận văn Phương pháp tối ưu hoá đàn kiến
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ó
so với các phuoeng pháp khác trong giải quyết các bài toán tối ưu hóa tổ hợp
(Combinatorial optimization problems).
Khóa luận này trình bày một cách khái quát về phương pháp tối ưu hóa đàn kiến
(Ant Colony Optimization), và trình bày một phương pháp áp dụng của thuật toán tối
ưu hóa đàn kiến cho bài toán người chào hàng động (Dynamic Travelling Salesman
Problem - DTSP) đã được công bố.
Khóa luận đã cài đặt và kiểm chứng hiệu quả của thuật toán đồng thời đưa ra một
cải tiến đối với thuật toán để nâng cao hiệu quả trong trường hợp bài toán đầu vào có
kích thước lớn.
MỤC LỤC
TÓM TẮT....................................................................................................................
BẢNG TỪ VIẾT TẮT .................................................................................................
MỞ ĐẦU ....................................................................................................................1
CHƯƠNG 1. GIỚI THIỆU PHƯƠNG PHÁP ACO.................................................3
1.1. Giới thiệu ..........................................................................................................3
1.2. Quá trình phát triển............................................................................................6
1.3. Một số thuật toán ACO áp dụng cho bài toán TSP .............................................9
1.3.1. Bài toán TSP.............................................................................................10
1.3.2. Ant System (AS).........................................................................................12
1.3.3. Max-Min Ant System (MMAS)...................................................................15
1.3.4. Ant Colony System (ACS).........................................................................17
1.3.5. Hệ kiến đa mức (xem [15]) .......................................................................19
1.4. Các nguyên tắc khi áp dụng tối ưu đàn kiến.....................................................20
1.4.2. Xác định các vệt mùi.................................................................................21
1.4.3. Các thông tin heuristic..............................................................................22
1.4.4. Kết hợp tìm kiếm địa phương....................................................................22
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
STT Từ viết tắt
Từ hoặc cụm từ
Ant Colony Optimization
(Tối ưu hóa đàn kiến)
Ant System
1
ACO
AS
2
(Hệ kiến AS)
Ant Colony System
(Hệ kiến ACS)
3
ACS
MMAS
MLAS
TSP
Max-Min Ant System
(Hệ kiến MMAS)
4
Multi-level Ant System
(Hệ kiến đa mức MLAS)
Travelling Salesman Problem
(Bài toán người chào hàng)
Job shop scheduling
(Bài toán lập lịch sản xuất)
6
9
10
JSS
11
12
g-best
i-best
global-best
iteration-best
MỞ ĐẦU
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.
1
Chương 4 là phần cài đặt thực nghiệm kiểm chứng đánh giá thuật toán cũng như đánh
giá hiệu quả của cải tiến được đề xuất. Ở đây luận văn sử dụng thư viện TSP chuẩn
được cung cấp trên mạng để làm đầu vào.
Chương 5 là phần kết luận cuối cùng.
2
CHƯƠNG 1. GIỚI THIỆU PHƯƠNG PHÁP ACO
Bài toán tối ưu hóa tổ hợp là bài toán hấp dẫn và thú vị bởi vì phần lớn chúng
đều dễ để hình dung nhưng khó mà tìm ra lời giải cho chúng. Nhiều bài toán tối ưu tổ
hợp là các bài toán NP-khó và chúng không thể giải được trong thời gian đa thức. Trên
thực tế người ta thường giải quyết các bài toán này bằng các phương pháp xấp xỉ,
chúng có nghiệm gần tối ưu và thời gian chạy khá ngắn. Các thuật toán thuộc lại này
tạm gọi là các thuật toán heuristic , chúng được sử ụng để giải quyết các bài toán cụ
thể . Mở rộng của chúng là các thuật toán metaheuristic có thể giải quyết được cả một
lớp các bài toán rộng lớn. ACO là một phương pháp theo hướng tiếp cận như thế.
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 = {c1, c2, ...cn}.
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 2C 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 : 2C 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*) z(S), S F.
Nhiều bài toán tối ưu quan trọng trong lý thuyết và thực tế là các bài toán thuộc loại
tối ưu hóa tổ hợp. Ví dụ, bài toán tìm đường đi ngắn nhất, cũng như nhiều bài toán có
ý nghĩa quan trọng khác trên thực tế như bài toán người chào hàng, bài toán phân công
lao động, bài toán định tuyến mạng, bài toán lập lịch công việc, bài toán lập lịch bay
cho các hãng hàng không, và nhiều bài toán khác nữa.
3
Một bài toán tối ưu hóa tổ hợp hoặc thuộc loại tìm giá trị nhỏ nhất hoặc là thuộc
loại bài toán tìm giá trị lớn nhất. Các phương pháp giải loại bài toán này phần lớn là
các phương pháp tìm kiếm heuristic (các thuật toán metaheuristic). Sau đây là các
thuật toán đã được sử dụng:
Thuật toán tìm kiếm cục bộ (Local search)
Thuật toán mô phỏng luyện kim (Simulated annealing)
Thuật toán GRASP(Greedy Randomized Adaptive Search Procedure)
Thuật toán bầy đàn (Swarm intelligence)
Thuật toán tìm kiếm theo bảng(Tabu search)
Thuật toán di truyền (Genetic algorithms)
Thuật toán tối ưu hóa đàn kiến (Ant colony optimization)
Metaheuristic
Metaheuristic là một tập các lý thuyết thuật toán được dùng để xác định các
phương pháp heuristic sao cho nó phù hợp với một lớp bài toán rộng lớn. Nói cách
khác metaheuristic có thể được xem như là một phương pháp heuristic có tính tổng
quát, nó được thiết kế để hướng dẫn các heuristic trong các bài toán cơ bản hướng về
những miền hứa hẹn trong không gian tìm kiếm các phương án tối ưu. Một
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ở
4
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.
Các con kiến sẽ lựa chọn đường đi nào có cường độ mùi lớn nhất tại thời điểm lựa
chọn để đi, nhờ cách giao tiếp mang tính gián tiếp và cộng đồng này mà đàn kiến trong
tự nhiên tìm được đường đi ngắn nhất.
Dựa vào ý tưởng trên, các thuật toán ACO sử dụng thông tin heuristic (chính là
thông tin có được do các dữ liệu đầu vào của bài toán) kết hợp thông tin từ các vết mùi
của các con kiến nhân tạo (artificial ant) để giải các bài toán tối ưu tổ hợp khó bằng
cách đưa về bài toán tìm đường đi tối ưu trên đồ thị cấu trúc tương ứng được xây dựng
từ đặc điểm của từng bài toán. Mỗi con kiến nhân tạo xây dựng lời giải của chúng dựa
vào luật phân phối xác suất của các vết mùi nhân tạo và các thông tin heuristic.
Lược đồ thuật toán ACO tổng quát áp dụng cho bài toán tối ưu tổ hợp tĩnh:
procedure ACOMetaheuristicStatic
Set parameters, initialize pheromone trails
while (termination condition not met) do
ConstructAntsSolutions
ApplyLocalSearch (optional)
UpdatePheromones
end-while
5
end-procedure
Như đã nhận định ở trên ACO thực chất là tìm kiếm ngẫu nhiên dựa vào thông tin
heuristic kết hợp với thông tin học tăng cường. So với các thuật toán heuristic cổ điển
ACO mở rộng thêm quá trình học tăng cường, các con kiến tỏ ra thích nghi hơn với
môi trường dựa vào các vệt mùi tích lũy trên các cạnh đồ thị.
1.2. Quá trình phát triển
Thuật toán Ant System (AS) là thuật toán đầu tiên trong lớp các thuật toán ACO
được đề xuất bởi Dorigo trong luận án tiến sỹ của ông năm 1991(tham khảo [2], [3]).
Thuật toán AS hướng đến giải quyết bài toán tìm đường đi tối ưu trong đồ thị. Mặc dù
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
Ant System
Tác giả
Dorigo Maniezzo, & Colorni (1991)
Elitist AS
Dorigo (1992); Dorigo, Maniezzo, &
Colorni (1996)
Ant-Q
Gambardella & Dorigo (1995); Dorigo &
Gambardella (1996)
Ant Colony System
Max-Min AS
Rank-based AS
ANTS
Dorigo & Gambardella (1996)
Stutzle & Hoos (1996, 2000); Stutzle (1999)
Bullnheimer, Hartl, & Strauss (1997, 1999)
Maniezzo (1999)
6
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ự
của ông năm 1989 (xem [7]), thí nghiệm này là cơ sở lý thuyết đầu tiên và cũng tạo ra
ý tưởng cho thuật toán ACO mà Dorigo đưa ra sau này. Ông sử dụng một cầu đôi nối
giữa một cái tổ của loài kiến Argentine là I. humilis với nguồn thức ăn. Ông đã thực
hiện thí nghiệm nhiều lần và thay đổi tỉ số r giữa độ dài của 2 nhánh cầu.
Hình 1. a – cầu đôi với 2 nhánh bằng nhau, b – cầu đôi với tỉ số các nhánh là 2
7
Biểu đồ 1. a – tỉ lệ các con kiến chọn 1 nhánh trong các lần thí nghiệm với trường
hợp 2 nhánh bằng nhau.
b – tỉ lệ các con kiến chọn 1 nhánh ngắn các lần thí nghiệm với trường
hợp 1 nhánh dài gấp đôi nhánh kia.
Trong thí nghiệm đầu tiên hai nhánh cầu có chiều dài bằng nhau (xem hình 1a) .
Khi bắt đầu các con kiến di chuyển tự dâo giữa tổ và nguồn thức ăn, người ta quan sát
tỉ lệ phần trăm các con kiến chọn các nhánh trong 2 nhánh qua thời gian. Kết quả thu
được như sau (xem đồ thị 1a), cho dù giai đoạn khởi đầu các lựa chọn ngẫu nhiên xảy
ra, song cuối cùng thì các con kiến đều hầu như chỉ đi qua một nhánh. Kết quả này có
thể được giải thích như sau. Khi bắt đầu một lần thử không có vệt mùi nào trên cả 2
nhánh cầu, sau đó các con kiến sẽ không có cái gì đề làm căn cứ lựa chọn và chú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
8
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
mới.
1.3. Một số thuật toán ACO áp dụng cho bài toán TSP
Bài toán Travelling Salesman Problem (TSP) là bài toán tối ưu tổ hợp kinh điển
và nổi tiếng. Bài toán này đóng một vai trò quan trọng trong nghiên cứu các thuật toán
ACO. TSP được chọn làm bài toán tối ưu tổ hợp điển hình và để áp dụng các thuật
toán ACO bởi vì: nó là một bài toán NP-khó và thường nảy sinh nhiều trong các ứng
dụng, dễ dàng áp dụng các thuật toán ACO ; nó cũng là một bài toán rất trực quan, dễ
hiểu không như nhiều bài toán NP-khó khác; các bước thực thi của thuật toán ACO
trên bài toán TSP là dễ hình dung, không có nhiều khó khăn về mặt kỹ thuật. Phần này
ta sẽ giới thiệu chi tiết về các thuật toán AS, MMAS, ACS thông qua việc ứng dụng nó
vào giải quyết bài toán TSP.
9
1.3.1. Bài toán TSP
Nội dung bài toán như sau: Một người chào hàng xuất phát từ thành phố của anh
ta, anh ta muốn tìm một đường đi ngắn nhất đi qua tất cả các thành phố của khách
hàng mỗi thành phố đúng một lần sau đó trở về thành phố ban đầu. TSP được phát
biểu vào thế kỷ 17 bởi hai nhà toán học vương quốc Anh là Sir William Rowan
Hamilton và Thomas Penyngton Kirkman, và được ghi trong cuốn gsiáo trình Lý
thuyết đồ thị nổi tiếng của Oxford. Nó nhanh chóng trở thành bài toán khó thách thức
toàn thế giới bởi độ phức tạp thuật toán tăng theo hàm số mũ (trong chuyên ngành
thuật toán người ta còn gọi chúng là những bài toán NP-khó). Người ta bắt đầu thử và
công bố các kết quả giải bài toán này trên máy tính từ năm 1954 (49 đỉnh), cho đến
năm 2004 bài toán giải được với số đỉnh lên tới 24.978, và dự báo sẽ còn tiếp tục tăng
cao nữa.
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ố 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.
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]).
10
Hình 2.a – Thể hiện các đỉnh trong thư viện TSP att532, tương ứng với 532
thành phố của Mỹ. Hình 2.b – Thể hiện các đỉnh trong TSPLIB pcb1173 biểu diễn
1173 lỗ trên một bảng mạch in.
Bảng 2. Một số thuật toán ACO và khả năng giải quyết bài toán TSP
ACO algorithms
Ant System
TSP
Yes
Yes
Yes
Yes
Yes
Yes
No
Elitist AS
Ant-Q
Ant Colony System
Max-Min AS
Rank-based AS
ANTS
Hyper-cube AS
No
11
1.3.2. Ant System (AS)
Thuật toán Ant System (AS) như đã giới thiệu là thuật toán đầu tiên trong lớp các thuật
toán ACO được đề xuất bởi Dorigo trong luận án tiến sỹ của ông năm 1991(tham khảo
[2], [3]). AS và cũng như nhiều thuật toán ACO cải tiến từ AS đều chọn TSP làm bài
toán thực nghiệm đầu tiên.
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:
ij (t) ij
k
j N i
Pk (t)
il (t) il
k
lN
ij
(1.1)
i
0
ngược lại
trong đó cường độ vệt mùi τij(t) và thông tin heuristic ηij ta đã giới thiệu ở trên.
12
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 Nik 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ớ Mk 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 Nik trong
công thức xác suất (1.1) ở trên. Mk 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ả 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:
ij (t 1) (1 )ij (t)
(i, j)L
(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
13
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:
m
(t 1) (t)
ikj (t)
(1.3)
(1.4)
ij
ij
k1
1
Ck
trong đó
nếu (i,j) thuộc Tk và ngược lại
k (t)
ij
0
Ck là độ dài của tuyến đường Tk được xây dựng bởi con kiến k. Với công thức (1.4),
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 đượ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ả.
14
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.
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
(xem công thức 1.2).
15
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 :
best
ij
ij ij
(1.5)
best
ij
, với Cbest hoặc là độ dài của tuyến đường tốt nhất tại vòng
1
Với
Cbest
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 (τ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 pij 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 [pmin, pmax].
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.
16
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:
argmax {il[il ] } if q q0
lNik
j
(1.6)
J
else
trong đó q là giá trị ngẫu nhiên phân phối đều trong đoạn [0, 1]
q0 (0 q0 1) là một tham số
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.
17
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
ij
ij (1 )ij
(1.7)
bs
1
Với
Cbs
ij
Trong đó Cbs 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(n2) 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)
ij (1)ij 0
(1.8)
với ( 0< <1) và 0 là hai tham số
18
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/nCnn với n là số lượng các thành phố và Cnn 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.
1.3.5. Hệ kiến đa mức (xem [15])
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 (0 ) và max ( 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 :
ij ij (1 )1
(13)
19
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 :
ij ij (1 )2
(14)
Ban đầu các cạnh có cường độ mùi
được khởi tạo bằng 0 , trong quá trình
ij
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 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
kiếm địa phương...
20
1.4.1. Số lượng kiến
Số lượng kiến trong các bài toán khác nhau cần có những điều chỉnh khác nhau.
Nếu số lượng kiến quá nhiều thì quá trình tìm kiếm sẽ mất nhiều thời gian tính toán,
đồng thời chưa chắc đã tăng hiệu quả tìm kiếm lên. Tất nhiên là nếu số lượng kiến quá
ít thì quá trình tìm kiếm sẽ rất khó khăn bởi vì với số ít các con kiến thì ít các đường đi
được chọn tại mỗi vòng lặp và do đó, sự tích lũy các thông tin mùi là mất nhiều thời
gian và số tuyến đường mà các con kiến lựa chọn cũng trở nên đơn điệu vì có quá ít
các con kiến.
Số lượng kiến phụ thuộc vào thuật toán cài đặt và phụ thuộc vào kích thước của
bài toán cần giải quyết. Chẳng hạn với thuật toán AS người ta thường chọn số kiến là
bằng số đỉnh. Với thuật toán MMAS thì với những bài toán nhỏ thì người ta chỉ chọn từ
2 – 10 con kiến, còn với những bài toán có kích thước khoảng vài trăm đỉnh trở lên thì
người ta tăng dần số đỉnh lên.
1.4.2. Xác định các vệt mùi
Quá trình học tăng cường có tác dụng nâng cao hiệu quả của thuật toán trong quá
trình các con kiến tìm kiếm lời giải. Một trong những điều quan trọng đầu tiên trong
việc áp dụng các thuật toán ACO là công việc xác định thông tin học tăng cường qua
các vệt mùi, nói cách khác là xác định thông tin mà vệt mùi biểu diễn.
Chẳng hạn, với bài toán TSP, vệt mùi ij giữa các cạnh có tác dụng biểu diễn sự
thích hợp của việc chọn thành phố j sau khi đã thăm thành phố i, nói cách khác nó là
một thông tin để thể hiện mối quan hệ giữa thành phố i và thành phố j. Cụ thể ở bài
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.
21
1.4.3. Các thông tin heuristic
Các thông tin heuristic là một trong các thông tin quan trọng trong các thuật
toán ACO. Các thông tin heuristic thể hiện mối quan hệ giữa các đỉnh và nó chính là
thông tin mà ta thu được từ dữ liệu đầu vào của bài toán, nó thể hiện các tri thức có
được từ bài toán. Nó được kết hợp với quá trình tìm kiếm địa phương để cải tiến lời
giải. Tìm kiếm địa phương cho phép có được những thông tin chi phí để cải tiến lời
giải theo cách trực tiếp hơn. Khi kết hợp các thuật toán ACO với phương pháp tìm
kiếm địa phương sẽ tìm ra được những lời giải tốt hơn cho những bài toán khó xây
dựng được những thông tin heuristic.
Trong các bài toán tĩnh, các thông tin heuristic sẽ chỉ cần tính một lần trước
khi bắt đầu thuật toán, ví dụ trong ứng dụng TSP người ta định nghĩa thông tin
heuristic dựa vào độ dài dij giữa các thành phố i và thành phố j, nó bằng nghịch đảo
độ dài này ij 1/ dij , tức là khoảng cách giữa các dỉnh càng nhỏ thì thông tin
heuristic giữa chúng càng lớn. Các thông tin heuristic tĩnh có các đăc điểm thuân lợi
sau : dễ tính toán, chỉ phải tính một lần trước khi bắt đầu thuật toán, và tại mỗi vòng
lặp của thuật toán ACO có thể tính trước một bảng các giá trị ij (t)[ij ] sẽ tiết kiệm
được đáng kể thời gian tính toán.
Trong trường hợp bài toán động, thông tin heuristic cần phải được tính tại mỗi
bước đi của con kiến bởi vì chúng phụ thuộc vào các lời giải thành phần được xây
dựng. Do đó quá trình này làm cho chi phí tính toán lớn nhưng có thể đạt được độ
chính xác cao trong tính toán các giá trị heuristic .
1.4.4. Kết hợp tìm kiếm địa phương
Việc sử dụng các thuật toán tìm kiếm địa phương là một yếu tố quyết định tính
hiệu quả cho các ứng dụng ACO. Tuy nhiên việc áp dụng các thuật toán tìm kiếm địa
phương vào các thuật toán ACO là không hề đơn giản.
Rất nhiều các ứng dụng của các bài toán tối ưu tổ hợp như TSP, bài toán phân
chia sản phẩm, hay bài toán định tuyến cho xe cộ, các thuật toán ACO đều cho ra kết
quả tốt khi kết hợp các thuật toán tìm kiếm địa phương. Các thuật toán địa phương
nhằm xác định ra một miền cục bộ trong lời giải hiện tại (thông qua các phép biến đổi,
22
xáo trộn láng giềng) và sau đó thực hiện tìm kiếm cụ bộ trong phạm vi nó định nghĩa
để có được lời giải tối ưu toàn cục. Các thuật toán tìm kiếm địa phương thường tìm ra
các lời giải tối ưu cục bộ và dùng những lời giải đó để cập nhật vệt mùi.
Người ta nhận thấy trong nhiều bài toán, quá trình lặp lại các tìm kiếm địa
phương ngay từ những lời giải ban đầu được sinh ra ngẫu nhiên không mang lại nhiều
hiệu quả lắm. Do đo quá trình sinh ra các lời giải ban đầu cho các thuật toán tìm kiếm
địa phương không mang lại các kết quả như ý và nó thực sự không phải là một nhiệm
vụ đơn giản.
Trên thực tế, khi kết hợp các thành phần của lời giải tối ưu cục bộ một cách ngẫu
nhiên người ta thu được những lời giải mới hứa hẹn hơn cho thuật toán tìm kiếm địa
phương. Bằng thực nghiệm, có thể thấy sự kết hợp của các lời giải tham lam thích nghi
theo xác suất với các thuật toán tìm kiếm địa phương có thể đạt được những kết quả
hơn cả.
1.4.5. Điều chỉnh giữa sự học tăng cường và sự khám phá
Các thuật toán metaheuristic muốn có hiệu quả tốt thì cần có sự điều chỉnh phù
hợp giữa việc sử dụng kinh nghiệm tìm kiếm với việc khám phá các không gian tìm
kiếm mới. Các thuật toán ACO điều chỉnh được sự cân bằng giữa chúng thông qua
qua việc điều chỉnh cập nhật các vệt mùi sao cho phù hợp.
Tác dụng của các vệt mùi là đưa ra một sự phân bố xác suất lựa chọn trên không
gian tìm kiếm, nó cho phép ta xác định được các phần nào trong không gian tìm kiếm
mà tập trung nhiều giải hơn, cũng tức là có nhiều khả năng cho lời giải tối ưu ở đó.
Khi đó nếu tập trung tìm kiếm trên các phần không gian này thì ta có quá trình học
tăng cường tức là chỉ tập trung tìm kiếm trên các lời giải tốt hay nói cách khác là trên
các cạnh có nhiều thông tin vệt mùi.
Để sử dụng kinh nghiệm tìm kiếm của các con kiến ta có thể sử dụng một thủ tục
kiểm tra hiệu suất của mỗi lời giải trong suốt quá trình cập nhật mùi. Một cách để tăng
khả năng học tăng cường trong quá trình xây dựng lời giải bằng cách áp dụng luật
chuyển trạng thái như trong thuật toán ACS, khi đó các con kiến sẽ tập trung nhiều hơn
vào các lời giải tốt ở bước trước hơn so với thuật toán AS. Mặt trái của quá trình này là
khả năng khám phá của các con kiến giảm đi vì chúng chỉ tập trung vào một phần nhỏ
của không gian tìm kiếm.
23
Để tăng khả năng khám phá cho các con kiến thì rõ ràng là ta cần mở rộng không
gian tìm kiếm lên bằng các phương pháp khác nhau. Quá trình này vừa có tác dụng
giảm bớt sự tập trung quá nhiều vào các lời giải được cho là tốt, vừa có tác dụng đưa
ra nhiều khả năng tìm kiếm cho các con kiến. Mở rộng không gian tìm kiếm trong
ACO chính là các thủ tục xây dựng lời giải ngẫu nhiên của các con kiến. Xem xét khi
thuật toán ACO không sử dụng thông tin heuristic (bằng cách đặt tham số 0 ).
Trong trường hợp này, quá trình cập nhật mùi sẽ gây ra sự thay đổi từ không gian tìm
kiếm mẫu cố định ban đầu thành một không gian mẫu khác và ở không gian này sự lựa
chọn các phương án chỉ phụ thuộc vào cường độ các vết mùi. Việc mở rộng không
gian tìm kiếm sẽ tốt hơn trong các vòng lặp ban đầu của thuật toán và sẽ giảm thiểu
được sự tính toán.
Để điều chỉnh sự tăng cường và khám phá người ta thường điều chỉnh các tham
số và , ảnh hưởng đến các vết mùi còn ảnh hưởng đến các thông tin
heuristic. MMAS sử dụng một phương pháp đó là giới hạn cận dưới của các cường độ
vệt mùi sao khi đó không gian tìm kiếm được điều chỉnh không trở nên thu hẹp quá
mức. Khi mà bài toán đi vào bế tắc MMAS tức là với không gian tìm kiếm hiện tại
không thể phát triển thêm lời giải thi nó khởi tạo lại các vệt mùi đồng nghĩa với việc
tăng trở lại không gian tìm kiếm. Việc khởi tạo lại các vệt mùi kết hợp với các cải tiến
lựa chọn cập nhật vệt mùi giúp MMAS tìm kiếm trên nhiều vùng không gian khác
nhau.
1.4.6. Sử dụng giới hạn danh sách láng giềng
Khi mà bài toán phải giải quyết có kích thước lớn thì đồng thời tại mỗi đỉnh các
con kiến cũng phải lựa chọn giữa một tập rất lớn các láng giềng của nó. Đây là vấn đề
lớn của thuật toán ACO vì nó làm tăng thời gian, và không gian tìm kiếm. Các con
kiến phải tìm kiếm trên một không gian khổng lồ các phương án. Mong muốn của ta là
giảm được không gian tìm kiếm này xuống càng nhỏ càng tốt nhưng vẫn đảm bảo cho
hiệu suất của thuật toán ở mức cao.
Để có thể giải quyết vấn đề nêu ta có thể giới hạn lại danh sách các đỉnh có thể
lựa chọn tạm gọi là danh sách các láng giềng gần nhất (nearest neighbour). Danh sách
các láng giềng gần nhất là tập con của tập các láng giềng của lời giải hiện tại. Danh
sách này được tạo ra dựa trên các thông tin tri thức có sẵn của bài toán(các thông tin
heuristic) nếu có hoặc các thông tin động được sinh ra. Đối với các bài toán tĩnh danh
24
sách này được tính toán ngay từ đầu .Việc sử dụng danh sách này cho phép các thuật
toán ACO tập trung vào các những con đường có hứa hẹn đồng thời giảm không gian
tìm kiếm đi rất nhiều.
Hiện nay việc sử dụng các danh sách các láng giềng gần nhất đã được nhiều thực
nghiệm chứng minh là có kết quả tốt hơn nhiều so với việc không sử dụng danh sách
này.
1.5. Các ứng dụng của ACO
Phương pháp ACO metaheuristic chủ yếu được áp dụng cho các bài toán tối ưu tổ
hợp, ví dụ như ứng dụng vào bài toán TSP đã trình bày ở các phần trước.
Một số bài toán tối ưu NP-khó như:
Các bài toán lập lịch (job shop, flow shop, project scheduling)
Bài toán phân chia sản phẩm (The Generalized Assignment Problem - GAP)
Bài toán phủ tập hợp (The Set Covering Problem - SCP).
Các bài toán trong học máy : bài toán phân lớp, mạng Bayes, ...
Trong khi ở bài toán TSP và bài toán lập lịch là các bài toán hoán vị tức là lời
giải của nó là các hoán vị các thành phần, thì lời giải của bài toán GAP là sự phân chia
các nhiệm vụ cho các đại lý, còn trong bài toán SCP lời giải được thể hiện như là một
tập con các thành phần lời giải, chúng đều thuộc lớp các bài toán tối ưu tổ hợp có thể
sử dụng tối ưu đàn kiến để giải quyết.
Ứng dụng của phương pháp ACO vào các bài toán động được đề cập ở đây chủ
yếu là bài toán dò đường trong mạng dữ liệu chẳng hạn như mạng truyền thông
internet hiện nay. Ví dụ như thuật toán AntNet, thuật toán ABC là các thuật toán khá
thành công cho các bài toán định tuyến trên các mạng truyền tin theo gói tin (packed
switched) như mạng truyền thông internet chẳng hạn.
25
CHƯƠNG 2. GIỚI THIỆU BÀI TOÁN DTSP
2.1. Bài toán DTSP
Bài toán DTSP (Dynamic Travelling Salesman Problem) là mở rộng của bài toán
TSP, với trọng số các cạnh có thể thay đổi hoặc số đỉnh có thể thay đổi tăng hoặc giảm
theo thời gian. Mục đích là tìm ra nhanh nhất có thể được đường đi ngắn nhất mới xuất
hiện sau mỗi lần đồ thị bị biến đổi.
Định nghĩa bài toán DTSP:
Cho n(t ) điểm (P1, P2, ... Pn(t)), và ma trận khoảng cách D={dij(t)} với i, j = 1,
2,... n(t). Tìm chu trình có độ dài nhỏ nhất chứa tất cả n(t) điểm. Ở đây n(t) và dij(t) là
phụ thuộc vào thời gian t.
Thông thường người ta chỉ xét bài toán đối xứng tức là:
dij(t) = dji(t)
DTSP là một trong các bài toán tối ưu tổ hợp động mà hiện nay người ta đang tìm
cách giải bởi vì đây là bài toán có nhiều ý nghĩa trong thực tiễn và nói chung các bài
toán động có nhiều ứng dụng trong thực tế hơn nhiều so với các bài toán tĩnh. Một bài
toán tối ưu tổ hợp động khác mà nhiều người quan tâm là bài toán Network Routing
Problem hay là bài toán định tuyến các gói tin trên mạng. Bài toán này có nhiều điểm
tương đồng với bài toán DTSP và ứng dụng của nó thì không cần phải bàn cãi.
2.2. Các phương pháp giải bài toán DTSP
Các bài toán tối ưu tổ hợp động là các bài toán đặc biệt và mỗi loại có một
phương pháp giải riêng rất khác nhau. Tùy thuộc rất nhiều vào đặc điểm của mỗi bài
toán mà ta thường đưa vào các kỹ thuật đặc biệt và chúng chỉ áp dụng được đối với
loại bài toán đó, mà không đem lại hiệu quả khi áp dụng cho các bài toán khác.
26
Tải về để xem bản đầy đủ
43 trang
16/06/2025
480
Bạn đang xem 30 trang mẫu của tài liệu "Luận văn Phương pháp tối ưu hoá đàn kiến", để tải tài liệu gốc về máy hãy click vào nút Download ở trên.
File đính kèm:
- luan_van_phuong_phap_toi_uu_hoa_dan_kien.pdf
