現(xiàn)代優(yōu)化算法-文庫吧
2025-07-31 23:02 本頁面
【正文】 ，從而形成一個新的個體。遺傳算法中的變異運(yùn)算是產(chǎn)生新個體的輔助方法，它決定了遺傳算法的局部搜索能力，同時保持種群的多樣性。交叉運(yùn)算和變異運(yùn)算的相互配合，共同完成對搜索空間的全局搜索和局部搜索。 SGA中變異算子采用基本位變異算子。 基本位變異算子 基本位變異算子是指對個體編碼串隨機(jī)指定的某一位或某幾位基因作變異運(yùn)算。對于基本遺傳算法中用二進(jìn)制編碼符號串所表示的個體，若需要進(jìn)行變異操作的某一基因座上的原有基因值為 0，則變異操作將其變?yōu)?1；反之，若原有基因值為 1，則變異操作將其變?yōu)?0 。 基本位變異算子的執(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é)束 計算個體適應(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ù)、可微等條件的約束，適用范圍很廣。 二、遺傳算法原理 遺傳算法的數(shù)學(xué)基礎(chǔ) 遺傳算法的收斂性分析 遺傳算法的改進(jìn) 遺傳算法的數(shù)學(xué)基礎(chǔ) （ 1）模式定理 （ 2）積木塊假設(shè) 模式 模式是指種群個體基因串中的相似樣板，它用來描述基因串中某些特征位相同的結(jié)構(gòu)。在二進(jìn)制編碼中，模式是基于三個字符集 (0,1,*)的字符串，符號 *代表任意字符，即 0 或者 1。 模式示例： 10**1 兩個定義 定義 1：模式 H 中確定位置的個數(shù)稱為模式 H 的階，記作 O(H)。例如 O(10**1)=3 。 定義 2：模式 H 中第一個確定位置和最后一個確定位置之間的距離稱為模式 H 的定義距，記作 δ(H)。例如 δ(10**1)=4 。 模式的階和定義距的含義 模式階用來反映不同模式間確定性的差異，模式階數(shù)越高，模式的確定性就越高，所匹配的樣本數(shù)就越少。在遺傳操作中，即使階數(shù)相同的模式，也會有不同的性質(zhì)，而模式的定義距就反映了這種性質(zhì)的差異。 模式定理 模式定理：具有低階、短定義距以及平均適應(yīng)度高于種群平均適應(yīng)度的模式在子代中呈指數(shù)增長。 模式定理保證了較優(yōu)的模式（遺傳算法的較優(yōu)解）的數(shù)目呈指數(shù)增長，為解釋遺傳算法機(jī)理提供了數(shù)學(xué)基礎(chǔ)。 模式定理 從模式定理可看出，有高平均適應(yīng)度、短定義距、低階的模式，在連續(xù)的后代里獲得至少以指數(shù)增長的串?dāng)?shù)目，這主要是因?yàn)檫x擇使最好的模式有更多的復(fù)制，交叉算子不容易破壞高頻率出現(xiàn)的、短定義長的模式，而一般突變概率又相當(dāng)小，因而它對這些重要的模式幾乎沒有影響。 積木塊假設(shè) 積木塊假設(shè)：遺傳算法通過短定義距、低階以及高平均適應(yīng)度的模式（積木塊），在遺傳操作下相互結(jié)合，最終接近全局最優(yōu)解。 模式定理保證了較優(yōu)模式的樣本數(shù)呈指數(shù)增長，從而使遺傳算法找到全局最優(yōu)解的可能性存在；而積木塊假設(shè)則指出了在遺傳算子的作用下，能生成全局最優(yōu)解。 遺傳算法的收斂性分析 遺傳算法要實(shí)現(xiàn)全局收斂，首先要求任意初始種群經(jīng)有限步都能到達(dá)全局最優(yōu)解，其次算法必須由保優(yōu)操作來防止最優(yōu)解的遺失。與算法收斂性有關(guān)的因素主要包括種群規(guī)模、選擇操作、交叉概率和變異概率。 種群規(guī)模對 收斂性的影響 通常，種群太小則不能提供足夠的采樣點(diǎn)，以致算法性能很差；種群太大，盡管可以增加優(yōu)化信息，阻止早熟收斂的發(fā)生，但無疑會增加計算量，造成收斂時間太長，表現(xiàn)為收斂速度緩慢。 選擇操作對 收斂性的影響 選擇操作使高適應(yīng)度個體能夠以更大的概率生存，從而提高了遺傳算法的全局收斂性。如果在算法中采用最優(yōu)保存策略，即將父代群體中最佳個體保留下來，不參加交叉和變異操作，使之直接進(jìn)入下一代，最終可使遺傳算法以概率 1收斂于全局最優(yōu)解。 交叉概率對 收斂性的影響 交叉操作用于個體對，產(chǎn)生新的個體，實(shí)質(zhì)上是在解空間中進(jìn)行有效搜索。交叉概率太大時，種群中個體更新很快，會造成高適應(yīng)度值的個體很快被破壞掉；概率太小時，交叉操作很少進(jìn)行，從而會使搜索停滯不前，造成算法的不收斂。 變異概率對 收斂性的影響 變異操作是對種群模式的擾動，有利于增加種群的多樣性 。但是，變異概率太小則很難產(chǎn)生新模式，變異概率太大則會使遺傳算法成為隨機(jī)搜索算法。 遺傳算法的本質(zhì) 遺傳算法本質(zhì)上是對染色體模式所進(jìn)行的一系列運(yùn)算，即通過選擇算子將當(dāng)前種群中的優(yōu)良模式遺傳到下一代種群中，利用交叉算子進(jìn)行模式重組，利用變異算子進(jìn)行模式突變。通過這些遺傳操作，模式逐步向較好的方向進(jìn)化，最終得到問題的最優(yōu)解。 遺傳算法的改進(jìn) 遺傳欺騙問題：在遺傳算法進(jìn)化
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1