intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

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

Chia sẻ: Thanh Tin | Ngày: | Loại File: DOC | Số trang:21

Thêm vào BST
Báo xấu
210
lượt xem 27
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài tiểu luận "Tối ưu hóa kết cấu" giới thiệu đến các bạn những nội dung về thuật toán bầy kiến, ý nghĩa tối ưu hóa kết cấu, nội dung tối ưu hóa kết cấu, áp dụng tối ưu hóa kết cấu,... Mời các bạn cùng tham khảo nội dung bài tiểu luận để có thêm tài liệu phục vụ nhu cầu học tập và nghiên cứu.

Chủ đề:

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

Lưu

Nội dung Text: Bài tiểu luận: Tối ưu hóa kết cấu

  1. 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 2 I.2: Ý NGHĨA  3 I.2.1: Ý nghĩa khoa học  3 I.2.2: Ý nghĩa thực tiễn  3 I.3: ỨNG DỤNG  3 I.4: THUẬT TOÁN BẦY KIẾN  4 I.4.1: Giới thiệu chung về thuật toán bầy kiến  4 I.4.2: Sơ đồ chung của thuật toán bầy kiến  8 I.4.3: Nội dung của thuật toán bầy kiến  10 I.4.3.1: Mã giả cho thuật toán  11 I.4.3.2: Các sơ đồ thuật toán  12 I.4.3.2.1: Thuật toán Ant System (AS)  13 I.4.3.2.2: Thuật toán Ant Colony System(ACS)  14 I.4.3.2.3: Thuật toán Max–Min Ant System(MMAS)  16 I.4.3.2.4: Thuật toán Rank­Based Ant System(RBAS)  17 I.4.3.2.5: Thuật toán Best­Worst Ant System(BWAS)  18 I.5: ÁP DỤNG  20 Nhóm: 3                                                                                           Trang 1
  2. 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. Nhóm: 3                                                                                           Trang 2
  3. TỐI ƯU HÓA KẾT CẤU GVHD: TS VŨ TRƯỜNG VŨ  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ó đượ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 Nhóm: 3                                                                                           Trang 3
  4. TỐI ƯU HÓA KẾT CẤU GVHD: TS VŨ TRƯỜNG VŨ 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. I.4: THU   ẬT TOÁN BẦY KIẾN  I.4.1: G    i  ớ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
  5. 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 Nhóm: 3                                                                                           Trang 5
  6. TỐI ƯU HÓA KẾT CẤU GVHD: TS VŨ TRƯỜNG VŨ 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 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 đề  Nhóm: 3                                                                                           Trang 6
  7. TỐI ƯU HÓA KẾT CẤU GVHD: TS VŨ TRƯỜNG VŨ 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à 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. Nhóm: 3                                                                                           Trang 7
  8. TỐI ƯU HÓA KẾT CẤU GVHD: TS VŨ TRƯỜNG VŨ 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   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. 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. 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; Nhóm: 3                                                                                           Trang 8
  9. TỐI ƯU HÓA KẾT CẤU GVHD: TS VŨ TRƯỜNG VŨ        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 9
  10. 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 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. Nhóm: 3                                                                                           Trang 10
  11. TỐI ƯU HÓA KẾT CẤU GVHD: TS VŨ TRƯỜNG VŨ 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.  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 Nhóm: 3                                                                                           Trang 11
  12. TỐI ƯU HÓA KẾT CẤU GVHD: TS VŨ TRƯỜNG VŨ 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 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) Nhóm: 3                                                                                           Trang 12
  13. TỐI ƯU HÓA KẾT CẤU GVHD: TS VŨ TRƯỜNG VŨ                     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   ơ đồ t h   u   ậ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 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)   Nhóm: 3                                                                                           Trang 13
  14. TỐI ƯU HÓA KẾT CẤU GVHD: TS VŨ TRƯỜNG VŨ Đượ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 đó:                                      ∆τ rs = f ( C ( Sk ) ) .   k 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: α β τ rs � � � ηrs � �. � � � α β , s N k (r )                          prsk = τ ru � � � ηru � �. � � � , u Nrk 0, trái  l¹ i. Nhóm: 3                                                                                           Trang 14
  15. TỐI ƯU HÓA KẾT CẤU GVHD: TS VŨ TRƯỜNG VŨ 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 ;  S k = r 3         Lk = r 4         while  (current­state   target_state) [ τ rs ] .[ ηrs ] α β 5                for  each  s    N k (r) do   p = k [ τ ru ] .[ ηru ] rs α β k u N r 6                next_state = apply_ant_decision_policy (P ,  N k (r ) ) 7                r = next_state ;   S k =< S k , r > 8                ­­­ 9                 Lk = Lk r 10              end  while                   { the pheromone_evaporation ( )  procedure  triggers and                   evaporates  pheromone in every edge   ars : τ rs = ( 1 − p ) .τ rs } 11              for  each  edge   ars Sk   do 12                     τ rs =τ rs + f ( C ( S k ) ) 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 : 1, s = arg max {τ ru .ηruβ },                                                  prsk = u Nk (r ) 0, trái  l¹ i.                           else  ( q > qo ) : α β τ rs � � � ηrs � � .� � � α β , s N k (r )                                                  prs = k u Nrk τ ru � � � ηru � � .� � � 0, trái  l¹ i. Nhóm: 3                                                                                           Trang 15
  16. TỐI ƯU HÓA KẾT CẤU GVHD: TS VŨ TRƯỜNG VŨ  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 ;    S k = r 3         Lk = r 4        while  (current­state   target_state) 5               for  each   s N k (r )  do  compute   brs =τ rs .ηrsβ 6               q = generate_random_value_in_[0 , 1]                  If   ( q 8                τ rs = (1 − ϕ ).τ rs + ϕ .τ 0: 9                Lk = Lk r   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   Sk   do  local_search ( S k )    {optional} 3          Scurrent −best = best_solution  ( S k ) 4         if  (better ( Scurrent −best , S global −best )) 5                 S global −best  = Scurrent −best 6          end  if Nhóm: 3                                                                                           Trang 16
  17. TỐI ƯU HÓA KẾT CẤU GVHD: TS VŨ TRƯỜNG VŨ 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 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. Nhóm: 3                                                                                           Trang 17
  18. TỐI ƯU HÓA KẾT CẤU GVHD: TS VŨ TRƯỜNG VŨ  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  Sk   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           Sbest  = decision ( S global −best , Scurrent −best ) 8          for  each  edge  ars   Sbest  do 9                  τ rs =τ rs + f ( C ( Sbest ) ) 10                if  ( τ rs
  19. TỐI ƯU HÓA KẾT CẤU GVHD: TS VŨ TRƯỜNG VŨ Và σ −1 (σ − µ ). f ( C ( S µ' ) ) , ars S µ'     ∆τ = rank                   rs µ =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  Sk   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                 S global −best  =  S1' 6          end  if 7          for   µ =1   to     σ −1   do 8                for  each  edge  ars   S µ'  do ( 9                         τ rs =τ rs + (σ − µ ). f C ( S µ ) ' ) 10               end for  11         end for 12         for  each  edge  ars     S global −best   do ( 13                         τ rs =τ rs + σ . f C ( S global −best ) ) 14        end  for 15   end Procedure I.4.3.2.5: Thuậ    t toán Best­W    orst 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 19
  20. 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  Sk   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 ) ) 9                    sum = sum + τ rs 10         end for      sum 11          τ threshold = | S globad − best | 12          Scurrent − worst = worst _ solution ( S k ) 13          for  each  edge  ars   Scurrent − worst and  ars   S global −best do 14                 τ rs = (1 − p).τ rs 15         end for   16          mut = mut ( it ,τ threshold ) 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 20
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

LV.09: Bộ Luận Văn Tốt Nghiệp Chuyên Ngành Quản Trị Kinh Doanh
81 tài liệu
1643 lượt tải
THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
2=>2