Tổng quan luận án
Tính cấp thiết và khoảng trống nghiên cứu
Trong thực tế và quá trình xây dựng các hệ thống thông tin, các bài toán tối ưu tổ hợp (TƯTH) xuất hiện phổ biến, đòi hỏi phải tìm kiếm các giá trị biến rời rạc nhằm tối ưu hóa một hàm mục tiêu xác định. Phần lớn các bài toán này thuộc lớp bài toán NP-khó (NP-hard). Đối với các bài toán quy mô lớn, việc tìm kiếm lời giải chính xác bằng phương pháp vét cạn là bất khả thi về mặt chi phí tính toán. Hiện nay, ba hướng tiếp cận chủ yếu được áp dụng gồm:
- Tìm kiếm heuristic để tìm kiếm lời giải đủ tốt;
- Tìm kiếm cục bộ để xác định lời giải tối ưu địa phương;
- Tìm kiếm lời giải gần đúng thông qua 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).
Trong nhóm phương pháp mô phỏng tự nhiên, phương pháp tối ưu đàn kiến (Ant Colony Optimization - ACO) là hướng tiếp cận metaheuristic được Marco Dorigo giới thiệu từ năm 1991. Thuật toán ACO kết hợp thông tin kinh nghiệm (heuristic) và cơ chế học tăng cường (reinforcement learning) thông qua vết mùi (pheromone) của các cá thể kiến nhân tạo để đưa bài toán TƯTH về bài toán tìm đường đi tối ưu trên đồ thị cấu trúc.
Mặc dù đã chứng minh được hiệu quả thực nghiệm trên nhiều bài toán, các thuật toán ACO phổ biến như Hệ đàn kiến (Ant Colony System - ACS) và Hệ kiến Max-Min (Max-Min Ant System - MMAS) vẫn tồn tại những hạn chế kỹ thuật đáng kể:
- Người dùng buộc phải tìm trước một lời giải đủ tốt bằng phương pháp heuristic, sau đó căn cứ vào giá trị hàm mục tiêu của lời giải này để xác định cận trên ($\tau_{max}$) và cận dưới ($\tau_{min}$) của vết mùi;
- Lượng mùi cập nhật cho mỗi thành phần trên đồ thị tỷ lệ với giá trị hàm mục tiêu của lời giải, dẫn đến việc thiết lập hàm tính lượng mùi phụ thuộc chặt chẽ vào từng bài toán cụ thể;
- Việc điều chỉnh và cân bằng giữa tính khai thác (exploitation) quanh lời giải tốt nhất đã biết và tính khám phá (exploration) các vùng không gian tìm kiếm mới chưa được tối ưu hóa một cách trực quan và khái quát.
Khoảng trống nghiên cứu này đòi hỏi phải có những phân tích toán học chi tiết về quy luật biến thiên của vết mùi, từ đó xây dựng các quy tắc cập nhật mùi mới đơn giản hơn, giảm bớt sự phụ thuộc vào tham số bài toán, đồng thời ứng dụng giải quyết các bài toán NP-khó trong lĩnh vực tin sinh học (bioinformatics).
Mục tiêu nghiên cứu
Mục tiêu tổng quát của luận án được xác định gồm hai nội dung chính:
- 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.
- Đề xuất các thuật toán giải một số bài toán thời sự trong tối ưu tổ hợp và xử lý dữ liệu sinh học.
Đối tượng và phạm vi nghiên cứu
- Đối tượng nghiên cứu:
- Cơ chế học tăng cường, hành vi biến thiên của vết mùi và các quy tắc cập nhật mùi trong thuật toán tối ưu đàn kiến (AS, ACS, MMAS);
- Các thuật toán đề xuất: Quy tắc cập nhật mùi đa mức (MLAS), Max-Min trơn (SMMAS), 3 mức (3-LAS);
- Các thuật toán ứng dụng chuyên biệt: Thuật toán ACOHAP (suy diễn Haplotype), Thuật toán ACOSeeD (tìm tập hạt giống tối ưu), Thuật toán ACOSVM và GASVM (tối ưu hóa tham số mô hình Support Vector Machine).
- Phạm vi không gian và dữ liệu thực nghiệm:
- Bài toán đối chuẩn chuẩn hóa (benchmarks): Bài toán người chào hàng (TSP), Bài toán quy hoạch toàn phương nhị phân không ràng buộc (UBQP), Bài toán lập lịch sản xuất (JSS);
- Dữ liệu suy diễn Haplotype: 32 bộ dữ liệu kiểm thử chuẩn và bộ dữ liệu thực tế CEU (nhiễm sắc thể số 20 của quần thể người da trắng châu Âu tại Utah);
- Dữ liệu tương đồng chuỗi sinh học: Các chuỗi so khớp nhị phân với các mức tương đồng $p$ khác nhau ở quy mô nhỏ, trung bình và lớn;
- Dữ liệu điều hòa gen: Tập dữ liệu liên kết yếu tố phiên mã (Transcription Factors - TFs) trong quá trình phát triển phôi của ruồi giấm Drosophila.
- Phạm vi học thuật và thời gian: Luận án tiến sĩ chuyên ngành Khoa học máy tính (Mã số: 62.01), thực hiện tại Trường Đại học Công nghệ – Đại học Quốc gia Hà Nội, bảo vệ năm 2012 dưới sự hướng dẫn khoa học của PGS. Hoàng Xuân Huấn.
Tổng quan tài liệu và vị trí của luận án
Các hướng nghiên cứu tiền đề được điểm lại
Luận án hệ thống hóa các công trình nghiên cứu nền tảng về tối ưu tổ hợp và phương pháp đàn kiến:
- Dorigo (1991): Khởi xướng mô hình Hệ kiến (Ant System - AS) áp dụng đầu tiên cho bài toán TSP, thiết lập nền tảng cho việc sử dụng vết mùi nhân tạo và hành vi bầy đàn trong tối ưu hóa;
- Dorigo & Gambardella (1997): Đề xuất Hệ đàn kiến (ACS) với ba cải tiến: áp dụng quy tắc chuyển trạng thái dựa trên thông tin tích lũy mạnh hơn, cập nhật mùi toàn cục chỉ trên đường đi tốt nhất ($G\text{-}best$), và cập nhật mùi cục bộ nhằm giảm nồng độ pheromone trên các cạnh vừa đi qua để kích thích khám phá;
- Stützle & Hoos (2000): Phát triển Hệ kiến Max-Min (MMAS) với bốn đặc điểm: chỉ cho phép lời giải tốt nhất trong lần lặp ($I\text{-}best$) hoặc tốt nhất toàn cục ($G\text{-}best$) cập nhật mùi, giới hạn vết mùi trong đoạn $[\tau_{min}, \tau_{max}]$, khởi tạo giá trị vết mùi ban đầu bằng $\tau_{max}$, và khởi tạo lại vết mùi khi thuật toán bị tắc nghẽn;
- Gutjahr (2002, 2003): Chứng minh tính hội tụ của thuật toán MMAS không có thông tin heuristic về mặt xác suất bằng mô hình xích Markov không thuần nhất;
- Stützle & Dorigo (2002): Phân tích và chứng minh tính chất hội tụ của vết mùi trong MMAS và mở rộng suy luận cho ACS;
- Gusfield (2003): Đề xuất tiêu chuẩn Pure Parsimony trong bài toán suy diễn Haplotype (HIPP - Haplotype Inference by Pure Parsimony), chứng minh bài toán thuộc lớp NP-khó;
- Gaspero & Roli (2008): Đề xuất kỹ thuật tìm kiếm cục bộ dựa trên cấu trúc lân cận khoảng cách 1-Hamming (1-Hamming distance neighborhood);
- Li và cộng sự (2004), Sun & Buhler (2005): Nghiên cứu các phương pháp heuristic tham lam và giải thuật leo đồi cho bài toán tìm tập hạt giống có cách tối ưu;
- Ilie và cộng sự (2011, 2012): Đề xuất hàm xấp xỉ độ phức tạp chồng lắp (Overlap Complexity - OC) và phát triển các phần mềm SpEED, SpEEDfast để tối ưu hóa độ nhạy của tập hạt giống.
Khoảng trống luận án lựa chọn giải quyết
- Khắc phục tính phức tạp và sự phụ thuộc tham số trong quy tắc cập nhật mùi của MMAS và ACS, loại bỏ nhu cầu thiết lập hàm tính lượng mùi theo giá trị mục tiêu cụ thể của từng bài toán;
- Giải quyết bài toán suy diễn Haplotype quy mô lớn theo tiêu chuẩn Pure Parsimony bằng cách thiết kế đồ thị cấu trúc dạng cây nhị phân động;
- Khắc phục nhược điểm của các giải pháp tìm kiếm hạt giống sinh học hiện hành (chỉ dùng leo đồi đơn giản trên hàm xấp xỉ OC) bằng việc xây dựng quy trình hai giai đoạn tích hợp ACO và tìm kiếm cục bộ;
- Xây dựng lược đồ tự động tối ưu hóa tham số cho mô hình Support Vector Machine (SVM) trong bài toán dự đoán điều hòa gen.
Cơ sở lý thuyết và phương pháp nghiên cứu
Khung lý thuyết và mô hình toán học
Luận án thiết lập khung hình thức hóa cho bài toán tối ưu tổ hợp tổng quát và mô hình ACO:
-
Phát biểu bài toán TƯTH tổng quát: Bài toán TƯTH cực tiểu hóa được biểu diễn dưới dạng bộ ba $(S, f, \Omega)$:
- $S$: Tập hữu hạn các trạng thái (các phương án hoặc lời giải tiềm năng);
- $f$: Hàm mục tiêu xác định trên $S$ ($f: S \to \mathbb{R}$);
- $\Omega$: Tập hợp các ràng buộc của bài toán. Mỗi phương án $s \in S$ thỏa mãn các ràng buộc $\Omega$ được gọi là phương án chấp nhận được. Tồn tại tập hữu hạn các thành phần $C = {c_1, c_2, \dots, c_n}$ sao cho mọi phương án đều biểu diễn được qua các liên kết tuần tự của các thành phần này.
-
Đồ thị cấu trúc của bài toán TƯTH: Đồ thị cấu trúc được định nghĩa là $G = (V, E, \eta, \tau)$:
- $V$: Tập đỉnh, mỗi đỉnh tương ứng với một thành phần trong $C$;
- $E$: Tập các cạnh định hướng các bước mở rộng hợp lệ;
- $\eta$: Vector trọng số heuristic biểu thị thông tin kinh nghiệm ($\eta_{ij} > 0$);
- $\tau$: Vector nồng độ vết mùi biểu thị thông tin học tăng cường ($\tau_{ij} > 0$, khởi tạo bằng $\tau_0$).
-
Quy tắc xác suất chuyển trạng thái: Khi kiến đang ở trạng thái thành phần mở rộng $s$, xác suất để kiến chọn đỉnh $c_j \in N(s)$ (tập các đỉnh hợp lệ tiếp theo) được xác định theo công thức: $$P(c_j | s) = \frac{[\tau_{ij}]^\alpha \cdot [\eta_{ij}]^\beta}{\sum_{c_k \in N(s)} [\tau_{ik}]^\alpha \cdot [\eta_{ik}]^\beta}$$ Trong đó, $\alpha$ và $\beta$ là hai tham số dương điều khiển mức độ ảnh hưởng tương đối giữa vết mùi $\tau$ và thông tin heuristic $\eta$.
Phương pháp nghiên cứu
- Phương pháp phân tích lý thuyết toán học: Sử dụng giải tích toán học và xác suất thống kê để khảo sát giới hạn hội tụ của vết mùi trên các cạnh thuộc và không thuộc tập lời giải tối ưu $s^*$, chứng minh các mệnh đề về tính bất biến của thuật toán qua các phép biến đổi đơn điệu tăng;
- Phương pháp mô phỏng thuật toán metaheuristic: Thiết kế cấu trúc đồ thị động, lập trình giải thuật trên máy tính, tích hợp các thuật toán tìm kiếm cục bộ (local search);
- Phương pháp thực nghiệm đối chuẩn (Benchmarking): Thực hiện thử nghiệm lặp nhiều lần trên các tập dữ liệu chuẩn quốc tế và tập dữ liệu sinh học thực tế, so sánh kết quả trực tiếp với các thuật toán chuyên dụng tốt nhất cùng thời điểm.
Nguồn tư liệu và dữ liệu nghiên cứu
| Lĩnh vực / Bài toán | Tên bộ dữ liệu | Đặc điểm / Quy mô dữ liệu | Nguồn tham chiếu |
|---|---|---|---|
| Tối ưu tổ hợp kinh điển | TSPLIB / UBQP Lib | Các đồ thị đối xứng và ma trận trọng số chuẩn | TSPLIB, bài toán JSS chuẩn |
| Suy diễn Haplotype | 32 Benchmark Test & CEU Dataset | 32 bài toán mẫu và nhiễm sắc thể 20 của người da trắng châu Âu tại Utah | Quần thể HapMap CEU |
| So khớp chuỗi sinh học | Chuỗi so khớp nhị phân | Các chuỗi độ dài $L$ với mức tương đồng $p \in [0.65, 0.90]$ | Dữ liệu đối chuẩn của SpEED |
| Điều hòa biểu hiện gen | Drosophila Embryo Dataset | Liên kết yếu tố phiên mã (TFs) trong phát triển phôi ruồi giấm | Dữ liệu sinh học phân tử Drosophila |
Nội dung chính theo từng chương
Chương 1: Bài toán tối ưu tổ hợp tổng quát
Chương 1 thiết lập cơ sở toán học hình thức cho toàn bộ luận án:
- Trình bày dạng tổng quát của bài toán TƯTH dưới dạng tìm kiếm vector có độ dài không quá $n$ trên đồ thị đầy đủ có các đỉnh được gán nhãn trong tập thành phần $C$;
- Phân tích các tiếp cận giải quyết bài toán NP-khó: Heuristic xây dựng, tìm kiếm cục bộ và thuật toán metaheuristic mô phỏng tự nhiên;
- Trình bày chi tiết hai bài toán minh họa kinh điển: Bài toán người chào hàng (TSP) và Bài toán quy hoạch toàn phương nhị phân không ràng buộc (UBQP).
Chương 2: Phương pháp tối ưu đàn kiến
Chương 2 tổng hợp nguyên lý hoạt động của đàn kiến tự nhiên và mô hình hóa toán học cho đàn kiến nhân tạo:
- Cơ chế sinh học: Đàn kiến thực trao đổi thông tin gián tiếp thông qua việc tiết chất hóa học pheromone lên đường đi; kiến có xu hướng chọn các tuyến đường có nồng độ pheromone cao hơn, dẫn đến việc tìm ra đường đi ngắn nhất giữa tổ và nguồn thức ăn.
- Mô hình kiến nhân tạo: Được xây dựng dưới dạng hệ đa tác tử (multi-agent), trong đó mỗi kiến nhân tạo có bộ nhớ riêng để ghi nhận các đỉnh đã đi qua, có khả năng tính toán độ dài hành trình và thực hiện cập nhật vết mùi.
- Quy trình tổng quát của thuật toán ACO:
- Khởi tạo tham số, ma trận vết mùi ban đầu $\tau_0$;
- Mỗi con kiến xây dựng lời giải từng bước dựa trên quy tắc xác suất kết hợp giữa vết mùi và thông tin heuristic;
- Cập nhật vết mùi (bao gồm cơ chế bay hơi mùi và bổ sung mùi mới theo chất lượng lời giải);
- Cập nhật lời giải tốt nhất qua các vòng lặp cho đến khi thỏa mãn điều kiện dừng.
- Hệ thống hóa các thuật toán kinh điển: Phân tích chi tiết ba biến thể chính gồm Hệ kiến (AS), Hệ đàn kiến (ACS) và Hệ kiến Max-Min (MMAS); điểm lại các kết quả chứng minh tính hội tụ xác suất của Gutjahr và Stützle - Dorigo.
Chương 3: Tính biến thiên của vết mùi và các thuật toán mới
Chương này trình bày các phân tích toán học về sự biến thiên nồng độ pheromone và các đóng góp cốt lõi về mặt thuật toán của luận án:
- Phân tích toán học:
- Khảo sát sự mất cân bằng giữa tính khai thác và tính khám phá. Khi số bước lặp đủ lớn, xác suất chọn các cạnh không thuộc lời giải tốt nhất giảm nhanh về 0 do hiện tượng bay hơi mùi, khiến thuật toán dễ rơi vào cực trị địa phương.
- Trong bài toán TSP không định hướng, một chu trình Hamilton qua cạnh $(i, j)$ và không qua cạnh $(r, s)$ có thể đổi nhiều nhất 7 cạnh để thu được chu trình đi qua $(r, s)$ mà không qua $(i, j)$. Điều này chứng minh rằng việc đánh giá chất lượng cạnh ở các bước đầu mang tính ngẫu nhiên cao.
- Đề xuất ba quy tắc cập nhật mùi mới:
- Quy tắc cập nhật mùi đa mức (MLAS - Multi-Level Ant System): Thiết lập các mức mùi trung gian $\tau_1, \tau_2, \dots$ thay vì chỉ cho bay hơi đơn thuần, cho phép kiểm soát độ lệch mùi để điều hòa tốc độ hội tụ.
- Quy tắc Max-Min trơn (SMMAS - Smooth Max-Min Ant System): Cập nhật vết mùi theo công thức: $$\tau_{ij}(t+1) = (1-\rho)\tau_{ij}(t) + \rho \cdot \Delta \tau_{ij}(t)$$ với: $$\Delta \tau_{ij}(t) = \begin{cases} 1 & \text{nếu } (i, j) \in s^{best} \ \tau_{min}/\tau_{max} & \text{nếu } (i, j) \notin s^{best} \end{cases}$$ Khi cài đặt, luận án chuẩn hóa $\tau_{max} = 1$ và chỉ cần chọn tỷ lệ $\tau_{min}/\tau_{max} \in (0, 1)$, loại bỏ hoàn toàn việc tính toán hàm mục tiêu phức tạp cho lượng mùi bổ sung.
- Quy tắc 3 mức (3-LAS - Three-Level Ant System): Bổ sung mức mùi thứ ba dành cho các cạnh được kiến lựa chọn trong bước lặp hiện tại nhưng không thuộc lời giải tốt nhất toàn cục, phù hợp cho các bài toán mà thông tin heuristic có ảnh hưởng chi phối.
- Tính bất biến của thuật toán: Luận án chứng minh rằng nếu hai thể hiện bài toán $P_1$ và $P_2$ có hàm mục tiêu liên hệ qua phép biến đổi đơn điệu tăng chặt $f_2(s) = g(f_1(s))$, thì khi giải bằng SMMAS hoặc 3-LAS với cùng bộ số ngẫu nhiên, thuật toán sẽ sinh ra cùng một dãy lời giải và vector vết mùi.
- Kết quả thực nghiệm trên TSP và UBQP: SMMAS cho kết quả tương đương MLAS và 3-LAS, đồng thời vượt trội hơn thuật toán MMAS truyền thống về tính ổn định và thời gian thiết lập tham số.
Chương 4: Thuật toán ACOHAP giải bài toán suy diễn Haplotype
Chương 4 áp dụng thuật toán đàn kiến giải bài toán HIPP trong tin sinh học:
- Mô hình toán học:
- Một Genotype độ dài $m$ biểu diễn bằng xâu trên bảng chữ cái ${0, 1, 2}$ ($0$: đồng hợp tử kiểu dại, $1$: đồng hợp tử biến dị, $2$: dị hợp tử).
- Một Haplotype biểu diễn bằng xâu nhị phân ${0, 1}$. Cặp Haplotype $(h_1, h_2)$ giải thích Genotype $g$ nếu tại mọi vị trí $j$: nếu $g[j]=0$ thì $h_1[j]=h_2[j]=0$; nếu $g[j]=1$ thì $h_1[j]=h_2[j]=1$; nếu $g[j]=2$ thì $(h_1[j]=0, h_2[j]=1)$ hoặc $(h_1[j]=1, h_2[j]=0)$.
- Bài toán HIPP: Cho danh sách $n$ Genotype, tìm tập Haplotype có kích thước nhỏ nhất để giải thích toàn bộ $n$ Genotype này.
- Thuật toán ACOHAP:
- Đồ thị cấu trúc động: Biểu diễn dưới dạng cây con của cây nhị phân đầy đủ độ sâu $m$. Để tránh bùng nổ tổ hợp, mỗi con kiến chỉ hiển thị động một cây con tương ứng với quá trình xây dựng lời giải, mỗi nút chứa danh sách kết hợp các Haplotype đang xây dựng.
- Thủ tục xây dựng lời giải: Lần lượt duyệt qua từng vị trí, xử lý cố định cho các vị trí đồng hợp tử và áp dụng quy tắc xác suất ACO cho các vị trí dị hợp tử.
- Quy tắc cập nhật mùi: Áp dụng quy tắc SMMAS.
- Tìm kiếm cục bộ: Tích hợp thuật toán tìm kiếm cục bộ trên không gian lân cận khoảng cách 1-Hamming của Gaspero & Roli.
- Kết quả thực nghiệm: Thử nghiệm trên 32 bộ dữ liệu benchmark chuẩn và tập dữ liệu thực tế CEU (nhiễm sắc thể số 20). Kết quả cho thấy ACOHAP đạt chất lượng lời giải tối ưu tương đương với thuật toán giải đúng RPoly và vượt trội hơn phương pháp xấp xỉ Collhap.
Chương 5: Thuật toán ACOSeeD tìm tập hạt giống có cách tối ưu
Chương 5 nghiên cứu bài toán so khớp chuỗi sinh học cục bộ:
- Mô hình bài toán:
- Miền tương đồng được mô hình hóa bằng chuỗi nhị phân $R$ độ dài $L$, trong đó ký tự $1$ thể hiện vị trí khớp (match) với xác suất $p$ (mức tương đồng) và ký tự $0$ thể hiện không khớp (mismatch).
- Hạt giống có cách (spaced seed) là xâu ký tự trên ${1, }$, với $1$ là vị trí bắt buộc khớp và $$ là vị trí tùy ý. Số lượng ký tự $1$ là trọng số (weight) của hạt giống.
- Mục tiêu: Tìm tập gồm $k$ hạt giống có cùng trọng số $W$ sao cho xác suất để ít nhất một hạt giống khớp đúng với chuỗi $R$ (gọi là độ nhạy - sensitivity) đạt cực đại.
- Thuật toán ACOSeeD:
- Cơ chế hai giai đoạn: Giai đoạn 1 sử dụng đồ thị cấu trúc dạng lưới cột để xác định độ dài tối ưu cho từng hạt giống trong khoảng $[l_{min}, l_{max}]$; Giai đoạn 2 sử dụng đồ thị cấu trúc tọa độ 3 chiều để xây dựng cấu trúc chi tiết của các hạt giống.
- Kết hợp hàm mục tiêu xấp xỉ: Do việc tính toán độ nhạy chính xác tốn nhiều thời gian, thuật toán sử dụng hàm xấp xỉ độ phức tạp chồng lắp (Overlap Complexity - OC) để định hướng tìm kiếm cục bộ nhanh, sau đó mới tính độ nhạy chính xác trên lời giải sau cải tiến để cập nhật mùi theo quy tắc SMMAS.
- Kết quả thực nghiệm: Thử nghiệm trên các tập dữ liệu chuỗi sinh học từ quy mô nhỏ, trung bình đến lớn. ACOSeeD cho kết quả vượt trội so với các phần mềm SpEED và SpEEDfast, tìm ra nhiều tập hạt giống mới có độ nhạy cao hơn các công bố trước đó.
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
Chương 6 mở rộng phạm vi ứng dụng sang bài toán học máy trong sinh học phân tử:
- Bối cảnh bài toán: Dự đoán hoạt động điều hòa biểu hiện gen thông qua các yếu tố phiên mã (TFs) trong quá trình phát triển phôi của ruồi giấm Drosophila.
- Mô hình hóa: Sử dụng phương pháp máy vector hỗ trợ (Support Vector Machine - SVM). Hiệu năng phân loại của SVM phụ thuộc quyết định vào việc lựa chọn bộ tham số tối ưu (như tham số phạt $C$ và tham số hàm nhân $\gamma$).
- Phương pháp đề xuất: Luận án xây dựng thuật toán di truyền GASVM và thuật toán tối ưu đàn kiến ACOSVM để tự động tìm kiếm bộ siêu tham số tối ưu cho SVM.
- Kết quả: Lược đồ kết hợp ACOSVM giúp nâng cao độ chính xác dự báo hoạt động điều hòa gen trên dữ liệu thực nghiệm so với các thiết lập SVM mặc định.
Kết quả và những đóng góp mới
Đóng góp mới về mặt lý luận và phương pháp
- Phân tích toán học về biến thiên vết mùi: Làm rõ bản chất của sự mất cân bằng giữa tính khám phá và tính khai thác trong các thuật toán ACO truyền thống khi số vòng lặp tăng dần.
- Hệ thống quy tắc cập nhật mùi mới (MLAS, SMMAS, 3-LAS):
- Đơn giản hóa quá trình cài đặt thuật toán bằng cách loại bỏ việc tính toán lượng mùi bổ sung dựa trên hàm mục tiêu cụ thể của từng bài toán;
- Chuẩn hóa $\tau_{max} = 1$ và chuyển việc chọn tham số về việc xác định tỷ lệ đơn giản $\tau_{min}/\tau_{max}$;
- Chứng minh về mặt toán học tính bất biến của thuật toán SMMAS và 3-LAS đối với các phép biến đổi đơn điệu tăng chặt của hàm mục tiêu.
Đóng góp mới về mặt ứng dụng thực tiễn
- Thuật toán ACOHAP cho bài toán HIPP: Xây dựng đồ thị cấu trúc dạng cây con nhị phân động, tích hợp tìm kiếm cục bộ 1-Hamming, giải quyết hiệu quả bài toán suy diễn Haplotype trên dữ liệu bộ gen quy mô lớn.
- Thuật toán ACOSeeD cho bài toán tìm tập hạt giống tối ưu: Thiết kế thành công thuật toán ACO hai giai đoạn (xác định độ dài và xây dựng cấu trúc hạt giống), tích hợp hàm xấp xỉ OC để nâng cao tốc độ tìm kiếm cục bộ, tạo ra công cụ tìm kiếm tập hạt giống có độ nhạy vượt trội hơn SpEED và SpEEDfast.
- Lược đồ ACOSVM và GASVM: Ứng dụng thuật toán đàn kiến và thuật toán di truyền để tối ưu hóa tham số mô hình SVM trong bài toán dự đoán liên kết yếu tố phiên mã ở ruồi giấm Drosophila.
Hạn chế và hướng nghiên cứu tiếp
Hạn chế được ghi nhận từ văn bản
- Quy tắc cập nhật mùi đa mức (MLAS) tuy có triển vọng trên lý thuyết nhưng việc điều khiển động khoảng cách chênh lệch giữa các mức mùi trong các bài toán thực tế gặp nhiều khó khăn, dẫn đến việc phải thay thế bằng quy tắc SMMAS hoặc 3-LAS;
- Chi phí tính toán của hàm mục tiêu chính xác (như tính độ nhạy của tập hạt giống hoặc suy diễn Haplotype đầy đủ) vẫn rất lớn đối với dữ liệu siêu quy mô, buộc thuật toán phải phụ thuộc vào các hàm đánh giá xấp xỉ (như hàm OC) trong pha tìm kiếm cục bộ;
- Các tham số cấu hình như số lượng kiến, hệ số bay hơi mùi $\rho$, hệ số ảnh hưởng $\alpha$ và $\beta$ vẫn cần được lựa chọn dựa trên kinh nghiệm thực nghiệm đối với từng bài toán cụ thể.
Hướng nghiên cứu tiếp
- Mở rộng ứng dụng quy tắc cập nhật mùi SMMAS cho các lớp bài toán tối ưu tổ hợp phức tạp khác trong công nghiệp và quản trị mạng;
- Nghiên cứu phát triển các cơ chế tự động thích nghi tham số ($\alpha, \beta, \rho$) trong quá trình thực thi thuật toán;
- Tối ưu hóa cấu trúc đồ thị động và mở rộng khả năng song song hóa thuật toán trên các hệ thống tính toán hiệu năng cao.
Giá trị tham khảo
Luận án là tài liệu tham khảo chuyên sâu cho các đối tượng sau:
- Nghiên cứu sinh và học viên cao học ngành Khoa học máy tính, Công nghệ thông tin và Toán ứng dụng: Có thể tham khảo phương pháp phân tích toán học về tính hội tụ của vết mùi trong metaheuristic, cũng như cách thiết kế và chứng minh các quy tắc cập nhật mùi mới tại Chương 3.
- Các nhà nghiên cứu trong lĩnh vực Tin sinh học (Bioinformatics): Cung cấp các mô hình hình thức hóa chi tiết và giải pháp thuật toán hoàn chỉnh cho hai bài toán quan trọng là suy diễn Haplotype (Chương 4) và tìm tập hạt giống có cách tối ưu cho so khớp chuỗi sinh học (Chương 5).
- Kỹ sư phát triển phần mềm tối ưu hóa và học máy: Cung cấp lược đồ tham khảo thực tế về việc kết hợp thuật toán metaheuristic (ACO, GA) với các thuật toán học máy giám sát (SVM) để tự động tinh chỉnh siêu tham số (Chương 6).
Câu hỏi thường gặp
1. Quy tắc cập nhật mùi SMMAS có điểm gì khác biệt cốt lõi so với quy tắc MMAS truyền thống?
Trong thuật toán MMAS truyền thống, người dùng phải tìm một lời giải ban đầu đủ tốt để tính toán cận $\tau_{max}, \tau_{min}$ và phải xây dựng hàm tính lượng mùi bổ sung tỷ lệ với giá trị hàm mục tiêu của bài toán. Ngược lại, quy tắc SMMAS chuẩn hóa cố định $\tau_{max} = 1$, chỉ yêu cầu người dùng xác định tỷ lệ $\tau_{min}/\tau_{max} \in (0, 1)$ và gán lượng mùi bổ sung bằng $1$ cho cạnh thuộc lời giải tốt nhất và bằng $\tau_{min}/\tau_{max}$ cho các cạnh còn lại. Điều này giúp loại bỏ việc tính toán hàm mục tiêu khi cập nhật mùi và giữ nồng độ mùi luôn nằm trong khoảng giới hạn một cách tự nhiên.
2. Bài toán suy diễn Haplotype theo tiêu chuẩn Pure Parsimony (HIPP) được định nghĩa như thế nào?
Bài toán HIPP xuất phát từ dữ liệu kiểu gen (Genotype) của các sinh vật lưỡng bội. Mỗi Genotype là một xâu ký tự ${0, 1, 2}$ (trong đó $0$ và $1$ là đồng hợp tử, $2$ là dị hợp tử). Bài toán yêu cầu tìm một tập hợp gồm số lượng tối thiểu các xâu Haplotype nhị phân ${0, 1}$ sao cho mỗi Genotype trong tập dữ liệu ban đầu đều được giải thích bởi một cặp Haplotype trong tập tìm được. Đây là bài toán thuộc lớp NP-khó.
3. Thuật toán ACOHAP xử lý vấn đề bùng nổ không gian trạng thái trên cây nhị phân ra sao?
Cây nhị phân đầy đủ biểu diễn tất cả các Haplotype độ dài $m$ có $2^m$ nút lá, dẫn đến bùng nổ tổ hợp khi $m$ lớn. Để khắc phục, ACOHAP sử dụng mô hình đồ thị cấu trúc động: mỗi con kiến chỉ khởi tạo và hiển thị một cây con được trích xuất trong quá trình xây dựng lời giải. Cây con này có tối đa $2k$ nút lá tương ứng với số lượng Haplotype cần tìm để giải thích $k$ Genotype, giúp giảm thiểu đáng kể bộ nhớ và không gian tìm kiếm.
4. Thuật toán ACOSeeD giải quyết bài toán tìm tập hạt giống khi chưa biết trước độ dài như thế nào?
Khi độ dài các hạt giống chưa được xác định trước mà nằm trong khoảng $[l_{min}, l_{max}]$, ACOSeeD áp dụng cấu trúc đồ thị hai giai đoạn. Ở giai đoạn đầu, kiến di chuyển trên một đồ thị lưới gồm $k$ cột (mỗi cột có các nút được đánh số từ $l_{min}$ đến $l_{max}$) để xác định dãy độ dài tăng dần cho $k$ hạt giống. Sau khi đã xác định được độ dài, kiến chuyển sang đồ thị cấu trúc 3 chiều ở giai đoạn hai để xây dựng cấu trúc các vị trí khớp ($1$) và vị trí tùy ý ($*$) cho từng hạt giống.
5. Vai trò của hàm xấp xỉ Overlap Complexity (OC) trong thuật toán ACOSeeD là gì?
Hàm tính độ nhạy chính xác của một tập hạt giống đòi hỏi thời gian tính toán rất lớn. Do đó, ACOSeeD sử dụng hàm xấp xỉ độ phức tạp chồng lắp OC (Overlap Complexity) làm hàm mục tiêu nhanh để định hướng các bước biến đổi trong thủ tục tìm kiếm cục bộ. Sau khi tìm kiếm cục bộ kết thúc, thuật toán mới tính độ nhạy chính xác của tập hạt giống để đánh giá và cập nhật vết mùi SMMAS, giúp tối ưu hóa tổng thời gian chạy của chương trình.
Kết luận
Luận án "Phương pháp tối ưu đàn kiến và ứng dụng" của tác giả Đỗ Đức Đông đã hoàn thành các mục tiêu nghiên cứu đề ra thông qua việc phân tích toán học hành vi vết mùi và đề xuất các quy tắc cập nhật mùi mới (đặc biệt là quy tắc SMMAS với tính chất bất biến toán học và quy trình cài đặt tham số tối giản). Các thuật toán phát triển trong luận án (ACOHAP, ACOSeeD, ACOSVM) đã giải quyết hiệu quả các bài toán tối ưu tổ hợp NP-khó trong lĩnh vực tin sinh học bao gồm suy diễn Haplotype, tối ưu hóa hạt giống so khớp chuỗi sinh học và dự đoán điều hòa gen. Các kết quả thực nghiệm đối chuẩn trên dữ liệu quốc tế và dữ liệu thực tế khẳng định tính chính xác, hiệu năng tính toán và giá trị ứng dụng của các giải pháp mà luận án đề xuất.