人工智能大作业解读

目录摘要.........................................................................................................2一．问题描述..........................................................................................2二．遗传算法特点介绍...........................................................................2三．使用基本遗传算法解决0-1背包问题..............................................3四．基本遗传算法解决0-1背包问题存在的不足...................................4五．改进的遗传算法解决0-1背包问题..................................................6六．心得体会..........................................................................................9七．参考文献.........................................................................................10八．程序代码.........................................................................................10摘要：研究了遗传算法解决0-1背包问题中的几个问题：1）对于过程中不满足重量限制条件的个体的处理,通过代换上代最优解保持种群的进化性）对于交换率和变异率的理解和处理方法,采用逐个体和逐位判断的处理方法）对于早熟性问题,引入相似度衡量值并通过重新生成个体替换最差个体方式保持种群多样性。）一种最优解只向更好进化方法的尝试。通过实际计算比较表明,效率。通过实例计算，表明本文改进遗传算法优于简单遗传算法和普通改进的遗传算法。关键词：遗传算法；背包问题；优化一、问题描述0-1背包问题属于组合优化问题的一个例子，求解0-1背包问题的过程可以被视作在很多可行解当中求解一个最优解。01背包问题的一般描述如下：给定n个物品和一个背包，物品i的重量为Wi，其价值为Vi，背包的容量为。选择合适量之和不能大于背包的容量。在选择装入背包的物品时，对每种物品i只有两种选择：装入背包或者不装入背包，即只能将物品i装入背包一次。称此类问题为0/1背包问题。其数学模型为：0-1背包问题传统的解决方法有动态规划法、分支界限法、回溯法等等。传统的方法不能有效地解决0-1GeneticAlgorithms）则是一种适合于在大量的可行解中搜索最优（或次优）解的有效算法。二、遗传算法特点介绍:遗传算法(GeneticAlgorithm,GA)是1962年Holland教授首次提出了GA算法的思想是近点，通过自然选择、遗传、变异等作用机制，实现各个个体的适应性的提高。基本遗传算法求解步骤：Step1参数设置：在论域空间U上定义一个适应度函数f，给定种群规模，交叉率Pc和变异率P，代数T；mStep2初始种群：随机产生U中的N个染色体s,s,…,s，组成初始种群={s,s,…,s，12N12N置代数计数器t=1；3计算适应度S)；Step4判断：若终止条件满足，则取S中适应度最大的染色体作为所求结果，算法结束。Step5选择-复制：按选择概率Px所决定的选中机会，每次从S中随机选定1个染色体并i将其复制，共做N次，然后将复制所得的N个染色体组成群体S；1Step6交叉：按交叉率P所决定的参加交叉的染色体数c，从S中随机确定c个染色体，c1配对进行交叉操作，并用产生的新染色体代替原染色体，得群体S；2Step7变异：按变异率P所决定的变异次数m，从S中随机确定m个染色体，分别进行m2变异操作，并用产生的新染色体代替原染色体，得群体S；3Step8更新：将群体S作为新一代种群，即用S代替，t=t，转步3；33遗传算法是一种仿生算法,即模拟生命演化的算法，它从一个代表问题初始解的初始种群出发,不断重复执行选择,杂交和变异的过程,使种群进化越来越接近某一目标既最优,选择、杂交和变异的过程即是在超空间中进行点集之间的某种变换,通过信息交换使种群不断变化，,适者生存”的原理激励好的结构,同时寻找更好的结构,作为一种随机的优化与搜索方法,遗传算法有着其鲜明的特点。—遗传算法一般是直接在解空间搜索,而不像图搜索那样一般是在问题空间搜索,最后才找到解如果搜索成功的话。—遗传算法的搜索随机地始于搜索空间的一个点集,而不像图搜索那样固定地始于搜索空间的初始节点或终止节点,所以遗传算法是一种随机搜索算法。—遗传算法总是在寻找优解(最优解或次优解),而不像图搜索那样并非总是要求优解,而一般是设法尽快找到解当然包括优解),所以遗传算法又是一种优化搜索算法。—遗传算法的搜索过程是从空间的一个点集种群)到另一个点集(种群)的搜索,而不像图搜索那样一般是从空间的一个点到另一个点地搜索。因而它实际是一种并行搜索,适合大规模并行计算,而且这种种群到种群的搜索有能力跳出局部最优解。—遗传算法的适应性强,除需知适应度函数外,几乎不需要其他的先验知识。—遗传算法长于全局搜索,它不受搜索空间的限制性假设的约束,不要求连续性,能以很大的概率从离散的、多极值的、含有噪声的高维问题中找到全局最优解。使用基本遗传算法解决0-1背包问题：三、1:打开数据文件2:设置程序运行主界面3:调用初始化种群模块3-1:按照一定的种群规模和染色体长度以基因为单位用随机产生的0-1对个体赋值3-2:调用计算适应度函数4:以最大进化代数为循环终止条件开始进行循环4-1:调用产生新一代个体的函数4-1-1:调用选择函数4-1-2:调用交叉函数4-1-3:调用变异函数4-1-4:调用计算适应度函数5:调用计算新一代种群统计数据函数6:调用输出新一代统计数据函数7:返回到第四步,直至循环结束基本遗传算法解决0-1背包问题存在的不足：四、1.对于过程中不满足重量限制条件的个体的处理在用基本遗传算法解决0-1合遗传算法的思想。具体做法为：在程序中加入一个变量保存每代的最优解，当前代在进行选择、复制、交叉、变异后如果有不满足约束条件的个体，则在种群更新时采用这个最优值作为替代。具体做法为：在每代遗传后通过函数FindBestandWorstIndividual()找到当前最优值并保存bestindividual中，在计算适应度函数中加入：其中w为当前个体的总重量，KW为背包最大承重量，X[i]表示种群中第i个个体，bestindividual为保存的个体最优解。2.对于交换率和变异率的理解和处理方法根据遗传算法的基本步骤的交叉和变异操作Step6交叉：按交叉率P所决定的参加交叉的染色体数c，从S中随机确定c个染色体，c1配对进行交叉操作，并用产生的新染色体代替原染色体，得群体S；2Step7变异：按变异率P所决定的变异次数m，从S中随机确定m个染色体，分别进行m2变异操作，并用产生的新染色体代替原染色体，得群体S；可以有两种处理方法：3其一，采用先确定数目在随机选取的方法，步骤如下：对于交叉操作：1,根据交叉率确定应该交叉的个体数目n对于变异操作：1,根据变异率确定应该变异的染色体数目n2,在种群中进行n次循环2-1随机选中种群中的一个个体a2-2随机选中种群中异于a的一个个体b2,在种群中进行n次循环2-1随机选中种群中的一个个体的染色体a2-2随机选中染色体a的某位基因2-3对进行0-1互换变异2-3随机确定交叉位数2-4进行交叉其二，采用对每个操作单元分别进行特定概率下处理的方法，步骤如下：1,SS1,SS2,X2,做NN作pp与pqq与qpq1中确定的需要操作的数目n后，总体上是保证了交叉或者变异的数目，但不是对于每一个个体而言的，因而会出现有的个体被选择交叉或者变异多次而有的没有机会交叉或者变异的情验证，以确定是否变异或者交叉。在程序中具体的实现方法体现在交叉和变异函数中：qw1.对于算法早熟性的分析及解决方法出现算法收敛于局部最优解的现象，称为早熟现象。早熟现象的可能解法：1）通过提高变异率来增加种群的多样性，以期更优解的出现，这也是最简单基本遗传算法中不添加相关操作的情况下唯一的一种方法，然而这种方法有明显的弊端：在提高变异率获得多样性种群的同时，个体变异的机会增加，使得较优解发生变异，从而遗传算法丧失了其优于其它算法的优越性，所以这种方法不是很好地解决方法。2）引入多样性衡量和处理基本思路：在出现进化停滞现象时要引入新的个体来增强种群的多样性。做法：1,判断是否达到早熟现象对于种群中Ssame,如果same达到一定的2,早熟现象的处理，即引入新的个体。处理过程中应该不违反适者生存的原则，所以应该保留较好的个体，所以首先选中适应度最小的打破早熟现象的新个体。理论值大小就可以认为达到了早熟现象。具体实现见函数：voidcheckalike(void)2.一种最优解只向更好进化方法的尝试基本思路为：每一组的最优解是一个独特的个体，我们求解的问题最终的最优解或者近它个体，而保证种群一定会向更好的方向进化。做法在交叉后和变异后调用以下函数判断：{}五、改进的遗传算法解决0-1背包问题：1、参数设置：SNT2个体的表示和染色体编码用变量i代表物件,i=1,2,,n定义变量xi，其含义为：xi=1表示：第i个物件被选入背包,xi=0表示第i个物件没有被选入背包。考虑n个物件的选择与否,就可以得到一个长度为n的0,1序列。由此可见遗传算法应用于上述背包问题时,采用简单二进制编码较为适宜1每一组编码即为某一个个体的基因表示,称其为染色体,染色体长度取决于待分配的物件的个数n.在编码形式的表示方法中,形如二进制编码10010101表示为一个待分配的物件的个数为8（编码长度）的一个背包问题的一个解,则该个体对应于选择了物件1,4,6,8，即第1,4,6,8个物品被放入了背包。用数据格式表示为：{2产生初始种群n个待分配的物件随机产生S个长度为n的二进制串,即种群中个体的染色体编码的每一位按等概率在0与1中选择S指的是种群规模,即种群中的个体数目.voidGenerateInitialPopulation(void);//初始种群3适应度函数背包内物件的总重量为a1x1+a2x2+,anxn,物件的总价值为c1x1+c2x2+,+cnxn0-1背包问题中采用每个个体的总价值作为适应度，在满足背包容量的条件下，价值越大，适应度越高。所以适应度求解方法为：fi=c1x1+c2x2+,+cnxn(当ta1x1+a2x2+,+anxn<=c，xj=0,1)考虑到会有不不满足容量条件的个体则：fi=0(当a1x1+a2x2+,+anxn>c，xj=0,1)可能为零,所以当随机产生的某个个体违背约束条件时,通过把其适应度函数值罚为0而达到淘汰该个体的目的。4选择-复制操作参照适应度函数值和约束条件用赌轮选择法进行模拟，具体为:(1)根据适应度函数值和约束条件,罚掉部分个体（前述不满足容量条件的个体）(2)对于满足约束条件的个体,根据适应度函数值计算个体被选中的概率,称为选择概率：公式为:P=p(称为染色体xi=1,2,…,的选择概率i(3)根据轮盘赌累计公式为：iqP(x)称为染色体xi=1,2,…,的积累概率ijij1(4)对已得到的累计概率作如下处理，完成选择操作：1）在［0,1］区间内产生一个均匀分布的伪随机数r。2）若r≤q1,则染色体x1被选中。31<r≤qk(2≤k≤N),则染色体xkn个个体,要进行n次选择,所以产生n个[0,1]之间的随机数,相当于转动n次轮盘,获得n次转盘停止时的指针位置,指针停止在某一扇区,SS5交叉操作:对于每一个个体，根据交叉率P做如下操作：c(1)随机产生一个交叉点的位置(2)随机选取当前代中的两个个体作为父个体(3)根据交叉点的位置,做单点交叉6变异操作:根据变异率Pm(1)随机产生变异点的位置(2)在变异点位置作0-1翻转8、算法终止stop=一般情况下这个最优值达不到，一旦程序在执行过最优解，结束。如果程序的最优值达不到理想情况下的的种群中找到一个最好的解作为本问题的最优解，程序结束。4算例1.小规模问题的算例：算例1-1：设定物品价值value={50,30,60,80,20}重量weight{35,40,40,20,15}背包的最大承重量为100遗传算法中参数：群体大小S=5，交叉率变异率Pm=0.05,最大换代次数T=20,通过多次试验比较本文改进后遗传算法和其他得到结果如下表所示：