Phương pháp tối ưu đàn kiến và ứng dụng

134 tr. + CD-ROM + Tóm tắt
Luận án TS. Khoa học máy tính — Trường Đại học Công nghệ. Đại học Quốc gia Hà Nội, 2012
Giới thiệu một phát biểu bài toán tối ưu tổ hợp dạng tổng quát. Tìm hiểu phương pháp tối ưu đàn kiến. Phân tích toán học về biến thiên vết mùi, luận án đề xuất các thuật toán mới MLAS, SMMAS và 3-LAS, hiệu quả của thuật toán được kiểm nghiệm trên hai bài toán cổ điển TSP và UBQP. Trình bày thuật toán ACOHAP giải bài toán suy diễn haplotype. Trình bày thuật toán AcoSeeD giải bài toán tìm tập hạt giống tối ưu ứng dụng trong tìm kiếm tương đồng của các chuỗi sinh học. Giới thiệu thuật toán GASVM và ACOSVM để cải tiến dự báo hoạt động điều tiết gen
Electronic Resources

0.00

Tải về miễn phí bản đầy đủ PDF luận văn tại Link bản đầy đủ 1 | Link bản đầy đủ 2


ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ

ĐẶNG THỊ THU HIỀN

I TOÁN NỘI SUY VÀ MẠNG NƠRON RBF

LUẬN ÁN TIẾN SĨ CÔNG NGHỆ THÔNG TIN

Hà nội – 2009

ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
——————————————

ĐỖ ĐỨC ĐÔNG

PHƯƠNG PHÁP TỐI ƯU ĐÀN KIẾN
VÀ ỨNG DỤNG

LUẬN ÁN TIẾN SĨ CÔNG NGHỆ THÔN I

Hà nội – 2012

ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
——————————————-

ĐỖ ĐỨC ĐÔNG

PHƯƠNG PHÁP TỐI ƯU ĐÀN KIẾN
VÀ ỨNG DỤNG

Chuyên ngành: Khoa học máy tính
Mã số: 62.48.01.01

LUẬN ÁN TIẾN SĨ CÔNG NGHỆ THÔNG TIN

NGƯỜI HƯỚNG DẪN KHOA HỌC:
PGS.TS. Hoàng Xuân Huấn

Hà nội – 2012
3

MỤC LỤC
Lời cam đoan …………………………………………………………………………………………………….. 1
Lời cảm ơn ……………………………………………………………………………………………………….. 2
Mục lục …………………………………………………………………………………………………………….. 3
Danh mục các ký hiệu và chữ viết tắt …………………………………………………………………… 7
Danh mục các bảng ………………………………………………………………………………………….. 12
Danh mục các hình vẽ, đồ thị …………………………………………………………………………….. 13
MỞ ĐẦU ………………………………………………………………………………………………………… 15
Chương 1. TỐI ƯU TỔ HỢP …………………………………………………………………………….. 20
1.1. Bài toán tối ưu tổ hợp tổng quát ……………………………………………………………….. 20
1.2. Các ví dụ ………………………………………………………………………………………………. 22
1.2.1. Bài toán người chào hàng …………………………………………………………………. 22
1.2.2. Bài toán quy hoạch toàn phương nhị phân không ràng buộc ………………….. 23
1.3. Các cách tiếp cận ……………………………………………………………………………………. 24
1.3.1. Heuristic cấu trúc …………………………………………………………………………….. 24
1.3.2. Tìm kiếm cục bộ ……………………………………………………………………………… 25
1.3.3. Phương pháp metaheuristic ……………………………………………………………….. 26
1.4. Kết luận chương …………………………………………………………………………………….. 27
Chương 2. PHƯƠNG PHÁP TỐI ƯU ĐÀN KIẾN ………………………………………………. 28
2.1. Từ kiến tự nhiên đến kiến nhân tạo …………………………………………………………… 28
2.1.1. Kiến tự nhiên …………………………………………………………………………………… 28
4

2.1.2. Kiến nhân tạo ………………………………………………………………………………….. 31
2.2. Phương pháp ACO cho bài toán TƯTH tổng quát ……………………………………… 32
2.2.1. Đồ thị cấu trúc …………………………………………………………………………………. 32
2.2.2. Mô tả thuật toán ACO tổng quát ………………………………………………………… 34
2.3. Phương pháp ACO giải bài toán người chào hàng ……………………………………… 37
2.3.1. Bài toán TSP và đồ thị cấu trúc………………………………………………………….. 38
2.3.2. Các thuật toán ACO cho bài toán TSP ………………………………………………… 39
2.4. Một số vấn đề liên quan ………………………………………………………………………….. 49
2.4.1. Đặc tính hội tụ …………………………………………………………………………………. 49
2.4.2. Thực hiện song song ………………………………………………………………………… 50
2.4.3. ACO kết hợp với tìm kiếm cục bộ ……………………………………………………… 50
2.4.4. Thông tin heuristic …………………………………………………………………………… 51
2.4.5. Số lượng kiến ………………………………………………………………………………….. 51
2.4.6. Tham số bay hơi ………………………………………………………………………………. 52
2.5. Kết luận chương …………………………………………………………………………………….. 52
Chương 3. TÍNH BIẾN THIÊN CỦA VẾT MÙI VÀ CÁC THUẬT TOÁN MỚI …… 53
3.1. Thuật toán tổng quát……………………………………………………………………………….. 53
3.1.1. Quy tắc chuyển trạng thái …………………………………………………………………. 54
3.1.2. Cập nhật mùi …………………………………………………………………………………… 54
3.2. Phân tích toán học về xu thế vết mùi ………………………………………………………… 55
3.2.1. Ước lượng xác suất tìm thấy một phương án ……………………………………….. 55
5

3.2.2. Đặc tính của vết mùi ………………………………………………………………………… 58
3.3. Thảo luận ………………………………………………………………………………………………. 60
3.3.1. Tính khai thác và khám phá ………………………………………………………………. 61
3.3.2. Các thuật toán cập nhật mùi theo quy tắc ACS ……………………………………. 63
3.3.3. Các thuật toán cập nhật mùi theo quy tắc MMAS ………………………………… 63
3.4. Đề xuất các phương pháp cập nhật mùi mới ………………………………………………. 63
3.5. Nhận xét về các thuật toán mới ………………………………………………………………… 65
3.5.1. Ưu điểm khi sử dụng SMMAS và 3-LAS ……………………………………………. 65
3.5.2. Tính bất biến …………………………………………………………………………………… 66
3.6. Kết quả thực nghiệm cho hai bài toán TSP và UBQP …………………………………. 67
3.6.1. Thực nghiệm trên bài toán TSP …………………………………………………………. 67
3.6.2. Thực nghiệm trên bài toán quy hoạch toàn phương nhị phân không ràng
buộc ………………………………………………………………………………………………………… 71
3.7. Kết luận chương …………………………………………………………………………………….. 80
Chương 4. THUẬT TOÁN ACOHAP GIẢI BÀI TOÁN SUY DIỄN HAPLOTYPE . 81
4.1. Bài toán suy diễn haplotype và tiêu chuẩn pure parsimony ………………………….. 81
4.1.1. Giải thích genotype ………………………………………………………………………….. 81
4.2.2. Suy diễn haplotype theo tiêu chuẩn pure parsimony …………………………….. 83
4.2. Thuật toán ACOHAP ……………………………………………………………………………… 84
4.2.1. Mô tả thuật toán ………………………………………………………………………………. 84
4.2.2. Đồ thị cấu trúc …………………………………………………………………………………. 85
6

4.2.3. Thủ tục xây dựng lời giải của mỗi con kiến…………………………………………. 86
4.2.4. Thông tin heuristic …………………………………………………………………………… 89
4.2.5. Cập nhật vết mùi ……………………………………………………………………………… 91
4.2.6. Hoán vị thứ tự xử lý các vị trí trong bộ genotype …………………………………. 91
4.2.7. Sử dụng tìm kiếm cục bộ ………………………………………………………………….. 92
4.2.8. Độ phức tạp thuật toán ……………………………………………………………………… 92
4.3. Kết quả thực nghiệm ………………………………………………………………………………. 93
4.3.1. Thực nghiệm trên bộ dữ liệu chuẩn ……………………………………………………. 94
4.3.2. Thử nghiệm trên dữ liệu thực …………………………………………………………….. 95
4.4. Kết luận chương …………………………………………………………………………………….. 96
Chương 5. THUẬT TOÁN AcoSeeD TÌM TẬP HẠT GIỐNG CÓ CÁCH TỐI ƯU .. 97
5.1. Bài toán tìm tập hạt giống có cách tối ưu và một số vấn đề liên quan …………… 97
5.1.1. Bài toán tìm tập hạt giống tối ưu ………………………………………………………… 97
5.1.2. Các cách tiếp cận hiện nay ………………………………………………………………… 99
5.2. Thuật toán AcoSeeD giải bài toán tìm tập hạt giống tối ưu ………………………… 101
5.2.1. Mô tả thuật toán …………………………………………………………………………….. 101
5.2.2. Thuật toán xác định độ dài các hạt giống ………………………………………….. 102
5.2.3. Thuật toán xây dựng các hạt giống …………………………………………………… 103
5.2.4. Tìm kiếm cục bộ ……………………………………………………………………………. 105
5.2.5. Cập nhật mùi …………………………………………………………………………………. 106
5.3. Kết quả thực nghiệm …………………………………………………………………………….. 106
7

5.3.1. Dữ liệu thực nghiệm ……………………………………………………………………….. 107
5.3.2. Kết quả thực nghiệm trên bộ dữ liệu nhỏ với độ dài các hạt giống đã xác
định ……………………………………………………………………………………………………….. 107
5.3.3. Kết quả thực nghiệm trên bộ dữ liệu trung bình …………………………………. 108
5.3.4. Kết quả thực nghiệm trên bộ dữ liệu lớn …………………………………………… 109
5.4. Kết luận chương …………………………………………………………………………………… 111
Chương 6. ỨNG DỤNG PHƯƠNG PHÁP ACO CẢI TIẾN HIỆU QUẢ DỰ ĐOÁN
HOẠT ĐỘNG ĐIỀU TIẾT GEN ……………………………………………………………………… 112
6.1. Bài toán dự đoán hoạt động điều tiết gen …………………………………………………. 112
6.1.1. Mối liên kết yếu tố phiên mã trong phát triển phôi của ruồi giấm Drosophila
……………………………………………………………………………………………………………… 113
6.1.2. Dự đoán hoạt động điều tiết gen bằng phương pháp học máy SVM ……… 114
6.2. Thuật toán di truyền tìm tham số cho SVM dùng trong dự đoán hoạt động điều
tiết gen ………………………………………………………………………………………………………. 116
6.2.1. Mã hóa các tham số cần tìm …………………………………………………………….. 117
6.2.2. Các phép toán di truyền ………………………………………………………………….. 117
6.2.3. Lược đồ thuật toán di truyền ……………………………………………………………. 118
6.3. Thuật toán tối ưu đàn kiến tìm tham số cho SVM dùng trong dự đoán hoạt động
điều tiết gen ……………………………………………………………………………………………….. 119
6.3.1. Đồ thị cấu trúc và ma trận mùi …………………………………………………………. 119
6.3.2. Thủ tục xây dựng lời giải của kiến và cập nhật mùi ……………………………. 120
6.4. Kết quả thực nghiệm …………………………………………………………………………….. 121
8

6.5. Kết luận chương …………………………………………………………………………………… 122
KẾT LUẬN …………………………………………………………………………………………………… 123
DANH MỤC CÁC CÔNG TRÌNH CÔNG BỐ CỦA TÁC GIẢ ………………………….. 125
TÀI LIỆU THAM KHẢO ……………………………………………………………………………….. 126

1

MỞ ĐẦU
1. Tính cấp thiết của luận án
Trong thực tế và khi xây dựng các hệ thông tin, ta thường gặp các bài toán tối
ưu tổ hợp (TƯTH). Trong đó phải tìm các giá trị cho các biến rời rạc để làm cực
trị hàm mục tiêu nào đó. Đa số các bài toán này thuộc lớp NP-khó. Trừ các bài
toán cỡ nhỏ có thể tìm lời giải bằng cách tìm kiếm vét cạn, còn lại thì thường
không thể tìm được lời giải tối ưu.
Đối với các bài toán cỡ lớn không có phương pháp giải đúng, đến nay người ta
vẫn dùng các cách tiếp cận sau:
1) Tìm kiếm heuristic để tìm lời giải đủ tốt;
2) Tìm kiếm cục bộ để tìm lời giải tối ưu địa phương;
3) Tìm lời giải gần đúng nhờ các thuật toán mô phỏng tự nhiên như: mô phỏng
luyện kim, giải thuật di truyền, tối ưu bầy đàn,…
Hai cách tiếp cận đầu thường cho lời giải nhanh nhưng không thể cải thiện thêm
lời giải tìm được, nên cách tiếp cận thứ ba đang được sử dụng rộng rãi cho các bài
toán cỡ lớn.
Trong các phương pháp mô phỏng tự nhiên, tối ưu đàn kiến (Ant Colony
Optimization – ACO) là cách tiếp cận m tah uristic tương đối mới, được giới thiệu
b i origo n m 1 1 đang được nghiên cứu và ứng dụng rộng rãi cho các bài toán
TƯTH khó.
Các thuật toán ACO sử dụng kết hợp thông tin kinh nghiệm (h uristic) và học
t ng cường qua các vết mùi của các con kiến nhân tạo để giải các bài toán TƯTH
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ủa
bài toán. Phương pháp này được áp dụng rộng rãi để giải nhiều bài toán khó và
hiệu quả nổi trội của chúng so với các phương pháp mô phỏng tự nhiên khác đã
được chứng tỏ bằng thực nghiệm.
Khi áp dụng các thuật toán tối ưu đàn kiến thông dụng như ACS và MMAS,
người ta phải tìm một lời giải đủ tốt, trên cơ s đó xác định các tham số cho cận
trên và cận dưới của vết mùi. Điều này gây nhiều khó kh n khi áp dụng thuật toán
cho các bài toán mới. Ngoài ra, lượng mùi cập nhật cho mỗi thành phần trong đồ
thị tỷ lệ với giá trị hàm mục tiêu của lời giải chứa nó liệu có phản ánh đúng thông
tin học t ng cường hay không cũng còn phải thảo luận.
Việc nghiên cứu sâu hơn về các thuật toán ACO và ứng dụng của nó đang được
nhiều người quan tâm. Từ n m 1 8 đến nay, cứ 2 n m thì có một hội nghị quốc tế
về phương pháp này tổ chức Brussels.
2

2. Mục tiêu của luận án
1) Phân tích xu thế biến thiên của vết mùi trong các thuật toán ACO, trên cơ s
đó đề xuất các quy tắc cập nhật mùi dễ sử dụng và hiệu quả hơn.
2) Đề xuất các thuật toán giải một số bài toán thời sự.
3. Các đóng góp của luận án
ựa trên các phân tích toán học, luận án đề xuất các quy tắc cập nhật mùi: Đa
mức (MLAS), Max Min trơn (SMMAS). Ưu điểm nổi trội của thuật toán được
kiểm định bằng thực nghiệm đối với các bài toán chuẩn như: lập lịch sản xuất (Job
Shop Scheduling – JSS), người chào hàng (Traveling Salesman Problem – TSP),
quy hoạch toàn phương nhị phân không ràng buộc (Unconstrained Binary
Quadratic Programming – UBQP). Trường hợp các thông tin h uristic có ảnh
hư ng nhiều tới kết quả tìm kiếm, luận án đề xuất quy tắc 3 mức (3-LAS) và kiểm
định hiệu quả của nó qua bài toán người chào hàng. Thực nghiệm cho thấy hiệu
quả của các quy tắc này như nhau nhưng quy tắc SMMAS đơn giản và dễ sử dụng
hơn, thích hợp cho ứng dụng rộng rãi.
Nhờ quy tắc cập nhật mùi SMMAS, luận án đề xuất các thuật toán mới ứng
dụng cho bài toán suy diễn haplotyp , bài toán tìm tập hạt giống tối ưu. Ngoài ra,
luận án cũng đưa ra lược đồ ứng dụng ACO, thuật toán di truyền xác định tham số
khi dùng phương pháp SVM (Support Vector Machine – SVM) cho bài toán dự báo
hoạt động điều hòa g n. Ưu điểm nổi trội của các đề xuất mới được kiểm nghiệm
bằng thực nghiệm trên dữ liệu tin cậy.
4. Bố cục của luận án
Ngoài phần kết luận, luận án được tổ chức như sau.
Chương 1: Luận án giới thiệu một phát biểu bài toán tối ưu tổ hợp dạng tổng
quát để tiện dụng về sau.
Chương 2: Những nét chính của phương pháp tối ưu đàn kiến được giới thiệu
trong chương 2.
Chương 3: Dựa trên phân tích toán học về biến thiên vết mùi, luận án đề xuất
các thuật toán mới MLAS, SMMAS và 3-LAS, hiệu quả của thuật toán được kiểm
nghiệm trên hai bài toán cổ điển TSP và UBQP.
Chương 4: Trình bày thuật toán ACOHAP giải bài toán suy diễn haplotype.
Chương 5: Trình bày thuật toán AcoS giải bài toán tìm tập hạt giống tối ưu
ứng dụng trong tìm kiếm tương đồng của các chuỗi sinh học.
Chương 6: Giới thiệu thuật toán GASVM và ACOSVM để cải tiến dự báo hoạt
động điều tiết g n.

3

Chương 1. Tối ưu tổ hợp
1.1. Bài toán tối ưu tổ hợp tổng quát
Về mặt hình thức, mỗi bài toán TƯTH ứng với một bộ ba ( ), trong đó
là tập hữu hạn trạng thái (lời giải tiềm n ng hay phương án), là hàm mục tiêu
xác định trên còn là tập các ràng buộc. Mỗi phương án 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. Mục đích của ta là
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 . Đối với
mỗi bài toán, tồn tại một tập hữu hạn gồm thành phần { } sao cho
mỗi phương án trong đều biểu diễn được nhờ các liên kết của các thành phần
trong nó. Cụ thể hơn, các tập và có các đặc tính sau.
1) Ký hiệu là tập các v ctơ trên độ dài không quá {
}, khi đó mỗi phương án trong được xác định nhờ ít nhất một
v ctơ trong như điểm 2.
2) Tồn tại tập con của và ánh xạ từ lên sao cho ( ) không rỗng
với mọi . Trong đó tập có thể xây dựng được từ tập con nào đó của
nhờ m rộng tuần tự dưới đây.
3) Từ m rộng được thành
th o thủ tục tuần tự:
i) là m rộng được với mọi
ii) Giả sử là m rộng được và chưa thuộc
. Từ tập ràng
buộc , xác định tập con ( ) của , sao cho với mọi ( ) thì
là m rộng được.
iii) Với mọi , thủ tục m rộng nêu trên xây dựng được mọi phần tử của
.
Như vậy, mỗi bài toán TƯTH được xem là một bài toán cực trị hàm biến,
trong đó mỗi biến nhận giá trị trong tập hữu hạn kể cả giá trị rỗng. Một cách
nhìn khác, nó là bài toán tìm kiếm v ctơ độ dài không quá trên đồ thị đầy có các
đỉnh có nhãn trong tập .
1.2. Các ví dụ
Hai bài toán người chào hàng (TSP) và quy hoạch toàn phương nhị phân không
ràng buộc (UBQP) được giới thiệu làm ví dụ cho các bài toán TƯTH.
1.3. Các cách tiếp cận
Các cách tiếp cận như tìm kiếm h uristic, tìm kiếm cục bộ, metaheuristic và
thuật toán m m tic cần dùng về sau được giới thiệu trong mục này.
4

Chương 2. Phương pháp tối ưu đàn kiến
Tối ưu đàn kiến (ACO) là một phương pháp m tah uristic 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 nó được cải tiến đa dạng và có nhiều ứng dụng. Trước khi giới thiệu phương
pháp ACO, luận án giới thiệu phương thức trao đổi thông tin gián tiếp của các con
kiến thực và mô hình kiến nhân tạo.
2.1. Từ kiến thực đến kiến nhân tạo
Trên đường đi, mỗi con kiến để lại một chất hóa học gọi là vết mùi dùng để
đánh dấu đường đi. Bằng cách cảm nhận vết mùi, kiến có thể lần th o đường đi
đến nguồn thức n được các con kiến khác khám phá th o phương thức chọn ngẫu
nhiên có định hướng th o nồng độ vết mùi để xác định đường đi ngắn nhất từ tổ
đến nguồn thức n.
Mô phỏng kiến tự nhiên, người ta dùng đa tác tử (multiagent) làm đàn kiến nhân
tạo, trong đó mỗi con kiến có nhiều khả n ng hơn kiến tự nhiên. Mỗi con kiến
nhân tạo (về sau sẽ gọi 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 các con kiến
có thể trao đổi thông tin có được với nhau, thực hiện tính toán cần thiết, cập nhật
mùi…
Nhờ các con kiến nhân tạo này (về sau cũng gọi đơn giản là kiến) Dorigo (1991)
đã xây dựng hệ kiến (AS) giải bài toán người chào hàng, hiệu quả của nó so với
các phương pháp mô phỏng tự nhiên khác như SA, GA đã được kiểm chứng bằng
thực nghiệm và được phát triển, ứng dụng phong phú với tên gọi chung là phương
pháp ACO.
2.2. Phương pháp ACO cho bài toán TƯTH tổng quát
Mục này giới thiệu tóm lược phương pháp tối ưu đàn kiến. Trước khi mô tả
thuật toán tổng quát, ta cần tìm hiểu về đồ thị cấu trúc cho bài toán tối ưu tổ hợp.
2.2.1. Đồ thị cấu trúc
Xét bài toán TƯTH tổng quát được nêu trong mục 1.1 dưới dạng bài toán cực
tiểu hoá ( ), trong đó là tập hữu hạn trạng thái, là hàm mục tiêu xác định
trên còn là các ràng buộc để xác định qua các thành phần của tập hữu hạn
và các liên kết của tập này. Các tập và có các đặc tính đã nêu trong chương
1.
Như đã nói trong chương trước, mỗi bài toán TƯTH được x m như một bài toán
tìm kiếm v ctơ độ dài không quá trên đồ thị đầy, các đỉnh có nhãn trong tập .
Để tìm các lời giải chấp nhận được, ta xây dựng đồ thị đầy với tập đỉnh mà 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 nhận được là
5

các v ctơ xây dựng tuần tự th o thủ tục bước ngẫu nhiên như mô tả chi tiết trong
mục 2.2.2.
Thông thường, đối với các bài toán thuộc loại NP-khó, người ta có các phương
pháp h uristic để tìm lời giải đủ tốt cho bài toán. Các thuật toán ACO kết hợp
thông tin h uristic này với phương pháp học t ng cường nhờ mô phỏng hành vi
của đàn kiến để tìm lời giải tốt hơn.
Giả sử với mỗi cạnh nối các đỉnh có trọng số h uristic để định hướng
chọn thành phần m rộng là khi thành phần cuối của là th o thủ tục tuần tự
( ( )). Ký hiệu là v ctơ các trọng số h uristic của cạnh tương ứng
(trong bài toán TSP nó có thể là v ctơ mà thành phần là nghịch đảo độ dài của
cạnh tương ứng), còn là v ctơ biểu thị các thông tin học t ng cường (về sau
gọi là vết mùi, ban đầu được kh i tạo bằng >0) định hướng m rộng với
thành phần cuối là nhờ thêm thành phần th o thủ tục tuần tự. Trường hợp đặc
biệt, và chỉ phụ thuộc vào thì các thông tin này chỉ để các đỉnh tương
ứng. Không giảm tổng quát, ta sẽ xét cho trường hợp các thông tin này các cạnh.
Khi đó ta gọi đồ thị ( ) là đồ thị cấu trúc của bài toán tối ưu tổ hợp
đang xét, trong đó là tập đỉnh, và là các thông tin đã nói trên còn là tập
cạnh của đồ thị sao cho từ các cạnh này có thể xây dựng được tập nhờ m rộng
tập th o thủ tục tuần tự. Nếu không có thông tin heuristic thì ta xem có các
thành phần như nhau và bằng 1.
2.2.2. Mô tả thuật toán ACO tổng quát
Với điều kiện kết thúc đã chọn (có thể là số bước lặp hoặc và thời gian chạy cho
trước), người ta dùng đàn kiến con thực hiện lặp xây dựng lời giải trên đồ thị
cấu trúc ( ) như sau. Trong mỗi lần lặp, mỗi con kiến chọn ngẫu
nhiên một đỉnh làm thành phần kh i tạo { } và thực hiện xây dựng
lời giải th o thủ tục bước ngẫu nhiên để xây dựng lời giải. ựa trên lời giải tìm
được đàn kiến sẽ thực hiện cập nhật mùi th o cách học t ng cường.
Thủ tục bước ngẫu nhiên
Giả sử là m rộng được, từ các ràng buộc xác định được
tập con ( ) của sao cho với mọi ( ) thì
là m rộng được hoặc
khi ( ) là rỗng. Đỉnh để m rộng được
chọn với xác suất ( ) như sau:
( ) {
[ ]

[ ]

∑ [ ]
[ ]

( )
( )
̅ ( )
(2.1)
Quá trình m rộng tiếp tục cho tới khi kiến tìm được lời giải chấp nhận được
( ) trong và do đó ( ) ( ( )) .
6

Để tiện trình bày, về sau ta sẽ xem ( ) và ( ) như nhau và không phân biệt
với .
Cập nhật mùi
Tùy th o chất lượng của lời giải tìm được mà vết mùi trên mỗi cạnh sẽ được
điều chỉnh t ng hoặc giảm tùy th o đánh giá mức độ ưu tiên tìm kiếm về sau. Vì
vậy, quy tắc cập nhật mùi được dùng làm tên gọi thuật toán và thường có dạng:
( ) ( ) ( ) (2.2)
Các bước thực hiện của các thuật toán ACO được mô tả trong hình 2.4.

Procedure Thuật toán ACO;
Begin
Kh i tạo tham số, ma trận mùi, kh i tạo con kiến;
repeat
for to do
Kiến xây dựng lời giải;
end-for
Cập nhật mùi;
Cập nhật lời giải tốt nhất;
until (Điều kiện kết thúc);
Đưa ra lời giải tốt nhất;
End;
Hình 2.4: Thuật toán ACO

Nhận xét chung về các thuật toán ACO
Nhờ kết hợp thông tin h uristic, thông tin học t ng cường và mô phỏng hoạt
động của đàn kiến, các thuật toán ACO có các ưu điểm sau:
1) Việc tìm kiếm ngẫu nhiên dựa trên các thông tin h uristic làm cho phép tìm
kiếm linh hoạt và mềm dẻo trên miền rộng hơn phương pháp h uristic 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.
2) Sự kết hợp học t ng cường 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 mà 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.
Chú ý. Khi áp dụng phương pháp ACO cho mỗi bài toán cụ thể, có ba yếu tố
quyết định hiệu quả thuật toán:
1) Xây dựng đồ thị cấu trúc thích hợp. Việc xây dựng đồ thị cấu trúc để tìm
được lời giải cho bài toán th o thủ tục tuần tự không khó. Khó kh n chính là với
các bài toán cỡ lớn thì không gian tìm kiếm quá rộng, đòi hỏi ta sử dụng các ràng
buộc một cách hợp lý để giảm miền tìm kiếm cho mỗi con kiến. Cách xử lý bài
toán suy diễn haplotyp chương 4 minh họa cho điều này.
7

2) Chọn thông tin heuristic. Thông tin h uristic tốt sẽ t ng hiệu quả thuật toán.
Tuy nhiên, nhiều bài toán ta không có thông tin này thì có thể đánh giá chúng như
nhau. Khi đó lúc ban đầu, thuật toán chỉ đơn thuần chạy th o phương thức tìm
kiếm ngẫu nhiên, vết mùi thể hiện định hướng của học t ng cường và thuật toán
vẫn thực hiện được.
3) Chọn quy tắc cập nhật mùi. Quy tắc cập nhật mùi thể hiện chiến lược học của
thuật toán. Nếu đồ thị cấu trúc và thông tin h uristic luôn phụ thuộc vào từng bài
toán cụ thể thì quy tắc cập nhật mùi là yếu tố phổ dụng và thường dùng để đặt tên
cho thuật toán. Có nhiều quy tắc cập nhật mùi đã được đề xuất, trong luận án này
chúng tôi sẽ tìm quy tắc thích hợp cho hai loại bài toán tùy th o thông tin heuristic
ảnh hư ng nhiều hay ít tới thủ tục tìm kiếm lời giải.
2.3. Phương pháp ACO giải bài toán TSP
Bài toán người chào hàng (Traveling Salesman Problem – TSP) là bài toán có
nhiều ứng dụng trong thực tế, được phát biểu như sau: một người giới thiệu sản
phẩm muốn tìm một hành trình ngắn nhất, xuất phát từ thành phố của mình, đi qua
tất cả các thành phố mà khách hàng cần giới thiệu sản phẩm và sau đó tr về thành
phố xuất phát với điều kiện các thành phố của khách hàng chỉ đi qua đúng một lần.
Bài toán TSP thuộc loại NP-khó và được x m là bài toán chuẩn để đánh giá hiệu
quả của các thuật toán giải các bài toán TƯTH mới. Thuật toán ACO đầu tiên
được gọi là hệ kiến (Ant System – AS), các thuật toán ACO về sau là cải tiến của
AS và đều dùng bài toán TSP để thử nghiệm chất lượng.
Trong mục này giới thiệu các thuật toán chính để giải bài toán này như là ví dụ
minh họa cho phương pháp ACO.
Hệ kiến (AS)
Trong mỗi bước lặp, sau khi tất cả các kiến xây dựng xong hành trình, vết mùi
sẽ được cập nhật. Việc này sẽ thực hiện như sau: trước tiên tất cả các cạnh sẽ bị
bay hơi th o một tỉ lệ không đổi, sau đó các cạnh có kiến đi qua sẽ được thêm một
lượng mùi. Việc cập nhật mùi được thực hiện như sau:
( ) ∑

( ) , (2.5)
trong đó
là lượng mùi do kiến cập nhật trên cạnh mà kiến đi qua. Giá
trị này bằng:

{

( )

(2.6)
trong đó là độ dài hành trình do kiến xây dựng, giá trị này được tính
bằng tổng độ dài các cạnh thuộc hành trình. Theo công thức (2.6), các cạnh thuộc
hành trình tốt hơn sẽ được cập nhật nhiều hơn. Nói chung, cạnh nào càng có nhiều

Tác giả

Đỗ Đức Đông

Nhà xuất bản

ĐHCN

Năm xuất bản

2012

Người hướng dẫn

Hoàng Xuân Huấn

Định danh

00050001651

Kiểu

text

Định dạng

text/pdf

Nhà xuất bản

Khoa công nghệ thông tin,

Trường đại học Công nghệ

Các đánh giá

Hiện chưa có đánh giá cho sản phẩm.

Hãy là người đầu tiên đánh giá “Phương pháp tối ưu đàn kiến và ứng dụng”

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *