Chương 1: Giới thiệu nguồn gốc sinh học của thuật toán kiến, cách truyền thông gián tiếp và lược sử phát triển của các thuật toán ACO. Chương 2: Trình bày về phương pháp tối ưu hoá đàn kiến:ACO Chương 3: Giới thiệu về thuật toán hệ kiến Max-Min và đề xuất cách cập nhật mùi theo Max-Min trơn, các kết quả thực nghiệm tốt mà hệ kiến Max-Min trơn đạt được. Chương 4: Trình bày hai ứng dụng điển hình của hệ kiến Max-Min đó là bài toán phân công bậc hai và bài toán thời khóa biểu. LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com -3- CHƢƠNG 1 LƢỢC SỬ PHÁT TRIỂN CỦA CÁC THUẬT TOÁN ACO Trong chương này chúng tôi giới thiệu lược sử phát triển của các thuật toán ACO, bắt đầu từ các thí nghiệm sinh học về cách chọn đường đi của các con kiến thực rồi đến hình thành ý tưởng thuật toán từ các thí nghiệm đó, sau đó là sự ra đời của hệ kiến, hệ đàn kiến, hệ kiến Max-Min.
Các thuật toán kiến có được nhờ sự quan sát cách chọn đường đi của các con kiến thực. Các con kiến là các côn trùng sống trong các bầy đàn và sống thành xã hội, chúng xuất hiện trên trái đất cách đây đã hơn 100 triệu năm, số lượng của chúng khoảng 106 con (xem [13]). Sự tổ chức bầy đàn của các con kiến trong xã hội kiến có cấu trúc cao đã thu hút nhiều nghiên cứu sinh học. Trong xã hội kiến, các con kiến thợ thường xuyên tìm kiếm thức ăn đem về tổ và đặc biệt là làm thế nào các con kiến có thể tìm được đường đi ngắn nhất từ tổ của chúng tới nguồn thức ăn? 1.
Nguồn gốc sinh học của các thuật toán kiến Trong quá trình đi từ tổ đến nguồn thức ăn và ngược lại, các con kiến rải xuống đất một hoá chất gọi là mùi (tên khoa học là pheromone) và tạo nên các vết mùi (pheromone trail). Các con kiến ngửi thấy mùi và chúng có khuynh hướng chọn theo xác suất, các đường đi được đánh dấu bởi sự tập trung mùi mạnh. Vết mùi cho phép các con kiến tìm ra đường quay lại của chúng tới nguồn thức ăn hoặc tổ, nó cũng có thể được sử dụng bởi các con kiến khác để tìm ra vị trí nguồn thức ăn. Thực nghiệm cho thấy rằng, cách thức theo vết mùi (pheromone trail following behavior) này là một phương pháp luận hiệu quả để tìm ra đường đi ngắn nhất.
LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com -4- Hình 1: Cách tìm đường đi của kiến Các con kiến thường để lại mùi (một chất hóa học đặc biệt mà chúng có thể ngửi được) trên đường đi. Bằng cách để lại mùi như vậy, chúng sẽ tạo ra các vết mùi để lại trên đường đi từ tổ đến nguồn thức ăn và ngược lại. Trong thực tế, bằng cách cảm nhận những vết mùi như vậy những con kiến khác có thể tìm đường tới các nguồn thức ăn do những con kiến trước đã tìm ra. Đồng thời, chúng có thể dựa vào đó để tìm được đường đi ngắn nhất từ tổ đến các nguồn thức ăn.
Nhằm nghiên cứu các cách tìm đường đi của các con kiến trong điều kiện quan sát được.Deneubourg [19] và các đồng nghiệp đã làm một thí nghiệm sử dụng một cây cầu đôi nối từ tổ đến nguồn thức ăn, hình 2. Tổ của một đàn kiến với nguồn thức ăn được ngăn bởi một các cầu đôi mà hai nhánh của nó bằng nhau để nghiên cứu sự lưu lại các vệt mùi và hành vi của chúng. Tiếp đó các con kiến được thả và tự do đi lại giữa tổ và nguồn thức ăn và phần trăm số kiến chọn nhánh nào để đi được quan sát theo thời gian. Kết quả là sau một giai đoạn ban đầu có sự do dự, trong chốc lát các con kiến có khuynh hướng chọn và hội tụ về cùng một đường đi.
LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com -5- Trong thí nghiệm trên, ban đầu không có mùi trên 2 nhánh, nên các nhánh được chọn có cùng một xác suất. Tuy nhiên, do sự thăng giáng tự nhiên, sau một giai đoạn ban đầu, nhánh trên được chọn nhiều hơn nhánh dưới. Bởi vì các con kiến rải mùi trong khi đi, số kiến lớn hơn ở nhánh trên thì lượng mùi mạnh hơn, do đó kích thích nhiều con kiến chọn nó hơn. Nhánh trên Tổ kiến Thức ăn Nhánh dưới Hình 2: Mô hình thí nghiệm cầu đôi 2 nhánh dài bằng nhau Tiếp đó họ thay đổi thí nghiệm trên tới trường hợp mà trong đó các nhánh có chiều dài khác và thu được kết quả là theo thời gian dần dần hầu hết con kiến đều đi vào nhánh ngắn hơn.
Kết quả được giải thích như sau: Do kỹ thuật rải mùi như nhau, khi thực nghiệm bắt đầu, hai nhánh cầu đều không có mùi, như vậy lúc đầu các con kiến chọn một trong hai nhánh theo xác suất là như nhau tức là một nửa số con kiến sẽ chọn nhánh ngắn và nửa còn lại sẽ chọn nhánh dài. Trong quá trình tìm kiếm thức ăn và đưa về tổ, con kiến luôn để lại vệt mùi trên hai nhánh cầu. Do nhánh ngắn hơn, thời gian con kiến đi sẽ ít hơn (đồng nghĩa với số lần các con kiến đi lại nhiều hơn), lượng mùi trên nhánh này sẽ nhiều hơn, nên theo thời gian các con kiến sẽ chọn nhánh ngắn hơn để đi do cường độ vệt mùi trên nhánh này cao hơn, minh hoạ trong hình 3. LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com -6- Hình 3: Thí nghiệm cầu đôi.
(a) Các con kiến bắt đầu khám phá chiếc cầu. (b) Hầu hết các con kiến chọn đường đi ngắn nhất. Trong các thuật toán kiến, cây cầu đôi ở thí nghiệm của Deneubourg được thay bằng một đồ thị cấu trúc và các vết mùi của con kiến là những vết mùi nhân tạo. Đồng thời khi muốn giải quyết những bài toán phức tạp hơn những bài toán của con kiến thực, người ta cung cấp thêm cho con kiến nhân tạo một số khả năng đặc biệt như bộ nhớ và khả năng để lại một lượng mùi tỷ lệ với hiệu quả của lời giải tìm được (một hành vi tương tự như hành vi của con kiến thực khi chúng mang thức ăn quay về tổ để lại một lượng mùi tỷ lệ với lượng thức ăn kiếm được).
Mỗi con kiến đơn lẻ chỉ có một sự đóng góp rất nhỏ trong quá trình tìm đường đi. Mặc dù một con kiến đơn lẻ về nguyên tắc có khả năng xây dựng một lời giải (Ví dụ: tìm ra một đường đi giữa tổ và nguồn thức ăn), nhưng cả đàn kiến mới là đối tượng biểu diễn cách thức "tìm đường đi ngắn nhất". Cách thức này là một thuộc tính nổi bật (emergent) của đàn kiến. Cũng cần chú ý là các con kiến có thể thực hiện cách thức riêng biệt này bằng cách sử dụng một dạng truyền thông gián tiếp-stigmergy bằng cách rải mùi.
LUAN VAN CHAT LUONG download : add luanvanchat@agmail. Truyền thông gián tiếp-stigmergy Dạng truyền thông stigmergy được đưa ra trong công trình của Grassé [20] (Bellicositermes Natalensis và Cubitermes), stigmergy là "Mô phỏng các thợ (workers-một đẳng cấp trong các đàn mối) bởi hiệu suất mà chúng đạt được". Mặc dù Grassé giới thiệu thuật ngữ stigmergy để giải thích các hành vi của xã hội đàn mối, nhưng sau đó thuật ngữ này được dùng để mô tả dạng truyền thống gián tiếp bởi sự thay đổi môi trường có thể quan sát được ở xã hội côn trùng. Những đặc trưng của stigmergy: - Tính vật lý tự nhiên của thông tin được sinh ra bởi các côn trùng truyền thông, tương ứng với sự thay đổi các trạng thái môi trường vật lý mà được thăm bởi các côn trùng.
- Tính cục bộ tự nhiên của thông tin được sinh ra, chỉ có thể được truy cập bởi các côn trùng thăm trạng thái đó. Vì vậy ta có thể nói truyền thông stigmergy là một dạng truyền thông gián tiếp dựa vào thay đổi thông tin qua tác động vật lý làm thay đổi môi trƣờng. Quá trình phát triển của các thuật toán ACO Hệ kiến là thể hiện đầu tiên và điển hình của các thuật toán ACO, hầu hết các thuật toán ACO hiện dùng đều được phát triển từ thuật toán này. Vì vậy, trước khi giới thiệu các thuật toán ACO, chúng tôi giới thiệu hệ kiến và các cải tiến quan trọng của chúng là hệ đàn kiến và hệ kiến Max-Min.
Hệ kiến và bài toán TSP 1. Bài toán TSP Bài toán TSP được phát biểu như sau: LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com -8- Bài toán người chào hàng (TSP-Traveling Salesman Problem) khá đơn giản: Người chào hàng phải tìm một đường đi khép kín đi qua mọi thành phố trong địa phận của anh ta đúng một lần và trở về nơi xuất phát để tổng độ dài (chi phí) của đường đi là nhỏ nhất. Bài toán TSP bậc n được phát biểu dưới dạng một bài toán đồ thị như sau: Cho một đồ thị G = (V, E), trong đó tập đỉnh V = {1, 2,. , n) ký hiệu các thành phố, E = {{i, j } , i, j V} mỗi cạnh (i, j) V có độ dài dij tương ứng (dij là khoảng cách từ thành phố i tới thành phố j và d i , j d j ,i nếu đó là đường một chiều).
Tìm đường đi qua tất cả các đỉnh của G mỗi đỉnh đúng một lần và trở về nơi xuất phát sao cho tổng chi phí của các cạnh thuộc đường đi (n cạnh) là nhỏ nhất. Như vậy, với đồ thị không đối xứng sẽ có (n 1)! đường đi chấp nhận (n 1)! được và với đồ thị đối xứng. Với n lớn thì ta không thể tìm hết các 2 đường đi và chỉ có thể tìm được một lời giải đủ tốt bằng các phương pháp truyền thống như: Quy hoạch động, nhánh và cận, tìm kiếm địa phương, tìm kiếm heuristic, tính toán tiến hóa hay là các phương pháp kết hợp giữa chúng. TSP là bài toán tối ưu tổ hợp khó và có nhiều ứng dụng, nó vẫn được xem là bài toán mẫu dùng để kiểm tra hiệu quả của các thuật toán tối ưu tổ hợp.
Khi G là đồ thị có hướng thì bài toán TSP được gọi TSP không đối xứng (Asymmeric Traveling Salesman Problem-ATSP), trường hợp còn lại gọi là TSP đối xứng (gọi tắt là TSP). Để đơn giản, ta xét bài toán trên đồ thị vô hướng, sau này ta dùng ký hiệu TSP. Tiếp theo chúng tôi sẽ trình bày các thuật toán kiến dựa trên tư tưởng lời giải của bài toán TSP. LUAN VAN CHAT LUONG download : add luanvanchat@agmail.