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