【正文】 算法。SPEAⅡ是對SPEA的改進。SPEA算法首先初始化一個父種群和一個外部種群，外部種群初始為空集，然后循環(huán)執(zhí)行如下操作：復制所有無支配個體到外部種群中，同時舍棄所有被支配個體。外部解集默認有大小，當所有無支配個體超出了這個大小，則采用某種方法舍棄多于個體，必須要保證這個外部種群的無支配特性，接著采用強度值的概念對父種群和外部種群進行適值分配，使用二元錦標賽法對父種群和外部種群中的個體進行選擇、交叉、變異操作，來產(chǎn)生下一代種群作為父種群，返回第一步重復操作。SPEA算法雖然有一定的優(yōu)化性能，但是也存在不足：外部種群的中只包含一個個體時，SPEA算法就會退化；SPEA在考慮密度信息時，只考慮外部種群，而沒考慮父種群信息，導致搜索過程無用功太大；SPEA算法無法有效的保留邊緣解。 SPEAⅡ?qū)PEA算法進行了有效的改進：考慮每一個個體的支配性和被支配性；改進密度估計算法，是種群的搜索過程更加優(yōu)化；采用新的外部解集修正法，避免邊緣解的流失。通過改進，使得算法的參數(shù)設(shè)置更少，收斂速度更快速，搜優(yōu)能力也更強，保持更好的種群多樣性。（5）非支配排序算法Ⅱ非支配排序算法（Nondominated Sorting Genetic Algorithm NSGAⅡ）是對NSGA算法的改進：NSGAⅡ的算法復雜度由原來的降低到了，采用了一種更加合理的快速非劣前沿分級法；采用小生境密度和小生境密度比較算子，不需要人為指定共享參數(shù)，使得結(jié)果更加客觀，在保持種群多樣性，保持優(yōu)秀個體的策略上更加有效；采用精英策略，為了保持下一代種群的優(yōu)秀性，采取父種群和其子種群相互競爭的方法。NSGAⅡ在下章將進行詳細的介紹。 本章小結(jié) 本章簡單介紹了求解多目標優(yōu)化模型的各種算法，從早期的傳統(tǒng)優(yōu)化算法到目前常用的啟發(fā)式算法，粒子群算法，并且著重介紹了多目標遺傳算法，對多目標遺傳算法的流程詳細闡述，并且對目前比較流行的幾種多目標遺傳算法進行評價，引出下一章節(jié)的內(nèi)容NSGAⅡ算法。第四章 非支配排序算法NSGAⅡ介紹和使用本文將使用NSGAⅡ算法來解決第二章中所提出的供應鏈下多目標調(diào)度模型，所以進行詳細的介紹。 小生境、精英策略和二元聯(lián)賽選擇要熟悉NSGAⅡ算法，首先對幾個基本概念進行一下了解。 小生境 自然界的小生境是指，棲息地中的某一個特定部分，一個個體在特定的時間里所處的特定空間和環(huán)境，小生境常常決定著其中的動植物的生存與否。居于小生境中的生物要競爭各種有限的資源，其中有兩種情況：一種是個體需要的生存資源與其他個體有很大差別，他需要特別的資源來生存，從而不需要與其他個體爭奪環(huán)境，資源；另一種則相反，個體之間的資源競爭非常激烈，適應這個競爭機制的個體才會存活下來，通常我們用排擠機制來表示這種現(xiàn)象。遺傳算法中的小生境技術(shù)[28]主要是為了維持種群的多樣性，防止算法發(fā)生“遺傳漂變”現(xiàn)象而陷入局部最優(yōu)。在同一非劣解集上，解個體的密度是不同的，比較稀疏的個體有比較大的機會在下一代種群中生存下來，而密度較大時，就必須通過一定的計算來進行劃分。 精英策略NSGAⅡ算法的精英策略就是將父代種群和子代種群結(jié)合的一種策略。通過結(jié)合產(chǎn)生數(shù)量為兩倍的新種群，其中為初始種群規(guī)模，采用父代與子代共同競爭來產(chǎn)生子代，這樣的做法主要是為了得到更優(yōu)的下一代。 二元聯(lián)賽選擇在以上的小生境技術(shù)的應用中，我們都是在同一個非劣解前沿面上，也就是同一個非劣解級數(shù)上的比較，只有在同一級數(shù)上，才能采用小生境技術(shù)計算比較密度來選擇個體。這只是個體選擇的一個方面，當有不同的非劣解級數(shù)，就需要根據(jù)級數(shù)來選擇個體。簡單的講就是：有不同級數(shù)的非劣解前沿面，取級數(shù)較小的；如果級數(shù)都相同，則采取小生境技術(shù)來選擇個體。這就是二元聯(lián)賽選擇，主要是為了保持種群多樣性，提高算法的效率。（NSGAⅡ）簡介非支配排序（Nondominated Sorting Genetic Algorithm）Ⅱ是Srinivas在由他自己和Deb共同提出的NSGA算法的基礎(chǔ)上改進的新型多目標遺傳算法。NSGA算法很好的將非支配排序思想應用其中，NSGA算法首先計算種群中所有個體的非支配數(shù)，并對其分配一個適應度值。接著對所有具有相同非支配數(shù)的個體進行分級：適應度值越小，級數(shù)越大；適應度值越大，級數(shù)越小。使得具有相同級數(shù)的個體有相同的機會進行選擇、交叉和變異操作進入到下一代種群中去。而為了保持種群的多樣性，采用基于擁擠策略的小生境技術(shù)，對于在相同級數(shù)，也就是在相同非支配前沿的個體中再進行重新制定。通過各種的實驗，NSGA算法的性能已經(jīng)得到了肯定，但是其中也存在諸多不足：NSGA算法的復雜多過高，為，其中M表示目標個數(shù)，N表示種群的大小，隨著目標函數(shù)和種群大小的增加，計算量的增加顯得尤為巨大；需要人為設(shè)定共享參數(shù)，這勢必影響算法的優(yōu)化性能；缺乏精英保留策略，精英保留策略可以有效的幫助留下優(yōu)秀個體，并且提高運算速度?；谝陨先秉c，NSGAⅡ應運而生。他對NSGA算法的上述確定進行了相應的改進：NSGAⅡ的算法復雜度由原來的降低到了，采用了一種更加合理的快速非劣前沿分級法；采用小生境密度和小生境密度比較算子，不需要人為指定共享參數(shù)，使得結(jié)果更加客觀，在保持種群多樣性，保持優(yōu)秀個體的策略上更加有效；采用精英策略，為了保持下一代種群的優(yōu)秀性，采取父種群和其子種群相互競爭的方法。（gen表示子代代數(shù)）文[28]。，NSGAⅡ算法的基本過程是：首先，采用某種算法或者隨機產(chǎn)生規(guī)模為N的初始種群，按照適應值進行非劣前沿分級，按照概率對初始種群進行選擇、交叉、變異操作，來得到第一代子種群；接著，將父種群和子種群結(jié)合，進行快速非劣前沿分級，同時對相應等級的個體計算小生境密度，根據(jù)非劣前沿等級和小生境密度，選取合適個體組成新的父代種群；重復以上步驟，選擇、交叉、變異，直到到達程序所要求的停止條件。Ⅱ的應用下面利用NSGAⅡ算法來求解第二章中所建立的多目標優(yōu)化模型。多目標車間調(diào)度問題一般都屬于NP難問題，遺傳算法的設(shè)計都比較復雜，要綜合考慮約束條件以及合理性。遺傳算法設(shè)計的難點，不外乎幾點：編碼解碼、適應度函數(shù)設(shè)計、選擇交叉變異概率的確定、終止條件的設(shè)定等，下面就這幾個方面，結(jié)合本文提出的模型進行一一的闡述。初始化種群開始生成第一代子群否進化代數(shù)gen＝2非劣前沿分級選擇、交叉、變異結(jié)束否是父、子代個體合并（精英策略）生成父代種群否gen＝gen+2快速非劣前沿分級選擇、交叉、變異小生境密度計算選擇適合個體組成新父代種群Gen小于最大代數(shù)？是是否 圖4. 1 多目標遺傳算法流程圖 編碼解碼遺傳算法的編碼問題一直是其出現(xiàn)以來的重要課題，編碼的好壞會影響算法的可行性和合法性。本文給出的是比較簡單的根據(jù)工件的編碼。用（x，z，t，D，H）表示一個工件的編碼，其中x表示工件序號， z表示工件產(chǎn)生的庫存大小，t表示工件的加工時間，D表示制造商工件x的交貨期，H表示物流商工件x的交貨期。表如一個工件的編碼（1，2，3，4，6）表示：工件1，會產(chǎn)生2的庫存量，使用了3的加工時間，制造商要在4的日期交貨，物流商要在6的日期交貨。用（y，s）表示一個機器的編碼，y表示機器的序號，s表示機器當前的工作狀態(tài)，0表示當前空閑，1表示當前繁忙正被占用。比如一個機器的編碼（1，1）表示，機器1當前有加工任務，新工件不能來被加工。這樣我們就可以用二維的染色體編碼來表示m臺機器和n個工件的加工情況，即為（x，y），染色體的長度即為工件數(shù)量n，編碼中相同機器編碼的先后出現(xiàn)，表示該機器上工件加工的先后次序。舉例，假設(shè)n＝6，m＝3，染色體編碼：（1，2）－（6，1）－（3，2）－（2，3）－（5，1）－（4，3）表示機器1上先后加工工件6和5，機器2上先后加工工件1和3，機器3上先后加工工件2和4。這樣解碼工作也就能順利的進行了，按照染色體的順序，一臺機器只能同時加工一個工件。以上例為例，機器1上先后加工工件6和5，機器2上先后加工工件1和3，機器3上先后加工工件3和4，然后根據(jù)工件的加工時間和庫存量來計算加工時間和運輸次數(shù)。 生成初始種群在滿足約束條件的基礎(chǔ)上，我們采用隨機生成的方法按照上述編碼方法，來生成初始種群，每個染色體長度為n，初始種群大小根據(jù)問題實際來設(shè)定。 適應度函數(shù)的設(shè)定適應度，顧名思義，就是個體對于環(huán)境的適應程度，我們以適應度的大小來衡量一個個體的優(yōu)劣能力。適應度大的個體被保留的概率也越大，反之則越小。在本算法的設(shè)計中，我們以目標函數(shù)的的值來衡量。在第二章的模型中，我們設(shè)計了4個目標函數(shù)，分別用，，來表示這個適應度值。 （4. 1） （4. 2） （4. 3） （4. 4） ：每臺機器同時只能加工一個工件，每個工件同時只能在一臺機器上加工，而且某個工件的完工時刻的庫存量不能大于b。對于不符合約束條件的個體我們不能直接淘汰，因為考慮到，雖然他目前不符合約束條件，但是在他的后代中可能隱藏著優(yōu)秀個體。所以我們對其添加一個懲罰系數(shù)。 非劣前沿分級 根據(jù)已經(jīng)產(chǎn)生的初始種群，我們根據(jù)其適應度的大小對其進行非劣前沿分級，NSGAⅡ方法有一種快速非劣前沿分級方法，步驟是：（1）對整個種群的染色體中每個染色體執(zhí)行下列操作：1）初始化集合，這個集合用來存放相對非劣的所有染色體； 2）初始化變量，代表相對所選染色體非劣的染色體數(shù)量； 3）對整個種群的染色體中的任何一個染色體執(zhí)行下列操作： ① 如果相對非劣，就把加入，表示為：② 如果相對非劣，相反的情況下，就增加的支配解數(shù)量，讓 4）如果，表示沒有其他染色體相對非劣，把劃分到第一級非劣前沿，用表示的非劣前沿級數(shù)，則，刷新第一級非劣前沿集合，將加入到中去，表示為：；（2）重復執(zhí)行第一步，將整個種群中的所有染色體進行非劣前沿分級；（3）初始化非劣前沿等級計數(shù)器；（4）判斷第級非劣前沿集合是否為空，如果非空，執(zhí)行下列操作：1）設(shè)，這個集合存放第級非劣前沿的染色體；2）對于在第級非劣前沿集合中的每個個體執(zhí)行下列操作：對中的每個染色體執(zhí)行下列操作：① 較少的支配解數(shù)量，令：；② 如果，表示在下一級非劣前沿中相對非劣的染色體不存在，設(shè)置，接著將加入到中，表示為：；3）再令非劣前沿等級計數(shù)器；4）當前中存放的就是下一級非劣前沿的染色體個體。本文的模型由到四個目標組成，對于模型的解需要由、這4個函數(shù)的大小一起決定，由這4個函數(shù)描繪出一個四維的等效用空間。 小生境技術(shù)假設(shè)t表示目標函數(shù)，g表示當前遺傳代數(shù)，表示初始種群規(guī)模，我們用表示第g代的第i個染色體在第r個目標函數(shù)上的值。這樣我們就能對各個目標函數(shù)的適應度函數(shù)值進行排序，表示為，其中，然后根據(jù)以下函數(shù)計算各個目標上的小生境大小： （4. 5） 精英策略在NSGAⅡ算法中采用精英策略來保留優(yōu)秀個體，以保證種群的多樣性和優(yōu)良性，具體的操作如下：(1)進行選擇，交叉和變異操作的父代種群是根據(jù)二元聯(lián)賽方法所獲取的。首先將父種群和子種群混合為數(shù)量兩倍于的種群，按照非劣前沿等級方法選擇個體，在同級非劣前沿等級中，對于密度較大的，進行小生境密度排序再進行選擇。通過這種二元聯(lián)賽方法取出數(shù)量為的個體作為選擇，交叉和變異操作的父種群，再產(chǎn)生下一代子種群。(2)我們采用保存每代前三級非劣前沿等級中的Pareto解，來作為最后的結(jié)果，也即是三個集合的并集（重復個體最為一個個體），其中g(shù)en為終止代數(shù)，G就作為最后的結(jié)果，表示問題的Pareto最優(yōu)解集。 NSGAⅡ算法選擇，交叉和變異算子的確定算子的確定也就是三種操作概率的設(shè)定，下面一一給予具體操作：（1）選擇算子 選擇操作也就是將父種群中的個體，按照適者生存的達爾文進化理論，選擇適應度比較好的個體進入下一代種群中去。本算法中選擇概率設(shè)定為＝，表示，父代種群中10%的個體將被淘汰，而這10%的消失數(shù)量就由下面的交叉和變異操作產(chǎn)生的新個體補全。 （2）交叉算子 －，的選擇會影響遺傳算法的搜索能力，增大雖然能提高全局搜索能力，但是也會降低局部搜索能力，導致局部優(yōu)秀解的流失；減小則效果相反。因此，引入了自適應的策略，使他在全局搜索和局部搜索的效果增強。自適應策略的意思就是根據(jù)遺傳算法中群體的狀態(tài)，自適應的改變的數(shù)值?；谝陨纤枷?，我們設(shè)計的交叉用下面的等式計算： （4. 6） 式中i表示遺傳代數(shù)，gen表示設(shè)定的遺傳代數(shù)。這樣初期的比較大，可以提高全局搜索能力，而后期為了防止陷入局部最優(yōu)，我們采取減小來提高性能。通過在父種群中40%到60%的個體進行交叉，然后在交叉的結(jié)果中按照選擇機制選取部分個體，來補充部分因選擇操作而丟失的個體，使得下一代種群保持一定的數(shù)目。 我們選擇多點交叉的方法來進行交叉操作，比如父代1染色體 （1，2）－（6，1）－（3，2）－（2，3）－（5，1）－（4，3）－（7，3）父代2染色體 （1，3）－（3，1）－（6，1）－（2，1）－（5，2）－（4，3）－（7，1）子代1染色體 （1，3）－（6，1）－（3，1）－（2，1）－（5，2）－（4，3）－（7，1）子代2染色體 （1，2）－（3，2）－（6，1）－（2，3）－（5，2）－（4，3）－（7，3） 在兩個父代中有完全相同的基因位（6，1）和（4，3），則選擇