人工智能学习笔记：基本遗传算法及其改进算法
文章目录1引言2基本思想及发展历史3基本遗传算法详细步骤3.1编码3.2初始群体设定3.3设计适应度函数3.4遗传操作3.4.1选择3.4.2交叉3.4.3变异4基本遗传算法总结5遗传算法改进5.1双倍体遗传算法5.2双种群遗传算法5.3自适应遗传算法6参考文献1引言本次学习报告主要介绍基本遗传算法的详细过程以及三种遗传算法的改进算法，旨在回顾和整理这一学期习得的部分知识。在撰写报告的过程中，会在其中增加一些个人的思考，这些思考主要基于过去所学的知识，目的在于寻找知识与知识之间的联系。由于本人能力所限，如有不当之处，恳请读者指正并提出宝贵的意见。
2基本思想及发展历史遗传算法来源于达尔文进化论和群体遗传学，由美国的Holland教授于1975年首先提出。遗传算法既是经典的启发式算法，同时也是非确定性的拟自然算法，它为复杂系统的优化提供了一种新思路，对于诸多NP-Hard问题，遗传算法都有不错的表现。简而言之，我发现，遗传算法参考了生物遗传过程，并用于解决最优化的问题。实际上，这里的“生物遗传”就是高中生物所学的基因学问题。有趣的是，我们目前学到的某些算法均参考了生物学的相关知识，比如西瓜书第五章所介绍的BP神经网络。在链式法则和参数寻优过程中，连接权重w和阈值θ的计算对应正是我们高中所学的神经元部分知识，这可能也体现了跨学科思维。
图1神经元结构又比如我在看过赵军团队的《知识图谱》后，利用放缩的思想，发现整个知识图谱的构建过程，可能类似于学生做英语阅读理解的思维过程。在此举一个可能不太恰当的例子，我在阅读之前需要找定位词（命名实体识别），并且尽可能找到关键词之间的关系（关系抽取），之后在回到原文中找到相关段落句子，并根据一些表达情感的定语做适当的推理得到答案（知识推理），以此类推，当做完整篇文章之后，我也对这片文章的脉络有了一个初步的认知，并在脑中建立起对应的框架。
图2知识图谱生命周期说回遗传算法，它主要借用生物进化中“适者生存”的规律。在遗传算法中，染色体对应的是数据或数组，通常是由一维的串结构数据来表示的。遗传算法处理的是染色体，或者称为基因型个体。一定数量的个体组成了群体。群体中个体的数量称为种群的大小，也叫种群的规模。各个个体对环境的适应程度叫适应度。适应度大的个体被选择进行遗传操作产生新个体，体现了生物遗传中适者生存的原理。选择两个染色体进行交叉产生一组新的染色体的过程，类似生物遗传中的婚配。编码的某一个分量发生变化的过程，类似于生物遗传中的变异。 遗传算法包含两个数据转换操作，一个是从表现型到基因型的转换，将搜索空间中的参数或解转换成遗传空间中的染色体或个体，这个过程称为编码。另一个是从基因型到表现型的转换，即将个体转换成搜索空间中的参数，这个过程称为解码。图3是总结的遗传算法模拟生物遗传过程的相关环节。
图3模拟生物进程总结表1是整理的遗传算法发展历史。
表1遗传算法发展历史时间人名研究成果1965年Holland首次提出人工遗传操作的重要性1967年Bagley提出选择、交叉和变异操作；引入适应度定标概念；首次提出遗传算法自我调整概念，即引入交叉和变异的概率1971年Hollstien第一个把遗传算法用于函数优化1975年Holland系统阐述遗传算法基本理论和方法，并提出模式理论3基本遗传算法详细步骤图4是总结的一次迭代的遗传算法流程，接下来将围绕该图进行算法步骤阐述。
图4基本遗传算法流程总结3.1编码由于遗传算法不能直接处理问题空间的参数，因此，必须通过编码将要求解的问题表示成遗传空间的染色体或个体。该部分操作类似于自然语言处理中，词表示成词向量，这样我们就可以在特征空间中处理自然语言。对一个具体的应用问题如何编码是应用遗传算法的首要问题，也是遗传算法应用的难点。实际上，还不存在一种通用的编码方法，特殊的问题往往采用特殊的方法。图5是常见的编码方法的总结。
图5编码方法总结其中，位串编码是将问题空间的参数编码为一维排列的染色体的方法，称为一维染色体编码方法。一维染色体编码中最常用的符号集是二值符号集{0,1}，即采用二进制编码。实际上，整理之后发现，其余的方法都是在解决二进制编码的不足之处。 比如，二进制编码的缺点有二：一是相邻整数的二进制编码可能具有较大的Hamming距离（例如，15和16的二进制表示为01111和10000，因此算法从15改进到16必须改变所有的位），这种缺陷造成了Hamming悬崖，降低了遗传算子的搜索效率；二是在求解高维优化问题时，二进制编码将非常长，从而使得算法的搜索效率很低。 针对缺点一，可以采用Gray编码，也就是说将二进制编码通过一次异或变换进行转换，这样会克服二进制编码的Hamming悬崖。针对缺点二，可以采用实数编码，即用若干实数表示一个个体，然后在实数空间上进行遗传操作。
3.2初始群体设定由于遗传算法是对群体进行操作的，所以，必须为遗传操作准备一个由若干初始解组成的初始群体。群体设定主要包括两个方面：初始种群的产生和种群规模的确定。
图6群体设定步骤总结初始种群的个体是随机产生的，但最好采用如下策略设定：一是根据问题固有知识，设法把我最优解所占空间在整个空间中的分布范围，然后，在此分布范围内设定初始群体；二是先随机产生一定数目的个体，然后从中挑选最好的个体（类似于种子实体）加入到初始群体中，这种过程不断迭代，直到初始群体中个体数目达到了预先确定的规模。针对于策略二这种反复迭代的描述，我认为类似于Bootstrapping策略。 种群规模影响遗传优化的结果和效率。当种群规模太小时，遗传算法的优化性能一般不会太好，容易陷入局部最优解。实际上，在学习完整个算法后，我发现针对于算法优化的一个关键环节就是在于如何“跳出”局部最优，进而“逼近”全局最优。这就让我联想到BP神经网络关于参数寻优部分的三种“跳出”策略，也可以说是启发式搜索策略。图7是总结的“跳出”策略。
图7“跳出”策略而种群规模太大也会带来弊端：一是群体越大，其适应度评估次数增加，所以计算量也增加，从而影响算法效率；二是群体中个体生存下来的概率大多采用和适应度成比例的方法，当群体中个体非常多时，少量适应度很高的个体会被选择而生存下来，但大多数个体却被淘汰，这会影响配对库的形成，从而影响交叉操作。
3.3设计适应度函数遗传算法遵循自然界优胜劣汰的原则，在进化搜索中基本不用外部信息，而是用适应度值表示个体的优劣，作为遗传操作的依据。适应度函数是用来区分群体中的个体好坏的标准，是算法演化过程的驱动力，是进行自然选择的唯一依据。
图8适应度函数设计方法一般而言，适应度函数是由目标函数变换得到的。最直观的方法就是将待求解优化问题的目标函数作为适应度函数。 在遗传算法中，将所有妨碍适应度值高的个体产生，从而影响遗传算法正常工作的问题统称为欺骗问题。比如，如果群体中出现超级个体，即该个体的适应值大大超过群体的平均适应值，则按照适应值比例进行选择时，该个体很快就会在群体中占有绝对的比例，从而导致算法较早地收敛到一个局部最优点，这一现象称为过早收敛。这就是一种欺骗问题。 对适应度函数值域的某种映射变换称为适应度函数的尺度变换（定标）。尺度变换分为线性变换和非线性变换，这里重点介绍线性变换。 设原适应度函数为f，定标后的适应度函数为f’，则线性变换可采用下式表示为
f‘=af+bf^`=af+bf‘=af+b
系数a和b可以有多种途径设定，但要满足两个条件：
①变换后的适应度的平均值要等于原适应度平均值，以保证适应度为平均值的个体在下一代的期望复制数为1；②变换后适应度函数的最大值要等于原适应度函数平均值的指定倍数（相当于最小公倍数），以控制适应度最大的个体在下一代中的复制数。favg=afavg+bCmultfavg=afmax+bf_{avg}=af_{avg}+b\C_{mult}f_{avg}=af_{max}+bfavg=afavg+bCmultfavg=afmax+b
根据上述条件得出的推导公式，通过简单的联立方程组求解即可得出线性变换的系数a和b。 线性变换法变换了适应度之间的差距，保持了种群的多样性。如果种群里某些个体适应度远远低于平均值时，甚至出现负数，为满足最小适应度非负的条件，可以满足进行如下变换：
favg=afavg+b0=afmin+bf_{avg}=af_{avg}+b\0=af_{min}+bfavg=afavg+b0=afmin+b
这是我根据书上结果反推得出的推导公式。通过简单的计算即可得出适应值非负条件下的系数a和b。与基础条件不同之处在于将可能为负值的变换后的适应度置为0.
3.4遗传操作3.4.1选择选择操作也称为复制操作是从当前群体中按照一定概率选出优良的个体，使他们有机会作为父代繁殖下一代子孙。判断个体优良与否的准则是各个个体的适应度值。 在遗传算法中，哪个个体被选择进行交叉是按照概率进行的。适应度大的个体被选择的概率大，但不是说一定能够被选上。同样，适应度小的个体被选择的概率小，但也可能被选上。这体现了遗传算法的随机性的特点。 适应度比例方法非常容易理解，就是按个体适应度在整个种群总适应度的所占比例分配概率。而排序方法根据适应度大小顺序对群体中个体进行排序，然后把事先设计好的概率按排序分配给个体，作为各自的选择概率。选择概率仅仅取决于个体在种群中的序位，而不是实际的适应度值。
图9选择流程及方法总结表2选择个体方法总结选择个体方法概述轮盘赌选择先按个体的选择概率产生一个轮盘，轮盘每个区的角度与个体的选择概率成比例，然后产生一个随机数，它落入转盘的哪个区域就选择相应的个体交叉锦标赛选择从群体中随机选择k个个体，将其中适应度最高的个体保存到下一代。这一过程反复执行，直到保存到下一代的个体数达到预先设定的数量为止最佳个体保存方法把群体中适应度最高的一个或者多个个体不进行交叉而直接复制到下一代中，保证遗传算法终止时候得到的最后结果一定是历代出现过的最高适应度的个体3.4.2交叉当两个生物体配对或者复制时，它们的染色体相互混合，产生一个由双方基因组成的全新的染色体组。这一过程称为重组或者交叉。这里的交叉操作就是高中生物中的AB和Ab进行交配产生新的基因型的过程。
图10交叉算子总结简单描述部分匹配交叉PMX。先依据均匀随机分布产生两个交叉点，定义两点之间的区域为一匹配区域，并使用位置交换操作交换两个父串的匹配区域。现在举例说明：
A=984|567|132B=871|239|546首先交换A和B的两个匹配区域，得到
A=984|239|132B=871|567|546显然，根据出现的重复任务，这就是非法调度。解决方法是将匹配区域外出现的重复任务，按照匹配区域内的位置映射关系进行交换，进而使排列成为可行调度。进一步解释，根据匹配区域的位置位置映射关系，即“2-5、3-6、9-7”，先对A中出现的重复任务“2、3”和“9”进行替换（不存在顺序关系，“3，2”也是重复的），即替换成“5，6，7”，然后将替换掉的字符“2，3，9”补到对应的B中所出现空缺的位置。最后结果即为
A=784|239|165B=891|567|243实验表明交叉概率通常取值为0.7左右是理想的。每次从群体中选择两个染色体，同时生成0和1之间的一个随机数，然后根据这个随机数确定这两个染色体是否需要交叉。如果随机数低于交叉概率，就进行交叉。
3.4.3变异对于变异操作，可以理解为高中生物中的加一段染色体或者替换染色体中的某一基因段等操作。在遗传算法中，变异是将个体编码的一些位进行随机变化。变异算子的基本内容是对群体中的个体串的某些基因座上的基因值作变动。变异操作是按位进行的，即把某一位的内容进行变异。变异概率是在一个染色体中按位进行变化的概率。主要的变异方法如图11所示。
图11变异算子总结在遗传算法中，变异属于辅助性的搜索操作（在做高中生物时，变异也属于题目需要特别提示的内容，并非必须）。变异概率一般不能大，以防止群体中重要的、单一的基因可能被丢失。实际上，变异概率太大将使得遗传算法趋于纯粹的随机搜索。
4基本遗传算法总结图12为基本遗传算法的流程图。遗传算法是一个利用随机技术来指导对一个编码的参数空间进行高效率搜索的方法，而不是无方向的随机搜索。许多传统搜索方法都是单解搜索方法，遗传算法采用群体搜索策略，即采用同时处理群体中多个个体的方法，同时对搜索空间中的多个解进行评估，从而使遗传算法具有较好的全局搜索性能，减少了陷于局部优解的风险，但不能保证每次都得到全局最优解。显而易见，遗传算法本身十分易于并行化。 在基本遗传算法中，基本上不用搜索空间的知识或其他辅助信息，而仅仅用适应度函数值来评估个体，并在此基础上进行遗传操作，使种群中个体之间进行信息交换。特别是遗传算法的适应度函数不仅不受连续可微的约束，而且其定义域也可以任意设定。对适应度函数的唯一要求就是能够算出可以比较的正值。
图12基本遗传算法流程图5遗传算法改进接下来的遗传算法改进，实际上就是针对与图12的基本遗传算法流程进行改进。下面将简述三种改进算法在哪一环节进行了改进。
5.1双倍体遗传算法上文阐述的基本遗传算法属于单倍体遗传，每个基因型由一条染色体（也就是基因型AB，分别只有一个等位基因A和B）。显然，大多数动物和高级植物都采用双倍体遗传（也就是AaBb），即每个基因型由一对染色体决定。这势必会出现显隐性遗传问题。 那具体在图12的哪一部分作出调整呢？须知双倍体遗传算法采用显性遗传，并且提供了一种记忆以前有用的基因块功能。 进一步而言，在选择操作中，按照显性染色体的选择概率将个体复制到下一代群体中；同时，在交叉操作中，两个体的显性染色体和隐形染色体分别进行交叉操作；在变异操作中，显性染色体按照正常的变异概率执行操作，隐形染色体按照较大的概率进行操作。 与基本遗传算法的一个显著区别在于，执行完上述操作后，会再增加一个显隐性重排操作，因为每一轮迭代之后，并不能确定显性和隐性的在下一轮划分，有了显隐性重排操作，增加了算法的随机性，也提高了隐性染色体里优良基因的存活概率。具体来说，个体中适应度较大的染色体设定为下一轮的显性染色体，适应度较小的染色体设定为下一轮的隐性染色体。
5.2双种群遗传算法双种群遗传算法意在突破平衡态——长时间进化后某些特征处于相对优势的状态，实际上，这再次体现出算法在接近全力“逼近”全局最优，是一个具有优秀扩展性的启发式搜索算法。 对比图12，主要区别在于双种群同时进行图中操作，但在执行完上述操作后，增加一步杂交操作，即交换种群之间优秀个体所携带的遗传信息，以打破种群内的平衡态以达到更高的平衡态，有利于算法跳出局部最优。 杂交算子，具体来说，设种群A和种群B，当两种群均完成了选择、交叉和变异操作后，产生一个随机数num，随机选择A中num个个体与A中最优个体，随机选择B中num个个体与B中最优个体，交换两者，打破平衡态。“产生随机数num”又一次体现了算法的随机性。
5.3自适应遗传算法自适应遗传算法的改进关键点在于交叉概率和变异概率，使两概率能随适应度变化自动改变。这样即可保证算法可以跳出局部最优情况，也可以利于优良个体的生存。所以，自适应遗传算法在保持群体多样性的同时，保证遗传算法的收敛性。 对比图12，区别在于交叉算子中，要使用自适应公式计算交叉概率，然后产生随机数，如果小于计算后的概率，那么交叉该对染色体对；同理，在变异算子中，也使用自适应公式计算变异概率，并产生随机数，若小于计算后的概率，那么变异该染色体。
6参考文献王万良.人工智能导论(第4版)[M]:高等教育出版社,2017.人工智能结课作业
代码已经发布到了github:https://github.com/roadwide/AI-Homework
如果帮到你了，希望给个star鼓励一下
1遗传算法1.1算法介绍遗传算法是模仿自然界生物进化机制发展起来的随机全局搜索和优化方法，它借鉴了达尔文的进化论和孟德尔的遗传学说。其本质是一种高效、并行、全局搜索的方法，它能在搜索过程中自动获取和积累有关搜索空间的知识，并自适应的控制搜索过程以求得最优解。遗传算法操作使用适者生存的原则，在潜在的解决方案种群中逐次产生一个近似最优解的方案，在遗传算法的每一代中，根据个体在问题域中的适应度值和从自然遗传学中借鉴来的再造方法进行个体选择，产生一个新的近似解。这个过程导致种群中个体的进化，得到的新个体比原来个体更能适应环境，就像自然界中的改造一样。
遗传算法具体步骤：
（1）初始化：设置进化代数计数器t=0、设置最大进化代数T、交叉概率、变异概率、随机生成M个个体作为初始种群P
（2）个体评价：计算种群P中各个个体的适应度
（3）选择运算：将选择算子作用于群体。以个体适应度为基础，选择最优个体直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代
（4）交叉运算：在交叉概率的控制下，对群体中的个体两两进行交叉
（5）变异运算：在变异概率的控制下，对群体中的个体进行变异，即对某一个体的基因进行随机调整
（6）经过选择、交叉、变异运算之后得到下一代群体P1。
重复以上（1）-（6），直到遗传代数为T，以进化过程中所得到的具有最优适应度个体作为最优解输出，终止计算。
旅行推销员问题（TravellingSalesmanProblem，TSP）：有n个城市，一个推销员要从其中某一个城市出发，唯一走遍所有的城市，再回到他出发的城市，求最短的路线。
应用遗传算法求解TSP问题时需要进行一些约定，基因是一组城市序列，适应度是按照这个基因的城市顺序的距离和分之一。
1.2实验代码importrandomimportmathimportmatplotlib.pyplotasplt#读取数据f=open("test.txt")data=f.readlines()#将cities初始化为字典，防止下面被当成列表cities={}forlineindata:#原始数据以 换行，将其替换掉line=line.replace(" ","")#最后一行以EOF为标志，如果读到就证明读完了，退出循环if(line=="EOF"):break#空格分割城市编号和城市的坐标city=line.split("")map(int,city)#将城市数据添加到cities中cities[eval(city[0])]=[eval(city[1]),eval(city[2])]#计算适应度，也就是距离分之一，这里用伪欧氏距离defcalcfit(gene):sum=0#最后要回到初始城市所以从-1，也就是最后一个城市绕一圈到最后一个城市foriinrange(-1,len(gene)-1):nowcity=gene[i]nextcity=gene[i+1]nowloc=cities[nowcity]nextloc=cities[nextcity]sum+=math.sqrt(((nowloc[0]-nextloc[0])**2+(nowloc[1]-nextloc[1])**2)/10)return1/sum#每个个体的类，方便根据基因计算适应度classPerson:def__init__(self,gene):self.gene=geneself.fit=calcfit(gene)classGroup:def__init__(self):self.GroupSize=100#种群规模self.GeneSize=48#基因数量，也就是城市数量self.initGroup()self.upDate()#初始化种群，随机生成若干个体definitGroup(self):self.group=[]i=0while(ibestFit):bestFit=person.fitbest=personreturnbest#计算种群中所有个体的平均距离defgetAvg(self):sum=0forpinself.group:sum+=1/p.fitreturnsum/len(self.group)#根据适应度，使用轮盘赌返回一个个体，用于遗传交叉defgetOne(self):#section的简称，区间sec=[0]sumsec=0forpersoninself.group:sumsec+=person.fitsec.append(sumsec)p=random.random()*sumsecforiinrange(len(sec)):if(p>sec[i]andpself.bestFit):self.bestFit=newfitself.bestAddr=self.addr#变异操作#设置变异后避免了所有鸟都聚集到一个离食物近，但又不是最近的地方，并且就停在那里不动了defchange(self):i,j=random.randrange(0,48),random.randrange(0,48)self.addr[i],self.addr[j]=self.addr[j],self.addr[i]self.upDate()#贪婪倒立变异defreverse(self):#随机选择一个城市cityx=random.randrange(1,49)noxcity=self.addr[:]noxcity.remove(cityx)maxFit=0nearCity=noxcity[0]forcinnoxcity:fit=calcfit([c,cityx])if(fit>maxFit):maxFit=fitnearCity=cindex1=self.addr.index(cityx)index2=self.addr.index(nearCity)tmp=self.addr[index1+1:index2+1]tmp.reverse()self.addr[index1+1:index2+1]=tmpself.upDate()#种群的类，里面有很多鸟classGroup:def__init__(self):self.groupSize=500#鸟的个数、粒子个数self.addrSize=48#位置的维度，也就是TSP城市数量self.w=0.25#w为惯性系数，也就是保留上次速度的程度self.pChange=0.1#变异系数pChangeself.pReverse=0.1#贪婪倒立变异概率self.initBirds()self.best=self.getBest()self.Gen=0#初始化鸟群definitBirds(self):self.group=[]foriinrange(self.groupSize):addr=[i+1foriinrange(self.addrSize)]random.shuffle(addr)bird=Bird(addr)self.group.append(bird)#获取当前离食物最近的鸟defgetBest(self):bestFit=0bestBird=None#遍历群体里的所有鸟，找到路径最短的forbirdinself.group:nowfit=calcfit(bird.addr)if(nowfit>bestFit):bestFit=nowfitbestBird=birdreturnbestBird#返回所有鸟的距离平均值defgetAvg(self):sum=0forpinself.group:sum+=1/p.fitreturnsum/len(self.group)#打印最优位置的鸟的相关信息defshowBest(self):print(self.Gen,":",1/self.best.fit)#更新每一只鸟的速度和位置defupDateBird(self):self.Gen+=1forbirdinself.group:#g代表group，m代表me，分别代表自己和群组最优、自己最优的差deltag=switchB2A(self.best.addr,bird.addr)deltam=switchB2A(bird.bestAddr,bird.addr)newv=multiply(self.w,bird.v)[:]+multiply(random.random(),deltag)[:]+multiply(random.random(),deltam)bird.switch(newv)bird.v=newvif(random.random()
遗传算法实验报告
遗传算法实验报告时间：2023.7.7遗传算法实验报告
姓名：**学号：**
一、实验目的：
熟悉和掌握遗传算法的运行机制和求解的基本方法。
遗传算法是一种基于空间搜索的算法，它通过自然选择、遗传、变异等操作以及达尔文的适者生存的理论，模拟自然进化过程来寻找所求问题的答案。其求解过程是个最优化的过程。一般遗传算法的主要步骤如下：
（1）随机产生一个确定长度的特征字符串组成的初始种群。。
（2）对该字符春种群迭代地执行下面的步骤a和步骤b，直到满足停止准则为止：
a计算种群中每个个体字符串的适应值；
b应用复制、交叉和变异等遗传算子产生下一代种群。
（3）把在后代中表现的最好的个体字符串指定为遗传算法的执行结果，即为问题的一个解。
二、实验原理和题目：
通过编码、设置种群、设置适应度函数、遗传操作、解码产生需要的解。
f(x)=x*sin(x)+1，x[0,2],求解f(x)的最大值和最小值。
三、实验条件
硬件：微型计算机。
语言：本实验选用的为C#语言。
四、实验内容：
建造针对f(x)的遗传算法程序，然后进行运行求解。
五、实验步骤：
1. 确定基本功能：本实验是实现f（x）的最大值和最小值的求解。
2.对f(x)进行编码：用一个二进制矢量表示一个染色体，由染色体来代表变量x的实数值，这里精度取小数点后6位数，变量x的域长为2，整个区间被分为2*1000000个等长的区间。由于2*1000000在23位二进制数的表示范围呢，所以，编码长度为23位。试验中用函数GetRandomBinaryArray(intcount,inti);来实现。
3.设计适应度函数：由于要求f（x）的最值，所以适应度函数就是f（x）。
4. 针对f(x)的设计并且实现遗传算法程序：遗传操作主要包括复制、交叉和变异。复制是直接将父代遗传给子代，即根据个体的适应度函数值所度量的优劣程度决定它在下一代是被淘汰还是被遗传。交叉从能进入下一代的个体中选出两个，将两者的部分码值进行交换。变异是根据变异概率选出一个个体，随机对其某位编码进行改变。复制由voidSelection(boolflag);实现；交叉由voidCrossed();实现；变异由voidMution();实现。
5. 设计初始种群：默认设置为50个随机产生的23位字节的染色体，可以通过输入来设置种群规模。
6.调试交叉和变异概率：在常用的交叉和变异概率范围内，结果随交叉和变异的概率的改变而改变，之间差异相对来说不太明显
7. 实验参数：实验中主要的参数有遗传代数、群体规模、交叉概率、变异概率。
实验结果：
求最大值
求最小值：
核心程序：
publicEGAlgorith(doublemin,doublemax,doublecrossRate,doublevarRate,intprecision,intpopulationNumeber)
{
m_minValue=min;
m_maxValue=max;
m_crossRate=crossRate;
m_varRate=varRate;
m_populationNumber=populationNumeber;
m_length=max-min;
m_populations=newstring[m_populationNumber][];
m_doublePopulation=newdouble[m_populationNumber];
m_fit=newdouble[m_populationNumber];
m_codeLength=Convert.ToString(Convert.ToInt32(m_length*Math.Pow(10,precision)),2).Length;
//初始化种群
for(inti=0;i＜m_populationNumber;i++)
{
m_populations[i]=GetRandomBinaryArray(m_codeLength,i);
}
}
//产生随机数组
publicstaticstring[]GetRandomBinaryArray(intcount,inti)
{
Randomrnd=newRandom(DateTime.Now.Millisecond+i);
byte[]keys=newbyte[count];
rnd.NextBytes(keys);
string[]items=newstring[count];
for(intj=0;j＜count;j++)
{
if(keys[j]＞127)
{
items[j]="1";
}
else
{
items[j]="0";
}
}
returnitems;
}
//根据适应度进行选择最值
publicvoidFromFitSelect(boolflag)
{
//int[]indexs=newint[m_populationNumber];
intwinIndex=0;
doubletempMin=double.MinValue;
doubletempMax=double.MaxValue;
if(flag)
{
for(inti=0;i＜m_populationNumber;i++)
{
//indexs[i]=i;
if(m_fit[i]＞tempMin)
{
tempMin=m_fit[i];
winIndex=i;
}
}
}
else
{
for(inti=0;i＜m_populationNumber;i++)
{
if(m_fit[i]＜tempMax)
{
tempMax=m_fit[i];
winIndex=i;
}
}
}
//intwinIndex=GetMaxIndex(indexs);
m_winCode=m_populations[winIndex];
m_winValue=m_doublePopulation[winIndex];
m_winFit=m_fit[winIndex];
}
//选择方法
privatevoidSelection(boolflag)
{
intsize=3;//竞争规模
string[][]tempPopulation=newstring[m_populationNumber][];
for(inti=0;i＜m_populationNumber;i++)
{
int[]inSelect=GetRandomIntArray(0,m_populationNumber-1,size,i);
intwinIndex=GetMaxIndex(inSelect,flag);
string[]tempStr=newstring[m_codeLength];
for(intj=0;j＜m_codeLength;j++)
{
tempStr[j]=m_populations[winIndex][j];
}
tempPopulation[i]=tempStr;
}
m_populations=tempPopulation;
}
//交叉方法
privatevoidCrossed()
{
int[]crossRate=GetRandomIntArray(0,1000,m_populationNumber,3);
for(inti=0;i＜m_populationNumber;i++)
{
if(crossRate[i]＜=m_crossRate*1000)
{
int[]doubCrossIndex=GetRandomIntArray(0,m_populationNumber-1,2,2);
Randomrnd=newRandom();
intcrossPosition=rnd.Next(m_codeLength);
string[]tempStr=newstring[m_codeLength];
for(intj=0;j＜crossPosition;j++)
{
tempStr[j]=m_populations[i][j];
}
for(intk=crossPosition;k＜m_codeLength;k++)
{
tempStr[k]=m_populations[doubCrossIndex[0]][k];
}
m_populations[i]=tempStr;
}
}
}
//变异方法
privatevoidMution()
{
int[]varRate=GetRandomIntArray(0,1000,m_populationNumber,3);
for(inti=0;i＜m_populationNumber;i++)
{
Randomrnd=newRandom(i*i);
intvarPosition=rnd.Next(m_codeLength);
if(varRate[i]＜m_varRate*1000)
{
if(m_populations[i][varPosition]=="0")
{
m_populations[i][varPosition]="1";
}
else
{
m_populations[i][varPosition]="0";
}
}
}
}
//遗传操作
publicvoidEvaluaton(boolflag)
{
ComputeIndividual();
ComputeFit();
FromFitSelect(flag);
Selection(flag);
Crossed();
Mution();
}
第二篇：遗传算法实验报告一、实验题目
求解线性约束优化问题的遗传算法
将物品由7个起运站运到7个目的地；已知由i站运到j地的单位运费是，表示i站的供应量，表示j地的需求量，表示从i站到j地的运量。(i,j=1,2,…,7）
约束条件：
目标函数为：
罚函数为：
其中，k=1，P=1/14，f为第t代群体的平均适应度，T为最大运行代数，为约束的违反度。
费用参数表如下：
使用策略：通用遗传算法模型、精英保存策略、轮盘赌法策略选择个体交叉和变异，对上述例子进行了算法的测试，种群个体大小为40，迭代10000次，得到比较稳定的结果。每次运行的结果是得到一个相对稳定的、代价小的目标值。实验结果：在当前条件下，在初始种群的40个个体，经过10000次迭代得到最低运费为1279，并且程序多次运行结果都稳定在1300左右。
二、实验环境
操作系统：MicrosoftWindowsXPProfessional
软件：MicrosoftVisualC++6.0
三、实验设计原理
1.实验内容分析
本实验采用遗传算法求解带约束条件的函数优化问题。
2.遗传算法的思想
生物的进化是以集团为主体的。与此相对应，遗传算法的运算对象是由M个个体所组成的集合，称为群体。与生物一代一代的自然进化过程相类似，遗传算法的运算过程也是一个反复迭代过程，第t代群体极为P（t），进过一代遗传和进化后，得到第t+1代群体，他们也是由多个个体组成的集合，记做P（t+1）。这个群体不断地经过遗传和进化操作，并且每次都按照有优胜劣汰的规则将适应度较高的个体更多地遗传到下一代，这样最终在群体中将会得到一个优良的个体X，它所对应的表现性X将达到或接近于问题的最优解。
3.算法实现步骤
①产生初始种群：产生初始种群的方法通常有两种：一种是完全随机的方法产生的，适合于对问题的解无任何先验知识的情况；另一种是将某些先验知识转变为必须满足的一组要求，然后在满足这些要求的解中再随机地选择样本，t=0,随机产生n个个体形成一个初始群体P（t），该群体代表优化问题的一些可能解的集合；
②适应度评价函数：按编码规则，将群体P（t）中的每一个个体的基因码所对应的自变量取值代入目标函数，算出其函数值，i=1,2,…,n,越大，表示该个体有较高的适应度，更适合于f所定义的生存环境，适应度为群体进化提供了依据；
③选择：按一定概率从群体P（t）中选出m个个体，作为双亲用于繁殖后代，产生新的个体加入下一个群体P（t+1）中；
④交叉（重组）：对于选中的用于繁殖的每一个个体，选择一种交叉方法，产生新的个体；
⑤变异：以一定的概率从群体P（t+1）中随机选择若干个个体，对于选中的个体，进行变异；
⑥对产生新一代的群体返回步骤③再进行评价，交叉、变异如此循环往复，使群体中个体的适应度和平均适应度不断提高，直至最优个体的适应度达到某一限值或最优个体的适应度和群体的平均适应度不再提高，则迭代过程收敛，算法结束。
4.算法流程图
5.实验调试与结果分析（问题的发现、分析、解决方案与创新）
1)程序结果如下图：
2)收敛效果如下图：
四、实验小结及附录
通过本次实验，我了解了演化计算的基本思想，并能够运用演化计算的思想解决函数最优值问题，能够编写相应的程序。实验过程中遇到很多问题，但是进过认真分析，最终能解决问题。
更多相关推荐：遗传算法实验报告桂林理工大学实验报告班级计算机111班学号同组实验者实验名称日期20xx年5月30日一实验目的用遗传算法求fxxsin10pix10的最大值其中x区间为12二实验内容初始化编码实现目标函数的计算将pop每行转化...
遗传算法实验报告人工智能实验报告遗传算法实验报告一问题描述对遗传算法的选择操作设种群规模为4个体用二进制编码适应度函数x的取值区间为030若遗传操作规定如下1选择概率为100选择算法为轮盘赌算法2交叉概率为1交叉算法为单点交叉...
遗传算法实验报告实验报告实验名称遗传算法实验实验目的熟悉和掌握遗传算法的运行机制和求解的基本方法实验原理通过编码设置种群设置适应度函数遗传操作解码产生需要的解fxxsinx1x02求解fx的最大值和最小值实验内容1确定数据结构...
遗传算法实验报告遗传算法实验报告专业自动化姓名张俊峰学号13351067摘要遗传算法是基于达尔文进化理论发展起来的一种应用广泛高效的随机搜索与优化方法本实验利用遗传算法来实现求函数最大值的优化问题其中的步骤包括初始化群体个体评...
遗传算法实验报告一题目12maxfxxxX最大值解空间为非负整数集求解优化问题X012311matlab源程序及说明question1mclearfigure1plot0312画出函数曲线定义遗传算法参数NIND4Number...
TSP问题的遗传算法实验报告TSP问题的遗传算法实验报告一实验题目TSP问题的遗传算法实现二实验目的1熟悉和掌握遗传算法的基本概念和基本思想2加深对遗传算法的理解理解和掌握遗传算法的各个操作算子3理解和掌握利用遗传算法进行问题求解的基本技...
遗传算法实验报告1定义种群和个体定义种群为S种群数N50其中xy是染色体中的两个基因组2算法设计1确定编码设计由于原函数的变量取值包含负数不方便进行编码所以将原函数的变量进行转换从1010转换成020相应的函数也要进行变换根据...
银行家算法实验报告操作系统实验报告课题银行家算法专业班级学号姓名年月日目录一实验目的错误未定义书签二实验内容3三问题描述3四设计思路4五详细设计5六运行结果10七心得体会16八参考文献17附源程序17一实验目的模拟实现银行家算法...
数据挖掘FP-Growth算法实验报告FPGrowth算法实验报告一算法介绍数据挖掘是从数据库中提取隐含的未知的和潜在的有用信息的过程是数据库及相关领域研究中的一个极其重要而又具有广阔应用前景的新领域目前对数据挖掘的研究主要集中在分类聚类关联规则挖...
计算机操作系统银行家算法实验报告计算机操作系统实验报告一实验名称银行家算法二实验目的银行家算法是避免死锁的一种重要方法通过编写一个简单的银行家算法程序加深了解有关资源申请避免死锁等概念并体会和了解死锁和避免死锁的具体实施方法三问题分析与设计1...
银行家算法+实验报告淮海工学院计算机工程学院实验报告书课程名操作系统原理题目银行家算法班级学号511021012姓名操作系统原理实验报告1一实验目的银行家算法是操作系统中避免死锁的典型算法本实验可以加深对银行家算法的步骤和相关数据...
银行家算法实验报告计算机学院操作系统课程设计报告设计题目银行家算法的实现姓名学号班级06网络工程班完成日期20xx年6月13日银行家算法分析设计与实现一设计理论描述本设计的目的是通过编写和调试一个系统动态分配资源的简单模拟程序观...
遗传算法实验报告（40篇）
遗传算法学习总结
遗传算法(GeneticAlgorithm)学习总结最近学习了一下遗传算法，感觉非常有趣，就深入钻研了一下，这是一个非常适合用来求全局最优解的算法思想。这篇文章主要是和大家分享一下自己学习下来的一些总结，希望对大家的学习也能有一定价值。
概述大自然的生存法则就是物竞天择，优胜劣汰，能够适应大自然，物种方可生存下去，得以繁衍。遗传算法（GeneticAlgorithm,GA）便是沿用了这一思想，它是根据模仿自然界生物进化机制发展起来的随机全局搜索和优化方法，借鉴了达尔文的进化论和孟德尔的遗传学说。其本质是一种高效、并行、全局搜索的方法，能在搜索过程中自动获取和积累有关搜索空间的知识，并自适应地控制搜索过程以求得全局最优解。
关键术语基因型(genotype)：性状染色体的内部表。表现型(phenotype)：染色体决定的性状的外部表现，或者说，根据基因型形成的个体的外部表现。适应度(fitness)：度量某个物种对于生存环境的适应程度。选择(selection)：以一定的概率从种群中选择若干个个体。一般，选择过程是一种基于适应度的优胜劣汰的过程。交叉配对(crossover)：两个染色体的某一相同位置处DNA被切断，前后两串分别交叉组合形成两个新的染色体，也称基因重组或杂交。变异(mutation)：配对时DNA可能（很小的概率）产生某些细小的差错，变异产生新的染色体，表现出新的性状。编码(coding)：DNA中遗传信息在一个长链上按一定的模式排列。遗传编码可看作从表现型到基因型的映射。解码(decoding)：基因型到表现型的映射。个体（individual）：指染色体带有特征的实体。种群（population）：个体的集合，该集合内个体数称为种群。代（generation）：指染色体交叉配对将产生的后代代数。引例太过专业的定义大家还是很难明白遗传算法是什么，要干什么。那么我来给大家举个例子。想象一下有一群人生活在山中，他们随机地居住在山中的不同位置，有人在山峰，有人在山谷，有人在山腰。突然有一天发起了大水，水不停地向上涨，那些住在地势比较低地方的人们就会淹死，不排除极个别少数人水性比较好，能存活一阵子。而那些住在地势比较高地方的人就不会淹死，我们称那些不会淹死的人对环境的适应度较高。为了繁衍后代，就在这些适应度高的人群中进行交叉繁殖，希望在繁殖的过程中得到能够到达所有山峰中最高的山峰从而得以存活的最优一代的DNA，当然在繁殖过程中不排除有基因变异的可能存在。那么在这个问题中如何繁衍出生活在最高山峰的这代种群就是遗传算法所要解决的问题。 我们可以将整座山投影到二维平面，那么山的地形就如同这个函数图像，把人就当作图像中的点，那么我们只需要得出最高点的横坐标即可得知最优一代的DNA。
即变成了求解该函数在区间[0,5]上的最大值点的问题。实现过程遗传算法的实现过程就像是自然界生物的进化那样，只不过你就是自然规则的缔造者。首先制定人的DNA的编码方案，即建立基因型和表现型的映射关系。然后随机初始化一个种群，即人类，为其分配随机的DNA序列，即人们在山中的位置（图中点的横坐标），并将DNA依照自己建立的映射关系编码成表现型。接下来通过自己制定的适应度算法来算出处在不同位置的人的适应度，地势高的人适应度越高，越容易存活，而地势低的人适应度低，存活率也就低，每隔一段时间，适应度较低的人就会被大自然所淘汰以保证人类总体数目持平。随后，根据自己的择优方案按照适应度对人进行择优，再从这些存活的人中随机选择父母进行交叉配对，各选择父母的部分DNA进行基因重组产生新的DNA，从而得到一个处在不同位置的新生儿，为了避免人们生出了一个处在某个局部最高山峰的新生儿便以为这是最优一代的DNA就停止繁殖，我们允许新生儿有小概率变异的可能性。按照这个过程迭代N代，最终它将找到最适应这个环境的人的DNA。对于遗传算法而言，它并不知道它自己要做什么，它只是不断地在生成新的解，而你不需要告诉它怎么求得最好的解，只需要不断地否定其不好的解即可。
具体步骤 以下内容循环N次评估每个个体的适应度。依据适应度越高，被选择概率越大的原则，从种群中随机选择出父母。让父母进行交叉配对，繁殖出子代。对子代染色体进行变异，并取代父母。1.基因编码方式学过生物的朋友们都知道DNA是由碱基对构成的，受其启发，在计算机中我们可以认为“0”，“1”这两种二进制码就是构成DNA的碱基，再将他们串在一起就形成了一条可以表达个体特征的染色体。这就是二进制码编码，例如1011011000011011就是一条染色体。 二进制编码虽然简单直观，但当个体特征比较复杂时，需要很长的二进制码才足以精准描述，为了解决这个问题就引入了浮点数编码，例如3.2-1.1-4.9-0.5-7.1-3.8。 这里我以二进制编码为例。我们可以将二进制数转换成十进制数，再将其映射到指定区间，即可得到人所处的位置。例如1011011000011011转换成十进制是46619，那么在对应区间[0,5]上，其横坐标的值应该是：
得出来结果是3.557，这便是DNA二进制编码后的结果。2.适应度评估为了刻画出个体在环境中的适应程度，我们需要制定一个适应度函数，这非常重要，关系到人该往哪个方向进化。适应度函数由你自己制定，在本例中，问题已经简化成找到该图像的最高点，因此适应度函数很好确定，位置越高的点，适应度就越高。我以表现型DNA作为输入，返回该值加上一个极小值再减去所有个体表现型DNA中最小的值，这么做的原因是图像上的高度有正有负，而算概率的时候不应该出现负值，所以减去负值之后所有值就都是正的了，再加上一个极小值是为了保证减去最小值后分母不会为0。当然这并不一定是最好的方法。
defget_fitness(result):returnresult+1e-9-np.min(result)复制代码3.选择函数选择函数决定了哪些个体有生存并繁衍的权利，通常其规则是适应度越高的个体越有可能作为父母进行繁殖，而适应度越低的个体则越有可能被淘汰。通常选择函数的制定方法有以下几种：
ProportionateRouletteWheelSelectionLinearRankingSelectionExponentialRankingSelectionTournamentSelection在实际应用中，最常见也是最易理解的方法就是ProportionateRouletteWheelSelection（轮盘赌算法）。其原理就是将每个个体的适应度在整体适应度中的占比，再依据占比对个体进行选择，因此适应度高的个体占比就大，被选中的概率也就高。
defselect(pop,fitness):idx=np.random.choice(np.arange(POP_SIZE),size=POP_SIZE,replace=True,p=fitness/fitness.sum())returnpop[idx]复制代码4.交叉配对配对的过程就类似DNA基因片段的交换，从而生成新的个体。
在实际过程中可以有实值重组和二进制交叉的方式来实现。这里我以二进制交叉为例，假如有两条DNA分别是1001010110001011和1011111100110101，那么这两条DNA配对的可能结果之一就是1001010100110101，当然也有可能是1011111110001011，具体的结果由你制定的基因选取方案决定。这里我选用的是二进制编码，如果选择的是浮点数编码，那么可以让新DNA的每个片段都取到父母DNA对应位置片段的中间值，例如3.4-4.2-1.5-6.1-7.4和4.4-5.2-2.3-5.6-9.2，其可能结果就可以是4.1-4.6-1.9-5.8-8.3。5.基因变异为了使得遗传算法具有局部的随机搜索能力以及避免陷入局部最优解，我们可以对生成的新DNA进行变异来使得DNA更加具有多样性。相应的，变异也分为实值变异和二进制变异。我以二进制变异为例，如果新生成的DNA是1001010100110101，那么可以将它某一位的0取成1或者1取成0，就变成了0001010100110101，同样这也取决于你制定的变异策略。由于变异具有随机性，因此我们无法断言变异会生成更好的DNA还是更坏的DNA。
这是之前那个例子的运行结果。总共有100个个体，DNA长度为10位，交配成功率为0.8，变异率为0.003，迭代200次，最终找到了最大值点的DNA:[1010100100]。（当新生一代的DNA为这个值时，将会在山顶成功存活，免于水灾。）至于图中为何没有所有点收敛于一点，我思考了一下，可能原因是每一次迭代都会进行交叉变异，虽然已经找到了最大值的点，但是仍然会有个别新生的DNA产生在局部最优位置，而种群中大部分的个体都已经收敛到了全局最优位置。（也可能是这个demo的实现算法还有需要改进的地方）
总结遗传算法的编写核心就在于这几点的确立：编码，适应度评估，选择策略，交叉配对，基因变异。 在设计适应度函数时最容易遇到的问题就是欺骗问题，使得最终答案偏离全局最优解收敛至局部最优解，在这篇paper中就提出使用均匀设计法去解决欺骗问题，有兴趣的朋友可以研究一下。（均匀设计法在GA欺骗问题中的应用研究） 目前遗传算法可以应用的问题还有很多，例如旅行商人问题，排班问题，句子生成等，这些应用都非常有趣，有兴趣的朋友可以自己去编码实现一下。
参考莫烦Python-遗传算法
遗传算法详解（GA）
遗传算法GA(GeneticAlgorithm)入门知识梳理
作者：Linx本文仅代表个人的一些理解，若有描述不当的地方，欢迎指正！码字不易，欢迎讨论，转载请注明出！。