張砦-遺傳算法在多目標(biāo)優(yōu)化中的應(yīng)用(編輯修改稿)
2025-01-19 17:27 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 行兩兩 隨機(jī) 配對(duì)。 Ⅱ. 每一對(duì)相互配對(duì)的個(gè)體， 隨機(jī) 設(shè)置某一基因座之后的位置為交叉點(diǎn)。 Ⅲ. 對(duì)每一對(duì)相互配對(duì)的個(gè)體，依設(shè)定的 交叉概率 pc在其交叉點(diǎn)處相互交換兩個(gè)個(gè)體的部分染色體，從而產(chǎn)生出兩個(gè)新的個(gè)體。 單點(diǎn)交叉 A； 10110111 00 A’： 10110111 11 B： 00011100 11 B’： 00011100 00 （ 5）變異算子 基本位變異算子： 最簡(jiǎn)單和最基本的變異操作算子。 對(duì)于基本遺傳算法中用二進(jìn)制編碼符號(hào)串所表示的個(gè)體，若需要進(jìn)行變異操作的某一基因座上的原有基因值為 0，則變異操作將該基因值變?yōu)?1，反之，若原有基因值為 1，則變異操作將其變?yōu)?0。 具體執(zhí)行過(guò)程： Ⅰ. 對(duì)個(gè)體的每一個(gè)基因座，依 變異概率 pm指定其為變異點(diǎn)。 Ⅱ. 對(duì)每一個(gè)指定的變異點(diǎn)，對(duì)其基因值做取反運(yùn)算或用其它等位基因值來(lái)代替，從而產(chǎn)生出一個(gè)新的個(gè)體。 A： 1010 1 01010 A’ ： 1010 0 01010 變異點(diǎn) 基本位變異 開(kāi)始 Gen=0 編碼 隨機(jī)產(chǎn)生 M個(gè)初始個(gè)體 滿足終止條件 ? 計(jì)算群體中各個(gè)體適應(yīng)度 從左至右依次執(zhí)行遺傳算子 j = 0 j = 0 j = 0 根據(jù)適應(yīng)度選擇復(fù)制個(gè)體 選擇兩個(gè)交叉?zhèn)€體 選擇個(gè)體變異點(diǎn) 執(zhí)行變異 執(zhí)行交叉 執(zhí)行復(fù)制 將復(fù)制的個(gè)體添入新群體中 將交叉后的兩個(gè)新個(gè)體添入新群體中 將變異后的個(gè)體添入新群體中 j = j+1 j = j+2 j = j+1 j = M? j = pcM ? j = pmLM? Gen=Gen+1 輸出結(jié)果 終止 Y N Y Y Y N N N pc pm 算法流程圖 遺傳算法的特點(diǎn) （ 1）群體搜索，易于并行化處理； （ 2）不是盲目窮舉，而是啟發(fā)式搜索； （ 3）適應(yīng)度函數(shù)不受連續(xù)、可微等條件的約束，適用范圍很廣。 遺傳算法的本質(zhì)： 對(duì)染色體模式所進(jìn)行的一系列運(yùn)算，即通過(guò)選擇算子將當(dāng)前種群中的優(yōu)良模式遺傳到下一代種群中，利用交叉算子進(jìn)行模式重組，利用變異算子進(jìn)行模式突變。通過(guò)這些遺傳操作，模式逐步向較好的方向進(jìn)化，最終得到問(wèn)題的最優(yōu)解。 遺傳算法的收斂性分析 遺傳算法要實(shí)現(xiàn)全局收斂，首先要求任意初始種群經(jīng)有限步都能到達(dá)全局最優(yōu)解，其次算法必須由保優(yōu)操作來(lái)防止最優(yōu)解的遺失。與算法收斂性有關(guān)的因素主要包括種群規(guī)模、選擇操作、交叉概率和變異概率。 (1) 種群規(guī)模對(duì)收斂性的影響 通常，種群太小則不能提供足夠的采樣點(diǎn)，以致算法性能很差；種群太大，盡管可以增加優(yōu)化信息，阻止早熟收斂的發(fā)生，但無(wú)疑會(huì)增加計(jì)算量，造成收斂時(shí)間太長(zhǎng)，表現(xiàn)為收斂速度緩慢。 (2)選擇操作對(duì)收斂性的影響 選擇操作使高適應(yīng)度個(gè)體能夠以更大的概率生存，從而提高了遺傳算法的全局收斂性。如果在算法中采用最優(yōu)保存策略，即將父代群體中最佳個(gè)體保留下來(lái)，不參加交叉和變異操作，使之直接進(jìn)入下一代，最終可使遺傳算法以概率 1收斂于全局最優(yōu)解。 (3)交叉概率對(duì)收斂性的影響 交叉操作用于個(gè)體對(duì)，產(chǎn)生新的個(gè)體，實(shí)質(zhì)上是在解空間中進(jìn)行有效搜索。交叉概率太大時(shí)，種群中個(gè)體更新很快，會(huì)造成高適應(yīng)度值的個(gè)體很快被破壞掉；概率太小時(shí)，交叉操作很少進(jìn)行，從而會(huì)使搜索停滯不前，造成算法的不收斂。 (4)變異概率對(duì)收斂性的影響 變異操作是對(duì)種群模式的擾動(dòng)，有利于增加種群的多樣性 。但是，變異概率太小則很難產(chǎn)生新模式，變異概率太大則會(huì)使遺傳算法成為隨機(jī)搜索算法。 遺傳算法研究的主要問(wèn)題 (1)局部最優(yōu) (2)收斂速度問(wèn)題 (3)正確性問(wèn)題 (4)算法的實(shí)現(xiàn)性問(wèn)題 改進(jìn)：編碼方式、遺傳算子、控制參數(shù)。 遺傳算法的應(yīng)用 遺傳算法提供了一種求解復(fù)雜系統(tǒng)優(yōu)化問(wèn)題的通用框架，它不依賴于問(wèn)題的具體領(lǐng)域，對(duì)問(wèn)題的種類有很強(qiáng)的魯棒性，所以廣泛應(yīng)用于很多學(xué)科。下面是遺傳算法的一些主要應(yīng)用領(lǐng)域： (1) 函數(shù)優(yōu)化 函數(shù)優(yōu)化是遺傳算法的經(jīng)典應(yīng)用領(lǐng)域，也是對(duì)遺傳算法進(jìn)行性能評(píng)價(jià)的常用算例。對(duì)于一些非線性、多模型、多目標(biāo)的函數(shù)優(yōu)化問(wèn)題，用其他優(yōu)化方法較難求解，用遺傳算法可以方便地得到較好的結(jié)果。 (2) 組合優(yōu)化 隨著問(wèn)題規(guī)模的增大，組合優(yōu)化問(wèn)題的搜索空間也急劇擴(kuò)大，有時(shí)在目前的計(jì)算機(jī)上用枚舉法很難或甚至不可能求出其精確最優(yōu)解。對(duì)這類復(fù)雜問(wèn)題，人們己意識(shí)到應(yīng)把主要精力放在尋求其滿意解上，而遺傳算法是尋求這種滿意解的最佳工具之一。實(shí)踐證明，遺傳算法對(duì)于組合優(yōu)化中的 NP完全問(wèn)題非常有效。例如，遺傳算法已經(jīng)在求解旅行商問(wèn)題、背包問(wèn)題、裝箱問(wèn)題、圖形劃分問(wèn)題等方面得到成功的應(yīng)用。 (3) 生產(chǎn)調(diào)度問(wèn)題 生產(chǎn)調(diào)度問(wèn)題在很多情況下所建立起來(lái)的數(shù)學(xué)模型難以精確求解，即使經(jīng)過(guò)一些簡(jiǎn)化之后可以進(jìn)行求解，也會(huì)因簡(jiǎn)化得太多而使得求解結(jié)果與實(shí)際相差甚遠(yuǎn)。而目前在現(xiàn)實(shí)生產(chǎn)中也主要是靠一
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1