Tối ưu bầy đàn

Bách khoa toàn thư mở Wikipedia

Tối ưu bầy đàn (tiếng Anh: particle swarm optimization, viết tắt PSO) là phương pháp tạo trí tuệ nhân tạo dựa trên quá trình mô phỏng mô hình đàn chim đang tìm kiếm thức ăn, được Eberhart và Kennedy[1] giới thiệu tại hội thảo về tính toán tiến hóa của IEEE vào năm 1995. Cũng như các thuật toán tiến hóa khác, phương pháp tối ưu bầy đàn tìm kiếm điểm cực trị toàn cục của hàm số cho trước theo phương pháp xấp xỉ, không như các phương pháp chính xác trước đây như phương pháp đơn hình, cận và nhánh,...luôn cho lời giải chính xác.

Phương pháp tối ưu bầy đàn được cho là có tốc độ tìm kiếm nhanh hơn so với thuật giải tiến hóa truyền thống khác. Tuy nhiên thuật toán này thường tìm ra điểm cực trị cục bộ rất nhanh nhưng lại bị mắc kẹt ở những điểm cực trị cục bộ này.

Thuật giải di truyền dựa vào qui luật di truyền và tiến hóa trong tự nhiên, dựa trên các phép lai, chọn lọc, biến dị mà trong đó những cá thể chứa những tính trạng xấu sẽ bị đào thải, chỉ giữ lại những cá thể cá tính trạng tốt. Trong khi đó Tối ưu bầy đàn mô phỏng mô hình xã hội, mỗi thành viên trong xã hội chú ý đến hành động của các thành viên khác trong xã hội và cùng với hiểu biết, kinh nghiệm của mình để đề ra quyết định hành động trong tương lai.

Hãy tưởng tượng đến đàn chim đang tìm kiếm thức ăn, khi có một con trong đàn tìm được tín hiệu khả quan về nơi chứa nguồn thức ăn, lập tức bằng một cách nào đó thông tin này sẽ được truyền đến những con bên cạnh, nhờ đó mà cả đàn có thể nhanh chóng tìm đến nơi chứa thức ăn thực sự. ông cha ta thường bảo "Đất lành chim đậu" cũng với ý tưởng này. Trong xã hội loài người cũng vậy khi một người tìm được miền đất hứa, ngay sau đó sẽ có rất nhiều người theo gót chân anh ta.



Particle swarm optimization (PSO) is a form of swarm intelligence. Imagine a swarm of insects or a school of fish. If one sees a desirable path to go (e.g., for food, protection, etc.) the rest of the swarm will be able to follow quickly even if they are on the opposite side of the swarm. On the other hand, in order to facilitate felicitous exploration of the search space, typically one wants to have each particle to have a certain level of "craziness" or randomness in their movement, so that the movement of the swarm has a certain explorative capability: the swarm should be influenced by the rest of the swarm but also should independently explore to a certain extent. (This is a manifestation of the basic exploration-exploitation tradeoff that occurs in any search problem.)

This is modeled by particles in multidimensional space that have a position and a velocity. These particles are flying through hyperspace (i.e., \mathbb{R}^n) and have two essential reasoning capabilities: their memory of their own best position and knowledge of the swarm's best, "best" simply meaning the position with the smallest objective value. Members of a swarm communicate good positions to each other and adjust their own position and velocity based on these good positions. There are two main ways this communication is done:

  • a global best that is known to all and immediately updated when a new best position is found by any particle in the swarm
  • "neighborhood" bests where each particle only immediately communicates with a subset of the swarm about best positions

An algorithm is presented below where there is a global best rather than neighborhood bests. Neighborhood bests allow better exploration of the search space and reduce the susceptibility of PSO to falling into local minima, but slow down convergence speed. Note that neighborhoods merely slow down the proliferation of new bests, rather than creating isolated subswarms because of the overlapping of neighborhoods: to make neighborhoods of size 3, say, particle 1 would only communicate with particles 2 through 5, particle 2 with 3 through 6, and so on. But then a new best position discovered by particle 2's neighborhood would be communicated to particle 1's neighborhood at the next iteration of the PSO algorithm presented below. Smaller neighborhoods lead to slower convergence, while larger neighborhoods to faster convergence, with a global best representing a neighborhood consisting of the entire swarm.

Mục lục

[sửa] Mô tả thuật toán (đơn giản hóa)

Giả sử chúng ta cần tối ưu (tìm điểm cực tiểu) hàm số f : \mathbb{R}^m \rightarrow \mathbb{R}. Hàm số f được gọi là hàm đối tượng (objective function). Thuật toán bầy đàn được bắt đầu bằng cách khởi tạo 1 quần thể gồm N cá thể, mỗi cá thể tương ứng với một véc tơ vị trí m chiều trong không gian \mathbb{R}^m và véc tơ vận tốc m chiều cũng trong không gian đó.


Let f : \mathbb{R}^m \rightarrow \mathbb{R} be the objective function. Let there be n particles, each with associated positions \mathbf{x}_i \in \mathbb{R}^m and velocities \mathbf{v}_i \in \mathbb{R}^m, i = 1, \ldots, n. Let \hat{\mathbf{x}}_i be the current best position of each particle and let \hat{\mathbf{g}} be the global best.

  • Initialize \mathbf{x}_i and \mathbf{v}_i for all i. One common choice is to take \mathbf{x}_{ij} \in U[a_j, b_j] and \mathbf{v}_i = \mathbf{0} for all i and j = 1, \ldots, m, where aj,bj are the limits of the search domain in each dimension.
  • \hat{\mathbf{x}}_i \leftarrow \mathbf{x}_i and \hat{\mathbf{g}} \leftarrow \min_{\mathbf{x}_i} f(\mathbf{x}_i), i = 1, \ldots, n.
  • While not converged:
    • For 1 \leq i \leq n:
      • \mathbf{x}_i \leftarrow \mathbf{x}_i+\mathbf{v}_i.
      • \mathbf{v}_i \leftarrow {\omega}\mathbf{v}_i+c_1r_1(\hat{\mathbf{x}}_i-\mathbf{x}_i)+c_2r_2(\hat{\mathbf{g}}-\mathbf{x}_i).
      • If f(\mathbf{x}_i) < f(\hat{\mathbf{x}}_i), \hat{\mathbf{x}}_i \leftarrow \mathbf{x}_i.
      • If f(\mathbf{x}_i) < f(\hat{\mathbf{g}}), \hat{\mathbf{g}} \leftarrow \mathbf{x}_i.

Note the following about the above algorithm:

  • ω is an inertial constant. Good values are usually slightly less than 1.
  • c1 and c2 are constants that say how much the particle is directed towards good positions. They represent a "cognitive" and a "social" component, respectively, in that they affect how much the particle's personal best and the global best (respectively) influence its movement. Usually, we take c_1, c_2 \approx 1 but this need not be the case.
  • Finally, it is standard to have r_1, r_2 \in U[0, 1].

[sửa] Bàn thảo

By studying this algorithm, we see that we are essentially carrying out something like a discrete-time simulation where each iteration of it represents a "tic" of time. The particles "communicate" information they find about each other by updating their velocities in terms of local and global bests; when a new best is found, the particles will change their positions accordingly so that the new information is "broadcast" to the swarm. The particles are always drawn back both to their own personal best positions and also to the best position of the entire swarm. They also have stochastic exploration capability via the use of the random multipliers r1,r2. The vector, floating-point nature of the algorithm suggests that high-performance implementations could be created that take advantage of modern hardware extensions pertaining to vectorization, such as Streaming SIMD Extensions and Altivec.

Typical convergence conditions include reaching a certain number of iterations, reaching a certain fitness value, and so on.

[sửa] Tính đa dạng và khả năng thực hiện

There are a number of considerations in using PSO in practice; one might wish to clamp the velocities to a certain maximum amount, for instance. The considerable adaptability of PSO to variations and hybrids is seen as a strength over other robust evolutionary optimization mechanisms, such as genetic algorithms. For example, one common, reasonable modification is to add a probabilistic bit-flipping local search heuristic to the loop. Normally, a stochastic hill-climber risks falling into local minima, but the stochastic exploration and communication of the swarm overcomes this. Thus, PSO can be seen as a basic search "workbench" that can be adapted as needed for the problem at hand.

Note that the research literature has uncovered many heuristics and variants determined to be better with respect to convergence speed and robustness, such as clever choices of ω, ci, and ri. There are also other variants of the algorithm, such as discretized versions for searching over subsets of \mathbb{Z}^n rather than \mathbb{R}^n. In other words, the canonical PSO algorithm is not nearly as strong as various improvements which have been developed on several common function optimization benchmarks.

For an up-to-date survey and in-depth discussion of PSO along with the related paradigm of ant colony optimization, see Engelbrecht's book below.

[sửa] Áp dụng

Although a relatively new paradigm, PSO has been applied to a variety of tasks, such as the training of artificial neural networks. Very recently, PSO has been applied in combination with grammatical evolution to create a hybrid optimization paradigm called "grammatical swarms." Engelbrecht's book has a chapter on applications of PSO.

[sửa] Chú thích

  1. J. Kennedy, and R. Eberhart, Particle swarm optimization, in Proc. of the IEEE Int. Conf. on Neural Networks, Piscataway, NJ, pp. 1942–1948, 1995.]

[sửa] Xem thêm

  • Repulsive particle swarm optimization
  • Ant colony optimization
  • Swarm intelligence
  • Invasive weed optimization algorithm
  • Optimization (mathematics)
  • Differential evolution

[sửa] Tham khảo

  • M. Clerc. Particle Swarm Optimization. ISTE, 2006.
  • 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.
  • 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

[sửa] Liên kết ngoài

Ngôn ngữ khác