使用遺傳算法求解函數(shù)最大值

1、使用遺傳算法求解函數(shù)最大值題目使用遺傳算法求解函數(shù)fx,y=x*sin6*y+y*cos(8*x)在x1, 2及y1, 2的最大值。解答算法使用遺傳算法進行求解，篇末所附源代碼中帶有算法的詳細注釋。算法中涉及不同的參數(shù)，參數(shù)的取值需要根據(jù)實際情況進行設(shè)定，下面運行時將給出不同參數(shù)的結(jié)果對比。定義整體算法的結(jié)束條件為，當種群進化次數(shù)達到maxGeneration時停止，此時種群中的最優(yōu)解即作為算法的最終輸出。設(shè)種群規(guī)模為N，首先是隨機產(chǎn)生N個個體，實驗中定義了類型Chromosome表示一個個體，并且在默認構(gòu)造函數(shù)中即進行了隨機的操作。然后程序進行若干次的迭代，在每次迭代過程中，進行選擇、交叉及

2、變異三個操作。一 選擇操作首先計算當前每個個體的適應度函數(shù)值，這里的適應度函數(shù)即為所要求的優(yōu)化函數(shù)，然后歸一化求得每個個體選中的概率，然后用輪盤賭的方法以允許重復的方式選擇選擇N個個體，即為選擇之后的群體。但實驗時發(fā)現(xiàn)結(jié)果不好，經(jīng)過仔細研究之后發(fā)現(xiàn)，這里在x、y取某些值的時候，目標函數(shù)計算出來的適應值可能會出現(xiàn)負值，這時如果按照把每個個體的適應值除以適應值的總和的進行歸一化的話會出現(xiàn)問題，因為個體可能出現(xiàn)負值，總和也可能出現(xiàn)負值，如果歸一化的時候除以了一個負值，選擇時就會選擇一些不良的個體，對實驗結(jié)果造成影響。對于這個問題，我把適應度函數(shù)定為目標函數(shù)的函數(shù)值加一個正數(shù)，保證得到的適應值為正數(shù)，

3、然后再進行一般的歸一化和選擇的操作。實驗結(jié)果表明，之前的實驗結(jié)果很不穩(wěn)定，修正后的結(jié)果比較穩(wěn)定，趨于最大值。二 交叉操作首先是根據(jù)交叉概率probCross選擇要交叉的個體進行交叉。這里根據(jù)交叉參數(shù)crossnum進行多點交叉，首先隨機生成交叉點位置，允許交叉點重合，兩個重合的交叉點效果互相抵消，相當于沒有交叉點，然后根據(jù)交叉點進行交叉操作，得到新的個體。三 變異操作首先是根據(jù)變異概率probMutation選擇要變異的個體。變異時先隨機生成變異的位置，然后把改位的01值翻轉(zhuǎn)。經(jīng)過一定的進化之后得到最終種群，從中選擇最優(yōu)的個體即可得到最終的結(jié)果。運行結(jié)果借助matlab軟件，我們可以知道該函數(shù)

4、在該定義域下的圖像為:以下設(shè)置不同的參數(shù)值進行對比試驗：表1 不同參數(shù)的對比實驗NlencrossnummaxGenerationprobCrossprobMutate實驗一實驗二11010410000.850.152.2.25010450000.850.152.2.320020450000.850.152.2.4200304100000.850.152.2.5200305100000.80.22.2.63004040.850.152.2.以上我們主要對種群規(guī)模N，個體染色體長度len，迭代次數(shù)maxGeneration進行比較?？梢钥闯?，隨著種群規(guī)模的增大，染色體長度的增長，迭代次數(shù)的增加，

5、算法得到的結(jié)果越來越精確。當參數(shù)規(guī)模達到一定程度時，再增加參數(shù)的值會明顯地增加程序運行時間，但卻不一定能明顯改善解的質(zhì)量，反而可能因為一些隨機因數(shù)而產(chǎn)生質(zhì)量更差的解，如第6組實驗一所示。同時也大概比較了一下多點交叉的交叉點個數(shù)crossnum，交叉概率probCross，變異概率probMutate等參數(shù)，由于參數(shù)太多，這里沒有一一進行控制變量的比較。大致估算可知，交叉概率及交叉點的個數(shù)影響交叉操作產(chǎn)生新個體的質(zhì)量，過多的交叉及變化過大的交叉可能會產(chǎn)生不好的結(jié)果，而過多的變異也應該會造成算法的不穩(wěn)定。下面給出以上幾個實驗結(jié)果的實驗截圖，其中到現(xiàn)在為止結(jié)果最好的一個為：其余若干個為：算法改進以上

6、實驗得到的最好結(jié)果仍然是差強人意，這里對算法做一個小的優(yōu)化，即添加防止種群退化的操作。記錄當前位置所得到的最優(yōu)值及對應的個體，每次更新種群之后，計算新種群的最優(yōu)值，如果最優(yōu)值變差了，則把之前較優(yōu)的個體替換進新種群，防止種群退化；否則更新最優(yōu)值。改進之后的效果如下所示，顯然比之前更優(yōu)，且實驗結(jié)果顯示對于前面對比實驗中的參數(shù)值，這里只需要較小的參數(shù)（如迭代次數(shù)只需2000次）值即可穩(wěn)定收斂到此最大值，可知改進非常有效。增加輸出精度之后為，于是得到最優(yōu)的結(jié)果為2.2841源代碼改進后的源代碼如下：#include #include #include #include #include using n

7、amespace std;/ 程序欲分配內(nèi)存的數(shù)組大小const int mxn = 10000;/ 最大的種群規(guī)模const int mxlen = 1000;/ 最大的染色體長度/ 遺傳算法關(guān)鍵參數(shù)const int N = 200;/ 種群的個體數(shù)const int len = 30;/ 每個個體的染色體的長度，x和y各占一半const int crossnum = 4;/ 交叉操作時多點交叉的交叉點個數(shù)const int maxGeneration = 2000;/ 最大進化代數(shù)const double probCross = 0.85;/ 交叉概率const double probM

8、utation = 0.15;/ 變異概率/ 個體的染色體類class Chromosome public:bool gmxlen;/ 二進制編碼的編碼數(shù)組Chromosome()/ 默認構(gòu)造函數(shù)，構(gòu)造隨機染色體for (int i = 0; i len; i+)gi = rand() % 2;Chromosome(const Chromosome& c)/ 拷貝構(gòu)造函數(shù)，進行深復制for (int i = 0; i len; i+)gi = c.gi;void operator=(const Chromosome& c)/ 重載=號，進行深復制for (int i = 0; i = len

9、/ 2; i-)tem += c.gi * q, q = q * 2;y = 1 + (2 - 1) / num * tem;tem = 0;for (int i = len / 2 - 1, q = 1; i = 0; i-)tem += c.gi * q, q = q * 2;x = 1 + (2 - 1) / num * tem;/ 適應度函數(shù)，為避免負值，把目標函數(shù)加一個正數(shù)double fitness(const Chromosome& c)double x, y;decode(c, x, y);return f(x, y) + 5;/ 輔助函數(shù)，生成0-1之間的隨機小數(shù)double

10、 inline random01()return rand() % 10000 / 10000.0;/ 選擇操作void select(Chromosome groupmxn)/ 計算每個個體的選擇概率double fitnessValmxn;for (int i = 0; i N; i+)fitnessVali = fitness(groupi);double sum = 0;for (int i = 0; i N; i+)sum += fitnessVali;double probmxn;for (int i = 0; i N; i+)probi = fitnessVali / sum;/

11、 隨機選擇N個個體組成新種群int selectIdmxn;for (int i = 1; i N; i+)probi += probi-1;for (int i = 0; i N; i+)/ 使用輪盤賭算法選擇個體double randNum = random01();int j;for (j = 0; j N - 1; j+)if (randNum probj)selectIdi = j;break;if (j = N - 1)selectIdi = j;/ 把種群更新為新選擇的個體集合for (int i = 0; i N; i+)temGroupi = groupi;for (int

12、i = 0; i N; i+)groupi = temGroupselectIdi;/ 交叉操作，使用多點交叉void crossover(Chromosome& c1, Chromosome& c2)/ 生成交叉點位置，并排序int crosspointmxn;for(int i = 0; i crossnum; i+)crosspointi = rand() % len;sort(crosspoint, crosspoint+crossnum);/ 進行交叉bool flag = 0;for(int i = 0, j = 0; i len; i+)if(!flag)swap(c1.gi,

13、c2.gi);if (i = crosspointj)/ 如果若干個交叉點重合，則效果疊加/ 偶數(shù)個交叉點效果相當于沒有交叉點while(j crossnum & i = crosspointj)j+;flag = !flag;/ 變異操作void mutate(Chromosome& c)/ 隨機選擇一位進行翻轉(zhuǎn)int i = rand() % len;c.gi = !c.gi;/ 獲取種群最優(yōu)個體int getOptimal(Chromosome groupmxn, double& x, double& y, double& val)/ 計算適應值，遍歷得到最優(yōu)值并進行解碼double f

14、itnessValmxn;for (int i = 0; i N; i+)fitnessVali = fitness(groupi);int id = 0;for (int i = 1; i fitnessValid)id = i;decode(groupid, x, y);val = f(x, y);return id;/ 遺傳算法總代碼void GA(double& x, double& y, double& val)/ 初始化種群for (int i = 0; i N; i+)groupi = Chromosome();/ bestC = groupgetOptimal(group, x

15、, y, bestval);/ 控制進化代數(shù)for (int g = 0; g maxGeneration; g+)/ 選擇操作select(group);/ 根據(jù)交叉概率進行交叉for (int i = 0, pre = -1; i N; i+)if (random01() probCross)if (pre = -1)pre = i;elsecrossover(grouppre, groupi);pre = -1;/ 根據(jù)變異概率進行變異for (int i = 0; i N; i+)if (random01() probMutation)mutate(groupi);/ 防止種群退化double temval;int bestId = getOptimal(group, x, y, temval);if (temval bestval)/ 如果新種群的最優(yōu)值變差，把較優(yōu)的個體替換進新種群groupbestId