Luận văn Thạc sĩ Công nghệ thông tin: Phương pháp tối ưu đàn kiến cho bài toán điều phối xe

Chia sẻ: Tomjerry001 | Ngày: | Loại File: PDF | Số trang:45

Thêm vào BST

Báo xấu

36
lượt xem 6
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Mục tiêu nghiên cứu của đề tài là tìm lời giải tốt nhất trong các lời giải có thể và không gian tìm kiếm lời giải của bài toán là rời rạc. Nhiều bài toán tối ưu tổ hợp có độ phức tạp tính toán cao và được phân loại thuộc lớp NP khó. Việc tìm ra lời giải tối ưu cho các bài toán này cho các hệ thống song song lớn nhất cũng không thể hoàn thành được trong giới hạn thời gian cho phép vì vậy các kỹ thuật heuristic cho việc giải các bài toán tổ hợp theo hướng xấp xỉ đã được phát triển để tìm ra các lời giải gần tối ưu (hay xấp xỉ ) trong giới hạn thời gian cho phép. Bài toán người du lịch (TSP) là một bài toán cổ điển thuộc lớp NP được nghiên cứu sâu trong lĩnh vực tối ưu tổ hợp.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn Thạc sĩ Công nghệ thông tin: Phương pháp tối ưu đàn kiến cho bài toán điều phối xe

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC CÔNG NGHỆ LÊ MỸ HẠNH PHƢƠNG PHÁP TỐI ƢU ĐÀN KIẾN CHO BÀI TOÁN ĐIỀU PHỐI XE LUẬN VĂN THẠC SĨ NGÀNH CÔNG NGHỆ THÔNG TIN Hà Nội-2014
2 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC CÔNG NGHỆ LÊ MỸ HẠNH PHƢƠNG PHÁP TỐI ƢU ĐÀN KIẾN CHO BÀI TOÁN ĐIỀU PHỐI XE Ngành: Công nghệ thông tin Chuyên ngành: Kỹ thuật phần mềm Mã số: 60480103 LUẬN VĂN THẠC SĨ NGÀNH CÔNG NGHỆ THÔNG TIN NGƯỜI HƯỚNG DẪN KHOA HỌC PGS.TS.HOÀNG XUÂN HUẤN TS.ĐỖ ĐỨC ĐÔNG Hà Nội-2014
3 Lời cam đoan Với mục đích học tập, nghiên cứu để nâng cao kiến thức và trình độ chuyên môn nên tôi đã làm luận văn này. Tôi xin cam đoan kết quả đạt được trong luận văn là sản phẩm của cá nhân tôi, thực hiện dưới sự hướng dẫn của PGS. TS Hoàng Xuân Huấn và TS Đỗ Đức Đông. Trong toàn bộ nội dung của luận văn, những điều được trình bày hoặc là của cá nhân hoặc là được tổng hợp từ nhiều nguồn tài liệu. Tất cả các tài liệu tham khảo đều có xuất xứ rõ ràng và được trích dẫn đúng quy định. Tôi xin hoàn toàn chịu trách nhiệm và chịu mọi hình thức kỷ luật theo quy định cho lời cam đoan của mình. Hà nội, ngày ….. tháng ….. năm 2014 Học viên Lê Mỹ Hạnh
4 LỜI CẢM ƠN Với những dòng chữ đầu tiên này, tôi xin dành để gửi lời cảm ơn chân thành và sâu sắc nhất tới thầy giáo, PGS. TS. Hoàng Xuân Huấn, Thầy giáo TS. Đỗ Đức Đông- hai người thầy đã tận tình hướng dẫn, chỉ bảo và tạo cho tôi những điều kiện tốt nhất từ khi bắt đầu cho tới khi hoàn thành công việc của mình. Đồng thời, tôi xin gửi lời cảm ơn tới các thầy cô giáo khoa Công nghệ thông tin - trường Đại học Công nghệ - Đại học Quốc gia Hà Nội đã tạo cho tôi một môi trường học tập thuận lợi, cung cấp nhiều kiến thức bổ ích để tôi có thể thực hiện công việc của mình. Tôi xin cảm ơn các nhà khoa học, các tác giả của các bài báo, báo cáo kỹ thuật và báo cáo hội thảo đã ghi ở phần tài liệu tham khảo, nhờ những tài liệu hữu ích này mà tôi có thêm sự phong phú và đa dạng trong khóa luận của mình. Cuối cùng, xin cảm ơn tất cả những người thân yêu trong gia đình tôi và bạn bè, những người đã luôn động viên và giúp đỡ tôi mỗi khi tôi gặp khó khăn trong quá trình làm luận văn.
5 MỤC LỤC MỤC LỤC ............................................................................................................ 5 DANH SÁCH CÁC HÌNH.................................................................................. 6 BẢNG TỪ VIẾT TẮT ........................................................................................ 7 MỞ ĐẦU .............................................................................................................. 8 TỐI ƢU HÓA ĐÀN KIẾN VÀ ỨNG DỤNG ................................................. 10 1.1 Lịch sử phát triển: ......................................................................................... 12 1.2 Phương pháp tối ưu hóa đàn kiến.................................................................. 13 1.2.1 Bài toán tối ưu hóa tổ hợp ...................................................................... 13 1.2.2 Bài toán tổng quát ................................................................................... 14 1.2.3 Thuật toán tổng quát ............................................................................... 15 1.2.4 Các ứng dụng của ACO .......................................................................... 19 1.3 Các nguyên tắc khi áp dụng tối ưu đàn kiến ................................................. 20 1.3.1 Nồng độ vệt mùi ..................................................................................... 20 1.3.2 Thông tin heuristic .................................................................................. 20 1.3.3 ACO và Local search .............................................................................. 21 1.3.4 Số lượng kiến .......................................................................................... 22 1.3.5 Điều chỉnh sự học tăng cường và sự khám phá ...................................... 22 1.3.6 Sử dụng giới hạn danh sách láng giềng .................................................. 24 1.4 Đánh giá về phương pháp ACO .................................................................... 24 CHƢƠNG 2........................................................................................................ 26 BÀI TOÁN ĐIỀU PHỐI XE ............................................................................ 26 VÀ CÁC CÁCH GIẢI HIỆN NAY.................................................................. 26 2.1 Giới thiệu về bài toán điều phối xe ............................................................... 26 2.1.1 Lịch sử phát triển .................................................................................... 26 2.1.2 Các biến thể của bài toán điều phối xe ................................................... 26 2.2 Tóm tắt nội dung bài toán ............................................................................. 28 2.3 Mô hình hóa bài toán: ................................................................................... 28 2.4 Các cách tiếp cận bài toán : ........................................................................... 29 2.4.1 Thuật toán nhánh cận .............................................................................. 30 2.4.2 Giải thuật di truyền ................................................................................. 31 CHƢƠNG 3........................................................................................................ 33 PHƢƠNG PHÁP TỐI ƢU ĐÀN KIẾN CHO ................................................ 33 BÀI TOÁN ĐIỀU PHỐI XE ............................................................................ 33 3.1 Bài toán điều phối xe (Vehicle Routing Problem -VRP ) ............................. 33 3.2 Sinh giải pháp ................................................................................................ 33 3.3 Cập nhật mùi ................................................................................................. 34 3.3.1 Cập nhật mùi theo chiến lược kiến trọng lượng ..................................... 35 3.3.2 Cập nhật mùi theo quy tắc Smooth-Max Min Ant System(SMMAS) ... 37 3.4 Tiến hành thực nghiệm ................................................................................. 38 3.4.1 Bộ dữ liệu chuẩn: .................................................................................... 38 3.4.2 Kết quả thực nghiệm và đánh giá ........................................................... 39 KẾT LUẬN ........................................................................................................ 43
6 DANH SÁCH CÁC HÌNH Hình 1.1: Lược đồ thuật toán ACO ..................................................................... 16 Hình 2.1: Ví dụ về hành trình các xe .................................................................. 29 Hình 2.2: Bảng hành trình các xe ........................................................................ 29 Hình 2.3: Thuật toán nhánh cận .......................................................................... 31 Hình 2.4: Thuật toán di truyền ............................................................................ 32 Hình 3.1: Ví dụ về hành trình các xe .................................................................. 36 Hình 3.2: Cách tính các thông số thành phần ..................................................... 36 Hình 3.3: Bảng cách tính các thông số cập nhật mùi .......................................... 37 Hình 3.4: Các tham số sử dụng cho thuật toán ................................................... 40 Hình 3.5: Bảng kết quả thực nghiệm .................................................................. 41 Hình 3.6: So sánh các kết quả khi sử dụng các thuật toán ACO ....................... 42
7 BẢNG TỪ VIẾT TẮT STT Từ viết tắt Từ hoặc cụm từ Ant Colony Optimization 1 ACO (Tối ưu đàn kiến) Improved Ant Colony Optimization 2 IACO (Cải tiến tối ưu đàn kiến) Ant System 3 AS (Hệ kiến AS) Ant Colony System 4 ACS (Hệ kiến ACS ) Max-Min Ant System 5 MMAS (Hệ kiến MMAS) Smooth-Max Min Ant System 6 SMMAS (Hệ kiến MMAS trơn) Multi-level Ant System 7 MLAS (Hệ kiến đa mức MLAS ) 8 Opt Optimization 9 Avg Average Travelling Salesman Problem 10 TSP (Bài toán người chào hàng) Vehicle Routing Problem 11 VRP (Bài toán điều phối xe) 12 g-best global-best 13 i-best Iteration-best
8 MỞ ĐẦU Bài toán điều phối xe (Vehicle Routing Problem_VRP) đã được nghiên cứu trong suốt 40 năm qua. Mục đích điển hình của bài toán điều phối xe là thiết lập hành trình cho một số phương tiện từ kho tới các thành phố và quay trở lại kho ban đầu mà không vượt quá năng lực hạn chế của mỗi xe với một chi phí tối thiểu. Sự kết hợp các khách hàng không bị giới hạn đến việc lựa chọn các hành trình. Bài toán điều phối xe được coi là một vấn đề tối ưu hóa tổ hợp mà số lượng các giải pháp khả thi cho bài toán tăng theo cấp số nhân với số lượng khách hàng ngày càng tăng. Mục đích của bài toán tối ưu tổ hợp là tìm lời giải tốt nhất trong các lời giải có thể và không gian tìm kiếm lời giải của bài toán là rời rạc. Nhiều bài toán tối ưu tổ hợp có độ phức tạp tính toán cao và được phân loại thuộc lớp NP khó. Việc tìm ra lời giải tối ưu cho các bài toán này cho các hệ thống song song lớn nhất cũng không thể hoàn thành được trong giới hạn thời gian cho phép vì vậy các kỹ thuật heuristic cho việc giải các bài toán tổ hợp theo hướng xấp xỉ đã được phát triển để tìm ra các lời giải gần tối ưu (hay xấp xỉ ) trong giới hạn thời gian cho phép. Bài toán người du lịch (TSP) là một bài toán cổ điển thuộc lớp NP được nghiên cứu sâu trong lĩnh vực tối ưu tổ hợp. Các giải thuật Heuristic như thuật toán luyện kim (SA) để giải quyết bài toán điều phối xe. Metaheuristic là một cách gọi chung cho các giải thuật heuristic trong việc giải quyết các bài toán tổ hợp khó. Metaheuristic bao gồm những chiến lược khác nhau trong việc khám phá không gian tìm kiếm bằng cách sử dụng những phương thức khác nhau và phải đạt được sự cân bằng giữa tính đa dạng và chuyên sâu của không gian tìm kiếm. Một cài đặt thành công của metaheuristic trong một bài toán tổ hợp phải cân bằng giữa sự khai thác được kinh nghiệm thu thập được trong quá trình tìm kiếm để xác định được những vùng với những lời giải có chất lượng cao gần tối ưu. Những ví dụ của metaheuristic bao gồm giải thuật luyện thép (SA), giải thuật di truyền (GA), giải thuật đàn kiến (ACO),…
9 Giải thuật đàn kiến là metaheuristic dùng chiến lược của kiến trong thế giới thực để giải bài toán tối ưu. Trong số các giải thuật heuristic, giải thuật tối ưu hóa đàn kiến ACO được công bố bởi nhà khoa học người Italia Dorigo năm 1996. Nó giống như việc mô phỏng lại hành vi tìm kiếm thức ăn của đàn kiến trong tự nhiên. Nó đã được áp dụng thành công như một giải pháp cho một số vấn đề tối ưu hóa kép cổ điển, ví dụ bài toán người du lịch, các bài toán lập lịch sản xuất, hay bài toán truyền thông … Nếu coi kho trung tâm là tổ và các thành phố là nơi chứa thức ăn thì các xe giống như các con kiến. Thuật toán ACO rất giống với hành vi tìm kiếm thức ăn của đàn kiến trong tự nhiên. Điều này làm việc mã hóa thuật toán tối ưu đàn kiến cho bài toán điều phối xe là rất đơn giản. Đã có rất nhiều nghiên cứu áp dụng thuật toán ACO cho bài toán VRP bao gồm các nghiên cứu của Bullnheimer và các cộng sự [11] , Bell và McMullen[12] Với những ý nghĩa thiết thực đó trong luận văn này chúng tôi đã tiến hành nghiên cứu, trình bày lại những lý thuyết chung nhất của phương pháp ACO, cách áp dụng phương pháp ACO cho bài toán VRP. Ngoài ra trong luận văn chúng tôi còn tiến hành cài đặt thử nghiệm các phương pháp cập nhật mùi mới. Cấu trúc luận văn như sau: Ngoài phần mở đầu, kết luận và các phụ lục, phần còn lại của luận văn được chia thành 3 chương chính: Chƣơng 1: Phương pháp Tối ưu hóa đàn kiến và ứng dụng Giới thiệu phương pháp tối ưu hóa đàn kiến: lịch sử phát triển, các thuật toán ACO, và một số nguyên tắc ứng dụng ACO. Chƣơng 2: Giới thiệu về bài toán điều phối xe, các vấn đề liên quan và các phương pháp chính giải quyết bài toán. Chƣơng 3: Tối ưu đàn kiến và bài toán điều phối xe: Trình bày cách thức chung để áp dụng tối ưu đàn kiến để giải các bài toán điều phối xe. Trình bày các kết quả thực nghiệm.
10 CHƢƠNG 1 TỐI ƢU HÓA ĐÀN KIẾN VÀ ỨNG DỤNG Mục đích của bài toán tối ưu tổ hợp là tìm lời giải tốt nhất trong các lời giải có thể và không gian tìm kiếm lời giải của bài toán là rời rạc. Nhiều bài toán tối ưu tổ hợp có độ phức tạp tính toán cao và được phân loại thuộc lớp NP khó. Việc tìm ra lời giải tối ưu cho các bài toán này không thể hoàn thành được trong giới hạn thời gian cho phép vì vậy các kỹ thuật heuristic cho việc giải các bài toán tổ hợp theo hướng xấp xỉ đã được phát triển để tìm ra các lời giải gần tối ưu (hay xấp xỉ) trong giới hạn thời gian cho phép. Metaheuristic là một cách gọi chung cho các giải thuật heuristic trong việc giải quyết các bài toán tổ hợp khó. Metaheuristic bao gồm những chiến lược khác nhau trong việc khám phá không gian tìm kiếm bằng cách sử dụng những phương thức khác nhau và phải đạt được sự cân bằng giữa tính đa dạng và chuyên sâu của không gian tìm kiếm. Một cài đặt thành công của metaheuristic trong một bài toán tổ hợp phải cân bằng giữa sự khai thác được kinh nghiệm thu thập được trong quá trình tìm kiếm để xác định được những vùng với những lời giải có chất lượng cao gần tối ưu. Những ví dụ của metaheuristic bao gồm giải thuật luyện thép (SA), giải thuật di truyền (GA), giải thuật đàn kiến (ACO),…Giải thuật đàn kiến là metaheuristic dùng chiến lược của kiến trong thế giới thực để giải bài toán tối ưu. SA xuất phát từ phương thức xác suất và kỹ thuật luyện kim bao gồm việc nung và điều khiển làm nguội các kim loại để đạt được trạng thái năng lượng nhỏ nhất. Trong khi đó giải thuật di truyền dựa trên ý tưởng từ cơ chế di truyền trong sinh học và tiến trình tiến hóa trong cộng đồng các cá thể của 1 loài. Tối ưu hóa đàn kiến (Ant Colony Optimizaton) là cách tiếp cận metaheuristic tương đối mới (xem [2],[3],[5],[6]) được đề xuất bởi Dorigo vào năm 1991 mô phỏng hành vi tìm đường đi từ tổ tới nguồn thức ăn và ngược lại của con kiến thực trong tự nhiên để giải gần đúng các bài toán tối ưu tổ hợp NP- khó.
11 Trên đường đi của mình các con kiến thực để lại một vệt hóa chất được gọi là vệt mùi (pheromon trail), đặc điểm sinh hóa học của vệt mùi này là có khả năng ứ đọng, bay hơi và là phương tiện giao tiếp báo cho các con kiến khác thông tin về đường đi đó một cách gián tiếp. Các con kiến sẽ lựa chọn đường đi nào tồn đọng lượng mùi hay có cường độ vệt mùi lớn nhất tại thời điểm lựa chọn để đi, nhờ cách giao tiếp gián tiếp và cộng đồng (xem [2]) này mà đà kiến trong tự nhiên tìm được đường đi ngắn nhất trong quá trình tìm thức ăn mang về tổ và ngược lại. Theo ý tưởng này, các thuật toán ACO sử dụng thông tin heuristic kết hợp với thông tin học tăng cường (xem [3]) qua các vệt mùi của các con kiến nhân tạo (artificial ant) để giải các bài toán tối ưu tổ hợp khó bằng cách đưa về bài toán tìm đường đi tối ưu trên đồ thị cấu trúc tương ứng được xây dựng từ đặc điểm của từng bài cụ thể. Thuật toán ACO đầu tiên (xem [4]) là hệ kiến (Ant System-AS) giải bài toán Người chào hàng (Travelling Salesman Problem-TSP), đến nay các thuật toán ACO đã được áp dụng một cách phong phú (xem [5] để giải nhiều bài toán tối ưu tổ hợp khác nhau và hiệu quả nổi trội của nó đã được chứng tỏ bằng thực nghiệm). Nhờ những thành quả to lớn trong việc ứng dụng phương pháp tối ưu đàn kiến vào giải các bài toán tối ưu tổ hợp khó mở ra một lĩnh vực nghiên cứu và ứng dụng mới thu hút sự quan tâm đông đảo các nhà khoa học trên thế giới, Dorigo đã được Hội đồng châu Âu trao giải thưởng đặc biệt Marie Curie(Marie Curie Excellence Award) trao hai năm một lần giành cho 5 nhà khoa học có nhiều đóng góp cho nền khoa học và công nghệ châu Âu vào ngày 05/11/2003. Cho đến nay, các hội nghị về đàn kiến đã đã tổ chức 6 lần (ANT’ 98, ANT’ 2000, ANT 2002, ANTS 2006, ANTS 2008) và ở mỗi hội nghị có khoảng 30-40 báo cáo về các công trình nghiên cứu lý thuyết và thực nghiệm có ý nghĩa khoa học và ứng dụng quan trọng góp phần chứng tỏ ACO là phương pháp tối ưu và mới mẻ (xem http://iridia.ulb.ac.be/~ants).
12 1.1 Lịch sử phát triển: Hệ thống ACO lần đầu tiên được Marco Dorigo giới thiệu trong luận văn của mình vào năm 1992, và được gọi là Hệ thống kiến (Ant System, hay AS). AS là kết quả của việc nghiên cứu trên hướng tiếp cận trí tuệ máy tính nhằm tối ưu tổ hợp mà Dorigo được hướng dẫn ở Politecnico di milano với sự hợp tác của Alberto Colorni và Vittorio Maniezzo. AS ban đầu được áp dụng cho bài toán người du lịch (TSP) và bài toán Phân bậc hai (QAP). Cũng vào năm 1992, tại hội nghị sự sống nhân tạo lần đầu tiên ở châu Âu, Dorigo và các cộng sự đã công bố bài: sự tối ưu được phân bố bởi đàn kiến. Tiếp theo tại hội nghị quốc tế thứ hai về giải quyết các vấn đề song song trong tự nhiên ở Hà Lan (1992), ông và các cộng sự đã công bố bài: nghiên cứu về các đặc tính của một giải thuật kiến. Kể từ năm 1995 Dorigo, Gambardella và Stützle đã phát triển các sơ đồ AS khác nhau. Dorigo và Gambardella đã đề xuất Hệ thống bầy kiến (Ant Colony System, hay ACS) trong khi Stützle và Hoos đề xuất MAX-MIN Ant System (MMAS). Dorigo, Gambardella và Stützle cũng đề xuất những phiên bản lai của ACO với tìm kiếm địa phương. Vào năm 1995, L.M. Gambardella và M. Dorigo đã đề xuất hệ thống Ant- Q, là một cách tiếp cận học tăng cường cho cho bài toán TSP. Và nó được áp dụng trong Học Máy. Tiếp đó, vào năm 1996, trong bài báo công nghệ của mình tại Bruxelles M. Dorigo và L.M. Gambardella đã công bố hệ thống Ant Conoly System (ACS). Đây là hệ thống đề cập đến cách học phối hợp áp dụng cho bài toán TSP. Cũng trong năm 1996 này, T. Stützle và H. H. Hoos đã đề xuất hệ thống Max-Min Ant System. Đây là một hệ thống cải tiến hệ thống AntSystem ban đầu và được đánh giá là hệ thống tính toán trong tương lai.
13 Sau đó, vào năm 1997, G. Di Caro và M. Dorigo đã đề xuất hệ thống AntNet. Đây là cách tiếp cận về định hướng sự thích nghi. Và phiên bản cuối cùng của hệ thống AntNet về điều khiển mạng truyền thông đã được công bố vào năm 1998. Cũng trong năm 1997, hệ thống Rank-based Ant System, một hệ thống cải tiến hệ thống kiến ban đầu về nghiên cứu hệ thống tính toán đã được đề xuất bởi B. Bullnheimer, R. F. Hartl và C. Strauss. Phiên bản cuối cùng của hệ thống này được công bố vào năm 1999. Vào năm 2001, C. Blum, A. Roli, và M. Dorigo đã cho công bố về hệ thống kiến mới là Hyper Cube – ACO. Phiên bản mở rộng tiếp đó đã được công bố vào năm 2004. Hầu hết các nghiên cứu gần đây về ACO tập trung vào việc phát triển các thuật toán biến thể để làm tăng hiệu năng tính toán của thuật toán Ant System ban đầu. 1.2 Phương pháp tối ưu hóa đàn kiến 1.2.1 Bài toán tối ưu hóa tổ hợp Bài toán tối ưu hóa tổ hợp liên quan tới việc tìm giá trị cho các biến số rời rạc như lời giải tối ưu mà có lưu ý tới hàm mục tiêu (objective function) cho trước. Bài toán có thể là bài toán tìm cực đại hoặc tìm cực tiểu. Một cách thông thường, bài toán tối ưu hoá tổ hợp được cho dưới dạng bộ 3 (S, f, Ω). Trong đó S là tập các lời giải ứng cử viên, f là hàm mục tiêu (hàm này gán giá trị f(s) cho mỗi lời giải ứng cử viên s  S), và Ω là tập các ràng buộc của bài toán. Các lời giải thuộc tập S*  S thỏa mãn tập các ràng buộc Ω gọi là lời giải khả thi. Mục tiêu bài toán là tìm ra một lời giải khả thi tối ưu toàn cục s *. Với các bài toán tối ưu hóa cực tiểu là tìm lời giải s* với giá nhỏ nhất, nghĩa là f(s*) ≤ f(s) với mọi lời giải s  S. Ngược lại bài toán tối ưu hóa cực đại là tìm lời giải s * với giá lớn nhất, nghĩa là f(s*) ≥ f(s) với mọi lời giải s  S. Bài toán tối ưu hóa tổ hợp có thể chia 2 loại: Bài toán tĩnh và bài toán động.
14 Bài toán tối ƣu hóa tổ hợp tĩnh (Static Combinatorial optimization): Là bài toán tối ưu hóa tổ hợp trong đó cấu trúc (topology) và giá (cost) không thay đổi khi bài toán đang được giải quyết. Ví dụ là bài toán người du lịch. Khi thực hiện thuật toán để giải bài toán vị trí các thành phố, khoảng cách giữa các thành phố là không thay đổi. Bài toán tối ƣu hóa tổ hợp động (Dynamic Combinatorial optimization): Là bài toán tối ưu hóa tổ hợp trong đó cấu trúc (topology) và giá (cost) có thể thay đổi khi bài toán đang được giải quyết. Ví dụ là bài toán định hướng trong mạng viễn thông, trong đó mô hình mạng và dung lượng yêu cầu luôn thay đổi. 1.2.2 Bài toán tổng quát Xét bài toán cực tiểu hóa (S,f,  ) trong đó S là tập hữu hạn các trạng thái (lời giải tiềm năng hay phương án ), f là hàm mục tiêu xác định trên S còn  là các ràng buộc. Mỗi phương án s  S thỏa mãn các ràng buộc  gọi là phương án (hay lời giải chấp nhận được). Mục đích của ta là tìm phương án chấp nhận được s* tối ưu hóa toàn cục hàm mục tiêu f. Đối với mỗi bài toán, tồn tại một tập hữu hạn gồm n thành phần C={c1,…,cn} sao cho mỗi phương án s trong S đều biểu diễn được nhờ các liên kết của các thành phần trong nó. Cụ thể hơn, các tập S,C và  có các đặc tính sau: 1) Ký hiệu X là tập các vectơ trên C độ dài không quá h: X={ ui  C i  k  h }, khi đó mỗi phương án s trong S được xác định nhờ ít nhất một vectơ trong X như ở điểm 2 . 2) Tồn tại tập con X* của X và ánh xạ  từ X* lên S sao cho  1 (s) không rỗng với mọi s  S . Trong đó tập X* có thể xây dựng từ tập con C0 nào đó của C nhờ mở rộng tuần tự dưới đây. 3) Từ C0 mở rộng được thành X* theo thủ tục tuần tự:
15 i) x0= là mở rộng được với mọi u0  C0 . ii) Giả sử xk= là mở rộng được và chưa thuộc X*. Từ tập ràng buộc  , xác định tập con J(xk) của C, sao cho với mọi uk+1  J ( xk ) thì xk+1= là mở rộng được. iii) Với mọi u0  C0 , thủ tục mở rộng nêu trên xây dựng được mọi phần tử của X*. Như vậy mỗi bài toán tối ưu tổ hợp được xem là một bài toán cực trị hàm h biến, trong đó mỗi biến nhận giá trị trong tập hữu hạn của C kể cả giá trị rỗng. Một cách nhìn khác, nó là bài toán tìm kiếm vectơ độ dài không quá h trên đồ thị đầy đủ có các đỉnh có nhãn trong tập C. Hai bài toán người du lịch (TSP) và quy hoạch toàn phương nhị phân không ràng buộc (UPQB) được giới thiệu làm ví dụ cho các bài toán tối ưu tổ hợp. 1.2.3 Thuật toán tổng quát Với bài toán tổng quát trên về lý thuyết ta có thể áp dụng thủ tục mở rộng để xây dựng X* và chọn lời giải tốt nhất bằng phương pháp vét cạn nhưng trên thực tế, do sự bùng nổ tổ hợp thì với số phần tử n của C lớn thì không thực hiện được và bài toán được xét thuộc dạng NP khó. Thông thường ta sẽ có các phương pháp heuristic để tìm lời giải đủ tốt cho bài toán. Các thuật toán ACO kết hợp thông tin heuristic này với phương pháp học tăng cường nhờ mô phỏng hành vi của đàn kiến để tìm lời giải tốt nhất hơn. Giả sử với mỗi cạnh nối các đỉnh i,j  C có trọng số heuristic hij để xác định hướng chọn thành phần mở rộng là j khi thành phần cuối cùng của xk là i theo thủ tục nêu trên (hi,j>0 (i, j ) ). Đàn kiến m con sẽ xây dựng lời giải trên đồ thị có trọng số G=(V,E,H,  ) trong đó V là tập đỉnh tương ứng với tập thành phần C ở trên, E là tập các cạnh, H là vector các trọng số Heuristic của cạnh
16 tương ứng (Trong bài toán TSP nó có thể là vectơ mà thành phần là nghịch đảo độ dài của các cạnh tương ứng ) còn  là vector biểu thị các thông tin học tăng cường  i , j (về sau gọi là vệt mùi có khởi tạo bằng  0 >0) định hướng mở rộng xk với thành phần cuối là i nhờ thêm thành phần j thì các thông tin này ở các cạnh. Khi đó ta gọi đồ thị G=(V,E,H,  ) là đồ thị cấu trúc của bài toán tối ưu tổ hợp đang xét, khi đó V là tập các đỉnh, H và  là các thông tin đã nói ở trên còn E là tập các cạnh của đồ thị sao cho từ các cạnh này có thể xây dựng được tập X* nhờ mở rộng tập C0 theo thủ tục tuần tự. Nếu không có thông tin heuristic thì ta xem H có các thành phần như nhau và bằng 1. Với điều kiện dừng đã chọn (giả sử như là với số lần lặp Nc xác định trước) các thuật toán được mô tả hình thức như sau: Procedure Thuật toán ACO cho bài toán tối ưu tổ hợp tĩnh Begin Đặt các tham số và vệt mùi khởi tạo While (chưa gặp điều kiện dừng ) do Begin Xây dựng các lời giải Áp dụng tìm kiếm địa phương(có thể có hoặc không) Cập nhật các vệt mùi End; End; Hình 1.1: Lược đồ thuật toán ACO 1.2.3.1 Xây dựng lời giải Với điều kiện kết thúc đã chọn (có thể là số bước lặp hoặc và thời gian chạy cho trước), người ta dùng đàn kiến m con thực hiện lặp xây dựng lời giải trên đồ thị cấu trúc G=(V,E,H,  ) như sau. Trong mỗi lần lặp, mỗi con kiến chọn ngẫu nhiên một đỉnh u0  C0 làm thành phần khởi tạo x0={u0} và thực hiện
17 xây dựng lời giải theo thủ tục bước ngẫu nhiên để xây dựng lời giải. Dựa trên lời giải tìm được đàn kiến sẽ thực hiện cập nhật mùi theo cách học tăng cường. Thủ tục bƣớc ngẫu nhiên Giả sử xk= là mở rộng được, từ các ràng buộc  xác định được tập con J(xk) của C sao cho với mọi uk+1  J(xk) thì xk+1= là mở rộng được hoặc xk  X* khi J(xk) là rỗng. Đỉnh J=uk+1 để mở rộng được chọn với xác suất P(J) như sau:  [ ij ] [h ij ]  j  J ( xk ) P( j )   l j ( xk ) [ ij ] [h ij ]   0 j  J ( xk ) Quá trình mở rộng tiếp tục cho tới khi kiến r tìm được lời giải chấp nhận được x(r) trong X* và do đó s(r )   ( x(r ))  S Để tiện trình bày, về sau ta sẽ xem x(r) và s(r) như nhau và không phân biệt X* với S. 1.2.3.2 Quy tắc cập nhật mùi Sau khi các con kiến xây dựng xong lời giải, các vệt mùi được cập nhật. Với thuật toán AS, các vệt mùi trên các cạnh sẽ được bay hơi một đại lương theo tham số   (0,1) (được gọi là tham số bay hơi mùi) và mỗi con kiến sẽ đặt mùi tại các cạnh mà chúng đi qua theo công thức:  i , j  (1   ) i , j  (i, j ), (i, j ) Ở đây luận văn đề cập các quy tắc cập nhật mùi điển hình và được sử dụng phổ biến hiện nay : Giả sử g là một hàm giá trị thực xác định trên S sao cho 0g(s’) nếu f(s)
18 Cập nhật mùi địa phương: nếu con kiến k thăm cạnh (i,j), tức là (i,j)  s(k) thì cạnh này sẽ thay đổi mùi theo công thức:  ij  (1   ) ij   l Cập nhật mùi toàn cục: Cập nhật mùi toàn cục chỉ áp dụng cho các cạnh thuộc w(t) là trạng thái tốt nhất các con kiến tìm được tại lần lặp t như sau:  ij  (1   ) ij   g (w(t )) Quy tắc MMAS: Quy tắc này được thực hiện theo cách cập nhật mùi của thuật toán MMAS, sau khi mỗi con kiến đã xây dựng xong lời giải ở mỗi bước lặp, vết mùi được thay đổi theo công thức sau:  ij  (1   ) ij  ij   g (w(t)) (i, j )  w(t) Trong đó  ij = max{  (1   ) , 0} (i, j )  w(t )  1 ij Ở đây 1  0 là tham số. Khắc phục nhược điểm này của quy tắc ACS và MMAS trong [7] đề xuất quy tắc cập nhật mùi ba mức dưới đây. Quy tắc ba mức(xem[7]): Quy tắc cập nhật mùi mới được đề xuất là lai giữa hai quy tắc nói trên, theo quy tắc này vệt mùi tại cạnh (i,j) được cập nhật toàn cục theo công thức:  ij  (1   ) ij   g (w(t )) (i, j)  w(t ) Trong đó:   g (w(t )) (i, j )  w(t )   ij    2 l : (i, j )  s(l )   (i, j )  w(t ), l : (i, j )  s(l )  1 Với quy tắc ba mức (xem[7]); các cận  1 , 2 là cố định. Trong [10] có đề xuất quy tắc cập nhật mùi đa mức mới như sau: Quy tắc đa mức(xem[10]):
19 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:  ij   ij  (1   )1 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:  ij   ij  (1   ) 2 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  2 sẽ được điều chỉnh tăng lên. 1.2.4 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 ở 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 ở các 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 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à các tập con các thành phần của 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à
20 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. 1.3 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 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 kế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 kết hợp tìm kiếm địa phương 1.3.1 Nồng độ 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 lựa chọn thành phố i sau khi đến thăm thành phố j. Cụ thể ở bài toán này ta chọn định nghĩa các vệt mùi 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 có ảnh hưởng rất nhiều đến thuật toán, nếu đưa ra một lựa chọn không tốt thuật toán có thể rất 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. 1.3.2 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 mà nó chính là thông tin 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