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 3 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 4 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 5 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 6 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 7 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 8 Danh mục các ký hiệu và chữ viết tắt Cận trên của vết mùi Cận dưới của vết mùi Cận giữa của vết mùi Vết mùi được khởi tạo ban đầu Vết mùi trên cạnh Thông tin heuristic trên cạnh Số vòng lặp trong thuật toán ACO Số kiến sử dụng trong thuật toán ACO Tham số bay hơi 3-LAS Three-Level Ant System (Hệ kiến ba mức) ACO Ant Colony Optimization (Tối ưu đàn kiến) ACOHAP Thuật toán tối ưu đàn kiến giải bài toán suy diễn haplotype AcoSeeD Thuật toán tối ưu đàn kiến tìm tập hạt giống tối ưu ACOSVM Thuật toán tối ưu đàn kiến tìm tham số trong SVM được dùng để dự báo hoạt động điều tiết gen ACS Ant Colony System (Hệ đàn kiến) 9 AS Ant System (Hệ kiến) CRM Cis-Regulatory Module (Mô-đun điều tiết) EC Evolutionary Computing (Tính toán tiến hoá) GA Genetic Algorithm (Thuật toán di truyền) GASVM Thuật toán di truyền tìm tham số trong SVM được dùng để dự báo hoạt động điều tiết gen G-best Global-best (Lời giải tốt nhất tính đến thời điểm hiện tại) HI Haplotype Inference (Suy diễn haplotype) HIPP Haplotype Inference by Pure Parsimony (Suy diễn haplotype theo tiêu chuẩn Pure Parsimony) I-best Iteration-best (Lời giải tốt nhất trong bước lặp hiện tại) JSS Job Shop Scheduling (Bài toán lập lịch sản xuất) MLAS Multi-level Ant System (Hệ kiến đa mức) MMAS Max-Min Ant System (Hệ kiến Max Min) PSO Particle Swarm Optimization (Tối ưu bầy đàn) SA Simulated Annealing (Thuật toán mô phỏng luyện kim) SMMAS Smoothed Max-Min Ant System (Hệ kiến Max Min trơn) SpEED Thuật toán leo đồi tìm tập hạt giống tối ưu 10 SVM Support Vector Machine (Phương pháp học máy SVM) TSP Traveling Salesman Problem (Bài toán người chào hàng) TƯTH Tối ưu tổ hợp UBQP Unconstrained Binary Quadratic Programming (Bài toán quy hoạch toàn phương nhị phân không ràng buộc) 11 Danh mục các bảng Bảng 2.1: Thuật toán ACO theo thứ tự thời gian xuất hiện ........................................... 41 Bảng 3.1: Kết quả thực nghiệm so sánh bốn phương pháp ........................................... 69 Bảng 3.2: Kết quả thực nghiệm so sánh các phương pháp MMAS, SMMAS, SMMASRS (SMMAS có khởi tạo lại vết mùi), MLAS và 3-LAS. ................................ 70 Bảng 3.3: So sánh SMMAS với MMAS_HCF với bộ dữ liệu =200 ........................... 74 Bảng 3.4: So sánh SMMAS với MMAS_HCF với bộ dữ liệu =500 ........................... 75 Bảng 3.5: So sánh SMMAS với MMAS_HCF với bộ dữ liệu =500 ........................... 77 Bảng 3.6: So sánh SMMAS với MMAS_HCF với bộ dữ liệu =1000 ......................... 78 Bảng 3.7: So sánh SMMAS với MMAS_HCF với bộ dữ liệu =2500 ......................... 79 Bảng 4.1: Thiết đặt tham số cho ACOHAP ................................................................... 93 Bảng 4.2: Bảng tóm tắt thông tin về các bộ dữ liệu chuẩn ............................................ 94 Bảng 4.3: Kết quả thực nghiệm so sánh ACOHAP với CollHap với dữ liệu chuẩn ..... 94 Bảng 4.4: Thông tin dữ liệu thực ................................................................................... 95 Bảng 4.5: Kết quả thực nghiệm với dữ liệu thực ........................................................... 96 Bảng 5.1: Kết quả thực nghiệm SpEED với AcoSeeD trên bộ dữ liệu nhỏ ................ 108 Bảng 5.2: So sánh AcoSeeD với các phương pháp khác trên bộ dữ liệu trung bình ... 109 Bảng 5.3: Kết quả thực nghiệm so sánh AcoSeeD với các phương pháp trên bộ dữ liệu lớn PatternHunterII và BFAST .................................................................................... 110 Bảng 5.4: So sánh AcoSeeD với SpEEDfast trên bộ dữ liệu lớn MegaBFAST .......... 110 Bảng 6.1: Kết quả thực nghiệm so sánh 3 phương pháp ............................................. 121 12 Danh mục các hình vẽ, đồ thị Hình 1.1: Phương pháp heuristic cấu trúc tham ăn ........................................................ 24 Hình 1.2: Lời giải nhận được nhờ thay 2 cạnh (2,3), (1,6) bằng (1,3), (2,6) ................. 26 Hình 1.3: Thuật toán memetic sử dụng EC .................................................................... 27 Hình 2.1: Thực nghiệm cây cầu đôi ............................................................................... 29 Hình 2.2: Thí nghiệm bổ xung ....................................................................................... 31 Hình 2.3: Đồ thị cấu trúc tổng quát cho bài toán cực trị hàm ................... 34 Hình 2.4: Thuật toán ACO ............................................................................................. 36 Hình 2.5: Lựa chọn đỉnh đi tiếp theo ............................................................................. 40 Hình 2.6: Thuật toán ACO giải bài toán TSP có sử dụng tìm kiếm cục bộ ................... 40 Hình 3.1: Hai chu trình khác nhau 7 cạnh, đường liền qua cạnh và đường đứt đoạn qua cạnh ...................................................................................................... 62 Hình 3.2: Đồ thị cấu trúc giải bài toán UBQP ............................................................... 72 Hình 4.1: Thuật toán ACOHAP ..................................................................................... 84 Hình 4.2: Đồ thị cấu trúc (phần thuộc đường đậm) xác định giải thích genotype 201 .. 86 Hình 4.3: Thủ tục tìm lời giải của mỗi con kiến ............................................................ 88 Hình 4.4: Lời giải HI của một con kiến với =121, =002, =221 ....................... 89 Hình 5.1: Thuật toán leo đồi dùng trong SpEED và SpEEDfast ................................. 100 Hình 5.2: Thuật toán AcoSeeD .................................................................................... 101 Hình 5.3: Đồ thị cấu trúc để xác định độ dài các hạt giống ......................................... 103 Hình 5.4: Đồ thị cấu trúc xây dựng các hạt giống. ...................................................... 105 13 Hình 6.1: Dự đoán hoạt động điều tiết gen dựa trên liên kết phiên mã ....................... 114 Hình 6.2: Sơ đồ đánh giá hiệu quả tham số SVM ........................................................ 116 Hình 6.3: Một nhiễm sắc thể biểu diễn và ............................................................. 117 Hình 6.4: Gen ở vị trí in đậm đột biến 0 thành 1 hoặc ngược lại ................................ 117 Hình 6.5: Minh họa phép toán tương giao chéo của cặp nhiễm sắc thể ...................... 118 Hình 6.6: Thuật toán GASVM ..................................................................................... 118 Hình 6.7: Thuật toán ACOSVM .................................................................................. 119 Hình 6.8: Đồ thị cấu trúc .............................................................................................. 120 Hình 6.9: Biểu đồ so sánh kết quả dự đoán đúng giữa ba phương pháp ..................... 122 14 MỞ ĐẦU 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 đó (xem [31,60]). Đ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, trong đó dựa trên phân tích toán học, người ta đưa ra các quy tắc định hướng tìm kiếm một lời giải đủ tốt. 2) Sử dụng các kỹ thuật 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 (xem [31,57,60]) như mô phỏng luyện kim (Simulated Annealing - SA), giải thuật di truyền (Genetic Algorithm - GA), tối ưu bầy đàn (Particle Swarm Optimization - PSO)… 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 metaheuristic tương đối mới, được giới thiệu bởi Dorigo năm 1991 (xem [28,29,31]) đang được nghiên cứu và ứng dụng rộng rãi cho các bài toán TƯTH khó (xem [7,9,10,31,36,37,55,59,63]). Các thuật toán ACO mô phỏng cách tìm đường đi của các con kiến thực. Trên đường đi, mỗi con kiến thực để lại một vết hoá chất gọi là vết mùi (pheromone trail) và 15 theo vết mùi của các con kiến khác để tìm đường đi. Đường có nồng độ vết mùi càng cao thì càng có nhiều khả năng được các con kiến chọn. Nhờ cách giao tiếp gián tiếp này [31], đàn kiến tìm được đường đi ngắn nhất từ tổ tới nguồn thức ăn. Theo ý tưởng đó, các thuật toán ACO sử dụng kết hợp thông tin kinh nghiệm (hay còn gọi là thông tin heuristic) 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. Với mỗi bài toán TƯTH , trong đó là tập hữu hạn các phương án chấp nhận được, là hàm mục tiêu xác định trên và là để 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, mỗi lời giải trong sẽ tương ứng với một hoặc một tập hữu hạn các vectơ có độ dài bị chặn thỏa mãn các ràng buộc . Như vậy, việc tìm kiếm các lời giải trong được đưa về xây dựng lời giải trên các vectơ độ dài không quá thỏa mãn ràng buộc đã cho. Về lý thuyết, quá trình giải có thể thực hiện trên đồ thị đầy đủ có tập đỉnh được gán nhãn bởi tập với một số thông tin thêm (được gọi là đồ thị cấu trúc). Tùy theo các ràng buộc mà trong nhiều trường hợp ta có thể xét bài toán tìm trên đồ thị cấu trúc đơn giản hơn để thu hẹp miền tìm kiếm. Trong mỗi lần lặp của các thuật toán, một đàn kiến nhân tạo sẽ xây dựng lời giải theo thủ tục phát triển tuần tự trên đồ thị cấu trúc, sau đó so sánh lời giải tìm được để cập nhật vết mùi như là thông tin học tăng cường dùng cho các vòng lặp sau. Nhờ đó mà lời giải được cải tiến dần. Các thuật toán 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 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: 16 1) Xây dựng đồ thị cấu trúc thích hợp; 2) Chọn thông tin heuristic; 3) Chọn quy tắc cập nhật mùi. Hai yếu tố đầu phụ thuộc vào đặc điểm của từng bài toán cụ thể, còn quy tắc cập nhật mùi là yếu tố phổ dụng cho các bài toán và nó thường dùng làm tên để phân biệt các thuật toán ACO. Thuật toán ACO đầu tiên [28] là thuật toán hệ kiến (Ant System - AS) giải bài toán người chào hàng (Traveling Salesman Problem - TSP). Đến nay đã có nhiều biến thể được đề xuất, thông dụng nhất là hệ đàn kiến (Ant Colony System - ACS) [30,31] và hệ kiến Max-Min (Max-Min Ant System - MMAS) [66]. Ngoài các kết quả được kiểm chứng bằng thực nghiệm trên các bài toán ứng dụng, đã có nhiều nghiên cứu về đặc tính của các thuật toán [8,10,36-38,55,65] như ảnh hưởng của vết mùi, thời gian chạy và tính hội tụ, tính bất biến đối với biến đổi của hàm mục tiêu,… nhằm hiểu rõ và cải tiến các thuật toán. Khi áp dụng các thuật toá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, vấn đề 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. Nhiệm vụ tác giả luận án đặt ra là: 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; 17 2) Áp dụng kết quả đạt được, đề xuất các thuật toán giải một số bài toán thời sự trong công nghệ sinh học. Trong luận án này, dựa trên các phân tích toán học, chúng tôi đề xuất quy tắc Max-Min trơn (Smoothed Max-Min Ant System - SMMAS) như là cải tiến của thuật toán Max-Min. Ưu điểm nổi trội của chúng được kiểm định bằng thực nghiệm qua đố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 heuristic có ảnh hưởng nhiều tới kết quả tìm kiếm, chúng tôi đề xuất quy tắc 3 mức (Three-Level Ant System - 3-LAS) và kiểm định hiệu quả của nó trong bài toán người chào hàng. Ngoài ra, để điều tiết linh hoạt tính khám phá và khai thác của phương pháp ACO, chúng tôi cũng gợi ý phát triển thuật toán đa mức (Multi-level Ant System - MLAS). Trong các quy tắc này, SMMAS đơn giản, dễ sử dụng hơn. Hiện nay, ứng dụng công nghệ thông tin để nghiên cứu sinh học phân tử đang được quan tâm. Nhờ quy tắc cập nhật mùi SMMAS, luận án đề xuất các thuật toán mới giải các bài toán thời sự trong sinh học: bài toán suy diễn haplotype, bài toán tìm tập hạt giống có cách tối ưu, tìm tham số trong phương pháp SVM (Support Vector Machine - SVM) dùng cho bài toán dự báo hoạt động điều tiết gen. Ư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. Các kết quả của luận án đã được công bố trong 7 báo cáo hội nghị quốc tế [20- 26], một bài báo ở tạp chí “Tin học và điều khiển học” [1] và một hội thảo toàn quốc “Các chủ đề chọn lọc của công nghệ thông tin “[2]. Ngoài phần kết luận, luận án được tổ chức như sau. Chương 1 giới thiệu phát biểu bài toán tối ưu tổ hợp dạng tổng quát. 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ề 18 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 và so sánh hiệu quả của nó với hai thuật toán thông dụng, được xem là tốt nhất hiện nay: RPoly [32] và CollHap [68]. Chương 5 trình bày thuật toán AcoSeeD giải bài toán tìm tập hạt giống có cách tối ưu và so sánh hiệu quả của nó với hai thuật toán SpEED [50] và SpEEDfast [51], được xem là tốt nhất hiện nay. Chương 6 giới thiệu lược đồ ACOSVM và GASVM sử dụng phương pháp ACO và thuật toán di truyền để cải tiến dự báo hoạt động điều tiết gen. Hiệu quả của nó được so sánh với phương pháp lưới thông dụng đã được Zinzen đã đề xuất sử dụng trong [71]. 19 Chương 1. TỐI ƯU TỔ HỢP Trong các bài toán thực tế cũng như trong lý thuyết, ta thường phải tìm các giá trị cho các biến rời rạc để cực trị hàm mục tiêu nào đó. Các bài toán này thường dễ phát biểu nhưng lại khó giải do chúng thuộc loại tối ưu tổ hợp (TƯTH) NP-khó. Chương này giới thiệu các bài toán tối ưu tổ hợp dưới dạng tổng quát, sẽ sử dụng trong phương pháp tối ưu đàn kiến, các ví dụ minh họa và những vấn đề liên quan cần dùng về sau. 1.1. Bài toán tối ưu tổ hợp tổng quát Trong đời sống và trong các hệ thông tin, ta thường phải giải nhiều bài toán tối ưu tổ hợp quan trọng. Chẳng hạn như: tìm đường đi ngắn nhất nối hai điểm trên một đồ thị đã cho, lập kế hoạch phân phối nguồn hàng tới nơi tiêu thụ với chi phí cực tiểu, lập thời khóa biểu cho giáo viên và học sinh thuận lợi nhất, định tuyến cho các gói dữ liệu trong Internet, lập lịch hợp lý cho các hệ thống sản xuất, đối sánh các chuỗi gen trong sinh học phân tử v.v… 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 (xem [31]). 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 . 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 . Đối với mỗi bài toán, đều có thể chỉ ra 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ờ liên kết các thành phần trong nó. Cụ thể hơn, các tập và có các đặc tính sau: 20 1) Ký hiệu là tập các vectơ trên có độ dài không quá { }. Khi đó, mỗi phương án trong được xác định nhờ ít nhất một vectơ 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ờ thủ tục mở rộng tuần tự dưới đây. 3) Từ ta mở rộng tuần tự thành như sau: i) Ta xem 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) Áp dụng thủ tục mở rộng từ các phần tử cho phép ta 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 có biến, trong đó mỗi biến nhận giá trị trong tập hữu hạn kể cả giá trị rỗng. Nói một cách khác, nó là bài toán tìm kiếm trong không gian vectơ độ dài không quá trên đồ thị đầy đủ có các đỉnh có nhãn trong tập . Chú ý. 1) Trong bài toán suy diễn haplotype ở chương 4, mỗi lời giải được biễu diễn qua xâu độ dài . Cách biễu diễn này không mâu thuẫn với phát biểu bài toán ở trên vì xâu này ứng với một vectơ có độ dài , trong đó mỗi thành phần của vectơ tương ứng với một ký tự trong các xâu con của xâu kết hợp. 2) Với các bài toán TƯTH có dạng giải tích: Tìm cực trị hàm trong đó mỗi biến nhận giá trị trong tập hữu hạn tương ứng và các biến 21 này thỏa mãn các ràng buộc nào đó, thì là tập ⋃ và là các vectơ -chiều , trong đó thành phần nhận giá trị trong tập , là tập còn là tập các vectơ thỏa mãn các ràng buộc . 1.2. Các ví dụ Để thuận tiện trong các trình bày về sau, mục này giới thiệu hai bài toán TƯTH điển hình: Bài toán người chào hàng (Traveling Salesman Problem - TSP) và bài toán Quy hoạch toàn phương nhị phân không ràng buộc (Unconstrained Binary Quadratic Programming - UBQP). 1.2.1. Bài toán người chào hàng Bài toán người chào hàng (Traveling Salesman Problem - TSP) là bài toán TƯTH điển hình, được nghiên cứu nhiều và được xem là bài toán chuẩn để đánh giá hiệu quả các lược đồ giải bài toán TƯTH mới (xem [30,31]). Bài toán được phát biểu như sau: Có một tập gồm thành phố (hoặc điểm tiêu thụ) { } độ dài đường đi trực tiếp từ ci đến cj là di,j . Một người chào hàng muốn tìm một hành trình ngắn nhất từ nơi ở, đi qua mỗi thành phố đúng một lần để giới thiệu sản phẩm cho khách hàng, sau đó trở về thành phố xuất phát. Như vậy, bài toán này chính là bài toán tìm chu trình Hamilton có độ dài ngắn nhất trên đồ thị đầy đủ có trọng số , trong đó là tập đỉnh với nhãn là các thành phố trong là các cạnh nối các thành phố tương ứng, độ dài các cạnh chính là độ dài đường đi giữa các thành phố. Trong trường hợp này, tập sẽ là các chu trình Hamilton trên , là độ dài của chu trình, là ràng buộc đòi hỏi chu trình là chu trình Hamilton (qua tất cả các đỉnh, mỗi đỉnh đúng một lần), là tập thành phố được xét 22