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ậnvănnày trình bày một cách khái quát về các thuật toán ACOvà 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. DTSPthực chất là mở rộng của bài toánngườ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àmrõ cho cho hiệu
quả củacải tiếnthuật toán.
Luận văn gồm có 5 chương.
Chương 1 giới thiệuphươngpháp tối ưu hóa đàn kiến: quá trìnhphá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ụngcủ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
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 TSPchuẩ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
43 trang |
Chia sẻ: oanhnt | Lượt xem: 1976 | Lượt tải: 1
Bạn đang xem trước 20 trang tài liệu Báo cáo Phương pháp tối ưu hoá đàn kiến, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trê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ừ
1 ACO
Ant Colony Optimization
(Tối ưu hóa đàn kiến)
2 AS
Ant System
(Hệ kiến AS)
3 ACS
Ant Colony System
(Hệ kiến ACS)
4 MMAS
Max-Min Ant System
(Hệ kiến MMAS)
6 MLAS
Multi-level Ant System
(Hệ kiến đa mức MLAS)
9 TSP
Travelling Salesman Problem
(Bài toán người chào hàng)
10 JSS
Job shop scheduling
(Bài toán lập lịch sản xuất)
11 g-best global-best
12 i-best iteration-best
1
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.
2
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.
3
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.
4
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ở
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.
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
6
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 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ự
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
8
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
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
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.
10
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