演化式計算 (Evolutionary Computation) | |
|
"But Natural Selection, as we shall hereafter see, is a power incessantly ready for action, and is as immeasurably superior to man's feeble efforts, as the works of Nature are to those of Art." --- C. Darwin, Origins of Species "Mimicking nature for problem solving" --- IEEE, Computational Intelligence Society
|
 |
| Evolutionary Computation |
|
演化式計算為人工智慧研究領域之一，其中的方法統稱為演化式演算法 (Evolutionary Algorithms): 包含 Genetic Algorithm (GA, 基因演算法)、Evolutionary Strategy (ES, 演化式策略)、Genetic Programming (GP)、Particle Swarm Optimization (PSO) 等等。這類演算法以模仿自然界的演化機制來解決一些複雜的問題，例如搜尋與最佳化問題。演化式演算法的"隨機性質"以及"仿效自然"的作法有別於傳統的演算法，並為其帶來強大的解題能力以及許多演算法上設計上的可能性。目前演化式演算法已廣泛用於機器學習、數值與組合最佳化、多目標最佳化、生物資訊、以及工程設計等問題上。 |
| Genetic Algorithm (GA) |
|
基因演算法 (GA) 為最著名也最廣為使用的演化式演算法。基因演算法完全承襲了演化式計算的原則: 模仿自然界的演化機制，其中包含了選拔 (selection)、交換 (crossover，或稱之為重組 recombination)、突變 (mutation)。基於達爾文的"適者生存"理論，基因演算法被認為能在電腦世界"演化"出一個問題的最佳解。 基因演算法的程序如下:
GAs encode candidate solutions as chromosomes. The way of encoding chromosomes is referred to as representation, which is essentially related to the problem to be solved. For example, bit strings are widely used in functional optimization problems while orders (sequences) are used in combinatorial problems. Depending on representation, GAs can be classified into three genres: binary-coded GAs, real-coded GAs, and order-based GAs. Instead of a single chromosome, GAs evolve with a set of chromosomes, called the population. The fitness function is devised to evaluate the quality (fitness) of candidate solutions (chromosomes). Intuitively, for a maximization problem, the better the solution, the higher the fitness. The evolution of GAs begins with initialization of the population. Afterwards, GAs embark on the process of reproduction. First, the selection operator picks two chromosomes from the population to serve as parents. Next, GAs perform crossover on these two parents to reproduce their offspring. The predetermined probability, crossover rate, defines the probability to perform crossover. Analogously, mutation is performed with a probability, mutation rate, on the offspring reproduced by crossover to slightly alter some genes. This process of reproduction repeats until the set of offspring, called the subpopulation, is filled. Acting on "Survival of the Fittest", the survivor operator draws the fittest chromosomes out of the subpopulation with (or without) the primitive population; the chosen chromosomes will constitute the population for the next generation. Following this procedure, GAs evolve until a predetermined termination criterion is met. |
| GA demonstration |
|
以下為一些基因演算法的 Java applet 範例: |
