遗传算法：组合优化算法，按照进化论的方式启发搜索寻优解

遗传算法源于美国密歇根大学 Holland 教授在六七十年代的研究成果，其设计灵感来自达尔文的进化论观点。该算法并非采用穷举搜索策略，而是通过模仿基因重组与变异过程，以群体迭代进化中适者生存的机制来寻求最优解。这种方法在处理组合优化问题时，对于应对解空间急剧增大的挑战具有显著优势。

人类进化图

一、如何理解遗传算法

能够生动地认识遗传算法，设想现在要找一个最能抵御严寒的人，那么遗传算法的运作方式是，首先设定一个较寒冷的环境（即问题的约束条件），接着在这个环境中投放一群形态各异的人（即初始种群），让他们在严寒条件下求生存。人类世世代代生存，所处环境逐渐变得严酷，并且每当我们繁衍子孙时，基因便发生着重组与变化，如同遗传算法的重复计算。基因重组和变异逐渐形成了少数能够抵御严寒的遗传特征，拥有这种特征的人群对环境更加适应并得以繁衍，逐渐能够承受严寒的人类得以存活，不适应当下环境的存在被自然选择淘汰，这一演变过程体现了解集逐步向最优状态靠拢的趋势，遗传算法正是对这一现象的模拟。

遗传算法容易明白，不过有必要提一下，它是一种寻求最优解的方法，一种算法思路，因此遗传算法在应对具体问题时，必须进行针对性的设计。

二、遗传算法

遗传算法依照其演化理念，将计算过程分解为四个环节，分别是符号化、拣选、组合和调整。

2.1编码

遗传算法首要处理的是编码环节，这涉及基因到性状的转化，旨在模拟基因运作方式。比如决定双眼皮或单眼皮的基因片段，就体现为眼皮这一具体特征。编码的核心在于构建基因与性状之间的对应关系开元棋官方正版下载，常见的编码方式包括二进制编码、整数编码以及浮点数编码，每种方式都有其独特的优势。

二进制编码以0和1的序列象征基因，假如011011里每两个0或1构成一个特征，那么特征便是1、2、3，若用于处理旅行商问题，则意味着选取从1到2再到3的路线。

二进制编码

二进制编码操作便捷，便于实现基因重组和突变机制，然而，这种编码方式易引发冗余现象，并且在重组与突变环节中会生成不可靠的新数据，进而造成搜索过程难以达到稳定状态。

基因采用整数编码时，其序列值与性状表现完全对应，例如在旅行商问题里，基因序列1,2,3对应的性状就是1,2,3，这表明了从1到2再到3的路径顺序。这种编码方式在处理旅行商问题时相当便捷，不过，在基因重组环节容易造成路径中节点出现重复现象。而浮点数编码则更多用于处理涉及小数的特定问题，其应用相对有限。

2.2选择

挑选出环境适应力突出的个体是选择的功能，对算法而言就是选出更符合优化标准的答案，并且在下一代中留存更多优良方案开yunapp体育官网入口下载手机版，这便是搜索过程的指引。环境适应力与优化条件是等同的，条件越优越则适应力越强。针对旅行商问题的优化标准是追求路线最短，换言之：

求距离X的最小值，等于求距离X的倒数的最大值

把适应函数定义为：f(X)=1/distance(X)，其中X表示一条路径。在适应度函数方面，若f(X)数值越高，代表适应度越好，同时distance(X)的值也越小，这正是我们希望达到的效果。

挑选时盼望，环境适应力强的个体能获得更多机会，通常借助轮盘选择法依据其适应度，按比例决定哪些后代得以繁衍，该方法要求预先计算概率分布表。

轮盘赌的方式

轮盘赌的操作步骤是这样的：一旦需要做出挑选，就会随机生成一个数值，比如这个数值是0.4，如果它落在个体1和个体2累积概率的范围之内，那么个体2就会成为被选中的对象，这种挑选方式能够依据个体适应性的好坏来决定下一代的产生比例

轮盘赌

轮盘赌中，适应度高，对应的选择的面积大，被选中的概率高。

2.3交叉和变异

基因行为的模拟可以通过交叉和变异实现，这是新物种形成的过程，在算法层面体现为从局部最优解向其他解空间探索的路径。交叉涉及两条染色体的部分片段相互交换，变异则指染色体上的基因发生改变，从而调整其原有构造。

运用二进制编码的基因进行重组时，具体表现为表中两端基因中加粗部分基因串的互换，与此同时，两端基因所呈现的性状也会随之改变。

基因发生交叉

基因运用整数编码进行交叉时，必须判断是否要借助映射来消除重复现象，确保结果的唯一性

映射去重

同样，若基因以二进制形式编码且发生变异，基因序列中某个位置上的0转变为1，或者1转变为0，那么其外在形态也会随之改变。

基因发生变异

三、解决什么问题

日常生活中时常碰到NP难题，特别是组合优化类问题开yun体育app入口登录，当组合数量增长时，其解的搜索空间会呈指数级扩大。由于无法在合理时间内找到问题的最佳答案，因此必须借助启发式搜索技术来获取近似最优解，或者在可接受的时间限制内得到令人满意的解决方案。遗传算法很有用，能够处理组合优化任务，例如：课程安排、生产安排、旅行路线等。

本文的版权归算法卡农所有，抄袭等侵权行为必究！

喜欢我的话，加个关注吧，有更加精彩的内容等着大家。