。

它借用了生物遗传学的观点#xff0c;通过自然选择、遗传和变异等作用机制#xff0c;实现各个个体适应性的提高。

基因型

是模拟生物在自然环境中的遗传和进化的过程而形成的自适应全局优化搜索算法。

它借用了生物遗传学的观点通过自然选择、遗传和变异等作用机制实现各个个体适应性的提高。

基因型

在自然界中通过基因型表征繁殖繁殖和突变基因型是组成染色体的一组基因的集合。

在遗传算法中每个个体都由代表基因集合的染色体构成。

例如一条染色体可以表示为二进制串其中每个位代表一个基因

(Population)

针对当前问题的候选解集合。

由于每个个体都由染色体表示因此这些种族的个体

(individuals)

在算法的每次迭代中使用适应度函数(也称为目标函数)对个体进行评估。

目标函数是用于优化的函数或试图解决的问题。

适应度得分更高的个体代表了更好的解其更有可能被选择繁殖并且其性状会在下一代中得到表现。

随着遗传算法的进行解的质量会提高适应度会增加一旦找到具有令人满意的适应度值的解终止遗传算法。

(Selection)

在计算出种群中每个个体的适应度后使用选择过程来确定种群中的哪个个体将用于繁殖并产生下一代具有较高值的个体更有可能被选中并将其遗传物质传递给下一代。

仍然有机会选择低适应度值的个体但概率较低。

这样就不会完全摒弃其遗传物质。

(Crossover)

为了创建一对新个体通常将从当前代中选择的双亲样本的部分染色体互换(交叉)以创建代表后代的两个新染色体。

此操作称为交叉或重组

(Mutation)

突变操作的目的是定期随机更新种群将新模式引入染色体并鼓励在解空间的未知区域中进行搜索。

突变可能表现为基因的随机变化。

变异是通过随机改变一个或多个染色体值来实现的。

例如翻转二进制串中的一位

遗传算法理论

构造遗传算法的理论假设——针对当前问题的最佳解是由多个要素组成的当更多此类要素组合在一起时将更接近于问题的最优解。

种群中的个体包含一些最优解所需的要素重复选择和交叉过程将个体将这些要素传达给下一代同时可能将它们与其他最优解的基本要素结合起来。

这将产生遗传压力从而引导种群中越来越多的个体包含构成最佳解决方案的要素

图式定理

表示所有这些染色体其中最左边的位置为1最右边的两个位置为01从左边数的第二个位置为

0其中

length)最远的两个固定数字之间的距离下表提供了四位二进制图式及其度量的几个示例

遗传算法的核心是循环——依次应用选择交叉和突变的遗传算子然后对个体进行重新评估——一直持续到满足停止条件为止

精英主义

尽管遗传算法群体的平均适应度通常随着世代的增加而增加但在任何时候都有可能失去当代的最佳个体。

这是由于选择、交叉和变异运算符在创建下一代的过程中改变了个体。

在许多情况下丢失是暂时的因为这些个体(或更好的个体)将在下一代中重新引入种群。

但是如果要保证最优秀的个体总是能进入下一代则可以选用精英主义策略。

这意味着在我们使用通过选择、交叉和突变创建的后代填充种群之前将前

个个体(

是预定义参数)复制到下一代。

复制后的的精英个体仍然有资格参加选择过程因此仍可以用作新个体的亲本。

Elitism

策略有时会对算法的性能产生重大的积极影响因为它避免了重新发现遗传过程中丢失的良好解决方案所需的潜在时间浪费。