遗传算法入门学习笔记
首先，我觉得学习一个算法必须要了解其理论依据，而后研究其代码，再研究其以往的案例，这样才会对一个算法有个全面的了解。当然学习领悟一个算法并不是一天两天的事，所以路漫漫兮~~~
遗传算法
第一步：简单介绍一下遗传算法的起源。
这个遗传算法官方上说是有Holland教授和他的学生创造出来的（是第一个全面具体以论文形式介绍遗传算的），遗传算法（Genetic Algorithm,简称GA），起源于对生物系统所进行的计算机模拟研究，是一种借鉴生物界自然选择和自然遗传机制的随机搜索方法。
遗传算法是模仿自然界生物进化机制发展起来的随机全局搜索和优化方法，借鉴了伟大的达尔文先生的进化论和孟德尔的遗传学说。以“适者生存”为原则，以N代遗传而产生一个近似最优的方案。
遗传算法是一种概率搜索算法，其仿照生物进化原则来寻求问题的最优解，并具有全局优化性能。其操作简单，可以在较短的时间内达到预期的收敛效果，遗传算法主要以选择，交叉，变异等操作实现。
第二步：遗传算法主要思想
Holland及其学生Bagley把遗传算法看作一个生态系统，遗传算法内部均可相互竞争、互相交配、一代一代地繁衍，朝向最优解的方向不断演化。
根据生物学中复制、杂交、繁殖、变异、竞争、以及选择等进化现象。Holland和J.D.Bagloy将其融入算法之中。遗传算法中每一个生物体对应一个个体。生物学中存在着适者生存的特性，在遗传算法中用适应函数来进行选择，而适应函数可以计算出个体对环境的适应程度。个体组成群体，对所有个体进行选择、交叉、变异等操作，生成新的群体，称为新一代。
算法首先初始化种群部分并选择编码方案，同时选择合适的参数，确定适应函数F(Xi)。根据以上步骤，形成一个初始群体（含M个个体）；然后对该群体中的每一个个体计算适应度，然后通过适应度的比较，进行选择，交叉，变异这三个过程，实现进化的迭代。每一次迭代都需要判定算法是否满足停止条件，如若满足，则输出当前的解，否则继续进行迭代。则对遗传算法来说，核心部分就是交叉、选择、变异。
遗传算法主要操作
（一） 选择
选择操作是选择当前种群中具有优良特性的染色体来遗传给下一代。其中最常用的一种选择方法就是“比例选择”。算法通过判定适应度来实现选择，适应度大的有更大的机会遗传给下一代，适应度小的则被淘汰。计算出每一个体被选中的相应概率后， 由于染色体的适应度越大其被选中的概率也就越大，所以适应度对选择的概率起到决定作用，选择过程起到保留优秀的淘汰没有优势的作用。
（二） 交叉
交叉运算是将互相匹配的染色体以某种方式互换基因序列其中的一部分，且是一种以一定概率的形式来交换部分染色体的运算。遗传算法中产生新的个体主要使用的就是此算法，它对整个遗传算法的全局搜索能力的影响是决定性的。交叉首先对群体内所有染色体进行随机配对，然后对配对成功的染色体在进行交换之前以某一概率选定交换的位置，最后对配对成功的染色体进行基因的交换。交叉使染色体能够交换信息，并结合选择规律，从而保留出色的信息并放弃不良信息。
（三） 变异
变异过程是染色体中的某一位基因发生了改变，由于基因决定生物的性状，所以基因的改变造成了表现型的变化，从而产生新的个体，如果新的个体数量到达M，就形成一个新的群体，则执行算法中计算个体适应度的操作，否则执行遗传操作。直至找到适应值最大的个体为止。变异是基因中某个位置的突变，以实现产生显着差异的新品种。通过这种方法可以避免不断的向好的方向选择而导致陷入局部最优的缺点。
遗传算法流程图
遗传算法优缺点
遗传算法模拟生物进化法则，通过选择和交叉变异三种方法实现优化，能够一定程度上克服局部优化，达到全局优化。该算法结构简单，具有很强的可扩展性，容易与其他算法结合。
由于算法是以群体的角度进行搜索寻优，所以可以同时与多个个体同时比较，方便转为分布式计算，容易提高求解速度。
遗传算法中选择、交叉、变异算子需要很多参数，这些参数设置的好坏严重影响解的品质，但该算法的各个参数设置没有具体规范，只能凭借经验。
另外遗传算法着重于全局，对种群的每一个个体都要计算，导致算法的搜索速度较慢，需要耗费大量时间才有可能得到近似最优解。针对大规模问题计算时，由于参数不能够很好的设置，特别是在适应函数选择不当的情况，以及实现选择、交叉、变异的算子不合适，特别容易进入局部最优，从而导致不能够达到全局最优的问题。
第三步：案例
案例使用一种简单的集成电路布局进行证明。本报告是使用标准单元方式建立的一种虚拟的简易布局模型进行布局说明。由于电子器件的大小以及端口位置等对算法整体没有太大的影响，并且本报告着重于算法的优化性能。故仅看作是单元间彼此进行交换的优化组合问题，如图所示布局模型简易图，不考虑元件大小和端口位置的N*N的简单Netlist。该布局网表内部的每个单元（cell，实现特定逻辑的模块）均具有四个端口与其他单元连接（net，单元间的连接关系）。
电路的初始化状态图：
上图是一定规模下的初始化状态图。
下图是优化后的状态图。
对比一下，遗传算法的优化效果很可观。
现在遗传算法已经被用于各行各业，也已被慢慢改进。