如果不知道遺傳算法的，后續會出一個，這里先不講了。

1.非支配遺傳算法簡介

非支配遺傳算法，從名字上就可以看出，是在遺傳算法概念上引申改進而來的。其在傳統的GA概念上引入了帕累托最優概念和小生境技術，使得產生的子代不僅具有較好的適應度值，而且保證了種群的多樣性。

非支配遺傳算法，非常適用于具有多個非線性的目標函數工程問題求解。因為簡單的多目標的工程問題也可以采用多個目標歸一化為單目標的問題。比如班主任要選出班上德智體美勞的優秀學生，可以將德智體美勞簡化為不同科目的成績，只需要選出所有科目成績總和最高的即可。這就是多目標歸一化為最大化單目標、或者最小化單目標。再比如我們去買水果，想要買又大又甜還便宜的水果，對于這個三目標的問題，大小越大、甜度越大、價格越低越讓我們滿意，所以可以簡單的將其歸一化，，其中f為最終目標函數，f(x)代表大小，f(y)代表甜度值，f(z)代表價格函數，這樣最終目標函數越大我們越滿意，或者也可以歸一化為最小化單目標問題。

當然歸一化也是有前提的，歸一化后的目標需要量綱相同、取值范圍相似，或者需要有一些系數（也叫權重）上的關系，但在實際工程中，我們要求解的問題大都涉及兩個及以上的目標優化，其量綱大都不同，甚至無法進行比較，顯然這種情況下，我們無法再使用歸一化進行簡單的求解。而非支配遺傳算法一般適應于該種情形，即多個目標相互制約、相互影響、相互矛盾的問題求解。

1.1多目標與帕累托最優概念

1. 多目標：一般問題的求解需要使用多個目標來衡量。不同于單目標，一般不存在一個絕對意義上的最優解，而是一個最優解集合，集合中的每一個最優解的特點是，至少存在一個目標優于其他所有的解，且其他的目標不劣于其他所有解。

2.帕累托最優：由意大利的一個著名的經濟學家Pareto提出的（這里直接引用百度百科的解釋），指的是社會中資源分配的一種理想狀態，即假定固有的一群人和可分配的資源，從一種分配狀態到另一種狀態的變化中，在沒有使任何人境況變壞的前提下，使得至少一個人變得更好，這就是帕累托改進或帕累托最優化。

簡單來說，比如我們在實際買衣服過程中，無法真的找到一個無論哪方面都令自己滿意的衣服，在最后選擇的時候總會陷入一個很糾結的過程，這個裙子很顯瘦，但是不僅不那么顯白而且價格超過了自己的預算，那個裙子穿上很溫柔很可人，但是沒有上一個顯瘦，自己更喜歡上一個風格，朋友的說法不一，這讓你很糾結。但是你的預算只能買一件，所以這時候，你可能會通過不同的選擇角度評價兩個裙子，1.顯瘦方面，2.價格方面，3.風格方面...。哦，當然還有來自朋友們的投票，從中選擇一個較好的裙子。這個過程其實就是體現了帕累托最優的思想。因為兩個裙子，各有各的優勢，在一個方面勝于對方，就會在另一個方面敗給對方，無法簡單的評價哪個裙子更好，但是這兩條裙子卻在眾多的裙子里勝出，讓你糾結，就是因為他們兩個在各方面勝于其他的裙子，但是無法單方面他們兩個中的勝者。這兩個裙子組成了所有裙子集合中的帕累托最優解集。

3.帕累托支配：概念這里不再解釋，簡單來說，即如果一個解A在全部目標函數中均優于另一個解B，就說解A支配解B。

若解A在某些方面優于解B，但是在其他方面劣于解B，無法衡量誰好誰差，我們就說解A和解B不存在支配關系，即解A和解B之間無差別。

4.帕累托最優解和帕累托最優解集：帕累托最優解是某一個非支配解。而所有帕累托最優解組成的集合叫帕累托最優解集，也就是所有和其他的解有非支配關系，但是他們之間不存在非支配關系的解的集合稱為帕累托最優解集。

簡單來說，上面的例子中的兩個裙子，每一個都是帕累托最優解，因為他們比其他的裙子更讓你喜歡，而這兩個之間不存在支配關系，因為你在她們之間的選擇中糾結了。這兩個裙子組成的集合就是帕累托最優集合。

5.快速非支配排序：就是在種群中，先通過比較將不同的個體就其支配關系進行分配等級，這里定義為是等級越低越好，也就是等級低的支配等級高的個體。

具體的步驟是，

step1：通過排序比較思想，找到所有種群中的非支配個體，把他們的等級定義為1(第一等級)；

step2：將他們從種群中去除，在剩余的個體中，再通過排序比較的思想，找到這時的非支配個體，把他們的等級定義為2(第二等級)；

step3：將第二等級的個體從種群中去除，再通過比較排序.....直到種群中沒有個體為止；

這就是非支配排序過程與思想。

1.2精英保留策略和小生境技術概念

1. 精英保留策略：將父代中優秀的個體保留到子代中。這樣能夠加快算法的收斂速度，保留了較好的基因。

其實可以結合輪盤賭的思想或者其他的思想，這里只說一個較為簡單的方法：（假設種群規模為N）將父代的個體和通過交叉變異操作得到的子代個體合并為一個新的子代，此時種群規模為2N，通過快速非支配排序，從低等級到高等級的解集中依次選擇N個個體進入子代，這樣就形成了一個種群規模為N的子代，其中可能將父代中較優的個體基因全部保留了下來，也可能沒有保留。若存在新的子代中沒有父代的個體，就說明，通過交叉和變異產生的子代個體全部優于父代，所以父代中的個體不算“精英”，不會被保留。

2.小生境技術：將每一次迭代的種群個體，劃分為多類，在每一個類中選擇若干個適應度值大（非支配）的個體，他們每個個體都作為所屬類的優秀代表，將他們組成一個集合作為一個子代種群，繼續交叉變異等操作。如此這般，便可以保持種群的多樣性，同時使得算法具有更好地全局尋優能力和較高的收斂速度。（其他更專業的概念可以自行去了解，這里不做過多的闡述）

其中，通過非支配排序，并結合精英選擇策略的遺傳算法，就是小生境技術的一種實現。

1.3非支配遺傳算法流程

1.4 非支配遺傳算法優點

1. 可以很好地解決復雜的多目標、多峰值的NP-Hard問題。多適用在調度等工程問題的求解上。

2. 可以嵌套其他的算法，具有很好的兼容性。

1.5?非支配遺傳算法改進技術點

1.選擇算子的改進：可以使用博弈論、輪盤賭等；

2.交叉算子的改進：采用自適應交叉算子、針對不同問題不同編碼方式對交叉算子的改進；

3.變異算子的改進：采用自適應變異算子、針對不同的問題不同編碼方式對變異算子的改進；

4.與其他的啟發式規則、算法進行結合；

2.柔性作業車間調度

柔性作業車間調度問題（FJSP）是經典的作業車間調度問題，其相對作業車間調度問題更接近企業實際，更受廣大學者的關注與研究。對比傳統的作業車間調度問題，其更具有柔性，具體體現在：不同工件的工藝路線不同，工件的每一道工序可以在多臺可選的加工能力互不相同的設備上加工。

顯然，柔性作業調度問題，可以分為兩個子問題，（1）設備的分配問題：給每一道工序分配一臺加工設備；（2）工序排序問題：不同設備所分配的工序間的加工順序問題。

柔性作業車間調度問題的描述為：

傳統柔性作業車間調度問題（FJSP）涉及n種工件(i=1,2..n)和m臺設備?(h=1,2..m)。每一種工件的加工都需要經過一系列具有嚴格順序的工序，表示工件的第j道工序。每一道工序都可由一臺或多臺設備進行加工。 因此，傳統FJSP涉及兩個子問題：分配和排序，即為每一道工序分配一臺加工設備以及對每一臺設備上的加工工序進行排序，從而達到工件最大完工時間（）的最小化。此處最小化目標的內涵與最大化設備等資源利用率一致?

2.1作業車間調度分類

1.作業車間根據工件的周轉模式的不同，可以分為如下幾類：

（1）流水作業車間調度問題：作業間、作業的工序間均呈流水式生產，同一批工件的可選設備在物理上呈連續、直線型/U型等布局，當一個工件的上一道工序加工完，該工序的設備馬上被同一批的下一個工件占用，該工件馬上流入下一個設備上進行生產，形成了一個加工流，像流水一般，所以叫做流水作業。（可以百度或者去b站搜一下，流水線生產的視頻）

（2）離散式柔性作業車間調度問題：作業間、作業的工序間均為離散式生產，工件所需要的設備在物理布局上并不是連續分布的，而是離散擺放的。比如，工件的某一道工序加工完，并不會立馬轉入下一個設備上加工，極大可能是等一批或部分加工完，才一起周轉到下一個設備旁邊，而下一個設備可能在車間的距離該道工序選擇的加工設備較遠的位置。

2.作業車間調度問題可以根據作業類型不同，分為以下幾類：

（1）機加工車間調度（也就是常說的作業車間調度問題）：主要是對工件進行機加工類的，所用到的資源是多維的，比如加工設備、操作工人、夾具、工裝等；

（2）兩階段作業車間調度（既包含機加工，也包括裝配任務）：這里的裝配作業，通常是作為工件的最后一個工序出現的。當然，大部分的產品，最后都要經過裝配，但是這里的兩階段，通常指的是較為簡單的裝配任務；

（3）裝配車間調度（主要指的是總裝車間調度）：主要指的是具有復雜的裝配作業任務的調度，比如汽車、飛機等產品的裝配，極為復雜。

3.裝配車間調度和柔性作業車間調度的區別：

序號	裝配車間調度	柔性作業車間調度
工藝流程	1.多涉及并行關系的工序； 2.工序順序方面具有裝配約束關系；	多具有先后加工順序約束；
主要涉及資源	主要涉及操作工人	主要涉及機加設備、操作人員
主要生產模式	多以流水生產、脈動生產模式為主	主要以離散、虛擬制造單元等為主

2.2柔性作業車間調度一般目標函數

1.最小化最大完工時間；

2.最大化資源利用率：其概念與第一個目標有異曲同工之處；

3.最小化工件拖期懲罰；

4.最小化工件等待時間；

等等，根據實際需求來進行定義。

2.3甘特圖

一般作業車間調度的結果使用資源甘特圖、訂單甘特圖等進行表示。

2.4非支配遺傳算法與柔性作業車間調度的結合

簡答來說，算法流程不變，主要是編碼、解碼的定義。

一般采用基于工序的編碼方式。

解碼：可以采用，一些規則來進行解碼。

（1）最小開工時間設備優先：優先選擇使得工序最早加工的設備；

（2）非瓶頸設備優先：優先選擇非瓶頸設備；

（3）最小加工時間設備優先：優先選擇使得工序加工時間最小的設備；

.....等等

總結

以上是生活随笔為你收集整理的大白话讲调度：非支配遗传算法与柔性作业车间调度的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。