遗传算法：组合优化算法，按照进化论的方式启发搜索寻优解
遗传算法源于美国密歇根大学 Holland 教授在六七十年代的研究成果，其设计灵感源自达尔文的进化论观点。该算法并非采用穷举搜索策略，而是通过模拟群体基因的交换与变异，依照适者生存的原理逐代迭代，以探寻最优解决方案。这种方法在处理组合优化问题时，对于应对解空间急剧膨胀的挑战尤为有效。
人类进化图
一、如何理解遗传算法
可以如此比喻遗传算法开yun体育app官网网页登录入口，设想必须寻觅一个最能抵御严寒的人种，那么遗传算法的运作方式如下：先设定一个较寒冷的生存环境（代表问题的约束条件），随后向其中投放一群形态各异的人（构成初始种群），让他们在这样酷寒的条件下求存。人类世世代代生存，外部条件逐渐变得严酷，并且个体繁衍过程中存在基因重组与突变现象，这类似于算法的逐步优化。基因重组和变异逐渐形成少数能抵御严寒的遗传特征，拥有这种特征的人更能适应环境得以繁衍，逐渐地能够承受严寒的人类得以存活，不适应当下环境者被自然选择淘汰，这就是解空间逐渐向最优状态演化的过程，遗传算法正是效仿了这一机制。
遗传算法不难明白，不过有必要提一下，它是一种优化途径，一种计算思路，因此针对不同情形，遗传算法都要进行专门的规划。
二、遗传算法
遗传算法基于进化理念，运作过程包含四个环节，分别是符号化、优中选优、组合基因和基因突变。
2.1编码
遗传算法首要处理的是编码环节，这涉及基因向表现型的转化，本质是模拟基因的运作方式。例如，如果双眼皮或单眼皮由特定基因片段决定，那么该基因片段就形成了眼皮这一特征的表现。编码的核心在于建立基因与表现型之间的对应关系，常见的编码方式包括二进制编码、整数编码以及浮点数编码，每种方式都有其独特的优势。
二进制编码用0和1的序列来象征基因，假如011011里每两个0或1的序列象征一个性状，那么性状就是1，2，3，假如用来处理旅行商问题，就象征挑选1经过2再到达3这条路线。
二进制编码
二进制编码操作便捷，便于实现基因的交换与突变kaiyun.ccm，然而，这种编码方式容易导致信息冗余，并且在交换与突变时可能生成不可靠的新数据，从而使得搜索过程难以稳定聚焦。
基因以整数形式编码时，其表达结果与基因本身相同，在旅行商问题中，基因序列1,2,3所对应的表达就是1,2,3，这表示从1到2再到3的路径顺序，因此整数编码方式特别适合解决旅行商问题，不过，在基因交换环节容易造成路径中节点出现重复现象，而浮点数编码通常用于处理浮点数相关课题，应用相对较少
2.2选择
挑选具备优良环境适应性的生物，这相当于算法挑选更符合优化标准的答案，并让这些优秀解在下一代中传承，从而指导搜索方向。环境适应性与优化目标直接相关kaiyun官方网站登录入口，条件越优越，适应力越强。针对旅行商问题，优化目标就是追求路线最短，具体表现为：
寻找距离X的最小值，等同于寻找距离X倒数的最大值
把适应函数定义为：f(X)=1/distance(X)，其中X表示一条路径。对于适应度函数，当f(X)数值越高，代表适应度越好，同时distance(X)值也会越小，这是我们希望达到的效果。
挑选时，期望个体具备较强的环境适应力，从而扩大选择范围，通常借助轮盘赌方法，依据适应能力差异，按比例决定后代的选取。轮盘赌法要求计算出相应的概率分布。
轮盘赌的方式
轮盘赌的操作步骤是这样的：一旦需要做出抉择，就会随机生成一个数值，比如这个数值是0.4，如果它落在个体1和个体2累积概率的范围之内，那么个体2就会成为被挑选的对象。这种轮盘赌的方法能够依据各个个体的适应程度来挑选下一代。
轮盘赌
轮盘赌中，适应度高，对应的选择的面积大，被选中的概率高。
2.3交叉和变异
模拟生物基因活动可以通过交叉和变异实现，这是新物种形成的过程，在算法层面体现为从局部最优解转向其他解空间的搜索策略。交叉涉及两条染色体的部分片段相互交换，变异则是指染色体上的基因发生改变，从而调整原有构造。
当运用二进制形式编码的基因实施重组时，具体表现为表格内端点基因中加粗片段的基因序列进行互换，与此同时，两端基因所呈现的性状也会随之改变。
基因发生交叉
运用整型表示的基因实施重组时，必须判断是否要借助转换消除重复现象
映射去重
如果基因以二进制形式编码并发生变异，那么基因序列中某个0转变为1，或者某个1转变为0，其外在形态也会随之改变。
基因发生变异
三、解决什么问题
日常生活中经常会碰到NP难题，特别是组合优化类问题，组合数量增长会导致解的搜索空间呈指数级扩大。由于无法在规定时间内找到问题的最佳答案，因此需要借助启发式搜索技术来寻求较优解，有时也能获得最佳解，并且要在可接受的时间限制之内完成。遗传算法十分有用，能够处理组合优化类课题，诸如课程安排、生产安排制定、旅行商课题等。
本文的版权归算法卡农所有，抄袭等侵权行为必究！
喜欢我的话，加个关注吧，有更加精彩的内容等着大家。
