遺傳演算法求解jsp問題

『壹』 遺傳演算法具體應用

1、函數優化

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

2、組合優化

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

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

3、車間調度

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

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

(1)遺傳演算法求解jsp問題擴展閱讀：

遺傳演算法的缺點

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

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

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

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

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

『貳』 遺傳演算法為什麼能求解npc問題，關鍵點在哪裡

遺傳演算法在很多領域都得到應用；從神經網路研究的角度上考慮，最關心的是遺傳演算法在神經網路的應用。在遺傳演算法應用中，應先明確其特點和關鍵問題，才能對這種演算法深入了解，靈活應用，以及進一步研究開發。

一、遺傳演算法的特點

1．遺傳演算法從問題解的中集開始嫂索，而不是從單個解開始。

這是遺傳演算法與傳統優化演算法的極大區別。傳統優化演算法是從單個初始值迭代求最優解的；容易誤入局部最優解。遺傳演算法從串集開始搜索，復蓋面大，利於全局擇優。

2．遺傳演算法求解時使用特定問題的信息極少，容易形成通用演算法程序。

由於遺傳演算法使用適應值這一信息進行搜索，並不需要問題導數等與問題直接相關的信息。遺傳演算法只需適應值和串編碼等通用信息，故幾乎可處理任何問題。

3．遺傳演算法有極強的容錯能力

遺傳演算法的初始串集本身就帶有大量與最優解甚遠的信息；通過選擇、交叉、變異操作能迅速排除與最優解相差極大的串；這是一個強烈的濾波過程；並且是一個並行濾波機制。故而，遺傳演算法有很高的容錯能力。

4．遺傳演算法中的選擇、交叉和變異都是隨機操作，而不是確定的精確規則。

這說明遺傳演算法是採用隨機方法進行最優解搜索，選擇體現了向最優解迫近，交叉體現了最優解的產生，變異體現了全局最優解的復蓋。

5．遺傳演算法具有隱含的並行性

『叄』 怎麼在基於JSP的網站中用到數據挖掘演算法呢

數據挖掘的核心是為數據建立模型的過程。所有的數據挖掘產品都有這個建模過程，不同的是它們構造模型的方式互不相同。進行數據挖掘時可採用許多不同的演算法。決策樹是一種經常要用到的技術，可以用於分析數據，同樣也可以用來作預測。常用的演算法有CHAID、CART、ID3和C4.5。決策樹方法很直觀，這是它的最大優點，缺點是隨著數據復雜性的提高，分支數增多，管理起來很困難。ANGOSS公司的KnowedgeSEEKER產品採用了混合演算法的決策樹。神經網路近來越來越受到人們的關注，因為它為解決大復雜度問題提供了一種相對來說比較有效的簡單方法。神經網路常用於兩類問題：分類和回歸。它的最大優點是它能精確地對復雜問題進行預測。神經網路的缺點是網路模型是個黑盒子，預測值難於理解；神經網路有過擬合的現象。IBM、SAS、SPSS、HNC、ANGOSS等公司是這個產品的供應者。遺傳演算法是一種基於進化過程的組合優化方法。它的基本思想是隨著時間的更替，只有最適合的物種才得以進化。遺傳演算法能夠解決其它技術難以解決的問題，然而，它也是一種最難於理解和最開放的方法。遺傳演算法通常與神經網路結合使用。採用上述技術的某些專門的分析工具已經發展了大約十年的歷史，不過這些工具所面對的數據量通常較小。而現在這些技術已經被直接集成到許多大型的工業標準的數據倉庫和聯機分析系統中去了。

『肆』 遺傳演算法可以解決哪些問題

遺傳演算法主要是用來求解最優化問題的。
一般來講可以求解函數的最大、最小值問題，還可以結合其它一些方法解決（非）線性回歸、分類問題等等。

但遺傳演算法有兩個缺點，一是時間長，二是初值的選擇會影響收斂的效果。

它的本質，實際上還是隨機搜索演算法，還是屬於所謂的蒙特卡羅式的方法。

『伍』 如何用遺傳演算法實現多變數的最優化問題

將多個變數的數值編碼編排進去，進行組合，只需要增長基因個體的長度，但是要明確每個變數具體的位置，然後讓每個變數轉化成二進制的等長編碼，組合在一起，就可以來運算了。

『陸』 遺傳演算法的主要步驟

為了使用遺傳演算法來解決優化問題，准備工作分為以下四步^{［56，57，61］}。

7.4.1 確定問題的潛在解的遺傳表示方案

在基本的遺傳演算法中，表示方案是把問題的搜索空間中每個可能的點表示為確定長度的特徵串（通常是二進制串）。表示方案的確定需要選擇串長l和字母表規模k。在染色體串和問題的搜索空間中的點之間選擇映射有時容易實現，有時又非常困難。選擇一個便於遺傳演算法求解問題的表示方案經常需要對問題有深入的了解。

7.4.2 確定適應值的度量

適應值度量為群體中每個可能的確定長度的特徵串指定一個適應值，它經常是問題本身所具有的。適應值度量必須有能力計算搜索空間中每個確定長度的特徵串的適應值。

7.4.3 確定控制該演算法的參數和變數

控制遺傳演算法的主要參數有群體規模Pop-Size、演算法執行的最大代數N-Gen、交叉概率P_c、變異概率P_m和選擇策略R等參數。

（1）群體規模Pop-Size。群體規模影響到遺傳演算法的最終性能和效率。當規模太小時，由於群體對大部分超平面只給出了不充分的樣本量，所以得到的結果一般不佳。大的群體更有希望包含出自大量超平面的代表，從而可以阻止過早收斂到局部最優解；然而群體越大，每一代需要的計算量也就越多，這有可能導致一個無法接受的慢收斂率。

（2）交叉率P_c。交叉率控制交叉運算元應用的頻率，在每代新的群體中，有P_c·Pop-Size個串實行交叉。交叉率越高，群體中串的更新就越快。如果交叉率過高，相對選擇能夠產生的改進而言，高性能的串被破壞得更快。如果交叉率過低，搜索會由於太小的探查率而可能停滯不前。

（3）變異率P_m。變異是增加群體多樣性的搜索運算元，每次選擇之後，新的群體中的每個串的每一位以相等的變異率進行隨機改變。對於M進制串，就是相應的位從1變為0或0變為1。從而每代大約發生P_m·Pop-Size·L次變異，其中L為串長。一個低水平的變異率足以防止整個群體中任一給定位保持永遠收斂到單一的值。高水平的變異率產生的實質是隨機搜索。

比起選擇和交叉，變異在遺傳演算法中是次要的，它在恢復群體中失去的多樣性方面具有潛在的作用。例如，在遺傳演算法執行的開始階段，串中一個特定位上的值1可能與好的性能緊密聯系，也就是說從搜索空間中某些初始隨機點開始，在那個位上的值1可能一致地產生適應性度量好的值。因為越好的適應值與串中那個位上的值1相聯系，復製作用就越會使群體的遺傳多樣性損失。當達到一定程度時，值0會從整個群體中的那個位上消失，然而全局最優解可能在串中那個位上是0。一旦搜索范圍縮小到實際包含全局最優解的那部分搜索空間，在那個位上的值0就可能正好是達到全局最優解所需的。這僅僅是一種說明搜索空間是非線性的方式，這種情形不是假定的，因為實際上所有我們感興趣的問題都是非線性的。變異作用提供了一個恢復遺傳多樣性的損失的方法。

（4）選擇策略R。有兩種選擇策略。一是利用純選擇，即當前群體中每個點復制的次數比與點的性能值成比例。二是利用最優選擇，即首先執行純選擇，且具有最好性能的點總是保留到下一代。在缺少最優選擇的情況下，由於采樣誤差、交叉和變異，最好性能的點可能會丟失。

通過指定各個參數Pop-Size、P_c、P_m和R的值，可以表示一個特定的遺傳演算法。

7.4.4 確定指定結果的方法和停止運行的准則

當遺傳的代數達到最大允許代數時，就可以停止演算法的執行，並指定執行中得到的最好結果作為演算法的結果。

基本的遺傳演算法

1）隨機產生一個由固定長度字元串組成的初始群體。

2）對於字元串群體，迭代地執行下述步驟，直到選擇標准被滿足為止。

①計算群體中的每個個體字元串的適應值；

②實施下列三種操作（至少前兩種）來產生新的群體，操作對象的選取基於與適應度成比例的概率。

選擇：把現有的個體串按適應值復制到新的群體中。

交叉：通過遺傳重組隨機選擇兩個現有的子串進行遺傳重組，產生兩個新的串。

變異：將現有串中某一位的字元隨機變異產生一個新串。

3）把在後代中出現的最好適應值的個體串指定為遺傳演算法運行的結果。這一結果可以是問題的解（或近似解）。

基本的遺傳演算法流程圖如圖7-1所示。