用遺傳演算法實現求ZDT6最優解以及自動設計模擬電路

用遺傳演算法實現求ZDT6最優解以及自動設計模擬電路

Diego大叔

標準圖像見： ETH - SOP - Downloads/Material - Supplementary Material - Testproblems - ZDT 6

從結果上看，我們做出來的符合標準圖像。

我是個電路工程師，所以不會講數學方面的原理知識，本篇文章純粹從實際項目入手。我們先完成了ZDT6的遺傳演算法，然後套用到了差分運算放大器的設計上。實現了mos管的長度和寬度的自動設計，以GBW和power為優化目標。當然以上這些都不是什麼新鮮東西，這是教課教授的學生在2000年以前完成的論文，距今已經過去了快20年。教授當年還用神經網路演算法，實現了IC layout的自動布線，從顯示的圖片上來看，效果也不錯。

不說廢話，進入code正題。文中我也不會去說母體，子代，mutation，recombination從生物領域拿過來的拗口的術語，我覺得這些術語純粹就是為了「看起來高大上」才用的，不利於工程師理解。如果有些地方我講錯了，要不就是我忘了，要不就是我不會，當然也有可能是你不會。請提出來，正好探討一下。

參考文獻是：A FAST ELITIST MULTIOBJECTIVE GENETIC ALGORITHM:NSGA-II Kalyanmoy Deb

A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II ARAVIND SESHADRI

一、演算法的目的：用6個數，帶入2個方程（方程形式內容不用管，有固定的格式），生成2個結果。目的讓結果的和（有時是平方和）越小越好。舉個簡單的例子，在[0,1]之間隨機選數，a,b,c,d,e,f，實現 最小，當然是當a=b=c=d=e=f=0時。這是一個結果時，所以最終在圖像上你會看到結果縮成一個最優點，也就是a,b,c,d,e,f都縮成了一個最優點。如果是2個結果，則會形成我在圖中所示的最優曲線。如果是3個結果，我想是不是會變成最優平面（沒試過）

二、步驟：

1、從一個固定的範圍內隨機選100個數，100記為N。選出6列，6記做V，這樣有100x6的矩陣.

2、將這600個數歸一化為[0,1]區間之內。我個人覺得，其目的是到了後面，做一些數據組合的時候好算。結果像這樣

3、將這600個數，放進方程中，生成100x2個結果，2記做M。然後把數和結果組合在一起，生成100x8的矩陣，前6列是數據，後2列是結果。假設第一列的結果從上到下是x1,x2,x3...， 第二列結果是y1,y2,y3...

4、生成matlab裡面的一個cell，cell裡面有4個內容，分別為「甲乙丙丁」。

每一行的甲都裝一行的abcdefxy

每一行的乙放一個初始值=0的rank，將來這個是排名用的

每一行的丙放空矩陣，這個是用來放東西

每一行的丁放初始值為0的index，這個是用來生成rank排名用的

有一個基礎知識這裡得提一下，學名叫「帕累托曲線」。以本文為例，就是如何來選最優曲線。從圖上能看到，對於點A(x1,y1)和B(x2,y2)，如果存在x1<x2且y1<y2，則A要優於B。如果存在x1<x2和y1>y2（或者正好反過來），則兩個點沒關係，如A和C。但C和A點也不是在一個最優曲線上的，因為存在著D比C要優。接下來就是如何求一條條的最優曲線。例如UB1是最優的，因為沒有其他線能比他更靠近原點OB了，而UB2是次優的，因為有一條UB1比他更靠近原點。UB3是次次優，以此類推。我們的目的就是要生成這樣一條條的曲線，當然曲線可能是凸向原點的或者凹向原點。例如用ZDT4，就能生成

逐行的做循環去比對x和y，同時存在xi<xj和yi<yj的話（i，j是行數），則i這個點要比j這個點優秀。那麼就把j這個點index+1。因為j點差，所以每次發現一個比j好的點時，我們都要把j點index+1. 同時再把j所在的行數放進第i行的丙中。最終的結果就是

甲：每一行甲存進了一行的abcdefxy

乙：每一行乙目前=0

丙：每一行丙存進了——比該行的結果要差的那一行的的行數（第幾行）。所以是個數組

丁：每一行丁存進了比該行的結果要好的行的總數（一共多少行），所以是個數。

5、排序

丁=0的自然處於最優曲線上，因此它的乙應該是rank=1

然後把所有剩下的丁-1，出現0的放進rank2。再把剩下的丁-1，出現0的放進rank3，以此類推。

最終能得到每一行的rank

接下來要對處於同一個rank里的每一行排序。

對每一個(xi,yi)，都取和他相鄰的x(i-1),y(i-1)和x(i+1),y(i+1)，把他們的直線距離求出來，舉例大的優先順序就高。

最終搞大排行，先按rank排，再按距離去排。

下面的步驟都不是重點了，所以我簡單寫

6、調出優秀的

隨機挑2行，比較rank和距離，選好的。從100行裡面，調出50行，50記做NP

7、組合數

將這50行數的abcdefg重新組合。

例如可以將一行的所有數都乘上同一個變數p，形成新的一組數

或者可以將一行的所有數乘上變數p，加上另一行的所有數乘上變數q，形成新的一組數。

上述方法有很多更高級的變體，這部分還是看文檔比較好。我們做到了Simulated Binary Crossover and polynomial mutation，不知道還有沒有更好的演算法。

最終生成50行新數組，50記做NC

8、將所有的新數組NC放回到原本的100行中去。變成150行大矩陣。然後再排序，從中選出來100行最好的（不用隨機挑了，而是大排行），剩下的50行不要。

9、然後（6，7, 8）的循環做。

job done!