遗传算法

概述

启发式算法，或称策略法、助发现法、启发力、捷思法等。是一种实用的解决问题的方法，该种方法不能保证是最佳的、完美的或理性的，但仍然足以达到立即的、短期的目标或近似值。特别是在不可能找到最佳解决方案或不切实际的情况下，可以使用启发式方法来加快找到满意解决方案的过程。该方法可以是减轻决策过程认知负荷的心理快捷方式。

启发式算法解释了在知识有限（信息不完整）和时间有限的情况下，得出可能陈述或可行解决方案的艺术。它描述了一种分析程序，在该程序中，在对系统了解有限的情况下，在推定结论的帮助下做出有关系统的陈述。 由此得出的结论往往偏离最优解。启发法的质量可以透过将其与最佳解决方案进行比较来确定。

启发式算法的特点：
计算机科学的两大基础目标，就是发现可证明其执行效率良好且可得最佳解或次佳解的算法。而启发式算法则试图一次提供一个或全部目标。例如它常能发现很不错的解，但也没办法证明它不会得到较坏的解；它通常可在合理时间解出答案，但也没办法知道它是否每次都可以这样的速度求解。

有时候人们会发现在某些特殊情况下，启发式算法会得到很坏的答案或效率极差，然而造成那些特殊情况的数据结构，也许永远不会在现实世界出现。因此现实世界中启发式算法很常用来解决问题。启发式算法处理许多实际问题时通常可以在合理时间内得到不错的答案（但并不保证一定是最优解）。

TSP问题

TSP问题被归类为NP-hard问题，因为它满足NP-hard的定义：任何NP问题都可以在多项式时间内归约到它。
对于TSP问题的NP-hard性质的证明，通常是通过从一个已知的NP-complete问题（如哈密顿回路问题）进行归约来完成的。

// 可能有其他概念问题要考

遗传算法

概述

遗传算法是一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法。

各个概念对应到遗传算法中：

主要特征

• 进化：进化体现在解的编码上，也就是生物学中的染色体，将问题的解通过某种方式进行编码（例如二进制编码），各种问题都在编码上进行。另一方面，如何编码也是遗传算法的一个主题。
• 适应函数：根据自然选择规律来决定哪些染色体能产生超过平均数的后代。根据实际优化问题的目标来人为地构造适应函数来计算每个个体（解或染色体）的适应度，适应度更好的染色体将产生超过平均数的后代。
• 交配：当染色体结合时，双亲的遗传基因的结合使得子女保持父母的特征。
• 变异：当染色体结合后，随机的变异会造成子代同父代的不同。

主要步骤

基本遗传算法

基本遗传算法（SGA，又称简单遗传算法或标准遗传算法），是由Goldberg总结出的一种最基本的遗传算法，其遗传进化操作过程简单，容易理解，是其它一些遗传算法的雏形和基础。

主要构成：

• 编码：产生初始种群
• 适应度函数：计算个体的适应度
• 遗传算子：模拟生物学上的行为（选择、交叉、变异）
• 运行参数

编码与初始种群

GA算法通过某种编码机制把对象抽象为由特定符号按一定顺序排成的串，例如SGA使用二进制串进行编码。

SGA采用随机方法生成若干个个体的集合，该集合称为初始种群。初始种群中个体的数量称为种群规模。

适应度函数

遗传算法对一个个体（解）的好坏用适应度函数值来评价。

适应度函数值越大，解的质量越好。适应度函数是遗传算法进化过程的驱动力，也是进行自然选择的唯一标准，它的设计应结合求解问题本身的要求而定。

选择算子

遗传算法使用选择运算来实现对群体中的个体进行优胜劣汰操作：适应度高的个体被遗传到下一代群体中的概率大；而适应度低的个体，被遗传到下一代群体中的概率小。
选择操作的任务就是按某种方法从父代群体中选取一些个体，遗传到下一代群体。SGA中选择算子采用轮盘赌选择方法。

轮盘赌选择又称比例选择算子，其基本思想是：各个个体被选中的概率与其适应度函数值大小成正比。
设群体大小为$n$，个体$i$的适应度为$F_i$，则个体$i$被选中遗传到下一代群体的概率为：

然后根据各个概率，就对应一个“饼状图”，也就是所谓的“轮盘”。
接下来，进行对每一个个体的选择。随机生成[0,1]之间的随机数，来从饼状图中进行匹配（相当于一个轮盘指针），选中的个体将会被遗传下去。

交叉算子

其实就相当于生物学中，精子和卵子之间的基因重组。
在SGA中，使用单点交叉算子：

变异算子

SGA中使用基本位变异算子，即将编码串中的某一位或某几位基因取反。

运行参数

运行参数用于在算法运行时指定一些基本的参数，例如各种概率。

遗传算法的特点

• 群体搜索，易于并行化处理
• 不是盲目穷举，而是启发式搜索
• 适应度函数不受连续、可微等条件的约束，适用范围很广

遗传算法的描述

遗传算法的数学基础

略。。。应该不考？

遗传算法的收敛性分析

遗传算法要实现全局收敛，首先要求任意初始种群经有限步都能到达全局最优解，其次算法必须由保优操作来防止最优解的遗失。与算法收敛性有关的因素主要包括种群规模、选择操作、交叉概率和变异概率。

种群规模对收敛性的影响

• 种群太小不能提供足够的采样点，以致算法性能很差
• 种群太大，尽管可以增加优化信息，阻止早熟收敛的发生，但无疑会增加计算量，造成收敛时间太长，表现为收敛速度缓慢

选择操作对收敛性的影响

选择操作使高适应度个体能够以更大的概率生存，从而提高了遗传算法的全局收敛性。

如果在算法中采用最优保存策略，即将父代群体中最佳个体保留下来，不参加交叉和变异操作，使之直接进入下一代，最终可使遗传算法以概率1收敛于全局最优解。

交叉概率对收敛性的影响

交叉操作实质上是在解空间中进行有效搜索。但是：

• 交叉概率太大时，种群中个体更新很快，会造成高适应度值的个体很快被破坏掉
• 交叉概率太小时，交叉操作很少进行，从而会使搜索停滞不前，造成算法的不收敛

变异概率对收敛性的影响

变异操作是对种群模式的扰动，有利于增加种群的多样性。但是：

• 变异概率太小则很难产生新模式
• 变异概率太大则会使遗传算法成为随机搜索算法

遗传算法的局限性

• GA在进化搜索过程中， 每代总要维持一定规模的群体，则：
  • 若群体规模太小，含有的信息量也少，不能使算法得到充分发挥
  • 群体规模大，包含的信息量也大，但计算次数会激剧增加，因而限制了算法的使用
• 早熟问题：即在解的搜索成熟前就已经收敛，原因有：
  • 交叉算子使群体中的染色体具有局部相似性，父代染色体的信息交换量小，从而使搜索停滞不前
  • 变异概率又太小，以至于不能使搜索转向其它的解空间进行搜索。GA的爬山能力差，也是由于变异概率低造成的

注：本文参考自课程ppt