人工智能课程设计汇报.ppt

《人工智能课程设计汇报.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、基于遗传算法的TSP问题产生式系统的应用by计算机科学与技术1401张凯歌基于遗传算法的TSP问题TSP问题，即旅行商问题。假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。遗传算法求解TSP的基本步骤（1）种群初始化。个体编码方法有：二进制编码和实数编码。每一条染色体就是一种编码，在解决TSP问题过程中个体编码方法为实数编码。对于TSP问题，实数编码为1-n的实数的随机排列。初始化的参数有城市个数，种群规模、进化次数、交叉

2、概率、变异概率遗传算法求解TSP的基本步骤（2）适应度函数。在TSP问题中，任意两个城市之间的距离D(i,j)已知，每个染色体（即n个城市的随机排列）可计算出总距离。因此可将一个随机全排列的总距离的倒数作为适应度函数，即距离越短，适应度函数越好，满足TSP要求。遗传算法求解TSP的基本步骤（3）选择操作。采用累计适应度最高的选择策略，即适应度越好的个体被选择的概率越大，同时在选择中保存适应度最高的个体。遗传算法求解TSP的基本步骤（4）交叉操作。相对于个体，随机选择两个个体，随机生成一个交叉位点。交换对应位置两侧的基因片段，同时确保每个个体依然是1-

3、n的随机排列。遗传算法求解TSP的基本步骤（5）变异操作。随机选取个体，随机选取个体的两个基因，进行交换以实现变异操作。流程图核心代码#definenum_C10//城市个数#defineN10//群体规模#definepc0.9//交叉概率#definepm0.1//变异概率#definegenmax500//最大遗传代数structgene//染色体结构{intpath[num_C];//路径doublecost;//个体代价值doublefitness;//个体适应度doubleprobability;//适应度doubleaccumulati

4、on;//幸存概率};核心代码voidSelect(structgenegroup[N])//选择{inti,j;intt=1;doublek;Cprobability(group);Caccumulation(group);for(i=0;i

5、*q)//交叉{inti,j,cross_point;intson1[num_C],son2[num_C];cross_point=Randominteger1(1,num_C-1);//随机生成交叉位点for(i=0;ipath[i];//子代后半部分来自父代qfor(i=cross_point;i

6、arch_son(son1,q->path[j])==1){son1[i]=q->path[j];break;}核心代码voidVaration(structgenegroup[N])//变异{inti,j,k,temp,c;structgene*p;doubleflag;for(c=1;c

7、1(0,num_C-1);//确定发生变异的位p=&group[i];//变异temp=p->path[j];p->path[j]=p->path[k];p->path[k]=temp;Calculate_cost(p);//重新计算变异后路径的代价}}}运行结果遗传算法属于启发式算法,最终只能获得最优解的一个近似解。每次的运行结果也是有差别的。产生式动物识别系统设计并实现具有15条规则能自动识别7种动物的产生式系统。知识库与控制系统相互独立，系统完成后除了能识别已有的7种动物外，按产生式知识表示方法向知识库中添加、修改新的知识后，系统能在不修改控制

8、系统程序的情况下仍然能正确识别。设计知识库知识用If前提then结论的形式来表示<知识库><事实><条件>1