Chương 1. BÀI TOÁN XÂU GẦN NHẤT VÀ MỘT SỐ PHƯƠNG PHÁP TIẾP CẬN Bài toán xâu gần nhất (Closest String Problem - CSP) thuộc lớp bài toán tối ưu tổ hợp (gọi tắt là TƯTH), bài toán này được đánh giá là phức tạp và là một trong những bài toán khó tính toán cho đến nay [10]. TƯTH là một dạng của bài toán tối ưu hóa. Tối ưu hoá là thuật ngữ thường được dùng để cực tiểu hoá hay cực đại hoá một hàm.
Thông thường chỉ cần tìm cực tiểu một hàm là đủ. Việc tìm cực đại của f(x) thực hiện một cách đơn giản bằng cách tìm cực tiểu của hàm −f(x).1 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.2) LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 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. LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 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ể.
LUAN VAN CHAT LUONG download : add luanvanchat@agmail.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 VAN CHAT LUONG download : add luanvanchat@agmail.com 16 Chương 2. PHƯƠNG PHÁP ACO ACO (Ant Colony Optimization - tối ưu đàn kiến) là một phương pháp metaheuristic [3, tr.48-53] dựa trên ý tưởng mô phỏng cách tìm đường đi từ tổ tới nguồn thức ăn của các con kiến tự nhiên. Đến nay phương pháp ACO được cải tiến với nhiều phiên bản đa dạng và có nhiều ứng dụng.
Trước khi tìm hiểu phương pháp ACO tôi đi tìm hiểu phương thức trao đổi thông tin gián tiếp của kiến tự nhiên và mô hình kiến nhân tạo.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 VAN CHAT LUONG download : add luanvanchat@agmail.com 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. LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 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.
Tuy nhiên, trong thời gian đầu không phải tất cả các kiến đều đi theo nhánh ngắn hơn. Phải mất một khoảng thời gian tiếp theo đàn kiến mới lựa chọn đi theo nhánh ngắn. Điều này minh chứng đàn kiến đã sử dụng phương thức thăm dò, tìm đường mới.