PDA

Xem phiên bản đầy đủ : Đàn kiến (Ant System ) và khoa học



Tran Xuan Sinh
26-07-2014, 09:34 AM
Bạn biết gì về đàn kiến? Chuyện về con kiến thì nhiều và ứng dụng các hoạt động của các cơ thể sống trong tự nhiên được khai thác phục vụ khoa học cũng lắm. Mô tả hoạt động sau đây đang được các nhà khoa học nghiên cứu và ứng dụng trong các trang mạng xã hội. Đó là Thuật toán đàn kiến (Ant System - AS). Chuyện là: 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, chúng dựa vào nồng độ pheromone của các hướng. Tại vị trí mà nồng độ pheromone xung quanh đều bằng nhau hoặc không có pheromone thì chúng sẽ quyết định hướng đi một cách ngẫu nhiên. Nếu ngã nào đó có nồng độ pheromone nhiều hơn thì kiến chọn đi theo ngã ấy. Đường đi càng có nhiều con kiến đi thì nồng độ pheromone càng đậm đặc. Dần dần các con kiến cùng đi trên một con đường và tạo thành một đường đi (path) ngắn nhất. Trong thuật toán con kiến, thay vì thả chất pheromone, người ta gắn vào mỗi tác nhân (agent) thao tác một thiết bị đệm (buffer) đánh dấu. Thuật toán AS này là một trong những thuật toán giải quyết bài toán "Học tăng cường (reinforcement learning)" - một ứng dụng tốt trong việc tối ưu sử dụng các trang WEB.
TXS