Trí tuệ nhân tạo - thuật toán tìm kiếm đàn kiến

- Trƣờng Đ ạ i H ọ c Công Nghi ệ p Hà N ộ iKhoa Công Ngh ệ Thông Tin.
- BÀI T Ậ P L Ớ N TRÍ TU Ệ NHÂN T Ạ O Đề tài: NGHIÊN C Ứ U V Ề BÀI TOÁN ĐÀN KIẾ N Gi ảng viên hướ ng d ẫ n:Nhóm sinh viên th ự c hi ệ n.
- Đào Duy Oánh • Lê Thành Thiệ n • Nguy ễn Đứ c Thu ậ n • Phan Thanh Tú L ớp: ĐH Hệ th ố ng thông tin - K5Hà N ộ i – 2013 Thu ật toán đàn kiế n ĐH HTTT – K5 1 M Ụ C L Ụ C CHƢƠNG I: SƠ LƢỢ C V Ề BÀI TOÁN ĐÀN KIẾ N.
- Đàn kiế n t ự nhiên (natural ant colonies.
- T ừ nh ữ ng con ki ế n t ự nhiên t ớ i thu ậ t toán ACO.
- 3 CHƢƠNG II: XÂY DỰ NG THU ẬT TOÁN ĐÀN KIẾ N.
- Gi ớ i thi ệ u v ề thu ậ t toán.
- Sơ đồ chung thu ật toán đàn kiế n.
- Các bƣớc giải quyết bài toán đàn kiến.
- Các sơ đồ thu ậ t toán khác phát tri ể n trên mô hình ACO.
- Thu ậ t toán Ant System (AS.
- Thu ậ t toán Ant Colony System (ACS.
- Thu ậ t toán Max – Min Ant System(MMAS.
- Thu ậ t toán Rank-Based Ant System (RBAS.
- Thu ậ t toán Best-Worst Ant System(BWAS.
- Thu ật toán đàn kiế n song song.
- 19 CHƢƠNG III: MỘ T S Ố Ứ NG D Ụ NG V Ề THU Ậ T TOÁN.
- Ứ ng d ụ ng thu ậ t toán ACO.
- 22 Thu ật toán đàn kiế n ĐH HTTT – K5 2 CHƢƠNG I: SƠ LƢỢ C V Ề BÀI TOÁN ĐÀN KI Ế N 1.
- Đàn kiến tự nhiên (natural ant colonies) Loài ki ế n là loài sâu b ọ có tính ch ấ t xã h ộ i, chúng s ố ng thành t ừng đàn, bở i v ậ ycó s ự tác độ ng l ẫ n nhau, chúng th ạ o tìm ki ế m th ức ăn và hoàn thành nhữ ng nhi ệ m v ụ t ừ ki ế n ch ỉ huy.
- M ột điề u thú v ị trong tìm ki ế m th ức ăn củ a vài con ki ến đặ c bi ệ t làkh ả năng của chúng để tìm ki ếm đƣờng đi ngắ n nh ấ t gi ữ a t ổ ki ế n và ngu ồ n th ức ăn.
- Trên th ự c t ế, điề u d ễ nh ậ n th ấy có trong suy nghĩ nhƣng nhiề u con ki ế n h ầ u h ế t khôngnh ậ n ra vì chúng không dùng th ị giác để tìm ki ế m nh ững đầ u m ố i th ức ăn.
- T ấ t c ả m ọ i con ki ế n h ầu nhƣ là mù, chúng chỉ có th ể tƣơng tác vớ i nhau và v ớ i môi trƣờ ng b ằ ng cách s ử d ụng pheromone: đi đến đâu chúng xịt pheromone ra đế n đấ y.
- M ỗ i m ộ t con ki ế n t ạ i m ỗ i v ị trí quy ết định hƣớng đi tiế p theo d ự a vào n ồ ng độ pheromone c ủa các hƣớ ng.
- C ứ nhƣ vậ y thì các con ki ế n c ứ đi theo bƣớ c chân c ủ a nhau và t ạ o thành m ộ t đƣờng đi (path).
- Ta xét trƣờ ng h ợ p t ổ ki ế n ở v ị trí 1 và ngu ồ n th ức ăn ở v ị trí 2 nhƣ hình v ẽ Gi ả s ử t ạ i th ời điểm ban đầ u có 2 con ki ến ra đi tìm thức ăn.
- M ột hƣớ ng có đƣờng đi đế n ngu ồ n th ức ăn dài hơn hƣớng kia.
- Trong giai đoạn đầ u các con ki ến đi sau s ẽ c ả m nh ậ n th ấ y n ồng độ pheromone c ủ a c ả 2 hƣớng là nhƣ nhau nên cũng chọ n đi theo một trong 2 hƣớ ng m ộ t cách ng ẫu nhiên.
- Tuy nhiên đƣờng đi ngắn hơn làm cho kho ả ng th ờ i gian di chuy ể n t ừ t ổ đế n ngu ồ n th ức ăn rồ i quay tr ở l ạ i c ủ a m ỗ i con ki ế n theo con đƣờng đó cũn g ng ắn hơn và do đó mật độ di chuy ể n qua l ạ i c ủa đàn kiế n t ạ i Thu ật toán đàn kiế n ĐH HTTT – K5 3 m ỗ i v ị trí c ủa con đƣờ ng ng ắ n s ẽ cao hơn con đƣờ ng dài.
- pheromone trên con đƣờ ng ng ắn càng ngày càng cao hơncon đƣờ ng dài.
- K ế t qu ả cu ố i cùng là đàn kiế n ngày càng t ừ b ỏ con đƣờng dài và đitheo con dƣờ ng ng ắn.
- Đế n m ột lúc nào đó sẽ không còn con ki ến nào đi theo conđƣờ ng dài n ữ a mà t ấ t c ả đều đi theo con đƣờ ng ng ắ n.Thu ậ t toán d ự a trên ho ạt độ ng c ủa đàn kiế n có m ộ t s ố bi ế n th ể .
- Thu ậ t toán này ch ỉ dùng để gi ả i quy ế t bài toán tìm đƣờ ng.
- Ở m ức cao hơn là thuậ t toán ACO (Ant Colony Optimization).
- Từ những con kiến tự nhiên tới thuật toán ACO Thu ậ t toán ACO l ấy ý tƣở ng t ừ vi ệ c ki ế m th ức ăn của đàn kiế n ngoài th ự c t ế để gi ả i quy ế t các bài toán t ối ƣu tổ h ợ p.
- Chúng d ựa trên cơ sở m ột đàn kiế n nhân t ạ o, chúng đƣợ c tính toán tìm ki ế m th ức ăn nhờ mùi l ạ nhân t ạ o.C ấu trúc cơ bả n c ủ a thu ậ t toán ACO: trong m ỗ i thu ậ t toán, t ấ t c ả ki ến đi xây d ự ng cách gi ả i quy ế t bài toán b ằ ng cách xây d ự ng m ột đồ th ị .
- M ỗ i c ạ nh c ủa đồ th ị miêu t ả các bƣớ c ki ế n có th ể đi đƣợ c k ế t h ợ p t ừ hai lo ại thông tin hƣớ ng d ẫ n ki ế n dichuy ể n: Thu ật toán đàn kiế n ĐH HTTT – K5 4 Thông tin kinh nghi ệ m (heuristic information): gi ớ i h ạ n kinh nghi ệm ƣu tiên di chuy ể n t ừ nút r t ới s…củ a c ạ nh a rs .
- Thông tin này không đƣợc thay đổ i b ở i ki ế n trong su ố t quá trình ch ạ y thu ậ t toán.Thông tin mùi l ạ nhân t ạ o (artificial pheromone trail information), nó gi ớ i h ạ n “nghiên cứ u s ự thèm mu ốn” củ a chuy ển độ ng là ki ế n nhân t ạ o và b ắt chƣớ c mùi l ạ th ự c t ế c ủa đàn kiế n t ự nhiên.
- Thông tin này b ị thay đổ i trong su ố t quá trình thu ậ t toánch ạ y ph ụ thu ộ c vào cách gi ả i quy ết đƣợ c tìm th ấ y b ở i nh ữ ng con ki ến.
- Nó đƣợc đánh d ấ u b ở i  rs .Gi ớ i thi ệu các bƣớ c ảnh hƣở ng t ừ nh ữ ng con ki ế n th ậ t vào ACO.
- Có hai v ấn đề c ầ n chú ý:- Chúng tr ừu tƣợ ng hoá vài mô hình th ức ăn củ a ki ế n ngoài th ự c t ế để tìm ra đƣờ ng đi tìm kiế m th ức ăn ngắ n nh ấ t.- Chúng bao g ồm vài đặc điể m không gi ố ng v ớ i t ự nhiên nhƣng lạ i cho phépthu ậ t toán phát tri ể n ch ứa đự ng cách gi ả i quy ế t t ố t t ớ i bài toán b ị c ả n (ví d ụ : s ử d ụ ngthông tin kinh nghi ệm để hƣớ ng d ẫ n chuy ển độ ng c ủ a ki ế n).Cách th ứ c ho ạt động cơ bả n c ủ a m ộ t thu ật toán ACO nhƣ sau: m kiế n nhân t ạ odi chuy ến, đồ ng th ời và không đồ ng b ộ , qua các tr ạ ng thái li ề n k ề c ủ a bài toán.
- S ự dichuy ể n này theo m ộ t t ậ p quy t ắc làm cơ sở t ừ nh ữ ng vùng thông tin có s ẵ n ở các thành ph ầ n (các nút).
- Vùng thông tin này bao g ồ m thông tin kinh nghi ệ m và thông tin mùi l ạ để hƣớ ng d ẫ n tìm ki ế m.
- Nh ữ ng con ki ế n s ẽ gi ả i phóng mùi l ạ ở m ỗ i l ần chúng đi qua mộ t c ạ nh (k ế t n ố i)trong khi xây d ự ng cách gi ả i quy ế t (c ậ p nh ậ t t ừng bƣớ c mùi l ạ tr ự c tuy ế n).
- M ỗ i l ầ nnh ữ ng con ki ế n sinh ra cách gi ả i quy ết, nó đƣợc đánh giá và nó có thể t ạ o lu ồ ng mùi l ạ là ho ạt độ ng c ủ a ch ất lƣợ ng c ủ a cách gi ả i quy ế t c ủ a ki ế n (c ậ p nh ậ t l ạ i mùi l ạ tr ự ctuy ế n).
- Thông tin này s ẽ hƣớ ng d ẫ n tìm ki ế m cho nh ữ ng con ki ến đi sau.
- Hơn thế n ữ a, cách th ứ c sinh ho ạt độ ng c ủ a thu ậ t toán ACO bao g ồ m thêm haith ủ t ụ c, s ự.
- bay hơi củ a mùi l ạ đƣợ c kh ở i s ự t ừ môi t rƣờng và nó đƣợ c s ử d ụng nhƣ là m ột kĩ thuật để tránh tìm ki ế m b ị d ừ ng l ạ i và cho phép ki ế n kh ả o sát vùng không gian Thu ật toán đàn kiế n ĐH HTTT – K5 5 m ớ i.
- Daemon actions là nh ữ ng ho ạt độ ng t ối ƣu nhƣ mộ t b ả n sao t ự nhiên để th ự c hi ệ nnh ữ ng nhi ệ m v ụ t ừ m ộ t m ụ c tiêu xa t ớ i vùng c ủ a ki ế n.
- CHƢƠNG II: XÂY DỰ NG THU ẬT TOÁN ĐÀN KIẾ N 1.
- Gi ớ i thi ệ u v ề thu ậ t toán 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ạitrê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ềukiến cùng đi qua.
- 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.
- Trên đƣờng ngắn hơn thì nhiều mùi (pheromone) hơn Thu ật toán đàn kiế n ĐH HTTT – K5 12 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.
- 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- Quantity: Thì đàn kiến sẽ đặt thêm pheromone trong quá trình xây dựnglờ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).
- Quy tắc di chuyển của kiến Trong thu ậ t toán AS, ki ế n xây d ự ng m ột đƣờng đi bắt đầ u t ạ i m ột đỉnh đƣợ cch ọ n ng ẫ u nhiên.T ại đỉ nh i, m ộ t con ki ế n k s ẽ ch ọn đỉnh j chƣa đƣợc đi qua trong tậ p láng gi ề ngc ủ a i theo công th ứ c sau: Trong đó: Thu ật toán đàn kiế n ĐH HTTT – K5 13 S ự l ự a ch ọ n c ủ a con khi quy ết định đi từ đỉnh i qua đỉnh j và đƣợ c tính theocông th ứ c.
- Quy t ắ c c ậ p nh ậ t thông tin mùi Trong quá trình di chuy ển tìm đƣờng đi của đàn kiế n, chúng th ự c hi ệ n c ậ p nh ậ tthông tin mùi trên nh ững đoạn đƣờng mà chúng đã đi qua.
- Gắ n v ớ i m ỗ i c ạ nh (i,j) n ồ ng độ v ế t mùi  ij và thông s ố heuristic  ij trên c ạnh đó.
- Đầ u tiên t ấ t c ả pheromone trên các cung s ẽ đƣợ c gi ả m đi bở i m ột lƣợ ng: Thu ật toán đàn kiế n ĐH HTTT – K5 14 V ớ i p trong kho ả ng (0,1) là t ốc độ.
- Ti ế p theo m ỗ i con ki ến trong đàn sẽ đặ t thêm m ột lƣợ ng thông tin pheromone trên nh ững cung mà chúng đã đi qua trong hành trình củ a chúng.
- Trong đó: deta  ij là lƣợ ng pheromone mà con ki ến k đặ t lên c ạnh mà nó đã điqua và đƣợc tính nhƣ sau: V ớ i: C k là độ dài đƣờng đi củ a con ki ế n th ứ k sau khi hoàn thành đƣờng đi, tứ clà b ằ ng t ổ ng các cung thu ộc đƣờng đi mà kiến đã đi qua.
- Thuật toán Ant Colony System (ACS) Phát triển từ thuật toán AS  Quy t ắ c di chuy ể n c ủ a ki ế n Trong thu ậ t toán ACS, con ki ến k đang ở.
- đỉ nh i, vi ệ c ki ế n ch ọn đỉnh j để dichuy ển đến đƣợc xác đị nh b ằ ng quy lu ật nhƣ sau.
- Cho q o là m ộ t h ằ ng s ố cho trƣớ c (0q 0 ki ế n k s ẽ ch ọn đỉnh u chƣa đƣợc đi qua trong tậ p láng gi ề ng c ủ a r theo công th ứ c sau:- Ch ọn đỉnh u là đỉ nh ti ế p theo, b ổ sung đỉ nh u vào S k S k :={r,u} Thu ật toán đàn kiế n ĐH HTTT – K5 25 - Tăng độ dài đƣờng đi C k :=C k +d ru - Gán a k u :=true Bước 3: Xác định đường đi ngắ n nh ấ t Ta có C k là độ dài đƣờng đi củ a con ki ế n k v ới k=[1..m] thu đƣợ c t ừ

Xem thử không khả dụng, vui lòng xem tại trang nguồn
hoặc xem Tóm tắt