ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
NGUYỄN THANH BÌNH
BÀI TOÁN XÂU GẦN NHẤT VÀ PHƯƠNG PHÁP ACO
Ngành: Công nghệ thông tin
Chuyên ngành: Hệ thống thông tin
Mã số: 60480104
LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN
Hà Nội – 2014
2
LỜI CẢM ƠN
Tôi xin gửi lời cảm ơn chân thành tới TS. Phạm Quang Dũng, người thầy đáng
kính đã tận tình chỉ bảo, hướng dẫn tôi trong suốt quá trình tìm hiểu, nghiên cứu,
người đã giúp đỡ tôi giải quyết những khúc mắc trong quá trình viết chương trình để
chạy thực nghiệm và hoàn thiện luận văn.
Tôi cũng xin được gửi lời cảm ơn sâu sắc tới PGS.TS. Hoàng Xuân Huấn. Thầy đã
đưa ra những góp ý quý báu giúp cho tôi có thể hoàn thành tốt luận văn. Với kiến thức
sâu rộng, nhiều năm nghiên cứu trong lĩnh vực tối ưu hóa cũng như phương pháp tối
ưu hệ kiến của thầy đã giúp tôi hiểu rõ, sâu sắc nhiều vấn đề khó khăn gặp phải trong
quá trình nghiên cứu.
Tôi cũng bày tỏ lòng biết ơn về sự giúp đỡ của Sở GD&ĐT Hải Dương, ban giám
hiệu và các đồng nghiệp trường THPT Thanh Miện III – cơ quan nơi tôi đang công tác,
bạn bè và gia đình đã luôn động viên, giúp đỡ và tạo điệu kiện tốt nhất cho tôi.
Hà Nội, tháng 6 năm 2014
3
LỜI CAM ĐOAN
Tôi xin cam đoan đây là công trình nghiên cứu của riêng tôi. Các kết quả được viết
chung với các tác giả khác đều được sự đồng ý của đồng tác giả trước khi đưa vào luận
văn. Các kết quả nêu trong luận văn là trung thực và chưa từng được ai công bố trong
các công trình nào khác.
Tác giả
4
MỤC LỤC
LỜI CẢM ƠN .............................................................................................................2
LỜI CAM ĐOAN........................................................................................................3
MỤC LỤC ...................................................................................................................4
DANH MỤC CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT .................................................7
DANH MỤC CÁC BẢNG..........................................................................................8
DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ .....................................................................9
MỞ ĐẦU .......................................................................................................................10
Chương 1. BÀI TOÁN XÂU GẦN NHẤT VÀ MỘT SỐ PHƯƠNG PHÁP TIẾP CẬN
.......................................................................................................................................12
1.1 BÀI TOÁN XÂU GẦN NHẤT ........................................................................12
Định nghĩa 1: Khoảng cách Hamming .........................................................12
Định nghĩa 2: Xâu gần nhất của một tập xâu ...............................................12
Xác định bài toán..........................................................................................13
Ứng dụng ......................................................................................................13
1.2 MỘT SỐ PHƯƠNG PHÁP TIẾP CẬN ...........................................................13
Heuristic cấu trúc .........................................................................................13
Tìm kiếm địa phương ...................................................................................14
Phương pháp Metaheuristic..........................................................................14
Phương pháp Memetic .................................................................................14
Chương 2. PHƯƠNG PHÁP ACO................................................................................16
2.1 TỪ KIẾN TỰ NHIÊN ĐẾN KIẾN NHÂN TẠO ............................................16
2.1.1
Con kiến tự nhiên .....................................................................................16
2.1.2
Kiến nhân tạo (Artificial Ant) ..................................................................19
2.2 PHƯƠNG PHÁP ACO .....................................................................................20
2.2.1
Đồ thị cấu trúc ..........................................................................................20
2.2.2
Đặc tả thuật toán ACO tổng quát ............................................................. 22
2.2.3
Các hệ kiến ............................................................................................... 24
2.2.4
Một số vấn đề liên quan ...........................................................................24
2.2.4.1 Yếu tố hội tụ ........................................................................................24
2.2.4.2 Thực hiện song song ............................................................................25
2.2.4.3 ACO kết hợp với tìm kiếm địa phương ...............................................25
5
2.2.4.4 Thông tin heuristic ...............................................................................26
2.2.4.5 Số lượng kiến .......................................................................................26
2.2.4.6 Hệ số bay hơi .......................................................................................27
2.2.4.7 Giới hạn vết mùi ..................................................................................27
2.2.4.8 Khởi tạo vết mùi ..................................................................................27
Chương 3. CÁC PHƯƠNG PHÁP ACO GIẢI BÀI TOÁN XÂU GẦN NHẤT .........28
3.1 THUẬT TOÁN ACOM-CSP ...........................................................................28
3.1.1
Thuật toán ACO-CSP ..............................................................................28
Đồ thị cấu trúc ..........................................................................................28
Thủ tục bước ngẫu nhiên để tìm lời giải ..................................................29
Quy tắc cập nhật mùi ...............................................................................30
3.1.2
Thuật toán Memetic .................................................................................30
3.2 THUẬT TOÁN TSIACO .................................................................................32
3.2.1
Phương pháp phân đoạn cứng ..................................................................33
3.2.2
Phương pháp phân đoạn mềm ..................................................................33
3.2.3
Đặc tả thuật toán T IACO giải bài toán CSP ..........................................34
3.3 THUẬT TOÁN TSIACO2-LS .........................................................................36
Chương 4. KẾT QUẢ THỰC NGHIỆM.......................................................................37
4.1 CHƯƠNG TRÌNH ............................................................................................ 37
4.1.1
Quy trình thực hiện ..................................................................................37
4.1.2
Cài đặt ứng dụng ......................................................................................37
Bài toán ....................................................................................................37
Chương trình ............................................................................................ 37
Các bước tiến hành thực nghiệm ............................................................. 38
4.2 CÀI ĐẶT THAM SỐ .......................................................................................39
4.3 CẤU HÌNH MÁY TÍNH ..................................................................................40
4.4 THỰC NGHIỆM ẢNH HƯỞNG CỦA HỆ SỐ BAY HƠI TỚI CHẤT
LƯỢNG LỜI GIẢI CỦA CÁC THUẬT TOÁN ......................................................41
4.5 THỰC NGHIỆM ẢNH HƯỞNG CỦA KỸ THUẬT TÌM KIẾM ĐỊA
PHƯƠNG ĐẾN CHẤT LƯỢNG LỜI GIẢI Ant-CSP .............................................44
4.5.1
N=10, Loop=2000 ....................................................................................44
4.5.2
N=30, Loop=2000 ....................................................................................44
6
4.5.3
N=50, Loop=2000 ....................................................................................45
4.6 THỰC NGHIỆM SO SÁNH ACOM-CSP, TSIACO1, TSIACO2
VỚI Ant-CSP ............................................................................................................45
4.6.1
So sánh hiệu quả và thời gian chạy với vòng lặp cho trước ....................45
4.6.1.1 N = 10, Loop = 2000 ...........................................................................46
4.6.1.2 N = 20, Loop = 2000 ...........................................................................48
4.6.1.3 N = 30, Loop = 2000 ...........................................................................50
4.6.1.4 N = 40, Loop = 2000 ...........................................................................52
4.6.1.5 N = 50, Loop = 2000 ...........................................................................54
4.6.2
So sánh hiệu quả các thuật toán với cùng thời gian chạy ........................57
4.7 THỰC NGHIỆM SO SÁNH ACOM-CSP, TSIACO2 VỚI TSIACO2-LS ....58
4.7.1
So sánh hiệu quả và thời gian chạy với vòng lặp cho trước ....................58
4.7.1.1 Giả sử thời gian không hạn chế: Chọn N=30, Loop=2500 .................58
4.7.1.2 Giả sử thời gian không hạn chế: Chọn N=40, Loop=2500 .................59
4.7.1.3 Giả sử thời gian không hạn chế: Chọn N=50, Loop=2500 .................59
4.7.2
So sánh hiệu quả các thuật toán với cùng thời gian chạy ........................60
KẾT LUẬN ...............................................................................................................62
TÀI LIỆU THAM KHẢO .........................................................................................63
7
DANH MỤC CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT
Ký hiệu
Ý nghĩa
ACO
Ant Colony Optimization (Tối ưu đàn kiến)
ACOM-CSP
An Efficient Two-phase Ant Colony Optimization Algorithm for the
Closest String Problem (Thuật toán tối ưu đàn kiến hai pha cho bài
toán xâu gần nhất)
ACS
Ant Colony System (Hệ đàn kiến)
ANTS
From Ant Colonies to Artificial Ants (Từ kiến tự nhiên đến kiến
nhân tạo)
CSP
Closest String Problem (Bài toán xâu gần nhất)
MMAS
Max-Min Ant System (Hệ kiến Max Min)
TƯTH
Tối ưu tổ hợp
TSIACO
Two-Stage
updating
pheromone
for
Invariant
Ant
Colony
Optimization algorithm (Thuật toán tối ưu đàn kiến hai giai đoạn cập
nhật mùi)
TSP
Traveling alesman Problem (Bài toán người chào hàng)
SMMAS
Smooth Max-Min Ant System (Hệ kiến Max Min trơn)
8
DANH MỤC CÁC BẢNG
Bảng 3.1 Hệ số bay hơi được trong các giai đoạn cập nhật mùi của TSIACO ............35
Bảng 3.2 Điều kiện phân chia giai đoạn cập nhật mùi của thuật toán TSIACO ..........35
Bảng 4.1 Kết quả lời giải tốt nhất mà các thuật toán tìm thấy sử dụng bộ dữ liệu
10 chuỗi ........................................................................................................................46
Bảng 4.2 Kết quả giá trị trung bình của các giải pháp tốt sử dụng bộ dữ liệu 10 chuỗi
.......................................................................................................................................47
Bảng 4.3 Kết quả lời giải tốt nhất mà các thuật toán tìm thấy sử dụng bộ dữ liệu
20 chuỗi ........................................................................................................................48
Bảng 4.4 Kết quả giá trị trung bình của các giải pháp tốt sử dụng bộ dữ liệu 20 chuỗi
.......................................................................................................................................49
Bảng 4.5 Kết quả lời giải tốt nhất mà các thuật toán tìm thấy sử dụng bộ dữ liệu
30 chuỗi ........................................................................................................................50
Bảng 4.6 Kết quả giá trị trung bình của các giải pháp tốt sử dụng bộ dữ liệu 30 chuỗi
.......................................................................................................................................51
Bảng 4.7 Kết quả lời giải tốt nhất mà các thuật toán tìm thấy sử dụng bộ dữ liệu
40 chuỗi ........................................................................................................................52
Bảng 4.8 Kết quả giá trị trung bình của các giải pháp tốt sử dụng bộ dữ liệu 40 chuỗi
.......................................................................................................................................53
Bảng 4.9 Kết quả lời giải tốt nhất mà các thuật toán tìm thấy sử dụng bộ dữ liệu
50 chuỗi ........................................................................................................................54
Bảng 4.10 Kết quả giá trị trung bình của các giải pháp tốt sử dụng bộ dữ liệu 50 chuỗi
.......................................................................................................................................55
Bảng 4.11 Kết quả thực nghiệm sử dụng bộ dữ liệu 30 chuỗi ......................................58
Bảng 4.12 Kết quả thực nghiệm sử dụng bộ dữ liệu 40 chuỗi ......................................59
Bảng 4.13 Kết quả thực nghiệm sử dụng bộ dữ liệu 50 chuỗi ......................................59
9
DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ
Hình 1.1 Phương pháp Heuristic cấu trúc ....................................................................14
Hình 1.2 Đặc tả thuật toán Memetic-EC .......................................................................15
Hình 2.1 Thể hiện hành vi của mỗi con kiến trong tự nhiên .........................................16
Hình 2.2 Thí nghiệm cây cầu đôi...................................................................................17
Hình 2.3 Thí nghiệm bổ xung ........................................................................................18
Hình 2.4 Đồ thị cấu trúc tổng quát cho bài toán cực trị hàm
..................21
Hình 2.5 Lựa chọn đỉnh đi tiếp theo ..............................................................................22
Hình 2.6 Đặc tả thuật toán ACO ...................................................................................23
Hình 3.1 Đồ thị cấu trúc ................................................................................................ 29
Hình 3.2 Xây dựng lời giải ............................................................................................ 29
Hình 3.3 Đặc tả thuật toán Memetic –CSP...................................................................31
Hình 3.4 Ví dụ về Tìm kiếm địa phương ........................................................................31
Hình 3.5 Đặc tả thuật toán TSIACO1 ...........................................................................34
Hình 3.6 Đặc tả thuật toán TSIACO2 ...........................................................................34
Hình 3.7 Đặc tả thuật toán TSIACO2-LS ......................................................................36
Hình 4.1 Giao diện chương trình chính ........................................................................38
Hình 4.2 Giao diện hiển thị bộ dữ liệu Input ................................................................ 39
Hình 4.3 Thông báo kết quả chạy thực nghiệm thuật toán ACOM-CSP.......................39
Đồ thị 4.1 Kết quả chạy thuật toán Ant-CSP với hệ số bay hơi khác nhau ..................41
Đồ thị 4.2 Kết quả chạy thuật toán ACOM-CSP với hệ số bay hơi khác nhau .............42
Đồ thị 4.3 Kết quả chạy thuật toán TSIACO1 với hệ số bay hơi khác nhau .................42
Đồ thị 4.4 Kết quả chạy thuật toán TSIACO2 với hệ số bay hơi khác nhau .................43
Đồ thị 4.5 Kết quả chạy thực nghiệm Ant-CSP sử dụng bộ dữ liệu 10 chuỗi ...............44
Đồ thị 4.6 Kết quả chạy thực nghiệm Ant-CSP sử dụng bộ dữ liệu 30 chuỗi ...............44
Đồ thị 4.7 Kết quả chạy thực nghiệm Ant-CSP sử dụng bộ dữ liệu 50 chuỗi ...............45
Đồ thị 4.8 Biểu đồ biến thiên kết quả của các thuật toán khi thời gian chạy thay đổi từ
1000s đến 10000s cho ví dụ có N = 30, Length=1000 .................................................57
Đồ thị 4.9 Biểu đồ biến thiên kết quả của các thuật toán khi thời gian chạy thay đổi từ
1000s đến 25000s cho ví dụ có N = 30, Length=1000 .................................................61
10
MỞ ĐẦU
Dữ liệu tin sinh học được tạo ra thường có dung lượng rất lớn, luôn đòi hỏi có
những thuật toán hiệu quả để xử lý trên máy tính. Bài toán xâu gần nhất có những ứng
dụng cụ thể vào tin sinh học như tìm kiếm motif trên các chuỗi sinh học, cũng không
phải là ngoại lệ về độ phức tạp tính toán. Việc kiểm thử các thuật toán đã có và tìm ra
một thuật toán mới hiệu quả cho bài toán này cũng như nhiều bài toán tin sinh học
khác là vấn đề cấp thiết ngày nay, không chỉ ở Việt Nam, mà trên toàn thế giới. Trong
bài luận văn đi sâu tìm hiểu phương pháp ACO để giải bài toán trên.
Trước tiên, tôi đã hệ thống hóa các nội dung lý thuyết và thuật toán liên quan đến
vấn đề nghiên cứu: bài toán xâu gần nhất và các phương pháp tiếp cận, phương pháp
ACO và các phương pháp biến thể mới áp dụng cho bài toán nêu trên (ví dụ như tìm
hiểu các thuật toán Ant-CSP, ACO-CSP, ACOM-CSP) và tìm hiểu thuật toán TSIACO
áp dụng cho bài toán người chào hàng.
au đó, tôi đã sử dụng quy tắc cập nhật mùi do Zhaojun Zhang và Zuren Feng [10]
đề xuất để xây dựng thuật toán giải bài toán nêu trên, đó là thuật toán TSIACO1,
TSIACO2.
Tôi đề xuất ra thuật toán mới TSIACO2-LS là thêm kỹ thuật tìm kiếm địa phương
vào giai đoạn 2 của thuật toán TSIACO2.
Tôi đã tiến hành cài đặt các thuật toán ACOM-CSP, TSIACO1, TSIACO2,
TSIACO2-LS. au đó, tôi chạy thực nghiệm và so sánh kết quả chạy của các thuật
toán trên.
Thực nghiệm cho thấy, thuật toán mới TSIACO2-LS có những ưu điểm nhất định,
khoảng cách Hamming trung bình tìm được thấp hơn so với các thuật toán đã có, tuy
thời gian thực hiện lâu hơn vì phải xử lý tìm kiếm địa phương. Thực nghiệm cũng cho
thấy, nếu thời gian hạn chế thì thuật toán cho chất lượng lời giải tốt nhất và hội tụ
nhanh nhất là ACOM-CSP, nếu thời gian không hạn chế thì thuật toán cho chất lượng
lời giải tốt nhất là TSIACO2-LS.
Nội dung chính trong bài luận văn của tôi gồm 4 chương như sau:
-
Chương 1. Bài toán xâu gần nhất và một số phương pháp tiếp cận
-
Chương 2. Phương pháp ACO
11
-
Chương 3. Các phương pháp ACO giải bài toán xâu gần nhất
-
Chương 4. Kết quả thực nghiệm
12
Chương 1.
BÀI TOÁN XÂU GẦN NHẤT VÀ MỘT SỐ
PHƯƠNG PHÁP TIẾP CẬN
Bài toán xâu gần nhất (Closest String Problem - CSP) thuộc lớp bài toán tối ưu tổ
hợp (gọi tắt là TƯTH), bài toán này được đánh giá là phức tạp và là một trong những
bài toán khó tính toán cho đến nay [10].
TƯTH là một dạng của bài toán tối ưu hóa. Tối ưu hoá là thuật ngữ thường được
dùng để cực tiểu hoá hay cực đại hoá một hàm. Thông thường chỉ cần tìm cực tiểu một
hàm là đủ. Việc tìm cực đại của f(x) thực hiện một cách đơn giản bằng cách tìm cực
tiểu của hàm −f(x).
1.1 BÀI TOÁN XÂU GẦN NHẤT
Xét tập X các xâu có độ dài m với các thành phần thuộc bộ chữ cái ∑, trên đó xác
định khoảng cách Hamming như sau:
Định nghĩa 1: Khoảng cách Hamming
- Với hai xâu tùy ý x = x1…xm và y = y1…ym, khoảng cách dH(x,y) là số vị trí khác
nhau của xi và yi với i
.
- Với mỗi tập hữu hạn xâu có cùng độ dài S, khoảng cách từ một xâu t đến tập S
là khoảng cách lớn nhất của t đến các chuỗi trong S, ký hiệu là dH(t,S):
dH(t,S) = max{dH(t,s): s S}
(1.1)
Ví dụ. Xét xâu t = “GGGGG” và tập xâu S={ s1= “AGGAA”, s2 = “AGGGA”,
s3 = “GGGGA”}. Do dH(t, s1)=3; dH (t,s2)=2; dH(t,s3)=1; Nên dH(t,S) =3.
Định nghĩa 2: Xâu gần nhất của một tập xâu
Cho trước tập S gồm n xâu có độ dài m với các thành phần thuộc bộ chữ cái ∑,
trên đó xác định xâu t được gọi là xâu gần nhất [10] của S nếu nó thỏa mãn công thức
(1.2):
dH(t,S) = min{ dH(x,S): x X}
(1.2)
13
Xác định bài toán
- Input: Cho một tập S={s1, s2, …, sn} có cùng độ dài m với các thành phần thuộc
bộ chữ cái ∑.
- Task: Tìm xâu t có độ dài m, sao cho khoảng cách Hamming của t tới xâu xa
nhất trong
đạt cực tiểu.
Ứng dụng
Bài toán xâu gần nhất có vai trò quan trọng trong xử lý thông tin và tìm kiếm
motif trong tin sinh học. Vì vậy, nó đang thu hút nhiều người quan tâm nghiên cứu và
đã được chứng minh thuộc loại NP-khó.
1.2 MỘT SỐ PHƯƠNG PHÁP TIẾP CẬN
Với những bài toán CSP cỡ nhỏ hoặc những bài toán đặc biệt thì có thể tìm lời giải
tối ưu nhờ kỹ thuật tìm kiếm vét cạn hoặc xây dựng những lời giải đặc thù riêng. Tuy
nhiên, với các bài toán CSP cỡ lớn, hầu hết các bài toán trong số đó là bài toán NP-khó
[3, tr.205-219], thì phải tìm lời giải theo phương pháp tìm kiếm gần đúng. Các phương
pháp giải loại bài toán này phần lớn dựa trên 2 kỹ thuật cơ bản: heuristic cấu trúc
(construction heuristic) và tìm kiếm địa phương (local search).
Heuristic cấu trúc
Đối với những bài toán không thể tìm lời giải tối ưu (ví dụ: bài toán với thời gian
đa thức) thì nghĩ tới việc tìm lời giải gần đúng. Heuristic cấu trúc là kỹ thuật hay được
dùng trong việc tìm lời giải gần đúng, lời giải của bài toán được xây dựng thông qua
việc mở rộng tuần tự. Từ đỉnh khởi tạo trong tập
, từng bước mở rộng không quay
lui, thêm vào các thành phần mới theo phương thức ngẫu nhiên hay tất định dựa trên
những quy tắc heuristic.
Ứng với mỗi bài toán cụ thể, có các quy tắc heuristic khác nhau, chúng được xây
dựng dựa trên các kết quả phân tích toán học hoặc kinh nghiệm.
Khái quát hóa mô phỏng thuật toán Heuristic cấu trúc như hình 1.1 – trang bên.
14
Procedure Heuristic cấu trúc
Begin
chọn thành phần
trong
While (chưa xây dựng xong lời giải) do
//chọn thành phần bổ sung vào
GreedyComponent( )
End-while
Đưa ra lời giải
End;
Hình 1.1 Phương pháp Heuristic cấu trúc
Tìm kiếm địa phương
- Ý tưởng: Bắt đầu từ một phương án chấp nhận được, lặp lại bước cải tiến lời
giải nhờ các thay đổi địa phương.
- Cách thực hiện: Để thực hiện kỹ thuật này, cần xác định được cấu trúc lân cận
của mỗi phương án (lời giải) đang xét, tức là những phương án chấp nhận được, gần
với nó nhất, nhờ thay đổi một số thành phần. Cách thường dùng là lân cận -thay đổi,
tức là lân cận bao gồm các phương án chấp nhận được khác với phương án đang xét
nhờ thay đổi nhiều nhất
thành phần.
Phương pháp Metaheuristic
Phương pháp Metaheuristic là một phương pháp heuristic tổng quát được thiết kế,
định hướng cho các thuật toán cụ thể (bao gồm cả heuristic cấu trúc và tìm kiếm địa
phương). Như vậy, mỗi metaheuristic là một lược đồ thuật toán tổng quát ứng dụng
cho các bài toán tối ưu khác nhau, với một chút sửa đổi cho phù hợp với từng bài toán.
Phương pháp Memetic
Phương pháp Memetic là một mô hình theo phương pháp metaheuristic. Trong các
thuật toán được thiết kế theo memetic, có nhiều thế hệ quần thể có lời giải chấp nhận
được. Trong mỗi quần thể của thế hệ tương ứng, chỉ chọn ra một số lời giải (chẳng hạn
lời giải tốt nhất) để thực hiện tìm kiếm địa phương nhằm cải thiện chất lượng. Quá
trình tiến hóa này tìm được lời giải tốt nhất có thể.
15
Hình 1.2 đặc tả một thuật toán memetic sử dụng tính toán tiến hóa (Evolutionary
Computing - EC).
Proedure Thuật toán Memetic-EC
Begin
Initialize: Tạo ra quần thể đầu tiên
While điều kiện dừng chưa thỏa mãn do
Đánh giá các cá thể trong quần thể
Thực hiện tiến hóa quần thể nhờ các toán tử cho trước
Chọn tập con
để cải tiến nhờ thủ tục tìm kiếm địa phương
For mỗi cá thể trong
do
Thực hiện tìm kiếm địa phương
End-for
Chọn phần tử tốt nhất
End-while
Đưa ra lời giải tốt nhất
End;
Hình 1.2 Đặc tả thuật toán Memetic-EC
16
Chương 2.
PHƯƠNG PHÁP ACO
ACO (Ant Colony Optimization - tối ưu đàn kiến) là một phương pháp
metaheuristic [3, tr.48-53] dựa trên ý tưởng mô phỏng cách tìm đường đi từ tổ tới
nguồn thức ăn của các con kiến tự nhiên. Đến nay phương pháp ACO được cải tiến với
nhiều phiên bản đa dạng và có nhiều ứng dụng. Trước khi tìm hiểu phương pháp ACO
tôi đi tìm hiểu phương thức trao đổi thông tin gián tiếp của kiến tự nhiên và mô hình
kiến nhân tạo.
2.1 TỪ KIẾN TỰ NHIÊN ĐẾN KIẾN NHÂN TẠO
(From Ant Colonies to Artificial Ants - ANTS)
Những hình ảnh 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. Trong thực tế, 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 (vết mùi).
2.1.1 Con kiến tự nhiên
Khi tìm đường đi, đàn kiến trao đổi thông tin gián tiếp và hoạt động theo phương
thức tự tổ chức. Phương thức này tuy đơn giản nhưng đã giúp cho đàn kiến có thể thực
hiện được những công việc phức tạp vượt xa khả năng của từng con kiến, đặc biệt là
khả năng tìm đường đi ngắn nhất từ tổ đến nguồn thức ăn [3, tr.16] (xem hình 2.1)
(mặc dù, kiến không có khả năng đo độ dài đường đi).
Hình 2.1 Thể hiện hành vi của mỗi con kiến trong tự nhiên
17
Để làm được điều đó, trên đường đi, mỗi con kiến để lại vết mùi dùng để đánh dấu
đường đi. Bằng cách cảm nhận vết mùi, con kiến có thể lần theo đường đi đến nguồn
thức ăn được các con kiến khác khám phá theo phương thức chọn ngẫu nhiên, có định
hướng theo nồng độ vết mùi.
Con kiến chịu ảnh hưởng của các vết mùi của các con kiến khác, đây là ý tưởng
chính để thiết kế thuật toán ACO.
Thí nghiệm chiếc cầu đôi
Sự gửi vết mùi và hành vi của một số loài kiến đã được điều tra kiểm soát trong
các thực nghiệm của một số nhà nghiên cứu. Một trong những thí nghiệm nổi bật nhất
là thí nghiệm được thiết kế và đi vào hoạt động của Deneubourg và các đồng nghiệp
[3, tr.17-19], người mà đã sử dụng một chiếc cầu nối tổ của đàn kiến với nguồn thức
ăn (xem hình 2.2). Họ chạy các thực nghiệm với tỉ lệ dài đường
khác nhau của chiếc cầu đôi, trong đó
là độ dài của nhánh dài còn
giữa hai nhánh
là độ dài của
nhánh ngắn.
Hình 2.2 Thí nghiệm cây cầu đôi
(a) Hai nhánh có độ dài bằng nhau
(b) Hai nhánh có độ dài khác nhau
Trong thí nghiệm thứ nhất, chiếc cầu đôi có hai nhánh bằng nhau (hình 2.2.a). Ban
đầu, con kiến lựa chọn đường đi một cách tự do đi từ tổ đến nguồn thức ăn, cả hai
nhánh đều có kiến đi, nhưng sau một thời gian các con kiến này tập trung đi theo cùng
một nhánh.
18
Giải thích kết quả: Ban đầu không có vết mùi nào trên cả hai nhánh, do đó kiến lựa
chọn nhánh bất kỳ với xác suất như nhau. Một cách ngẫu nhiên, sẽ có một nhánh có số
lượng kiến lựa chọn nhiều hơn nhánh kia. Do con kiến để lại vết mùi trong quá trình di
chuyển, nhánh có nhiều con kiến lựa chọn sẽ có nồng độ mùi lớn hơn nồng độ mùi của
nhánh còn lại. Nồng độ mùi trên cạnh lớn hơn sẽ ngày càng lớn hơn, vì ngày càng có
nhiều kiến lựa chọn. Cuối cùng, hầu như tất cả các kiến sẽ tập trung trên cùng một
nhánh. Thực nghiệm này cho thấy là sự tương tác địa phương giữa các con kiến với
thông tin gián tiếp là vết mùi để lại, cho phép điều chỉnh hoạt động vĩ mô của đàn kiến.
Trong thí nghiệm thứ hai, độ dài của nhánh dài gấp đôi độ dài nhánh ngắn (hình
2.2b). Trong trường hợp này, sau một thời gian tất cả các con kiến đều chọn đoạn
đường ngắn hơn.
Giải thích kết quả: Cũng như thí nghiệm thứ nhất, ban đầu đàn kiến lựa chọn hai
nhánh đi như nhau, một nửa số kiến đi theo nhánh ngắn và một nửa đi theo nhánh dài
(mặc dù trên thực tế, do tính ngẫu nhiên có thể một nhánh nào đó được nhiều kiến lựa
chọn hơn nhánh kia). Những con kiến lựa chọn đi theo nhánh ngắn sẽ nhanh chóng
quay trở lại tổ và khi phải lựa chọn giữa nhánh ngắn và nhánh dài, kiến sẽ thấy nồng
độ mùi trên nhánh ngắn cao hơn nồng độ mùi trên nhánh dài, do đó sẽ ưu tiên lựa chọn
đi theo nhánh ngắn hơn. Tuy nhiên, trong thời gian đầu không phải tất cả các kiến đều
đi theo nhánh ngắn hơn. Phải mất một khoảng thời gian tiếp theo đàn kiến mới lựa
chọn đi theo nhánh ngắn. Điều này minh chứng đàn kiến đã sử dụng phương thức thăm
dò, tìm đường mới.
Thí nghiệm thứ ba: Ban đầu từ tổ đến nguồn thức ăn chỉ có một nhánh dài và sau
30 phút, thêm một nhánh ngắn (hình 2.3). Trong trường hợp này, nhánh ngắn thường
không được kiến chọn mà kiến tập trung đi trên nhánh dài.
Hình 2.3 Thí nghiệm bổ xung
Ban đầu chỉ có một nhánh và sau 30 phút thêm nhánh ngắn hơn
19
Giải thích kết quả: Nồng độ vết mùi cao trên cạnh dài và sự bay hơi của vết mùi
trên cạnh dài diễn ra chậm nên đại đa số các con kiến vẫn lựa chọn nhánh dài (có nồng
độ vết mùi cao). Hành vi này tiếp tục được củng cố kiến chọn đi theo nhánh dài, ngay
cả khi có một nhánh ngắn xuất hiện. Việc bay hơi vết mùi là cơ chế tiện lợi cho việc
tìm đường mới, nghĩa là việc bay hơi có thể giúp kiến quên đi đường đi tối ưu địa
phương đã được tìm thấy trước đây để tìm khám phá đường đi mới tốt hơn.
2.1.2 Kiến nhân tạo (Artificial Ant)
Thí nghiệm chiếc cầu đôi 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
luật xác xuất. Vết mùi của đàn kiến cho phép liên tưởng tới cách học tăng cường trong
bài toán chọn tác động tối ưu [3], gợi mở mô hình mô phỏng cho bài toán tìm đường đi
ngắn nhất giữa hai nút (tương ứng là tổ và nguồn thức ăn) trên đồ thị, trong đó các tác
tử (agent) là đàn kiến nhân tạo.
Tuy nhiên, trong các bài toán ứng dụng các đồ thị thường phức tạp hơn. Từ mỗi
đỉnh có thể có nhiều cạnh, nên nếu mô phỏng thực sự hành vi của đàn kiến tự nhiên
nhiều con kiến sẽ đi luẩn quẩn và do đó hiệu quả thuật toán sẽ rất kém. Vì vậy, dùng
kỹ thuật đa tác tử (multiagent) mô phỏng đàn kiến nhân tạo, trong đó mỗi con kiến
nhân tạo có khả năng nhiều hơn so với kiến tự nhiên.
Kiến nhân tạo (gọi đơn giản là kiến) có bộ nhớ riêng, có khả năng ghi nhớ các đỉnh
đã thăm trong hành trình và tính được độ dài đường đi nó chọn. Ngoài ra, kiến có thể
trao đổi thông tin với nhau, thực hiện tính toán cần thiết, cập nhật mùi…
Năm 1991, Dorigo [2] sử dụng mô hình kiến nhân tạo này, đã xây dựng thuật toán
hệ kiến AS (Ant System) giải bài toán người chào hàng (Traveling Salesman Problem
- TSP). Hiệu quả của thuật toán so với các phương pháp mô phỏng tự nhiên khác (như:
thuật toán luyện kim và thuật toán di truyền) đã được kiểm chứng bằng thực nghiệm.
Thuật toán này về sau được phát triển và có nhiều ứng dụng phong phú, được gọi
chung là phương pháp ACO.
Dorigo đã được Hội đồng châu Âu trao giải thưởng đặc biệt Marie Curie (Marie
Curie Excellence Award – trao hai năm một lần giành cho năm nhà khoa học có nhiều
đóng góp cho nền khoa học và công nghệ châu Âu) vào ngày
các hội nghị về kiến đã tổ chức
11 2
3. Đến nay,
lần (ANT 9 , ANT 2000, ANTS 2002, ANTS
20
2004, ANTS 2006, ANTS 2008, ANTS 2010, ANTS 2 12) và ở mỗi hội nghị có
khoảng 3 -4 báo cáo về các công trình nghiên cứu lý thuyết và thực nghiệm có ý
nghĩa khoa học và ứng dụng quan trọng góp phần chứng tỏ ACO là phương pháp tối
ưu mới m và hiệu quả.
2.2 PHƯƠNG PHÁP ACO
2.2.1 Đồ thị cấu trúc
Xét bài toán TƯTH tổng quát như sau:
-
. Mỗi phương án
Input: Cho bộ ba
thỏa mãn các ràng buộc
gọi là phương án (hay lời giải) chấp nhận được.
-
Task: Tìm phương án chấp nhận được
tối ưu hóa toàn cục hàm mục tiêu .
Trong đó: S là tập hữu hạn trạng thái (lời giải tiềm năng hay phương án), f là hàm
mục tiêu xác định trên ,
là tập các ràng buộc. Chẳng hạn, với bài toán cực tiểu thì
với mọi phương án chấp nhận được s.
Các tập S, f và Ω có các đặc tính sau:
1) Ký hiệu
là tập các dãy trong
độ dài không quá
}. Khi đó, mỗi phương án trong
{
được xác định bởi ít nhất một véc
tơ trong .
2) Tồn tại tập con
, trong đó tập
mọi
của
và ánh xạ
từ
lên
sao cho
có thể xây dựng được từ tập con
của
khác rỗng với
nhờ mở rộng tuần
tự.
3) Từ
, mở rộng tuần tự thành
là mở rộng được với mọi
i)
Xem
ii)
Giả sử
buộc
như sau:
là mở rộng được và chưa thuộc
, xác định tập con
của C, sao cho với mọi
. Từ tập ràng
thì
là mở rộng được.
iii) Áp dụng thủ tục mở rộng từ các phần tử
phần tử của
cho phép xây dựng được mọi
.
Để tìm các lời giải chấp nhận được cho bài toán trên, xây dựng đồ thị đầy đủ với
tập đỉnh , mỗi đỉnh của nó tương ứng với mỗi thành phần của
Các lời giải chấp
- Xem thêm -