Tài liệu Thuật toán hệ kiến Max - Min và ứng dụng

ĐẠI HỌC QUỐC GIA HÀ NỘI KHOA CÔNG NGHỆ Nguyễn Thanh Tùng THUẬT TOÁN HỆ KIẾN MAX-MIN VÀ ỨNG DỤNG LUẬN VĂN THẠC SỸ Hà Nội - 2004 ĐẠI HỌC QUỐC GIA HÀ NỘI KHOA CÔNG NGHỆ Nguyễn Thanh Tùng THUẬT TOÁN HỆ KIẾN MAX-MIN VÀ ỨNG DỤNG Chuyên ngành: Cụng nghệ thông tin Mó số: 1.01.10 LUẬN VĂN THẠC SỸ NGƯỜI HƯỚNG DẪN KHOA HỌC: TS. Hoàng Xuân Huấn Hà Nội - 2004 MỤC LỤC Trang MỞ ĐẦU ........................................................................................... 1 Chƣơng 1 – LƢỢC SỬ PHÁT TRIỂN CỦA CÁC THUẬT TOÁN ACO .... 3 1.1. Nguồn gốc sinh học của các thuật toán kiến ............................. 3 1.2. Truyền thông gián tiếp-stigmergy............................................. 7 1.3. Quá trình phát triển của các thuật toán ACO ............................ 7 1.3.1. Hệ kiến và bài toán TSP ................................................. 7 1.3.1.1. Bài toán TSP ................................................... 7 1.3.1.2. Hệ kiến ........................................................... 9 1.3.2. Hệ đàn kiến .................................................................... 12 1.3.3. Thuật toán hệ kiến Max-Min ........................................... 15 Chƣơng 2 - PHƢƠNG PHÁP TỐI ƢU HOÁ ĐÀN KIẾN: ACO ................. 17 2.1. Một số heuristic ACO .................................................................. 17 2.2. Meta-heuristic tối ƣu hoá đàn kiến .............................................. 18 2.2.1. Bài toán tổng quát .......................................................... 18 2.2.2. Thuật toán ACO tổng quát ............................................. 20 2.2.3. Xây dựng lời giải............................................................ 23 2.2.4. Cập nhật mùi .................................................................. 24 2.3. Đặc tính hội tụ của vết mùi ....................................................... 25 2.4. Các thuật toán trong ACOmin .................................................. 28 Chƣơng 3 - THUẬT TOÁN HỆ KIẾN MAX-MIN ..................................... 31 3.1. Thuật toán hệ kiến MAX-MIN..................................................... 31 3.1.1. Giới thiệu hệ kiến Max-Min ........................................... 31 3.1.2. Cập nhật vết mùi ............................................................ 32 3.1.3. Giới hạn của vết mùi ...................................................... 33 3.1.4. Giá trị thông số ............................................................ 34 3.1.5. Khởi tạo vết mùi ............................................................. 35 3.1.6. Phƣơng thức cập nhật mùi .............................................. 35 3.1.7. Một số nguyên lý ứng dụng ............................................ 36 3.2. Hệ kiến MAX-MIN trơn ........................................................... 39 Chƣơng 4 - MỘT SỐ ỨNG DỤNG CỦA HỆ KIẾN MAX-MIN ................. 43 4.1. Cách giải bài toán tối ƣu tổ hợp ................................................ 43 4.2. Một số ứng dụng ...................................................................... 44 4.2.1. Bài toán phân công bậc hai ............................................... 45 4.2.2. Bài toán lập thời khóa biểu ............................................... 48 KẾT LUẬN .................................................................................................. 54 Tài liệu tham khảo ........................................................................................ 56 Phụ lục ......................................................................................................... 59 -1- MỞ ĐẦU ác bài toán tối ưu tổ hợp (Combinatorial Optimization Problems - C COP) đóng góp vai trò quan trọng trong thực tế, có rất nhiều ứng dụng trong lĩnh vực kinh tế, sản xuất. Khi giải các bài toán tối ưu tổ hợp khó thường gặp trở ngại lớn, các thuật toán truyền thống thường khó giải quyết, các thuật toán mô phỏng tự nhiên như luyện kim, di truyền, tiến hóa, hệ kiến...tỏ ra có ưu thế hơn. Trong một thập kỷ qua các thuật toán ACO tỏ ra là phương pháp nổi trội để giải quyết các bài toán tối ưu tổ hợp khó. Tối ưu hóa đàn kiế n (Ant Colony Optimization - ACO) là cách tiế p cận meta heuristic tương đố i mới được đề xuất đầu tiên bởi Marco Dorigo và các đồng nghiệp năm 1991. Một trong những thành công đầu tiên của lớp thuật toán ACO là giải quyết tốt bài toán nổi tiếng Người chào hàng (Traveling Salesman Problem-TSP) với số thành phố khá lớn, hơn 2000. Từ đó đến nay ACO ngày càng thu hút được sự quan tâm và nghiên cứu của giới khoa học và hiệu quả nổi trội của nó được chứng minh bằng thực nghiệm như giải quyết các bài tối ưu tổ hợp điển hình: Bài toán phân công bậc hai (Quadratic Assignment Problem-QAP), Bài toán lập lịch công việc (Job-shop Scheduling Problem-JSP), Bài toán định đường xe tải (Vehicle Rouling Problem -VRP), Bài toán tô màu đồ thị (Graph Coloring Problem-GCP), Bài toán siêu dãy chung ngắn nhất (Shortest Colnmon Supersequence Poblem-SCS)… Trong ACO, hệ kiến Max-Min (Max-Min Ant System-MMAS) tỏ ra đơn giản, thông dụng và được rất nhiều người ưa dùng so với các thuật toán kiến trước đó như hệ kiến (Ant System-AS), hệ đàn kiến (Ant Conoly SystemACS). Hệ kiến Max-Min là thuật toán đầu tiên đề xuất cập nhật mùi theo tư tưởng Max-Min. Năm 1999, nhằm mục đích đưa ra một lược đồ làm việc chung cho các thuật toán kiến, Marco Dorigo, Luca M. Gambardella và -2- Gianni Di Cao đã khái quát hóa thành lớp ACO và ứng dụng một cách phong phú để giải quyết các bài toán tối ưu tổ hợp tĩnh và động. Nội dung của luận văn sẽ khảo cứu về các thuật toán ACO theo quy tắc cập nhật mùi Max-Min. Trên cơ sở đó chúng tôi đề xuất thuật toán hệ kiến MaxMin trơn (Max-Min Smooth Ant System-MMSAS) và thử nghiệm với bài toán TSP. Kết quả thực nghiệm cho thấy hệ kiến Max-Min trơn có ưu điểm hơn hệ kiến Max-Min trong bài toán được xét. Ngoài phần mở đầu và phần kết luận, luận văn được tổ chức như sau: 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. -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.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. -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. J.L.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. -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 Thức ăn Tổ kiế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. -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. -7- 1.2. 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. 1.3. 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. 1.3.1. Hệ kiến và bài toán TSP 1.3.1.1. Bài toán TSP Bài toán TSP được phát biểu như sau: -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 được và (n  1)! 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. -9- 1.3.1.2. Hệ kiến Hệ kiến (Ant System-AS) được đề xuất từ cách ứng xử được đề cập ở trên của các con kiến thực, là một thuật toán mà trong đó một tập các con kiến nhân tạo hợp tác với nhau để tìm lời giải của một bài toán bằng việc trao đổi thông tin thông qua mùi được rải trên các cạnh của một đồ thị. Có nhiều thuật toán AS như ant-cycle, ant-density, và ant-quantity, ở đây chúng tôi chỉ xét thuật toán ant-cycle. Do thuật toán ant-cycle có kết quả thực nghiệm tốt hơn hai thuật toán kia, nên sau này nó được gọi đơn giản là thuật toán AS, trong khi hai thuật toán còn lại về sau không còn được nghiên cứu và phát triển nữa. Hệ kiến hoạt động như sau: mỗi con kiến sinh ra một đường đi (tour) bằng cách chọn những thành phố theo một qui tắc chọn thành phố mới (state transition rule) ngẫu nhiên, những con kiến thích đi tới các thành phố mà nối với những cạnh ngắn có lượng mùi cao. Khi tất cả các con kiến đã hoàn thành đường đi của nó, một qui tắc cập nhật mùi toàn cục (global pheromone updating rule) được áp dụng: i) Một tỉ lệ mùi bị bốc hơi trên tất các các cạnh bởi một hệ số bay hơi mùi cho trước (những cạnh không được làm tươi sẽ ít được con kiến chú ý). ii) Mỗi con kiến rải một lượng mùi lên các cạnh thuộc đường đi tương xứng với chiều dài đường đi của nó (hay nói cách khác là các cạnh thuộc về nhiều đường đi ngắn là những cạnh nhận lượng mùi lớn hơn). Tiến trình trên được lặp lại. Để giải bài toán TSP, AS dùng biến vết mùi i,j kết hợp với mỗi cạnh (i,j) và ban đầu được khởi tạo bởi giá trị 0. Có m con kiến nhân tạo, ở bước lặp t chúng thực hiện các thủ tục xây dựng lời giải và cập nhật mùi như sau: - 10 - Xây dựng lời giải Ban đầu mỗi con kiến được đặt ngẫu nhiên tại các thành phố và thăm các thành phố khác để xây dựng đường đi với thủ tục tuần tự theo quy tắc chuyển trạng thái sau: Quy tắc chuyển trạng thái: Qui tắc chọn thành phố mới, được gọi là qui tắc tỉ lệ ngẫu nhiên (random-proportional rule), được cho bởi công thức (1.1), là công thức đưa ra xác suất chọn thành phố j để di chuyển tới đối với kiến k khi đang ở thành phố i. Giả sử kiến k đang ở thành phố i, nó sẽ chọn thành phố j tiếp theo với xác suất:   i, j (t ) i, j     k Pi , j (t )    i ,u i ,u  uJ k ( i )  0  j  J k (i) j  J k (i) (1.1) Hai tham số  ,  thể hiện: xác suất lựa chọn cạnh (i, j) tỷ lệ thuận với cường độ vết mùi  ij (t) tại bước lặp t đang xét. Jk(i) là tập các đỉnh chưa được con kiến k đi qua khi nó ở đỉnh i (để làm lời giải khả thi). Thông tin heuristic ij  1 d ij là nghịch đảo của khoảng cách d(i, j), nếu   0 con kiến sẽ lựa chọn đỉnh tiếp theo dựa vào chiến lược “tham lam”: Cạnh nào ngắn nhất sẽ được ưu tiên chọn trước, nếu   0 sự lựa chọn chỉ phụ thuộc vào cường độ vết mùi. Tiếp tục như vậy nó sẽ tìm được một chu trình chấp nhận được làm một lời giải đủ tốt cho bài toán. Cập nhật mùi: Trong AS, qui tắc cập nhật toàn cục được thực hiện như sau: Khi tất cả các con kiến đã xây dựng xong đường đi của nó, mùi được cập nhật trên tất cả các cạnh theo công thức (1.2). - 11 - m  ij (t  1)  (1   ) ij (t )    ij k (t ) (1.2) k 1 Trong đó  (0,1) được gọi là hệ số bay hơi mùi và  1 k  ij k (t )   L (t )  0 Nếu (i,j) thuộc chu trình của kiến k ngược lại (1.3) Lk(t) là chiều dài của đường đi được thực hiện bởi kiến k tại bước lặp t, còn m là số các con kiến được sử dụng. Tham số  được sử dụng để làm bay hơi các vết mùi trên các cạnh và cho phép lãng quên những cạnh ít sử dụng (các cạnh không thuộc hành trình của con kiến nào sẽ có cường độ mùi giảm rất nhanh theo hàm mũ của số vòng lặp). Với những cạnh có con kiến đi qua, lượng mùi sẽ được tăng thêm một lượng là 1/Lk. Ƣu và nhƣợc điểm của AS AS có một số ưu điểm:  Việc tìm kiếm ngẫu nhiên dựa trên các thông tin heuristic làm cho việc tìm kiếm linh hoạt và mềm dẻo trên không gian tìm kiếm rộng, nó hơn phương pháp heuristic sẵn có, do đó cho ta lời giải tốt hơn và có thể tìm được lời giải tối ưu.  Sự kết hợp được việc học tăng cường (reinforcement learning), trong đó những lời giải tốt sẽ được sự tăng cường cao hơn thông qua thông tin về cường độ vết mùi , cho phép ta từng bước thu hẹp không gian tìm kiếm mà vẫn không bỏ qua những lời giải tốt. Do đó nâng cao chấ t lượng thuật toán . - 12 - Nhược điểm: Giả sử w*(t) là chu trình có độ dài ngắn nhất mà các con kiến tìm được đến lần lặp t thì sau Nc lần lặp w*(Nc) cho ta lời giải đủ tốt. Mặc dù AS là hữu dụng cho việc khám phá lời giải tốt hoặc tối ưu cho các bài toán TSP nhỏ (tới 30 thành phố), thời gian cần để tìm những kết quả tốt như vậy trên những bài toán lớn đối với AS là khó đạt được. Khi số đỉnh lớn thì lượng mùi trên mỗi cạnh không thuộc lời giải tốt nhanh chóng dần về không nên hệ AS kém hiệu quả. Chất lượng thuật toán phụ thuộc nhiều vào chất lượng của thông tin heuristic, mà điều này thì chúng ta rất khó can thiệp vào . Hệ đàn kiến sẽ đưa ra ba thay đổi chính để cải thiện hiệu suất của hệ kiến khi áp dụng vào các bài toán lớn, được trình bày ở phần tiếp theo. 1.3.2. Hệ đàn kiến Hệ đàn kiến (Ant Colony System-ACS) là thuật toán được xây dựng trên AS dựa tên ý tưởng tăng tầm quan trọng của các thông tin được tích luỹ bởi các con kiến trước nhằm cải thiện hiệu suất khi áp dụng cho các bài toán TSP có hướng kích thước lớn (trên 50 thành phố). So với AS, ACS có ba cải tiến sau: i) Qui tắc chọn thành phố mới cung cấp một cách thức cân bằng giữa sự khám phá cạnh mới với sự khai thác độ ưu tiên và thông tin được tích luỹ về bài toán. ii) Qui tắc cập nhật mùi toàn cục (global updating pheromone rule) được áp dụng chỉ với các cạnh thuộc về đường đi tốt nhất. iii) Qui tắc cập nhật mùi địa phƣơng (local updating pheromone rule), được áp dụng trong khi các con kiến xây dựng một lời giải cho nó. - 13 - Trong ACS, ở bước lặp t các quy tắc chuyển trạng thái (1.1) và cập nhật mùi (1.2) thay đổi như sau: Quy tắc chuyển trạng thái: Giả sử con kiến k đang ở đỉnh i, nó chọn đỉnh s tiếp theo nhờ quy tắc: arg max k { ij (t )ij  } jNi  sj   Nếu qq0 (Sự khai thác) trái lại (hướng đến sự khám phá) (1.4) Ở đây q là một số ngẫu nhiên phân phối đều trong [0, l], q0 là một tham số (0q0 1), còn j là đỉnh được chọn theo công thức (1.1) với =1. Qui tắc chọn thành phố theo công thức (1.1) và (1.4) được gọi là qui tắc tỉ lệ giả ngẫu nhiên (pseudo-random proportional rule). Theo qui tắc chọn thành phố mới này, hướng các con kiến di chuyển đến các nút được nối với cạnh ngắn có lượng mùi lớn. Tham số q0 quyết định mức quan trọng tương quan giữa sự khai thác các đường đi cũ đối với sự khám phá đường đi mới. Quy tắc cập nhật mùi : Mùi sẽ được cập nhật theo cả hai quy tắc : Cập nhật địa phương và cập nhật toàn cục. Cập nhật mùi địa phƣơng: Trong khi đang xây dựng một lời giải (tức là đường đi) của mình, mỗi con kiến sẽ cập nhật mùi cho cạnh (i, j) mà nó đi qua bằng cách áp dụng qui tắc cập nhật địa phương của công thức (1.5).  ij  (1   ) ij   (i, j ) (1.5) Ở đây 0 <  < 1 gọi là tham số bay hơi mùi,  (i, j) có thể lấy một trong 2 giá trị sau: *  ( i, j) = 0, ở đây 0 là mùi khởi đầu. *  (i, j) = 0 - 14 - Luật này có tác dụng giúp các con kiến tránh hội tụ về cùng một đường đi, điều này giải thích không khó: khi đặt 0 = (nLnn-1) trong đó n là số đỉnh, Lnn là chiều dài của một lời giải do một heulistic sinh ra từ trước (giai đoạn khởi tạo và do  (i,j) (i, j)  (i, j) nên cứ sau mỗi lần cập nhật địa phương i,j lại giảm đi một lượng ((i, j)-  (i, j)) làm giảm đi mức độ "hấp dẫn" của các cạnh được thăm khiến cho các con kiến sẽ chú ý thăm các cạnh chưa bao giờ được thăm, tránh được tình trạng hội tụ tới cùng một đường đi. Ngoài ra ACS sử dụng một cấu trúc dữ liệu gọi là danh sách tuyển chọn (candidate list-cl), cấu trúc này có nhiệm vụ cung cấp thêm thông tin heuristic cục bộ cho thủ tục xây dựng lời giải. Với một thành phố cho trước, danh sách này sẽ chứa hữu hạn cl thành phố lân cận được ưu tiên đến hơn (cl là một tham số của thuật toán). Các con kiến khi đến một thành phố bất kì, nó sẽ đọc tuần tự danh sách này từ đầu đến cuối (danh sách được sắp theo thứ tự tăng dần của khoảng cách nối thành phố hiện lại với thành phố lân cận tương ứng) và chọn thành phố đầu tiên chưa nằm trong đường đi của nó làm thành phố kế tiếp, khi không có thành phố nào trong danh sách thỏa mãn tính chất này thì các thành phố bên ngoài danh sách chưa được thăm sẽ được chọn theo luật chuyển trạng thái. Các kết quả khi chạy ACS trên các bài toán chuẩn được đem so sánh với các siêu heuristic khác đã cho thấy ACS là heuristic tốt nhất về chất lượng lời giải cũng như thời gian thực hiện (có thể không quan trọng vì các heuristic khác có thể thực hiện trên các máy khác nhau và được viết mã chưa tối ưu…) Cập nhật mùi toàn cục : Trong ACS chỉ duy nhất con kiến toàn cục tốt nhất (là con kiến đã xây dựng đường đi ngắn nhất trong các bước lặp) là được phép rải mùi. Sự chọn lựa này cùng với việc sử dụng qui tắc tỉ lệ giả ngẫu nhiên nhằm mục đích làm cho việc tìm kiếm thực tế hơn: Các con kiến tìm kiếm trong một lân cận của - 15 - đường đi tốt nhất được tìm thấy cho đến bước lặp hiện tại của thuật toán. Việc cập nhật toàn cục được thực hiện sau khi tất cả các con kiến đã hoàn thành xong đường đi của chúng. Mùi được cập nhật bởi qui tắc cập nhật toàn cục của công thức (1.6). Cập nhật mùi toàn cục được áp dụng cho những cạnh (i, j) thuộc đường đi ngắn nhất w*(t) theo công thức :  i , j  (1   ) i , j  1 Lgl (t ) (1.6) Trong đó Lgl (t) là độ dài đường đi ngắn nhất w*(t). 1.3.3. Thuật toán hệ kiến Max-Min Hệ kiến Max-Min (Max-Min Ant System-MMAS) được cải tiến từ AS bằng cách chỉ cho phép một con kiến tốt nhất cập nhật mùi (con kiến có hành trình tốt nhất w(t) kể từ khi bắt đầu thuật toán hoặc con kiến có hành trình tốt nhất w(t) tại bước lặp hiện tại). Để tránh hiện tượng tắc nghẽn (stagnation): do nồng độ mùi tập trung ở một số cung quá cao nên các con kiến lựa chọn đi lựa chọn lại các cung đó, MMAS đưa vào hai cận, cận trên (  max ) và cận dưới ( min ) để khống chế nồng độ các vết mùi trên mỗi cung. Chính vì vậy thuật toán được gọi là hệ kiến Max-Min về sau các thuật toán ACO có tính chất này cũng gọi là thuật toán Max-Min. MMAS khống chế nồng độ các vết mùi bằng cách sử dụng cận dưới  min có giá trị nhỏ nhất và cận trên có giá trị lớn nhất là  max , nghĩa là tất cả các cạnh ít được con kiến đi qua có xác suất nhỏ nhưng vẫn lớn hơn 0 nhiều lần và hạn chế lựa chọn đi lựa chọn lại một cạnh tốt của các con kiến (cạnh này tập trung mùi mạnh). Điều này làm cho thuật toán tránh được tình trạng tắc nghẽn trong quá trình tìm kiếm, đặc biệt khi số vòng lặp lớn nó sẽ tăng khả năng khám phá cho những con kiến. Các vết mùi khi khởi tạo luôn có giá - 16 - trị lớn nhất cho tất cả các cạnh làm cho luôn đạt được sự bốc mùi mạnh, hấp dẫn các con kiến. Sau mỗi lần lặp trên tất cả các cạnh, lượng mùi đều bị bốc hơi theo một tỷ lệ như nhau, do tham số  . Chỉ các cạnh thuộc lời giải tốt nhất toàn cục w*(t) mới được rải thêm một lượng mùi do chính con kiến tìm ra lời giải đó thực hiện (trong thực nghiệm lời giải tốt trong vòng lặp hiện tại được rải thêm mùi sẽ tốt hơn vì nó tăng khả năng khám phá cho các con kiến). Nồng độ mùi trên các cạnh ít được sử dụng sẽ giảm chậm nhưng trên các cạnh thuộc lời giải tốt vẫn được gia tăng nên các con kiến vẫn ưa chọn nhiều hơn. Trong hệ kiến Max-Min thủ tục xây dựng lời giải giống như trong AS còn quy tắc cập nhật mùi thực hiện như sau: Cập nhật mùi:  ij  (1   ) ij   ij  L1 ( w(t ))  trong đó  ij    max{ min  (1   ) ij ,0} (1.7) (i, j) w(t) (1.8) ngược lại Nhược điểm của thuật toán này là sẽ tập trung vào khai thác các lời giải tốt tìm được mà không phân biệt được các cạnh không dùng được với các cạnh dùng được nhưng không thuộc lời giải tốt. Do đó sẽ hạn chế khả năng khám phá nếu chọn  min bé, còn nếu chọn  min lớn thì thuật toán sẽ gần với tìm kiếm ngẫu nhiên dựa trên thông tin heuristic, nhưng điều này lại giảm khả năng học tăng cường-một ưu điểm trong các thuật toán kiến. Vì vậy chọn tỷ lệ giữa  min và  max ảnh hưởng rất nhiều đến hiệu suất của thuật toán.