遺傳演算法組合優化

① 遺傳演算法怎麼回事

遺傳演算法（Genetic Algorithm）是一類借鑒生物界的進化規律（適者生存，優勝劣汰遺傳機制）演化而來的隨機化搜索方法。它是由美國的J.Holland教授1975年首先提出，其主要特點是直接對結構對象進行操作，不存在求導和函數連續性的限定；具有內在的隱並行性和更好的全局尋優能力；採用概率化的尋優方法，能自動獲取和指導優化的搜索空間，自適應地調整搜索方向，不需要確定的規則。遺傳演算法的這些性質，已被人們廣泛地應用於組合優化、機器學習、信號處理、自適應控制和人工生命等領域。它是現代有關智能計算中的關鍵技術。對於一個求函數最大值的優化問題(求函數最小值也類同)，一般可以描述為下列數學規劃模型: 遺傳演算法式中為決策變數，為目標函數式，式2-2、2-3為約束條件，U是基本空間，R是U的子集。滿足約束條件的解X稱為可行解，集合R表示所有滿足約束條件的解所組成的集合，稱為可行解集合。遺傳演算法的基本運算過程如下:a)初始化:設置進化代數計數器t=0，設置最大進化代數T，隨機生成M個個體作為初始群體P(0)。b)個體評價:計算群體P(t)中各個個體的適應度。c)選擇運算:將選擇運算元作用於群體。選擇的目的是把優化的個體直接遺傳到下一代或通過配對交叉產生新的個體再遺傳到下一代。選擇操作是建立在群體中個體的適應度評估基礎上的。d)交叉運算；將交叉運算元作用於群體。所謂交叉是指把兩個父代個體的部分結構加以替換重組而生成新個體的操作。遺傳演算法中起核心作用的就是交叉運算元。e)變異運算:將變異運算元作用於群體。即是對群體中的個體串的某些基因座上的基因值作變動。群體P(t)經過選擇、交叉、變異運算之後得到下一代群體P(t 1)。f)終止條件判斷:若tT,則以進化過程中所得到的具有最大適應度個體作為最優解輸出，終止計算

② 什麼是遺傳演算法

遺傳演算法是模擬自然界中按「優勝劣汰」法則進行進化過程而設計的演算法。Bagley和Rosengerg於1967年在他們的博士論文中首先提出了遺傳演算法的概念。1975年Holland出版的專著奠定了遺傳演算法的理論基礎。如今遺傳演算法不但給出了清晰的演算法描述，而且也建立了一些定量分析的結果，在眾多領域得到了廣泛的應用，如用於控制(煤氣管道的控制)、規劃(生產任務規劃)、設計(通信網路設計)、組合優化(TSP問題、背包問題)以及圖像處理和信號處理等。

③ 為什麼遺傳演算法能被廣泛的應用到各個領域

遺傳演算法在很多領域都得到應用；從神經網路研究的角度上考慮，最關心的是遺傳演算法在神經網路的應用。在遺傳演算法應用中，應先明確其特點和關鍵問題，才能對這種演算法深入了解，靈活應用，以及進一步研究開發。一、遺傳演算法的特點 1．遺傳演算法從問題解的中集開始嫂索，而不是從單個解開始。這是遺傳演算法與傳統優化演算法的極大區別。傳統優化演算法是從單個初始值迭代求最優解的；容易誤入局部最優解。遺傳演算法從串集開始搜索，復蓋面大，利於全局擇優。 2．遺傳演算法求解時使用特定問題的信息極少，容易形成通用演算法程序。由於遺傳演算法使用適應值這一信息進行搜索，並不需要問題導數等與問題直接相關的信息。遺傳演算法只需適應值和串編碼等通用信息，故幾乎可處理任何問題。 3．遺傳演算法有極強的容錯能力遺傳演算法的初始串集本身就帶有大量與最優解甚遠的信息；通過選擇、交叉、變異操作能迅速排除與最優解相差極大的串；這是一個強烈的濾波過程；並且是一個並行濾波機制。故而，遺傳演算法有很高的容錯能力。 4．遺傳演算法中的選擇、交叉和變異都是隨機操作，而不是確定的精確規則。這說明遺傳演算法是採用隨機方法進行最優解搜索，選擇體現了向最優解迫近，交叉體現了最優解的產生，變異體現了全局最優解的復蓋。 5．遺傳演算法具有隱含的並行性

④ 什麼是遺傳演算法如何利用它進行結構優化，請形象的加以闡述。

如果要培養優良品種，我們就要先培育第一代，然後看他們的生長發育有什麼不同，然後呢，把好的個體雜交，壞的個體舍棄不要，好的個體再經過培育再次舍棄壞的合體，這樣依次類推經過很多代肯定可以搜索到新品種的。遺傳演算法在尋找最優解時候也是這個道理，先隨即生成一些數，這裡面有的接近最優值，有的不是的，這時候就計算他們各自的函數值，比較好的保留差的舍棄，好解再進行交叉變異等操作差生下一代，再次進行類操作，如此循環總可以找到最優的解。自己的話比較朴實，需要在理解要泡論壇了！

⑤ 因為對遺傳演算法不太了解，想請教一下建立物理環境優化組合模型可以採用遺傳演算法嗎

只要你能把你優化對象的數學模型找出來，就能夠用遺傳演算法，遺傳演算法應用還是很廣泛的。需要優化對象的數學模型及其影響模型的參數，只要這兩點你找出來了就可以用遺傳演算法了。。。不知道對你說的有沒有幫助

⑥ 遺傳演算法有哪些應用

遺傳演算法的搜索策略和優化搜索方法是不依附於梯度信息及其它的輔助知識，而只需要影響搜索方向的目標函數和相應的適應度函數，所以遺傳演算法提供了一種求解復雜系統問題的通用框架，它不依賴於問題的具體領域，對問題的種類有很強的魯棒性，所以廣泛應用於許多科學。遺傳演算法的應用領域有很多，下面針對一些主要的應用領域做簡單的介紹。

1．函數優化：該領域是遺傳演算法得以應用的經典領域，同時它也是遺傳演算法進行性能評價的常用算例，許多人構造出了各種各樣復雜形式的測試函數：連續函數和離散函數、凸函數和凹函數、低維函數和高維函數、單峰函數和多峰函數等。對於函數優化問題，如一些非線性、多模型、多目標等函數問題用遺傳演算法很容易得到較好的結果，而用其他演算法則較難。

2．組合優化：由於組合優化問題的搜索空間在不斷地增大，有時用枚舉法很難得到最優解。對這類復雜的問題，人們已經意識到應把主要精力放在尋求滿意解上，而遺傳演算法是尋求這種滿意解的最佳工具之一。實踐證明，遺傳演算法對於組合優化中的NP問題非常有效。比如，在旅行商問題、裝箱問題及圖形劃分等問題上，已經成功得以應用了遺傳演算法。

⑦ 什麼是遺傳演算法

遺傳演算法（Genetic Algorithm）是一類借鑒生物界的進化規律（適者生存，優勝劣汰遺傳機制）演化而來的隨機化搜索方法。它是由美國的J.Holland教授1975年首先提出，其主要特點是直接對結構對象進行操作，不存在求導和函數連續性的限定；具有內在的隱並行性和更好的全局尋優能力；採用概率化的尋優方法，能自動獲取和指導優化的搜索空間，自適應地調整搜索方向，不需要確定的規則。遺傳演算法的這些性質，已被人們廣泛地應用於組合優化、機器學習、信號處理、自適應控制和人工生命等領域。它是現代有關智能計算中的關鍵技術。
對於一個求函數最大值的優化問題(求函數最小值也類同)，一般可以描述為下列數學規劃模型：
遺傳演算法式中x為決策
變數，式2-1為目標函數式，式2-2、2-3為約束條件，U是基本空間，R是U的子集。滿足約束條件的解X稱為可行解，集合R表示所有滿足約束條件的解所組成的集合，稱為可行解集合。
遺傳演算法的基本運算過程如下：
a)初始化：設置進化代數計數器t=0，設置最大進化代數T，隨機生成M個個體作為初始群體P(0)。
b)個體評價：計算群體P(t)中各個個體的適應度。
c)選擇運算:將選擇運算元作用於群體。選擇的目的是把優化的個體直接遺傳到下一代或通過配對交叉產生新的個體再遺傳到下一代。選擇操作是建立在群體中個體的適應度評估基礎上的。
d)交叉運算：將交叉運算元作用於群體。所謂交叉是指把兩個父代個體的部分結構加以替換重組而生成新個體的操作。遺傳演算法中起核心作用的就是交叉運算元。
e)變異運算：將變異運算元作用於群體。即是對群體中的個體串的某些基因座上的基因值作變動。
群體P(t)經過選擇、交叉、變異運算之後得到下一代群體P(t 1)。
f)終止條件判斷:若t=T,則以進化過程中所得到的具有最大適應度個體作為最優解輸出，終止計算。
遺傳演算法是從代表問題可能潛在的解集的一個種群（population）開始的，而一個種群則由經過基因（gene）編碼的一定數目的個體(indivial)組成。每個個體實際上是染色體(chromosome)帶有特徵的實體。染色體作為遺傳物質的主要載體，即多個基因的集合，其內部表現（即基因型）是某種基因組合，它決定了個體的形狀的外部表現，如黑頭發的特徵是由染色體中控制這一特徵的某種基因組合決定的。因此，在一開始需要實現從表現型到基因型的映射即編碼工作。由於仿照基因編碼的工作很復雜，我們往往進行簡化，如二進制編碼，初代種群產生之後，按照適者生存和優勝劣汰的原理，逐代（generation）演化產生出越來越好的近似解，在每一代，根據問題域中個體的適應度（fitness）大小選擇（selection）個體，並藉助於自然遺傳學的遺傳運算元（genetic operators）進行組合交叉（crossover）和變異（mutation），產生出代表新的解集的種群。這個過程將導致種群像自然進化一樣的後生代種群比前代更加適應於環境，末代種群中的最優個體經過解碼（decoding），可以作為問題近似最優解。

⑧ 使用matlab遺傳演算法工具箱能不能解決組合優化問題還有使用工具箱方便還是自己編程方便呢

1、要看你組合優化是屬於哪種問題，一般的組合優化都是混合整數線性或非線性的，那麼就不行了，因此要對遺傳演算法改進才能計算。
2、如果有現成的工具箱求解你的組合優化問題肯定要方便些，但碰到具體問題，可能要對參數進行一些設置更改，所以最好能有編程基礎，那樣就可以自己修改工具箱裡面的參數或策略了

對你的補充問題，組合優化問題一般都是用matlab 和 lingo實現吧。建議買一本數學建模的書看一看，都涉及到組合優化問題，也可以下載論文看看。lingo對編程要簡單些，主要是求混合規劃，缺點是似乎還不能用上多目標問題，一般的組合優化都屬於多目標問題。但是matlab功能強大的多。

⑨ 遺傳演算法屬於數學優化理論嗎

算的
遺傳演算法是一種利用自然遺傳規律來搜索最優解的數學優化工具。其基本過程及原理簡單概括如下：

遺傳演算法是具有「生成＋檢測」迭代過程的搜索演算法，是一種群體型操作。操作以群體中的所有個體為對象。它有三個基本操作運算元：選擇、變異和交叉。遺傳演算法中包含五個基本要素：參數編碼；初始群體設定；適應度函數設計；遺傳操作設計；控制參數設定（主要指群體大小和使用遺傳操作的概率等）。這五個要素構成了遺傳演算法的核心內容。參數編碼就是將優化問題變數通過一定的變換映射到染色體基因上面。初始群體設定應使其具有足夠的規模和隨機性。遺傳演算法根據染色體基因值來計算染色體適應度，並根據適應度值決定染色體的交配概率，適應度大的染色體交配概率大。染色體交配之後應對染色體進行變異，這樣可以避免演算法過早收斂。變異之後的群體就是子代，它將作為下一代群體的父代，進行同樣的遺傳操作，如此循環。在演算法執行過程中，控制參數的設定直接影響演算法的精度和效率，因此選定合適的控制參數是提高演算法效率的關鍵之一。一般採用觀察法來選定合適的控制參數

⑩ 遺傳演算法具體應用

1、函數優化

函數優化是遺傳演算法的經典應用領域，也是遺傳演算法進行性能評價的常用算例，許多人構造出了各種各樣復雜形式的測試函數：連續函數和離散函數、凸函數和凹函數、低維函數和高維函數、單峰函數和多峰函數等。

2、組合優化

隨著問題規模的增大，組合優化問題的搜索空間也急劇增大，有時在目前的計算上用枚舉法很難求出最優解。對這類復雜的問題，人們已經意識到應把主要精力放在尋求滿意解上，而遺傳演算法是尋求這種滿意解的最佳工具之一。

此外，GA也在生產調度問題、自動控制、機器人學、圖象處理、人工生命、遺傳編碼和機器學習等方面獲得了廣泛的運用。

3、車間調度

車間調度問題是一個典型的NP-Hard問題，遺傳演算法作為一種經典的智能演算法廣泛用於車間調度中，很多學者都致力於用遺傳演算法解決車間調度問題，現今也取得了十分豐碩的成果。

從最初的傳統車間調度（JSP）問題到柔性作業車間調度問題（FJSP），遺傳演算法都有優異的表現，在很多算例中都得到了最優或近優解。

(10)遺傳演算法組合優化擴展閱讀：

遺傳演算法的缺點

1、編碼不規范及編碼存在表示的不準確性。

2、單一的遺傳演算法編碼不能全面地將優化問題的約束表示出來。考慮約束的一個方法就是對不可行解採用閾值，這樣，計算的時間必然增加。

3、遺傳演算法通常的效率比其他傳統的優化方法低。

4、遺傳演算法容易過早收斂。

5、遺傳演算法對演算法的精度、可行度、計算復雜性等方面，還沒有有效的定量分析方法。