現(xiàn)代優(yōu)化算法-展示頁(yè)
2024-08-30 23:02本頁(yè)面
【正文】 法的特點(diǎn) 它們的共同特點(diǎn)：都是從任一解出發(fā)，按照某種機(jī)制，以一定的概率在整個(gè)求解空間中探索最優(yōu)解。智能優(yōu)化算法 智能優(yōu)化算法 智能優(yōu)化算法又稱為現(xiàn)代啟發(fā)式算法，是一種具有全局優(yōu)化性能、通用性強(qiáng)、且適合于并行處理的算法。這種算法一般具有嚴(yán)密的理論依據(jù)，而不是單純憑借專家經(jīng)驗(yàn)，理論上可以在一定的時(shí)間內(nèi)找到最優(yōu)解或近似最優(yōu)解。由于它們可以把搜索空間擴(kuò)展到整個(gè)問題空間，因而具有全局優(yōu)化性能。 遺傳算法的搜索機(jī)制 遺傳算法模擬自然選擇和自然遺傳過程中發(fā)生的繁殖、交叉和基因突變現(xiàn)象，在每次迭代中都保留一組候選解，并按某種指標(biāo)從解群中選取較優(yōu)的個(gè)體，利用遺傳算子(選擇、交叉和變異 )對(duì)這些個(gè)體進(jìn)行組合，產(chǎn)生新一代的候選解群，重復(fù)此過程，直到滿足某種收斂指標(biāo)為止。 基本遺傳算法的組成 （ 1）編碼（產(chǎn)生初始種群） （ 2）適應(yīng)度函數(shù) （ 3）遺傳算子（選擇、交叉、變異） （ 4）運(yùn)行參數(shù) 編碼 GA是通過某種編碼機(jī)制把對(duì)象抽象為由特定符號(hào)按一定順序排成的串。SGA使用二進(jìn)制串進(jìn)行編碼。 )10s i n()( ???? xxxf ?SGA對(duì)于本例的編碼 由于區(qū)間長(zhǎng)度為 3，求解結(jié)果精確到 6位小數(shù)，因此可將自變量定義區(qū)間劃分為 3 106等份。 幾個(gè)術(shù)語(yǔ) 基因型： 1000101110110101000111 表現(xiàn)型： 編碼 解碼 個(gè)體（染色體） 基因 初始種群 SGA采用隨機(jī)方法生成若干個(gè)個(gè)體的集合，該集合稱為初始種群。 適應(yīng)度函數(shù) 遺傳算法對(duì)一個(gè)個(gè)體（解）的好壞用適應(yīng)度函數(shù)值來評(píng)價(jià)，適應(yīng)度函數(shù)值越大，解的質(zhì)量越好。 選擇算子 遺傳算法使用選擇運(yùn)算來實(shí)現(xiàn)對(duì)群體中的個(gè)體進(jìn)行優(yōu)勝劣汰操作：適應(yīng)度高的個(gè)體被遺傳到下一代群體中的概率大；適應(yīng)度低的個(gè)體，被遺傳到下一代群體中的概率小。 SGA中選擇算子采用輪盤賭選擇方法。設(shè)群體大小為 n ，個(gè)體 i 的適應(yīng)度為 Fi，則個(gè)體 i 被選中遺傳到下一代群體的概率為： ???niiii FFP1/輪盤賭選擇方法的實(shí)現(xiàn)步驟 （ 1） 計(jì)算群體中所有個(gè)體的適應(yīng)度函數(shù)值（需要解碼）； （ 2） 利用比例選擇算子的公式，計(jì)算每個(gè)個(gè)體被選中遺傳到下一代群體的概率； （ 3） 采用模擬賭盤操作（即生成 0到 1之間的隨機(jī)數(shù)與每個(gè)個(gè)體遺傳到下一代群體的概率進(jìn)行匹配）來確定各個(gè)個(gè)體是否遺傳到下一代群體中。交叉運(yùn)算是遺傳算法區(qū)別于其他進(jìn)化算法的重要特征，它在遺傳算法中起關(guān)鍵作用，是產(chǎn)生新個(gè)體的主要方法。 單點(diǎn)交叉運(yùn)算 交叉前： 00000|01110000000010000 11100|00000111111000101 交叉后： 00000|00000111111000101 11100|01110000000010000 交叉點(diǎn) 變異算子 所謂變異運(yùn)算，是指依據(jù)變異概率 Pm 將個(gè)體編碼串中的某些基因值用其它基因值來替換，從而形成一個(gè)新的個(gè)體。交叉運(yùn)算和變異運(yùn)算的相互配合，共同完成對(duì)搜索空間的全局搜索和局部搜索。 基本位變異算子 基本位變異算子是指對(duì)個(gè)體編碼串隨機(jī)指定的某一位或某幾位基因作變異運(yùn)算。 基本位變異算子的執(zhí)行過程 變異前： 000001110000000010000 變異后： 000001110001000010000 變異點(diǎn) 運(yùn)行參數(shù) （ 1） M ： 種群規(guī)模 （ 2） T ： 遺傳運(yùn)算的終止進(jìn)化代數(shù) （ 3） Pc ： 交叉概率 （ 4） Pm ： 變異概率 SGA的框圖 產(chǎn)生初始群體 是否滿足停止準(zhǔn)則 是 輸出結(jié)果并結(jié)束 計(jì)算個(gè)體適應(yīng)度值 比例選擇運(yùn)算 單點(diǎn)交叉運(yùn)算 基本位變異運(yùn)算 否 產(chǎn)生新一代群體 執(zhí)行 M/2次 遺傳算法的特點(diǎn) （ 1）群體搜索，易于并行化處理； （ 2）不是盲目窮舉，而是啟發(fā)式搜索； （ 3）適應(yīng)度函數(shù)不受連續(xù)、可微等條件的約束，適用范圍很廣。在二進(jìn)制編碼中，模式是基于三個(gè)字符集 (0,1,*)的字符串，符號(hào) *代表任意字符，即 0 或者 1。例如 O(10**1)=3 。例如 δ(10**1)=4 。在遺傳操作中，即使階數(shù)相同的模式，也會(huì)有不同的性質(zhì)，而模式的定義距就反映了這種性質(zhì)的差異。 模式定理保證了較優(yōu)的模式（遺傳算法的較優(yōu)解）的數(shù)目呈指數(shù)增長(zhǎng)，為解釋遺傳算法機(jī)理提供了數(shù)學(xué)基礎(chǔ)。 積木塊假設(shè) 積木塊假設(shè)：遺傳算法通過短定義距、低階以及高平均適應(yīng)度的模式（積木塊），在遺傳操作下相互結(jié)合，最終接近全局最優(yōu)解。 遺傳算法的收斂性分析 遺傳算法要實(shí)現(xiàn)全局收斂，首先要求任意初始種群經(jīng)有限步都能到達(dá)全局最優(yōu)解，其次算法必須由保優(yōu)操作來防止最優(yōu)解的遺失。 種群規(guī)模對(duì) 收斂性的影響 通常，種群太小則不能提供足夠的采樣點(diǎn)，以致算法性能很差；種群太大，盡管可以增加優(yōu)化信息，阻止早熟收斂的發(fā)生，但無疑會(huì)增加計(jì)算量，造成收斂時(shí)間太長(zhǎng)，表現(xiàn)為收斂速度緩慢。如果在算法中采用最優(yōu)保存策略，即
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1