关于西电人工智能大作业

1、人工智能大作业学生：021151* 021151*时间：2013年12月4号一启发式搜索解决八数码问题1. 实验目的问题描述：现有一个3*3的棋盘，其中有0-8一共9个数字，0表示空格，其他的数字可以和0交换位置（只能上下左右移动）。给定一个初始状态和一个目标状态，找出从初始状态到目标状态的最短路径的问题就称为八数码问题。例如：实验问题为283104765123804765到目标状态：从初始状态： 要求编程解决这个问题，给出解决这个问题的搜索树以及从初始节点到目标节点的最短路径。2. 实验设备及软件环境利用计算机编程软件Visual C+ 6.0，用C语言编程解决该问题。3. 实验方法(1).

2、算法描述：.把初始节点S放到OPEN表中，计算，并把其值与节点S联系起来。.如果OPEN表是个空表，则失败退出，无解。.从OPEN表中选择一个值最小的节点。结果有几个节点合格，当其中有一个为目标节点时，则选择此目标节点，否则就选择其中任一节点作为节点。.把节点从OPEN表中移出，并把它放入CLOSED的扩展节点表中。.如果是目标节点，则成功退出，求得一个解。.扩展节点，生成其全部后继节点。对于的每一个后继节点： a.计算。 b.如果既不在OPEN表中，也不在CLOSED表中，则用估价函数把它添加入OPEN表。从加一指向其父辈节点的指针，以便一旦找到目标节点时记住一个解答路径。 c.如果已在OP

3、EN表或CLOSED表上，则比较刚刚对计算过的值和前面计算过的该节点在表中的值。如果新的值较小，则 I.以此新值取代旧值。 II.从指向，而不是指向它的父辈节点。 III.如果节点在CLOSED表中，则把它移回OPEN表。 转向，即GO TO 。 (2).流程图描述： (3).程序源代码：#include <stdio.h>#include<stdlib.h>struct nodeint number33;/用二维数组存放8数码 int W;/W表示与目标状态相比错放的数码数int Depth;/记录当前节点的深度struct node *parent;/指向父节点的指

4、针struct node *next;/指向链表中下一个节点的指针;int CounterW(int Number33)/函数说明：计算当前状态与目标状态的W值int i,j;int W=0;int Desnode33=1,2,3,8,0,4,7,6,5;for(i=0; i<3; i+)for(j=0; j<3; j+)if(Numberij != Desnodeij)W+; return W;void PrintNode(node *A)int i,j;for(i=0; i<3; i+)for(j=0; j<3; j+)printf("%d ",

5、A->numberij);printf("n");printf("n");int CheckNode(node *open, node *close, int a33)/检验该节点状态是否出现过的子程序int CheckFlag=0;int flag1,flag2;node *p=open;node *q=close;while(p != NULL) flag1=0;for(int i=0; i<3; i+)for(int j=0; j<3; j+)if(aij=p->numberij)flag1+;if(flag1 = 9)br

6、eak;elsep=p->next;while(q != NULL)flag2=0;for(int i=0; i<3; i+)for(int j=0; j<3; j+)if(aij = q->numberij)flag2+;if(flag2 = 9)break;elseq=q->next;if(flag1=9) | (flag2=9)CheckFlag=1;/如果出现过，置标志位为1return CheckFlag;struct node *FindNextNode(node *Prenode, node *open, node *close) /扩展Prenod

7、e指向的节点，并将扩展所得结点组成一条单链表int i,j,m,n; /循环变量int temp; /临时替换变量int flag=0; int a33;/临时存放二维数组struct node *p, *q, *head; head=(node *)malloc(sizeof(node);/head指向该链表首结点，并且作为返回值p=head;q=head;head->next=NULL;/初始化for(i=0;i<3;i+)/找到二维数组中0的位置for(j=0;j<3;j+)if(Prenode->numberij=0)flag=1;break;if(flag=1

8、)break;/根据0的位置的不同，对a进行相应的变换 for(m=0;m<3;m+)/将Prenode->number赋给afor(n=0;n<3;n+)amn=Prenode->numbermn; if(i+1<=2)/情况1，0向下移temp=aij; aij=ai+1j; ai+1j=temp;int CheckNum=CheckNode(open, close, a); if(CheckNum = 0)/若该结点未出现过则执行下面的操作 q=(node *)malloc(sizeof(node); for(m=0;m<3;m+)/将a赋给扩展节点q

9、->number for(n=0;n<3;n+) q->numbermn=amn; PrintNode(q); q->parent=Prenode; q->Depth=q->parent->Depth+1;/子结点的深度等于其父结点深度加1 q->W=CounterW(q->number); q->next=NULL; p->next=q;/扩展节点插入head链表 p=p->next; for(m=0;m<3;m+)/将Prenode->number重新赋给afor(n=0;n<3;n+)amn=Pre

10、node->numbermn;if(i-1>=0)/情况2,0向上移temp=aij; aij=ai-1j; ai-1j=temp;int CheckNum=CheckNode(open, close, a); if(CheckNum = 0)/若该结点未出现过则执行下面的操作 q=(node *)malloc(sizeof(node); for(m=0;m<3;m+)/将a赋给q->number for(n=0;n<3;n+) q->numbermn=amn; PrintNode(q); q->parent=Prenode; q->Depth=

11、q->parent->Depth+1; q->W=CounterW(q->number); q->next=NULL; p->next=q; p=p->next; for(m=0; m<3; m+)for(n=0; n<3; n+)amn=Prenode->numbermn;if(j-1>=0)/情况3,0向左移 temp=aij; aij=aij-1; aij-1=temp;int CheckNum=CheckNode(open, close, a); if(CheckNum = 0)/若该结点未出现过则执行下面的操作 q=(

12、node *)malloc(sizeof(node); for(m=0; m<3; m+)/将a赋给q->number for(n=0; n<3; n+) q->numbermn=amn; PrintNode(q); q->parent=Prenode; q->Depth=q->parent->Depth+1; q->W=CounterW(q->number); q->next=NULL; p->next=q; p=p->next; for(m=0;m<3;m+)for(n=0;n<3;n+)amn=Pr

13、enode->numbermn;if(j+1<=2)/情况4,0向右移temp=aij; aij=aij+1; aij+1=temp;int CheckNum=CheckNode(open, close, a); if(CheckNum = 0)/若该结点未出现过则执行下面的操作 q=(node *)malloc(sizeof(node); for(m=0; m<3; m+)/将a赋给q->number for(n=0; n<3; n+) q->numbermn=amn; PrintNode(q); q->parent=Prenode; q->D

14、epth=q->parent->Depth+1; q->W=CounterW(q->number); q->next=NULL; p->next=q; p=p->next; head=head->next;return head; node *insert(node *open,node *head) /将head链表的结点依次插入到open链表相应的位置， /使open表中的结点按从小到大排序。函数返回open指针node *p,*q;/p、q均指向open表中的结点，p指向q所指的前一个结点int flag=0;if(open=NULL) &

15、amp;& (head != NULL)/初始状态，open表为空 /首先将head表第一个结点直接放入open表中open=head;q=head; head=head->next;q->next=NULL;if(open != NULL) && (open->next=NULL) &&(head != NULL)/open表中只有一个元素q=open; if(head->W + head->Depth) < (open->W + open->Depth)/若后一结点的f值小于首结点，则将它插入到首结点位

16、置open=head;head=head->next;open->next=q; else/或者第二个结点的位置 q->next=head; head=head->next; q=q->next; q->next=NULL;p=open;while(head!=NULL)q=open;if(head->W + head->Depth) < (open->W + open->Depth) /插入到表头open=head;head=head->next;open->next=q;continue;else q=q->

17、;next; p=open; /否则，q指像第二个结点，p指向q前一个结点while(q->next!=NULL) /将head的一个结点插入到链表中（非表尾的位置）if(q->W < head->W) q=q->next;p=p->next;elsep->next=head;head=head->next;p->next->next=q; break;if(q->next=NULL)/将head的一个结点插入到表尾或倒数第二个位置if(q->W + q->Depth) < (head->W + head

18、->Depth)q->next=head;head=head->next;q->next->next=NULL;elsep->next=head;head=head->next;p->next->next=q;return open; void main()int i,j;int key=0;node FirstNode; node *open, *close;node *p, *r;node *NodeList;printf("请输入初始状态的8数码（按每行从左往右依次输入,用0表示空格）：n"); for(i=0;

19、i<3; i+)for(j=0; j<3; j+)scanf("%d",&FirstNode.numberij);printf("n");printf("搜索树为：n");for(i=0; i<3; i+) for(j=0; j<3; j+)printf("%d ",FirstNode.numberij);printf("n");printf("n"); FirstNode.parent=(node *)malloc(sizeof(node);

20、 FirstNode.Depth=0;/开始结点深度为零 FirstNode.W=CounterW(FirstNode.number); open=&FirstNode; p=&FirstNode; if(open->W = 0)/该结点的状态与目标结点相同 printf("该结点已为目标结点状态！n"); return; r=&FirstNode; close=&FirstNode;r->next=NULL; open=NULL; NodeList=FindNextNode(r,open,close);/NodeList指向新扩

21、展出来的链表 open=insert(open,NodeList);/将扩展出来的结点插入到open表中 while(open != NULL) r->next=open;/将open表的第一个元素加到close表，r始终指向close表的最后一个元素 open=open->next; r=r->next; r->next=NULL; if(r->W = 0) key=1; printf("n启发式搜索成功！n"); break; NodeList=FindNextNode(r,open,close);/对close表最后一个结点进行扩展，扩展

22、得到的链表接到head表 open=insert(open,NodeList);/将扩展的结点按顺序插入到open表中if(key = 1) p=close; printf("最优搜索过程如下：n"); printf("结点深度为:%dn",FirstNode.Depth); printf("-n"); while(p!=NULL) for(i=0; i<3; i+) for(j=0; j<3; j+) printf("%d ",p->numberij); printf("n"

23、); printf("n"); p=p->next; if(p != NULL) printf("结点深度为:%dn",p->Depth); printf("-n"); else printf("查找失败，该问题无解！n"); 4. 实验结果搜索树为：最短路径为：5. 实验分析本次实验采用启发式搜索，利用C语言编写程序实现八数码问题的求解。采用简单的估价函数： 其中是搜索树中节点的深度；用来计算对应于节点的数据库中错放的棋子个数。例如初始节点的估价函数值为3。 估价函数能够提供一个评定候选扩展节点的方法

24、，以便确定哪个节点时最有可能在通向目标的最佳路径上。这样选择正确的估价函数，可以减少扩展节点个数，对于实验所给的初始节点和估价函数，只用扩展11个节点就能找到目标节点；相比于盲目搜索可以减少被扩展的节点数，减少很多空间占用和时间损耗。 利用启发信息来决定哪一个是下一步要扩展的节点，这种搜索总是选择“最有希望”的节点作为下一步被扩展的节点。这实际上是通过估价函数值的大小重排OPEN表，小的一直排在OPEN表的前面。每次取OPEN表的第一个节点放到CLOSED表中进行扩展，这样一步步靠近目标节点，直到最后找到目标节点，停止扩展。6. 结论正确选择估价函数对确定搜索结果具有决定性作用。使用不能识别某

25、些节点真是希望的估价函数会形成非最小代价路径；而使用一个过多地估计了全部节点希望的估价函数，又会扩展过多的节点。在选对估价函数的前提下，启发式搜索能准确识别有希望和没有希望的节点，从而很快扩展到目标节点，找到最短路径。在本次实验中如果选择估价函数值为（用来计算对应于节点的数据库中错放的棋子个数），将会扩展更少的节点，更加快的找到到达目标节点的最短路径。二英文期刊翻译Adaptive Evolutionary Artificial NeuralNetworks for Pattern Classification自适应进化人工神经网络模式分类摘要：这篇文章提出了一种新的进化方法称为混合进化人工神

26、经网络(HEANN),同时提出进化人工神经网络(ANNs)拓扑结构和权重。进化算法(EAs)具有较强的全局搜索能力且很可能指向最有前途的领域。然而,在搜索空间局部微调时，他们效率较低。HEANN强调全局搜索的平衡和局部搜索的进化过程，通过调整变异概率和步长扰动的权值。这是区别于大多数以前的研究，那些研究整合EA来搜索网络拓扑和梯度学习来进行权值更新。四个基准函数被用来测试的HEANN进化框架。此外,HEANN测试了七个分类基准问题的UCI机器学习库。实验结果表明在少数几代算法中，HEANN在微调网络复杂性的性能是优越的。同时，他还保留了相对于其他算法的泛化性能。简介：人工神经网络(ANNs)已

27、经成为一种强大的工具被用于模式分类1,2。ANN拓扑优化和连接权重训练经常被单独处理。这样一个分治算法产生一个不精确的评价选择的神经网络拓扑结构。事实上,这两个任务都是相互依存的且应当同时解决以达到最佳结果。 一个模式分类的关键任务是设计一个紧凑和广义ANN拓扑。为特定的问题选择一个适当的ANN拓扑是至关重要的，由于ANN泛化相关性信息处理能力和ANN拓扑的强关联能力。过度的小型网络的大小表明问题不能学得很好,而一个特别大的网络规模将导致过度学习和差的推广性能。耗时的实验训练方法和爬山建设性或修剪算法3-7用于设计一个ANN架构，对于一个给定的任务只有探索小型建筑子集，或往往是停在结构局部最优

28、解。相关的神经网络是一个流行的8建设性算法而用于构造有多个维层的ANN拓扑。新的隐藏节点一个接一个的被添加进来且都与每一个现有的隐藏节点在当前的网络连接。因此,网络可以被视为拥有多个可以形成一个级联结构的集中度值层。然而,网络是倾向于结构局部最优解由于它具有建设性的行为。设计一个ANN拓扑使用进化算法(EAs)已经成为一种流行的方法来克服建设性或修剪方法9-13的缺点。它有很强的全局搜索能力,可以有效地搜索通过接近完整的ANN拓扑类。许多工作已经致力于进化神经网络ANN拓扑结构。两个主要的方法来发展ANN拓扑的文献报告是没有重权值和ANN拓扑同步进化的两个拓扑和权重。演化的一个无权值得ANN拓

29、扑,必须从一组随机的初始权重训练评估其适应性。姚和刘11指出,这个适应性评价方法很嘈杂因为一个显性型的适应性是用来代表隐形型的适应性。虽然的进化ANN拓扑的适应性可以通过运行多个不同的随机初始权重而得到的平均结果来估计,为适应性计算评价时间是急剧增加。因此,只有小ANN拓扑在14和15中被演化。同时进化的ANN拓扑和权重,权重信息拓扑和编码在每个个体是独立的。因此嘈杂的适应性评价问题可以被缓解。一个突出的工作称为EPNet被姚和刘11引入，那是一个同时进化ANN拓扑和权重例子。姚和刘用混合训练来进化ANN权重测试。梯度学习和模拟退火都纳入进化过程演变的ANN权重。Martínez-E

30、studillo等人在最好的独立ANN下使用梯度学习方法演变权重。他们用聚类算法划分的个体在总数中分成几个属于同一区域的吸引力集群。然而,由于灵敏度高的反向传播算法对初始权重，使用梯度学习方法如反向传播算法进化ANN权重引起噪声适应性评价。Palmes et al12使用基于突变EA在一个进化的ANN下解决这个问题。其他作品也集中在同步进化的ANN拓扑和权重。Anget al13介绍增长概率允许网络演变到合适的大小。Angeline et al9使用参数突变和结构性突变进化安重量、隐藏节点和网络链接。Jian和Yugeng10用进化规划(EP)进化体系结构和前馈神经网络的权重和递归神经网络。L

31、iang et al17提出了一种改进遗传算法的进化神经网络的结构和参数。Gutiérrez et al。18使用模拟退火控制参数突变和五个结构突变进化径向基函数(RBF)神经网络。所有这些以前作品的目的是产生一个紧凑和广义的ANN。通常,拓扑的一个ANN可以编码到一个染色体编码方案来使用直接或间接编码方案。在直接编码方案中,所有的ANN拓扑编码直接进入一个染色体，这是通过使用二进制表示，而这表明存在网络连接和隐藏的节点。间接编码方案只有编码的一些重要参数的一个ANN拓扑,如数量的隐藏层和隐藏的节点。其他细节ANN拓扑是预定义的或指定的一组确定的发展规则19。直接编码方案易于实现,适

32、合于精确的搜索。尽管间接编码方案可以减少染色体的长度,它可能不适合找一个紧凑的具有良好的泛化能力的ANN19。在本文中,一个直接编码方案是用来代表ANN拓扑。进化的ANN拓扑和权重可以帮助缓解此问题的嘈杂的评价。然而,仅仅依靠EA来进化神经网络是相当低效执行本地搜索。进一步训练使用传统的梯度下降方法进化后可以是一个简单的方法来调整网络。认为情势的过早收敛在进化过程中,ANN发现经过进一步培训可能不是最优的。其他方法如使用退火温度指导重量扰动步长9和调度的突变概率12的个人网络的种群可以被认为是初步指南向本地搜索,但没有不同的方向已经被提供。因此,EA应该引导正确维持两者之间的平衡整个搜索空间的

33、探索和开发的重要区域。出于平衡的重要性，在进化过程和同步进化的ANN拓扑和权重下的全局和本地搜索,本文提出了一种新的进化方法称为混合进化人工神经网络(HEANN)，同时发展ANN拓扑和权重。此外,HEANN演示了一个平衡的全局搜索和局部搜索通过引入一个在演化工程中产生新颖的自适应变异技术。而不是使用传统的方法来降低突变概率或步长大小,HEANN使用信息从种群引导进化过程将逐渐向全局搜索到本地搜索过渡。首先,概括损失(GL)在种群是用来适应变异概率和步长。第二，适应性价值的每个个体的种群是用来确定突变的严重性，在给定个体的种群。在本文中,主要有两个因素：网络拓扑优化和进化能力。一种很流行的方法,

34、优化两个或两个以上的目标是基于Pareto优势20-22。然而,查找和估算Pareto适应度的计算成本会增，当优化目标数量增加时21。另一个流行的方法是基于多目标学习10,12、20,它聚合了几个目标变成一个标量成本函数。在这种情况下,该方法假设凸性的Pareto。这种方法是用在当前的实现。其余的部分组织如下：第二部分详细的描述了HEANN和每个成分。第三部分分析了所提出的自适应变异技术在ANN拓扑(添加或删除节点,连接)下的影响,这种技术平衡全局和局部搜索的进化过程。第四节显示了结果的新的自适应进化框架四个基准函数。第五部分包含实验结果的HEANN。第六节提出了讨论结果。最后,第七节总结了本

35、文的工作。结论：本文描述了一种新的方法来同时进化ANN拓扑和权重。解决的弱点在精细调谐，ANN EAs,HEANN使用一种自适应变异策略来改进本地搜索功能，在设计神经网络方面。GL和适应性价值被认为在演化过程下帮助了突变适应。此外,全局和局部的突变策略的分析研究HEANN。 首次测试是针对基准函数来证明提高局部搜索能力和能够摆脱局部极值的能力。实验结果表明，HEA比传统的EA好。HEANN是用来测试七真是世界分类问题。总的来说，实验结果显示了在各方面的优越性HEANN，相比其他算法。非常聚合的人工神经网络可以由HEANN产生与其自适应变异策略。此外,HEANN需要更少的后代能达到良好的结果。唯一的缺点是，它有很多可以由用户定义的HEANN参数。然而，HEANN对这些参数不是很敏感。不同的突变测试参数结果表明，HEANN对于这些参数不是很敏感，但他的这些价值不应过低的被估计。如果没有需要在进化过程中集中计算的梯度学习而使用一个更大的种群规模也是可行的。最终的种群肯定包含更多的信息比