Xem mẫ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 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 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 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 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: 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 Nhóm: 3 Trang 5 ... - tailieumienphi.vn
nguon tai.lieu . vn