試驗(yàn)要求:一個(gè)迷宮，左邊有一入口（紅色方塊）,右邊有一出口（紅色方塊）,并有一些障礙物（黑色方塊）散布在其中。然后在動(dòng)身點(diǎn)放置一個(gè)虛擬人Bob，使用遺傳算法編程實(shí)現(xiàn)路徑查找方案，使他能找到出口，并避開與全部障礙物相碰撞。怎樣來(lái)產(chǎn)生Bob的染色體的編碼？怎樣進(jìn)行適應(yīng)度評(píng)價(jià)？圍繞染色體編碼、初始群體的設(shè)定、適應(yīng)度函數(shù)的設(shè)計(jì)、遺傳操作設(shè)計(jì)、掌握參數(shù)設(shè)定五個(gè)要素進(jìn)行文檔說(shuō)明提交完整的軟件系統(tǒng)和相關(guān)文檔，包括源程序和可執(zhí)行程序。（編程語(yǔ)言C,C++,Java任選其一）要求程序執(zhí)行時(shí)能顯示當(dāng)前個(gè)體的代數(shù)以及適應(yīng)度函數(shù)值二.試驗(yàn)原理.遺傳算法?遺傳算法（GeneticAlgorithm）是一類借鑒生物界的進(jìn)化規(guī)律（適者生存，優(yōu)勝劣汰遺傳機(jī)制）演化而來(lái)的隨機(jī)化搜尋方法。它是由美國(guó)的J.Holland教授1975年首先提出，其主要特點(diǎn)是直接對(duì)結(jié)構(gòu)對(duì)象進(jìn)行操作，不存在求導(dǎo)和函數(shù)連續(xù)性的限定；具有內(nèi)在的隱并行性和更好的全局尋優(yōu)力量；采納概率化的尋優(yōu)方法，能自動(dòng)獵取和指導(dǎo)優(yōu)化的搜尋空間，自適應(yīng)地調(diào)整搜尋方向，不需要確定的規(guī)章。遺傳算法的這些性質(zhì)，已被人們廣泛地應(yīng)用于組合優(yōu)化、機(jī)器學(xué)習(xí)、信號(hào)處理、自適應(yīng)掌握和人工生命等領(lǐng)域。它是現(xiàn)代有關(guān)智能計(jì)算中的關(guān)鍵技術(shù)。?對(duì)于一個(gè)求函數(shù)最大值的優(yōu)化問題（求函數(shù)最小值也類同）,一般可以描述為下列數(shù)學(xué)規(guī)劃模型：式中為決策變量，為目標(biāo)函數(shù)式，式2-2、2-3為約束條件，U是基本空間，R是U的子集。滿意約束條件的解X稱為可行解，集合R表示全部滿意約束條件的解所組成的集合，稱為可行解集合。遺傳算法的基本運(yùn)算過(guò)程如下：a）初始化:設(shè)置進(jìn)化代數(shù)計(jì)數(shù)器t=0,設(shè)置最大進(jìn)化代數(shù)T,隨機(jī)生成M個(gè)個(gè)體作為初始群體P（0）eb）個(gè)體評(píng)價(jià):計(jì)算群體P⑴中各個(gè)個(gè)體的適應(yīng)度。c）選擇運(yùn)算:將選擇算子作用于群體。選擇的目的是把優(yōu)化的個(gè)體直接遺傳到下一代或通過(guò)配對(duì)交叉產(chǎn)生新的個(gè)體再遺傳到下一代。選擇操作是建立在群體中個(gè)體的適應(yīng)度評(píng)估基礎(chǔ)上的。d）交叉運(yùn)算；將交叉算子作用于群體。所謂交叉是指把兩個(gè)父代個(gè)體的部分結(jié)構(gòu)加以替換重組而生成新個(gè)體的操作。遺傳算法中起核心作用的就是交叉算子。e）變異運(yùn)算:將變異算子作用于群體。即是對(duì)群體中的個(gè)體串的某些基因座上的基因值作變動(dòng)。群體P(t)經(jīng)過(guò)選擇、交叉、變異運(yùn)算之后得到下一代群體P(t1)0f)終止條件推斷:若tT,則以進(jìn)化過(guò)程中所得到的具有最大適應(yīng)度個(gè)體作為最優(yōu)解輸出,終止計(jì)算。.數(shù)據(jù)結(jié)構(gòu))Jie類紀(jì)錄遺傳編碼及其相關(guān)操作用一個(gè)70位的int數(shù)組來(lái)表示一個(gè)基因組,其中每2位表示一步(00上01下10左右11X由于迷宮大小固定為15*8所以35步確定能找到結(jié)果了。該類包含了基本的get、set操作，其中有一個(gè)名為getquan的函數(shù)，調(diào)用它將返回這個(gè)基因所代表的走法離出口最近的時(shí)候的權(quán)值.)jieji類代表一個(gè)由10個(gè)基因組成的種群,包含了交叉、變異、選擇和GET、SET函數(shù)publicintxuanze()::評(píng)價(jià)+選擇函數(shù)。先掃描紀(jì)錄全部基因的權(quán)值，假如找到了一個(gè)解則直接打印。然后通過(guò)輪盤法選擇后代。依次累加讀入的權(quán)值，將其除以總權(quán)值得到一個(gè)百分?jǐn)?shù)；產(chǎn)生一個(gè)隨機(jī)數(shù)，通過(guò)推斷它落在了哪個(gè)區(qū)間選擇后代。publicvoidjiaochaQ::交叉函數(shù)由于每代都是通過(guò)選擇重新產(chǎn)生的，全部本函數(shù)中總是選擇相鄰的兩個(gè)基因進(jìn)行交叉操作；首先產(chǎn)生一個(gè)隨機(jī)數(shù)，假如小于交叉率則進(jìn)行交叉操作；隨機(jī)選擇5個(gè)位置(代表走一步的相鄰2位)交換。publicvoidbianyi()::變異函數(shù)首先推斷推斷產(chǎn)生的隨機(jī)數(shù)是否小于變異率打算進(jìn)行變異操作;然后在基因隨機(jī)選擇一位，取反。)migong類表示一個(gè)迷宮，并包含它的基本操作本次試驗(yàn)中的迷宮是固定的{{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1),(6,0,1,0,0,0,0,0,1,1,1,0,0,0,11,(1,0,0,0,0,0,0,0,1,1,1,0,0,0,1),(1,0,0,0,1,1,1,0,0,1,0,0,0,0,11,(1,0,0,0,1,1,1,0,0,0,0,0,1,0,1),(1,1,0,0,1,1,1,0,0,0,0,0,1,0,1),(1,0,0,0,0,1,0,0,0,0,1,1,1,0,1),(1,0,1,1,0,0,0,1,0,0,0,0,0,0,1),(1,0,1,1,0,0,0,1,0,0,0,0,0,0,9),(1,1,1,1,1,1,1,1,1,1,1,1,1,1,1});打印時(shí)挨次掃描矩陣1表示墻，6為入口，9為出口，走過(guò)的路徑為100;)zhuhanshu類主函數(shù)調(diào)用其他類實(shí)現(xiàn)算法.算法怎樣來(lái)產(chǎn)生Bob的染色體的編碼？用一個(gè)70位int數(shù)組表示染色體，初始化時(shí)隨機(jī)把每一位賦值為1或0；相鄰2位表示一步(oo上oi下io左n右)怎樣進(jìn)行適應(yīng)度評(píng)價(jià)？由于起點(diǎn)在矩陣的左上角，終點(diǎn)在右下角，全部越接近終點(diǎn)，橫縱坐標(biāo)平方和越大，可以用它來(lái)作為適應(yīng)度。圍繞染色體編碼、初始群體的設(shè)定、適應(yīng)度函數(shù)的設(shè)計(jì)、遺傳操作設(shè)計(jì)、掌握參數(shù)設(shè)定五個(gè)要素進(jìn)行文檔說(shuō)明染色體編碼：染色體有70位，相鄰2位表示一步(00上01下10左11右)，一共35步。由于迷宮為15*8固定，全部35步足夠找到解。初始群體的設(shè)定：整個(gè)種群有10個(gè)染色體，初始時(shí)每個(gè)染色體都是隨機(jī)產(chǎn)生的。適應(yīng)度函數(shù)的設(shè)計(jì)：依據(jù)染色體編碼所表示的走法，從起點(diǎn)開頭模擬走一次。每走一步，計(jì)算一下起橫縱坐標(biāo)的平方和作為權(quán)值，若撞墻則忽視這一步。取權(quán)值的最大值作為這個(gè)染色體的適應(yīng)度。遺傳操作設(shè)計(jì)：不斷循環(huán)產(chǎn)生新的子代，知道找到解。每一代執(zhí)行一下操作.評(píng)估，掃描每個(gè)染色體的適應(yīng)度，假如找到解則直接調(diào)用打印函數(shù).選擇，用輪盤法選擇10次，作為子代替換群體.交叉，調(diào)用交叉函數(shù)，每相鄰2個(gè)染色體有肯定概率交叉5個(gè)隨機(jī)位置上的基因.變異，調(diào)用變異函數(shù)，每個(gè)染色體都有肯定概率在一個(gè)隨機(jī)位置上發(fā)生反轉(zhuǎn)三.試驗(yàn)內(nèi)容代碼詳見程序.生成原始種群.不斷循環(huán)，直到找到解1）評(píng)估2）交叉）變異4）選擇.打印出這個(gè)解四.試驗(yàn)結(jié)果五、試驗(yàn)總結(jié).本試驗(yàn)原理雖然并不太難，但假如對(duì)遺傳算法的精神理解不夠透徹，就不簡(jiǎn)單保證算法的效率。我在這次試驗(yàn)中很快就完成了基本的代碼編寫和調(diào)試，也能得到正確的運(yùn)行結(jié)果，但是效率卻特別低下，往往要上萬(wàn)代的操作才能得到結(jié)果，耗時(shí)十多秒。然后我就投入了大量