人工智能课程设计汇报

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、体的两个基因，进行交换以实现变异操作。流程图核心代码#define num_c 10 /城市个数#define n 10 /群体规模#define pc 0.9 /交叉概率#define pm 0.1 /变异概率#define genmax 500 /最大遗传代数struct gene /染色体结构 int pathnum_c; /路径 double cost; /个体代价值 double fitness; /个体适应度 double probability; /适应度 double accumulation; /幸存概率;核心代码void select(struct gene groupn)

4、 /选择 int i,j; int t=1; double k; cprobability(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; void cross(struct gene*p,struct gene*q) /交叉 int i,j,cross_point; int son1num_c,son2num_c; cross_point=ra

5、ndominteger1(1,num_c-1); /随机生成交叉位点 for(i=0;inum_c;i+) son1i=-1; son2i=-1; /子代1前半部分直接从父代p复制 for(i=0;ipathi; /子代后半部分来自父代q for(i=cross_point;inum_c;i+) for(j=0;jpathj)=1) son1i=q-pathj; break; 核心代码void varation(struct gene groupn)/变异 int i,j,k,temp,c; struct gene *p; double flag; for(c=1;cn;c+) flag=ra

6、ndominteger(0,1); if(flagpathj;p-pathj=p-pathk;p-pathk=temp;calculate_cost(p);/重新计算变异后路径的代价 运行结果遗传算法属于启发式算法,最终只能获得最优解的一个近似解。每次的运行结果也是有差别的。产生式动物识别系统设计并实现具有15条规则能自动识别7种动物的产生式系统。知识库与控制系统相互独立，系统完成后除了能识别已有的7种动物外，按产生式知识表示方法向知识库中添加、修改新的知识后，系统能在不修改控制系统程序的情况下仍然能正确识别。设计知识库知识用 if 前提 then 结论 的形式来表示1:有毛发 2:产奶 3:

7、有羽毛 4:会飞 5:会下蛋 6:吃肉 7:有犬齿 8:有爪9:眼盯前方 10:有蹄 11:反刍 12:黄褐色13:有斑点 14:有黑色条纹 15:长脖 16:长腿17:不会飞 18:会游泳 19:黑白二色 20:善飞设计知识库21:哺乳类 22:鸟类 23:食肉类 24:蹄类 25:金钱豹 26:虎 27:长颈鹿 28:斑马 29:鸵鸟30:企鹅 31:信天翁设计知识库有毛-哺乳类产奶-哺乳类有羽毛-鸟类会飞,会下蛋-鸟类哺乳类,吃肉-食肉类有犬齿,有爪,眼盯前方-食肉类哺乳类,有蹄-蹄类哺乳类,反刍-蹄类食肉类,黄褐色,有斑点-金钱豹食肉类,黄褐色,有黑色条纹-虎蹄类,长脖,长腿,有斑点-

8、长颈鹿蹄类,有黑色条纹-斑马鸟类,长脖,长腿,会飞-鸵鸟鸟类,会游泳,黑白二色,会飞-企鹅鸟类,善飞-信天翁规则符号化1-21 /有毛-哺乳类2-21 /产奶-哺乳类3-22 /有羽毛-鸟类4,5-22 /会飞,会下蛋-鸟类21,6-23 /哺乳类,吃肉-食肉类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 /蹄类,有黑色条纹

9、-斑马22,15,16,4-29 /鸟类,长脖,长腿,会飞-鸵鸟22,18,19,4-30 /鸟类,会游泳,黑白二色,会飞-企鹅22,20-31 /鸟类,善飞-信天翁核心代码string factfact_num = 有毛发,产奶,有羽毛,会飞,会下蛋, 吃肉,有犬齿,有爪,眼盯前方,有蹄, 反刍,黄褐色,有斑点,有黑色条纹,长脖, 长腿,不会飞,会游泳,黑白二色,善飞, 哺乳类,鸟类,食肉类,蹄类,金钱豹, 虎,长颈鹿,斑马,鸵鸟,企鹅,信天翁 ; 核心代码int rule_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 ; int rule_resultrule_num = 21, 21, 22, 22, 23, 23, 24, 24, 25, 26, 27, 28, 29, 30, 31 ; 核心代码逆向推理函数bool backwa