Tài liệu Bài tiểu luận tối ưu hóa kết cấu

TỐI ƯU HÓA KẾT CẤU GVHD: TS VŨ TRƯỜNG VŨ MỤC LỤC I.1: GIỚI THIỆU CHUNG I.2: Ý NGHĨA I.2.1: Ý nghĩa khoa học I.2.2: Ý nghĩa thực tiễn I.3: ỨNG DỤNG I.4: THUẬT TOÁN BẦY KIẾN I.4.1: Giới thiệu chung về thuật toán bầy kiến I.4.2: Sơ đồ chung của thuật toán bầy kiến I.4.3: Nội dung của thuật toán bầy kiến I.4.3.1: Mã giả cho thuật toán I.4.3.2: Các sơ đồ thuật toán I.4.3.2.1: Thuật toán Ant System (AS) I.4.3.2.2: Thuật toán Ant Colony System(ACS) I.4.3.2.3: Thuật toán Max–Min Ant System(MMAS) I.4.3.2.4: Thuật toán Rank-Based Ant System(RBAS) I.4.3.2.5: Thuật toán Best-Worst Ant System(BWAS) I.5: ÁP DỤNG Nhóm: 3 2 3 3 3 3 4 4 8 10 11 12 13 14 16 17 18 20 Trang 1 TỐI ƯU HÓA KẾT CẤU GVHD: TS VŨ TRƯỜNG VŨ I.1: GIỚI THIỆU CHUNG Trước khi nói về nội dung thuật toán bầy kiến ta đi tìm hiểu về đàn kiến trong tự nhiên, xem các đặc điểm và cách hoạt động của đàn kiến tự nhiên. Từ đó có thể đưa ra các đặc điểm cần thiết, tác động tới thuật toán bầy kiến. Hình: Đàn kiến trong tự nhiên Đàn kiến tự nhiên: Là một loài có tổ chức cao, mỗi con kiến khi di chuyển sẽ để lại một lượng thông tin pheromone trên mặt đất. Đây là phương tiện để đánh dấu và để đàn kiến trao đổi thông tin khi tìm kiếm thức ăn. Khi đi tìm kiếm thức ăn: Sau khi tìm thấy nguồn thức ăn, thì mỗi con kiến sẽ tìm ra đường đi của nó để đi từ tổ tới nguồn thức ăn. Chúng sẽ giao tiếp trao đổi thông tin với nhau, sau một thời gian cả đàn kiến gần như tìm ra và đi theo con đường ngắn nhất từ tổ tới nguồn thức ăn. Sau khi nghiên cứu cho thấy cơ chế hoạt động của đàn kiến tự nhiên trong quá trình tìm đuờng đi ngắn nhất từ tổ tới nguồn thức ăn dựa trên các nguyên tắc sau:  Đường đi ngắn nhất được xác định thông qua các thông tin về Pheromone, là một loại hóa chất mà các con kiến dùng để trao đổi thông tin với nhau.  Khi di chuyển thì mỗi con kiến sẽ để lại một lượng Pheromone trên đường đi mà nó đã đi qua.  Trong quá trình di chuyển tìm đường đi, các con kiến sẽ được định hướng bởi các thông tin pheromone đã được để lại trên đường đi.  Mỗi con kiến di chuyển một cách ngẫu nhiên khi không có thông tin về pheromone trên đoạn đường đi.  Các đường đi có lượng pheromone lớn thì xác suất được chọn càng cao, ngược lại các đoạn đường có lượng pheromone thấp thì xác suất được chọn là bé. Từ việc nghiên cứu cơ chế hoạt động của đàn kiến tự nhiên đã cho ra đời thuật toán bầy kiến. Một cách không chính thức có thể nói thuật toán bầy kiến là một bầy kiến nhân tạo để giải bài toán đưa ra. Tối ưu đàn kiến (ACO) Là một đàn kiến nhân tạo (Artificial Ants) mô phỏng các hoạt động của đàn kiến tự nhiên. Trong đó hoạt động chính của các con kiến nhân tạo là cách tìm đường đi từ tổ tới nguồn thức ăn của các con kiến tự nhiên. Đến nay nó Nhóm: 3 Trang 2 TỐI ƯU HÓA KẾT CẤU GVHD: TS VŨ TRƯỜNG VŨ được cải tiến đa dạng và có nhiều ứng dụng. Trước khi giới thiệu phương pháp ACO, luận án giới thiệu phương thức trao đổi thông tin gián tiếp của các con kiến và mô hình kiến nhân tạo. Trên đường đi, mỗi con kiến để lại một chất hóa học gọi là vết mùi dùng để đánh dấu đường đi. Bằng cách cảm nhận vết mùi, kiến có thể lần theo đường đi đến nguồn thức ăn được các con kiến khác khám phá theo phương thức chọn ngẫu nhiên có định hướng theo nồng độ vết mùi để xác định đường đi ngắn nhất từ tổ đến nguồn thức ăn. Ngoài ra các con kiến có thể trao đổi thông tin có được với nhau, thực hiện tính toán cần thiết, cập nhật mùi… Nhờ các con kiến nhân tạo này (về sau cũng gọi đơn giản là kiến) Dorigo (1991) đã xây dựng hệ kiến (AS) giải bài toán người chào hàng, hiệu quả của nó so với các phương pháp mô phỏng tự nhiên khác như AS, GA đã được kiểm chứng bằng thực nghiệm và được phát triển, ứng dụng phong phú với tên gọi chung là phương pháp ACO. I.2: Ý NGHĨA I.2.1: Ý nghĩa khoa học Áp dụng lý thuyết của thuật toán đàn kiến ACO để áp dụng trong các bài toán tối ưu tổ hợp So sánh và đánh giá hiệu quả của thuật toán di truyền và thuật toán đàn kiến ACO trong việc giải bài toán. I.2.2: Ý nghĩa thực tiễn Thuật toán đàn kiến có thể áp dụng trong các bài toán thực tế: lập lịch đi hành trình với chi phí tối thiểu, định tuyến trên mạng, cách di chuyển lắp đặt dầm cầu qua các chứng ngại vật ngắn và nhanh nhất, ….vv I.3: ỨNG DỤNG Thuật toán ACO được ứng dụng cho một số lượng lớn bài toán tối ưu tổ hợp. Những ứng dụng hiện nay của ACO chia thành hai lớp ứng dụng:  Lớp ứng dụng thứ nhất: Lớp bài toán tối ưu tổ hợp NP-hard cho cho công nghệ cũ thường ít thức ăn. Đặc tính thành công nhất của ứng dụng ACO tới những bài toán mà ở đó kiến kết hợp với vùng tìm kiếm để có cách giải quyết tốt nhất.  Lớp ứng dụng thứ hai là bài toán tìm đường đi ngắn nhất, ở đó khoảng cách bài toán giải quyết thay đổi ở thời gian thực thi bài toán. Những thay đổi này có thể ảnh hưởng không đổi của bài toán như đã có sẵn, nếu ảnh hưởng bị lẫn lộn , đặc tính được coi như chi phí cạnh, thay đổi theo thời gian. Nhóm: 3 Trang 3 TỐI ƯU HÓA KẾT CẤU GVHD: TS VŨ TRƯỜNG VŨ I.4: THUẬT TOÁN BẦY KIẾN I.4.1: Giới thiệu chung về thuật toán bầy kiến Các thuật toán kiến lần đầu tiên được giới thiệu bởi Dorigo và các cộng sự như là cách tiếp cận đa tác tử tới các vấn đề về tối ưu tổ hợp khó, như bài toán người du lịch (TSP), bài toán người đưa thư. Hiện nay số lượng các ứng dụng càng ngày càng tăng và các nhà khoa học đã ứng dụng nó vào rất nhiều các vấn đề tối ưu rời rạc. Các ứng dụng gần đây có thể kể đến như các bài toán lập lịch, tô màu đồ thị, định hướng trong mạng truyền thông, v.v… Các thuật toán kiến là các thuật toán dựa vào sự quan sát các bầy kiến thực. Kiến là loại cá thể sống bầy đàn. Chúng giao tiếp với nhau thông qua mùi mà chúng để lại trên hành trình mà chúng đi qua. Mỗi kiến khi đi qua một đoạn đường sẽ để lại trên đoạn đó một chất mà chúng ta gọi là mùi. Số lượng mùi sẽ tăng lên khi có nhiều kiến cùng đi qua. Các con kiến khác sẽ tìm đường dựa vào mật độ mùi trên đường, mật độ mùi càng lớn thì chúng càng có xu hướng chọn. Dựa vào hành vi tìm kiếm này mà đàn kíên tìm được đường đi ngắn nhất từ tổ đến nguồn thức ăn và sau đó quay trở tổ của mình. Sau đây là ví dụ về luồng đi của đàn kiến thực tế: Nhóm: 3 Trang 4 TỐI ƯU HÓA KẾT CẤU GVHD: TS VŨ TRƯỜNG VŨ Hình 1: Mô phỏng đường đi của bầy kiến a. Kiến đi theo đường thẳng giữa A và E b. Khi có chướng ngại vật kiến sẽ chọn hướng đi, có hai hướng với khả năng kiến sẽ chọn là như nhau. c. Trên đường ngắn hơn thì nhiều mùi (pheromone) hơn Hình 2: Mô phỏng khoảng cách đường đi của bầy kiến Xem hình 2a là giải thích rõ tình huống trong hình 1b. Giả sử khoảng cách DH=BH=DB qua C và =1, C là điểm nằm giữa B và D(hình 2a). Bây giờ chúng ta xem xét điều gì xảy ra tại những khoảng thời gian rời rạc: t=0, 1, 2… Giả định rằng 30 con kiến mới đi từ A đến B, 30 con từ E đến D, mỗi kiến di chuyển với tốc độ một đơn vị thời gian và khi di chuyển kiến để tại thời điểm t Nhóm: 3 Trang 5 TỐI ƯU HÓA KẾT CẤU GVHD: TS VŨ TRƯỜNG VŨ một vệt pheromone với nồng độ là 1. Để đơn giản chúng ta xét lượng pheromone bay hơi hoàn toàn và liên tục trong khoảng thời gian (t+1, t+2). Tại thời điểm t=0, thì không có vệt mùi nào trên cạnh và có 30 kiến ở B, 30 ở D. Việc lựa chọn đường đi của chúng ta ngẫu nhiên do đó, trung bình từ mỗi nút có 15 con kiến sẽ đi đến H và 15 con sẽ đi đến C (hình 2b) Tại thời điểm t=1, 30 con kiến mới đi từ A đến B, lúc này nó sẽ chọn hướng đến C hoặc hướng đến H. Tại hướng đến H có vệt mùi 15 do 15 con kiến đi từ B đến H, tại hướng đến C có vệt mùi 30 do 15 kiến đi từ B đến D và 15 con đi từ D đến B thông qua C (hình 2c). Do đó khả năng kiến hướng đến chọn đường đến C, do đó số kiến mong muốn đi đến C sẽ gấp đôi số kiến đi đến H (20 con đến C và 10 con đến H). Tương tự như vậy cho 30 con kiến mới đi từ D đến B. Quá trình sẽ liên tục cho đến khi tất cả kiến sẽ chọn đường đi ngắn nhất. Trên đây chúng ta mô tả hành vi tìm kiếm của bầy kiến thực.Sau đây , chúng ta sẽ tìm hiểu sâu hơn về các thuật toán kiến. Thuật toán tối ưu bầy kiến (ACO) nghiên cứu các hệ thống nhân tạo dựa vào hành vi tìm kiếm của bầy kiến thực và được sử dụng để giải quyết các vấn đề về tối ưu rời rạc.Thuật toán bầy kiến siêu tìm kiếm(ACO meta_heuristic) lần đầu tiên được Dorigo, Di Caro và Gambardella đề xuất vào năm 1999. Metaheuristic là một tập các khái niệm về thuật toán được sử dụng để xác định các phương thức tìm kiếm thích hợp cho một tập các vấn đề khác nhau. Hay nói cách khác, một siêu tìm kiếm ( meta-heuristic) có thể coi là một phương thức tìm kiếm đa năng. ACO là một meta-heuristic, trong đó một tập các con kiến nhân tạo phối hợp tìm kiếm các giải pháp tốt cho các vấn đề về tối ưu rời rạc. Sự phối hợp là yếu tố cối lõi của các thuật toán ACO. Các con kiến nhân tạo liên lạc với nhau thông qua trung gian mà ta thường gọi là mùi. Các thuật toán ACO được sử dụng để giải quyết các vấn đề về tối ưu tổ hợp tĩnh và động. Các vấn đề tĩnh là các vấn đề mà ở đó các đặc tính của vấn đề là không thay đổi trong suốt quá trình giải quyết vấn đề. Còn các vấn đề động thì ngược lại là một hàm các tham số mà giá trị của nó là động hay thay đổi trong quá trình giải quyết vấn đề, ví dụ bài toán người đưa thư là một vấn đề dynamic problem 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à Nhóm: 3 Trang 6 TỐI ƯU HÓA KẾT CẤU GVHD: TS VŨ TRƯỜNG VŨ 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à 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 and Hoos đề xuất MAX-MIN Ant System (MMAS). Tất cả đều áp dụng cho bài toán người du lịch đối xứng hay không đối xứng và cho kết quả mỹ mãn. Dorigo, Gambardella and Stützle cũng đề xuất những phiên bản lai của ACO với tìm kiếm địa phưong. 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. Đâ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ệt thống MaxMin 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. 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. Nhóm: 3 Trang 7 TỐI ƯU HÓA KẾT CẤU GVHD: TS VŨ TRƯỜNG VŨ 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. Trên đây là sơ lược chung về các thuật toán kiến, mục tiếp theo sẽ mô tả về sơ đồ chung của thuật toán kiến. I.4.2: Sơ đồ chung của thuật toán bầy kiến Procedure ACO Initial(); While (!ĐK dừng) do ConstructSolutions(); LocalSearch(); /*Tuỳ ý, có thể có hoặc không UpdateTrails(); End; End; trong đó: ĐK dừng (tức là điều kiện dừng) là điều kiện đạt được khi thuật toán ở trạng thái kết thúc. Với bài toán người đưa thư thì ĐK dừng là điều kiện đạt được khi số vòng lặp của thuật toán = số vòng lặp lớn nhất do người dùng tự định nghĩa hoặc là tất cả đàn kiến đều đi theo một đường (tức là đường đi ngắn nhất). ConstrucSolutions() là hàm xây dựng một giải pháp có thể theo phương pháp siêu tìm kiếm(meta-heuristic), với bài toán người đưa thư thì đó là hàm xây dựng chu trình cho mỗi kiến . UpdateTrails() là hàm cập nhật mùi cho hành trình mà kiến đã đi qua. LocalSearch() là hàm tìm kiếm địa phương, giúp tìm ra tối ưu cục bộ. Nhóm: 3 Trang 8 TỐI ƯU HÓA KẾT CẤU GVHD: TS VŨ TRƯỜNG VŨ Hình: Sơ đồ chung của thuật toán bầy kiến Từ thuật toán trên ta có thể rút ra các bước giải quyết một bài toán ứng dụng với thuật toán đàn kiến: Bước 1: Thể hiện bài toán trong khung cảu tập các thành phần và sự chuyển đổi hoặc bởi một đồ thị được đánh dấu bởi kiến đề xây dựng cách giải quyết. Bước 2: Định nghĩa thích hợp cho mùi lạ  rs là một xu hướng quyết định. Đó là một bước chủ yếu trong việc hình thành thuật toán ACO và xác định rõ mùi lạ không là một nhiệm vụ tầm thường và nó tính toán yêu cầu bên trong bài toán sau đáp án. Bước 3: Định nghĩa thích hợp kinh nghiệm cho mỗi quyết định để một con kiến có thể xây dựng cách giải quyết, ví dụ: Định nghĩa thông tin kinh nghiệm nrs kết hợp Nhóm: 3 Trang 9 TỐI ƯU HÓA KẾT CẤU GVHD: TS VŨ TRƯỜNG VŨ mỗi thành phần hoặc trạng thái chuyển đổi. Thông tin kinh nghiệm chủ yếu cho việc tìm kiếm tốt nếu thuật toán tìm kiếm vùng không có sẵn hoặc không thể ứng dụng Bước 4: Nếu thực hiện được, tạo ra một vùng thuật toán tìm kiếm hiệu quả cho bài toán sau đáp án bởi vì kết quả của nhiều ứng dụng ACO cho bài toán tổ hợp tối ưu NP-hard thể hiện sự tìm kiếm tốt nhất đạt được khi ACO có vùng lạc quan. Bước 5: Lựa chọn một thuật toán ACO và các ứng dụng nó vào những bài toán cần giải quyết. Bước 6: Các tham số phù hợp cảu thuật toán ACO. Một điểm bắt đầu tốt cho tham số phù hợp là sử dụng cài đặt tham số để tìm kiếm tốt khi ứng dụng thuật toán ACO vào bài toán đơn giản hoặc các bài toán khác nhau. Một vấn đề khác chi phối thời gian trong nhiệm vụ phù hợp là để sử dụng thủ tục động cho tham số phù hợp. Nó nên xóa đi các bước tiếp để có thể chỉ đưa ra một hướng dẫn sử dụng thuật toán ACO. Thêm nữa, việc sử dụng là sự kết hợp các quá trình ở đó với vài bài toán sâu hơn và hoạt động của thuật toán, vài lựa chọn ban đầu cần phải sửa lại. Cuối cùng, chúng ta muốn trên thực tế, điều quan trọng nhất của các bước là đầu tiên phải khớp bởi vì lựa chọn tồi ở trạng thái này tính không thể tính với một tham số gốc phù hợp tốt. I.4.3: Nội dung của thuật toán bầy kiến Bài toán cần giải sẽ được đưa về dạng một đồ thị đầy đủ với các ràng buộc của bài toán được thể hiện bằng các công thức toán học. Việc giải bài toán đặt ta có sẽ đưa về là tìm một đường đi (hoặc tập các đỉnh) thỏa mãn các ràng buộc của bài toán. Các nguyên tắc sau được đưa ra:  Thông tin pheromone được tính toán và đặt trên mỗi đoạn đường.  Nút ban đầu cho đường đi của mỗi con kiến được chọn một cách ngẫu nhiên.  Đường đi được lựa chọn dựa trên các nguyên tắc sau:  Dựa vào thông tin pheromone có trên các đoạn đường để tính xác suất của các đoạn tiếp theo được chọn vào làm đường đi của con kiến.  Xác suất lớn hơn cho đoạn đường đi có nhiều lượng pheromone được đặt hơn. Và các đường đi có lượng thông tin pheromone bé sẽ có xác suất được chọn thấp hơn.  Con kiến tiếp tục việc tìm đường đi cho tới khi hoàn thành một đường đi của nó (thỏa mãn điều kiện dừng của con kiến).  Một đường đi hoàn chỉnh được gọi là một lời giải (solution) cho bài toán đặt ra. Các lời giải sẽ được phân tích, so sánh và đánh giá để tìm phương án tối ưu nhất có thể. Đó là lời giải tối ưu của bài toán. Nhóm: 3 Trang 10 TỐI ƯU HÓA KẾT CẤU GVHD: TS VŨ TRƯỜNG VŨ  Sau khi con tất cả kiến trong đàn hoàn thành lời giải của nó thì sẽ tiến hành cập nhật thông tin pheromone cho các cung. Số lượng của pheromone sẽ được tính toán và điều chỉnh để tìm được phương án tối ưu tốt hơn.  Các lời giải tốt hơn sẽ có khối lượng pheromone lớn hơn để đặt trên các cung đã được đi qua. Ngược lại các lời giải tồi hơn sẽ có khối lượng pheromone bé hơn.  Xác suất cao hơn cho một con kiến chọn đường đi có pheromone lớn.  Quá trình lặp cho đến khi phần lớn kiến trong đàn kiến chọn cùng một đường đi (phương án hội tụ của lời giải). I.4.3.1: Mã giả cho thuật toán Procedure AntColonyAlgorithm B1: Khởi tạo các thông tin Pheromone cho các đường đi B2: Do while (Chưa thỏa mãn điều kiện dừng) B3: Do until (Mỗi Ant hoàn thành một đường đi) B4: Cập nhật thông tin pheromone cục bộ (Local trail update) B5: End Do B6: Phân tích các lời giải thu được (Analyze solution) B7: Cập nhật thông tin pheromone toàn cục (Global trail update) B8: End Do End Procedure Đối với thuật toán ACO, sự hội tụ được đảm bảo tuy nhiên tốc độ và thời gian thì không biết trước, thường sử dụng để giải quyết các vấn đề tối thiểu về giá thành. Thường các bài toán trước khi được giải bằng thuật toán ACO phải được biến đổi đưa về dạng đồ thị đầy đủ có trọng số. Bao gồm các nút và các cung không định hướng. Sau khi đi biến đổi bài toán về dạng phù hợp mới áp dụng thuật toán ACO để giải. Trên đồ thị này các con kiến sẽ đi xây dựng các lời giải cho bài toán. Sau đây là mô hình cụ thể hơn về thuật toán ACO. Mô tả về thuật toán ACO với việc thực hiện song song hoạt động của các con kiến: 1 Procedure ACO_Metaheuristic 2 parameter_initialization 3 while (termination_criterion_not_satisfied) 4 schedule_activities 5 ants_generation_and_activity ( ) 6 pheromone_evaporation ( ) 7 daemon_actions ( ) {optional} 8 end schedule_activities 9 end while 10 end Procedure Nhóm: 3 Trang 11 TỐI ƯU HÓA KẾT CẤU GVHD: TS VŨ TRƯỜNG VŨ 1 Procedure ants_generation_and_activity ( ) 2 repeat in parallel for k=1 to m (number_of_ants) 3 new_ant (k) 4 end repeat in parallel 5 end Procedure 1 Procedure new_ant (ant_id) 2 initialize_ant (ant_id) 3 L = update_ant_memory ( ) 4 While (current_state  target_state) 5 P = compute_transition_probabilities (A , L ,  ) 6 next_state = apply_ant_decision_policy (P ,  ) 7 move_to_next_state (next_state) If (on_line_step-by-step-pheromone_update) 8 deposit_pheromone_on_the_visited_edge ( ) end if 9 L = update-internal_state ( ) 10 end while if (online_delayed_pheromone_update) 11 for each visited edge 12 deposit_pheromone_on_the_visited_edge ( ) 13 end for end if 14 release_ant_resources (ant_id) 15 end Procedure Trong đó thủ tục ants_generation_and_activity() là thủ tục chính, cơ bản của giải thuật. Thủ tục này công việc chính gồm: Tạo và khởi tạo các thông số cho đàn kiến. Với mỗi con kiến trong đàn sẽ tiến hành xây dựng một lời giải cho bài toán khi chưa thỏa mãn điều kiện dừng. Ngoài ra có hai thủ tục phụ thêm vào là:  Pheromone_evaporation(): Là tác động của môi trường để làm giảm thông tin pheromone theo thời gian. Thủ tục này để tránh bế tắc trong tìm kiếm và cho phép đàn kiến mở rộng không gian tìm kiếm.  Daemon_action(): Là thủ tục hỗ trợ thêm và không gặp trong thực tế (không có ở đàn kiến tự nhiên). Là một thủ tục để điều chỉnh các thông số khi cần thiết làm tăng tính hiệu quả của thuật toán. Ví dụ: Thủ tục tìm kiếm cục bộ, thủ tục khởi tạo lại các thông tin pheromone khi gặp bế tắc trong tìm kiếm. I.4.3.2: Các sơ đồ thuật toán Nhiều thuật toán đã được đưa ra dựa trên mô hình thuật toán metaheuristic ACO. Trong các mô hình đưa ra để giải quyết các bài toán tổ hợp tối ưu NP-khó luận văn trình bày chi tiết về 5 mô hình. Các mô hình này là phát triển dựa trên mô hình Nhóm: 3 Trang 12 TỐI ƯU HÓA KẾT CẤU GVHD: TS VŨ TRƯỜNG VŨ thuật toán ACO cụ thể trình bày ở phần 3.2 ngay trên. Theo các nghiên cứu cho thấy khi sử dụng thuật toán bầy kiến nói chung các thông tin pheromone và heuristic có thể áp dụng cho các nút hoặc cạnh nối. Trong các thuật toán đưa ra sau đây thì thông tin pheromone và heuristic chỉ gắn với các cạnh mà thôi. I.4.3.2.1: Thuật toán Ant System (AS) Được phát triển bởi Dorigo, Maniezzo và Colorni năm 1991, là thuật toán ACO đầu tiên. Ban đầu có 3 biến thể khác nhau là: AS-Density, AS-Quantity và AS-Cycle khác nhau bởi cách thức cập nhật thông tin Pheromone. Trong đó:  AS-Density: Thì đàn kiến sẽ đặt thêm pheromone trong quá trình xây dựng lời giải (online step-by-step pheromone update), lượng pheromone để cập nhật là một hằng số.  AS-Quantity: Thì đàn kiến sẽ đặt thêm pheromone trong quá trình xây dựng lời giải (online step-by-step pheromone update), lượng pheromone để cập nhật là phụ thuộc vào độ mong muốn (thông tin heuristic) với đoạn đường đi qua ηij.  AS-Cycle: Thông tin pheromone sẽ được cập nhật khi lời giải đã hoàn thành (online delayed pheromone update). Đây là mô hình cho kết quả tốt nhất và được coi như là thuật toán AS. Như vậy theo mô hình của AS-cycle thì pheromone sẽ cập nhật khi tất cả con kiến hoàn thành lời giải của mình.Việc cập nhật pheromone được tiến hành như sau:  Đầu tiên tất cả pheromone trên các cung sẽ được giảm đi bởi một hằng số (pheromone evaporation).  rs  (1  p). rs . Với ρ trong khoảng (0,1) là tốc độ bay hơi của pherromone.  Tiếp theo mỗi con kiến trong đàn sẽ đặt thêm một lượng thông tin pheromone, lượng pheromone này là hàm của chất lượng lời giải mà con kiến xây dựng.  rs  rs   rsk , ars  Sk . Trong đó:  rsk  f  C (Sk )  . Ban đầu AS không sử dụng daemon action, tuy nhiên sẽ càng tốt hơn nếu thêm vào đó một thủ tục tìm kiếm cục bộ để làm tăng chất lượng của lời giải. Còn phương trình để xác định nút tiếp theo trong quá trình xây dựng lời giải của con kiến như sau: Nhóm: 3 Trang 13 TỐI ƯU HÓA KẾT CẤU GVHD: TS VŨ TRƯỜNG VŨ     rs  . rs   , s  N k (r )  k prs    k  ru  . ru   , uN r  trái l¹i.  0, Tóm tắt về thuật toán này như sau: 1 Procedure new_ant (ant_id) 2 k = ant_id ; r = generate_initial_state ; Sk  r 3 Lk  r 4 while (current-state  target_state)    rs  .rs   k 5 for each s  N k (r) do prs     uN  ru  .ru  k r 6 7 8 9 10 11 next_state = apply_ant_decision_policy (P , N k (r ) ) r = next_state ; Sk  Sk , r  --Lk  Lk  r end while { the pheromone_evaporation ( ) procedure triggers and evaporates pheromone in every edge ars :  rs  1  p  . rs } for each edge ars  Sk do  rs  rs  f  C (Sk )  12 13 end for 14 release_ant_resources (ant_id) 15 end Procedure. I.4.3.2.2: Thuật toán Ant Colony System(ACS) Phát triển từ thuật toán AS với một số cải thiện như sau:  Sử dụng một luật khác cho việc di chuyển, gọi là pseudo-random proportional rule. Gọi k là con kiến đang đứng tại nút r. q0 là một tham số, và một giá trị ngẫu nhiên q. Trong đó giá trị của q và q0 là trong khoảng (0,1). Nút s tiếp theo được chọn để di chuyển kiến k tới được chọn như sau: If q  qo : prsk  1,   0, s  arg max { ru .ru }, u  Nk ( r ) trái l¹i. else ( q  qo ) : Nhóm: 3 Trang 14 TỐI ƯU HÓA KẾT CẤU GVHD: TS VŨ TRƯỜNG VŨ    prsk    0,  rs  . rs   uN   k r  ru  . ru   , s  N k (r ) trái l¹i.  Có Daemon action, thực hiện việc cập nhật pheromone chỉ duy nhất với lời giải Sglobal-best. Cập nhật theo công thức như sau:  rs  (1  p). rs , ars  S global best ,  rs  rs  p . f (C ( S global best )), ars  S global best.  Áp dụng online step-by-step pheromone update  rs  (1   ). rs   . 0 . Trong đó φ là một tham số để giảm pheromone thứ hai sau ρ. Còn được chọn là một tham số rất bé (như là ngưỡng dưới của pheromone). Tóm tắt về thuật toán này như sau: 1 Procedure new_ant (ant_id) 2 k = ant_id ; r = generate_initial_state ; Sk  r 3 Lk  r 4 while (current-state  target_state) 5 for each s  Nk (r ) do compute brs  rs .rs 6 q = generate_random_value_in_[0 , 1] If ( q  q0 ) Next_state = max brs , N k (r ) ) else for each s  Nk (r ) do prsk  brs  uNk ( r ) bru next_state = apply_ant_decision_policy (P , N k (r ) ) end if 7 r = next_state ; Sk  Sk , r   rs  (1   ). rs   . 0: 8 Lk  Lk  r 9 10 end while 11 --12 release_ant_resources (ant_id) 13 end Procedure. Và thủ tục cập nhật: 1 Procedure daemon_actions 2 for each S k do local_search ( S k ) Scurrent best  best_solution ( S k ) 3 Nhóm: 3 {optional} Trang 15 TỐI ƯU HÓA KẾT CẤU GVHD: TS VŨ TRƯỜNG VŨ 4 if (better ( Scurrent best , S global best )) 5 S global best = Scurrent best 6 end if 7 for each edge ars  S global best do { the pheromone_evaporation ( ) procedure triggers and evaporates pheromone in every edge ars :  rs  1  p  . rs } 8  rs  rs  p . f  C (S global best )  9 end for 10 end Procedure. I.4.3.2.3: Thuật toán Max–Min Ant System(MMAS) Được phát triển bởi Stutzle và Hooss vào năm 1996, được mở rộng lên từ hệ thống AS. Một số đặc điểm được mở rộng từ hệ thống AS như sau:  Giống như ACS, MMAS thực hiện offline pheromone trail update, tức là sau khi toàn bộ kiến trong đàn hoàn thành lời giải thì việc cập nhật được tiến hành cho lời giải tối ưu. Đầu tiên thực hiện bay hơi bớt thông tin pheromone (pheromone evaporation) trên tất cả các cạnh.  rs  1    . rs . Sau đó chỉ có các cạnh thuộc lời giải tốt nhất được cập nhật thông tin pheromone  rs   rs  f  C  Sbest   , ars  Sbest . Thông thường trong MMAS các lời giải được tinh chỉnh bằng cách tối ưu cục bộ (local optimizer) trước khi cập nhật thông tin pheromone.  Một cải tiến quan trọng trong hệ thống MMAS là việc thêm vào giới hạn cận trên và dưới của thông tin Pheromone (  max và  min ), điều đó giúp tránh hội tụ tại điểm tối ưu cục bộ. Khởi tạo tất cả thông số Pheromone giá trị cận trên để ưu tiên việc khai phá không gian tìm kiếm. Cận trên  max thường được chọn là giá trị lớn nhất mà Pheromone có thể đạt được ở vòng lặp cuối cùng. *  max 1/( p . C (S * )). Trong đó S là lời giải tối ưu, bởi vì lời giải tối ưu không biết trước nên thông thường được thay thế bởi Sglobal-best trong tính toán. Cách chọn cận dưới  min , thông thường người ta chọn  min để thỏa mãn theo tỷ lệ giữa cận trên và cận dưới  max /  min = 2n. Do đó tính  min =  max / 2n. Tỉ lệ này phải chọn không nên quá cao, bởi vì khi đó xác suất để chọn đường đi có mức độ Pheromone thấp là quá nhỏ. Mặt khác nếu chọn Nhóm: 3 Trang 16 TỐI ƯU HÓA KẾT CẤU GVHD: TS VŨ TRƯỜNG VŨ tỉ lệ này quá lớn thì xác suất chọn đường đi co Pheromone cao là gần với xác suất chọn đường đi có mức độ Pheromone thấp.  Khi khởi tạo thông tin pheromone cho các thành phần thì tất cả nhận giá trị lớn nhất có thể của Pheromone là  max nhằm tăng cường việc khai phá không gian tìm kiếm. Một chú ý trong hệ thống MMAS là khi xảy ra hội tụ cục bộ thì có cơ chế khởi tạo lại thông tin pheromone cho các nút và giá trị để khởi tạo lại là  max . Hàm cập nhật Daemon action của thuật toán MMAS như sau: 1 Procedure daemon_actions 2 for each S k do local_search ( S k ) 3 Scurrent best  best_solution ( S k ) 4 if (best ( Scurrent best , S global best )) 5 S global best = Scurrent best 6 end if Sbest = decision ( S global best , Scurrent best ) 7 8 for each edge ars  Sbest do  rs  rs  f  C (Sbest )  9 10 if (  rs  min )  rs  min 11 end for 12 if (stagnation_condition) 13 for each edge ars do  rs  max 14 end if 15 end Procedure I.4.3.2.4: Thuật toán Rank-Based Ant System(RBAS) Đây cũng là một thuật toán được mở rộng phát triển từ hệ thống AS đưa ra bởi Bullnheimer, Hartl và Strauss vào năm 1997. Thuật toán này đưa vào ý tưởng xếp hạng cho các lời giải khi thực hiện cập nhật pheromone. Cụ thể như sau:  Đầu tiên, m con kiến được xếp hạng theo thứ tự giảm dần dựa theo chất lượng lời giải mà nó thu được. Ví dụ: (S1, S2, … Sm-1, Sm) trong đó S1 là phương án tốt nhất.  Pheromone chỉ được đặt thêm trên các cung của б -1 con kiến có lời giải tốt nhất. Lượng pheromone cũng phụ thuộc trực tiếp vào thứ hạng sắp xếp của con kiến.  Các đoạn đường đi của lời giải tốt nhất được nhận thêm một lượng pheromone phụ thuộc vào chất lượng lời giải. Các công thức như sau:  rs  rs   .  rsgb   rsrank . Nhóm: 3 Trang 17 TỐI ƯU HÓA KẾT CẤU Trong đó GVHD: TS VŨ TRƯỜNG VŨ   f (C (S global best )), ars  S global best  rsgb   trái l¹i.  0, Và  rsrank  1 ' '  (   ). f C ( S  ) , ars S     1 0, trái l¹i.    Tóm tắt thủ tục cập nhật pheromone của thuật toán này: 1 Procedure daemon_actions 2 for each S k do local_search ( S k ) {optional} 3 rank (S1 ,..., S m ) in decreasing order of solution quality into (S1' ,..., Sm' ) 4 if (best ( S1' , S global best )) 5 6 7 8 9 10 11 12 13 S global best = S1' end if for  1 to  1 do for each edge ars  S ' do   rs  rs  (   ). f C  S'   end for end for for each edge ars  S global best do   rs  rs   . f C  S global best   14 end for 15 end Procedure I.4.3.2.5: Thuật toán Best-Worst Ant System(BWAS) Thuật toán được đưa ra bởi Cordon vào năm 1999. Thuật toán này bao gồm một thuật toán mở rộng khác của AS là MMAS (về luật di chuyển và việc bay hơi của pheromone). Bên cạnh đó trong thuật toán này còn quan tâm tới của việc tối ưu cục bộ một cách hệ thống để nâng cao chất lượng lời giải của con kiến. Trong thuật toán BWAS có 3 daemon action thêm vào gồm có:  Đầu tiên, áp dụng luật có tên best-worst pheromone update để tăng cường pheromone trên các đoạn đường đi qua bởi lời giải tốt nhất toàn cục (global best solution). Thêm vào đó luật này sẽ phạt những cạnh của lời giải tồi nhất trong lần lặp Scurrent-worst.  Áp dụng Pheromone trail mutation để đi theo các hướng khác nhau trong quá trình tìm kiếm.  BWAS có cơ chế khởi tạo lại thông tin pheromone khi thuật toán bị đình trệ, bằng cách thiết lập pheromone trail cho tất cả các thành phần bằng . Nhóm: 3 Trang 18 TỐI ƯU HÓA KẾT CẤU GVHD: TS VŨ TRƯỜNG VŨ Mô hình thủ tục Daemon action của thuật toán BWAS như sau: 1 Procedure daemon_actions 2 for each S k do local_search ( S k ) 3 Scurrent best  best_solution ( S k ) 4 if (best ( Scurrent best , S global best )) 5 S global best = Scurrent best 6 end if 7 for each edge ars  S global best do 8  rs  rs  p. f  C (S global best )  sum  sum   rs 9 10 end for 11  threshold  sum | S globad  best | Scurrent  worst  worst _ solution (Sk ) 12 13 for each edge ars Scurrent  worst and ars S global best do 14  rs  (1  p). rs 15 end for mut  mut  it , threshold  16 17 for each nút / component r {1,..., l} do 18 z = generate_random_value_in_[0,1] 19 if ( z   Pm ) 20 s = generate_random_value_in_[1,…, 1] 21 a = generate_random_value_in_[0,1] 22 if (a  0)  rs  rs  mut 23 else  rs  rs  mut 24 end if 25 end for 26 if (stagnation_condition) 27 for each ars do  rs  0 28 end if 29 end Procedure Mục này chỉ đưa ra 5 mô hình thuật toán ACO phát triển từ hệ thống Ant System. Nhưng đó chỉ là một số các dạng tiêu biểu của thuật toán ACO, còn tồn tại rất nhiều các biến thể khác. Và trong đồ án sẽ áp dụng thuật toán theo mô hình hệ thống MMAS để giải bài toán CPMP. Mô hình thuật toán MMAS là một trong các thuật toán hiệu quả nhất của các thuật toán bầy kiến. Nhóm: 3 Trang 19 TỐI ƯU HÓA KẾT CẤU GVHD: TS VŨ TRƯỜNG VŨ I.5: ÁP DỤNG Tài liệu tham khảo [1] [2] [3] [4] [5] [6] [7] [8] [9] Nhóm: 3 Nguyễn Đức Nghĩa, Nguyễn Tô Thành - Toán rời rạc – Nhà xuất bản đại học Quốc Gia Hà Nội, 2001. Nguyễn Đức Nghĩa. Giáo trình Phân tích và thiết kế thuật toán, Hà Nội, 2003. Nguyễn Đức Nghĩa. Giáo trình Nhập môn tính toán khoa học, Hà Nội, 2002. Nguyễn Đức Nghĩa. Tối ưu hóa: quy hoạch tuyến tính và rời rạc, Nhà xuất bản Giáo Dục, 1999. Marco Dorigo and ThomasStu¨ tzle: “Ant Conoly Optimization”, A Bradford Book, The MIT Press, Cambridge, Massachusetts, London, England. M. Dorigo, V. Maniezzo & A. Colorni: Ant System . IEEE Transactions on Systems, Man, and Cybernetics-Part B, 26(1):29-41,1996 M. Dorigo, Optimization, Learning and Natural Algorithms: Elitist Ant System , 1992 David E. Goldberg. The parameter-less genetic algorithm in practice, 2003 Kumara Sastry, David Goldberg. Genetic Algorithm Trang 20