智能搜索算法教學(xué)軟件的設(shè)計(jì)與開發(fā)

1、智能搜索算法教學(xué)軟件的設(shè)計(jì)與開發(fā) 為了適應(yīng)人工智能技術(shù)發(fā)展的需要 , 國內(nèi)外高校普遍開設(shè)了 人工智能方面的課程 , 而且已經(jīng)成為計(jì)算機(jī)相關(guān)專業(yè)的核心課程 之一。我校自從 1996 年開始為計(jì)算機(jī)科學(xué)與技術(shù)、自動(dòng)化、機(jī) 械自動(dòng)化等專業(yè)本科生開設(shè)了人工智能導(dǎo)論課程。 我校王萬良教 授也在 2005 年編著了人工智能及其應(yīng)用教材 ,2008 年又出 版了該教材第 2 版, 并制作了完整的電子教案和教學(xué)錄像。 由于人工智能是交叉學(xué)科 ,涉及面廣 ,在教學(xué)過程中又會(huì)涉 及到很多抽象理論和復(fù)雜的算法 , 而教材上的內(nèi)容過于理論化 , 教材上的應(yīng)用實(shí)例又只是停留在書本文字上的紙上談兵 , 所以學(xué) 生在學(xué)習(xí)人

2、工智能導(dǎo)論這門課程的過程中都感覺好像在學(xué)數(shù)學(xué) 和算法 , 往往有望而生畏的感覺。 為了解決以上問題 ,如果單純依 靠老師在課堂上講解和用PPT做課件進(jìn)行演示，是很難達(dá)到啟發(fā) 和指導(dǎo)學(xué)生的要求。為了更好地實(shí)現(xiàn)教學(xué)目標(biāo) , 提高人工智能導(dǎo) 論課程的教學(xué)質(zhì)量 , 協(xié)調(diào)好教與學(xué)的雙邊關(guān)系 , 使學(xué)生由望而生 畏的感覺 , 變?yōu)橛杏糜腥さ母杏X , 根據(jù)已有人工智能課程在教學(xué) 與實(shí)踐方面的經(jīng)驗(yàn)和方法 1-2, 在人工智能課程網(wǎng)站 () 的基礎(chǔ)上 , 以高等教育出版社出版的 人工智能及 其應(yīng)用(第2版)3 教材第 5章和第 9章內(nèi)容為例 ,設(shè)計(jì)開發(fā)了 智能搜索算法教學(xué)軟件。 1教學(xué)軟件

3、的總體結(jié)構(gòu) 智能搜索教學(xué)實(shí)驗(yàn)系統(tǒng)是 人工智能及其應(yīng)用 (第 2版)教 材配套的實(shí)驗(yàn)CAI系統(tǒng),系統(tǒng)設(shè)計(jì)目的是提供一個(gè)簡潔、友好的 用戶界面 , 使學(xué)生通過使用該系統(tǒng) , 可以實(shí)現(xiàn)不同智能搜索算法 的過程演示和對比 , 提供自主設(shè)計(jì)實(shí)驗(yàn)的功能。 為了能夠讓學(xué)生更好地學(xué)習(xí)并熟練一些智能搜索算法 , 所設(shè) 計(jì)的智能搜索教學(xué)實(shí)驗(yàn)系統(tǒng)結(jié)構(gòu)如圖 1所示,包括A*算法、模擬 退火算法、遺傳算法、作業(yè)管理和系統(tǒng)幫助 5 大模塊。 圖 1 教學(xué)實(shí)驗(yàn)系統(tǒng)的總體結(jié)構(gòu)圖 基金項(xiàng)目 :浙江工業(yè)大學(xué)校級優(yōu)秀課程建設(shè)項(xiàng)目 (YX0811)。 圖1中,A*算法、模擬退火算法和遺傳算法模塊又提供了算 法介紹 , 以及各算法的演

4、示程序、 驗(yàn)證程序和自主實(shí)驗(yàn)等子模塊。 1) 算法介紹。算法介紹子模塊的主要功能是向?qū)W生介紹 A* 算法、模擬退火算法、遺傳算法等智能搜索算法的特點(diǎn)、流程及 參數(shù)設(shè)置問題等。 2) 演示程序。演示程序子模塊的主要功能是展示各算法求 解八數(shù)碼問題、TSP問題等的搜索過程、運(yùn)算結(jié)果等；同時(shí)可以 通過單擊“下一步”、 “繼續(xù) / 暫?！钡劝粹o , 查看算法運(yùn)行過程 中臨時(shí)變量的狀態(tài)。 3) 驗(yàn)證程序。驗(yàn)證程序子模塊的主要功能是通過設(shè)定給定 問題的規(guī)模 , 以及算法的一些參數(shù)設(shè)置 , 測試智能搜索算法對于 不同規(guī)模問題的解決效果 , 以及參數(shù)設(shè)置對算法性能的影響 ; 同 時(shí)展示不同算法對同一問題的求解

5、性能 , 以作對比。 4) 自主實(shí)驗(yàn)。自主實(shí)驗(yàn)子模塊的主要功能是根據(jù)系統(tǒng)所提 供的一些算法核心代碼 ,開展各算法的自主實(shí)驗(yàn)設(shè)計(jì) , 解決最短 路徑問題、TSP問題和Flow shop調(diào)度問題等一些難題。 作業(yè)管理模塊主要是便于學(xué)生上傳實(shí)驗(yàn)報(bào)告和程序源代碼 以及教師批改作業(yè)。另外 , 系統(tǒng)幫助模塊包括系統(tǒng)概述、系統(tǒng)安 裝與卸載說明、服務(wù)器配置說明、系統(tǒng)使用說明和技術(shù)支持。 2 智能搜索算法實(shí)驗(yàn)設(shè)計(jì)與實(shí)現(xiàn) 2.1A* 算法 A*算法是一種啟發(fā)式搜索方法，目前在網(wǎng)絡(luò)路由算法、機(jī)器 人探路、人工智能、游戲設(shè)計(jì)等方面有著普遍的應(yīng)用。 啟發(fā)式搜索是利用與問題有關(guān)的啟發(fā)信息進(jìn)行搜索 , 達(dá)到減 少搜索范圍

6、, 提高搜索效率的目的。這種利用啟發(fā)信息的搜索過 程稱為啟發(fā)式搜索方法。啟發(fā)式搜索過程中，要對Open表進(jìn)行排 序, 這就需要一種方法來計(jì)算待擴(kuò)展節(jié)點(diǎn)有希望通向目標(biāo)節(jié)點(diǎn)的 不同程度 , 人們總是希望能找到最有希望通向目標(biāo)節(jié)點(diǎn)的待擴(kuò)展 節(jié)點(diǎn)優(yōu)先擴(kuò)展。A*算法一般是以估價(jià)函數(shù) 的大小來排列待擴(kuò)展 狀態(tài)的次序 , 每次選擇 值最小者進(jìn)行擴(kuò)展 3 。 (1) 其中 是初始節(jié)點(diǎn)到 節(jié)點(diǎn)的實(shí)際代價(jià) , 而 是從 節(jié)點(diǎn)到目的 節(jié)點(diǎn)的最佳路徑的估計(jì)代價(jià) , 且, 為 節(jié)點(diǎn)到目的結(jié)點(diǎn)的最優(yōu)路 徑的代價(jià)。 1) 演示程序。針對A*算法求解問題時(shí)啟發(fā)信息不直觀、難 理解,Open表和Closed表變化的可視化程度差

7、，問題狀態(tài)演變復(fù) 雜等問題，設(shè)計(jì)了求解自動(dòng)尋路和八數(shù)碼問題的A*算法演示程 序。演示程序具備了顯示 Open表和Closed表的功能,并且能將 每一個(gè)狀態(tài)的變化都直觀地顯示出來。 圖2是自動(dòng)尋路問題的A*算法演示程序。尋路問題常見于 各類游戲中角色尋路、 三維虛擬場景中運(yùn)動(dòng)目標(biāo)的路徑規(guī)劃、 機(jī) 器人尋路等多個(gè)應(yīng)用領(lǐng)域。 自動(dòng)尋路問題是在以方格表示的地圖 場景中,對于給定的起點(diǎn)、 終點(diǎn)和障礙物 （墻）, 如何找到一條從起 點(diǎn)開始避開障礙物到達(dá)終點(diǎn)的最短路徑。 如圖 2 所示 , 程序運(yùn)行時(shí) , 可以通過選擇“起點(diǎn)”、 “終點(diǎn)” 和“墻” ,在方格場景中設(shè)置起點(diǎn)、 終點(diǎn)和墻的任意位置 ,其中墻 可

8、以設(shè)置多個(gè)方格 , 另外分別以紅、綠和黑三色來區(qū)分起點(diǎn)、終 點(diǎn)和墻。通過單擊“開始”按鈕 , 可以看到起點(diǎn)位置的 、 和 值。 然后連續(xù)單擊“下一步”按鈕 , 可以進(jìn)行連續(xù)手動(dòng)單步運(yùn)行 , 從 而可以直觀地看到自動(dòng)尋路過程中每一狀態(tài)的變化 , 以及任一狀 態(tài) 的 、 和 值;若單擊“繼續(xù) /暫?！卑粹o , 可以從當(dāng)前結(jié)點(diǎn)開 始進(jìn)行自動(dòng)連續(xù)運(yùn)行 , 從而可以看到從當(dāng)前結(jié)點(diǎn)到終點(diǎn)的自動(dòng)尋 路的連續(xù)過程 , 以及尋路過程中每一狀態(tài)的變化 , 任一狀態(tài) 的 、 和 值; 同時(shí)也可從連續(xù)運(yùn)行狀態(tài)轉(zhuǎn)為暫停狀態(tài)。在“運(yùn)行狀態(tài)” 提示框上方可以看到“自動(dòng)運(yùn)行”、“暫?！钡瘸绦蜻\(yùn)行狀態(tài) , 而下方可以看到“ O

9、pen 表”、“擴(kuò)展結(jié)點(diǎn)”、“停止”等信息 , 其中“ Open表”表示在地圖場景中以淡藍(lán)色顯示Open表中的各 結(jié)點(diǎn)（狀態(tài)）; “擴(kuò)展結(jié)點(diǎn)”表示選中當(dāng)前被擴(kuò)展結(jié)點(diǎn) , 并在地圖 場景中用藍(lán)色框顯示當(dāng)前被擴(kuò)展結(jié)點(diǎn)。與此同時(shí) , 在地圖場景中 以黑色標(biāo)注尋路過程中 Closed 表中的各個(gè)結(jié)點(diǎn) （ 狀態(tài)） 。 圖 2 自動(dòng)尋路問題的演示程序 圖3是八數(shù)碼問題的A*算法演示程序。八數(shù)碼問題是在3X3 的九宮格棋盤上，擺有8個(gè)刻有18數(shù)碼的將牌。棋盤中有一個(gè) 空格,允許緊鄰空格的某一將牌可以移到空格中 ,這樣通過平移 將牌可以將某一將牌布局變換為另一布局。 針對給定的一種初始 布局或結(jié)構(gòu) （目標(biāo)狀態(tài)

10、 ）, 問如何移動(dòng)將牌 , 實(shí)現(xiàn)從初始狀態(tài)到目 標(biāo)狀態(tài)的轉(zhuǎn)變。 圖 3 八數(shù)碼問題的演示程序 如圖 3 所示 , 可以手動(dòng)設(shè)置八數(shù)碼問題的初始狀態(tài)和目標(biāo)狀 態(tài), 也可以通過單擊“隨機(jī)產(chǎn)生”按鈕 , 隨機(jī)生成其初始狀態(tài) , 然 后單擊“開始 /停止”按鈕 , 可以由停止?fàn)顟B(tài)轉(zhuǎn)為運(yùn)行狀態(tài) , 也可 由運(yùn)行狀態(tài)轉(zhuǎn)為停止?fàn)顟B(tài)。在運(yùn)行狀態(tài)下 , 首先針對所產(chǎn)生的初 始狀態(tài)和給定的目標(biāo)狀態(tài) ,判斷八數(shù)碼問題是否有解 ,若無解,則 停止運(yùn)行。 然后在問題有解的情況下 , 根據(jù)一般的估價(jià)函數(shù) , 通過 連續(xù)單擊“下一步”按鈕可以在“彈出結(jié)點(diǎn)并擴(kuò)展”框中看到 整個(gè)搜索過程，與此同時(shí)，在“ OPEN表”和“ CL

11、OSED表”中會(huì)分 別顯示整個(gè)過程的 Open表和Closed表的變化,包括各狀態(tài)及其 估計(jì)代價(jià)值 h 和估計(jì)函數(shù)值 f, 以及當(dāng)前步數(shù)。若單擊“手動(dòng) / 自 動(dòng)”按鈕 , 可以由手動(dòng)轉(zhuǎn)入自動(dòng) , 即從當(dāng)前結(jié)點(diǎn)開始進(jìn)行自動(dòng)連 續(xù)運(yùn)行 ,從而可以看到從當(dāng)前結(jié)點(diǎn)到終點(diǎn)的自動(dòng)搜索的連續(xù)過程 同時(shí)也可從自動(dòng)運(yùn)行狀態(tài)轉(zhuǎn)為手動(dòng)狀態(tài)。 2）驗(yàn)證程序。A*算法實(shí)現(xiàn)時(shí)有兩個(gè)關(guān)鍵問題需要解決 ， 一個(gè)是如何尋找并設(shè)計(jì)一個(gè)與問題有關(guān)的啟發(fā)函數(shù) 及構(gòu)造出估 價(jià)函數(shù)，另一個(gè)是在Open表中如何排列待擴(kuò)展?fàn)顟B(tài)的次序。為 了比較不同估價(jià)函數(shù)以及不同 Open表排序?qū)*算法求解問題的 影響,在如圖4所示的A*算法驗(yàn)證程序中

12、，給出了兩種不同的估 價(jià)函數(shù)以及兩種不同的排序方法 , 通過選擇相應(yīng)的估價(jià)函數(shù)及排 序方法,可以比較不同估價(jià)函數(shù)、不同排序方法的A*算法在求解 同一問題時(shí)的“搜索結(jié)果”、“訪問結(jié)點(diǎn)數(shù)”和“耗時(shí)”的差 異。 圖 4 八數(shù)碼問題的驗(yàn)證程序 考慮到盲目搜索和啟發(fā)式搜索之間的區(qū)別在普遍的教材上 解析得不夠詳細(xì) , 使得學(xué)生對算法的理解往往不夠清晰。為此 , 設(shè)計(jì)了寬度優(yōu)先搜索、廣度優(yōu)先搜索和A*算法來求解八數(shù)碼問 題的驗(yàn)證程序。 在驗(yàn)證程序中 , 通過單擊兩個(gè)“隨機(jī)產(chǎn)生”按鈕 , 不僅可以隨機(jī)生成問題的初始狀態(tài) , 而且也可以隨機(jī)生成目標(biāo)狀 態(tài);當(dāng)單擊“計(jì)算”按鈕時(shí) , 同樣首先判斷問題是否有解 ,最

13、后在 驗(yàn)證程序下方顯示不同算法的“搜索結(jié)果 / 步”、“訪問結(jié)點(diǎn)數(shù) / 個(gè)”和“耗時(shí) /毫秒”內(nèi)容 , 從而了解各算法的差異以及各自的 優(yōu)缺點(diǎn)。 3）自主實(shí)驗(yàn)。為了讓學(xué)生能夠自己動(dòng)手用A*算法來解決一 些實(shí)際問題 , 如圖 5所示,設(shè)計(jì)了一些求解傳教士和野人問題、 迷 宮問題、 最短路徑問題等一些作業(yè)題目。 同時(shí)“實(shí)驗(yàn)幫助”中也 提供了 A*算法中的一些核心代碼，使學(xué)生可以下載這些核心代碼 并在這些代碼的基礎(chǔ)上，通過修改代碼的過程中學(xué)會(huì)并掌握A*算 法。由于智能搜索教學(xué)軟件是在 Microsoft Visual Studio 2005 環(huán)境中用C+吾言開發(fā)的，所以通過設(shè)計(jì)型實(shí)驗(yàn)，可以讓學(xué)生在學(xué)

14、 習(xí)人工智能導(dǎo)論課程的基礎(chǔ)上 , 更好地熟悉 Microsoft Visual Studio 2005 環(huán)境以及C+語言的應(yīng)用實(shí)現(xiàn)。 圖5A*算法設(shè)計(jì)型實(shí)驗(yàn)界面 2.2 模擬退火算法 模擬退火算法最早由 Metropolis 在 1953 年提 出Kirkpatrick 等人在1983年成功地將模擬退火算法用于組合 優(yōu)化問題求解。作為求解復(fù)雜組合優(yōu)化問題的一種有效方法 , 模 擬退火算法已經(jīng)在許多工程和科學(xué)領(lǐng)域得到廣泛的應(yīng)用。 在模擬退火算法中 , 把某類優(yōu)化問題的求解過程與統(tǒng)計(jì)力學(xué) 中的熱平衡問題進(jìn)行對比 , 通過模擬高溫物體退火過程的方法 , 來找到優(yōu)化問題的全局最優(yōu)或近似全局最優(yōu)解 4

15、。模擬退火算 法以概率 1 找到全局最優(yōu)解的基本條件是初始溫度必須足夠高 , 在每個(gè)溫度下狀態(tài)的交換必須足夠充分 , 溫度 t 的下降必須足夠 緩慢。在進(jìn)行模擬退火算法的教學(xué)過程當(dāng)中 , 由于現(xiàn)有的課件和 動(dòng)畫的固有限制 , 無法把模擬退火算法求解問題的整個(gè)過程做一 個(gè)完整的展示 , 同時(shí)針對具體的問題 , 如何設(shè)置合適的參數(shù)以及 參數(shù)設(shè)置對算法優(yōu)化性能的影響也無法做一個(gè)完整的描述和解 析 , 所以學(xué)生在學(xué)習(xí)這部分的內(nèi)容時(shí)較難理解。 針對以上所述模擬退火算法的教學(xué)問題 , 設(shè)計(jì)了模擬退火算 法求解TSP問題的演示程序（如圖6所示）和驗(yàn)證程序（如圖7所 示）, 還給出了模擬退火算法的介紹界面 （

16、如圖 8所示）, 以及應(yīng)用 模擬退火算法求解其他問題的一些自主設(shè)計(jì)實(shí)驗(yàn)題目。TSP問題, 即旅行商問題是 ,有 個(gè)城市 ,城市間的距離用矩陣 表示, 表示 城市 與城市 之間的距離。有一個(gè)旅行商從一個(gè)城市出發(fā) , 每個(gè) 城市訪問一次 , 并且只能訪問一次 , 最后回到出發(fā)城市。 問如何行 走才能使得行走的路徑長度最短。 圖6TSP問題演示程序 圖7TSP問題驗(yàn)證程序 進(jìn)入模擬退火算法模塊 , 首先可以通過模擬退火算法的算法 介紹界面 , 如圖 8所示, 了解模擬退火算法的有關(guān)演算步驟、 相應(yīng) 的偽代碼和應(yīng)用模擬退火算法時(shí)的一些參數(shù)設(shè)置問題。 圖 8 模擬退火算法介紹界面 在模擬退火算法求解 T

17、SP問題的演示程序中，可以通過“新 解產(chǎn)生演示”模塊，如圖9所示，以8個(gè)城市（城市07）的TSP 問題為例 , 了解“兩點(diǎn)互換”、“相鄰互換”、“區(qū)間逆轉(zhuǎn)”、 “單點(diǎn)移動(dòng)”這四種新解產(chǎn)生函數(shù)的差異 , 其中 8個(gè)城市的任何 一種排列均是問題的一個(gè)可能解 ; 單擊“下一步”可以看到上述 四種產(chǎn)生函數(shù)的整個(gè)變化過程。另外通過演示程序的“ TSP 問題 演示”模塊，如圖6所示,針對8個(gè)城市的TSP問題（城市位置見 “地圖”方框 ）, 可以選擇不同的新解產(chǎn)生函數(shù) , 在給定初始溫 度、降溫率、最低溫度的情況下 , 連續(xù)單擊“運(yùn)行 / 下一步”可以 進(jìn)行手動(dòng)的單步運(yùn)行 , 并在“地圖”方框顯示 8個(gè)城市

18、 的旅行路線變化情況 , 與此同時(shí) , “搜索過程”框顯示模擬 退火算法在求解8個(gè)城市的TSP過程中“當(dāng)前溫度”、“當(dāng)前能 量”、“新能量”、“替換概率”等變化情況。若單擊“連續(xù)運(yùn) 行”可以連續(xù)顯示模擬退火算法求解 8個(gè)城市TSP問題的整個(gè)搜 索過程和“地圖”路線變化情況。 圖9TSP問題新解的產(chǎn)生函數(shù)演示 在模擬退火算法求解 TSP問題的驗(yàn)證程序中，如圖7所示， 通過單擊“隨機(jī)添加”按鈕和設(shè)置城市數(shù) , 可以在“地圖”方框 中隨機(jī)產(chǎn)生 個(gè)城市的坐標(biāo)位置 , 從而實(shí)現(xiàn)模擬退火算法對不同 規(guī)模的TSP問題的求解，同時(shí)也可以通過“重置”按鈕清空“地 圖”方框顯示。單擊“開始”按鈕后 , 可以在“地

19、圖”方框得到 模擬退火算法的最后求解結(jié)果 , 即 個(gè)城市的旅行路線 , 同時(shí)在 “地圖”上方顯示最好解、 最差解和平均解質(zhì)量。 而通過選擇不 同的新解產(chǎn)生函數(shù) , 設(shè)置不同的初始溫度、降溫率、最低溫度和 迭代步數(shù)這四個(gè)參數(shù) , 比較不同的產(chǎn)生函數(shù)、不同的參數(shù)設(shè)置對 模擬退火算法性能的影響。 另外驗(yàn)證程序左側(cè)下方“狀態(tài)”提示 顯示“停止”和“計(jì)算中”這兩種程序執(zhí)行信息。 在模擬退火算法的自主設(shè)計(jì)實(shí)驗(yàn)中 , 給出了學(xué)生自主應(yīng)用模 擬退火算法解決TSP問題、車輛路徑問題和 Flow Shop問題等一 些設(shè)計(jì)型作業(yè)題目 , 使學(xué)生可以在系統(tǒng)所提供的模擬退火算法核 心代碼的基礎(chǔ)上 , 自己動(dòng)手修改代碼

20、, 從而更好地掌握模擬退火 算法的精髓。 2.3 遺傳算法 遺傳算法 (Genetic Algorithms,GA) 是基于生物界自然選擇 和基因遺傳學(xué)原理的一種廣為應(yīng)用的、高效的隨機(jī)搜索算法 ,20 世紀(jì) 60 年代由美國的密執(zhí)根大學(xué)的 Holland 教授首先提出。該 算法將優(yōu)化問題看作是自然界中生物的進(jìn)化過程, 通過模擬大自 然中生物進(jìn)化過程中的遺傳規(guī)律 , 來達(dá)到尋優(yōu)的目的。近年來 , 遺傳算法已廣泛地應(yīng)用于作業(yè)調(diào)度與排序、 可靠性設(shè)計(jì)、 車輛路 徑選擇與調(diào)度、成組技術(shù)、設(shè)備布置與分配、交通問題等等。 用遺傳算法求解優(yōu)化問題 , 首先對優(yōu)化問題的解進(jìn)行編碼 , 編碼后的一個(gè)解稱為一個(gè)染

21、色體 , 組成染色體的元素稱為基因。 一個(gè)群體由若干個(gè)染色體組成 , 染色體的個(gè)數(shù)稱為群體的規(guī)模。 在遺傳算法中用適應(yīng)度函數(shù)表示環(huán)境 , 它是已編碼的解的函數(shù) , 是一個(gè)解適應(yīng)環(huán)境程度的評價(jià)。當(dāng)適應(yīng)度函數(shù)確定后 , 自然選擇 規(guī)律以適應(yīng)度函數(shù)值的大小來決定一個(gè)染色體是否繼續(xù)生存下 去的概率。生存下來的染色體成為種群 , 它們中的部分或全部以 一定的概率進(jìn)行交叉、變異 , 從而得到下一代群體。 在遺傳算法的教學(xué)過程中 , 也存在和模擬退火算法一樣的問 題,為了增加學(xué)生在教學(xué)活動(dòng)中的參與感, 激發(fā)起他們的學(xué)習(xí)熱 情，同樣也設(shè)計(jì)開發(fā)了遺傳算法的介紹模塊，求解TSP問題的演 示程序和驗(yàn)證程序 , 以及

22、自主實(shí)驗(yàn)?zāi)K。遺傳算法的介紹模塊提 供“算法描述”、“算法參數(shù)”、“算法特點(diǎn)”等介紹 （如圖 10 所示）。 圖 10 遺傳算法介紹界面 在遺傳算法求解TSP問題的演示程序中，通過“交叉操 作演示”和“變異操作演示”模塊 , 了解“部分匹配交叉”和 “順序交叉”這兩種交叉操作 （如圖 11所示）, 以及“兩點(diǎn)互 換”、“相鄰互換”、“區(qū)間逆轉(zhuǎn)”、“單點(diǎn)移動(dòng)”這四種變異 操作 （同模擬退火算法的新解產(chǎn)生 ）的差異。在演示程序的“ TSP 問題演示”中，如圖12所示,針對10個(gè)城市的TSP問題,通過選 擇不同的交叉和變異操作 , 在給定種群規(guī)模、交叉概率、變異概 率和迭代步數(shù)等算法參數(shù)的情況下 , 連續(xù)單擊“下一步”可以進(jìn) 行手動(dòng)的單步運(yùn)行 , 并在程序右側(cè)顯示城市旅行路線的變化 , 與 此同時(shí) , 程序下方顯示遺傳算法求解過程中當(dāng)前迭代次數(shù)、當(dāng)前 步驟、當(dāng)前最優(yōu)個(gè)體、當(dāng)前最優(yōu)個(gè)體的適應(yīng)度、當(dāng)前種群的平均 適應(yīng)度等變化。若單擊“自動(dòng) / 手動(dòng)”可由“手動(dòng)”運(yùn)行轉(zhuǎn)為 “自動(dòng)”運(yùn)行,從而可以連續(xù)顯示遺傳算法求解 10個(gè)城市TSP問 題的整個(gè)搜索過程和“地圖”路線變化情況 ; 反之也可由“自 動(dòng)”運(yùn)行轉(zhuǎn)為“手動(dòng)”運(yùn)行。 圖 11 交叉操作演示 圖 12遺傳算法演示程序 在遺傳算法（GA）求解TSP問題的驗(yàn)證程序中