【文章內(nèi)容簡(jiǎn)介】 體。交叉運(yùn)算是遺傳算法區(qū)別于其它進(jìn)化算法的重要特征， 它在遺傳算法中起著關(guān)鍵作用，是產(chǎn)生新個(gè)體的主要方法， 決定了遺傳算法的 全局搜索能力 。 智能計(jì)算及其在數(shù)值計(jì)算中的應(yīng)用 A : 1 0 1 1 0 1 1 0B : 0 1 1 0 1 0 0 10 01 1 A : 1 0 1 1 0 1 1 0B : 0 1 1 0 1 0 0 1??1 10 0單 點(diǎn) 交 叉交 叉 點(diǎn)11( 1 )( 1 )t t tA B At t tB A BX X XX X X??????? ? ? ?? ? ? ??單點(diǎn)交叉 ： 算術(shù)交叉： 變異 （ mutation）：變異運(yùn)算是指將個(gè)體染色體編碼串 中的某些基因座上的基因值用該基因座上的其它等位基因來(lái) 替換從而形成一個(gè)新的個(gè)體。變異運(yùn)算只是產(chǎn)生新個(gè)體的輔 助方法，但也是一個(gè)必不可少的運(yùn)算步驟，它決定了遺傳算 法的 局部搜索能力 。通過(guò)變異操作可以維持 群體多樣性 ，防 止出現(xiàn)早熟現(xiàn)象，改善遺傳算法的局部搜索能力。 基本位變異：對(duì)個(gè)體編碼串中以變異概率隨機(jī)指定的某一位 或某幾位基因座上的基因值做變異運(yùn)算。二進(jìn)制中，把基因 值取反，即 0變 1， 1變 0。浮點(diǎn)數(shù)編碼中對(duì)選定的第 i個(gè)個(gè)體 進(jìn)行逆轉(zhuǎn)操作，如果浮點(diǎn)數(shù)變化范圍是 ，則 智能計(jì)算及其在數(shù)值計(jì)算中的應(yīng)用 ix?,i ne w i i oldx x x? ? ? 遺傳算法是一個(gè)迭代過(guò)程，它模擬生物在自然環(huán)境中的 遺傳和進(jìn)化機(jī)理，反復(fù)將選擇算子、交叉算子、變異算子作 用于群體，最終可得到問(wèn)題的最優(yōu)解或近似最優(yōu)解。遺傳算 法提供了一種求解復(fù)雜系統(tǒng)優(yōu)化問(wèn)題的 通用框架 ，它不依賴 于問(wèn)題的領(lǐng)域和種類。 對(duì)于一個(gè)需要進(jìn)行優(yōu)化計(jì)算的實(shí)際應(yīng)用問(wèn)題，可按下述 步驟構(gòu)造求解該問(wèn)題的遺傳算法 : 第一步：確定決策變量及其各種約束條件，即確定出個(gè)體的 表現(xiàn)型和問(wèn)題的解空間； 第二步：建立優(yōu)化模型，即確定出目標(biāo)函數(shù)的類型（求解目 標(biāo)函數(shù)的最大值還是最小值）及其數(shù)學(xué)描述形式或量化方法 智能計(jì)算及其在數(shù)值計(jì)算中的應(yīng)用 第三步：確定表示可行解的染色體編碼方法，即確定出個(gè)體 的基因型及遺傳算法的搜索空間； 第四步：確定解碼方法，即確定出由個(gè)體基因型到個(gè)體表現(xiàn) 型的對(duì)應(yīng)關(guān)系或轉(zhuǎn)換方法； 第五步：確定個(gè)體適應(yīng)度的量化評(píng)價(jià)方法，即確定出由目標(biāo) 函數(shù)值 到個(gè)體適應(yīng)度值 的轉(zhuǎn)換規(guī)則； 第六步：設(shè)計(jì)遺傳算法，即確定出選擇、交叉、變異等遺傳 算子的具體操作方法； 第七步：確定遺傳算法的有關(guān)運(yùn)行參數(shù)，包括個(gè)體數(shù)、進(jìn)化 代數(shù)、變異概率、交叉概率等。 智能計(jì)算及其在數(shù)值計(jì)算中的應(yīng)用 ()fX ()FX智能計(jì)算及其在數(shù)值計(jì)算中的應(yīng)用 最 優(yōu) 化 問(wèn) 題 描 述確 定 決 策 變 量 、 約 束 條 件建 立 優(yōu) 化 模 型 X個(gè) 體 表 現(xiàn) 型 ( )fX目 標(biāo) 函 數(shù) X個(gè) 體 基 因 型 ( )FX適 應(yīng) 度 設(shè) 計(jì) 遺 傳 算 子確 定 運(yùn) 行 參 數(shù)遺 傳 算 法第 一 步 第 二 步解 空 間遺 傳 空 間編 碼 方 法解 碼 方 法確 定 適 應(yīng) 度 轉(zhuǎn) 換 規(guī) 則第 三 步 第 四 步 第 五 步第 六 步第 七 步具體的運(yùn)算步驟： 第一步：初始化，設(shè)置進(jìn)化代數(shù)記數(shù)器 ，設(shè)置最大進(jìn) 化代數(shù) T，隨機(jī)生成 M個(gè)個(gè)體作為初始群體 ； 第二步：個(gè)體評(píng)價(jià)，計(jì)算群體 中每個(gè)個(gè)體的適應(yīng)度 第三步：選擇運(yùn)算； 第四步：交叉運(yùn)算； 第五步：變異運(yùn)算，群體 經(jīng)過(guò)選擇、交叉、變異運(yùn)算得到 下一代群體 ； 第六步：終止條件判斷，若 ，則 ，轉(zhuǎn)到第二 步；若 ，則以進(jìn)化過(guò)程中所得到的具有最大適應(yīng)度的 個(gè)體作為最優(yōu)解輸出，終止計(jì)算。 智能計(jì)算及其在數(shù)值計(jì)算中的應(yīng)用 0 t?(0)P()Pt ()Ft()Pt( 1)Pt?tT? 1tt??tT?智能計(jì)算及其在數(shù)值計(jì)算中的應(yīng)用 ()Pt群 體選 擇 運(yùn) 算交 叉 運(yùn) 算變 異 運(yùn) 算( 1 )Pt ?群 體 解 集 合個(gè) 體 評(píng) 價(jià)遺 傳 空 間解 空 間解 碼 群體智能算法 （ Swarm Intelligence Algorithm）的研究 開(kāi)始于 20世紀(jì) 90年代，其基本思想是模擬自然界生物的 群體 行為 來(lái)構(gòu)造隨機(jī)優(yōu)化算法。典型的有蟻群算法、粒子群算法、 人工魚(yú)群算法等。 粒子群優(yōu)化 （ Particle Swarm Optimization， PSO）算 法由美國(guó)社會(huì)心理學(xué)家 James Kennedy和電氣工程師 Eberhart 共同提出?；舅枷胧鞘艿进B(niǎo)群和魚(yú)群群體覓食行為研究結(jié) 果的啟發(fā)，與基于達(dá)爾文“適者生存，優(yōu)勝劣汰”進(jìn)化思想不 同，粒子群優(yōu)化算法是通過(guò) 個(gè)體間的協(xié)作 來(lái)尋找最優(yōu)解的。 作為一種新的并行優(yōu)化進(jìn)化算法，粒子群優(yōu)化算法具有很強(qiáng) 的 通用性 ，可用于解決大量 非線性、不可微和多峰值的復(fù)雜 問(wèn)題 優(yōu)化，并已廣泛應(yīng)用于科學(xué)和工程領(lǐng)域。 智能計(jì)算及其在數(shù)值計(jì)算中的應(yīng)用 自然界中各種生物體均具有一定的 群體行為 ，人工生命 的主要研究領(lǐng)域之一就是探索自然界生物的群體行為，從而 在計(jì)算機(jī)上構(gòu)建其群體模型。通常，群體行為可以由幾條簡(jiǎn) 單的規(guī)則進(jìn)行建模，但群體表現(xiàn)出的行為卻非常復(fù)雜。在對(duì) 鳥(niǎo)群行為進(jìn)行仿真時(shí)，可以采用下面三條簡(jiǎn)單規(guī)則： （ 1）飛離最近的個(gè)體，避免碰撞； （ 2）飛向目標(biāo)； （ 3）飛向群體的中心。 群體內(nèi)的每一個(gè)體的行為可采用上述規(guī)則描述，這是粒子群 算法的基本概念之一。 智能計(jì)算及其在數(shù)值計(jì)算中的應(yīng)用 在研究人類的決策過(guò)程中，人們提出了個(gè)體學(xué)習(xí)和文化 傳遞的概念。一個(gè)人在決策過(guò)程中，會(huì)使用兩類重要的信息： 一是 自身的經(jīng)驗(yàn) ，二是 其他人的經(jīng)驗(yàn) 。也就是說(shuō)，人們根據(jù) 自身的經(jīng)驗(yàn)和他人的經(jīng)驗(yàn)進(jìn)行自己的決策。這是粒子群算法 的另一基本概念。 粒子群（ PSO）算法與其它進(jìn)化類算法相類似，也采用 “群體”與“進(jìn)化”的概念，同樣也是依據(jù)個(gè)體（粒子）的適應(yīng)度 大小進(jìn)行操作。粒子群算法將每個(gè)個(gè)體看作是在 N維搜索空間 中的一個(gè)沒(méi)有重量和體積的粒子，并在搜索空間中以一定的 速度飛行。飛行速度由 個(gè)體的飛行經(jīng)驗(yàn) 和 群體的飛行經(jīng)驗(yàn) 進(jìn) 行動(dòng)態(tài)調(diào)整。 智能計(jì)算及其在數(shù)值計(jì)算中的應(yīng)用 假設(shè) 為粒子 的當(dāng)前位置， 為粒子 的當(dāng)前飛行速度， 為粒子 所飛 過(guò)的最好位置，也就是粒子 所經(jīng)歷過(guò)的具有最好適應(yīng)度的位 置，稱為 個(gè)體最好位置 。對(duì)于最小化問(wèn)題，目標(biāo)函數(shù)值越小 ，對(duì)應(yīng)的適應(yīng)度越好。為了討論方便，設(shè) 為最小化的目 標(biāo)函數(shù)，則粒子 的當(dāng)前最好位置由下式確定： 智能計(jì)算及其在數(shù)值計(jì)算中的應(yīng)用 12( , , , )i i i inX x x x? ??? i 12( , , , )i i i inV v v v? ???i 12( , , , )i i i inP p p p? ??? ii()fXi( ) , ( ( 1 ) ) ( ( ) )( 1 )( 1 ) , ( ( 1 ) ) ( ( ) )i i iii