Phương Pháp ACO Trong Giải Bài Toán Xâu Gần Nhất

Khám phá luận văn thạc sĩ về bài toán xâu gần nhất và phương pháp ACO 04, ứng dụng trong tối ưu hóa và giải quyết vấn đề phức tạp.

• Người hướng dẫn: TS. Phạm Quang Dũng
• Trường học: Đại Học Quốc Gia Hà Nội
• Chuyên ngành: Công Nghệ Thông Tin
• Đề tài: Phương Pháp Tối Ưu Đàn Kiến Trong Giải Bài Toán Xâu Gần Nhất
• Loại tài liệu: Luận Văn Thạc Sĩ
• Năm xuất bản: 2014
• Địa điểm: Hà Nội

Mục lục chi tiết

• LỜI CẢM ƠN
• LỜI CAM ĐOAN
• DANH MỤC CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT
• DANH MỤC CÁC BẢNG
• DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ
• MỞ ĐẦU
• 1. 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
• 1.1. BÀI TOÁN XÂU GẦN NHẤT
• 1.1.1. Định nghĩa 1: Khoảng cách Hamming
• 1.1.2. Định nghĩa 2: Xâu gần nhất của một tập xâu
• 1.1.3. Xác định bài toán
• 1.2. MỘT SỐ PHƯƠNG PHÁP TIẾP CẬN
• 1.2.1. Heuristic cấu trúc
• 1.2.2. Tìm kiếm địa phương
• 1.2.3. Phương pháp Metaheuristic
• 1.2.4. Phương pháp Memetic
• 2. CHƯƠNG 2: PHƯƠNG PHÁP ACO
• 2.1. TỪ KIẾN TỰ NHIÊN ĐẾN KIẾN NHÂN TẠO
• 2.1.1. Con kiến tự nhiên
• 2.1.2. Kiến nhân tạo (Artificial Ant)
• 2.2. PHƯƠNG PHÁP ACO
• 2.2.1. Đồ thị cấu trúc
• 2.2.2. Đặc tả thuật toán ACO tổng quát
• 2.2.3. Một số vấn đề liên quan
• 2.2.3.1. Yếu tố hội tụ
• 2.2.3.2. Thực hiện song song
• 2.2.3.3. ACO kết hợp với tìm kiếm địa phương
• 2.2.3.4. Thông tin heuristic
• 2.2.3.5. Số lượng kiến
• 2.2.3.6. Hệ số bay hơi
• 2.2.3.7. Giới hạn vết mùi
• 2.2.3.8. Khởi tạo vết mùi
• 3. CHƯƠNG 3: CÁC PHƯƠNG PHÁP ACO GIẢI BÀI TOÁN XÂU GẦN NHẤT
• 3.1. THUẬT TOÁN ACOM-CSP
• 3.1.1. Thuật toán ACO-CSP
• 3.1.1.1. Đồ thị cấu trúc
• 3.1.1.2. Thủ tục bước ngẫu nhiên để tìm lời giải
• 3.1.1.3. Quy tắc cập nhật mùi
• 3.1.2. Thuật toán Memetic
• 3.2. THUẬT TOÁN TSIACO
• 3.2.1. Phương pháp phân đoạn cứng
• 3.2.2. Phương pháp phân đoạn mềm
• 3.2.3. Đặc tả thuật toán TSIACO giải bài toán CSP
• 3.3. THUẬT TOÁN TSIACO2-LS
• 4. CHƯƠNG 4: KẾT QUẢ THỰC NGHIỆM
• 4.1. CHƯƠNG TRÌNH
• 4.1.1. Quy trình thực hiện
• 4.1.2. Cài đặt ứng dụng
• 4.1.3. Chương trình
• 4.1.4. Các bước tiến hành thực nghiệm
• 4.2. CÀI ĐẶT THAM SỐ
• 4.3. CẤU HÌNH MÁY TÍNH
• 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
• 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
• 4.6. THỰC NGHIỆM SO SÁNH ACOM-CSP, TSIACO1, TSIACO2 VỚI Ant-CSP
• 4.6.1. So sánh hiệu quả và thời gian chạy với vòng lặp cho trước
• 4.6.2. So sánh hiệu quả các thuật toán với cùng thời gian chạy
• 4.7. THỰC NGHIỆM SO SÁNH ACOM-CSP, TSIACO2 VỚI TSIACO2-LS
• 4.7.1. So sánh hiệu quả và thời gian chạy với vòng lặp cho trước
• 4.7.1.1. Giả sử thời gian không hạn chế: Chọn N=30, Loop=2500
• 4.7.1.2. Giả sử thời gian không hạn chế: Chọn N=40, Loop=2500
• 4.7.1.3. Giả sử thời gian không hạn chế: Chọn N=50, Loop=2500
• 4.7.2. So sánh hiệu quả các thuật toán với cùng thời gian chạy
• TÀI LIỆU THAM KHẢO

Tóm tắt

I. Tổng Quan Bài Toán Xâu Gần Nhất Định Nghĩa Ứng Dụng

Bài toán xâu gần nhất (Closest String Problem - CSP) là một bài toán tối ưu tổ hợp quan trọng. Nó thuộc lớp bài toán phức tạp, NP-khó. Bài toán này có ứng dụng thực tế trong nhiều lĩnh vực, đặc biệt là trong tin sinh học để tìm kiếm motif trên các chuỗi sinh học. Về bản chất, CSP tìm một xâu sao cho khoảng cách Hamming lớn nhất từ nó đến các xâu trong tập đầu vào là nhỏ nhất. Một ví dụ điển hình về ứng dụng của bài toán xâu gần nhất là xác định các vùng bảo tồn trong các chuỗi DNA. Các vùng này thường có sự tương đồng cao và có thể được tìm thấy bằng cách giải bài toán xâu gần nhất. Theo nghiên cứu của Nguyễn Thanh Bình, CSP có tính ứng dụng cao và độ phức tạp tính toán đáng kể.

1.1. Định nghĩa Khoảng cách Hamming và Xâu Gần Nhất

Cho hai xâu x và y có cùng độ dài m, khoảng cách Hamming d_H(x, y) là số vị trí mà các ký tự tương ứng khác nhau. Xâu t là xâu gần nhất của tập xâu S nếu khoảng cách lớn nhất từ t đến bất kỳ xâu nào trong S là nhỏ nhất. Ví dụ, nếu S = {“AGGAA”, “AGGGA”, “GGGGA”} và t = “GGGGG”, thì d_H(t, S) = max{d_H(t, s_i) : s_i ∈ S}. Khoảng cách Hamming đóng vai trò then chốt trong việc định lượng sự khác biệt giữa các xâu.

1.2. Xác định Bài Toán Xâu Gần Nhất Nearest String Problem

Bài toán xâu gần nhất có đầu vào là một tập S gồm n xâu có cùng độ dài m. Mục tiêu là tìm một xâu t có độ dài m sao cho khoảng cách Hamming lớn nhất từ t đến bất kỳ xâu nào trong S là nhỏ nhất. Bài toán này có thể được biểu diễn dưới dạng bài toán tối ưu hóa: tìm t sao cho max{d_H(t, s_i) : s_i ∈ S} đạt giá trị nhỏ nhất. Độ phức tạp của thuật toán giải bài toán xâu gần nhất ảnh hưởng trực tiếp tới thời gian xử lý.

1.3. Ứng Dụng Của Bài Toán Xâu Gần Nhất Trong Tin Sinh Học

Bài toán xâu gần nhất có ứng dụng quan trọng trong tin sinh học, đặc biệt trong việc tìm kiếm motif (mẫu) trong các chuỗi sinh học như DNA và protein. Việc tìm kiếm các motif này giúp các nhà khoa học hiểu rõ hơn về chức năng và cấu trúc của các gen. Ngoài ra, bài toán xâu gần nhất còn được sử dụng trong việc string alignment, so sánh và sắp xếp các chuỗi sinh học để tìm ra các vùng tương đồng. Các thuật toán giải bài toán xâu gần nhất có thể được sử dụng để xác định các vùng bảo tồn trong các chuỗi DNA, giúp hiểu rõ hơn về quá trình tiến hóa và chức năng của gen.

II. Thách Thức Khi Giải Bài Toán Xâu Gần Nhất Độ Phức Tạp

Bài toán xâu gần nhất là một bài toán NP-khó, có nghĩa là không có thuật toán nào có thể giải nó một cách tối ưu trong thời gian đa thức. Điều này gây ra nhiều thách thức, đặc biệt khi xử lý dữ liệu lớn trong tin sinh học và các lĩnh vực liên quan. Các thuật toán xấp xỉ và metaheuristic thường được sử dụng để tìm kiếm giải pháp chấp nhận được trong thời gian hợp lý. Các phương pháp tìm kiếm cục bộ và giải thuật di truyền là những lựa chọn phổ biến. Theo tài liệu nghiên cứu, bài toán này đòi hỏi những thuật toán hiệu quả để xử lý trên máy tính do dung lượng dữ liệu tin sinh học thường rất lớn.

2.1. Tại Sao Bài Toán Xâu Gần Nhất Thuộc Lớp NP Khó

Tính chất NP-khó của bài toán xâu gần nhất xuất phát từ việc không có thuật toán nào có thể giải quyết nó một cách tối ưu trong thời gian đa thức đối với kích thước đầu vào. Điều này có nghĩa là thời gian tính toán có thể tăng lên theo cấp số nhân khi kích thước bài toán tăng lên. Do đó, việc tìm kiếm giải pháp tối ưu cho bài toán xâu gần nhất trở nên bất khả thi đối với các bộ dữ liệu lớn.

2.2. Ảnh Hưởng Của Độ Phức Tạp Lên Hiệu Năng Thuật Toán

Độ phức tạp NP-khó của bài toán xâu gần nhất ảnh hưởng trực tiếp đến hiệu năng của các thuật toán giải. Các thuật toán chính xác, như vét cạn, không thể áp dụng được cho các bộ dữ liệu lớn do thời gian chạy quá lớn. Do đó, cần sử dụng các thuật toán xấp xỉ hoặc metaheuristic để tìm kiếm các giải pháp chấp nhận được trong thời gian hợp lý. Việc đánh đổi giữa chất lượng giải pháp và thời gian tính toán là một vấn đề quan trọng khi lựa chọn thuật toán.

2.3. Các Phương Pháp Tiếp Cận Xấp Xỉ Cho Bài Toán

Để giải quyết bài toán xâu gần nhất trong thực tế, các phương pháp tiếp cận xấp xỉ thường được sử dụng. Các phương pháp này bao gồm tìm kiếm cục bộ, giải thuật di truyền, và các thuật toán dựa trên metaheuristic. Các thuật toán xấp xỉ không đảm bảo tìm được giải pháp tối ưu, nhưng chúng có thể tìm được các giải pháp gần tối ưu trong thời gian đa thức. Việc lựa chọn phương pháp xấp xỉ phù hợp phụ thuộc vào đặc điểm của bộ dữ liệu và yêu cầu về chất lượng giải pháp.

III. Phương Pháp Tối Ưu Đàn Kiến ACO Cho Bài Toán Xâu Gần Nhất

Phương pháp tối ưu đàn kiến (Ant Colony Optimization - ACO) là một metaheuristic được lấy cảm hứng từ hành vi tìm kiếm thức ăn của đàn kiến. Trong ACO, mỗi con kiến nhân tạo xây dựng một giải pháp bằng cách di chuyển trên một đồ thị, để lại pheromone trên các cạnh đã đi qua. Các con kiến khác sẽ có xu hướng chọn các cạnh có nồng độ pheromone cao hơn, tạo ra một cơ chế tự tăng cường để tìm kiếm giải pháp tốt. ACO đã được áp dụng thành công cho nhiều bài toán tối ưu tổ hợp, bao gồm cả bài toán xâu gần nhất.

3.1. Giới Thiệu Tổng Quan Về Thuật Toán Đàn Kiến ACO

Thuật toán đàn kiến (ACO) là một kỹ thuật tối ưu hóa dựa trên quần thể, lấy cảm hứng từ cách kiến thật tìm đường từ tổ đến nguồn thức ăn. Kiến sử dụng pheromone để đánh dấu đường đi, và các kiến khác có xu hướng đi theo đường có nồng độ pheromone cao hơn. Trong ACO, các "kiến nhân tạo" xây dựng giải pháp bằng cách di chuyển trên một đồ thị, để lại pheromone trên các cạnh. Quá trình này lặp lại cho đến khi tìm thấy một giải pháp tốt.

3.2. Cách ACO Áp Dụng Vào Bài Toán Xâu Gần Nhất String Alignment

Trong bài toán xâu gần nhất, ACO có thể được áp dụng bằng cách xem xét các vị trí trong các xâu là các đỉnh của đồ thị, và việc thay đổi ký tự tại một vị trí là một cạnh. Các con kiến sẽ di chuyển trên đồ thị này, thay đổi các ký tự trong các xâu để tìm ra một xâu trung tâm có khoảng cách Hamming nhỏ nhất đến tất cả các xâu trong tập đầu vào. Nồng độ pheromone trên các cạnh thể hiện mức độ "hấp dẫn" của việc thay đổi một ký tự cụ thể tại một vị trí cụ thể.

3.3. Ưu Điểm và Nhược Điểm Của ACO Trong CSP

Ưu điểm của ACO trong bài toán xâu gần nhất bao gồm khả năng tìm kiếm giải pháp tốt trong không gian tìm kiếm lớn, khả năng thích ứng với các bộ dữ liệu khác nhau, và khả năng kết hợp với các kỹ thuật tìm kiếm cục bộ để cải thiện chất lượng giải pháp. Nhược điểm bao gồm yêu cầu điều chỉnh tham số cẩn thận để đạt được hiệu quả tốt nhất, và khả năng bị mắc kẹt trong tìm kiếm cục bộ nếu không có cơ chế thoát ra khỏi các cực tiểu cục bộ.

IV. Các Phương Pháp ACO Cải Tiến Giải Bài Toán Xâu Gần Nhất

Nhiều biến thể của ACO đã được phát triển để cải thiện hiệu suất giải bài toán xâu gần nhất. Một số phương pháp tập trung vào việc cải thiện cách các con kiến xây dựng giải pháp, trong khi những phương pháp khác tập trung vào việc cải thiện cách pheromone được cập nhật. Các thuật toán như ACOM-CSP, TSIACO1 và TSIACO2 là những ví dụ về các phương pháp ACO cải tiến đã được đề xuất để giải bài toán xâu gần nhất. Theo nghiên cứu, thuật toán 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ó.

4.1. Thuật Toán ACOM CSP Tối Ưu Đàn Kiến Hai Pha

Thuật toán ACOM-CSP (An Efficient Two-phase Ant Colony Optimization Algorithm for the Closest String Problem) là một phương pháp ACO cải tiến sử dụng hai pha để giải bài toán xâu gần nhất. Trong pha đầu tiên, các con kiến xây dựng giải pháp ban đầu bằng cách chọn các ký tự từ các xâu đầu vào. Trong pha thứ hai, các con kiến tinh chỉnh giải pháp bằng cách sử dụng tìm kiếm cục bộ. ACOM-CSP được thiết kế để cân bằng giữa việc khám phá không gian tìm kiếm và việc khai thác các giải pháp tiềm năng.

4.2. Thuật Toán TSIACO1 và TSIACO2 Cập Nhật Pheromone Hai Giai Đoạn

Thuật toán TSIACO1 và TSIACO2 (Two-Stage updating pheromone for Invariant Ant Colony Optimization algorithm) là các phương pháp ACO cải tiến sử dụng hai giai đoạn cập nhật pheromone. Trong giai đoạn đầu tiên, pheromone được cập nhật dựa trên các giải pháp tốt nhất được tìm thấy bởi các con kiến. Trong giai đoạn thứ hai, pheromone được cập nhật dựa trên sự đa dạng của các giải pháp. TSIACO1 và TSIACO2 được thiết kế để tăng cường sự khám phá không gian tìm kiếm và tránh bị mắc kẹt trong các cực tiểu cục bộ.

4.3. Thuật Toán TSIACO2 LS Kết Hợp Tìm Kiếm Cục Bộ Để Tối Ưu

Thuật toán TSIACO2-LS là một cải tiến của TSIACO2 bằng cách tích hợp kỹ thuật tìm kiếm cục bộ vào giai đoạn thứ hai của thuật toán. Sau khi các con kiến đã xây dựng các giải pháp ban đầu, tìm kiếm cục bộ được áp dụng để tinh chỉnh các giải pháp này và tìm ra các giải pháp tốt hơn. TSIACO2-LS thường cho kết quả tốt hơn so với TSIACO2 do khả năng khai thác các giải pháp tiềm năng tốt hơn.

V. Kết Quả Thực Nghiệm So Sánh Hiệu Năng Các Thuật Toán

Các thuật toán ACO cải tiến, bao gồm ACOM-CSP, TSIACO1, TSIACO2 và TSIACO2-LS, đã được triển khai và thử nghiệm trên các bộ dữ liệu khác nhau để đánh giá hiệu suất của chúng. Các kết quả thực nghiệm cho thấy rằng TSIACO2-LS thường đạt được kết quả tốt nhất về chất lượng giải pháp, nhưng có thời gian chạy lâu hơn. ACOM-CSP có thời gian chạy nhanh hơn, nhưng chất lượng giải pháp có thể kém hơn so với TSIACO2-LS. Việc lựa chọn thuật toán phù hợp phụ thuộc vào sự cân bằng giữa chất lượng giải pháp và thời gian chạy.

5.1. Thiết Lập Thực Nghiệm và Bộ Dữ Liệu Sử Dụng

Các thực nghiệm được thực hiện trên một bộ dữ liệu gồm các xâu có độ dài khác nhau và số lượng xâu khác nhau. Các tham số của các thuật toán ACO, bao gồm số lượng kiến, hệ số bay hơi pheromone, và các tham số liên quan đến tìm kiếm cục bộ, được điều chỉnh để đạt được hiệu suất tốt nhất. Các kết quả được đánh giá dựa trên khoảng cách Hamming trung bình giữa xâu trung tâm tìm được và các xâu trong tập đầu vào, cũng như thời gian chạy của thuật toán.

5.2. So Sánh Kết Quả Thực Nghiệm và Đánh Giá

Kết quả thực nghiệm cho thấy rằng TSIACO2-LS thường đạt được khoảng cách Hamming trung bình thấp nhất, cho thấy chất lượng giải pháp tốt nhất. Tuy nhiên, TSIACO2-LS có thời gian chạy lâu hơn so với các thuật toán khác do phải thực hiện tìm kiếm cục bộ. ACOM-CSP có thời gian chạy nhanh nhất, nhưng chất lượng giải pháp có thể kém hơn so với TSIACO2-LS. TSIACO1 và TSIACO2 có hiệu suất trung bình giữa ACOM-CSP và TSIACO2-LS.

5.3. Ảnh Hưởng Của Tham Số Đến Hiệu Quả Thuật Toán

Các tham số của thuật toán ACO có ảnh hưởng đáng kể đến hiệu quả của thuật toán. Ví dụ, hệ số bay hơi pheromone ảnh hưởng đến sự cân bằng giữa khám phá và khai thác. Một hệ số bay hơi cao có thể dẫn đến việc thuật toán khám phá quá nhiều và không hội tụ được, trong khi một hệ số bay hơi thấp có thể dẫn đến việc thuật toán bị mắc kẹt trong các cực tiểu cục bộ. Việc điều chỉnh tham số cẩn thận là rất quan trọng để đạt được hiệu suất tốt nhất.

VI. Kết Luận và Hướng Phát Triển Của Phương Pháp ACO Trong CSP

Phương pháp tối ưu đàn kiến là một kỹ thuật hiệu quả để giải bài toán xâu gần nhất. Các biến thể cải tiến của ACO, như ACOM-CSP, TSIACO1, TSIACO2 và TSIACO2-LS, đã chứng minh khả năng tìm kiếm giải pháp tốt trong thời gian hợp lý. Tuy nhiên, vẫn còn nhiều hướng phát triển tiềm năng cho phương pháp ACO trong bài toán xâu gần nhất, bao gồm việc kết hợp với các kỹ thuật học máy, tối ưu hóa song song và tối ưu hóa đa mục tiêu.

6.1. Tóm Tắt Kết Quả Nghiên Cứu và Đóng Góp

Nghiên cứu này đã trình bày một tổng quan về các phương pháp ACO để giải bài toán xâu gần nhất, và so sánh hiệu suất của một số thuật toán cải tiến. Các kết quả thực nghiệm cho thấy rằng TSIACO2-LS là một thuật toán hiệu quả để tìm kiếm giải pháp chất lượng cao, nhưng có thời gian chạy lâu hơn. ACOM-CSP là một lựa chọn tốt nếu thời gian chạy là một yếu tố quan trọng. Nghiên cứu này đóng góp vào việc hiểu rõ hơn về các ưu điểm và nhược điểm của các phương pháp ACO khác nhau, và cung cấp hướng dẫn cho việc lựa chọn thuật toán phù hợp cho các ứng dụng cụ thể.

6.2. Hướng Nghiên Cứu và Phát Triển Trong Tương Lai

Trong tương lai, có nhiều hướng nghiên cứu tiềm năng cho phương pháp ACO trong bài toán xâu gần nhất. Một hướng là kết hợp ACO với các kỹ thuật học máy để tự động điều chỉnh các tham số của thuật toán. Một hướng khác là sử dụng tối ưu hóa song song để giảm thời gian chạy của thuật toán. Ngoài ra, có thể phát triển các thuật toán ACO để giải các biến thể phức tạp hơn của bài toán xâu gần nhất, chẳng hạn như bài toán tối ưu hóa đa mục tiêu.

6.3. Ứng Dụng Tiềm Năng và Ảnh Hưởng Đến Các Lĩnh Vực Liên Quan

Các thuật toán ACO để giải bài toán xâu gần nhất có tiềm năng ứng dụng rộng rãi trong nhiều lĩnh vực, bao gồm tin sinh học, khai phá dữ liệu, và phân tích chuỗi. Trong tin sinh học, chúng có thể được sử dụng để tìm kiếm motif trong các chuỗi DNA và protein, giúp hiểu rõ hơn về chức năng và cấu trúc của các gen. Trong khai phá dữ liệu, chúng có thể được sử dụng để tìm kiếm các mẫu trong các tập dữ liệu văn bản. Các thuật toán này có thể có ảnh hưởng đáng kể đến các lĩnh vực liên quan, giúp cải thiện hiệu quả của các ứng dụng và giải quyết các bài toán phức tạp hơn.

Nội dung chính

Tổng quan nghiên cứu

Bài toán xâu gần nhất (Closest String Problem - CSP) là một bài toán tối ưu tổ hợp kinh điển thuộc lớp NP-khó, đóng vai trò nền tảng trong lĩnh vực tin sinh học, đặc biệt là bài toán tìm kiếm motif di truyền và căn chỉnh chuỗi sinh học. Khi kích thước dữ liệu gen mở rộng với bộ ký tự nucleotide 4 phần tử gồm Adenine, Cytosine, Guanine và Thymine, không gian tìm kiếm bùng nổ theo hàm mũ $4^m$ (với $m$ là độ dài chuỗi), khiến các phương pháp duyệt toàn bộ hoàn toàn bất khả thi về mặt chi phí tính toán. Vấn đề cốt lõi mà nghiên cứu giải quyết là tìm ra một chuỗi mục tiêu có độ dài $m$ sao cho khoảng cách Hamming cực đại từ chuỗi đó đến tập hợp $n$ chuỗi cho trước đạt giá trị nhỏ nhất.

Mục tiêu cụ thể của luận văn là nghiên cứu, cải tiến và phát triển các biến thể thuật toán tối ưu đàn kiến (Ant Colony Optimization - ACO) hai pha nhằm nâng cao chất lượng tìm kiếm nghiệm gần đúng cho bài toán CSP. Nghiên cứu được thực hiện tại Trường Đại học Công nghệ - Đại học Quốc gia Hà Nội vào năm 2014, khảo sát trên các bộ dữ liệu mô phỏng sinh học chuẩn hóa có số lượng từ 10 đến 50 chuỗi và độ dài chuỗi biến thiên từ 100 đến 1000 ký tự.

Ý nghĩa khoa học và thực tiễn của công trình thể hiện qua việc nâng cấp quy tắc cập nhật vết mùi hai giai đoạn và tích hợp kỹ thuật tìm kiếm địa phương, giúp hạ thấp khoảng cách Hamming trung bình từ 8% đến 15% so với thuật toán Ant-CSP truyền thống. Kết quả nghiên cứu cung cấp một giải pháp tính toán hiệu năng cao, mở ra hướng ứng dụng tin cậy trong việc xử lý các tập dữ liệu chuỗi DNA/RNA quy mô lớn với thời gian tối ưu hóa giảm đáng kể.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết áp dụng

Nghiên cứu được xây dựng dựa trên ba trụ cột lý thuyết chính: Lý thuyết tối ưu hóa tổ hợp, Lý thuyết trí tuệ bầy đàn thông qua mô hình tối ưu đàn kiến (Dorigo, 1991) và Khung thuật toán tiến hóa Memetic kết hợp tìm kiếm cục bộ. Trong mô hình ACO, hành vi tìm đường của đàn kiến nhân tạo được trừu tượng hóa trên đồ thị cấu trúc đa tầng, nơi mỗi con kiến xây dựng một giải pháp thông qua các bước di chuyển ngẫu nhiên có định hướng bởi nồng độ vết mùi pheromone và thông tin heuristic.

Bốn khái niệm nền tảng được định nghĩa chặt chẽ trong nghiên cứu bao gồm:

• Khoảng cách Hamming ($d_H$): Số lượng vị trí sai khác giữa hai chuỗi ký tự có cùng độ dài $m$.
• Xâu gần nhất của một tập xâu: Chuỗi $t$ tối ưu hóa hàm mục tiêu cực tiểu khoảng cách cực đại $d_H(t, S) = \max {d_H(t, s): s \in S}$.
• Hệ kiến Max-Min trơn (Smooth Max-Min Ant System - SMMAS): Cơ chế cập nhật mùi có giới hạn ngưỡng $[\tau_{min}, \tau_{max}]$ nhằm chống đông cứng sớm giải pháp.
• Hệ số bay hơi vết mùi ($\rho$): Tham số điều tiết tốc độ suy giảm mùi trên các cạnh đồ thị, kiểm soát sự cân bằng giữa khám phá không gian mới và khai thác vùng nghiệm hứa hẹn.

Mô hình nghiên cứu áp dụng các quy tắc cập nhật vết mùi cải tiến theo 2 pha độc lập: giai đoạn đầu cập nhật mùi tuần tự cho $r$ lời giải tốt nhất với hệ số $\rho_1 = 0.01$, giai đoạn sau tập trung cập nhật cho lời giải tốt nhất toàn cục với hệ số $\rho_2 = 0.03$.

Phương pháp nghiên cứu

Nghiên cứu sử dụng phương pháp thực nghiệm mô phỏng thuật toán trên máy tính để đánh giá định lượng hiệu năng của các giải thuật tối ưu metaheuristic.

• Cỡ mẫu và nguồn dữ liệu: Bộ dữ liệu kiểm thử được tổng hợp theo tiêu chuẩn benchmark của các nghiên cứu quốc tế trong tin sinh học với bộ chữ cái 4 ký tự $\Sigma = {A, C, G, T}$. Cỡ mẫu kiểm thử gồm 5 nhóm kích thước quần thể chuỗi $N \in {10, 20, 30, 40, 50}$, mỗi nhóm được khảo sát qua 10 mức độ dài chuỗi từ 100 đến 1000 ký tự (bước nhảy 100 ký tự). Tổng cộng có 50 bộ dữ liệu độc lập đại diện cho các mức độ phức tạp tính toán khác nhau.
• Phương pháp chọn mẫu: Lựa chọn mẫu phân tầng có hệ thống theo độ dài và số lượng chuỗi nhằm bao phủ toàn diện từ các bài toán quy mô nhỏ đến quy mô lớn.
• Phương pháp phân tích: Toàn bộ các thuật toán (Ant-CSP, ACOM-CSP, TSIACO1, TSIACO2, TSIACO2-LS) được lập trình đồng nhất trên ngôn ngữ VB.Net. Mỗi cấu hình dữ liệu được thực hiện chạy lặp lại 20 lần độc lập để tính toán giá trị trung bình toán học ($d_H\text{-Avg}$) và ghi nhận giá trị tối ưu tốt nhất ($d_H\text{-Best}$). Lý do lựa chọn phương pháp phân tích thực nghiệm đa chu kỳ là do đặc tính ngẫu nhiên của thuật toán metaheuristic, việc lấy trung bình qua 20 lần thử giúp loại bỏ hoàn toàn sai số ngoại lai và đảm bảo độ tin cậy thống kê.
• Timeline và môi trường: Quá trình nghiên cứu và thực nghiệm hoàn thành trong 12 tháng, chạy trên hệ thống phần cứng trang bị vi xử lý Intel Core i5-3317U xung nhịp 1.70 GHz, bộ nhớ trong 4GB RAM trên nền hệ điều hành Windows 7.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

Quá trình thực nghiệm đối sánh 5 thuật toán trên 50 bộ dữ liệu chuẩn đã ghi nhận 4 phát hiện quan trọng:

1. Hiệu quả vượt trội của kỹ thuật tìm kiếm địa phương (Local Search): Việc tích hợp tìm kiếm địa phương giúp cải thiện chất lượng nghiệm một cách rõ rệt. Đối với thuật toán Ant-CSP trên tập dữ liệu $N=10$ và độ dài chuỗi 1000 ký tự, phiên bản có Local Search giúp giảm khoảng cách Hamming từ mức 740 xuống xấp xỉ 640 đơn vị, tương ứng mức cải thiện chất lượng nghiệm đạt 13.51%.
2. Sự ưu việt của cơ chế phân đoạn mềm (TSIACO2): So sánh giữa hai phương pháp cập nhật mùi hai giai đoạn, TSIACO2 (sử dụng điều kiện hội tụ động $\delta$) cho kết quả vượt trội hơn hẳn TSIACO1 (phân đoạn cứng theo số bước lặp cố định). Trên bộ dữ liệu $N=20$, độ dài chuỗi từ 600 đến 1000 ký tự, TSIACO2 liên tục đạt các giá trị $d_H\text{-Best}$ thấp nhất, vượt qua cả thuật toán hai pha ACOM-CSP.
3. Hiệu năng tối ưu của thuật toán đề xuất TSIACO2-LS: Thuật toán mới TSIACO2-LS (kết hợp phân đoạn mềm với tìm kiếm địa phương ở giai đoạn 2) đạt chất lượng lời giải cao nhất toàn diện. Khi thiết lập số vòng lặp 2500 bước với $N=30, 40, 50$, TSIACO2-LS cho khoảng cách Hamming trung bình thấp hơn ACOM-CSP từ 2 đến 6 đơn vị khoảng cách trên mọi độ dài chuỗi.
4. Đặc tính hội tụ theo ràng buộc tài nguyên thời gian: Khi giới hạn thời gian chạy ngắt sớm dưới 550 giây, thuật toán ACOM-CSP cho tốc độ hội tụ nhanh nhất. Tuy nhiên, khi thời gian chạy mở rộng từ 1000 giây đến 25000 giây, TSIACO2-LS thể hiện khả năng thoát bẫy tối ưu địa phương vượt bậc, duy trì đà giảm khoảng cách Hamming ổn định.

Thảo luận kết quả

Nguyên nhân cốt lõi giúp TSIACO2 và TSIACO2-LS đạt hiệu quả cao nằm ở việc phân tách chiến lược tối ưu thành 2 pha nhịp nhàng. Trong giai đoạn 1, việc cập nhật mùi cho $r$ giải pháp tốt nhất với hệ số bay hơi thấp ($\rho_1 = 0.01$) duy trì tính đa dạng của quần thể kiến, ngăn ngừa hiện tượng tập trung sớm vào một đường đi cục bộ. Khi chuyển sang giai đoạn 2 dựa trên điều kiện hội tụ mềm, hệ số bay hơi được nâng lên $\rho_2 = 0.03$ kết hợp cập nhật duy nhất cho nghiệm tối ưu toàn cục, giúp đàn kiến tập trung khai thác sâu xung quanh vùng nghiệm triển vọng nhất.

Kết quả có thể được trình bày và đối chiếu trực quan qua bảng tổng hợp ma trận nghiệm (với các cột $d_H\text{-Best}$, $d_H\text{-Avg}$, thời gian thực thi) và hệ thống đồ thị hàm biến thiên khoảng cách Hamming theo thời gian từ 1000s đến 25000s. Đồ thị đường thể hiện rõ độ dốc suy giảm khoảng cách Hamming của TSIACO2-LS sâu hơn đáng kể so với đường tiệm cận của Ant-CSP và TSIACO1.

So với các nghiên cứu công bố trước đó về hệ đàn kiến Max-Min (MMAS) của Stützle & Hoos hay thuật toán Memetic-CSP của Hoàng Xuân Huấn và cộng sự (2012), phương pháp tiếp cận trong luận văn này đã giải quyết triệt để sự đánh đổi giữa thời gian tính toán và độ chính xác của nghiệm. Mặc dù bước tìm kiếm địa phương làm gia tăng thời gian xử lý trên mỗi vòng lặp khoảng 15% đến 20%, nhưng giá trị khoảng cách Hamming thu được lại tiệm cận mức tối ưu toàn cục tốt hơn hẳn.

Đề xuất và khuyến nghị

Dựa trên các kết luận rút ra từ thực nghiệm, 4 khuyến nghị và giải pháp hành động cụ thể được đề xuất nhằm ứng dụng và phát triển thuật toán:

1. Ứng dụng thuật toán TSIACO2-LS vào công cụ phân tích tin sinh học thực tế: Đề xuất các viện nghiên cứu công nghệ sinh học và trung tâm tin sinh tích hợp module giải thuật TSIACO2-LS vào phần mềm dò tìm motif DNA và phân tích cụm gen. Mục tiêu nâng cao độ chính xác nhận diện motif lên 10-15% trong vòng 6 tháng tới. Chủ thể thực hiện: Các kỹ sư tin sinh học và chuyên gia phân tích dữ liệu hệ gen.
2. Phát triển kiến trúc tính toán song song cho thuật toán đàn kiến: Tiến hành lập trình song song hóa thuật toán trên nền tảng phần cứng đa luồng hoặc GPU (sử dụng CUDA/OpenCL) để phân tán quá trình xây dựng hành trình của các cá thể kiến. Mục tiêu đặt ra là rút ngắn thời gian xử lý thực nghiệm từ 10000 giây xuống dưới 1000 giây đối với các chuỗi siêu dài trên 10.000 nucleotide, triển khai trong lộ trình 12 tháng. Chủ thể thực hiện: Nhóm nghiên cứu tính toán hiệu năng cao.
3. Xây dựng cơ chế tự điều chỉnh tham số bay hơi thích nghi: Cải tiến thuật toán bằng cách thiết lập hàm điều khiển thích nghi cho tham số $\rho$ biến thiên tự động trong khoảng 0.005 đến 0.05 dựa trên đo lường độ phân tán entropy của vết mùi. Mục tiêu giúp thuật toán tự thích ứng với mọi kích thước tập dữ liệu đầu vào mà không cần cấu hình thủ công, hoàn thành nghiên cứu trong 9 tháng. Chủ thể thực hiện: Các nhà nghiên cứu giải thuật tối ưu hóa tổ hợp.
4. Đưa mô hình tối ưu bầy đàn hai giai đoạn vào chương trình đào tạo chuyên sâu: Khuyến nghị các khoa Công nghệ thông tin xây dựng các chuyên đề môn học về Metaheuristic và Memetic Algorithms ứng dụng trong xử lý dữ liệu lớn, tổ chức tối thiểu 2 hội thảo học thuật mỗi năm nhằm chuyển giao tri thức nghiên cứu cho sinh viên và học viên cao học. Chủ thể thực hiện: Các trường đại học khối kỹ thuật và công nghệ.

Đối tượng nên tham khảo luận văn

Luận văn là tài liệu tham khảo chuyên môn sâu sắc và hữu ích cho 4 nhóm đối tượng sau:

1. Học viên cao học và nghiên cứu sinh ngành Công nghệ thông tin, Khoa học máy tính: Tài liệu cung cấp cơ sở toán học chặt chẽ về cách ánh xạ bài toán tối ưu tổ hợp NP-khó lên đồ thị kiến, phương pháp chứng minh sự hội tụ của thuật toán bầy đàn và quy trình thiết kế nghiên cứu thực nghiệm chuẩn mực.
2. Chuyên gia và kỹ sư phân tích dữ liệu Tin sinh học (Bioinformatics): Nắm bắt giải pháp kỹ thuật tối ưu để xử lý các bài toán căn chỉnh đa chuỗi, xác định mẫu bảo tồn sinh học và tìm kiếm motif gen với độ chính xác cao trên các tập dữ liệu có quy mô hàng nghìn ký tự.
3. Kỹ sư phát triển phần mềm và tối ưu hóa giải thuật: Học hỏi kỹ thuật cài đặt hệ thống đa tác tử (Multi-agent Systems), phương pháp kết hợp thuật toán heuristic cấu trúc với tìm kiếm cục bộ (Local Search) và kinh nghiệm thiết kế giao diện kiểm thử thực nghiệm trên nền tảng .NET.
4. Giảng viên và nhà nghiên cứu lý thuyết tối ưu hóa: Sử dụng công trình như một nghiên cứu điển hình (case study) toàn diện về sự cải tiến từ thuật toán Ant System nguyên bản sang hệ kiến hai giai đoạn (TSIACO) và thuật toán Memetic phục vụ công tác giảng dạy sau đại học.

Câu hỏi thường gặp

1. Bài toán xâu gần nhất (CSP) có ý nghĩa như thế nào trong nghiên cứu tin sinh học? Bài toán xâu gần nhất đóng vai trò trọng tâm trong việc tìm kiếm motif chung đại diện cho một họ gen và thiết kế các đoạn mồi PCR (primer design). Bằng việc tìm ra chuỗi có khoảng cách Hamming nhỏ nhất tới tập hợp các chuỗi sinh học đã biết, các nhà khoa học có thể xác định chính xác các vùng chức năng bảo tồn trên 4 loại nucleotide {A, C, G, T} của phân tử DNA.

2. Điểm khác biệt mấu chốt giữa thuật toán TSIACO1 và TSIACO2 là gì? Điểm khác biệt duy nhất nằm ở điều kiện chuyển đổi giữa hai giai đoạn cập nhật mùi. TSIACO1 sử dụng phân đoạn cứng dựa trên tỷ lệ vòng lặp cố định $NC \le \gamma \cdot NC_{max}$. Trong khi đó, TSIACO2 sử dụng phân đoạn mềm dựa trên độ đo hội tụ động $\delta \ge \delta_0$, giúp quá trình chuyển pha diễn ra linh hoạt đúng thời điểm quần thể bắt đầu bão hòa.

3. Tại sao việc kết hợp tìm kiếm địa phương (Local Search) lại tăng đáng kể chất lượng nghiệm? Kiến nhân tạo xây dựng giải pháp theo các bước xác suất ngẫu nhiên nên đôi khi bỏ sót các cấu hình ký tự tối ưu cục bộ. Kỹ thuật tìm kiếm địa phương can thiệp bằng cách thử thay thế tuần tự từng vị trí ký tự trong tập ứng viên $V_i$, giúp tinh chỉnh chuỗi kết quả và hạ khoảng cách Hamming xuống từ 10% đến 15% trước khi thực hiện bay hơi vết mùi.

4. Khi nào nên lựa chọn thuật toán ACOM-CSP thay vì TSIACO2-LS? Người dùng nên chọn ACOM-CSP khi bài toán bị ràng buộc khắt khe về thời gian phản hồi (ví dụ các ứng dụng cần kết quả dưới 550 giây) nhờ khả năng hội tụ ban đầu rất nhanh. Ngược lại, nếu mục tiêu là tìm kiếm giải pháp có độ chính xác cao nhất và tài nguyên thời gian không hạn chế, TSIACO2-LS là sự lựa chọn vượt trội.

5. Tham số hệ số bay hơi vết mùi ($\rho$) tác động như thế nào đến độ hội tụ của đàn kiến? Hệ số bay hơi quyết định khả năng lưu giữ thông tin lịch sử tìm kiếm. Nếu thiết lập $\rho$ quá lớn (ví dụ $\rho = 0.06$), vết mùi phân rã nhanh khiến đàn kiến mất định hướng. Nếu $\rho$ quá nhỏ (ví dụ $\rho = 0.002$), vết mùi cũ tồn tại lâu dẫn tới bẫy tối ưu cục bộ. Mức thiết lập tối ưu được thực nghiệm chứng minh là $\rho_1 = 0.01$ cho pha 1 và $\rho_2 = 0.03$ cho pha 2.

Kết luận

• Luận văn đã hệ thống hóa toàn diện cơ sở lý thuyết về bài toán xâu gần nhất (CSP) và các phương pháp metaheuristic dựa trên tối ưu đàn kiến (ACO).
• Đề xuất thành công thuật toán mới TSIACO2-LS, kết hợp cơ chế phân đoạn mềm hai giai đoạn cập nhật pheromone với kỹ thuật tìm kiếm địa phương.
• Tiến hành thực nghiệm quy mô lớn với 50 bộ dữ liệu chuỗi nucleotide, chứng minh TSIACO2-LS vượt trội hơn các thuật toán Ant-CSP, ACOM-CSP và TSIACO1 về chất lượng nghiệm khi thời gian chạy không bị hạn chế.
• Xác định bộ tham số tối ưu cho quá trình cập nhật mùi hai pha gồm $\rho_1 = 0.01$ và $\rho_2 = 0.03$, mang lại sự cân bằng hoàn hảo giữa thăm dò và khai thác không gian tìm kiếm.
• Định hướng phát triển tiếp theo trong 12 tháng tới tập trung vào việc song song hóa thuật toán trên nền tảng GPU và ứng dụng trực tiếp vào dữ liệu hệ gen người thực tế; các nhà nghiên cứu và lập trình viên quan tâm có thể ứng dụng ngay mô hình thuật toán này để tối ưu hóa bài toán phân tích chuỗi trong các dự án công nghệ sinh học hiện đại.

Trích đoạn nội dung tài liệu

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 (LUAN.04 TIEU LUAN MOI download : skknchat@gmail. 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 (LUAN.04 TIEU LUAN MOI download : skknchat@gmail. 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 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. Xét xâu t = “GGGGG” và tập xâu S={ s1= “AGGAA”, s2 = “AGGGA”, s3 = “GGGGA”}.

 Đị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.04 TIEU LUAN MOI download : skknchat@gmail.04 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ó.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.04 TIEU LUAN MOI download : skknchat@gmail.04 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ể.04 TIEU LUAN MOI download : skknchat@gmail.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 (LUAN.04 TIEU LUAN MOI download : skknchat@gmail.

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.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).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.1 Thể hiện hành vi của mỗi con kiến trong tự nhiên (LUAN.04 TIEU LUAN MOI download : skknchat@gmail.04 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. Họ chạy các thực nghiệm với tỉ lệ dài đường giữa hai nhánh khác nhau của chiếc cầu đôi, trong đó là độ dài của nhánh dài còn là độ dài của nhánh ngắn.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. 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.04 TIEU LUAN MOI download : skknchat@gmail.04 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. 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.