遗传算法原理、编程和应用(上课笔记)

一.遗传算法的起源和特点:

　　Genetic Algorithms是模拟达尔文的遗传选择和自然淘汰、适者生存的生物进化过程的计算模型，是由美国Michigan大学的J.Holland教授于1975年首先提出的，是搜索最优解的一种随机化的方法。

　　遗传算法模拟生物在自然环境中的遗传和进化，是一种自适应全局优化概率搜索算法。

　　主要特点: 平行性、广泛搜索和局部精化结合、不需要过程的知识、解题范围广，容易编程、没有初值问题、 容易理解。

二、基本思想:

1、遗传算法的具体思路：进化程序（Evolution Programs)
　　特点： 借用遗传学的词汇 、薄弱的理论基础 。

2、进化过程的模拟
生物进化 遗传算法
群体 　Population
基因 　 bits
染色体 Chromosome
选择或复制 Selection
交配 Crossover
突变 Mutation
适应 Fitness

3、解的表达
　　Individual=解（数字或文字）
　　 chromosome ，a set of bits
　　Chromosomes could be:
Bit strings (0101 ... 1100)
Real numbers (43.2 -33.1 ... 0.0 89.2)
Permutations of element (E11 E3 E7 ... E1 E15)
Lists of rules (R1 R2 R3 ... R22 R23)
Program elements (genetic programming)
... any data structure ...

4、过程
{
　initialize population;evaluate population;
　while TerminationCriteriaNotSatisfied
　{
　　select parents for reproduction;
　　perform recombination and mutation;
　　evaluate population;
　}
}

Exploitation、exploration
优化，自然过程高度理想化的模拟遗传算子.

三、两种编码的方法

1、两种方法
　◎经典遗传算法 二进制，改造问题
　 ◎自然表达算法 十进制，改造遗传操作

2、二进制编码
　　bits-> string
　　00110010111111
　　遗传操作：crossover, mutation
P1 (0 1 1 0 1 0 0 0) (0 1 0 0 1 0 0 0) C1
P2 (1 1 0 1 1 0 1 0) (1 1 1 1 1 0 1 0) C2

Crossover is a critical feature of genetic algorithms:
　　It greatly accelerates search early in evolution of a populationIt leads to effective combination of schemata (subsolutions on different chromosomes)
Before: (1 0 1 1 0 1 1 0)
After: (0 1 1 0 0 1 1 0)

3、十进制编码
　　用实数 a) 位操作 b) 实数操作

四、遗传算法程序
。。。