【正文】 roupSize1)。 如下 是具體代碼： for(i=0。 算子的設(shè)計（ 交叉 、選擇、變異） 交叉 算子 交叉運(yùn)算，一般 指對兩個相互配對的染色體依據(jù)交叉概率 Pc 按某種方式相互交換其部分基因，從而形成兩個新的個體。 浮點(diǎn)數(shù)編碼方法有下面幾個優(yōu)點(diǎn)： （ 1)適用于在遺傳算法中表示范圍較大的數(shù) （ 2)適用于精度要求較高的遺傳算法 （ 3)便于較大空間的遺傳搜索 （ 4)改善了遺傳算法的計算復(fù)雜性，提高了運(yùn)算交率 （ 5)便于遺傳算法與經(jīng)典優(yōu)化方法的混合使用 （ 6)便于設(shè)計針對問題的專門知識的知識型遺傳算子 （ 7)便于處理復(fù)雜的決策變量約束條件 ： 符號編碼法是指個體染色體編碼串中的基因值取自一個無數(shù)值含義、而只有代碼含義的符號集如｛ A,B,C?｝。它有以下一些優(yōu)點(diǎn)： (1）編碼、解碼操作簡單易行 (2)交叉、變異等遺傳操作便于實(shí)現(xiàn) (3)符合最小字符集編碼原則 (4)利用模式定理對算法進(jìn)行理論分析。要求得的路徑路程為所有可能路徑之中的最小值， 即 最優(yōu)值問題 。 （ 6）人工 生命 人工生命是用計算機(jī)、機(jī)械等人工媒體模擬或構(gòu)造出的具有自然生物系統(tǒng)特有行為的人造系統(tǒng)。 （ 4）機(jī)器人 學(xué) 機(jī)器人是一類復(fù)雜的難以精確建模的人工系統(tǒng)， 而遺傳算法的起源就來自于人工自適應(yīng)系統(tǒng)的研究。對于 這些 非線性、 求 極 值、 多模型或 多目標(biāo)的 函數(shù) 優(yōu)化 問題，用傳統(tǒng)的優(yōu)化方法很難解決，而用遺傳算法可以 方便地 得到 較好的結(jié)果。 （ 3） 遺傳算法 不是采用確定性規(guī)則，而是采用概率的變遷規(guī)則來指導(dǎo) 它 的搜索方向 ，具有 自組織 、自適應(yīng)和自學(xué)習(xí)性。 主要有 以 下幾點(diǎn)： （ 1） 遺傳 算法的本質(zhì)并行性。 變異 操作可以保證 算法 過程中不會產(chǎn)生無法進(jìn)化的單一群體， 避免 算法 早熟 出現(xiàn) 局部最優(yōu)。參數(shù) N 可以根據(jù) 具體的情況 而定 。 9）串（ String） :它是 個體的 形式 ，在算法 中 為二進(jìn)制串，并且對應(yīng)于遺傳學(xué) 中 的染色體。 4）進(jìn)化（ evolution） 。在這個多維曲面里面也有數(shù)不清的 “山峰 ”，而這些最優(yōu)解所對應(yīng)的就 是 這些山峰 ， 這些山峰就是局部最優(yōu)解 。在 遺傳算法中，種群中的 每一個 個體是問題的一個 解 ， 稱為“染色體”， 染色體是 一串 符號，比如二進(jìn)制的 01 串 。 下面 是一些在遺傳算法發(fā)展 進(jìn)程 中做出 杰出 貢獻(xiàn)的 人物 ： 1 60 年代提出在研究和設(shè)計人工自適應(yīng)系統(tǒng)時 ,可以借鑒生物遺傳的機(jī)制； 70 年代初提出了遺傳算法的基本定理－模式定理 (Schema Theorem)，從而奠定了遺傳算法的理論基礎(chǔ)； 80 年代實(shí)現(xiàn)了第一個基于遺傳算法的機(jī)器學(xué)系統(tǒng)－分類器系統(tǒng) (Classifier Systems),開創(chuàng)了基于遺傳算法的機(jī)器學(xué)習(xí)的新概念 。 第五 章結(jié)論 。 本文 的結(jié)構(gòu) 本文 一共分為 5 章 ， 結(jié)構(gòu) 如下： 第一章緒論 。 遺傳算法（ Geic Algorithms,GA） 又叫 基因進(jìn)化算法或進(jìn)化算法 ，是 一種通過模擬自然界生物 適者生存 、優(yōu)勝劣 汰的 進(jìn)化過程而形成的一種自適應(yīng)、具有全局優(yōu)化能力的隨機(jī)搜索算法。 1980Crowder和 Padberg 求解 了 318 個 城市的 TSP 問題； 1987 年 Padberg 和 Rinaldi 成功 將城市數(shù)量增加到了 2392 個 ； 最大的 成功求解的旅行 商問題 已經(jīng) 增加 到 24798 個 城市。雖然它是一個比較古老的問題，最早可以追溯到 Euler 提出的騎士旅行問題，但同時它也是一個新的問題，因?yàn)樗挠嬎銖?fù)雜度 較高， 雖然人們一直在嘗試用新的方法來改進(jìn)求解該問題的復(fù)雜度，但是 這一類問題 距今 都沒有能找到一個有效的算法來解決 。 TSP 問題其實(shí)是“ 哈密頓回路問題 ”中的“哈密頓最短 回路問題 ”。 MUTATION ALGORITHM。 遺傳 算法（ Geic Algorithms,簡稱 GA） 是模擬 自然界生物 自然 選擇和進(jìn)化 的 機(jī)制而發(fā)展起來的一種高度并行、 自適應(yīng)的 隨機(jī) 搜索 算法。 本文 選 用遺傳算法 求解 45個 城市 的 TSP問題，基于 Microsoft Visual C++環(huán)境 ,采用 Grefenstette 等提出 的 一種 新的 巡回路線編碼方法 ，變異 算 子 采用了常規(guī)的 基本位變異 法 ， 通過 多 組實(shí)驗(yàn)和數(shù)據(jù) 近似的 求解 出了 45 個 城市的最優(yōu)解， 實(shí)現(xiàn) 了計算機(jī)仿真求解 TSP 問題 。 即使在所定義的適應(yīng)度函數(shù) 中 是不連續(xù)的、不規(guī)則 的 情況下，也可以很大概率 找到 全局最優(yōu)解 。 所以 要在 編碼方式的確定上做好足夠的 功夫 ， 以 確定 程序 求解的精確度。 尋求 一種 能 短時間求 解 出高精度解 的算法，已成為此問題研究的熱門。再比如 在裝配線 的 流程中，對每個工件為完成裝配過程節(jié)約的少許時間意味著一天的產(chǎn)量的相應(yīng)增加。在遺傳算法中，以個體適應(yīng)度的大小來確定該個體被遺傳到下一代群體中的概率。 本章 主要介紹了 本系統(tǒng) 具體使用什么方式實(shí)現(xiàn)求解過程， 包括 編碼方式、選擇、交叉、變異算子的具體選取 。 在一系列研究工作的基礎(chǔ)上 80 年代 Goldberg進(jìn)行總結(jié)歸納， 形成了 遺傳算法的基本框架 ； Smith將 遺傳算法應(yīng)用于機(jī)械學(xué)習(xí)領(lǐng)域； Bethke 對 函數(shù)優(yōu)化的遺傳算法進(jìn)行了系統(tǒng)的研究。 1992 年將遺傳算法應(yīng)用于計算機(jī)程序的優(yōu)化設(shè)計及自動生成，提出了遺傳編程 (Geic Programming) 的概念，并成功的將其提出的遺傳編程應(yīng)用于人工智能、機(jī)器學(xué)習(xí)符號處理等方面。新的下一代再重復(fù) 根據(jù) 適應(yīng)度選擇部分后代，淘汰一部分后代，這樣 即 可以 保證 種群染色體的優(yōu)越性，也 保持了 種群大小的穩(wěn)點(diǎn)性。生物的基因根據(jù)物種的不同而多少不一。 7）變異（ musation）：復(fù)制時很小的概率產(chǎn)生的某些復(fù)制差錯。 6 遺傳 算法基本步驟 步驟一 ： 編碼 ： 把 所需要選擇的群體進(jìn)行編號，每一個個體就是 一條 染色體 ，一個 解就是一串基因的組合 。 步驟五 ： 選擇 算子： 選擇 的目的是為了從交換后的群體中 選出 優(yōu)良 的 染色體攜帶者，使 它們 有機(jī)會作為父 代 繁殖 出 下一代群體。一般的 迭代 方法容易陷入局部極小的陷阱而出現(xiàn)“ 死循環(huán) ” 現(xiàn)象 ， 使迭代無法進(jìn)行。 其次 ，算法內(nèi) 含 并行性，遺傳算法采用種群方式組織搜索，因而可同時搜索解空間的多個區(qū)域，并 相互 交流信息，能以較小的計算獲得較大收益。 遺傳 算法的應(yīng)用 遺傳 算法為求解復(fù)雜 系統(tǒng)問題 提供了一種通用的算法框架，它不取決于問題的 具體 領(lǐng)域，有很強(qiáng)的魯棒性 ， 因而被廣泛的 使用 于 組合 優(yōu)化 、 機(jī)械設(shè)計、人工智能、數(shù)學(xué)建模、軟件工程等領(lǐng)域 。目前在現(xiàn)實(shí)生產(chǎn)中主要是靠一些經(jīng)驗(yàn)來進(jìn)行調(diào)度。因此，應(yīng)用遺傳算法在數(shù)據(jù)庫中進(jìn)行搜索，對隨機(jī)產(chǎn)生的一組規(guī)則進(jìn)行進(jìn)化 .直 到數(shù)據(jù)庫能被該組規(guī)則覆蓋，從而挖掘出隱含在數(shù)據(jù)庫中的規(guī)則。人工生命與遺傳算法相輔相成，遺傳算法為人工生命的研究提供一個有效的工具，人工生命的研究也必將促進(jìn)遺傳算法的進(jìn)一步發(fā)展?？偟膩碚f，這些編碼方法可以分為三大類：二進(jìn)制編碼法、浮點(diǎn)編碼法、符號編碼法。個體長度較知時，可能達(dá)不到精度要求，而個體編碼長度較長時，雖然能提高精度，但卻使遺傳算法的搜索空間急劇擴(kuò)大。 對于 給定的旅行商問題 ， 設(shè) 其 城市列表 W， 假定 對 各個 城市的 訪問順序?yàn)?T： T=（ T1， T2， T3， ….. ， Tn） 規(guī)定 每訪問完一個 城市， 就 從 城市列表 W 中 將 該城市 除去，則用第 i（ i=1,2,3……n ）個所訪問的城市 Ti 在所有未訪問城市列表 W={T1， T2， T3，? ..， Ti1}中的對應(yīng)位置序號 Gi（ 1≤ Gi≤ ni+1）就可表示具體訪問哪個城市，如此這樣直到處理完 W 中所有的城市。因此 ， 就可以使用常規(guī)的單點(diǎn)交叉算子 。 //父代基因 2 parent1=RandomInt(0,m_nGroupSize1)。 (amp。pop1)。具體 操作如下： 計算出群體中每個個體的適應(yīng)度 f(i=1， 2，?， M)， M 為群體大小； 歸一化 適應(yīng)度 f 的值 將 適應(yīng)度 f 的 值從 大 到小排列， 查找 其中 最小 費(fèi) 用 的個體 然后 將其作為 下一代 選擇出來。i++) oldpop[i].fit=1/oldpop[i].cost/TotalF*100。 maxpos=j。 //AfxMessageBox(顯示數(shù)據(jù) )。 變異 算子 變異運(yùn)算，是指改變個體編碼串中的某些基因值，從而形成新的個體。 （ 2）對每一個指定的變異點(diǎn)，對其基因值做取反運(yùn)算或用其他等位基因值來代替，從而產(chǎn)生出一個新個體。 為變異結(jié)點(diǎn) ） PopNode pop。 因此適應(yīng)度函數(shù)的選擇至關(guān)重要，直接影響到遺傳算法的收斂速度以及能否找到最優(yōu)解。下圖是系統(tǒng)的功能模塊圖。 這些在上文中已作過詳細(xì)介紹 ,這里就不再重復(fù)。 m_CurGANum = 0。 DDX_Text(pDX, IDC_EDIT4, m_GAVariProb)。具體代碼如下： void CChina45Dlg::OnMenuGaset() { // TODO: Add your mand handler code here CGASetDlg dlg。 for(int k=0。 為了便于 演示觀察，本系統(tǒng)將城市位置用圓圈表示出來 ，具體操作 是 ： 將 已知 城市的坐標(biāo)點(diǎn)分別向上下左右移動兩個單位，并 以 城市位置作為圓心畫圓，這 樣 就在主窗口上的地圖區(qū)域確定了城市的位置。 =。i++) { CRect city。 } （ 2） 關(guān)于 軟件： 在 VC 工具欄 insent 中插入窗口 IDD_ABOUTBOX， 對其添加如下操作： enum { IDD = IDD_ABOUTBOX } (指定窗口 ID) protected: virtual void DoDataExchange(CDataExchange* pDX)。 這兩種 情況 分別 進(jìn)行了兩次實(shí)驗(yàn)。 } 測試結(jié)果及分析 測試 一 如 下圖所示，本次測試的是默認(rèn)的參數(shù) {M， T， Pc， Pm}={200， 100， ， }， 所取數(shù)值 都 在系統(tǒng)設(shè)置的參考范圍 之 內(nèi)。（城市 位置 向左 兩個單位） =px+m_point[i].x+2。 pDCSetBkColor(0x00FFFFFF)。 CDC* pDC=GetDC()。k++) { ExecGA(k, oldpop)。 （將新的 群體規(guī)模 賦值 給對話框） m_GACrossProb=。 DDX_Text(pDX, IDC_EDIT6, m_CurGANum)。 m_CrossNum = 0。 具體 變量 及其窗口 對話框 設(shè)置如下表。 本系統(tǒng)中所使用的遺傳算法是 由 以下要素所構(gòu)成的： ●編碼方法 基本遺傳算法使用由 Grefenstette 所提出的編碼方法，詳細(xì)設(shè)計見第四章編碼方 式 一節(jié)。 為正確計算不同情況下各個個體的遺傳概率，要求所有個體的適應(yīng)度必須為正數(shù)或零，不能是負(fù)數(shù)。oldpop[0])。 變異是單個個體內(nèi)部發(fā)生變化，導(dǎo)致產(chǎn)生新個體， 從而產(chǎn)生出一條新的巡回路線。交叉運(yùn)算可以和變異運(yùn)算相互配合，共同完成對搜索空間的全局搜索和局部搜索。 UpdateWindow()。oldpop[maxpos])。im_nGroupSize1。genm_GANum。pop2)。 (amp。 if(parent1temp) parent1=temp。產(chǎn)生 下一代個體在使用 Grefenstette 等提出的 編碼方式 時 ， 染色體 編碼串 前面 的一 些 基因發(fā)生變化 時 ，會對后面的基因值 產(chǎn)生巨大 的影響 ，產(chǎn)生 的新的個體 與 上一代的性狀變化 就會 十分明顯，有利于整個算法 跳出 局部最優(yōu)解。例如 ， 假設(shè)現(xiàn)在有這樣一個城市序列： W=(A,B,C,D,E,F,G,H,I,J) 有 如下兩條 巡回 路線 ： T1=(A,D,B,H,F,I,J,G,E,C) T2=(B,C,A,D,E,J,H,I,F,G) 則按本 系統(tǒng)所用的編碼方法 ， 這兩 條 巡回路線可以編碼為： G1 =(1,3,1,5,3,4,4,3,2,1) 12 G2 =(2,2,1,1,1,5,3,3,1,1) 這種 編碼方式的 優(yōu)點(diǎn) 在于任意的染色體都對應(yīng)一條有實(shí)際意義的巡回路線， 因此 可以使用常規(guī)的交叉算子對它 進(jìn)行 計算，有利于算 法的實(shí)現(xiàn)。在浮點(diǎn)數(shù)編 10 碼方法中，必須保證基因值在給定的區(qū)間限制范圍內(nèi)，遺傳算法中所使用的交叉、變異等 11 遺傳算子也必須保證其運(yùn)算結(jié)果所產(chǎn)生的新個體的基因值也在這個區(qū)間限制范圍內(nèi)。 ： 它由二進(jìn)制符號 0 和 1 所組成的二值符號集。 它可以 大致 描述 為 這樣 ： 有一個旅行商人要拜訪 n 個城市，他必須要 經(jīng)過所有的城市 ，而且每個城市只能拜訪一次，最后要回到原來出發(fā)的城市。利用該工