遗传算法的特点
1、遗传算法的处理对象既可以是优化问题原有的某些参数的代码，也可以是有待优化额某种结构对象的编码。
2、遗传算法中每次迭代的作用对象是多个可行解的集合，而非单个可行解。
3、遗传算法仅用适应度来评估个体，而无需搜索空间的其他知识或辅助信息。
4、遗传算法不是采用确定性规则，而是采用概率的变迁规则来指导它的搜索方向。
人工智能
一、简介
遗传算法（GeneticAlgorithm,GA）借鉴了生物学遗传进化的思想，模拟了种群进化过程中经历的繁殖、杂交、基因变异的自然选择和自然变异的过程。遗传算法是一种高效的进行全局搜索和优化的方法，能在‘进化’过程中自适应获得适应度最大个体，该个体即为最优化问题最优解。
遗传算法首先需要把待解决的问题进行编码，相当于生物学当中的原始染色体。不同人的染色体是不同的，因此在遗传算法中，不同的编码相当于不同的染色体，即不同的个体，这些不同的编码个体构成了一个种群。遗传算法开始时，总是随机地产生一些个体（即初始解），根据预定的目标函数对每个个体进行评价，给出了一个适应度值。根据生物学的适者生存原理，基于此适应度值，选择个体用来复制下一代。如此循环繁衍进化，直至满足目标为止。
二、基本概念
遗传算法的基本思想是从初始种群出发，采用优胜劣汰、适者生存的自然法则选择个体，并通过杂交、变异来产生新一代种群，如此逐代进化，直到满足目标为止。遗传算法所涉及到的基本概念主要有以下几个：
种群（Population）：种群是指用遗传算法求解问题时，初始给定的多个解的集合。遗传算法的求解过程是从这个子集开始的。
个体（Individual）：个体是指种群中的单个元素，它通常由一个用于描述其基本遗传结构的数据结构来表示。
染色体（Chromos）：染色体是指对个体进行编码后所得到的编码串。其中的每1位称为基因，若干个基因构成的一个有效信息段称为基因组。
适应度（Fitness）函数：适应度函数是一种用来对种群中各个个体的环境适应性进行度量的函数。
遗传操作（GeneticOperator）：遗传操作是指作用于种群而产生新的种群的操作。标准的遗传操作包括以下3种基本形式：
选择（Selection）：根据概率从种群中选择若干个个体。一般，选择过程是一种基于适应度的适者生存的过程。
交叉（Crosssover）：两个编码的某一相同位置处编码被切断，前后两串分别交叉组合形成两个新的染编码。也称基因重组或杂交；
变异（Mutation）复制时可能（很小的概率）产生某些复制差错，变异产生新的编码，表现出新的适应度。
三、遗传算法结构
四、编码方式
(1)二进制编码（Binaryencoding）
二进制编码是将原问题的结构变换为染色体的位串结构。（缺点：汉明悬崖，位数突变）
(2)格雷编码（Grayencoding）
格雷编码是对二进制编码进行变换后所得到的一种编码方法。
(3)实数编码（Realencoding）
实数编码是将每个个体的染色体都用某一范围的一个实数（浮点数）来表示，其编码长度等于该问题变量的个数。
五、适应度函数
根据目标不同适应度函数往往不同，但总结起来最优化问题最后需要达到的目标一般有两个分类，即极大化问题和极小化问题。
极大化标准的适应度函数如下：
极小化标准的适应度函数如下：
依照适应度函数计算适应度。
六、选择操作
选择（Selection）操作是指根据选择概率按某种策略从当前种群中挑选出一定数目的个体，使它们能够有更多的机会被遗传到下一代中常用的选择方法分类是比例选择和竞技选择。
1.比例选择之轮盘赌算法
轮盘赌选择法又被称为转盘赌选择法或轮盘选择法。在这种方法中，个体被选中的概率取决于该个体的相对适应度。而相对适应度的定义为：
其中，P(xi)是个体xi的相对适应度，即个体xi被选中的概率；f(xi)是个体xi的原始适应度。 轮盘赌选择算法的基本思想是：根据每个个体的选择概率P(xi)将一个圆盘分成N个扇区，其中第i个扇区的中心角为：
再设立一个移动指针，将圆盘的转动等价为指针的移动。选择时，假想转动圆盘，若静止时指针指向哪个扇区，则选择哪个扇区。
2.竞技选择之锦标赛选择
每次从种群中取出一定数量个体（放回抽样），然后选择其中最好的一个进入子代种群。重复该操作，直到新的种群规模达到原来的种群规模。
1、确定每次选择的个体数量N。（二元锦标赛选择即选择2个个体）2、从种群中随机选择N个个体(每个个体被选择的概率相同)，根据每个个体的适应度值，选择其中适应度值最好的个体进入下一代种群。3、重复步骤(2)多次（重复次数为种群的大小），直到新的种群规模达到原来的种群规模。
七、交叉操作
交叉（Crossover）操作是指按照某种方式对选择的父代个体的染色体的部分基因进行交配重组，从而形成新的个体。交叉主要分为二进制交叉和实值交叉。
1.二进制交叉
二进制交叉（BinaryValuedCrossover）是指二进制编码情况下所采用的交叉操作，它主要包括单点交叉、两点交叉、多点交叉和均匀交叉等方法。
（1）单点交叉随机选择第k位为交叉点，若采用对交叉点后面的基因进行交换的方法，但点交叉是将X中的xk+1到xn部分与Y中的yk+1到yn部分进行交叉
单点交叉例子如下：
设有两个父代的个体串A=001101和B=110010，若随机交叉点为4，则交叉后生成的两个新的个体是A’=001110 和B’=110001
（2）两点交叉随机设定第i、j位为两个交叉点（其中i
人工智能之遗传算法(GA)
人工智能之遗传算法(GA)
原创 张志荣
今天我们重点探讨一下遗传算法（GA）。 ^_^
人们一提到遗传算法（GA），就会联想到达尔文的生物进化论。遗传算法（GA）是一类借鉴生物界的进化规律演化而来的随机化搜索方法。它是由美国的J.Holland教授1975年首先提出。目前，遗传算法（GA）已成为进化计算研究的一个重要分支。
概念和定义：
遗传算法（Genetic Algorithm）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。
遗传算法（GA）是从代表问题可能潜在的解集的一个种群（population）开始，而一个种群则由经过基因（gene）编码的一定数目的个体(individual)组成。每个个体实际上是染色体(chromosome)带有特征的实体。染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现（即基因型）是某种基因组合，它决定了个体的形状的外部表现。因此，在一开始需要实现从表现型到基因型的映射即编码工作。
由于仿照基因编码的工作很复杂，往往进行简化，初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代（generation）演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度（fitness）大小选择（selection）个体，并借助于自然遗传学的遗传算子（geneticoperators）进行组合交叉（crossover）和变异（mutation），产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码（decoding），可以作为问题近似最优解。
遗传操作是模拟生物基因遗传的做法。在遗传算法中，通过编码组成初始群体后，遗传操作的任务就是对群体的个体按照它们对环境适应度(适应度评估)施加一定的操作，从而实现优胜劣汰的进化过程。从优化搜索的角度而言，遗传操作可使问题的解，一代又一代地优化，并逼近最优解。
框架与术语：
1）编码—把问题空间的参数转换成遗传空间的由基因按一定结构组成的染色体或个体的操作过程。目前的几种常用的编码技术有二进制编码，浮点数编码，字符编码，变成编码等，最常用的是二进制编码。评估编码策略有3个规范：a)完备性(completeness)；b)健全性(soundness)；c)非冗余性(nonredundancy)。
2）适应度函数—表示某一个体对环境的适应能力，也表示该个体繁殖后代的能力。遗传算法的适应度函数也叫评价函数，是用来判断群体中的个体的优劣程度的指标，它是根据所求问题的目标函数来进行评估的。遗传算法在搜索进化过程中一般不需要其他外部信息，仅用评估函数来评估个体或解的优劣，并作为以后遗传操作的依据。适应度函数设计直接影响到遗传算法的性能，因此适应度函数的设计需要满足以下条件：a）单值、连续、非负、最大化；b) 合理、一致性；c）计算量小；d）通用性强。
3）初始群体选取—初始群体中的个体是随机产生的。初始群体的设定可采取如下策略:a)根据问题固有知识，设法把握最优解所占空间在整个问题空间中的分布范围，然后，在此分布范围内设定初始群体。b)先随机生成一定数目的个体，然后从中挑出最好的个体加到初始群体中。这种过程不断迭代，直到初始群体中个体数达到了预先确定的规模。
4）染色体—又叫做基因型个体(individuals),一定数量的个体组成了群体(population),群体中个体的数量叫做群体大小。
5）基因—串中的元素，基因用于表示个体的特征。
6）基因位置—简称基因位，在算法中表示一个基因在串中的位置称为基因位置(GenePosition)。
7）特征值—在用串表示整数时，基因的特征值与二进制数的权一致。
8）选择—从群体中选择优胜的个体，淘汰劣质个体的操作。选择算子有时又称为再生算子(reproductionoperator)。选择的目的是把优化的个体(或解)直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。选择操作是建立在群体中个体的适应度评估基础上的。目前常用的选择算子有：适应度比例方法、随机遍历抽样法、局部选择法、锦标赛选择和轮盘赌选择法（最简单、最常用）等。
9）交叉—把两个父代个体的部分结构加以替换重组而生成新个体的操作。遗传算法中起核心作用的是遗传操作的交叉算子。交叉算子根据交叉率将种群中的两个个体随机地交换某些基因，能够产生新的基因组合，期望将有益基因组合在一起。通过交叉，遗传算法的搜索能力得以飞跃提高。最常用的交叉算子为单点交叉(one-pointcrossover)。
10）变异—变异算子是对群体中的个体串的某些基因座上的基因值作变动。利用变异算子的局部随机搜索能力可以加速向最优解收敛；利用变异算子可维持群体多样性，防止出现未成熟收敛现象。依据个体编码表示方法的不同，可以有：a)实值变异；b)二进制变异。变异率的选取一般受种群大小、染色体长度等因素的影响，通常选取很小的值。
11）终止条件—当最优个体的适应度达到给定的阈值，或者最优个体的适应度和群体适应度不再上升时，或者迭代次数达到预设的代数时，算法终止。
遗传操作进行的是高效有向的搜索。遗传操作包括3个基本遗传算子(geneticoperator):选择(selection)；交叉(crossover)；变异(mutation)。遗传操作的效果和3个遗传算子所取的操作概率、编码方法、群体大小、初始群体以及适应度函数的设定密切相关。3个基本遗传算子的作用：a)选择的作用：优胜劣汰，适者生存；b)交叉的作用：保证种群的稳定性，朝着最优解的方向进化；c)变异的作用：保证种群的多样性，避免交叉可能产生的局部收敛。
遗传算法中，交叉算子因其全局搜索能力而作为主要算子，变异算子因其局部搜索能力而作为辅助算子。遗传算法通过交叉和变异这对相互配合又相互竞争的操作而使其具备兼顾全局和局部的均衡搜索能力。如何有效地配合使用交叉和变异操作，是目前遗传算法的一个重要研究内容。
运算过程：
1）初始化：设置进化代数计数器t=0，设置最大进化代数T，随机生成M个个体作为初始群体P(0)。
2）个体评价：计算群体P(t)中各个个体的适应度。
3）选择运算:将选择算子作用于群体。选择的目的是把优化的个体直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。选择操作是建立在群体中个体的适应度评估基础上的。
4）交叉运算：将交叉算子作用于群体。遗传算法中交叉算子起核心作用。
5）变异运算：将变异算子作用于群体。对群体中的个体串的某些基因座上的基因值作变动。群体P(t)经过选择、交叉、变异运算之后得到下一代群体P(t+1)。
6）终止条件判断:若t=T,则以进化过程中所得到的具有最大适应度个体作为最优解输出，终止计算。
可把遗传算法的运算过程看作是一个在多元函数里面求最优解的过程。如下图所示，这个多维曲面里面有数不清的“山峰”，而这些“山峰”所对应的就是局部最优解。而其中也会有一个“山峰”的海拔最高的，那么这个就是全局最优解。而遗传算法的任务就是尽量爬到最高峰，而不是陷落在一些小山峰。
算法优点：
1）遗传算法从问题解的串集开始搜索，而不是从单个解开始。这是遗传算法与传统优化算法的极大区别。遗传算法从串集开始搜索，覆盖面大，利于全局择优。
2）遗传算法同时处理群体中的多个个体，即对搜索空间中的多个解进行评估，减少了陷入局部最优解的风险，同时算法本身易于实现并行化。
3）遗传算法不用搜索空间的知识或其它辅助信息，而仅用适应度函数值来评估个体，在此基础上进行遗传操作。适应度函数不仅不受连续可微的约束，而且其定义域可以任意设定。这一特点使得遗传算法的应用范围大大扩展。
4）遗传算法不是采用确定性规则，而是采用概率的变迁规则来指导它的搜索方向。
5）具有自组织、自适应和自学习性。遗传算法利用进化过程获得的信息自行组织搜索时，适应度大的个体具有较高的生存概率，并获得更适应环境的基因结构。
6）算法本身也可以采用动态自适应技术，在进化过程中自动调整算法控制参数和编码精度，比如使用模糊自适应法。
简而言之，主要优点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。可以把搜索空间扩展到整个问题空间，因而具有全局优化性能。同时也缩短了整个搜寻额时间，整体上效率更高、结果更接近最优解。实现简单，没有复杂的数学计算。
算法缺点：
1）遗传算法编码和解码比较复杂，在进化前需要做复杂的编码工作，而在得到最优解后还要做复杂的解码工作，比较繁琐和复杂；
2）编码不规范及编码存在表示的不准确性，在遗传操作过程中，遗传算法编、解码不易掌控，容易出错；
3）遗传算法对初始种群的选择有一定的依赖性；
4）遗传算法通常的效率比其他传统的优化方法低；
5）遗传算法在适应度函数选择不当的情况下有可能收敛于局部最优，而不能达到全局最优；也容易过早收敛；
6）遗传算法对算法的精度、可行度、计算复杂性等方面，还没有有效的定量分析方法。
研究动向与应用前景：
遗传算法的应用研究已从初期的组合优化求解扩展到了许多更新、更工程化的应用方面。随着应用领域的扩展，遗传算法的研究出现了几个引人注目的新动向：
1）基于遗传算法的机器学习，这是把遗传算法从历来离散的搜索空间的优化搜索算法扩展到具有独特的规则生成功能的机器学习算法。这一新的学习机制对于解决人工智能中知识获取和知识优化精炼的瓶颈难题带来了希望。
2）遗传算法正日益和神经网络、模糊推理以及混沌理论等其它智能计算方法相互渗透和结合，这对开拓21世纪中新的智能计算技术将具有重要的意义。
3）并行处理的遗传算法的研究十分活跃。这一研究不仅对遗传算法本身的发展，而且对于新一代智能计算机体系结构的研究都是十分重要的。
4）遗传算法和人工生命的崭新研究领域正不断渗透。
5）遗传算法和进化规划（EP）以及进化策略（ES）等进化计算理论日益结合。这三者之间的比较研究和彼此结合的探讨正形成热点。
由于遗传算法的整体搜索策略和优化搜索方法在计算时不依赖于梯度信息或其它辅助知识，而只需要影响搜索方向的目标函数和相应的适应度函数，所以遗传算法提供了一种求解复杂系统问题的通用框架，它不依赖于问题的具体领域，对问题的种类有很强的鲁棒性，适用于非常复杂和困难的环境。所以广泛应用于许多科学和领域。
目前，遗传算法已被人们广泛地应用于生产调度、组合优化、通信网络设计、机器学习、机器人学、图象处理与模式识别、运动估计、信号处理、遗传编码、自适应控制和人工生命等领域。遗传算法也是人工智能领域中用于解决最优化的一种搜索启发式算法，是进化算法的一种。这种启发式通常用来生成有用的解决方案来优化和搜索问题。
结语:
遗传算法模拟生物繁殖的突变、交换和达尔文的自然选择（适者生存）。它把问题可能的解编码为一个向量（个体），向量的每一个元素称为基因，并利用目标函数（选择标准）对群体（个体集合）中的每一个个体进行评价，根据评价值（适应度）对个体进行选择、交换、变异等遗传操作，从而得到新的群体。遗传算法提供了一种求解复杂系统问题的通用框架，它不依赖于问题的具体领域，对问题的种类有很强的鲁棒性，适用于非常复杂和困难的环境。所以广泛应用于许多科学和领域。遗传算法特别在人工智能领域有突出表现，对推动人工智能发展具有重要意义！
---------------------------------------------------------------
更多有关AI/ML文章，敬请关注“科技优化生活”微信公众号，谢谢！