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

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.

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.