Luận văn Phương pháp tối ưu hoá đàn kiến

h về phía chúng. Vì thế mùi sẽ bắt đầu tích lũy nhanh hơn trên nhánh ngắn, cuối cùng hầu hết các con kiến sẽ chọn nhánh này theo như sự tương tác giữa các con kiến được mô tả ở thí nghiệm trước. Điều thú vị quan sát được là thậm chí khi một nhánh dài gấp đôi nhánh kia thì không phải tất cả các con kiến sử dụng nhánh ngắn hơn mà có một lượng nhỏ kiến chọn nhánh dài hơn. Đây là cách để kiến có thể khám phá được những con đường mới. 1.3. Một số thuật toán ACO áp dụng cho bài toán TSP Bài toán Travelling Salesman Problem (TSP) là bài toán tối ưu tổ hợp kinh điển và nổi tiếng. Bài toán này đóng một vai trò quan trọng trong nghiên cứu các thuật toán ACO. TSP được chọn làm bài toán tối ưu tổ hợp điển hình và để áp dụng các thuật toán ACO bởi vì: nó là một bài toán NP-khó và thường nảy sinh nhiều trong các ứng dụng, dễ dàng áp dụng các thuật toán ACO ; nó cũng là một bài toán rất trực quan, dễ hiểu không như nhiều bài toán NP-khó khác; các bước thực thi của thuật toán ACO trên bài toán TSP là dễ hình dung, không có nhiều khó khăn về mặt kỹ thuật. Phần này ta sẽ giới thiệu chi tiết về các thuật toán AS, MMAS, ACS thông qua việc ứng dụng nó vào giải quyết bài toán TSP. 10 1.3.1. Bài toán TSP Nội dung bài toán như sau: Một người chào hàng xuất phát từ thành phố của anh ta, anh ta muốn tìm một đường đi ngắn nhất đi qua tất cả các thành phố của khách hàng mỗi thành phố đúng một lần sau đó trở về thành phố ban đầu. TSP được phát biểu vào thế kỷ 17 bởi hai nhà toán học vương quốc Anh là Sir William Rowan Hamilton và Thomas Penyngton Kirkman, và được ghi trong cuốn gsiáo trình Lý thuyết đồ thị nổi tiếng của Oxford. Nó nhanh chóng trở thành bài toán khó thách thức toàn thế giới bởi độ phức tạp thuật toán tăng theo hàm số mũ (trong chuyên ngành thuật toán người ta còn gọi chúng là những bài toán NP-khó). Người ta bắt đầu thử và công bố các kết quả giải bài toán này trên máy tính từ năm 1954 (49 đỉnh), cho đến năm 2004 bài toán giải được với số đỉnh lên tới 24.978, và dự báo sẽ còn tiếp tục tăng cao nữa. Bài toán TSP có thể phát biểu dưới dạng đồ thị như sau: Cho G = (N, A,) là đồ thị có hướng đầy đủ có trọng số, trong đó N là tập hợp của n = |N| nút (thành phố) , A = {(i,j)| (i,j) є VxV} là tập tất cả các cung của đồ thị. Mỗi cung (i, j) được gán một trọng số dij để biểu diễn khoảng cách giữa 2 thành phố i và j. Bài toán TSP trở thành bài toán tìm chu trình Hamilton có độ dài ngắn nhất trên đồ thị G. Ta cần phân biệt hai loại TSP, symmetric TSP có khoảng cách giữa các thành phố không phụ thuộc vào hướng dij = dji với mọi thành phố i, j và asymmetric TSP – ATSP tồn tại ít nhất một cặp cạnh sao cho dij ≠ dji. Đối với đồ thị không đối xứng có (n-1)! đường đi chấp nhận được còn đối với đồ thị đối xứng có (n-1)!/2 đường đi có khả năng. Khi n lớn ta không thể tìm được lời giải tối ưu bằng các thuật toán vét cạn, hướng đi giải quyết bài toán là tìm các lời giải xấp xỉ tối ưu bằng các thuật toán heuristic, hoặc các thuật toán tiến hóa. Hình sau đây (hình 2.a và 2.b) đưa ra 2 ví dụ về bài toán TSP, được lấy từ TSPLIB website (xem [14]). 11 Hình 2.a – Thể hiện các đỉnh trong thư viện TSP att532, tương ứng với 532 thành phố của Mỹ. Hình 2.b – Thể hiện các đỉnh trong TSPLIB pcb1173 biểu diễn 1173 lỗ trên một bảng mạch in. Bảng 2. Một số thuật toán ACO và khả năng giải quyết bài toán TSP ACO algorithms TSP Ant System Yes Elitist AS Yes Ant-Q Yes Ant Colony System Yes Max-Min AS Yes Rank-based AS Yes ANTS No Hyper-cube AS No 12 1.3.2. Ant System (AS) Thuật toán Ant System (AS) như đã giới thiệu là thuật toán đầu tiên trong lớp các thuật toán ACO được đề xuất bởi Dorigo trong luận án tiến sỹ của ông năm 1991(tham khảo [2], [3]). AS và cũng như nhiều thuật toán ACO cải tiến từ AS đều chọn TSP làm bài toán thực nghiệm đầu tiên. Phương pháp giải TSP bằng AS Đầu tiên là xây dựng đồ thị, n đỉnh biểu diễn cho n thành phố. Vệt mùi: mỗi cạnh được (i, j) được gắn một vệt mùi τij. Thông tin heuristic: ηij là nghịch đảo khoảng cách giữa hai thành phố (i, j) ηij = 1/ dij Trong phần lớn các thuật toán ACO cho bài toán TSP người ta đều sử dụng thông tin heuristic như trên. Có hai quá trình chính trong thuật toán AS là quá trình xây dựng lời giải và quá trình cập nhật các vệt mùi. Xây dựng lời giải: Có m con kiến nhân tạo được đặt khởi tạo ngẫu nhiên tại các đỉnh, và tại mỗi bước lặp của thuật toán, mỗi con kiến sẽ xây dựng lời giải riêng của nó bằng cách chọn một đỉnh mà chúng chưa thăm để đi. Ban đầu các vệt mùi được khởi tạo bởi giá trị τ0, mỗi con kiến được đặt ngẫu nhiên tại một đỉnh xuất phát và lần lượt đi thăm các đỉnh còn lại để xây dựng đường đi với theo quy tắc như sau (gọi là quy tắc random proportional), con kiến thứ k đang ở đỉnh i sẽ chọn đỉnh j tiếp theo với xác suất:                 0 )( )( )( k iNl ilil ijij k ij t t tP     (1.1) trong đó cường độ vệt mùi τij(t) và thông tin heuristic ηij ta đã giới thiệu ở trên. ngược lại k iNj  13 Hai tham số α và β là hai tham số xác định sự ảnh hưởng của vệt mùi và thông tin heuristic : nếu α = 0 các thành phố gần nhất có nhiều khả năng được chọn, thuật toán trở nên giống với thuật toán heuristic thông thường, nếu β = 0 chỉ có thông tin về cường độ vệt mùi được sử dụng mà không hề có bất kỳ một thông tin heuristic nào làm cho kết quả tìm kiếm được nghèo nàn và bài toán đễ rơi vào trường hợp cực tiểu địa phương. Nik là các láng giềng có thể đi của con kiến k khi nó ở đỉnh i, đó là tập các đỉnh chưa được con kiến thứ k đi qua (xác suất chọn một đỉnh nằm ngoài Nik là 0). Với luật xác suất này, thì xác suất để chọn một cạnh (i, j) tăng lên khi mà mùi τij và thông tin heuristic ηij tương ứng của cạnh đó tăng. Mỗi con kiến có một bộ nhớ Mk chứa danh sách các thành phố mà chúng đã đến thăm theo thứ tự. Nó được dùng để tính toán tập các láng giềng chưa thăm Nik trong công thức xác suất (1.1) ở trên. Mk cũng cho phép các con kiến tính toán quãng đường mà nó đã đi được và giúp kiến xác định được cạnh nó đi qua để cập nhật mùi. Chú ý rằng trong khi xây dựng lời giải, có hai cách cài đặt nó: song song và tuần tự. Với cách cài đặt song song, tại mỗi bước xây dựng lời giải tất cả các con kiến đều di chuyển từ thành phố của chúng đến thành phố tiếp theo. Trong khi đó với phương pháp cài đặt tuần tự thì sau khi một con kiến hoàn tất đường đi của nó, con kiến tiếp theo mới bắt đầu xây dựng đường đi của nó. Đối với thuật toán AS thì cả hai cách cài đặt trên là tương đương, tức là chúng không gây ra ảnh hưởng quan trọng gì đến thuật toán. Sau này ta sẽ thấy với thuật toán AS thì không như thế. Cập nhật mùi Sau khi tất cả các con kiến xây dựng xong các lời giải của chúng, các vệt mùi sẽ được cập nhật. Đây là hình thực cập nhật offline sẽ nói đến sau. Đầu tiên tất cả các cạnh sẽ bị mất đi một lượng mùi (do bị bay hơi), sau đó những cạnh mà có các con kiến đi qua sẽ được tăng cường thêm một lượng mùi. Công thức thức bay hơi mùi: )()1()1( tt ijij   Lji  ),( (1.2) trong đó 0 < ρ <= 1 là tỉ lệ bay hơi mùi, tham số ρ được dùng để tránh sự tích lũy không có giới hạn của các vết mùi và nó làm cho thuật toán quên đi những quyết định 14 tồi ở bước trước. Nếu một cạnh không được chọn bởi bất kì con kiến nào thì cường độ mùi của nó sẽ bị giảm theo hàm mũ của số vòng lặp. Sau khi bay hơi mùi tất cả các con kiến sẽ tăng cường mùi cho những cạnh mà chúng đã đi qua theo công thức: )()()1( 1 ttt kij m k ijij     (1.3) trong đó      0 1 )( kkij Ct nếu (i,j) thuộc T k và ngược lại (1.4) Ck là độ dài của tuyến đường Tk được xây dựng bởi con kiến k. Với công thức (1.4), tuyến đường của những con kiến nào mà càng tốt hơn thì nó càng được tăng cường thêm nhiều mùi. Nói tóm lại thì những cạnh mà được nhiều con kiến lựa chọn thì sẽ nhận được nhiều mùi hơn và có nhiều khả năng hơn sẽ được lựa chọn bởi các con kiến trong các vòng lặp tiếp theo của thuật toán. Ưu điểm của AS: Việc tìm kiếm ngẫu nhiên dựa vào trên các thông tin heuristic làm cho phép tìm kiếm linh hoạt và mềm dẻo trên không gian rộng 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 với học tăng cường (reinforcement learning) trong đó những lời giải tốt hơn sẽ được sự tăng cường 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 và vẫn không loại bỏ các lời giải tốt, do đó nâng cao chất lượng thuật toán. Nhược điểm của AS: Hiệu suất của nó giảm đột ngộ so với nhiều thuật toán metaheuristic khác khi mà kích thước của bài toán tăng lên. Bởi vì khi số đỉnh của đồ thị lớn thì cường độ vệt mùi trên những cạnh không thuộc lời giải tốt (hoặc ít được con kiến lựa chọn) sẽ nhanh chóng giảm dần về 0, làm cho cơ hội khám phá hay tìm kiếm ngẫu nhiên của thuật toán sẽ giảm mà đây là một trong những điểm mạnh của các thuật toán mô phỏng tiến hóa tự nhiên nên thuật toán hệ kiến AS kém hiệu quả. 15 Vì thế, thực tế là các nghiên cứu về ACO ngày nay tập trung vào việc làm thế nào để cải tiến AS. 1.3.3. Max-Min Ant System (MMAS) MMAS và một số thuật toán khác như Elitist AS, Rank-Based AS là các thuật toán có được hiệu suất cao hơn nhiều so với thuật toán AS nhờ vào những thay đổi nhỏ trong thuật toán AS, đây được coi là các thuật toán kế thừa trực tiếp từ thuật toán AS vì chúng về cơ bản là không khác gì nhiều so với AS. MMAS đưa ra bốn thay đổi chính đối với AS. Thứ nhất, nó chú trọng nhiều vào những tuyến đường tốt nhất được tìm thấy : MMAS, chỉ cho phép con kiến tốt nhất hoặc là tại vòng lặp hiện tại iteration-best , hoặc tính từ thời điểm bắt đầu best-so-far được phép cập nhật mùi. Tuy nhiên việc này sẽ dẫn đến hiện tượng ứ đọng, tập trung (stagnation) quá nhiều khi mà tất cả các con kiến đều cùng chọn một tuyến đường đi, do sự tăng lên quá thừa của cường độ các vết mùi trên các cạnh tốt. Để tránh hiện tượng trên một cải tiến thứ hai là MMAS giới hạn cường độ mùi trong một khoảng cố định [τmax , τmin]. Tất cả vệt mùi trên các cạnh đều nằm trong khoảng này. Thứ ba, các vệt mùi được khởi tạo là cận trên của vệt mùi τmax , cùng với việc một tỉ lệ bay hơi mùi nhỏ sẽ làm tăng khả năng khám phá cho các con kiến ngay từ khi bắt đầu. Cuối cùng, trong thuật toán MMAS các vệt mùi sẽ được khởi tạo lại nếu như hệ thống rơi vào trạng thái stagnation, hoặc không thể cải thiện được tuyến đường đã tạo ra sau một số lượng các vòng lặp liên tiếp. Cập nhật mùi Cũng như thuật toán AS, sau khi tất cả các con kiến xây dựng xong lời giải của chúng tất cả các vết mùi đều bay hơi một lượng phụ thuộc vào tham số bay hơi mùi (xem công thức 1.2). 16 Sau đó cường độ mùi trên mỗi cạnh có con kiến tốt nhất đi qua được cập nhật một lượng theo công thức : best ijijij   (1.5) Với bestbestij C 1 , với Cbest hoặc là độ dài của tuyến đường tốt nhất tại vòng lặp hiện tại, hoặc là độ dài của tuyến đường tốt nhất từ khi bắt đầu thuật toán. Khi ta sử dụng luật update best-so-far thì quá trình tìm kiếm sẽ tập trung nhanh chóng vào tuyến đường tốt nhất từ đầu đến hiện tại. Còn khi sử dụng update iteration-best thì số lượng các cạnh được tăng cường mùi là nhiều hơn và sự tìm kiếm cũng phân tán hơn. Các kết quả thực nghiệm cho thấy rằng, với những bài toán TSP nhỏ thì tốt nhất là chỉ sử dụng update iteration-best . Trong khi đó với những bài toán TSP lớn khoảng vài trăm đỉnh thì hiệu suất tốt nhất đạt được với việc sử dụng chú trọng đến update best-so-far. Giới hạn vết mùi MMAS sử dụng hai cận trên (τmax) và cận dưới (τmin) để khống chế nồng độ mỗi mùi trên mỗi cạnh với mục đích tránh cho thuật toán khỏi hiện tượng tắc nghẽn tìm kiếm. Cụ thể hơn, giới hạn của vệt mùi sẽ làm cho xác suất pij của việc chọn thành phố j khi kiến ở thành phố i bị giới hạn trong khoảng [pmin, pmax]. Nhược điểm của thuật toán này là sẽ tập trung tìm kiếm vào các cạnh thuộc lời giải tốt nhất tìm được, vì vậy hạn chế khả năng khám phá nếu τmin chọn bé. Ngoài ra khi chọn τmin bé thì gần như các thông tin heuristic được tận dụng triệt để, còn các cường độ mùi sẽ bị giảm nhanh và không có tác dụng mấy. 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 và ít phụ thuộc vào các thông tin heuristic đồng thời khả năng học tăng cường cũng giảm theo. 17 1.3.4. Ant Colony System (ACS) Trong khi MMAS là thuật toán chỉ thay đổi phần nhỏ từ thuật toán AS, thì các thuật toán khác như ACS, Ant-Q ,.. đạt được hiệu suất cao bằng cách đưa hẳn các kỹ thuật hoàn toàn mới mà ý tưởng của nó không có trong thuật toán AS cơ bản. Đây là những thuật toán mở rộng của AS. Thuật toán ACS khác với AS ở ba điểm chính. Thứ nhất, nó lợi dụng kinh nghiệm tích lũy được từ những con kiến hơn nhiều so với thuật toán AS thông qua việc dùng một luật lựa chọn đỉnh linh hoạt hơn. Thứ hai, sự tăng cường mùi và bay hơi mùi chỉ áp dụng trên những cạnh thuộc tuyến đường đi tốt nhất từ trước tới hiện tại. Thứ ba, mỗi khi một con kiến sử dụng một cạnh (i, j) để di chuyển từ thành phố i sang j, nó sẽ lấy đi một ít mùi từ cạnh đó để tăng khả năng khám phá đường đi. Sau đây là chi tiết của các cải tiến. Xây dựng lời giải Trong ACS giả sử con kiến k đang ở đỉnh i, nó sẽ chọn đỉnh j tiếp theo nhờ quy tắc sau (pseudorandom proportional ) với công thức:        elseJ qqif j ililNl k i 0}][{maxarg  (1.6) trong đó q là giá trị ngẫu nhiên phân phối đều trong đoạn [0, 1] q0 (0q01) là một tham số J là đỉnh ngẫu nhiên dựa vào phân phối xác suất theo công thức (1.1) với α = 1. Như vậy với xác suất q0 các con kiến sẽ chọn đường đi tốt nhất có thể theo chỉ dẫn của các thông tin heuristic và sự tích lũy mùi, trong khi với xác suất 1-q0 các con kiến sẽ thiên về hướng khám phá bằng công thức phân phối xác suất. Sự điều chỉnh tham số q0 cho phép điều chỉnh mức độ khám phá và lựa chọn hoặc tập trung tìm kiếm xung quanh tuyến đường tốt nhất tính từ đầu (best-so-far solution) hoặc khám phá các tuyến đường khác. 18 Cập nhật mùi toàn cục:(global pheromone trail update) Cập nhật mùi toàn cục: chỉ cập nhật sau khi các con kiến đã xây dựng xong lời giải của mình và chỉ cho phép một con kiến tốt nhất (tính đến thời điểm hiện tại) được phép cập nhật mùi sau mỗi vòng lặp. Công thức: bsijijij   )1( (1.7) Với bsbsij C 1 Trong đó Cbs là độ dài của tuyến đường đi tốt nhất tính đến thời điểm hiện tại. Một điểm quan trọng trong quá trình cập nhật mùi của ACS là cả bay hơi và tăng cường mùi đều chỉ thực hiện trên những cạnh thuộc đường đi tốt nhất (best-so-far tour) không phải trên tất cả các cạnh như AS. Điều này là quan trọng vì độ phức tạp tính toán của cập nhật mùi tại mỗi vòng lặp giảm từ O(n2) xuống O(n) (với n là số đỉnh của bài toán). Tham số ρ ở đây vẫn là tham số bay hơi mùi như trên. Trong thực nghiệm người ta đã cân nhắc việc sử dụng đường đi tốt nhất tại vòng lặp hiện tại (iteration-best) để cập nhật mùi. Mặc dù với những thí nghiệm với bài toán TSP có kích thước nhỏ thì sự khác biệt giữa việc sử dụng hai cách cập nhật mùi trên là không nhiều, nhưng với những bài toán có kích thước lớn khoảng hơn 100 thành phố trở lên thì việc sử dụng tuyến đường best-so-far cho kết quả tốt hơn nhiều. Cập nhật mùi địa phương (local pheromone trail update) Một sự cải tiến thêm trong quá trình update mùi của thuật toán ACS là trong khi xây dựng lời giải của mình, mỗi con kiến sẽ cập nhật mùi ngay lập tức cho cạnh (i,j) mà nó vừa đi qua theo công thức (gọi là công thức cập nhật mùi địa phương) 0)1(   ijij (1.8) với  ( 0< <1) và 0 là hai tham số 19 giá trị 0 là giá trị khởi tạo cho các vệt mùi. Nhiều thực nghiệm đã tiến hành cho thấy 0.1 là giá trị tốt cho  , còn một giá trị tốt cho 0 là 1/nC nn với n là số lượng các thành phố và Cnn là độ dài của một nearest- neighbor tour. Quá trình local update làm cho lượng mùi trên mỗi cạnh giảm đi một ít sau mỗi lẫn con kiến đi qua một cạnh, làm cho kiến ít bị thu hút bởi các cạnh đó hơn. Hay nói cách khác local update làm tăng khả năng khám phá các đường đi chưa được đến thăm, và trong thực nghiệm việc này không gây ra hiện tượng ứ đọng các vết mùi (stagnation) như trong thuật toán MMAS. Tới đây ta có thêm một chú ý đáng quan trọng là trong các thuật toán ở trên không có chuyện gì xảy ra cho dù các con kiến xây dựng đường đi của chúng hoặc là song song hoặc là tuần tự. Tuy nhiên với ACS thì khác bởi do quá trình local update , trong phần lớn các cài đặt thuật toán ACS người ta đều để cho các con kiến xây dựng các đường đi song song. Cuối cùng thuật toán ACS cũng như MMAS cho thấy là kết quả thu được tốt hơn hẳn so với AS. 1.3.5. Hệ kiến đa mức (xem [15]) Thuật toán hệ kiến MMAS đã làm rõ được khả năng học tăng cường và tìm kiếm ngẫu nhiên của đàn kiến nhưng chưa thể hiện được khả năng điều chỉnh hai ưu điểm này của các thuật toán đàn kiến, ý tưởng ở đây xuất phát từ việc không giữ nguyên giá trị của hai cận min ( 0 ) và max ( 2 ) và thay đổi nó trong các vòng lặp chạy để điều khiển sự học tăng cường và tìm kiếm ngẫu nhiên bằng cách tăng dần cận 2 sau mỗi bước lặp. Lúc đó, quy tắc cập nhật mùi được thực hiện như sau : Cập nhật mùi online : một con kiến đang ở đỉnh i và đi đến đỉnh j thì cạnh (i, j) được cập nhật mùi như sau : 1)1(   ijij (13) 20 Cập nhật mùi offline : sau khi tất cả các con kiến tìm ra hành trình của mình thì các cạnh thuộc hành trình của con kiến tốt nhất (i-best hoặc g-best) sẽ được cập nhật mùi theo công thức như sau : 2)1(   ijij (14) Ban đầu các cạnh có cường độ mùi ij được khởi tạo bằng 0 , trong quá trình chạy hai cận 1 và 2 sẽ được điều chỉnh, khi 1 được tăng lên sẽ tiết kiệm được quá trình bay hơi, còn 1 và 2 sẽ được tăng lên theo tỷ lệ điều khiển quá trình học tăng cường và tìm kiếm ngẫu nhiên. Quá trình học tăng cường sẽ thực hiện khi 1 và 2 xích ra xa nhau còn ngược lại sẽ là quá trình tìm kiếm ngẫu nhiên, sở dĩ có được điều này là do theo 2 qui tắc cập nhật mùi (13) và (14) thì các cạnh có con kiến đi qua sẽ tiến về 1 còn các cạnh thuộc hành trình của con kiến tốt nhất sẽ tiến về 2 , và theo cách cập nhật mùi này thì không cần quá trình bay hơi nữa vì trong mỗi vòng lặp hai cận điều khiển được tăng lên như vậy các cạnh ít không thay đổi mà các cạnh thuộc hành trình của con kiến hoặc các cạnh thuộc hành trình của con kiến tốt nhất tiến về hai cận đó cho nên coi như là các cạnh ít sử dụng bị bay hơi. Ý tưởng thì cải tiến này là rất hay nhưng lại cực kỳ gây khó khăn cho người làm thực nghiệm khi phải điều chỉnh tỷ lệ thích hợp của việc tăng hay giảm tỷ lệ giữa 1 và 2 . 1.4. Các nguyên tắc khi áp dụng tối ưu đàn kiến Các chú ý sau đây làm tăng khả năng cho thuật toán ACO khi áp dụng vào các bài toán khác nhau. Có nhiều vấn đề cần quan tâm khi ta áp dụng các thuật toán ACO để giải quyết một bài toán, chẳng hạn lựa chọn số lượng kiến, lựa chọn các tham số khác, xác định các vết mùi, xác định các thông tin heuristic và sử dụng tìm kết hợp kiếm địa phương... 21 1.4.1. Số lượng kiến Số lượng kiến trong các bài toán khác nhau cần có những điều chỉnh khác nhau. Nếu số lượng kiến quá nhiều thì quá trình tìm kiếm sẽ mất nhiều thời gian tính toán, đồng thời chưa chắc đã tăng hiệu quả tìm kiếm lên. Tất nhiên là nếu số lượng kiến quá ít thì quá trình tìm kiếm sẽ rất khó khăn bởi vì với số ít các con kiến thì ít các đường đi được chọn tại mỗi vòng lặp và do đó, sự tích lũy các thông tin mùi là mất nhiều thời gian và số tuyến đường mà các con kiến lựa chọn cũng trở nên đơn điệu vì có quá ít các con kiến. Số lượng kiến phụ thuộc vào thuật toán cài đặt và phụ thuộc vào kích thước của bài toán cần giải quyết. Chẳng hạn với thuật toán AS người ta thường chọn số kiến là bằng số đỉnh. Với thuật toán MMAS thì với những bài toán nhỏ thì người ta chỉ chọn từ 2 – 10 con kiến, còn với những bài toán có kích thước khoảng vài trăm đỉnh trở lên thì người ta tăng dần số đỉnh lên. 1.4.2. Xác định các vệt mùi Quá trình học tăng cường có tác dụng nâng cao hiệu quả của thuật toán trong quá trình các con kiến tìm kiếm lời giải. Một trong những điều quan trọng đầu tiên trong việc áp dụng các thuật toán ACO là công việc xác định thông tin học tăng cường qua các vệt mùi, nói cách khác là xác định thông tin mà vệt mùi biểu diễn. Chẳng hạn, với bài toán TSP, vệt mùi ij giữa các cạnh có tác dụng biểu diễn sự thích hợp của việc chọn thành phố j sau khi đã thăm thành phố i, nói cách khác nó là một thông tin để thể hiện mối quan hệ giữa thành phố i và thành phố j. Cụ thể ở bài toán này ta chọn định nghĩa các vệt mùi ij là khả năng đường đi từ thành phố i đến thành phố j có thuộc đường đi các con kiến lựa chọn hay không, tức là mức độ ưu tiên của đoạn đường này. Việc định nghĩa các vệt mùi ảnh hưởng rất nhiều đến hiệu quả của thuật toán, nếu đưa ra một lựa chọn không tốt thì thuật toán có thể trở nên rất là xấu. Với phần nhiều các bài toán ứng dụng của ACO các lựa chọn dựa trên trực quan mà người ta nhận thấy ngay thường đưa lại hiệu quả tốt. 22 1.4.3. Các thông tin heuristic Các thông tin heuristic là một trong các thông tin quan trọng trong các thuật toán ACO. Các thông tin heuristic thể hiện mối quan hệ giữa các đỉnh và nó chính là thông tin mà ta thu được từ dữ liệu đầu vào của bài toán, nó thể hiện các tri thức có được từ bài toán. Nó được kết hợp với quá trình tìm kiếm địa phương để cải tiến lời giải. Tìm kiếm địa phương cho phép có được những thông tin chi phí để cải tiến lời giải theo cách trực tiếp hơn. Khi kết hợp các thuật toán ACO với phương pháp tìm kiếm địa phương sẽ tìm ra được những lời giải tốt hơn cho những bài toán khó xây dựng được những thông tin heuristic. Trong các bài toán tĩnh, các thông tin heuristic  sẽ chỉ cần tính một lần trước khi bắt đầu thuật toán, ví dụ trong ứng dụng TSP người ta định nghĩa thông tin heuristic dựa vào độ dài dij giữa các thành phố i và thành phố j, nó bằng nghịch đảo độ dài này ijij d/1 , tức là khoảng cách giữa các dỉnh càng nhỏ thì thông tin heuristic giữa chúng càng lớn. Các thông tin heuristic tĩnh có các đăc điểm thuân lợi sau : dễ tính toán, chỉ phải tính một lần trước khi bắt đầu thuật toán, và tại mỗi vòng lặp của thuật toán ACO có thể tính trước một bảng các giá trị  ])[( ijij t sẽ tiết kiệm được đáng kể thời gian tính toán. Trong trường hợp bài toán động, thông tin heuristic cần phải được tính tại mỗi bước đi của con kiến bởi vì chúng phụ thuộc vào các lời giải thành phần được xây dựng. Do đó quá trình này làm cho chi phí tính toán lớn nhưng có thể đạt được độ chính xác cao trong tính toán các giá trị heuristic . 1.4.4. Kết hợp tìm kiếm địa phương Việc sử dụng các thuật toán tìm kiếm địa phương là một yếu tố quyết định tính hiệu quả cho các ứng dụng ACO. Tuy nhiên việc áp dụng các thuật toán tìm kiếm địa phương vào các thuật toán ACO là không hề đơn giản. Rất nhiều các ứng dụng của các bài toán tối ưu tổ hợp như TSP, bài toán phân chia sản phẩm, hay bài toán định tuyến cho xe cộ, các thuật toán ACO đều cho ra kết quả tốt khi kết hợp các thuật toán tìm kiếm địa phương. Các thuật toán địa phương nhằm xác định ra một miền cục bộ trong lời giải hiện tại (thông qua các phép biến đổi, 23 xáo trộn láng giềng) và sau đó thực hiện tìm kiếm cụ bộ trong phạm vi nó định nghĩa để có được lời giải tối ưu toàn cục. Các thuật toán tìm kiếm địa phương thường tìm ra các lời giải tối ưu cục bộ và dùng những lời giải đó để cập nhật vệt mùi. Người ta nhận thấy trong nhiều bài toán, quá trình lặp lại các tìm kiếm địa phương ngay từ những lời giải ban đầu được sinh ra ngẫu nhiên không mang lại nhiều hiệu quả lắm. Do đo quá trình sinh ra các lời giải ban đầu cho các thuật toán tìm kiếm địa phương không mang lại các kết quả như ý và nó thực sự không phải là một nhiệm vụ đơn giản. Trên thực tế, khi kết hợp các thành phần của lời giải tối ưu cục bộ một cách ngẫu nhiên người ta thu được những lời giải mới hứa hẹn hơn cho thuật toán tìm kiếm địa phương. Bằng thực nghiệm, có thể thấy sự kết hợp của các lời giải tham lam thích nghi theo xác suất với các thuật toán tìm kiếm địa phương có thể đạt được những kết quả hơn cả. 1.4.5. Điều chỉnh giữa sự học tăng cường và sự khám phá Các thuật toán metaheuristic muốn có hiệu quả tốt thì cần có sự điều chỉnh phù hợp giữa việc sử dụng kinh nghiệm tìm kiếm với việc khám phá các không gian tìm kiếm mới. Các thuật toán ACO điều chỉnh được sự cân bằng giữa chúng thông qua qua việc điều chỉnh cập nhật các vệt mùi sao cho phù hợp. Tác dụng của các vệt mùi là đưa ra một sự phân bố xác suất lựa chọn trên không gian tìm kiếm, nó cho phép ta xác định được các phần nào trong không gian tìm kiếm mà tập trung nhiều giải hơn, cũng tức là có nhiều khả năng cho lời giải tối ưu ở đó. Khi đó nếu tập trung tìm kiếm trên các phần không gian này thì ta có quá trình học tăng cường tức là chỉ tập trung tìm kiếm trên các lời giải tốt hay nói cách khác là trên các cạnh có nhiều thông tin vệt mùi. Để sử dụng kinh nghiệm tìm kiếm của các con kiến ta có thể sử dụng một thủ tục kiểm tra hiệu suất của mỗi lời giải trong suốt quá trình cập nhật mùi. Một cách để tăng khả năng học tăng cường trong quá trình xây dựng lời giải bằng cách áp dụng luật chuyển trạng thái như trong thuật toán ACS, khi đó các con kiến sẽ tập trung nhiều hơn vào các lời giải tốt ở bước trước hơn so với thuật toán AS. Mặt trái của quá trình này là khả năng khám phá của các con kiến giảm đi vì chúng chỉ tập trung vào một phần nhỏ của không gian tìm kiếm. 24 Để tăng khả năng khám phá cho các con kiến thì rõ ràng là ta cần mở rộng không gian tìm kiếm lên bằng các phương pháp khác nhau. Quá trình này vừa có tác dụng giảm bớt sự tập trung quá nhiều vào các lời giải được cho là tốt, vừa có tác dụng đưa ra nhiều khả năng tìm kiếm cho các con kiến. Mở rộng không gian tìm kiếm trong ACO chính là các thủ tục xây dựng lời giải ngẫu nhiên của các con kiến. Xem xét khi thuật toán ACO không sử dụng thông tin heuristic (bằng cách đặt tham số 0 ). Trong trường hợp này, quá trình cập nhật mùi sẽ gây ra sự thay đổi từ không gian tìm kiếm mẫu cố định ban đầu thành một không gian mẫu khác và ở không gian này sự lựa chọn các phương án chỉ phụ thuộc vào cường độ các vết mùi. Việc mở rộng không gian tìm kiếm sẽ tốt hơn trong các vòng lặp ban đầu của thuật toán và sẽ giảm thiểu được sự tính toán. Để điều chỉnh sự tăng cường và khám phá người ta thường điều chỉnh các tham số  và  ,  ảnh hưởng đến các vết mùi còn  ảnh hưởng đến các thông tin heuristic. MMAS sử dụng một phương pháp đó là giới hạn cận dưới của các cường độ vệt mùi sao khi đó không gian tìm kiếm được điều chỉnh không trở nên thu hẹp quá mức. Khi mà bài toán đi vào bế tắc MMAS tức là với không gian tìm kiếm hiện tại không thể phát triển thêm lời giải thi nó khởi tạo lại các vệt mùi đồng nghĩa với việc tăng trở lại không gian tìm kiếm. Việc khởi tạo lại các vệt mùi kết hợp với các cải tiến lựa chọn cập nhật vệt mùi giúp MMAS tìm kiếm trên nhiều vùng không gian khác nhau. 1.4.6. Sử dụng giới hạn danh sách láng giềng Khi mà bài toán phải giải quyết có kích thước lớn thì đồng thời tại mỗi đỉnh các con kiến cũng phải lựa chọn giữa một tập rất lớn các láng giềng của nó. Đây là vấn đề lớn của thuật toán ACO vì nó làm tăng thời gian, và không gian tìm kiếm. Các con kiến phải tìm kiếm trên một không gian khổng lồ các phương án. Mong muốn của ta là giảm được không gian tìm kiếm này xuống càng nhỏ càng tốt nhưng vẫn đảm bảo cho hiệu suất của thuật toán ở mức cao. Để có thể giải quyết vấn đề nêu ta có thể giới hạn lại danh sách các đỉnh có thể lựa chọn tạm gọi là danh sách các láng giềng gần nhất (nearest neighbour). Danh sách các láng giềng gần nhất là tập con của tập các láng giềng của lời giải hiện tại. Danh sách này được tạo ra dựa trên các thông tin tri thức có sẵn của bài toán(các thông tin heuristic) nếu có hoặc các thông tin động được sinh ra. Đối với các bài toán tĩnh danh 25 sách này được tính toán ngay từ đầu .Việc sử dụng danh sách này cho phép các thuật toán ACO tập trung vào các những con đường có hứa hẹn đồng thời giảm không gian tìm kiếm đi rất nhiều. Hiện nay việc sử dụng các danh sách các láng giềng gần nhất đã được nhiều thực nghiệm chứng minh là có kết quả tốt hơn nhiều so với việc không sử dụng danh sách này. 1.5. Các ứng dụng của ACO Phương pháp ACO metaheuristic chủ yếu được áp dụng cho các bài toán tối ưu tổ hợp, ví dụ như ứng dụng vào bài toán TSP đã trình bày ở các phần trước. Một số bài toán tối ưu NP-khó như: Các bài toán lập lịch (job shop, flow shop, project scheduling) Bài toán phân chia sản phẩm (The Generalized Assignment Problem - GAP) Bài toán phủ tập hợp (The Set Covering Problem - SCP). Các bài toán trong học máy : bài toán phân lớp, mạng Bayes, ... Trong khi ở bài toán TSP và bài toán lập lịch là các bài toán hoán vị tức là lời giải của nó là các hoán vị các thành phần, thì lời giải của bài toán GAP là sự phân chia các nhiệm vụ cho các đại lý, còn trong bài toán SCP lời giải được thể hiện như là một tập con các thành phần lời giải, chúng đều thuộc lớp các bài toán tối ưu tổ hợp có thể sử dụng tối ưu đàn kiến để giải quyết. Ứng dụng của phương pháp ACO vào các bài toán động được đề cập ở đây chủ yếu là bài toán dò đường trong mạng dữ liệu chẳng hạn như mạng truyền thông internet hiện nay. Ví dụ như thuật toán AntNet, thuật toán ABC là các thuật toán khá thành công cho các bài toán định tuyến trên các mạng truyền tin theo gói tin (packed switched) như mạng truyền thông internet chẳng hạn. 26 CHƯƠNG 2. GIỚI THIỆU BÀI TOÁN DTSP 2.1. Bài toán DTSP Bài toán DTSP (Dynamic Travelling Salesman Problem) là mở rộng của bài toán TSP, với trọng số các cạnh có thể thay đổi hoặc số đỉnh có thể thay đổi tăng hoặc giảm theo thời gian. Mục đích là tìm ra nhanh nhất có thể được đường đi ngắn nhất mới xuất hiện sau mỗi lần đồ thị bị biến đổi. Định nghĩa bài toán DTSP: Cho n(t ) điểm (P1, P2, ... Pn(t)), và ma trận khoảng cách D={dij(t)} với i, j = 1, 2,... n(t). Tìm chu trình có độ dài nhỏ nhất chứa tất cả n(t) điểm. Ở đây n(t) và dij(t) là phụ thuộc vào thời gian t. Thông thường người ta chỉ xét bài toán đối xứng tức là: dij(t) = dji(t) DTSP là một trong các bài toán tối ưu tổ hợp động mà hiện nay người ta đang tìm cách giải bởi vì đây là bài toán có nhiều ý nghĩa trong thực tiễn và nói chung các bài toán động có nhiều ứng dụng trong thực tế hơn nhiều so với các bài toán tĩnh. Một bài toán tối ưu tổ hợp động khác mà nhiều người quan tâm là bài toán Network Routing Problem hay là bài toán định tuyến các gói tin trên mạng. Bài toán này có nhiều điểm tương đồng với bài toán DTSP và ứng dụng của nó thì không cần phải bàn cãi. 2.2. Các phương pháp giải bài toán DTSP Các bài toán tối ưu tổ hợp động là các bài toán đặc biệt và mỗi loại có một phương pháp giải riêng rất khác nhau. Tùy thuộc rất nhiều vào đặc điểm của mỗi bài toán mà ta thường đưa vào các kỹ thuật đặc biệt và chúng chỉ áp dụng được đối với loại bài toán đó, mà không đem lại hiệu quả khi áp dụng cho các bài toán khác. 27 Thậm chí DTSP cũng có nhiều loại khác nhau, chẳng hạn: khi thay đổi trọng số giữa các cạnh theo thời gian ta sẽ được một loại DTSP, một loại DTSP khác là thêm bớt các đỉnh theo thời gian tức là tại một thời điểm nào đó một hoặc nhiều đỉnh sẽ được thêm vào hoặc loại bỏ đi khỏi đồ thị. Ở bài khóa luận này đưa ra một phương pháp có hiệu quả cải tiến từ thuật toán AS để giải quyết loại bài toán DTSP trong đó mỗi con kiến phải vượt qua các tắc nghẽn. Các tắc nghẽn được đảm bảo rằng chỉ xảy ra trên những tuyến đường tốt nhất tại thời điểm hiện tại. Hơn nữa những tắc nghẽn ở đây giống như thực tế ở chỗ là nó tăng lên một thời gian sau đó thì giảm dần đến khi hết tắc nghẽn. Chi tiết hơn về vấn đề tắc nghẽn chúng ta sẽ đề cập tới ở phần sau. Một số phương pháp mà người ta đã sử dụng để giải bài toán DTSP: phương pháp di truyền học kết hợp với heurisric (xem [7]), phương pháp tính toán tiến hóa (xem [8], [9]), phương pháp mạng nơron cũng được sử dụng (xem [10]), tất nhiên phương pháp ACO cũng có những hiệu quả lớn (xem [12], [13]). 28 CHƯƠNG 3. SỬ DỤNG THUẬT TOÁN AS ĐỂ GIẢI QUYẾT BÀI TOÁN DTSP 3.1. Phân tích bài toán Bài toán DTSP mà chúng tôi đề cập ở đây là bài toán mở rộng từ bài toán TSP thông thường, tuy nhiên ta đưa thêm tắc nghẽn vào các con đường, do đó khi các con kiến xây dựng lời giải chúng sẽ gặp phải các đoạn đường có tắc nghẽn (xem [11]). Nếu xem khoảng cách giữa các thành phố là thời gian di chuyển thì chúng không còn cố định, thời gian sẽ tăng nếu tắc nghẽn càng tăng và ngược lại. Lưu ý rằng ở đây số lượng các đỉnh là cố định, ta chỉ xem như khoảng cách giữa các đỉnh là thay đổi. Ngoài ra một điểm quan trọng là các tắc nghẽn chỉ đưa ra trên những đoạn đường nằm trên tuyến đường tốt nhất tại thời điểm hiện tại. Tại một thời điểm xác định nào đó ta sẽ đưa vào các tắc nghẽn, chúng sẽ tăng dần đến một ngưỡng nào đó rồi lại giảm xuống trở về không. Đến phần thực nghiệm ta sẽ trình bày chi tiết về việc đưa vào các tắc nghẽn, về số lượng tắc nghẽn cũng như thời gian và cường độ tắc nghẽn. Trong các bài toán tĩnh, việc áp dụng phương pháp tăng cường và giảm bớt các vết mùi (pheromone) bằng cách update và bay hơi mùi đã đem lại hiệu quả tốt. Khi bắt đầu các con kiến sẽ khám phá khá nhiều con đường. Sau một thời gian khi mà tất cả các con đường không hứa hẹn dần bị loại ra khỏi không gian tìm kiếm bởi vì chúng không nhận được bất kỳ sự tăng cường mùi nào đồng thời lượng mùi trên đó vẫn bay hơi dần theo thời gian. Tuy nhiên trong bài toán động các phương án tồi trước khi có một sự biến đổi của môi trường có thể trở thành một phương án tốt về sau. Do đó nếu như thuật toán của ta hội tụ về trạng thái mà các phương án tồi như trên bị bỏ qua thì rất nhiều phương án hứa hẹn sẽ không được lấy và kết quả là ta thu được một tuyến đường không tối ưu nhiều. Chúng ta phải tìm cách nào đó tránh được hiện tượng này. 29 3.2. Cải tiến AS cho phù hợp Thêm cận dưới Như đã phân tích ở trên để tránh bỏ qua các phương án tồi ở thời điểm hiện tại, ta sẽ sử dụng một cận dưới mùi 0 tức là mùi trên tất cả các đoạn đường sẽ luôn lớn hơn hoặc bằng 0 . Như vậy sẽ không xảy ra hiện tượng mùi trên một đoạn đường sẽ trở về không nếu như nó không được con kiến nào lựa chọn. Đồng thời mà đưa thêm vào cận dưới ta cũng đã làm tăng thêm khả năng khám phá cho các con kiến. Tuy nhiên việc lựa chọn giá trị cận dưới cho phù hợp là điều rất quan trọng và đòi hỏi cần qua các bước thực nghiệm. Kỹ thuật shaking Một trong những thay đổi khác mà ta sẽ giới thiệu ngay đây là kỹ thuật shaking. Đây là một kỹ thuật sử dụng trong môi trường biến đổi, nó có tác dụng làm mịn cường độ vệt mùi trên tất cả các cạnh của đồ thị. Nếu lượng mùi trên một cạnh nào đó trở nên cao hơn rất nhiều so với tất cả các cạnh khác đi ra khỏi một thành phố thì cạnh này hầu như chắc chắn sẽ được các con kiến chọn. Điều này trong trường hợp bài toán tĩnh đảm bảo rằng một tuyến đường tốt sẽ luôn đi qua cạnh đó, nhưng hệ quả là nó ngăn cản các con kiến chọn các con đường khác ngay cả khi có tắc nghẽn xảy ra trên nó. Shaking sẽ thay đổi tỉ số giữa cường độ mùi trên tất cả các con đường, trong khi vẫn đảm bảo mối quan hệ về thứ tự, tức là: nếu )()( '' tt jiij   trước khi shaking thì sau khi shaking nó vẫn được giữ nguyên. Công thức shaking: ))/log(1()( 00  ijij t  Công thức này làm cho những cường độ mùi gần 0 dịch chuyển một khoảng nhỏ về phía 0 và những giá trị cao hơn dịch chuyển nhiều hơn về phía 0 . Để ý rằng 0 là giá trị nhỏ nhất vì thế điều kiện 0)(  tij được đảm bảo. Một vấn đề đối với shaking ở trên là nó có tính chất global, tức là nó ảnh hưởng đến cường độ mùi trên tất cả các đoạn đường. Khi chúng ta gặp một bài toán có kích 30 thước lớn, khi tắc nghẽn xảy ra (trên tuyến đường tốt nhất tại thời điểm đó) thì tuyến đường chỉ cần phải thay đổi trong một lân cận của tắc nghẽn. Do đó có rất nhiều thông tin bị mất đi trong quá trình global shaking. Vì thế để tránh mất mát chúng ta đưa ra định nghĩa local shaking. Local shaking cũng sử dụng công thức trên song chỉ áp dụng cho những đoạn đường gần hơn p.MaxDist đến một trong hai thành phố nơi xảy ra tắc nghẽn giữa chúng. Ở đây MaxDist là khoảng cách lớn nhất giữa hai thành phố bất kỳ trong bài toán TSP gốc (mà chưa có tắc nghẽn) còn p nằm trong khoảng (0, 1). Giả mã local shaking: if the distance between cities (a, b) changed then for every road (i, j) do if (dai < p ·MaxDist) ∨ (dbi < p ·MaxDist)∨ (daj < p ·MaxDist) ∨ (dbj < p ·MaxDist) then τij = τ0 · (1 + log(τij/t0)) endif endfor endif Lưu ý rằng chúng ta chỉ đưa tắc nghẽn vào những đoạn đường nằm trên tuyến đường tốt nhất hiện tại. Vì thế những cặp thành phố mà xảy ra tắc nghẽn nói chung là khá gần nhau, do đó sự ảnh hưởng của local shaking (với giá trị p) và global shaking là rất khác nhau. Một chú ý khác là với p=0 không có bất kỳ cạnh nào bị ảnh hưởng, global shaking tương đương với p=1 khi đó tất cả các vệt mùi đều bị thay đổi(shaking). Giá trị p được gọi là shaking-percentage. 31 CHƯƠNG 4. THỰC NGHIỆM VÀ ĐÁNH GIÁ Một vấn đề đặt ra trong việc ước lượng và đánh giá kết quả của chúng ta đó là thiếu một chuẩn hoàn chỉnh. Với bài toán TSP tĩnh có các chuẩn để kiểm chứng: thường chỉ là kết quả tốt nhất và đôi khi là thời gian cần để có các kết quả đó với một thuật toán xác định(trên một máy tính có cấu hình xác định). Với bài toán DTSP không có một chuẩn nào cả, chúng ta buộc phải đưa ra một chuẩn để có thể ước đo được hiệu suất của thật toán. Có một vài thứ hiển nhiên khi xem xét bài toán động. Bởi vì bài toán luôn thay đổi nên thuật toán cần đáp ứng trước những thay đổi đó nhanh nhất có thể. Trong trường hợp bài toán DTSP đưa ra ở trên khi mà một tắc nghẽn được tạo ra thì các con kiến phải nhanh chóng tìm được một tuyến đường tốt hơn mà không chứa đoạn đường tắc nghẽn. Vì tất cả các tắc nghẽn trong bài toán của ta được đưa vào dần dần trong một số bước vì thế trước khi tắc nghẽn đạt giá trị cao nhất các con kiến đã phải thay đổi đường đi của chúng rồi. Sau khi các con kiến thay đổi đường đi của chúng để tránh tắc nghẽn, thông thường một vài phần nằm trên tuyến đường tối ưu sẽ phải được điều chỉnh. Nghĩa là chúng ta muốn thấy một sự biến thiên lớn khi mà tắc nghẽn xảy ra, cũng tương đương với có một vài sự tối ưu đã được thực hiện trước khi những thay đổi tiếp theo xảy ra. Và cuối cùng độ dài của các tuyến đường hoàn tất phải là thấp nhất có thể. Đối với bài toán động thì có nghĩa là phải có một giá trị trung bình thấp. Khi thảo luận về kết quả của các thực nghiệm khác nhau trên ta sẽ phân tích về vấn đề này. Chúng ta sẽ tiến hành thực nghiệm trên bộ dữ liệu chuẩn TSP eil51 (xem [14]). Các bộ dữ liệu TSP có thể tìm kiếm trên mạng dễ dàng. Trong quá trình tính toán ta sẽ 32 đưa các tắc nghẽn vào để biến chúng thành bài toán động. Cụ thể các tắc nghẽn được đưa vào như thế nào sẽ được trình bày ngay trong phần thực nghiệm dưới đây. 4.1. Thực nghiệm trên tsplib eil51 Eil51 là một thư viện TSP có tổng cộng 51 đỉnh. Tại thời điểm mà ta đưa các tắc nghẽn lên các đoạn đường ta cần đảm bảo rằng các đoạn đường đó nằm trên đường đi khá tối ưu. Vì thế trước khi đưa các tắc nghẽn vào ta sẽ chạy khởi tạo thuật toán trong một thời gian đầu như là trường hợp bài toán TSP thông thường. Điều này đảm bảo rằng chúng ta sẽ tìm được ra các cặp thành phố khá gần nhau và tất nhiên là chúng nằm trên tuyến đường tốt nhất có thể tìm thấy. Chúng ta sẽ tiến hành thực nghiệm như sau. Tối đa mười tắc nghẽn sẽ được đưa vào đồng thời từ vòng lặp thứ 100 đến vòng lặp thứ 150. Có nghĩa là tại vòng lặp thứ 100 của thuật toán, ta sẽ tìm được một tuyến đường tối ưu nhất tính đến lúc đó. Sau đó ta sẽ chọn tối đa 10 đoạn đường bất kì nằm trên tuyến đường đó để đưa các tắc nghẽn vào. Lưu ý rằng các tắc nghẽn được đưa vào theo cách như sau: các đoạn đường được chọn sẽ có độ dài tăng dần sau mỗi bước lặp cho đến vòng lặp thứ 150. Mỗi vòng lặp chúng sẽ làm độ dài các đoạn đường tăng lên 50. Bằng cách này thuật toán sẽ có thể đáp ứng trước những thay đổi nhỏ của môi trường(sự lớn lên của các tắc nghẽn) mà ta có thể kiểm chứng được. Nhưng nếu như tắc nghẽn được đưa vào luôn chỉ một lần mà không có sự lớn lên dần thì thuật toán không thể cho thấy được sự thay đổi tuyến đường đi của nó ngay trong khi các tắc nghẽn vẫn tiếp tục tăng lên. Chúng ta sẽ kiểm tra với 4 trường hợp sau: Trường hợp 1: sử dụng cận dưới và không shaking (p=0). Trường hợp 2, 3, 4: vừa sử dụng cận dưới, vừa tiến hành kĩ thuật shaking: global shaking với p = 1, local shaking với p = 0.1 và p = 0.25. Sau nhiều lần thực nghiệm trên eil51 thì thấy rằng các tham số như sau là khá phù hợp: m = 25, α = 1, β = 5, 0 = 1e-5, ρ = 0.5 Kết quả được biểu diễn bởi biểu đồ thị sau: 33 Biểu đồ 2a: (Trường hợp 2) p=0(không shaking), cận dưới 0 = 1e-5 Biểu đồ 2b: (Trường hợp 3) p=1(global shaking), cận dưới 0 = 1e-5 Biểu đồ 2c: (Trường hợp 4) p=0.1(local shaking), cận dưới 0 = 1e-5 34 Biểu đồ 2d: (Trường hợp 5) p=0.25 (local shaking), cận dưới 0 = 1e-5 4.2. Nhận xét Trên các đồ thị trên, chiều thẳng đứng biểu thị tuyến đường đi tốt nhất tại các vòng lặp tương ứng (chiều ngang). Quan sát các đồ thị ta có nhận xét: Ở biểu đồ 2a, với việc sử dụng cận dưới, mặc dù độ dài vẫn tăng khi gặp tắc nghẽn tại vòng lặp thứ 100 nhưng ngay sau đó độ dài các đường đi giảm xuống nhanh, chứng tỏ các con kiến đã tìm được đường đi mới tránh được tắc nghẽn. Khi đưa thêm kĩ thuật shaking vào (xem các hình 2b, 2c, 2d) thì ta vẫn có cùng nhận xét trên độ dài giảm xuống rõ rệt ngay sau tắc nghẽn. Tuy nhiên ở hình 2b với global shaking (p = 1) kết quả là độ dài đường đi khi mà gặp tắc nghẽn lớn hơn so với local shaking (p = 0.1 và p = 0.25 ở các hình 2c, 2d). Việc lựa chọn giá trị shaking_percentage là rất quan trọng và nó tùy thuộc vào mỗi bài toán cũng như kích thước của bài toán. Nếu kích thước của bài toán là nhỏ thì global shaking cũng không khác nhiều so với local shaking , tức là sự khác biệt khi lựa chọn các giá trị shaking_percentage là ít vì do các đỉnh khá gần nhau và số lượng các đỉnh ít. Khi kích thước bài toán là lớn thì global shaking sẽ làm mất mát rất nhiều thông tin mà các con kiến đã tích lũy được, vì nó làm thay đổi tất cả lượng mùi trên tất cả các tuyến đường. Còn nếu chọn giá trị shaking_percentage nhỏ thì chỉ số ít các 35 đoạn đường là chịu ảnh hưởng của quá trình shaking do đó ta cung không tìm được các kết quả tốt. Một tham số khác cũng khá quan trọng là giá trị cận dưới, nếu chọn cận dưới quá nhỏ thì tác dụng của nó là không đáng kể, lượng mùi trên các cạnh giảm xuống quá thấp sẽ làm giảm khả năng khám phá là điều rất quan trọng trong bài toán DTSP. Ngược lại nếu chọn cận dưới quá lớn, thuật toán sẽ thiên về hướng ngẫu nhiên nhiều hơn và như vậy thì hiệu quả của thuật toán sẽ giảm. Cân bằng được giá trị này thì ta sẽ đạt được kết quả cao khi giải quyết bài toán. Thuật toán này gặp phải một nhược điểm cũng như nhược điểm của thuật toán AS mà ta sẽ thấy ngay sau đây (xem biểu đồ 3a) đó là khi mà số đỉnh của bài toán lớn thì hiệu quả của thuật toán sẽ bị giảm mạnh. Thực nghiệm trên TSPLIB att532 với các tham số m = 100, α = 1, β = 5 , ρ = 0.5, 0 = 1 / mρC nn , p = 0.01 với Cnn là độ dài của đường đi tìm được bằng cách chọn các láng giềng gần nhất. Ta thu được một kết quả là độ dài của đường đi không được cải thiện mấy khi mà con kiến gặp phải tắc nghẽn. Đồ thị 3a. Độ dài trung bình của đường đi tại mỗi vòng lặp với att532 Nguyên nhân mà hiệu quả thuật toán bị giảm sút là vì khi kích thước lớn thí có nhiều cạnh không được cập nhật bởi thuật toán AS và chúng sẽ giảm mùi rất nhanh về giá trị cận dưới, làm cho thuật toán khó lòng lựa chọn các cạnh này, việc lựa chọn các cận dưới cho phù hợp là điều cực kỳ khó khăn. 36 Để khắc phục hiện tượng trên thay vì sử dụng ký thuật shaking và cận dưới cùng với thuật toán AS, thì ta sử dụng kết hợp kỹ thuật shaking với thuật toán MMAS, vì MMAS có nhiều ưu điểm hơn so với AS đồng thời thuật toán MMAS có thể giải quyết được những bài toán kích thược lớn. Bằng cách chọn các tham số mà nhiều lý thuyết đã chỉ ra là tốt đối với MMAS: τmax = 1 / ρCnn τmin = τmax / 2n n là số đỉnh và Cnn là độ dài của đường đi tìm được bằng cách chọn các láng giềng gần nhất. Và sử dụng cùng một giá trị shaking_percentage như với AS là p=0.01, cũng như cùng giá trị các tham số: m = 100, α = 1, β = 5 , ρ = 0.5 so sánh với thuật toán AS đã cải tiến cho DTSP ta có được một kết quả khả quan hơn hẳn (xem đồ thị 3b) Đồ thị 3b. Độ dài trung bình của đường đi tại mỗi vòng lặp trên 2 thuật toán AS cải tiến và MMAS cải tiến cho tsplib att532 Ta nhận thấy sau khi gặp tắc nghẽn thì cải tiến mà luận văn đề xuất tỏ ra là hoạt động khá tốt, nó giảm ngay độ dài đường đi sau đó và cứ mỗi khi tắc nghẽn tăng thêm ở các vòng lặp tiếp theo nó vẫn điều chỉnh lại đường đi giảm xuống nhanh chóng, đặc biệt là ngay sau khi tắc nghẽn không còn. 37 PHẦN 5. KẾT LUẬN Trong loại DTSP của trình bày trong khóa luận này, các tắc nghẽn được điều chỉnh sao cho nó tăng dần trên những tuyến đường xác định theo thời gian. Với cách để cho các tắc nghẽn lớn dần như thế trong các bước chúng ta có thể so sánh được hiệu quả của thuật toán trong các lần thực nghiệm khác nhau một cách dễ dàng. Những kết quả thực nghiêm thu được ở trên cho phép ta rút ra kết luận rằng thuật toán AS với những cải tiến nhất định có khả năng giải quyết tốt bài toán DTSP. Ở đây thuật toán của ta đã được hình thành bằng cách mở rộng từ thuật toán AS cho bài toán TSP thông thường bằng cách đưa thêm vào hành động hay nói đúng hơn là kỹ thuật shaking mà ta đã trình bày rất kỹ ở trên. Khi mà tần số động của bài toán DTSP càng cao thì điều quan trọng là ta vẫn cần phải giữ được các thông tin đã tích lũy được trong ma trận mùi. Đó là lí do vì sao mà khi ta thay đổi toàn bộ lượng mùi trên tất cả các tuyến đường bằng global shaking thì kết quả là lượng thông tin lưu trữ được đã gần như bị mất đi và làm cho hiệu quả thuật toán bị tụt dốc. Điểm mạnh của thuật toán là ta có thể điều chỉnh được tham số shaking_percentage trong local shaking sao cho nó phù hợp với từng bài toán cụ thể với những kích thước và đặc điểm khác nhau của mỗi bài. Điểm yếu của thuật toán là cũng giống với AS, hiệu suất giảm mạnh khi tăng số lượng đỉnh lên. Và với cải tiến bằng cách áp dụng kỹ thuật shaking lên thuật toán MMAS thay vì thuật toán AS ta có được một thuật toán mà có kết quả tốt hơn nhiều so với thuật toán ban đầu trên các bài toán kích thước lớn. 38 THAM KHẢO [15] Huy Q. D, Dong Do Duc, and Huan Hoang Xuan. Multi-level ant system - a new approach through the new pheromone update for ant colony optimization. In: the 2006 Inter-national Conference on Research, Innovation and Vision for the Future, pp. 5558, (2006). [2] A. Colorni, M. Dorigo, and V. Maniezzo, Distributed optimization by ant colonies, Proceedings of ECAL'91, European Conference on Artificial Life, Elsevier Publishing, Amsterdam, 1991. [8] A. Zhou, L. Kang, and Z. Yan, “Solving dynamic TSP with evolutionary approach in real time,” in Proc. of the Congress on Evolutionary Computation, Canberra, Australia, 2003, vol. 2, pp. 951-957. [11] Casper Joost Eyckelhof. Ant systems for dynamic problems, the TSP case - ants caught in a traffic jam. Master’s thesis, University of Twente, The Netherlands, August 2001. Available throug [6] Goss, S., Aron, S., Deneubourg, J. L., & Pasteels, J. M. (1989). Self-organized shortcuts in the Argentine ant. Naturwissenschaften, 76, 579–581. [1] J.L. Denebourg, J.M. Pasteels et J.C. Verhaeghe, Probabilistic Behaviour in Ants : a Strategy of Errors?, Journal of Theoretical Biology, numéro 105, 1983. [10] K. Shinozawa, T. Uchiyama, and K. Shimohara, “An approach for solving dynamic TSPs using neural networks,” in Proc. of the IEEE International Joint Conference on Neural Networks, Singapore, 1991, vol. 3, pp. 2450-2454. 39 [3] M. Dorigo, V. Maniezzo, and A. Colorni, The ant system: an autocatalytic optimizing process, Technical Report TR91-016, Politecnico di Milano (1991). [4] M. Dorigo, Optimization, learning and natural algorithms, Ph.D. Thesis, Politecnico di Milano, Milano, 1992. [13] Michael Guntsch, Martin Middendorf, and Hartmut Schmeck. An ant colony optimization approach to dynamic TSP. In Lee Spector et al., editor, Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2001), pages 860– 867, San Francisco, California, USA, 7-11 July 2001. Morgan Kaufmann. [12] Michael Guntsch, Jurgen Branke, Martin Middendorf, and Hartmut Schmeck. ACO strategies for dynamic TSP. In Marco Dorigo et al., editor, Abstract Proceedings of ANTS’2000, pages 59–62, 2000. [7] Traveling Salesman Problem for Dynamic Graphs Kovrig Antal Attila CIR Report No. 052005 July, 2005 [9] Z.-C. Huang, X.-L. Hu, and S.-D. Chen, “Dynamic traveling salesman problem based on evolutionary computation,” in Proc. of the Congress on Evolutionary Computation, Seoul, Korea, 2001, vol. 2, pp. 1283-1288. [5] M. Dorigo, Ant colony optimization web page, [14]