多目標遺傳演算法程序
排課問題的本質是將課程、教師和學生在合適的時間段內分配到合適的教室中，涉及到的因素較多，是一個多目標的調度問題，在運籌學中被稱為時間表問題（Timetable Problem，TTP）。設一個星期有n個時段可排課，有m位教師需要參與排課，平均每位教師一個星期上k節課，在不考慮其他限制的情況下，能夠推出的可能組合就有 種，如此高的復雜度是目前計算機所無法承受的。因此眾多研究者提出了多種其他排課演算法，如模擬退火，列表尋優搜索和約束滿意等。
Github ： https://github.com/xiaochus/GeneticClassSchele
遺傳演算法（Genetic Algorithm）是模擬達爾文生物進化論的自然選擇和遺傳學機理的生物進化過程的計算模型，是一種通過模擬自然進化過程搜索最優解的方法。遺傳演算法的流程如下所示：
遺傳演算法首先針對待解決問題隨機生成一組解，我們稱之為種群（Population）。種群中的每個個體都是問題的解，在優化的過程中，演算法會計算整個種群的成本函數，從而得到一個與種群相關的適應度的序列。如下圖所示：
為了得到新的下一代種群，首先根據適應度對種群進行排序，從中挑選出最優的幾個個體加入下一代種群，這一個過程也被稱為精英選拔。新種群餘下的部分通過對選拔出來的精英個體進行修改得到。
對種群進行修改的方法參考了生物DAN進化的方法，一般使用兩種方法： 變異 和 交叉 。 變異 的做法是對種群做一個微小的、隨機的改變。如果解的編碼方式是二進制，那麼就隨機選取一個位置進行0和1的互相突變；如果解的編碼方式是十進制，那麼就隨機選取一個位置進行隨機加減。 交叉 的做法是隨機從最優種群中選取兩個個體，以某個位置為交叉點合成一個新的個體。
經過突變和交叉後我們得到新的種群（大小與上一代種群一致），對新種群重復重復上述過程，直到達到迭代次數（失敗）或者解的適應性達到我們的要求（成功），GA演算法就結束了。
演算法實現
首先定義一個課程類，這個類包含了課程、班級、教師、教室、星期、時間幾個屬性，其中前三個是我們自定義的，後面三個是需要演算法來優化的。
接下來定義cost函數，這個函數用來計算課表種群的沖突。當被測試課表沖突為0的時候，這個課表就是個符合規定的課表。沖突檢測遵循下面幾條規則：
使用遺傳演算法進行優化的過程如下，與上一節的流程圖過程相同。
init_population ：隨機初始化不同的種群。
mutate ：變異操作，隨機對 Schele 對象中的某個可改變屬性在允許范圍內進行隨機加減。
crossover ：交叉操作，隨機對兩個對象交換不同位置的屬性。
evolution ：啟動GA演算法進行優化。
實驗結果
下面定義了3個班，6種課程、教師和3個教室來對排課效果進行測試。
優化結果如下，迭代到第68次時，課程安排不存在任何沖突。
選擇1203班的課表進行可視化，如下所示，演算法合理的安排了對應的課程。
2. MATLAB遺傳演算法工具箱求解非線性多目標優化問題
將下屬兩個目標函數分別保存在兩個m文件中
function f1=func1(x) %第一目標函數
f1=x(:,1).*x(:,1)./4+x(:,2).*x(:,2)./4;
function f2=func2(x) %第二目標函數
f2=x(:,1).*(1-x(:,2))+10;
function GA()
clear;clc;close all
NIND=100; %個體數目
MAXGEN=50; %最大遺傳代數
NVAR=2; %變數個數
PRECI=20; %變數的二進制位數
GGAP=0.9; %代溝
trace1=[];trace2=[];trace3=[]; %性能跟蹤
%建立區域描述器
% rep([PRECI],[1,NVAR])
FieldD=[rep([PRECI],[1,NVAR]);rep([1;2],[1,NVAR]);rep([1;0;1;1],[1,NVAR])];
Chrom=crtbp(NIND,NVAR*PRECI); %初始種群
v=bs2rv(Chrom,FieldD) ; %初始種群十進制轉換
gen=1;
while gen<MAXGEN,
[NIND,N]=size(Chrom);
M=fix(NIND/2);
ObjV1=func1(v(1:M,:)); %分組後第一目標函數值
FitnV1=ranking(ObjV1); %分配適應度值
SelCh1=select('sus',Chrom(1:M,:),FitnV1,GGAP); %選擇
ObjV2=func2(v(M+1:NIND,:)); %分組後第二目標函數值
FitnV2=ranking(ObjV2); %分配適應度值
SelCh2=select('sus',Chrom(M+1:NIND,:),FitnV2,GGAP); %選擇
SelCh=[SelCh1;SelCh2]; %合並
SelCh=recombin('xovsp',SelCh,0.7); %重組
Chrom=mut(SelCh); %變異
v=bs2rv(Chrom,FieldD);
trace1(gen,1)=min(func1(v));
trace1(gen,2)=sum(func1(v))/length(func1(v));
trace2(gen,1)=min(func2(v));
trace2(gen,2)=sum(func2(v))/length(func2(v));
trace3(gen,1)=min(func1(v)+func2(v));
trace3(gen,2)=sum(func1(v))/length(func1(v))+sum(func2(v))/length(func2(v));
gen=gen+1;
end
figure(1);clf;
plot(trace1(:,1));hold on;plot(trace1(:,2),'-.');
plot(trace1(:,1),'.');plot(trace1(:,2),'.');grid on;
legend('解的變化','種群均值的變化')
xlabel('迭代次數');ylabel('目標函數值');
figure(2);clf;
plot(trace2(:,1));hold on;
plot(trace2(:,2),'-.');
plot(trace2(:,1),'.');
plot(trace2(:,2),'.');grid;
legend('解的變化','種群均值的變化');
xlabel('迭代次數');ylabel('目標函數值');
figure(3);clf;
plot(trace3(:,1));hold on;
plot(trace3(:,2),'-.');
plot(trace3(:,1),'.');
plot(trace3(:,2),'.');grid;
legend('解的變化','種群均值的變化');
xlabel('迭代次數');ylabel('目標函數值');
figure(4);clf;plot(func1(v));hold on;
plot(func2(v),'r-.');grid;
3. 多目標優化問題
形式化定義：
特點：
①包含多個可能有沖突的目標函數。
②希望找到能夠很好平衡全部優化目標的解集；
帕累托最優是指資源分配的一種理想狀態。給定固有的一群人和可分配的資源，如果從一種分配狀態到另一種分配狀態，在沒有使得任何人的境況變壞的前提下，使得至少有一個人變得更好，這就是帕累托改善的狀態；換言之，不可能在不是任何其他人受損的情況下再改善某些人的境況。
支配（Dominace） ：當x1和x2滿足如下條件時稱x1支配x2：①對於所有目標函數x1不比x2差；②至少在一個目標函數上，x1嚴格比x2要好。
對於點1和點2：對於目標函數f1是越大越好，在取相同f2時，點1比點2好；對於目標函數f2是越小越好，在取相同f1時，點1比點2好。所以點1支配點2。
對於點1和點4：目標函數f1上，取相同f2時，點4比點1好；目標函數f2上，取相同f1時，點1比點4好。所以點1和點4互不支配。
不可支配解集（Non-dominated solution set） ：當一個解集中任何一個解都不能被該集合中其他解支配，那麼就稱該解集為不可支配解集。
帕累托最優解集（Pareto-optimal set ）：所有可行中的不可支配解集被稱為帕累托最優解集。
帕累托最優前沿面（Pareto-optimal front） ：帕累托最優解集的邊界（boundary）被稱為帕累托最優前沿面。
多目標優化問題的目標 ：①尋找盡可能接近最優的解集；②盡可能增大找到解的多樣性。
優點：簡單
缺點：①很難設定一個權重向量能夠獲得帕累托最優解；②在一些非凸情況下不能夠保證獲得帕累托最優解。
優點：能夠應用到凸函數和非凸函數場景下。
缺點：函數需要精心選擇，需要在獨立函數的最小值或最大值之內。
優點：weighted Techebycheff metirc能夠保證獲得所有帕累托最優解。
缺點：①需要有每個函數最大值和最小值的先驗知識；②需要每個目標函數的z*能夠獨立被找到；③對於較小的p值，不一定保證所有能夠獲得所有的帕累托最優解；④隨著p增加，問題會變得不可求導。
①隨機產生初始種群；
②計算各點的目標函數值和約束函數值；
③根據目標函數值對種群分級；
④根據約束函數值和分級結果計算各點的約束罰項、劣解罰項及總罰項；
⑤根據各點的總罰項計算適應度；
⑥根據各點的適應度，進行選擇、交叉和變異操作，生成新種群；
⑦將總罰項為0的點放入非劣解集候選表，對候選表進行檢查，保留第1級非劣點，刪除其他點；
⑧檢查是否收斂，如沒有，轉到步驟②；
⑨刪除候選表中與其他店距離太近的點；
⑩輸出候選表中的帕累托最優解集及對應的目標函數值；
最後，決策人根據個人偏好從帕累托最優解集中挑選出最適合該問題的解。
遺傳演算法相比傳統的演算法的優點是能夠得到一個最優解集，而不是單單一個最優解，這樣會提供更多的選擇，但是計算的復雜度可能稍高，而且裡面涉及的一些函數需要精心設計。
1.權重系數轉換法
對每個目標函數fi(x)賦予權重wi，wi為目標函數的重要程度。μ=Σwi·fi(x)，這里就將多目標轉化為單目標函數，將μ作為評價函數。
2.並列選擇法
主要步驟：(1)將種群按照目標函數個數等分為子種群，為每個子種群分配一個目標函數。(2)將子種群中的個體按照各自的目標函數選擇出適應度高的個體，然後將其組成一個子種群。(3)再將子種群進行交配、變異、生成下一代父親種群。然後再重復第一步。
並列選擇法的缺點在於易於生成單個目標函數的極端最優解，而較難生成一種多個目標在某種程度上都比較滿意的折中解。
3.排序選擇法
基本思想就是基於「帕累托最優個體」的概念對群體中的個體進行排序，然後根據這個次序進行種群選擇。這樣的話，就能夠讓帕累托最優個體有更多的機會遺傳到下一代。這種方法的缺點是僅僅度量了各個個體之間的優越次序，而並未度量各個個體的分散程度，所以容易生成相似的解，而不是分布較廣的多個最優解。
4.共享函數法
針對排序選擇方法的缺點，即所求的幾個最優解通常都是集中於最優解集合的某一個小區域內，而不是分散在整個帕累托最優解集合。由此，引出了基於共享函數的 小生境技術 （小生境技術就是將每一代個體劃分為若干類，每個類中選出若干適應度較大的個體作為一個類的優秀代表組成一個群，再在種群中，以及不同種群中之間，雜交，變異產生新一代個體群。同時採用預選擇機制和排擠機制或分享機制完成任務。）。該演算法對相同個體或類似個體的數目加以限制，以便能夠產生出種類較多的不同的最優解。這就引出一個問題，怎麼衡量兩個個體之間的相似度？這就是小生境數。顧名思義，小生境就是在一個小環境中相似的個體種群。最常見的公式為：
s(d)為共享函數，是表示群體中兩個個體之間密切關系程度的一個函數。d(X,Y)為個體X,Y之間的hanmin距離，也是用於衡量個體間相似度的一個函數。在計算出小生境數後，可以是小生境數較小的個體能夠有更多的機會被選中，遺傳到下一代群體中，即相似程度較小的個體能夠有更多的機會被遺傳到下一代群體中。
缺點：每次選擇操作時都需要進行大量的個體之間的優越關系的評價和比較運算，使得演算法搜索效率較低。
5.Horn和Nafploitis印的基於小生境帕累托多目標遺傳演算法(NPGA)
類似於第2個的並列選擇法，將每一代個體劃分為若干類，每個類別選出若干適應度較大的個體作為一個類的優秀代表組成一個種群，然後交配變異產生新一代種群。基於這種小生境的遺傳演算法（Niched Genetic Algorithms，NGA），可以更好地保持解的多樣性，同時具有很高的全局尋優能力和收斂速度，特別適合於復雜多峰函數的優化問題。
6.Srinvivas和Deb的非支配排序遺傳演算法NSGA
1980年提出來的，在遺傳演算法的基礎上對選擇再生方法進行改進：將每個個體按照他們的支配和非支配關系進行再分層，再做選擇操作，從而達到目的。
其分層的含義就是取出種群中的非支配個體組成一個小種群（第一個非支配最優層），並賦予其中所有個體一個共享的虛擬適應度值。然後再取出個體後的種群中繼續取出非支配個體，再將它們組成一個小種群（第二個非支配最優層），並且賦予所有個體一個共享的虛擬適應度值。重復上述步驟，直到原始種群分配完畢，這就是分層，也叫非支配型排序。
非支配型排序遺傳演算法的缺點：①計算復雜度較高；②沒有精英策略；③需要制定共享半徑。
針對以上問題，k·Deb 於2002年提出了 7 的方法。
7.帶精英策略的非支配排序遺傳散發——NSGAII
1).採用快速非支配型排序，降低了演算法復雜度。其復雜度降為了O(MN**2)。
2).提出了擁擠度和擁擠度比較運算元，代替需要指定共享半徑的適應度共享策略。並在快速排序後的同級比較中作為勝出標准。使准pareto解中的個體能擴展到整個pareto域中，並均勻分布，保持了種群的多樣性。
3).引入精英策略，擴大采樣空間。將父代種群和子代種群合並，保證優良個體能夠留存下來。
其演算法步驟如下：1.首先隨機產生數量為n的初始種群，然後對其進行非支配型排序。接下來，就是常規的選擇，交叉，變異操作產生第一代子代種群。2.然後，從第二代開始，將父代和子代合並。然後對其進行快速非支配型排序，同時計算每個非支配層的個體進行擁擠度的計算。然後根據非支配關系和擁擠度來選擇合適的個體組成新的父代種群。最後通過再通過選擇，交叉，變異產生子代。3.接下來，重復第二步。
具體做法參考：https://blog.csdn.net/quinn1994/article/details/80679528/
4. 怎麼評價MATLAB中gamultiobj函數（多目標遺傳演算法）的計算結果比如下面的函數和其部分結果
您好，多目標遺傳演算法可以得到Pareto Front圖，即您展示的結果。至於評價方法應由您自己確定，比如最簡單的線性加權函數評價方法，評價值Evalue=w1*minf1(x1,x2)+w2*minf2(x1,x2)，其中w1+w2=1。
總的來說，就是依據自己的需要進行評價，matlab中不含有評價方法（因為評價方法很靈活）。
5. tSp Concorder演算法原理
tsp問題遺傳演算法將多目標按照線性加權的方式轉化為單目標，然後應用傳統遺傳演算法求解
其中w_i表示第i個目標的權重，f_k表示歸一化之後的第i個目標值。我們很容易知道，這類方法的關鍵是怎麼設計權重。比如，Random Weight Genetic Algorithm (RWGA) 採用隨機權重的方式，每次計算適應度都對所有個體隨機地產生不同目標的權重，然後進行選擇操作。Vector-Evaluated Genetic Algorithm (VEGA) 也是基於線性加權的多目標遺傳演算法。如果有K個目標，VEGA 會隨機地將種群分為K個同等大小子種群，在不同的子種群按照不同的目標函數設定目標值，然後再進行選擇操作。VEGA 實質上是基於線性加權的多目標遺傳演算法。VEGA 是第一個多目標遺傳演算法，開啟了十幾年的研究潮流。
1.TSP問題是指假設有一個旅行商人要拜訪n個城市，他必須選擇所要走的路徑，路徑的限制是每個城市只能拜訪一次，而且最後要回到原來出發的城市。路徑的選擇目標是要求得的路徑路程為所有路徑之中的最小值。本文使用遺傳演算法解決att30問題，即30個城市的旅行商問題。旅行商問題是一個經典的組合優化問題。一個經典的旅行商問題可以描述為：一個商品推銷員要去若干個城市推銷商品，該推銷員從一個城市出發，需要經過所有城市後，回到出發地。應如何選擇行進路線，以使總的行程最短。從圖論的角度來看，該問題實質是在一個帶權完全無向圖中，找一個權值最小的Hamilton迴路。由於該問題的可行解是所有頂點的全排列，隨著頂點數的增加，會產生組合爆炸，它是一個NP完全問題。TSP問題可以分為對稱和不對稱。在對稱TSP問題中，兩座城市之間來回的距離是相等的，形成一個無向圖，而不對稱TSP則形成有向圖。對稱性TSP問題可以將解的數量減少了一半。所以本次實驗的TSP問題使用att48數據，可在tsplib中下載數據包。演化演算法是一類模擬自然界遺傳進化規律的仿生學演算法，它不是一個具體的演算法，而是一個演算法簇。遺傳演算法是演化演算法的一個分支，由於遺傳演算法的整體搜索策略和優化計算是不依賴梯度信息，所以它的應用比較廣泛。我們本次實驗同樣用到了遺傳演算法（用MATLAB編寫）來解決TSP問題。
6. nsga2演算法全稱
NSGA2演算法
1、得到：可以看到NSGA-II演算法得到的Pareto最優前沿質量很高：最優解均勻分布在不連續前沿的各個線段上；同時在最優前沿以外沒有個體存在。
2、NSGA-II特別的地方就在它的選擇過程上，其他的和其他演算法也沒什麼區別。選擇過程分兩個部分： 把種群分成一組Pareto非支配集。一個非支配集里的個體不被當前或之後非支配集里的任何個體支配。
3、遺傳演算法在matlab里有兩個函數，分別是ga和gaoptimset，前者用來調用遺傳演算法，後者用來設定遺傳演算法的參數，具體內容可以doc ga查看，遺傳演算法有哪些參數可以直接在命令窗口輸入gaoptimset查看，祝好。
4、針對新生代群體進行交叉和變異操作，以概率的方法判決進行交叉還是變異操作，一般來說，我們以較大的概率交叉，較小的概率進行變異，具體的交叉變異操作文獻上都有，和二進制遺傳演算法是不一樣的，一會兒我會講到。
ncga和nsga-ii遺傳演算法的區別
1、ncga和nsga-ii遺傳演演算法的區別 1 初始化染色體，這一步和粒子群初始化沒啥區別 2 採用二人或多人錦標賽形式，在配對池裡產生新的染色體子代，新生代種群規模為原來種群規模的一半。
2、NSGA-II特別的地方就在它的選擇過程上，其他的和其他演算法也沒什麼區別。選擇過程分兩個部分： 把種群分成一組Pareto非支配集。一個非支配集里的個體不被當前或之後非支配集里的任何個體支配。
3、可以看到NSGA-II演算法得到的Pareto最優前沿質量很高：最優解均勻分布在不連續前沿的各個線段上；同時在最優前沿以外沒有個體存在。
4、基本遺傳演算法是對交叉後的個體進行變異的，具體你可以看王小平的《遺傳演算法——理論、應用與軟體實現》。
學習多目標優化需要掌握哪些python知識
你需要掌握Python基本語法規則及變數、邏輯控制、內置數據結構、文件操作、高級函數、模塊、常用標准庫模塊、函數、異常處理、MySQL使用、協程等知識點。
學習基本的語法，包括數據結構（數組，字典等）。了解數據類型，以及他的類型轉換。2學會流程式控制制---選擇，循環。3函數，模塊，熟練使用常用的內建函數。
文件操作：很多時候我們需要對本地文件進行一些增刪改查的操作。模塊和包：Python之所以如此受歡迎，很大程度上得益於它有非常豐富模塊和包，這些東西可以讓你少造輪子。
WEB開發 Python擁有很多免費數據函數庫、免費web網頁模板系統、以及與web伺服器進行交互的庫，可以實現web開發，搭建web框架，目前比較有名氣的Python web框架為Django。
混合遺傳演演算法和遺傳演演算法有什麼區別
1、一樓回答的對，混合遺傳演算法就是將遺傳演算法與其他演算法相混合，互取所長，互補所短。比如遺傳演算法與模擬退火演算法的混合，就是將遺傳演算法的全局搜索能力與模擬退火演算法的局部搜索能力結合起來，形成一種強大的演算法。
2、遺傳演算法是一種全局搜索演算法，不需要目標函數的導數信息，它能夠很快搜索到最優值所處范圍范圍。
3、遺傳演算法是演化演算法中的一種。遺傳演算法（Genetic Algorithm）是一類借鑒生物界的進化規律（適者生存，優勝劣汰遺傳機制）演化而來的隨機化搜索方法。
4、混合遺傳就是子代的性狀是父本和母本性狀的混合，它的後代再也分不出那是父本性狀或母本性狀了。但孟德爾遺傳包括分離定律和自由組合定律，是親本基因的組合。額，語文水平有限。。
7. 遺傳演算法-總結
最近在做遺傳演算法的項目，簡單記錄一下。
遺傳演算法是模擬自然界生物進化機制的一種演算法，在尋優過程中有用的保留無用的去除。包括3個基本的遺傳運算元：選擇（selection）、交叉（crossover）和變異（mutation）。遺傳操作的效果與上述3個遺傳運算元所取的操作概率、編碼方法、群體大小、初始群體，以及適應度函數的設定密切相關。
1、種群初始化
popsize 種群大小，一般為20-100，太小會降低群體的多樣性，導致早熟；較大會影響運行效率；迭代次數一般100-500；交叉概率：0.4-0.99，太小會破壞群體的優良模式；變異概率：0.001-0.1，太大搜索趨於隨機。編碼包括實數編碼和二進制編碼，可以參考遺傳演算法的幾個經典問題，TSP、背包問題、車間調度問題。
2、選擇
目的是把優化個體直接遺傳到下一代或通過配對交叉產生新的個體再遺傳到下一代，我大部分採用了輪盤賭的方法。具體可參考 http://my.oschina.net/u/1412321/blog/192454 輪盤賭方法各個個體的選擇概率和其適應值成比例，個體適應值越大，被選擇的概率也越高，反之亦然。在實際問題中，經常需要最小值作為最優解，有以下幾種方法進行轉換
a、0-1之間的數據，可以用1-該數值，則最小值與最大值互換；
b、 求倒數；
c、求相反數；
以上幾種方法均可以將最大值變為最小值，最小值變為最大值，便於利用輪盤賭選擇最優個體，根據實際情況來確定。
3、交叉
交叉即將兩個父代個體的部分結構加以替換重組而生成新個體的操作，通過交叉，遺傳演算法的搜索能力得以飛躍提高。根據編碼方法的不同，可以有以下的演算法：
a、實值重組
離散重組、中間重組、線性重組、擴展線性重組
b、二進制交叉
單點交叉、多點交叉、均勻交叉、洗牌交叉、縮小代理交叉
4、變異
基本步驟：對群中所有個體以事先設定的變異概率判斷是否進行變異；對進行變異的個體隨機選擇變異位進行變異。根據編碼表示方法的不同，有實值變異和二進制變異
變異的目的：
a、使遺傳演算法具有局部的隨機搜索能力。當遺傳演算法通過交叉運算元已接近最優解鄰域時，利用變異運算元的這種局部搜索能力可以加速向最優解收斂。顯然該情況下變異概率應取較小值，否則接近最優解的積木塊會因為變異遭到破壞。
b、使遺傳演算法可維持多樣性，以防止未成熟收斂現象。此時收斂概率應取較大值。
變異概率一般取0.001-0.1。
5、終止條件
當最優個體的適應度達到給定的閾值，或者最優個體的適應度和群體適應度不再上升時，或者迭代次數達到預設的代數時，演算法終止。預設代數一般為100-500。
6、其它
多變數：將多個變數依次連接
多目標：一種方法是轉化為單目標，例如按大小進行排序，根據排序和進行選擇，可以參考 https://blog.csdn.net/paulfeng20171114/article/details/82454310