【正文】 繁殖過程前的編碼樣本。在接下去的繁殖過程中，遺傳算法提供了交叉和變異兩種算子對挑選后的樣本進(jìn)行交換。這樣通過選擇和繁殖就產(chǎn)生了下一代編碼組。1980年以來，人們越來越清楚地意識到傳統(tǒng)人工智能方法的局限性，而且隨著計(jì)算機(jī)速度的提高及并行計(jì)算機(jī)的普及，遺傳算法和進(jìn)化計(jì)算對計(jì)算機(jī)速度的要求已不再是制約其發(fā)展的因素。 基因（gene） 所有的生物都是由細(xì)胞組成的。染色體是一串 DNA 的片斷，它為整個(gè)有機(jī)體提供了一種復(fù)制模式。每一個(gè)基因?yàn)橐粋€(gè)特定的蛋白質(zhì)編碼。所有可能的某一特定特征的屬性（比如，藍(lán)色，桔黃色等）被稱之為等位基因。 全部序列的基因物質(zhì)（或者全部的染色體）稱之為基因組（或染色體組）（Genome） 。基因型和后天的表現(xiàn)型兩者是有機(jī)體的顯性、生理和心理特征比如說眼睛的顏色、智力的基礎(chǔ)。來自于父代的基因按照一定的方式組成了新的基因。變異的意思是 DNA 上的某一些成分發(fā)生了一點(diǎn)點(diǎn)的變化。 搜索空間（Search Space） 在很多情況下，我們解決一個(gè)問題就是從一大堆的數(shù)據(jù)中尋找一個(gè)解，而通常這個(gè)解都是混雜在數(shù)據(jù)中的。搜索空間中的每一個(gè)點(diǎn)都是一個(gè)可行解。問題的解就是搜索空間中的一個(gè)點(diǎn)，于是我們就是要從搜索空間中找到這個(gè)點(diǎn)。搜索空間在求解問題時(shí)可能是完全已知的，但一般來說我們只知道一些孤立的點(diǎn)，然后我們逐漸地生成其它點(diǎn)。事實(shí)上，有很多尋找合適解（注意：不一定是最優(yōu)解）的方法，比如說爬山法（Hill Climbing）禁止接近法(Tabu Search),模擬退火算法(Simulated Annealing)一個(gè)比較好的解,因?yàn)槲覀儧]有辦法證明它是最優(yōu)解. 遺傳算法的步驟遺傳算法與傳統(tǒng)的搜索算法不同，它以適應(yīng)度函數(shù)為依據(jù)，通過對種群中的所有個(gè)體實(shí)施遺傳操作，實(shí)現(xiàn)群體內(nèi)個(gè)體結(jié)構(gòu)重組的迭代過程搜索法。參數(shù)編碼、初始群體的設(shè)定適應(yīng)度函數(shù)設(shè)計(jì)、控制參數(shù)設(shè)定等要素組成遺傳算法的核心內(nèi)容。 遺傳算法的特點(diǎn)傳統(tǒng)的優(yōu)化方法主要有三種：枚舉法、啟發(fā)式算法和搜索算法。主要區(qū)別在于：1 自組織、自適應(yīng)和自學(xué)習(xí)性（智能性） 。由于基于自然的選擇策略“適者生存、不適者被淘汰” 。通常適應(yīng)度大的個(gè)體具有更適應(yīng)環(huán)境的基因結(jié)構(gòu)，再通過基因重組和基因突變等遺傳操作，就可能產(chǎn)生更適應(yīng)環(huán)境的后代。自然選擇消除了算法設(shè)計(jì)過程中的一個(gè)最大障礙，即需要事先描述問題的全部特點(diǎn)，并要說明針對問題的不同特點(diǎn)算法應(yīng)采取的措施。2 遺傳算法的本質(zhì)并行性。它的并行性表現(xiàn)在兩個(gè)方面，一是遺傳算法是內(nèi)在并行的（inherent parallelism） ,即遺傳算法本身非常適合大規(guī)模并行，最簡單的并行方式是讓幾百甚至數(shù)千臺計(jì)算機(jī)各自進(jìn)行獨(dú)立種群的演化計(jì)算, 運(yùn)行過程中甚至不進(jìn)行任何通信（獨(dú)立的種群之間若有少量的通信一般會(huì)帶來更好的結(jié)果)，等到運(yùn)算結(jié)束時(shí)才通信比較，選取最佳個(gè)體。二是遺傳算法的內(nèi)含并行性（implicit parallelism） 。3 遺傳算法不需要求導(dǎo)或其他輔助知識，而只需要影響搜索方向的目標(biāo)函數(shù)和相應(yīng)的適應(yīng)度函數(shù)。5 遺傳算法可以更加直接的應(yīng)用。9 / 49在某些特殊情況下，如多目標(biāo)優(yōu)化問題不止一個(gè)解存在，有一組pareto最優(yōu)解。 遺傳算法在國內(nèi)外研究現(xiàn)狀近年來，GA在商業(yè)應(yīng)用方面取得一系列重要成果。GA的商業(yè)應(yīng)用五花八門，覆蓋面甚廣， 上的一篇專論較為詳細(xì)地介紹了美國近年來的一些成果。Engeneous已成功地應(yīng)用于汽輪機(jī)設(shè)計(jì)，并改善了新的波音777發(fā)動(dòng)機(jī)的性能。計(jì)算機(jī)在屏幕上顯示出20種面孔，目擊者按十分制給這些面孔評分。Faceprint的效果很好，已申報(bào)專利。GA在軍事上的應(yīng)用也有報(bào)道：如用于紅外線圖象目標(biāo)判別的休斯遺傳程序系統(tǒng)（Hughes geic programming system） ， 效果很好，以至準(zhǔn)備把它固化成硬件。和國外工作比較，一個(gè)顯著區(qū)別是，國內(nèi)工作多只停留在論文這一層次，幾乎沒有看到具體實(shí)際應(yīng)用，與研究成果商品化的差距就更遠(yuǎn)。因此，在我國發(fā)展GA，當(dāng)前應(yīng)該特別重視它的應(yīng)用和推廣普及。國家組建的工程研究中心應(yīng)該在這方面發(fā)揮更大的作用。 本文工作本文采用馬爾可夫方法，對虛擬企業(yè)中的風(fēng)險(xiǎn)管理問題進(jìn)行了初步的研究，在本10 / 49文中利用馬爾可夫?qū)ιa(chǎn)的整個(gè)過程進(jìn)行動(dòng)態(tài)跟蹤以達(dá)到對風(fēng)險(xiǎn)的動(dòng)態(tài)控制。2 風(fēng)險(xiǎn)管理模型 基于馬爾可夫過程的風(fēng)險(xiǎn)管理模型馬 爾 可 夫 過 程 是 一 種 比 較 常 用 的 隨 機(jī) 過 程 ， 它 描 述 的 是 這 樣 的 情 形 ： 一 個(gè) 系 統(tǒng)具 有 有 限 個(gè) 狀 態(tài) ， 系 統(tǒng) 在 下 一 時(shí) 刻 的 狀 態(tài) 取 決 于 系 統(tǒng) 現(xiàn) 在 所 處 的 狀 態(tài) ， 而 與 以 前 的狀 態(tài) 無 關(guān) ， 即 系 統(tǒng) 的 無 后 效 性 。 馬爾可夫鏈分析是利用狀態(tài)間的狀態(tài)轉(zhuǎn)移概率 來反映系統(tǒng)狀態(tài)的動(dòng)態(tài)變ijp化， 表示從第 狀態(tài)經(jīng)過一步轉(zhuǎn)移到第 狀態(tài)的概率， 。P ???????nnnpp?? ?? ?? ??21212如果馬爾可夫鏈上的兩狀態(tài)可以相互轉(zhuǎn)移，則稱兩狀態(tài)是連通的。根據(jù)連通的概念，馬爾可夫的狀態(tài)空間可以分為不返回狀態(tài)（過渡態(tài)）和吸收態(tài)。在馬爾可夫鏈中，如果有的狀態(tài)不屬于吸收態(tài)，則稱之為不返回狀態(tài) [5]。易知，矩陣 ，其中Imnm???nijqQ??（對所有的 ）且 ， （ ） [5]。首先分析整個(gè)過程可能出現(xiàn)的風(fēng)險(xiǎn)因素，忽略次要因素。現(xiàn)以兩階段為例對模型進(jìn)行描述。準(zhǔn)備階段有一個(gè)狀態(tài)，運(yùn)行階段存在多種狀態(tài)，最后整個(gè)生產(chǎn)達(dá)到成功狀態(tài)。B12,b（2）生產(chǎn)平均成本 ：表示狀態(tài)占有成本矢量。決策者根據(jù)自身的實(shí)際情況選擇適合自己的措施。依據(jù)馬爾可夫過程的基本原理，得到各工序的轉(zhuǎn)移矩陣：1 編制任務(wù)計(jì)劃書13 / 49 ()???????? ??? 1000 .. . ttttttttP2 技術(shù)設(shè)計(jì) ()???????? ???? 1000 2.. . ttttttttP3 機(jī)械裝配設(shè)計(jì) ()???????? ???1002... ttttP4 電器裝配設(shè)計(jì) ()???????? ???1003..616.. ttttP5 原材料及外購件購買14 / 49 ()???????? ???? 1000 3.. . ttttttttP6 機(jī)械裝配工藝規(guī)程 ()???????? ???1003..212.. ttttP7 零件設(shè)計(jì) ()???????? ???1002... ttttP8 電器裝配工藝規(guī)程 ()???????????1005... ttttP9 制定材料定額 ()???????? ???1005... ttttP10 零件加工15 / 49 ()???????? ???? 1000 3.. ... ttttttttP11 機(jī)械裝配 ()???????? ???? 1000 09.. ... ttttttttP12 電器裝配 ()???????????1005... ttttP13 調(diào)試 ???????????1005... ttttP現(xiàn)有某聯(lián)盟生產(chǎn)一種車，其工序流程如表 ：表 各工序風(fēng)險(xiǎn)規(guī)劃結(jié)果A 工序名稱 各工序?qū)?yīng)的時(shí)間 完工概率 完工成本（元）2 359B 技術(shù)任務(wù)書3 C 技術(shù)設(shè)計(jì) 8 308416 / 499 304510 30068 21809 2140D 機(jī)械裝配設(shè)計(jì)10 21004 545E 電器裝配設(shè)計(jì)5 5255 45616 4432F 原材料及外購件購買7 43035 10806 1056G 機(jī)械裝配工藝規(guī)程7 10328 21729 2132H 零件設(shè)計(jì)10 20901 224I 電器裝配工藝規(guī)程2 2082 制定材料定額3 5 897K 零件加工6 85216 17 18 19 L 機(jī)械裝配20 3858M 電器裝配 1 22417 / 492 2081 310N 調(diào)試2 270 風(fēng)險(xiǎn)管理模型 上例中的風(fēng)險(xiǎn)管理模型如下：　　　　 　 　　　　　　　　 ()???itbmnax?N,21??　　　　 　　 ().ts01CtiNi???　　　　　　　　 　　　　　　　　　　　　　 ()TtKi其中：：工序 的完工時(shí)間iti：工序 完工時(shí)間為 時(shí)對應(yīng)的完工概率??ibit：工序 完工時(shí)間為 時(shí)對應(yīng)的成本itCii：關(guān)鍵工序集合K：工序數(shù)目N：規(guī)定的項(xiàng)目完工時(shí)間0T：規(guī)定的項(xiàng)目完工成本C18 / 493 遺傳算法對風(fēng)險(xiǎn)管理模型的求解生物進(jìn)化論的觀點(diǎn)認(rèn)為：生物不但遺傳而且有變異，這種變異是因?yàn)槿旧w不但復(fù)制而且有交叉及基因突變，如果這種變異更適應(yīng)環(huán)境，那么這種產(chǎn)生變異的個(gè)體會(huì)繁衍下去，反之則被環(huán)境所淘汰，這就是適者生存，不適者被淘汰的自然法則。它是建立在自然選擇和遺傳變異基礎(chǔ)上的迭代自適應(yīng)概率性搜索算法。通過“染色體”群的一代一代不斷變化，包括復(fù)制、交叉、和變異等操作，最終收斂到“最適應(yīng)環(huán)境”的個(gè)體，從而求得問題的最優(yōu)解或滿意解。2 GA 的搜索過程是從問題解的一個(gè)集合開始的，而不是從單個(gè)個(gè)體開始的，具有19 / 49隱含并行搜索特性，從而大大減小了陷入局部極小的可能。4 GA 具有全局搜索能力，最善于搜索復(fù)雜問題和非線性問題 [6]。由于 GA 不是直接在解空間上進(jìn)行搜索，而是在一定編碼機(jī)制對應(yīng)的碼空間上進(jìn)行的，因此編碼的選擇是影響算法性能與效率的重要因素。2 確定適應(yīng)值函數(shù)：用于對個(gè)體進(jìn)行評價(jià)，也是優(yōu)化過程發(fā)展的依據(jù)。適應(yīng)值函數(shù)可以由很多方法得出，可以直接利用目標(biāo)函數(shù)，也可以通過目標(biāo)函數(shù)的變換來定義。對于目標(biāo)函數(shù)求極小值問題，可以采用倒數(shù)的方式或用一個(gè)極大值減去目標(biāo)函數(shù)值。該操作包括三個(gè)基本算子：選擇、交叉和變異。前者以正比于個(gè)體適應(yīng)值的概率來選擇相應(yīng)個(gè)體，后者則基于個(gè)體在種群中的排名來選擇相應(yīng)的個(gè)體。常用的有單點(diǎn)交叉和多點(diǎn)交叉，其中單點(diǎn)交叉就是隨機(jī)地在兩個(gè)父串上選擇一個(gè)交叉點(diǎn)，然后交換這兩個(gè)串的對應(yīng)的子串。4 算法參數(shù)的選?。褐饕ǚN群數(shù)目、交叉與變異概率、進(jìn)化代數(shù)、種群數(shù)目是影響算法優(yōu)化性能20 / 49和效率的因素之一。交叉概率用于控制交叉操作的頻率。交叉操作很少進(jìn)行，從而會(huì)使搜索停滯不前。概率太小不會(huì)產(chǎn)生新個(gè)體，概率太大則使 GA 成為隨機(jī)搜索。不過，目前還沒有一種判斷性能很好，適應(yīng)范圍很廣的控制標(biāo)準(zhǔn)，所以，一般的 GA 程序都使用由用戶控制的最大進(jìn)化代數(shù)來控制算法的進(jìn)程 [7]。Step2：判斷算法收斂準(zhǔn)則是否滿足。Step3：根據(jù)適應(yīng)值大小以一定的方式進(jìn)行選擇。復(fù)制、交叉、變異。Step5：重復(fù) Step2 到 Step4，直到滿足終止條件。 例 如 ：（ 2， 8， 10， 5， 5， 7， 10， 2， 2， 6， 20， 2， 2） ， 13 個(gè) 數(shù) 字 依 次 對 應(yīng) 13 個(gè) 工 序 ，每 個(gè) 位 置 上 的 數(shù) 字 對 應(yīng) 該 工 序 的 完 工 時(shí) 間 選 擇 。 每 個(gè) 染 色 體 代 表 一 個(gè) 解 決 方 案 。由于本問題中個(gè)工序的完工時(shí)間存在不同個(gè)數(shù)種選擇（不滿足矩陣的 原則） ，所以 MATLAB 的遺傳算法NM?模板中的隨機(jī)產(chǎn)生自然數(shù)編碼初始種群的函數(shù)不適用于本問題。3 計(jì) 算 適 值 ：在 本 問 題 中 ， 是 以 13 道 工 序 中 最 小 完 工 概 率 的 最 大 值 作 為 目 標(biāo) 函 數(shù) ， 考 慮 到 遺傳 算 法 本 身 就 是 按 照 最 大 值 排 序 的 特 點(diǎn) ， 所 以 就 以 本 問 題 的 目 標(biāo) 函 數(shù) 作 為 適 應(yīng) 值 函數(shù) 。 對 于 不 滿 足約 束 條 件 的 個(gè) 體 將 其 適 值 乘 以 的 系 數(shù) ， 以 便 在 下 一 步 驟 （ 選 擇 ） 時(shí) 降 低 其 被遺傳運(yùn)算選擇更新種群23 / 49選 擇 的 概 率 。5 交 叉 運(yùn) 算 ：采 用 單 點(diǎn) 交 叉 。 利 用 產(chǎn) 生 隨 機(jī) 數(shù) 的 方 法 ， 選 擇父 親 和 母 親 ， 然 后 再 隨 機(jī) 產(chǎn) 生 一 個(gè) 斷 點(diǎn) ， 進(jìn) 行 交 叉 。 由 于 本 問 題 采 用 自然 數(shù) 編 碼 方 式 ， 而 MATLAB 的遺傳算法模板中的變 異 函 數(shù) 只 能 做 二 進(jìn) 制 編 碼 的 變 異 ，所 以 本 設(shè) 計(jì) 中 設(shè) 計(jì) 了 一 種 全 新 的 可 進(jìn) 行 十 進(jìn) 制 編 碼 變 異 的 方 法 。 然 后 按 個(gè) 體 適 值 的 大 小 與 初 始 種 群 進(jìn) 行 比 對 重 新 產(chǎn) 生 新 的種 群 。另 外 本 設(shè) 計(jì) 還 嘗 試 運(yùn) 用 模 擬 退 火 算 法 中 保 留 最 優(yōu)