關于西電人工智能大作業(yè)

1、人工智能大作業(yè)學生：021151* 021151*時間：2013年12月4號一啟發(fā)式搜索解決八數(shù)碼問題1. 實驗目的問題描述：現(xiàn)有一個3*3的棋盤，其中有0-8一共9個數(shù)字，0表示空格，其他的數(shù)字可以和0交換位置（只能上下左右移動）。給定一個初始狀態(tài)和一個目標狀態(tài)，找出從初始狀態(tài)到目標狀態(tài)的最短路徑的問題就稱為八數(shù)碼問題。例如：實驗問題為283104765123804765到目標狀態(tài)：從初始狀態(tài)： 要求編程解決這個問題，給出解決這個問題的搜索樹以及從初始節(jié)點到目標節(jié)點的最短路徑。2. 實驗設備及軟件環(huán)境利用計算機編程軟件Visual C+ 6.0，用C語言編程解決該問題。3. 實驗方法(1).

2、算法描述：.把初始節(jié)點S放到OPEN表中，計算，并把其值與節(jié)點S聯(lián)系起來。.如果OPEN表是個空表，則失敗退出，無解。.從OPEN表中選擇一個值最小的節(jié)點。結果有幾個節(jié)點合格，當其中有一個為目標節(jié)點時，則選擇此目標節(jié)點，否則就選擇其中任一節(jié)點作為節(jié)點。.把節(jié)點從OPEN表中移出，并把它放入CLOSED的擴展節(jié)點表中。.如果是目標節(jié)點，則成功退出，求得一個解。.擴展節(jié)點，生成其全部后繼節(jié)點。對于的每一個后繼節(jié)點： a.計算。 b.如果既不在OPEN表中，也不在CLOSED表中，則用估價函數(shù)把它添加入OPEN表。從加一指向其父輩節(jié)點的指針，以便一旦找到目標節(jié)點時記住一個解答路徑。 c.如果已在OP

3、EN表或CLOSED表上，則比較剛剛對計算過的值和前面計算過的該節(jié)點在表中的值。如果新的值較小，則 I.以此新值取代舊值。 II.從指向，而不是指向它的父輩節(jié)點。 III.如果節(jié)點在CLOSED表中，則把它移回OPEN表。 轉(zhuǎn)向，即GO TO 。 (2).流程圖描述： (3).程序源代碼：#include <stdio.h>#include<stdlib.h>struct nodeint number33;/用二維數(shù)組存放8數(shù)碼 int W;/W表示與目標狀態(tài)相比錯放的數(shù)碼數(shù)int Depth;/記錄當前節(jié)點的深度struct node *parent;/指向父節(jié)點的指

4、針struct node *next;/指向鏈表中下一個節(jié)點的指針;int CounterW(int Number33)/函數(shù)說明：計算當前狀態(tài)與目標狀態(tài)的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)/檢驗該節(jié)點狀態(tài)是否出現(xiàn)過的子程序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;/如果出現(xiàn)過，置標志位為1return CheckFlag;struct node *FindNextNode(node *Prenode, node *open, node *close) /擴展Prenod

7、e指向的節(jié)點，并將擴展所得結點組成一條單鏈表int i,j,m,n; /循環(huán)變量int temp; /臨時替換變量int flag=0; int a33;/臨時存放二維數(shù)組struct node *p, *q, *head; head=(node *)malloc(sizeof(node);/head指向該鏈表首結點，并且作為返回值p=head;q=head;head->next=NULL;/初始化for(i=0;i<3;i+)/找到二維數(shù)組中0的位置for(j=0;j<3;j+)if(Prenode->numberij=0)flag=1;break;if(flag=1

8、)break;/根據(jù)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)/若該結點未出現(xiàn)過則執(zhí)行下面的操作 q=(node *)malloc(sizeof(node); for(m=0;m<3;m+)/將a賦給擴展節(jié)點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;/擴展節(jié)點插入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)/若該結點未出現(xiàn)過則執(zhí)行下面的操作 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)/若該結點未出現(xiàn)過則執(zhí)行下面的操作 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)/若該結點未出現(xiàn)過則執(zhí)行下面的操作 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表中的結點按從小到大排序。函數(shù)返回open指針node *p,*q;/p、q均指向open表中的結點，p指向q所指的前一個結點int flag=0;if(open=NULL) &

15、amp;& (head != NULL)/初始狀態(tài)，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的一個結點插入到表尾或倒數(shù)第二個位置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("請輸入初始狀態(tài)的8數(shù)碼（按每行從左往右依次輸入,用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)/該結點的狀態(tài)與目標結點相同 printf("該結點已為目標結點狀態(tài)！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啟發(fā)式搜索成功！n"); break; NodeList=FindNextNode(r,open,close);/對close表最后一個結點進行擴展，擴展

22、得到的鏈表接到head表 open=insert(open,NodeList);/將擴展的結點按順序插入到open表中if(key = 1) p=close; printf("最優(yōu)搜索過程如下：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. 實驗分析本次實驗采用啟發(fā)式搜索，利用C語言編寫程序?qū)崿F(xiàn)八數(shù)碼問題的求解。采用簡單的估價函數(shù)： 其中是搜索樹中節(jié)點的深度；用來計算對應于節(jié)點的數(shù)據(jù)庫中錯放的棋子個數(shù)。例如初始節(jié)點的估價函數(shù)值為3。 估價函數(shù)能夠提供一個評定候選擴展節(jié)點的方法

24、，以便確定哪個節(jié)點時最有可能在通向目標的最佳路徑上。這樣選擇正確的估價函數(shù)，可以減少擴展節(jié)點個數(shù)，對于實驗所給的初始節(jié)點和估價函數(shù)，只用擴展11個節(jié)點就能找到目標節(jié)點；相比于盲目搜索可以減少被擴展的節(jié)點數(shù)，減少很多空間占用和時間損耗。 利用啟發(fā)信息來決定哪一個是下一步要擴展的節(jié)點，這種搜索總是選擇“最有希望”的節(jié)點作為下一步被擴展的節(jié)點。這實際上是通過估價函數(shù)值的大小重排OPEN表，小的一直排在OPEN表的前面。每次取OPEN表的第一個節(jié)點放到CLOSED表中進行擴展，這樣一步步靠近目標節(jié)點，直到最后找到目標節(jié)點，停止擴展。6. 結論正確選擇估價函數(shù)對確定搜索結果具有決定性作用。使用不能識別某

25、些節(jié)點真是希望的估價函數(shù)會形成非最小代價路徑；而使用一個過多地估計了全部節(jié)點希望的估價函數(shù)，又會擴展過多的節(jié)點。在選對估價函數(shù)的前提下，啟發(fā)式搜索能準確識別有希望和沒有希望的節(jié)點，從而很快擴展到目標節(jié)點，找到最短路徑。在本次實驗中如果選擇估價函數(shù)值為（用來計算對應于節(jié)點的數(shù)據(jù)庫中錯放的棋子個數(shù)），將會擴展更少的節(jié)點，更加快的找到到達目標節(jié)點的最短路徑。二英文期刊翻譯Adaptive Evolutionary Artificial NeuralNetworks for Pattern Classification自適應進化人工神經(jīng)網(wǎng)絡模式分類摘要：這篇文章提出了一種新的進化方法稱為混合進化人工神

26、經(jīng)網(wǎng)絡(HEANN),同時提出進化人工神經(jīng)網(wǎng)絡(ANNs)拓撲結構和權重。進化算法(EAs)具有較強的全局搜索能力且很可能指向最有前途的領域。然而,在搜索空間局部微調(diào)時，他們效率較低。HEANN強調(diào)全局搜索的平衡和局部搜索的進化過程，通過調(diào)整變異概率和步長擾動的權值。這是區(qū)別于大多數(shù)以前的研究，那些研究整合EA來搜索網(wǎng)絡拓撲和梯度學習來進行權值更新。四個基準函數(shù)被用來測試的HEANN進化框架。此外,HEANN測試了七個分類基準問題的UCI機器學習庫。實驗結果表明在少數(shù)幾代算法中，HEANN在微調(diào)網(wǎng)絡復雜性的性能是優(yōu)越的。同時，他還保留了相對于其他算法的泛化性能。簡介：人工神經(jīng)網(wǎng)絡(ANNs)已

27、經(jīng)成為一種強大的工具被用于模式分類1,2。ANN拓撲優(yōu)化和連接權重訓練經(jīng)常被單獨處理。這樣一個分治算法產(chǎn)生一個不精確的評價選擇的神經(jīng)網(wǎng)絡拓撲結構。事實上,這兩個任務都是相互依存的且應當同時解決以達到最佳結果。 一個模式分類的關鍵任務是設計一個緊湊和廣義ANN拓撲。為特定的問題選擇一個適當?shù)腁NN拓撲是至關重要的，由于ANN泛化相關性信息處理能力和ANN拓撲的強關聯(lián)能力。過度的小型網(wǎng)絡的大小表明問題不能學得很好,而一個特別大的網(wǎng)絡規(guī)模將導致過度學習和差的推廣性能。耗時的實驗訓練方法和爬山建設性或修剪算法3-7用于設計一個ANN架構，對于一個給定的任務只有探索小型建筑子集，或往往是停在結構局部最優(yōu)

28、解。相關的神經(jīng)網(wǎng)絡是一個流行的8建設性算法而用于構造有多個維層的ANN拓撲。新的隱藏節(jié)點一個接一個的被添加進來且都與每一個現(xiàn)有的隱藏節(jié)點在當前的網(wǎng)絡連接。因此,網(wǎng)絡可以被視為擁有多個可以形成一個級聯(lián)結構的集中度值層。然而,網(wǎng)絡是傾向于結構局部最優(yōu)解由于它具有建設性的行為。設計一個ANN拓撲使用進化算法(EAs)已經(jīng)成為一種流行的方法來克服建設性或修剪方法9-13的缺點。它有很強的全局搜索能力,可以有效地搜索通過接近完整的ANN拓撲類。許多工作已經(jīng)致力于進化神經(jīng)網(wǎng)絡ANN拓撲結構。兩個主要的方法來發(fā)展ANN拓撲的文獻報告是沒有重權值和ANN拓撲同步進化的兩個拓撲和權重。演化的一個無權值得ANN拓

29、撲,必須從一組隨機的初始權重訓練評估其適應性。姚和劉11指出,這個適應性評價方法很嘈雜因為一個顯性型的適應性是用來代表隱形型的適應性。雖然的進化ANN拓撲的適應性可以通過運行多個不同的隨機初始權重而得到的平均結果來估計,為適應性計算評價時間是急劇增加。因此,只有小ANN拓撲在14和15中被演化。同時進化的ANN拓撲和權重,權重信息拓撲和編碼在每個個體是獨立的。因此嘈雜的適應性評價問題可以被緩解。一個突出的工作稱為EPNet被姚和劉11引入，那是一個同時進化ANN拓撲和權重例子。姚和劉用混合訓練來進化ANN權重測試。梯度學習和模擬退火都納入進化過程演變的ANN權重。Martínez-E

30、studillo等人在最好的獨立ANN下使用梯度學習方法演變權重。他們用聚類算法劃分的個體在總數(shù)中分成幾個屬于同一區(qū)域的吸引力集群。然而,由于靈敏度高的反向傳播算法對初始權重，使用梯度學習方法如反向傳播算法進化ANN權重引起噪聲適應性評價。Palmes et al12使用基于突變EA在一個進化的ANN下解決這個問題。其他作品也集中在同步進化的ANN拓撲和權重。Anget al13介紹增長概率允許網(wǎng)絡演變到合適的大小。Angeline et al9使用參數(shù)突變和結構性突變進化安重量、隱藏節(jié)點和網(wǎng)絡鏈接。Jian和Yugeng10用進化規(guī)劃(EP)進化體系結構和前饋神經(jīng)網(wǎng)絡的權重和遞歸神經(jīng)網(wǎng)絡。L

31、iang et al17提出了一種改進遺傳算法的進化神經(jīng)網(wǎng)絡的結構和參數(shù)。Gutiérrez et al。18使用模擬退火控制參數(shù)突變和五個結構突變進化徑向基函數(shù)(RBF)神經(jīng)網(wǎng)絡。所有這些以前作品的目的是產(chǎn)生一個緊湊和廣義的ANN。通常,拓撲的一個ANN可以編碼到一個染色體編碼方案來使用直接或間接編碼方案。在直接編碼方案中,所有的ANN拓撲編碼直接進入一個染色體，這是通過使用二進制表示，而這表明存在網(wǎng)絡連接和隱藏的節(jié)點。間接編碼方案只有編碼的一些重要參數(shù)的一個ANN拓撲,如數(shù)量的隱藏層和隱藏的節(jié)點。其他細節(jié)ANN拓撲是預定義的或指定的一組確定的發(fā)展規(guī)則19。直接編碼方案易于實現(xiàn),適

32、合于精確的搜索。盡管間接編碼方案可以減少染色體的長度,它可能不適合找一個緊湊的具有良好的泛化能力的ANN19。在本文中,一個直接編碼方案是用來代表ANN拓撲。進化的ANN拓撲和權重可以幫助緩解此問題的嘈雜的評價。然而,僅僅依靠EA來進化神經(jīng)網(wǎng)絡是相當?shù)托?zhí)行本地搜索。進一步訓練使用傳統(tǒng)的梯度下降方法進化后可以是一個簡單的方法來調(diào)整網(wǎng)絡。認為情勢的過早收斂在進化過程中,ANN發(fā)現(xiàn)經(jīng)過進一步培訓可能不是最優(yōu)的。其他方法如使用退火溫度指導重量擾動步長9和調(diào)度的突變概率12的個人網(wǎng)絡的種群可以被認為是初步指南向本地搜索,但沒有不同的方向已經(jīng)被提供。因此,EA應該引導正確維持兩者之間的平衡整個搜索空間的

33、探索和開發(fā)的重要區(qū)域。出于平衡的重要性，在進化過程和同步進化的ANN拓撲和權重下的全局和本地搜索,本文提出了一種新的進化方法稱為混合進化人工神經(jīng)網(wǎng)絡(HEANN)，同時發(fā)展ANN拓撲和權重。此外,HEANN演示了一個平衡的全局搜索和局部搜索通過引入一個在演化工程中產(chǎn)生新穎的自適應變異技術。而不是使用傳統(tǒng)的方法來降低突變概率或步長大小,HEANN使用信息從種群引導進化過程將逐漸向全局搜索到本地搜索過渡。首先,概括損失(GL)在種群是用來適應變異概率和步長。第二，適應性價值的每個個體的種群是用來確定突變的嚴重性，在給定個體的種群。在本文中,主要有兩個因素：網(wǎng)絡拓撲優(yōu)化和進化能力。一種很流行的方法,

34、優(yōu)化兩個或兩個以上的目標是基于Pareto優(yōu)勢20-22。然而,查找和估算Pareto適應度的計算成本會增，當優(yōu)化目標數(shù)量增加時21。另一個流行的方法是基于多目標學習10,12、20,它聚合了幾個目標變成一個標量成本函數(shù)。在這種情況下,該方法假設凸性的Pareto。這種方法是用在當前的實現(xiàn)。其余的部分組織如下：第二部分詳細的描述了HEANN和每個成分。第三部分分析了所提出的自適應變異技術在ANN拓撲(添加或刪除節(jié)點,連接)下的影響,這種技術平衡全局和局部搜索的進化過程。第四節(jié)顯示了結果的新的自適應進化框架四個基準函數(shù)。第五部分包含實驗結果的HEANN。第六節(jié)提出了討論結果。最后,第七節(jié)總結了本

35、文的工作。結論：本文描述了一種新的方法來同時進化ANN拓撲和權重。解決的弱點在精細調(diào)諧，ANN EAs,HEANN使用一種自適應變異策略來改進本地搜索功能，在設計神經(jīng)網(wǎng)絡方面。GL和適應性價值被認為在演化過程下幫助了突變適應。此外,全局和局部的突變策略的分析研究HEANN。 首次測試是針對基準函數(shù)來證明提高局部搜索能力和能夠擺脫局部極值的能力。實驗結果表明，HEA比傳統(tǒng)的EA好。HEANN是用來測試七真是世界分類問題?？偟膩碚f，實驗結果顯示了在各方面的優(yōu)越性HEANN，相比其他算法。非常聚合的人工神經(jīng)網(wǎng)絡可以由HEANN產(chǎn)生與其自適應變異策略。此外,HEANN需要更少的后代能達到良好的結果。唯一的缺點是，它有很多可以由用戶定義的HEANN參數(shù)。然而，HEANN對這些參數(shù)不是很敏感。不同的突變測試參數(shù)結果表明，HEANN對于這些參數(shù)不是很敏感，但他的這些價值不應過低的被估計。如果沒有需要在進化過程中集中計算的梯度學習而使用一個更大的種群規(guī)模也是可行的。最終的種群肯定包含更多的信息比