Tối ưu bầy đàn

Phương pháp tối ưu bầy đàn

Phương pháp tối ưu bầy đàn là một trong những thuật toán xây dựng dựa trên khái niệm trí tuệ bầy đàn để tìm kiếm lời giải cho các bài toán tối ưu hóa trên một không gian tìm kiếm nào đó.

Giới thiệu

Phương pháp tối ưu bầy đàn là một dạng của các thuật toán tiến hóa quần thể đã được biết đến trước đây như thuật giải di truyền(Genetic algorithm (GA)), Thuật toán đàn kiến(Ant colony algorithm). Tuy vậy PSO khác với GA ở chỗ nó thiên về sử dụng sự tương tác giữa các cá thể trong một quần thể để khám phá không gian tìm kiếm. PSO là kết quả của sự mô hình hóa việc đàn chim bay đi tìm kiếm thức ăn cho nên nó thường được xếp vào các loại thuật toán có sử dụng trí tuệ bầy đàn. Được giới thiệu vào năm 1995 tại một hội nghị của IEEE bởi James Kennedy và kỹ sư Russell C. Eberhart. Thuật toán có nhiều ứng dụng quan trọng trong tất cả các lĩnh vực mà ở đó đòi hỏi phải giải quyết các bài toán tối ưu hóa. Để hiểu rõ thuật toán PSO hãy xem một ví dụ đơn giản về quá trình tìm kiếm thức ăn của một đàn chim. Không gian tìm kiếm thức ăn lúc này là toàn bộ không gian ba chiều mà chúng ta đang sinh sống. Tại thời điểm bắt đầu tìm kiếm cả đàn bay theo một hướng nào đó, có thể là rất ngẫu nhiên. Tuy nhiên sau một thời gian tìm kiếm một số cá thể trong đàn bắt đầu tìm ra được nơi có chứa thức ăn. Tùy theo số lượng thức ăn vừa tìm kiếm, mà cá thể gửi tín hiệu đến các các cá thể khác đang tìm kiếm ở vùng lân cận. Tín hiệu này lan truyền trên toàn quần thể. Dựa vào thông tin nhận được mỗi cá thể sẽ điều chỉnh hướng bay và vận tốc theo hướng về nơi có nhiều thức ăn nhất. Cơ chế truyền tin như vậy thường được xem như là một kiểu hình của trí tuệ bầy đàn. Cơ chế này giúp cả đàn chim tìm ra nơi có nhiều thức ăn nhất trên không gian tìm kiếm vô cùng rộng lớn.

Như vậy đàn chim đã dùng trí tuệ, kiến thức và kinh nghiệm của cả đàn để nhanh chóng tìm ra nơi chứa thức ăn. Bây giờ chúng ta tìm hiểu làm cách nào mà một mô hình trong sinh học như vậy có thể áp dụng trong tính toán và sinh ra thuật toán PSO mà ta từng nhắc đến. Việc mô hình hóa này thường được gọi là quá trình phỏng sinh học (bioinspired) mà chúng ta thường thấy trong các ngành khoa học khác. Một thuật toán được xây dựng dựa trên việc mô hình hóa các quá trình trong sinh học được gọi là thuật toán phỏng sinh học (bioinspired algorithms).

Hãy xét bài toán tối ưu của hàm số F trong không gian n chiều. Mỗi vị trí trong không gian là một điểm tọa độ n chiều. Hàm F là Hàm mục tiêu(fitness function) xác định trong không gian n chiều và nhận giá trị thực. Mục đích là tìm ra điểm cực tiểu của hàm F trong miền xác định nào đó. Ta bắt đầu xem xét sự liên hệ giữa bài toán tìm thức ăn với bài toán tìm cực tiểu của hàm theo cách như sau. Giả sử rằng số lượng thức ăn tại một vị trí tỉ lệ nghịch với giá trị của hàm F tại vị trí đó. Có nghĩa là ở một vị trí mà giá trị hàm F càng nhỏ thì số lượng thức ăn càng lớn. Việc tìm vùng chứa thức ăn nhiều nhất tương tự như việc tìm ra vùng chứa điểm cực tiểu của hàm F trên không gian tìm kiếm.

Tham khảo

  • J. Kennedy and R. C. Eberhart. Swarm Intelligence. Morgan Kaufmann. 2001
  • M. Clerc. Particle Swarm Optimization. ISTE, 2006.
  • D. N. Wilke, S. Kok, and A. A. Groenwold, Comparison of linear and classical velocity update rules in particle swarm optimization: notes on diversity, International Journal for Numerical Methods in Engineering, Vol. 70, No. 8, pp. 962–984, 2007.
  • A. Chatterjee, P. Siarry, Nonlinear inertia variation for dynamic adaptation in particle swarm optimization, Computers and Operations Research, Vol. 33, No. 3, pp. 859–871, 2006.
  • A. P. Engelbrecht. Fundamentals of Computational Swarm Intelligence. Wiley, 2005. [1]
  • D. N. Wilke. Analysis of the particle swarm optimization algorithm, Master's Dissertation, University of Pretoria, 2005. [2]
  • T. Marwala. Finite element model updating using particle swarm optimization. International Journal of Engineering Simulation, 2005, 6(2), pp. 25–30. ISSN: 1468-1137.
  • M. Clerc, and J. Kennedy, The Particle Swarm-Explosion, Stability, and Convergence in a Multidimensional Complex Space, IEEE Transactions on Evolutionary Computation, 2002, 6, 58-73
  • J. Kennedy, and R. Eberhart, Particle swarm optimization, in Proc. of the IEEE Int. Conf. on Neural Networks, Piscataway, NJ, pp. 1942–1948, 1995.

Liên kết ngoài