1、目標規劃與遺傳算法第1頁，共42頁，2022年，5月20日，9點12分，星期五一、多目標規劃第2頁，共42頁，2022年，5月20日，9點12分，星期五多目標規劃是在一組剛性約束條件下，以多個柔性條件為目標函數的一種規劃問題。為了能夠同時達到多個目標的優化，往往是很難做到的。因為，目標函數是相互沖突的，一個目標的更優是要犧牲其他目標作為代價的。有效解（非劣解、Pareto解） 在不犧牲其他目標函數的前提下，不能再改進任何一個目標函數值的可行解。第3頁，共42頁，2022年，5月20日，9點12分，星期五求解方法; 1、權重和方法：每個目標函數分配權重并將其組合成為一個目標函數 權重的選擇原則：

2、使每個目標在加權后的地位相當。比如：一個目標表示利潤， 另一個目標表示效率，兩者相差 因此，權重應取相當數量級。第4頁，共42頁，2022年，5月20日，9點12分，星期五 2、妥協方法：是一種根據距離函數進行目標搜索行為的數學表達。 設 表示是第i個目標在不考慮其他目標時的最優值。第5頁，共42頁，2022年，5月20日，9點12分，星期五例 最小費用最大流第6頁，共42頁，2022年，5月20日，9點12分，星期五網絡最大流中不涉及費用問題，在實際問題中，在網絡中的各邊的運輸費用是各不相同的，在滿足最大流的情況下，求出最小費用，就是最小費用最大流問題。下圖所示是最小費用最大流問題。每一條邊

3、上有兩個數字，前者表示容量，后者表示單位費用。 第7頁，共42頁，2022年，5月20日，9點12分，星期五 設 是定義在網絡圖G的邊集E上的一個實數函數，表示i-j運輸量及最大量。設 是定義在網絡圖G的邊集E上的一個實數函數，表示i-j運輸的運費。滿足：第8頁，共42頁，2022年，5月20日，9點12分，星期五（1） -每條邊的流量不超過該邊大弧容量。 （2） -中間點流入與流出平衡。 第9頁，共42頁，2022年，5月20日，9點12分，星期五（3） -發點總流出與收點總流入平衡。 其數學模型： -由發點1到其它點的流出量總和。N表示收點.第10頁，共42頁，2022年，5月20日，9點

4、12分，星期五-由發點1到其它點的費用總和。N表示收點.第11頁，共42頁，2022年，5月20日，9點12分，星期五二、目標規劃目標規劃是多目標優化的一種妥協模型，其特點是，每一個目標都有一個理想目標值，目標規劃的目的是極小化各目標函數與理想目標值的正、負偏差。在目標之間，根據其重要性的不同，建立一個優先結構是非常必要的。即根據決策者的偏好對所有目標進行排序。第12頁，共42頁，2022年，5月20日，9點12分，星期五數學模型:第13頁，共42頁，2022年，5月20日，9點12分，星期五解釋:為優化因子,表示各目標的相對重要性為優先級j的第i個目標正、負偏差的權因子;為目標I偏離目標值的

5、正、負偏差；N維決策變量；為目標約束，軟性條件第14頁，共42頁，2022年，5月20日，9點12分，星期五系統約束，剛性條件第i個目標值優先級個數，目標約束個數，系統約束個數。目標函數另一種表示：表示按字典序極小化目標向量第15頁，共42頁，2022年，5月20日，9點12分，星期五續例 最小費用最大流在沒有考慮費用的前提下,最大流顯然是11.要完成最大流的費用的最小值是180.現在的問題:如何用最小的費用,完成最大流(至少5以上)?第16頁，共42頁，2022年，5月20日，9點12分，星期五第一目標是費用S,理想值為180. 越大越好.極大化第17頁，共42頁，2022年，5月20日，9

6、點12分，星期五（2）第二目標是流量，至少為5。 越大流越大，極大化。第18頁，共42頁，2022年，5月20日，9點12分，星期五（3）字典序的目標函數 第19頁，共42頁，2022年，5月20日，9點12分，星期五三、遺傳算法遺傳算法是一種通過模擬自然進化過程搜索最優解的方法，對多目標規劃問題的求解很有效。在優化問題中，如果目標函數是多峰的，或者搜索空間不規則，就要求所使用的算法必須具有高度的魯棒性，以避免在局部最優解附近徘徊。遺傳算法的優點恰好是全局搜索能力強。第20頁，共42頁，2022年，5月20日，9點12分，星期五遺傳算法: 染色體通常是一串數據(或數組),用來作為優化問題的解的

7、代碼,其本身不一定是解.1、隨機產生一定數目的初始染色體，組成一個種群，種群中染色體的數目稱為種群規模（pop_size);2、用評價函數（eval)來評價每一個染色體的優劣（即適應度）;3、遺傳選擇操作，根據適應度，從當前種群中選出優良的染色體，成為新一代染色體；第21頁，共42頁，2022年，5月20日，9點12分，星期五4、對這個新的種群進行交叉操作，然后進行變異操作。5、重復進行選擇、交叉、變異，經過一定次數的迭代處理以后，把最好的染色體作為優化問題的最優解。第22頁，共42頁，2022年，5月20日，9點12分，星期五例1第23頁，共42頁，2022年，5月20日，9點12分，星期五

8、1、解的結構 種群pop_size=30; 變量個數N=3； 染色體CHROMOSOMEpop_size+1N+1;2、解的可行性 static void initialization(void) double xN+1; /* N is the number of variables*/ int i,j; for(i=1; i=POP_SIZE; i+) mark: for(j=1; j=N; j+) xj=myu(0,10); if(constraint_check(x)=0) goto mark; for(j=1; jb) printf(nThe first parameter shou

9、ld be less than the second!);exit(1); y = (double)rand()/(RAND_MAX); return (a+(b-a)*y);第25頁，共42頁，2022年，5月20日，9點12分，星期五static int constraint_check(double x)double a;int n;for(n=1;n=N;n+) if(xn100) return 0;return 1;第26頁，共42頁，2022年，5月20日，9點12分，星期五3、評價函數A、基于序的評價函數：i=1染色體最好，i=pop_size染色體最差根據偏好（多目標規劃）、優

10、先級（目標規劃）將個體進行排序，好的染色體排前面，差的排后面。第27頁，共42頁，2022年，5月20日，9點12分，星期五B、權重和評價函數適應值越小，染色體越好第28頁，共42頁，2022年，5月20日，9點12分，星期五static void objective_function(void)double x1,x2,x3; int i;for(i = 1; i = POP_SIZE; i+) x1 = CHROMOSOMEi1;x2 = CHROMOSOMEi2;x3 = CHROMOSOMEi3;OBJECTIVEi1 = 3-sqrt(x1);if(OBJECTIVEi10) OBJ

11、ECTIVEi1=0; OBJECTIVEi2 = 4-sqrt(x1+2*x2);if(OBJECTIVEi20) OBJECTIVEi2=0;OBJECTIVEi3 = 5-sqrt(x1+2*x2+3*x3);if(OBJECTIVEi30) OBJECTIVEi3=0;for(i=1;i=POP_SIZE;i+) OBJECTIVEi0= 10000*OBJECTIVEi1+100*OBJECTIVEi2+OBJECTIVEi3;第29頁，共42頁，2022年，5月20日，9點12分，星期五static void evaluation(int gen) double a; int i,

12、 j, k, label; objective_function(); if(gen=0) for(k=0; k=M; k+) OBJECTIVE0k=OBJECTIVE1k; for(j = 1; j = N; j+) CHROMOSOME0j=CHROMOSOME1j; 第30頁，共42頁，2022年，5月20日，9點12分，星期五for(i=0; iPOP_SIZE; i+) label=0; a=OBJECTIVEi0; for(j=i+1; j=POP_SIZE; j+) if(TYPE*a)(TYPE*OBJECTIVEj0) a=OBJECTIVEj0;label=j; if(l

13、abel!=0) for(k=0; k=M; k+) a=OBJECTIVEik;第31頁，共42頁，2022年，5月20日，9點12分，星期五 OBJECTIVEik=OBJECTIVElabelk; OBJECTIVElabelk=a; for(j=1; j=N; j+) a=CHROMOSOMEij; CHROMOSOMEij=CHROMOSOMElabelj; CHROMOSOMElabelj=a; 第32頁，共42頁，2022年，5月20日，9點12分，星期五4、選擇過程 選擇過程是以旋轉輪盤賭pop_size次為基礎的，賭輪上刻度是按染色體的適應值來劃分的。刻度不是均勻分配的，染色

14、體的適應值越大，該染色體所占賭盤的面積越大，該染色體被選中的概率越大。每次選擇都會產生新一代染色體pop_size個。 無論使用何種評價函數，選擇過程總可以表示以下步驟完成： 1、對每個染色體 ，計算累積概率 第33頁，共42頁，2022年，5月20日，9點12分，星期五2、從區間 中產生一個隨機數r3、若 ，則選擇第i個染色體4、重復步驟2和步驟3共pop_size次，這樣可以得到pop_size個復制的染色體第34頁，共42頁，2022年，5月20日，9點12分，星期五static void selection() double r, tempPOP_SIZE+1N+1; int i, j

15、, k; for(i=1; i=POP_SIZE; i+) r=myu(0, qPOP_SIZE); for(j=0; j=POP_SIZE; j+) if(r=qj) for(k=1; k=N; k+) tempik=CHROMOSOMEjk;第35頁，共42頁，2022年，5月20日，9點12分，星期五break; for(i=1; i=POP_SIZE; i+) for(k=1; k=N; k+) CHROMOSOMEik=tempik;第36頁，共42頁，2022年，5月20日，9點12分，星期五5、交叉操作 用種群（pop_size個）的染色體進行交叉操作產生新一代染色體，方法如下：

16、 1、定義概率參數 ，（表示每一次交叉操作后大約有 個染色體發生改變）。 2、在0，1中產生隨機數r,如果 ，則在1到pop_size中隨機取兩個染色體進行交叉操作，產生兩個新的染色體取代舊的染色體，（注意：如果新的染色體不是可行解，則新的染色題無效，不取代，但交叉操作一次），重復步驟2共pop_size/2次。 第37頁，共42頁，2022年，5月20日，9點12分，星期五static void crossover() int i, j, jj, k, pop; double r, xN+1, yN+1; pop=POP_SIZE/2; for(i=1; iP_CROSSOVER) cont

17、inue; j=(int)myu(1,POP_SIZE); jj=(int)myu(1,POP_SIZE); r=myu(0,1); for(k=1; k=N; k+) xk=r*CHROMOSOMEjk+(1-r)*CHROMOSOMEjjk;第38頁，共42頁，2022年，5月20日，9點12分，星期五yk=r*CHROMOSOMEjjk+(1-r)*CHROMOSOMEjk; if(constraint_check(x)=1) for(k=1; k=N; k+) CHROMOSOMEjk=xk; if(constraint_check(y)=1) for(k=1;k=N; k+) CHR

18、OMOSOMEjjk=yk; 第39頁，共42頁，2022年，5月20日，9點12分，星期五6、變異操作 同交叉操作類似。 1、定義概率參數 大數M，方向 （表示每一次變異后大約有 個染色體發生進化，其中 ） 2、在區間0，1中產生隨機數r,如果 ,則在1到pop_size中隨機取一個染色體進行變異，如果是可行解，則取代該染色體。 3、重復pop_size次步驟2。 第40頁，共42頁，2022年，5月20日，9點12分，星期五static void mutation(void) int i, j, k; double xN+1, yN+1, infty, directionN+1; double INFTY=10, pre