【文章內(nèi)容簡介】 現(xiàn)型兩者是有機體的顯性、生理和心理特征比如說眼睛的顏色、智力的基礎(chǔ)。 遼寧 科技大學(xué) 本科生 畢業(yè)設(shè)計 (論文 ) 第 7 頁 復(fù)制（ Repeoduction） 在復(fù)制中，首先發(fā)生的是交叉（ Crossover）。來自于父代的基因按照一定的方式組成了新的基因。 新的子代還可能發(fā)生變異 （ Mutation） 。變異的意思是 DNA 上的某一些成分發(fā)生了一點點的變化。 這些改變可能是由于在由父代到子代的基因復(fù)制中出現(xiàn)的誤差。 搜索空間 （ Search Space） 在很多情況下 ，我們解決一個問題就是從一大堆的數(shù)據(jù)中尋找一個解，而通常這個解都是混雜在數(shù)據(jù)中的。 所有可行解 （ Feasible Solution 可行解就是滿足了一定約束條件的解）組成的空間稱之為搜索空間（也可以稱之為狀態(tài)空間）。 搜索空間中的每一個點都是一個可 行解。每一個可行解都可以被它的函數(shù)值或者它的適應(yīng)度所標(biāo)記。 問題的解就是搜索 空間中的一個點，于是我們就是要從搜索空間中找到這個點。 這樣，求解問題就可以轉(zhuǎn)化為在搜索空間中尋找極值點（最大值或者最小值點） 。搜索空間在求解問題時可能是完全已知的，但一般來說我們只知道一些孤立的點，然后我們逐漸地生成其它點。問題是，這個搜索過程可能很復(fù) 雜，我們甚至不知道該去哪里搜索或者該從是么地方開始搜索。事實上，有很多尋找合適解（注意：不一定是最優(yōu)解）的方法，比如說爬山法（ Hill Climbing）禁止接近法 (Tabu Search),模擬退火算法(Simulated Annealing)以及遺傳算 法等等 .用遺傳算法求解出來的解一般被認(rèn)為是一個比較好的解 ,因為我們沒有辦法證明它是最優(yōu)解 . 遺傳算法的步驟 遺傳算法與傳統(tǒng)的搜索算法不同，它以適應(yīng)度函數(shù)為依據(jù)，通過對種群中的所有個體實施遺傳操作，實現(xiàn)群體內(nèi)個體結(jié)構(gòu)重組的迭代過程搜索法。選擇、雜交、變異構(gòu)成遺傳算法的 3個主要遺傳操作。參數(shù)編碼、初始群體 的設(shè)定適應(yīng)度函數(shù)設(shè)計、控制參數(shù)設(shè)定等要素組成遺傳算法的核心內(nèi)容。 其主要步驟是編碼→初始種群的生成→適應(yīng)度評估檢測→選擇→雜交→變異。 遺傳算法的特點 傳統(tǒng)的優(yōu)化方法主要有三種 ： 枚舉法、啟 發(fā)式算法和搜索算法 。 遺傳算法不同于傳統(tǒng)的搜索和優(yōu)化方法。主要區(qū)別在于 ： 遼寧 科技大學(xué) 本科生 畢業(yè)設(shè)計 (論文 ) 第 8 頁 1 自組織、自適應(yīng)和自學(xué)習(xí)性 （ 智能性 ）。 應(yīng)用遺傳算法求解問題時 ， 在編碼方案、適應(yīng)度函數(shù)及遺傳算子確定后 ，算法將利用進化過程中獲得的信息自行組織搜索。由于基于自然的選擇策略“適者生存、 不適者被淘汰 ”。因而適應(yīng)度大的個體具有較高的生存概率。 通常適應(yīng)度大的個體具有更適應(yīng)環(huán)境的基因結(jié)構(gòu) ， 再通過基因重組和基因突變等遺傳操作 ，就可能產(chǎn)生更適應(yīng)環(huán)境的后代。 進化算法的這種自組織、自適應(yīng)特征 ， 使它同時具有能根據(jù)環(huán)境變化來自動發(fā)現(xiàn)環(huán)境的特性和規(guī)律的能力。自 然選擇消除了算法設(shè)計過程中的一個最大障礙 ， 即需要事先描述問題的全部特點 ，并要說明針對問題的不同特點算法應(yīng)采取的措施。 因此 ， 利用遺傳算法 ， 我們可以解決那些復(fù)雜的非結(jié)構(gòu)化問 題。 2 遺傳算法的本質(zhì)并行性。遺傳算法按并行方式搜索一個種群數(shù)目的點 ，而不是單點。 它的并行性表現(xiàn)在兩個方面 ， 一是遺傳算法是內(nèi)在并行的 （ inherent parallelism） ,即遺傳算法本身非常適合大規(guī)模并行， 最簡單的并行方式是讓幾百甚至數(shù)千臺計算機各自進行獨立種群的演化計算 , 運行過程中甚至不進行任何通信 （ 獨立的種群之間若有少量的通信 一般會帶來更好的結(jié)果 )， 等到運算結(jié)束時才通信比較 ， 選取最佳個體。這種并行處理方式對并行系統(tǒng)結(jié)構(gòu)沒有什么限制和要求 ， 可以說 ， 遺傳算法適合在目前所有的并行機或分布式系統(tǒng)上進行并行處理 ，而且對并行效率沒有太大影響。 二是遺傳算法的內(nèi)含并行性 （ implicit parallelism）。 由于遺傳算法采用種群的方式組織搜索 ， 因而可同時搜索解空間內(nèi)的多個區(qū)域 ，并相互交流信息。 3 遺傳算法不需要求導(dǎo)或其他輔助知識 ， 而只需要影響搜索方向的目標(biāo)函數(shù)和相應(yīng)的適應(yīng)度函數(shù)。 4 遺傳算法強調(diào)概率轉(zhuǎn)換規(guī)則 ， 而不是確定的轉(zhuǎn)換規(guī)則。 5 遺傳算法可以更加直接的應(yīng)用 。 6 遺傳算法對給定問題 ， 可以產(chǎn)生許多的潛在解 ， 最終選擇可以 由使用者確定。 在某些特殊情況下 ， 如多目標(biāo)優(yōu)化問題不止一個解存在 ， 有一組 pareto最優(yōu)解。 這種遺傳算法對于確認(rèn)可替代解集而言是特別合適的。 遺傳算法在國內(nèi)外研究現(xiàn)狀 近年來 ， GA在商業(yè)應(yīng)用方面取得一系列重要成果。或許這也是它受到學(xué)術(shù)界之外的企業(yè)界、政府部門以及更廣泛的社會階層普遍重視的原因 。 GA的商業(yè)應(yīng)用五花八門 ， 遼寧 科技大學(xué) 本科生 畢業(yè)設(shè)計 (論文 ) 第 9 頁 覆蓋面甚廣 ， Coldb在 成果 。例如 ， 通用電器的計算機輔助設(shè)計系統(tǒng) Engeneous， 這是一個混合系統(tǒng) （ hyb rid system）， 采用了 GA以及其他傳統(tǒng)的優(yōu)化技術(shù)做為尋優(yōu)手段 。 Engeneous已成功地應(yīng)用于汽輪機設(shè)計 ， 并改善了新的波音 777發(fā)動機的性能。美國新墨西哥州州立大學(xué)心理學(xué)系開發(fā)了一個所謂的 Faceprint系統(tǒng) ， 可根據(jù)目擊者的印象通過計算機生成嫌疑犯的面貌。計算機在屏幕上顯示出 20種面孔 ，目擊者按十分制給這些面孔評分。 在這基礎(chǔ)上 ， GA按通常的選擇、交換和突變算子生成新的面孔。 Faceprint的效果很好 ， 已申報專利。同一個州的一家企業(yè) —— 預(yù)測公司 （ Prediction Company） 則首先開發(fā)了一組用于金融交易的時間序列預(yù)測和交易工具 ， 其中 GA 起了重要作用 ： 據(jù)說 ， 這一系統(tǒng)實際運行效果很好 ， 可以達到最好的交易員的水平 ， 引起銀行界的關(guān)注 。 GA在軍事上的應(yīng)用也有報道 ：如用于紅外線圖象目標(biāo)判別的休斯遺傳程序系統(tǒng) （ Hughes geic programming system）， 效果很好 ， 以至準(zhǔn)備把它固化成硬件。 就 GA本身的研究而言 ， 應(yīng)該說 ， 我國起步較晚 ， 近幾年才 陸續(xù)看到一些介紹性的文章、不多于兩三部的專著以及初步的研 究報告。 和國外工作比較 ， 一個顯著區(qū)別是 ，國內(nèi)工作多只停留在論文這一層次 ， 幾乎沒有看到具體實際應(yīng)用 ，與研究成果商品化的差距就更遠。 理論研究與實際應(yīng)用不夠緊密 ， 阻礙了我國高新技術(shù)的迅速發(fā)展 ，幾乎已經(jīng)成為頑癥。 因此 ， 在我國發(fā)展 GA，當(dāng)前應(yīng)該特別重視它的應(yīng)用和推廣普及。 學(xué)術(shù)界要主動和企業(yè)界連手開發(fā) GA的應(yīng)用 ， 要重視引進或自行研制類似于 Splicer的程序設(shè)計環(huán)境 ， 使 GA的應(yīng)用更加方便和快捷。國家組建的工程研究中心應(yīng)該在這方面發(fā)揮更大的作用。工科數(shù)學(xué)教育也應(yīng)有所調(diào)整 ， 以適應(yīng)高新技術(shù)發(fā)展的需要。 本文工作 本文 采用馬爾可夫方法， 對虛擬企業(yè)中的風(fēng)險 管理 問題進行了初 步的研究， 在本文中利用馬爾可夫?qū)ιa(chǎn)的整個過程進行動態(tài)跟蹤以達到對風(fēng)險的動態(tài)控制。 在 下面的章節(jié)中，根據(jù)馬爾可夫理論提出了馬爾可夫的動態(tài)風(fēng)險 管理 模型； 并深入討論了遺傳算法在此問題中的應(yīng)用。 遼寧 科技大學(xué) 本科生 畢業(yè)設(shè)計 (論文 ) 第 10 頁 2 風(fēng)險 管理 模型 基于馬爾可夫過程的風(fēng)險 管理 模型 馬爾可夫過程是一種比較常用的隨機過程，它描述的是這樣的情形：一個系統(tǒng)具有有限個狀態(tài)，系統(tǒng)在下一時刻的狀態(tài)取決于系統(tǒng)現(xiàn)在所處的狀態(tài)，而與以前的狀態(tài)無關(guān)，即系統(tǒng)的無后效性。系統(tǒng)由一種狀態(tài)轉(zhuǎn)移至另一種狀態(tài)的過程稱為 馬爾可夫過程。 馬爾可夫鏈分析是利用狀態(tài)間的狀態(tài)轉(zhuǎn)移概率 ijp 來反映系統(tǒng)狀態(tài)的動態(tài)變化， ijp 表示從第 i 狀態(tài)經(jīng)過一步轉(zhuǎn)移到第 j 狀態(tài)的概率， ? ?njip ij ,2,1,10 ???? 。以狀態(tài)轉(zhuǎn)移概率 ijp 為元素的矩陣稱為馬爾可夫鏈的一步狀態(tài)轉(zhuǎn)移概率矩陣，簡稱轉(zhuǎn)移矩陣，記為 P ，其每行元素之和為 1。 ?????????????nnnnnnpppppppppP????????212222111211 如果馬爾可夫鏈上的兩狀態(tài)可以相互轉(zhuǎn)移，則稱兩狀態(tài)是連通的。如果狀態(tài)空間中的任意兩狀態(tài)都是連通的，則稱此狀態(tài)空間是連通狀態(tài)空間。根據(jù)連通的概念，馬爾可夫的狀態(tài)空間可以分為不返回狀態(tài)（過渡態(tài)）和吸收態(tài)。在馬爾可夫鏈中如果有的狀態(tài)一旦進入就不能離開，則此狀態(tài)稱為吸收態(tài)。在馬爾可夫鏈中，如果有的狀態(tài)不屬于吸收態(tài)，則稱之為不返回狀態(tài) [5]。 一個具有 n 個不返回狀態(tài)和 m 個吸收狀態(tài)的馬爾可夫鏈可以表示為下列轉(zhuǎn)移矩陣： mn nmIRQP ???????? () 其中： Q 表示系統(tǒng)的不返回狀態(tài)之間的關(guān)系； R 表示不返回狀態(tài)和吸收態(tài)之間的關(guān)系； I ： m 階單位矩陣； ? ： nm? 零矩陣。易知，矩陣 ? ?nnijqQ ??，其中 10 ?? ijq （對所有的 ji, ）且 11 ???ni ijq，（ nj ??1 ） [5]。 遼寧 科技大學(xué) 本科生 畢業(yè)設(shè)計 (論文 ) 第 11 頁 依據(jù)馬爾可夫過程的基本原理，對虛擬企業(yè)風(fēng)險進行評價。首先分析整個過程可能出現(xiàn)的風(fēng)險因素，忽略次要因素。并依據(jù)風(fēng)險因素的影響把整個生產(chǎn)過程分成若干個狀態(tài)， 用馬爾可夫來追蹤整個生產(chǎn)過程的發(fā)展情況。現(xiàn)以兩階段為例對模型進行描述。假設(shè)整個生產(chǎn)過程分成兩個階段，準(zhǔn)備和運行階段。準(zhǔn)備階段有一個狀態(tài)，運行階段存在多種狀態(tài)，最后整個生產(chǎn)達到成功狀態(tài)。 馬爾可夫 鏈狀態(tài)空間 ? ? ? ?nxxxS , 21 ?? 狀態(tài)轉(zhuǎn)移矩陣 ?????????????????????????????????????????????1000000010000000000000000000000000000,21,2,41,4,31,3,21,23321124321124321????????????????nnnnnnnnnnnnnnnnnrrrrrrrrppppxxxxxxxIRQPxxxxxxx? （ ） 引入?yún)?shù) ijr 表示從狀態(tài) ix 進入吸收態(tài) jx 的概率， ip 表示從狀態(tài) ix 進入過渡態(tài) lx 的概率，則必有 10,10,1121 ?????? ?? ???? ilijnnj ijnl il prrp ? ?133211100000100000100000101 ????????????????????? ????????????????? nppppQIF （ ） ??? RFB??????????????????????????????????????????????????????? ?????????????2,21,24241323122211211,21,241,431,321,132100100000100000100000101nnnnnnnnnnnnmbbbbbbbbbbrrrrrrrrpppp?????????????? （ ） 在此基礎(chǔ)上進一步分析如下： 遼寧 科技大學(xué) 本科生 畢業(yè)設(shè)計 (論文 ) 第 12 頁 （ 1） 吸收矩陣 B 的第一行的兩個元素 1211,bb 分別表示完工概率和失敗率。 （ 2） 生產(chǎn)平均成本 C ：表示狀態(tài)占有成本矢量 。 ? ?ixf : f 的向量元素， 表示 狀態(tài) ix內(nèi)占有的成本 ? ? ? ? ? ?? ??????????????????????3212211,nnpppxfxfxfBfC?? 問題描述 項目的各個工序有不同的完工時間，對應(yīng)的完工成本和完工概率就不同，從而項目的完工時間、完工成本和完工概率也不同。決策者根據(jù)自身的實際情況選擇適合自己的措施。本文所研究的問題就是要在投入成本和用戶工期要求一定的條件下，使項目的各工序最小完工概率最大。 依據(jù)馬爾可夫過程的基本原理，得到 各工序的轉(zhuǎn)移矩陣： 1 編制任務(wù)計劃書 ?????????????????????????????10000000100000ttttttttttttP