遗传算法的基本概念

遗传算法(genetic algorithm, GA)是模拟自然界生物进化机制的一种算法，遵循适者生存、优胜劣汰的法则。

遗传算法的作用对象是种群(Population)，种群中的每个个体是问题的一个解，叫做染色体(Chromosome)。染色体按照一定的编码（比如二进制编码）来表示一个解。染色体中的元素叫做基因(Gene)。遗传算法对种群施加选择(Selection)、交叉(Crossover)和变异(Mutation)等操作，使个体和种群的适应度(Fitness)不断改进，从而达到趋向最优的目的。

遗传算法过程图如下图。

常见的编码策略有二进制编码、格雷编码、实数编码、符号编码等。编码通常需遵循三个原则：完备性、健全性和非冗余性。

选择算子的任务就是从父代中选出一部分个体遗传到下一代。选择操作建立在种群个体的适应度评估基础上，常见的选择方法有轮盘赌算法、适应度比例方法、随机遍历抽样法和局部选择法。

交叉算子的作用是生物遗传基因的重组。常用的交叉方法有实值重组和二进制交叉。

变异算子的任务是对群体中的染色体的某些基因做变动。变异操作的主要目的有两个：一是使遗传算法具有局部的随机搜索能力，这种情况下变异概率应该取较小值；二是使遗传算法维持群体多样性，以避免早熟的现象，这种情况下变异概率应该取较大值。

遗传算法的特点是：

1. 从串级开始搜索，对空间中多个解进行评估，覆盖面大，利于寻找全局最优。
2. 基本上不用搜索空间的知识和其他辅助信息，仅用适应度值评估个体，适应度函数不受连续可微的约束，定义域可以任意设定。
3. 采用概率的变迁确定搜索方向。 具有自组织、自适应和自学习性。