Bài giảng Tính toán tiến hóa - Chương 8: Ant Colony Optimization

Ant Colony Optimization (ACO) Giải thuật tối ưu hóa bầy kiến Xuất phát từ ý tưởng đàn kiến đi tìm thức ăn Giải thuật tối ưu hóa bầy kiến Giải thuật tối ưu hóa bầy ong Dựa trên phương thức đàn ong đi tìm hoa lấy mật Giải thuật tối ưu hóa bầy đàn Lịch sử: Được đề xuất năm 1995 bởi giáo sư Russell Eberhart và nhà tâm lý học James Kenedy Russell Eberhart James Kenedy Giải thuật tối ưu hóa bầy đàn Lấy ý tưởng từ việc đàn chim tìm kiếm thức ăn Ví dụ đơn giản minh họa: Tổng quan Ant Colony Optimization: Được giới thiệu bởi Marco Dorigo ở đầu những năm 1990s. Thuộc lớp các thuật toán tối ư u sử dụng Trí thông minh bầy đàn. Lấy cảm hứng từ tập tính xã hội trong việc tìm kiếm thức ăn của đàn kiến trong tự nhiên. Thuật toán dựa trên quần thể. Đối t ư ợng áp dụng: các bài toán tối ư u rời rạc (bài toán tìm đ ư ờng đi). Quá trình tìm kiếm thức ăn của đàn kiến Ban đầu, các cá thể kiến đi theo các h ư ớng ngẫu nhiên để tìm kiếm thức ăn. Nếu tìm thấy thức ăn, các cá thể kiến mang thức ăn về tổ và để lại một chất hóa học (đ ư ợc gọi là pheromone ) trên đ ư ờng quay lại của nó. Pheromone trên mỗi đ ư ờng đi giảm dần theo thời gian Đường có pheromone càng cao thì khả năng lựa chọn đi theo đường đi đó của các cá thể kiến khác càng lớn . Càng nhiều cá thể kiến tìm thấy thức ăn trên một đ ư ờng đi , thì pheromone của đ ư ờng đi đó càng cao. Quá trình tìm kiếm thức ăn của đàn kiến Đàn kiến có thể tìm đ ư ợc đ ư ờng đi ngắn nhất giữa tổ và thức ăn bằng cách nào? Đầu tiên: Các cá thể kiến đi ngẫu nhiên theo mọi h ư ớng Nếu đ ư ờng đi có khả năng dẫn tới nguồn thức ăn => Pheromone đ ư ợc rải trên đ ư ờng quay trở lại Đ ư ờng đi càng ngắn, các cá thể kiến càng quay lại tổ nhanh => Nồng độ pheromone của đ ư ờng đi đó đ ư ợc tăng c ư ờng sớm. Đ ư ờng đi càng dài=> Các cá thể kiến quay lại tổ lâu h ơ n => Nồng độ pheromone đ ư ợc cập nhật chậm và giảm dần do sự bay hơi Sau một thời gian => Các cá thể kiến chỉ đi theo một đ ư ờng đi duy nhất Giải thuật tối ư u hóa đàn kiến Giải thuật tối ư u hóa đàn kiến Quá trình xây dựng đường đi cho cá thể kiến Xét cá thể kiến . Quá trình xây dựng đường đi cho kiến như sau: Giả sử kiến đang ở nút Xác xuất đi từ đến nút là Với là pheromone trên cạnh ( i ,j) là mức độ thu hút của cạnh (i,j) là tập các nút hàng xóm của mà ch ư a đi qua và là tham số thuật toán Giải thuật tối ư u hóa đàn kiến Quá trình xây dựng đường đi cho cá thể kiến Nút , mà kiến di chuyển đến, sẽ đ ư ợc chọn theo bánh xe Roulete Quá trình tiếp tục cho đến khi kiến có thể đến đ ư ợc (lời giải hợp lệ) hoặc không thể tiếp tục (lời giải không hợp lệ) Giải thuật tối ư u hóa đàn kiến Quá trình cập nhật pheromone Pheromone trên mỗi cạnh (i,j) đ ư ợc cập nhật nh ư sau: Với là tốc độ bay hơi của các pheromone trước đó trên dường đi là tổng các pheromone mới mà các cá thể kiến để lại trên đ ường đi của chúng: Giải thuật tối ư u hóa đàn kiến Quá trình cập nhật pheromone Giá trị pheromone để lại bởi kiến trên đ ư ờng đi của nó đ ư ợc tính nh ư sau: Với là chiều dài của hành trình Q là hằng số kinh nghiệm Giải thuật tối ư u hóa đàn kiến Ý nghĩa của các tham số, thuộc tính là mức độ thu hút hay kinh nghiệm của việc lựa chọn cạnh (i,j) chỉ ra mức độ xuất hiện của cạnh (i,j) trên đường đi của các cá thể kiến Nếu : Các cạnh trên đường đi được lựa chọn tham lam theo kinh nghiệm Nếu : Ưu tiên sử dụng các cạnh có xu hướng được xuất hiện nhiều nhất trước đó ACO for TSP problem : Mong muốn đi theo các cạnh có chi phí nhỏ nhất Thêm thành phần “kiến tinh hoa”: Đánh trọng số cho pheromone của cạnh nằm trên đ ư ờng đi tốt nhất Với Tham số thuật toán: Giải quyết một bài toán bằng ACO Phải chuyển bài toán về dạng đồ thị có trọng số G(V,E,w) Định nghĩa đ ư ợc pheromone trên cạnh Xác định biểu thức Lựa chọn các toán tử cụ thể ( xây dựng đ ư ờng đi cho kiến, cập nhật pheromone) cho bài toán cần giải quyết Hiệu chỉnh các tham số thuật toán Thực nghiệm Antsim v1.1 Thanks for your attention