編寫組決策理論與方法第一講遺傳算法專題六智能決策主要內(nèi)容智能決策基本概念1遺傳算法的基本原理2基于遺傳算法的智能決策3一.智能決策基本概念

決策問(wèn)題：?jiǎn)稳藳Q策—>群決策

單目標(biāo)決策—>多目標(biāo)決策靜態(tài)決策—>動(dòng)態(tài)決策決策環(huán)境：確定型—>不確定型決策過(guò)程：結(jié)構(gòu)化—>非結(jié)構(gòu)化背景簡(jiǎn)介傳統(tǒng)決策支持系統(tǒng)(DecisionSupportSystem，DSS)智能決策支持系統(tǒng)(IntelligentDecisionSupportSystem，IDSS)引例

智能決策是在動(dòng)態(tài)和多維信息收集的基礎(chǔ)上，對(duì)復(fù)雜問(wèn)題進(jìn)行自主識(shí)別、判斷、推理，并做出前瞻性、實(shí)時(shí)性的決策過(guò)程，同時(shí)系統(tǒng)要具有自優(yōu)化、自適應(yīng)的能力。

具體來(lái)說(shuō)，就是收集大量的信息與知識(shí)，并將之存儲(chǔ)在數(shù)據(jù)庫(kù)和知識(shí)庫(kù)中，基于此對(duì)問(wèn)題進(jìn)行分解和分析，建立問(wèn)題求解模型，根據(jù)模型各部分的目標(biāo)、功能、數(shù)據(jù)和要求進(jìn)行求解，并將結(jié)果返回給決策者的過(guò)程?；靖拍罨靖拍?/p>

智能決策支持系統(tǒng)將人工智能融入決策系統(tǒng)中，對(duì)數(shù)據(jù)庫(kù)、模型庫(kù)、方法庫(kù)、知識(shí)庫(kù)進(jìn)行管理和調(diào)用，并使用智能方法進(jìn)行決策?；靖拍罨靖拍顑?yōu)化問(wèn)題函數(shù)極值問(wèn)題背包問(wèn)題最短路徑問(wèn)題形狀優(yōu)化多孔材料的設(shè)計(jì)拓?fù)鋯?wèn)題基本概念

優(yōu)化算法，就是一種搜索過(guò)程或規(guī)則，是基于某種思想或者機(jī)制，通過(guò)一定的途徑或規(guī)則得到滿足用戶要求的問(wèn)題解決方案。經(jīng)典優(yōu)化算法線性規(guī)劃、動(dòng)態(tài)規(guī)劃、整數(shù)規(guī)劃、分支定界等（運(yùn)籌學(xué)）智能優(yōu)化算法人工神經(jīng)網(wǎng)絡(luò)、遺傳算法、進(jìn)化規(guī)劃、模擬退火、禁忌搜索、蟻群搜索、粒子群算法及其混合優(yōu)化策略等基本概念智能優(yōu)化算法（IntelligentOptimizationAlgorithms）又稱為現(xiàn)代啟發(fā)式算法，是一種具有全局優(yōu)化性能、通用性強(qiáng)、且適合于并行處理的算法。這種算法一般具有嚴(yán)密的理論依據(jù)，而不是單純憑借專家經(jīng)驗(yàn)，理論上可以在一定的時(shí)間內(nèi)找到最優(yōu)解或近似最優(yōu)解。基本概念特點(diǎn)：都是從任一解出發(fā)，按照某種機(jī)制，以一定的概率在整個(gè)求解空間中探索最優(yōu)解。由于它們可以把搜索空間擴(kuò)展到整個(gè)問(wèn)題空間，因而具有全局優(yōu)化性能。通過(guò)模擬或揭示某些自然現(xiàn)象或過(guò)程而得到的優(yōu)化算法。算法構(gòu)造：直觀性+自然機(jī)理智能優(yōu)化算法蟻群算法人工魚群算法粒子群算法遺傳算法模擬退火算法基本概念人工蜂群算法二.GA基本原理

簡(jiǎn)介遺傳算法簡(jiǎn)稱GA（GeneticAlgorithms）是由美國(guó)密切根大學(xué)（Michigan）的霍蘭德（Holland）教授于1975年在他的專著《自然系統(tǒng)和人工系統(tǒng)的適應(yīng)性》中詳細(xì)闡述的，它是模擬自然界遺傳機(jī)制和生物進(jìn)化論而形成的一種并行隨機(jī)搜索最優(yōu)化方法。遺傳算法是以達(dá)爾文的自然選擇學(xué)說(shuō)為基礎(chǔ)發(fā)展起來(lái)的。GA基本原理個(gè)體（individual）：指模擬生物個(gè)體而對(duì)問(wèn)題中的對(duì)象的一種稱呼，一個(gè)個(gè)體也就是搜索空間中的一個(gè)點(diǎn)。種群（population）：指模擬生物種群而由若干個(gè)體組成的群體，它一般是整個(gè)搜索空間的一個(gè)很小的子集。染色體（chromosome）：指對(duì)個(gè)體進(jìn)行編碼后所得到的編碼串，是遺傳物質(zhì)的主要載體。自然選擇學(xué)（遺傳學(xué)）的術(shù)語(yǔ)：GA基本原理自然選擇學(xué)（遺傳學(xué)）的術(shù)語(yǔ)：基因（gene）：指染色體中的每一個(gè)位，即編碼串中的一個(gè)字符，是控制生物性狀遺傳物質(zhì)功能和結(jié)構(gòu)的基本單元，表示問(wèn)題解中每一分量的特征。1111111

1110111GA基本原理基因型（genotype）：染色體的內(nèi)部表現(xiàn)模式，是指與表現(xiàn)密切相關(guān)的基因組成。表現(xiàn)型（phenotype）：染色體的外部表現(xiàn)，是指生物個(gè)體表現(xiàn)出來(lái)的性狀。編碼（coding）：表現(xiàn)型到基因型的映射；解碼（decoding）：從基因型到表現(xiàn)型的映射。自然選擇學(xué)（遺傳學(xué)）的術(shù)語(yǔ)：1111111

編碼解碼適應(yīng)度（fitness），指借鑒生物個(gè)體對(duì)環(huán)境的適應(yīng)程度，而對(duì)問(wèn)題中的個(gè)體對(duì)象所設(shè)計(jì)的表征其優(yōu)劣的一種測(cè)度。GA基本原理適應(yīng)度函數(shù)（fitnessfunction），指問(wèn)題中的全體個(gè)體與其適應(yīng)度之間的一個(gè)對(duì)應(yīng)關(guān)系，用來(lái)對(duì)種群中各個(gè)個(gè)體進(jìn)行環(huán)境適應(yīng)性度量的函數(shù)。選擇（selection）：又稱為復(fù)制（reproduction），是用某種方法從群體中選取若干個(gè)體的操作。交叉（crossover）：又稱重組或雜交，是指互換兩個(gè)染色體某些位上的基因，實(shí)現(xiàn)兩個(gè)染色體重新組合的操作。變異（mutation）又稱突變，是指改變?nèi)旧w某個(gè)（些）位上的基因，讓遺傳因子以一定概率變化的操作。自然選擇學(xué)（遺傳學(xué)）的術(shù)語(yǔ)：GA基本原理基本思想

遺傳算法將“優(yōu)勝劣汰，適者生存”的生物進(jìn)化原理引入優(yōu)化參數(shù)編碼形成的基因碼鏈群體中，按所選擇的適應(yīng)度函數(shù)并通過(guò)遺傳中的選擇、交叉及變異對(duì)個(gè)體進(jìn)行篩選，使適應(yīng)度高的個(gè)體被保留下來(lái)，組成新的群體，新的群體既繼承了上一代的信息，又優(yōu)于上一代。這樣周而復(fù)始，群體中個(gè)體適應(yīng)度不斷提高，直到滿足一定的終止條件。遺傳算法的算法簡(jiǎn)單，可并行處理，并能到全局最優(yōu)解。GA基本原理算法流程基本遺傳算法可定義為一個(gè)7元組：

GA＝(M,F,s,c,m,pc,pm)M——群體大??；F——個(gè)體適應(yīng)度評(píng)價(jià)函數(shù)；s——選擇操作算子；c——交叉操作算子：m——變異操作算子；pc——交叉概率；pm——變異概率；GA基本原理求下列一元函數(shù)的最大值(求解結(jié)果精確到6位小數(shù))：編碼二進(jìn)制，實(shí)數(shù)，格雷碼型，…GA基本原理假設(shè)某一參數(shù)的取值范圍是[umin,umax]，我們用長(zhǎng)度為λ的二進(jìn)制編碼符號(hào)串來(lái)表示該參數(shù)，則它總共能夠產(chǎn)生2λ種不同的編碼，參數(shù)編碼時(shí)的對(duì)應(yīng)關(guān)系如下：00000000…00000000＝0umin

00000000…00000001＝1umin+

……11111111…11111111=2λ–1umax編碼精度假設(shè)某一個(gè)體的編碼是：

x：bλ-1bλ-2……b1b0

則對(duì)應(yīng)的解碼公式為：GA基本原理解碼精度要求

1/1000000

解：采用多少位二進(jìn)制數(shù)進(jìn)行編碼？2097152=221<3000001<222=4194304x需要22位二進(jìn)制數(shù)表示，例如1000101110110101000111

解碼：

編碼過(guò)程實(shí)質(zhì)上是將區(qū)間[-1,2]內(nèi)對(duì)應(yīng)的實(shí)數(shù)值轉(zhuǎn)化為一個(gè)二進(jìn)制串（b21b20…b0）。求下列一元函數(shù)的最大值(求解結(jié)果精確到6位小數(shù))：表現(xiàn)型：0.637197編碼解碼染色體：1000101110110101000111基因求下列一元函數(shù)的最大值(求解結(jié)果精確到6位小數(shù))：適應(yīng)度函數(shù)所有個(gè)體的適應(yīng)度必須為正數(shù)或零，不能是負(fù)數(shù)如果不能保證所有個(gè)體的適應(yīng)度為非負(fù)，則需要進(jìn)行尺度轉(zhuǎn)化，f(x)->F(x)100010111011010100011110101011101101011001111100101110110101001000……初始種群初始種群的適應(yīng)度值0.6371971.0122201.387198

……1）Generations（代數(shù)）——當(dāng)產(chǎn)生的代數(shù)達(dá)到規(guī)定的代數(shù)值時(shí)，算法停止。2）Timelimit（時(shí)限）——當(dāng)運(yùn)行時(shí)間等于時(shí)限時(shí)，算法停止。

3）Fitnesslimit（適應(yīng)度限）——當(dāng)適應(yīng)度函數(shù)的值到達(dá)某一限度時(shí)，算法停止。算法終止迭代的條件：算法終止迭代的條件：4）Stallgenerations（停滯代數(shù)）——在連續(xù)繁殖的時(shí)間序列中，若長(zhǎng)時(shí)間不繁殖新代，亦即目標(biāo)函數(shù)無(wú)改進(jìn)，到達(dá)停滯代數(shù)規(guī)定的代數(shù)時(shí)，則算法停止。5）Stalltimelimit（停滯時(shí)限）——在秒數(shù)等于停滯時(shí)限的時(shí)間間隔期間，若目標(biāo)函數(shù)無(wú)改進(jìn)，則算法停止。選擇算子（SelectionOperator）目的：從當(dāng)前群體中選出優(yōu)良個(gè)體，使其有機(jī)會(huì)作為父代。判斷個(gè)體優(yōu)良與否的標(biāo)準(zhǔn)是個(gè)體適應(yīng)度值。適應(yīng)度值越高，個(gè)體被選中的概率越大。常見(jiàn)的方法有比例選擇法（比率法）、排序選擇法（排列法）、聯(lián)賽選擇法（競(jìng)技法）三種類型輪盤賭：是比例選擇中最常用的一種策略?；舅枷耄簜€(gè)體被選中的概率取決于該個(gè)體的相對(duì)適應(yīng)度，根據(jù)相對(duì)適應(yīng)度值產(chǎn)生一個(gè)輪盤，然后產(chǎn)生一個(gè)隨機(jī)數(shù)，這個(gè)數(shù)落入輪盤的哪個(gè)區(qū)域就選擇相應(yīng)個(gè)體。特點(diǎn)：個(gè)體適應(yīng)度越高，被選中概率越大。但是適應(yīng)度小的個(gè)體也有可能備選中，以增加下一代群體多樣性?？刹捎镁⒉呗?。實(shí)現(xiàn)：首先計(jì)算群體中所有個(gè)體適應(yīng)度的總和，然后計(jì)算每個(gè)個(gè)體適應(yīng)度所占比例，并以此作為選擇相應(yīng)個(gè)體的概率。GA基本原理交叉算子（CrossoverOperator）

模擬生物進(jìn)化過(guò)程中的繁殖現(xiàn)象，通過(guò)來(lái)自雙親的兩個(gè)染色體的交換組合，以產(chǎn)生新的優(yōu)良個(gè)體。實(shí)現(xiàn)：選擇群體中的兩個(gè)個(gè)體，將這兩個(gè)個(gè)體作為雙親，進(jìn)行基因鏈碼的交叉，從而產(chǎn)生兩個(gè)新個(gè)體作為個(gè)體的后代。GA基本原理a.單點(diǎn)交叉b.兩點(diǎn)交叉c.均勻交叉單點(diǎn)交叉算子對(duì)群體中的個(gè)體進(jìn)行兩兩隨機(jī)配對(duì)；每一對(duì)配對(duì)個(gè)體，隨機(jī)設(shè)置某個(gè)基因座之后的位置為交叉點(diǎn)；對(duì)每一對(duì)配對(duì)個(gè)體，按照交叉概率在其交叉點(diǎn)處相互交換兩個(gè)個(gè)體的部分染色體，產(chǎn)生出兩個(gè)新的個(gè)體。GA基本原理單點(diǎn)交叉x1；1011011100

x1’：1011011111x2：0001110011x2’：0001110000N—種群中個(gè)體的數(shù)目Nc—種群中被交換個(gè)體的數(shù)目交叉概率變異算子（MutationOperator）目的：通過(guò)在染色體上某些基因位置產(chǎn)生突變，使得新產(chǎn)生個(gè)體與其他個(gè)體有所不同。實(shí)現(xiàn)：對(duì)群體中的某個(gè)個(gè)體（即基因鏈碼）隨機(jī)選擇一位（即基因），將該基因改變（對(duì)于二進(jìn)制，就是0改為1，1改為0）。GA基本原理基本位變異算子對(duì)個(gè)體的每一個(gè)基因座，按變異概率指定其為變異點(diǎn)；對(duì)每一個(gè)指定的變異點(diǎn)，對(duì)其基因值取反，從而產(chǎn)生出一個(gè)新的個(gè)體。A：1010101010A’：1010001010基本位變異pm—變異概率式中B——種群中變異的基因數(shù)目；N——種群擁有的個(gè)體數(shù)目

λ

——個(gè)體中基因串長(zhǎng)度。為什么需要變異算子？若只有選擇和交叉，而沒(méi)有變異，則無(wú)法在初始基因組合以外的空間進(jìn)行搜索，使進(jìn)化過(guò)程在早期就陷入局部解而進(jìn)入終止過(guò)程，從而影響解的質(zhì)量。為了在盡可能大的空間中獲得質(zhì)量較高的優(yōu)化解，必須采用變異操作。GA基本原理求下列一元函數(shù)的最大值(求解結(jié)果精確到6位小數(shù))：對(duì)參數(shù)的編碼進(jìn)行操作，而非對(duì)參數(shù)本身，便于在優(yōu)化計(jì)算過(guò)程中借鑒生物學(xué)中染色體和基因等概念；可同時(shí)使用多個(gè)搜索點(diǎn)的搜索信息，克服了傳統(tǒng)優(yōu)化方法往往從解空間的單個(gè)初始點(diǎn)開(kāi)始最優(yōu)解的迭代搜索過(guò)程的局限性，極大地提高了搜索效率；直接使用由目標(biāo)函數(shù)值變換來(lái)的適應(yīng)度函數(shù)值作為搜索信息，以確定進(jìn)一步的搜索方向和搜索范圍，而無(wú)需目標(biāo)函數(shù)的導(dǎo)數(shù)值等其他一些輔助信息。GA基本原理優(yōu)缺點(diǎn)分析GA基本原理優(yōu)缺點(diǎn)分析使用概率搜索技術(shù)。復(fù)制、交叉、變異等運(yùn)算都是以一種概率的方式來(lái)進(jìn)行的，因而其搜索過(guò)程具有很好的靈活性。對(duì)于待尋優(yōu)的函數(shù)基本無(wú)限制，它既不要求函數(shù)連續(xù)，也不要求函數(shù)可微，既可以是數(shù)學(xué)解析式所表示的顯函數(shù)，又可以是映射矩陣甚至是神經(jīng)網(wǎng)絡(luò)的隱函數(shù)，因而應(yīng)用范圍較廣。具有并行計(jì)算的特點(diǎn)，可通過(guò)大規(guī)模并行計(jì)算來(lái)提高計(jì)算速度，適合大規(guī)模復(fù)雜問(wèn)題的優(yōu)化。GA基本原理優(yōu)缺點(diǎn)分析隨機(jī)性是遺傳算法的本質(zhì)，因此很難對(duì)其進(jìn)行預(yù)測(cè)。有時(shí)候可能經(jīng)過(guò)幾代就可以找到正確解，有時(shí)候可能要無(wú)休止的迭代下去。如果需要快速求解問(wèn)題，不能依賴于隨機(jī)性。遺傳算法需要將求解的整個(gè)群體參與計(jì)算，即使是簡(jiǎn)單的基因型，都需要占用大量的內(nèi)存和計(jì)算資源。對(duì)于復(fù)雜的問(wèn)題，即使用足夠高速的計(jì)算機(jī)進(jìn)行交互式優(yōu)化，通常也是不現(xiàn)實(shí)的。適用范圍（1）函數(shù)優(yōu)化。（2）組合優(yōu)化。（3）任務(wù)分配（生產(chǎn)調(diào)度）（4）自動(dòng)控制領(lǐng)域（5）機(jī)器人（6）圖像處理GA基本原理三.基于遺傳算法的智能決策

遺傳算法則先羅列出可行的分配方案集，再對(duì)各個(gè)可行方案進(jìn)行比較，最終選擇最優(yōu)方案。能夠?qū)Ω鞣N火力分配方案進(jìn)行比較后保留最優(yōu)方案?；鹆Ψ峙湟话阌芍笓]實(shí)體完成。常見(jiàn)的決策方法是最近鄰目標(biāo)分配法：各個(gè)目標(biāo)由離該目標(biāo)最近的火力單元打擊。最近鄰目標(biāo)分配法是按照一定的分配規(guī)則確定火力分配方案，僅僅制定了一種方案，沒(méi)有進(jìn)行多種方案之間的比較，該方法在目標(biāo)數(shù)量較大時(shí)存在明顯的局限性。案例：基于遺傳算法的火力最優(yōu)分配航空兵對(duì)地火力突擊并實(shí)施對(duì)地攻擊為作戰(zhàn)任務(wù)，通過(guò)算法解決作戰(zhàn)中可能出現(xiàn)的空中作戰(zhàn)力量完全出動(dòng)情況：空中作戰(zhàn)力量通過(guò)一次突擊力爭(zhēng)徹底摧毀對(duì)方核心力量，使其不具備反制能力，即不按照傳統(tǒng)戰(zhàn)術(shù)保留預(yù)備力量，己方飛機(jī)全部出動(dòng)，力求一次飽和攻擊，摧毀目標(biāo)價(jià)值最大，即解決哪種機(jī)型多少飛機(jī)攻擊哪個(gè)目標(biāo)（群）的效果最佳。約束條件假設(shè)某機(jī)場(chǎng)當(dāng)前可用于執(zhí)行攻擊任務(wù)的飛機(jī)有2架H1型、2架H2型轟炸機(jī)，1架JH1型、2架JH2型殲轟機(jī)，1架QJ1型強(qiáng)擊機(jī)，1架QJ2型強(qiáng)擊機(jī)，現(xiàn)擬定所有可用飛機(jī)出動(dòng)，對(duì)敵方7個(gè)目標(biāo)進(jìn)行打擊。目標(biāo)的價(jià)值系數(shù)（此處用威脅度評(píng)價(jià)）和一架飛機(jī)對(duì)目標(biāo)的任務(wù)完成率是已知的，制定出兵