Tài liệu Bài toán xâu gần nhất và phương pháp ACO

ĐẠ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