《人工智能课程设计汇报》由会员分享，可在线阅读，更多相关《人工智能课程设计汇报（24页珍藏版）》请在金锄头文库上搜索。
1、基于遗传算法的TSP问题产生式系统的应用by计算机科学与技术1401张凯歌基于遗传算法的TSP问题TSP问题，即旅行商问题。假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。遗传算法求解TSP的基本步骤（1）种群初始化。个体编码方法有：二进制编码和实数编码。每一条染色体就是一种编码，在解决TSP问题过程中个体编码方法为实数编码。对于TSP问题，实数编码为1-n的实数的随机排列。初始化的参数有城市个数，种群规模、进化次数、交叉概率、变异概率遗传算法求解TSP的基本步骤（
2、2）适应度函数。在TSP问题中，任意两个城市之间的距离D(i,j)已知，每个染色体（即n个城市的随机排列）可计算出总距离。因此可将一个随机全排列的总距离的倒数作为适应度函数，即距离越短，适应度函数越好，满足TSP要求。遗传算法求解TSP的基本步骤（3）选择操作。采用累计适应度最高的选择策略，即适应度越好的个体被选择的概率越大，同时在选择中保存适应度最高的个体。遗传算法求解TSP的基本步骤（4）交叉操作。相对于个体，随机选择两个个体，随机生成一个交叉位点。交换对应位置两侧的基因片段，同时确保每个个体依然是1-n的随机排列。遗传算法求解TSP的基本步骤（5）变异操作。随机选取个体，随机选取个体的两
3、个基因，进行交换以实现变异操作。流程图核心代码#definenum_C10/城市个数#defineN10/群体规模#definepc0.9/交叉概率#definepm0.1/变异概率#definegenmax500/最大遗传代数structgene/染色体结构intpathnum_C;/路径doublecost;/个体代价值doublefitness;/个体适应度doubleprobability;/适应度doubleaccumulation;/幸存概率;核心代码voidSelect(structgenegroupN)/选择inti,j;intt=1;doublek;Cprobability(
4、group);Caccumulation(group);for(i=0;iN-1;i+)k=Randominteger(0,1);for(j=0;jN-1;j+)if(kgroupj.accumulation)Copy_gene(&groupj,&groupt);t+;break;voidCross(structgene*p,structgene*q)/交叉inti,j,cross_point;intson1num_C,son2num_C;cross_point=Randominteger1(1,num_C-1);/随机生成交叉位点for(i=0;inum_C;i+)son1i=-1;son2
5、i=-1;/子代1前半部分直接从父代p复制for(i=0;ipathi;/子代后半部分来自父代qfor(i=cross_point;inum_C;i+)for(j=0;jpathj)=1)son1i=q-pathj;break;核心代码voidVaration(structgenegroupN)/变异inti,j,k,temp,c;structgene*p;doubleflag;for(c=1;cN;c+)flag=Randominteger(0,1);if(flagpathj;p-pathj=p-pathk;p-pathk=temp;Calculate_cost(p);/重新计算变异后路径的
6、代价运行结果遗传算法属于启发式算法,最终只能获得最优解的一个近似解。每次的运行结果也是有差别的。产生式动物识别系统设计并实现具有15条规则能自动识别7种动物的产生式系统。知识库与控制系统相互独立，系统完成后除了能识别已有的7种动物外，按产生式知识表示方法向知识库中添加、修改新的知识后，系统能在不修改控制系统程序的情况下仍然能正确识别。设计知识库知识用If前提then结论的形式来表示1:有毛发2:产奶3:有羽毛4:会飞5:会下蛋6:吃肉7:有犬齿8:有爪9:眼盯前方10:有蹄11:反刍12:黄褐色13:有斑点14:有黑色条纹15:长脖16:长腿17:不会飞18:会游泳19:黑白二色20:善飞设计
7、知识库21:哺乳类22:鸟类23:食肉类24:蹄类25:金钱豹26:虎27:长颈鹿28:斑马29:鸵鸟30:企鹅31:信天翁设计知识库有毛-哺乳类产奶-哺乳类有羽毛-鸟类会飞,会下蛋-鸟类哺乳类,吃肉-食肉类有犬齿,有爪,眼盯前方-食肉类哺乳类,有蹄-蹄类哺乳类,反刍-蹄类食肉类,黄褐色,有斑点-金钱豹食肉类,黄褐色,有黑色条纹-虎蹄类,长脖,长腿,有斑点-长颈鹿蹄类,有黑色条纹-斑马鸟类,长脖,长腿,会飞-鸵鸟鸟类,会游泳,黑白二色,会飞-企鹅鸟类,善飞-信天翁规则符号化1-21/有毛-哺乳类2-21/产奶-哺乳类3-22/有羽毛-鸟类4,5-22/会飞,会下蛋-鸟类21,6-23/哺乳类,
8、吃肉-食肉类7,8,9-23/有犬齿,有爪,眼盯前方-食肉类21,10-24/哺乳类,有蹄-蹄类21,11-24/哺乳类,反刍-蹄类23,12,13-25/食肉类,黄褐色,有斑点-金钱豹23,12,14-26/食肉类,黄褐色,有黑色条纹-虎24,15,16,13-27/蹄类,长脖,长腿,有斑点-长颈鹿24,14-28/蹄类,有黑色条纹-斑马22,15,16,4-29/鸟类,长脖,长腿,会飞-鸵鸟22,18,19,4-30/鸟类,会游泳,黑白二色,会飞-企鹅22,20-31/鸟类,善飞-信天翁核心代码stringfactfact_num=有毛发,产奶,有羽毛,会飞,会下蛋,吃肉,有犬齿,有爪,眼
9、盯前方,有蹄,反刍,黄褐色,有斑点,有黑色条纹,长脖,长腿,不会飞,会游泳,黑白二色,善飞,哺乳类,鸟类,食肉类,蹄类,金钱豹,虎,长颈鹿,斑马,鸵鸟,企鹅,信天翁;核心代码intrule_prerequisiterule_numrule_volume=1,0,0,0,2,0,0,0,3,0,0,0,4,5,0,0,21,6,0,0,7,8,9,0,21,10,0,0,21,11,0,0,23,12,13,0,23,12,14,0,24,15,16,13,24,14,0,0,22,15,16,4,22,18,19,4,22,20,0,0;intrule_resultrule_num=21,21,22,22,23,23,24,24,25,26,27,28,29,30,31;核心代码逆向推理函数boolbackward_reasoning(intnum,intmessage);（1）规则集中的规则后件与假设的目标事实进行匹配，得到匹配的规则集合。（2）从匹配规则集合中选择一条规则作为使用规则。（3）将使用规则的前件作为新的假设子目标。重复这个过程，直至个子目标为已知事实后成功结束。核心代码THANKS
