遗传算法的基本概念

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

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

遗传算法过程图如下图。

遗传算法流程图

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

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

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

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

遗传算法的特点是:

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

发表评论

电子邮件地址不会被公开。 必填项已用*标注