人工智能技术导论——基于遗传算法的随机优化搜索
在高中生物上，我们就学习过关于遗传变异、自然选择的知识，自然选择的原则是优胜劣汰、适者生存，有性繁殖则可以不断使基因进行混合和重组，因此自然选择和有性生殖实际上是生物体的优化过程，正是这种优化过程的不断进行才导致了生物的进化。
遗传算法（GA）就是人们从生物界按自然选择和有性生殖、遗传变异的自然进化现象中得到启发，而设计出来的一种优化搜索算法。
博主学习遗传算法算是一种被动学习，就是听老师讲课，后来看了几篇知乎，发现大佬们写的入门文章通俗易懂，这里附上链接：
https://www.zhihu.com/question/23293449?utm_source=qq&utm_medium=social&utm_oi=875107575870418944
一、基本概念1.适应度与适应度函数适应度(fitness)就是借鉴生物个体对环境的适应程度,而对所求解问题中的对象设计的一种表征优劣的测度。适应度函数(fitnessfunction)就是问题中的全体对象与其适应度之间的一个对应关系,即对象集合到适应度集合的一个映射。它一般是定义在论域空间上的一个实数值函数。
2.染色体及其编码遗传算法以生物细胞中的染色体(chromosome)代表问题中的个体对象。而一个染色体可以看作是由若干基因组成的位串,所以需要将问题中的个体对象编码为某种位串的形式。这样,原个体对象也就相当于生命科学中所称的生物体的表现型(phenotype),而其编码即“染色体”也就相当于生物体的基因型(genotype)。遗传算法中染色体一般用字符串表示,而基因也就是字符串中的一个个字符。例如,假设数字9是某问题中的个体对象,则我们就可以用它的二进制数串1001作为它的染色体编码。
3.种群种群(population)就是模拟生物种群而由若干个染色体组成的群体,它一般是整个论域空间的一个很小的子集。遗传算法就是通过在种群上实施所称的遗传操作,使其不断更新换代而实现对整个论域空间的搜索。
4.遗传操作遗传算法中有三种关于染色体的运算:选择-复制、交叉和变异,这三种运算被称为遗传操作或遗传算子(geneticoperator)。
选择-复制选择-复制(selectionreproduction)操作是模拟生物界优胜劣汰的自然选择法则的一种染色体运算,就是从种群中选择适应度较高的染色体进行复制,以生成下一代种群。选择-复制的通常做法是,对于一个规模为N的种群S,按每个染色体xi∈S的选择概率P(xi)所决定的选中机会,分N次从S中随机选定N个染色体,并进行复制。这里的选择概率P(xi)的计算公式为
其中,f为适应度函数,f(xi)为xi的适应度。可以看出,染色体xi被选中的概率就是其适应度f(xi)所占种群中全体染色体适应度之和的比例。显然,按照这种选择概率定义,适应度越高的染色体被随机选定的概率就越大,被选中的次数也就越多,从而被复制的次数也就越多。相反,适应度越低的染色体被选中的次数也就越少,从而被复制的次数也就越少。如果把复制看做染色体的一次换代的话,则这就意味着适应度越高的染色体其后代也就越多,适应度越低的染色体其后代也就越少,甚至被淘汰。这正吻合了优胜劣汰的自然选择法则。
上述按概率选择的方法可用一种称为赌轮的原理来实现。即做一个单位圆,然后按各个染色体的选择概率将圆面划分为相应的扇形区域(如图4-1所示)。这样,每次选择时先转动轮盘,当轮盘静止时,上方的指针所正对着的扇区即为选中的扇区,从而相应的染色体即为所选定的染色体。例如,假设种群S中有4个染色体:s1,s2,s3,s4,其选择概率依次为:0.11,0.45,0.29,0.15,则它们在轮盘上所占的份额如图4－1中的各扇形区域所示。
在算法中赌轮选择法可用下面的子过程来模拟:①在［0,1］区间内产生一个均匀分布的伪随机数r。②若r≤q1,则染色体x1被选中。③若qk-1