遺傳演算法流程圖
Ⅰ 如何利用遺傳演算法求解問題試舉例說明求解過程急急急！！！
遺傳演算法將目標函數轉換為適應度函數，評估，復制，交叉，變異種群中的個體，並從中選出適應性最強的個體，演算法的最優解就是這個個體。具體流程是：1.初始種群的產生。2.適應度函數的構造。3.選擇和繁殖。4.終止條件。
Ⅱ 螞蟻演算法的思想進化公式及遺傳演算法的演算法流程圖
遺傳演算法（Genetic Algorithm）是模擬達爾文生物進化論的自然選擇和遺傳學機理的生物進化過程的計算模型，是一種通過模擬自然進化過程搜索最優解的方法，它最初由美國Michigan大學J.Holland教授於1975年首先提出來的，並出版了頗有影響的專著《Adaptation in Natural and Artificial Systems》，GA這個名稱才逐漸為人所知，J.Holland教授所提出的GA通常為簡單遺傳演算法（SGA）。
Ⅲ 遺傳演算法的優缺點
優點：
1、遺傳演算法是以決策變數的編碼作為運算對象，可以直接對集合、序列、矩陣、樹、圖等結構對象進行操作。這樣的方式一方面有助於模擬生物的基因、染色體和遺傳進化的過程，方便遺傳操作運算元的運用。
另一方面也使得遺傳演算法具有廣泛的應用領域，如函數優化、生產調度、自動控制、圖像處理、機器學習、數據挖掘等領域。
2、遺傳演算法直接以目標函數值作為搜索信息。它僅僅使用適應度函數值來度量個體的優良程度，不涉及目標函數值求導求微分的過程。因為在現實中很多目標函數是很難求導的，甚至是不存在導數的，所以這一點也使得遺傳演算法顯示出高度的優越性。
3、遺傳演算法具有群體搜索的特性。它的搜索過程是從一個具有多個個體的初始群體P(0)開始的，一方面可以有效地避免搜索一些不必搜索的點。
另一方面由於傳統的單點搜索方法在對多峰分布的搜索空間進行搜索時很容易陷入局部某個單峰的極值點，而遺傳演算法的群體搜索特性卻可以避免這樣的問題，因而可以體現出遺傳演算法的並行化和較好的全局搜索性。
4、遺傳演算法基於概率規則，而不是確定性規則。這使得搜索更為靈活，參數對其搜索效果的影響也盡可能的小。
5、遺傳演算法具有可擴展性，易於與其他技術混合使用。以上幾點便是遺傳演算法作為優化演算法所具備的優點。
缺點：
1、遺傳演算法在進行編碼時容易出現不規范不準確的問題。
2、由於單一的遺傳演算法編碼不能全面將優化問題的約束表示出來，因此需要考慮對不可行解採用閾值，進而增加了工作量和求解時間。
3、遺傳演算法效率通常低於其他傳統的優化方法。
4、遺傳演算法容易出現過早收斂的問題。
(3)遺傳演算法流程圖擴展閱讀
遺傳演算法的機理相對復雜，在Matlab中已經由封裝好的工具箱命令，通過調用就能夠十分方便的使用遺傳演算法。
函數ga：[x, fval,reason]= ga(@fitnessfun, nvars, options)x是最優解，fval是最優值，@fitnessness是目標函數，nvars是自變數個數，options是其他屬性設置。系統默認求最小值，所以在求最大值時應在寫函數文檔時加負號。
為了設置options，需要用到下面這個函數：options=gaoptimset('PropertyName1', 'PropertyValue1', 'PropertyName2', 'PropertyValue2','PropertyName3', 'PropertyValue3', ...)通過這個函數就能夠實現對部分遺傳演算法的參數的設置。
Ⅳ 關於遺傳演算法
遺傳演算法（Genetic Algorithm，簡稱GA）是美國 Michigan大學的 John Golland提出的一種建立在自然選擇和群體遺傳學機理基礎上的隨機、迭代、進化、具有廣泛適用性的搜索方法。現在已被廣泛用於學習、優化、自適應等問題中。圖4-1 給出了 GA搜索過程的直觀描述。圖中曲線對應一個具有復雜搜索空間（多峰空間）的問題。縱坐標表示適應度函數（目標函數），其值越大相應的解越優。橫坐標表示搜索點。顯然，用解析方法求解該目標函數是困難的。採用 GA時，首先隨機挑選若干個搜索點，然後分別從這些搜索點開始並行搜索。在搜索過程中，僅靠適應度來反復指導和執行 GA 搜索。在經過若干代的進化後，搜索點後都具有較高的適應度並接近最優解。
一個簡單GA由復制、雜交和變異三個遺傳運算元組成：
圖4-2 常規遺傳演算法流程圖
Ⅳ C語言遺傳演算法在求解TSP問題 畢業論文+源代碼
目
錄
摘要
I
Abstract
II
引
言
1
第一章
基本遺傳演算法
2
1.1
遺傳演算法的產生及發展
3
1.2
基本原理
3
1.3
遺傳演算法的特點
3
1.4
基本遺傳演算法描述
5
1.5
遺傳演算法構造流程
6
第二章
遺傳演算法的實現技術
6
2.1
編碼方法
7
2.1.1
二進制編碼
7
2.1.2
格雷碼編碼
7
2.1.3
符點數編碼
8
2.1.4
參數編碼
8
2.2
適應度函數
10
2.3
選擇運算元
10
2.4
交叉運算元
10
2.4.1
單點交叉運算元
10
2.4.2
雙點交叉運算元
11
2.4.3
均勻交叉運算元
11
2.4.4
部分映射交叉
11
2.4.5
順序交叉
12
2.5
變異運算元
12
2.6
運行參數
12
2.7
約束條件的處理方法
13
2.8
遺傳演算法流程圖
14
第三章
遺傳演算法在TSP上的應用
15
3.1
TSP問題的建模與描述
15
3.2
對TSP的遺傳基因編碼方法
16
3.3
針對TSP的遺傳操作運算元
17
3.3.1
選擇運算元
17
3.3.1.1
輪盤賭選擇
17
3.3.1.2
最優保存策略選擇
17
3.3.2
交叉運算元
20
3.3.2.1
單點交叉
20
3.3.2.2
部分映射交叉
21
3.3.3
變異運算元
23
3.4
TSP的混和遺傳演算法
26
第四章
實例分析
27
4.1
測試數據
27
4.2
測試結果
27
4.3
結果分析
27
摘
要
TSP
(Traveling
Salesman
Problem)旅行商問題是一類典型的NP完全問題，遺傳演算法是解決NP問題的一種較理想的方法。文章首先介紹了基本遺傳演算法的基本原理、特點及其基本實現技術；接著針對TSP
問題，論述了遺傳演算法在編碼表示和遺傳運算元（包括選擇運算元、交叉運算元變異運算元這三種運算元）等方面的應用情況，分別指出幾種常用的編碼方法的優點和缺點，並且結合TSP的運行實例詳細分析了基本遺傳演算法的4個運行參數群體大小、遺傳演算法的終止進化代數、交叉概率、變異概率，對遺傳演算法的求解結果和求解效率的影響，經過多次的測試設定出了它們一組比較合理的取值。最後，簡單說明了混合遺傳演算法在求解TSP問題中的應用並對遺傳演算法解決TSP問題的前景提出了展望。
關鍵詞：TSP
遺傳演算法
遺傳運算元
編碼
@@@需要的話按我的名字找我吧
Ⅵ 求基於遺傳演算法的TPS的matlab程序，坐標手動輸入
1. 遺傳演算法實現過程
現實生活中很多問題都可以轉換為函數優化問題，所以本文將以函數優化問題作為背景，對GA的實現過程進行探討。大部分函數優化問題都可以寫成求最大值或者最小值的形式，為了不是一般性，我們可以將所有求最優值的情況都轉換成求最大值的形式，例如，求函數f(x)的最大值，
clip_image002
若是求函數f(x)的最小值，可以將其轉換成g(x)=-f(x)，然後求g(x)的最大值，
clip_image004
這里x可以是一個變數，也可是是一個由k個變數組成的向量, x=(x1, x2, …, xk)。每個xi, i=1,2,…,k, 其定義域為Di，Di=[ai, bi]。
一般規定f(x)在其定義域內只取正值，若不滿足，可以將其轉換成以下形式，
clip_image006
其中C是一個正常數。
1.1 編碼與解碼
要實現遺傳演算法首先需要弄清楚如何對求解問題進行編碼和解碼。對於函數優化問題，一般來說，有兩種編碼方式，一是實數編碼，一是二進制編碼，兩者各有優缺點，二進制編碼具有穩定性高、種群多樣性大等優點，但是需要的存儲空間大，需要解碼過程並且難以理解；而實數編碼直接用實數表示基因，容易理解並且不要解碼過程，但是容易過早收斂，從而陷入局部最優。本文以最常用的二進制編碼為例，說明遺傳編碼的過程。
從遺傳演算法求解的過程來看，需要處理好兩個空間的問題，一個是編碼空間，另一個是解空間，如下圖所示
clip_image007
從解空間到編碼空間的映射過程成為編碼過程；從編碼空間到解空間的映射過程成為解碼過程。下面就以求解一個簡單的一維函數f(x) = -(x-1)^2+4, x的取值范圍為[-1,3]最大值為例，來說明編碼及解碼過程。
編碼：
在編碼之前需要確定求解的精度，在這里，我們設定求解的精度為小數點後四位，即1e-4。這樣可以將每個自變數xi的解空間劃分為clip_image011個等分。以上面這個函數為例，即可以將x的解空間劃分為(3-(-1))*1e+4=40000個等分。使ni滿足clip_image013，這里ni表示使上式成立的最小整數，即表示自變數xi的基因串的長度。因為215<40000<216 ，這里ni取16。例如0000110110000101就表示一個解空間中的基因串。表示所有自變數x=(x1, x2, …, xk)的二進制串的總長度稱為一個染色體(Chromosome)的長度或者一個個體(Indivial)的長度，clip_image015。編碼過程一般在實現遺傳演算法之前需要指定。
解碼：
解碼即將編碼空間中的基因串翻譯成解空間中的自變數的實際值的過程。對於二進制編碼而言，每個二進制基因串都可以這樣翻譯成一個十進制實數值，clip_image017。例如基因串0000110110000101，可以翻譯為clip_image019，這里二進制基因串轉變成十進制是從左至右進行的。
1.2 初始化種群
在開始遺傳演算法迭代過程之前，需要對種群進行初始化。設種群大小為pop_size，每個染色體或個體的長度為chromo_size，種群的大小決定了種群的多樣性，而染色體的長度則是由前述的編碼過程決定的。一般隨機生成初始種群，但是如果知道種群的實際分布，也可以按照此分布來生成初始種群。假設生成的初始種群為(v1, v2, …, vpop_size)。
1.3 選擇操作
選擇操作即從前代種群中選擇個體到下一代種群的過程。一般根據個體適應度的分布來選擇個體。以初始種群(v1, v2, …, vpop_size)為例，假設每個個體的適應度為(fitness(v1), fitness(v2),…, fitness(vpop_size))，一般適應度可以按照解碼的過程進行計算。以輪盤賭的方式選擇個體，如下圖
clip_image020
隨機轉動一下輪盤，當輪盤停止轉動時，若指針指向某個個體，則該個體被選中。很明顯，具有較高適應度的個體比具有較低適應度的個體更有機會被選中。但是這種選擇具有隨機性，在選擇的過程中可能會丟失掉比較好的個體，所以可以使用精英機制，將前代最優個體直接選到下一代中。
輪盤賭選擇具體演算法如下（這里假定種群中個體是按照適應度從小到大進行排列的，如果不是，可以按照某種排序演算法對種群個體進行重排）：
Selection Algorithm
var pop, pop_new;/*pop為前代種群，pop_new為下一代種群*/
var fitness_value, fitness_table;/*fitness_value為種群的適應度，fitness_table為種群累積適應度*/
for i=1:pop_size
r = rand*fitness_table(pop_size);/*隨機生成一個隨機數，在0和總適應度之間，因為fitness_table(pop_size)為最後一個個體的累積適應度，即為總適應度*/
first = 1;
last = pop_size;
mid = round((last+first)/2);
idx = -1;
/*下面按照排中法選擇個體*/
while (first <= last) && (idx == -1)
if r > fitness_table(mid)
first = mid;
elseif r < fitness_table(mid)
last = mid;
else
idx = mid;
break;
end if
mid = round((last+first)/2);
if (last - first) == 1
idx = last;
break;
end if
end while
for j=1:chromo_size
pop_new(i,j)=pop(idx,j);
end for
end for
/*是否精英選擇*/
if elitism
p = pop_size-1;
else
p = pop_size;
end if
for i=1:p
for j=1:chromo_size
pop(i,j) = pop_new(i,j);/*若是精英選擇，則只將pop_new前pop_size-1個個體賦給pop，最後一個為前代最優個體保留*/
end for
end for
1.3 交叉操作
交叉操作是對任意兩個個體進行的（在這里我們實現的演算法是直接對相鄰的兩個個體進行的）。隨機選擇兩個個體，如下圖所示
clip_image001
然後隨機生成一個實數0<=r<=1, 如果r<cross_rate， 0<cross_rate<1為交叉概率，則對這兩個個體進行交叉，否則則不進行。如果需要進行交叉，再隨機選擇交叉位置(rand*chromo_size)，如果等於0或者1，將不進行交叉。否則將交叉位置以後的二進制串進行對換（包括交叉位置）。（注意：有時候還可以進行多點交叉，但是這里只討論單點交叉的情況）
單點交叉具體演算法如下：
Crossover algorithm
for i=1:2:pop_size
if(rand < cross_rate)/*cross_rate為交叉概率*/
cross_pos = round(rand * chromo_size);/*交叉位置*/
if or (cross_pos == 0, cross_pos == 1)
continue;/*若交叉位置為0或1，則不進行交叉*/
end if
for j=cross_pos:chromo_size
pop(i,j)<->pop(i+1,j);/*交換*/
end for
end if
end for
1.4 變異操作
變異操作是對單個個體進行的。首先生成一個隨機實數0<=r<=1, 如果r<mutate_rate，則對此個體進行變異操作， 0<mutate_rate<1為變異概率，一般為一個比較小的實數。對每一個個體，進行變異操作，如下圖所示
clip_image001[4]
如個體需要進行變異操作，首先需要確定變異位置(rand*chromo_size)，若為0則不進行變異，否則則對該位置的二進制數字進行變異：1變成0, 0變成1.（當然也可以選擇多點進行變異）
單點變異的具體演算法描述如下：
Mutation algorithm
for i=1:pop_size
if rand < mutate_rate/*mutate_rate為變異概率*/
mutate_pos = round(rand*chromo_size);/*變異位置*/
if mutate_pos == 0
continue;/*若變異位置為0，則不進行變異*/
end if
pop(i,mutate_pos) = 1 - pop(i, mutate_pos);/*將變異位置上的數字至反*/
end if
end for
1.5 遺傳演算法流程
遺傳演算法計算流程圖如下圖所示
clip_image001[6]
1.6 MATLAB程序實現
初始化：
%初始化種群
%pop_size: 種群大小
%chromo_size: 染色體長度
function initilize(pop_size, chromo_size)
global pop;
for i=1:pop_size
for j=1:chromo_size
pop(i,j) = round(rand);
end
end
clear i;
clear j;
計算適應度：（該函數應該根據具體問題進行修改，這里優化的函數是前述的一維函數）
%計算種群個體適應度，對不同的優化目標，此處需要改寫
%pop_size: 種群大小
%chromo_size: 染色體長度
function fitness(pop_size, chromo_size)
global fitness_value;
global pop;
global G;
for i=1:pop_size
fitness_value(i) = 0.;
end
for i=1:pop_size
for j=1:chromo_size
if pop(i,j) == 1
fitness_value(i) = fitness_value(i)+2^(j-1);
end
end
fitness_value(i) = -1+fitness_value(i)*(3.-(-1.))/(2^chromo_size-1);
fitness_value(i) = -(fitness_value(i)-1).^2+4;
end
clear i;
clear j;
對個體按照適應度大小進行排序：
%對個體按適應度大小進行排序，並且保存最佳個體
%pop_size: 種群大小
%chromo_size: 染色體長度
function rank(pop_size, chromo_size)
global fitness_value;
global fitness_table;
global fitness_avg;
global best_fitness;
global best_indivial;
global best_generation;
global pop;
global G;
for i=1:pop_size
fitness_table(i) = 0.;
end
min = 1;
temp = 1;
temp1(chromo_size)=0;
for i=1:pop_size
min = i;
for j = i+1:pop_size
if fitness_value(j)<fitness_value(min);
min = j;
end
end
if min~=i
temp = fitness_value(i);
fitness_value(i) = fitness_value(min);
fitness_value(min) = temp;
for k = 1:chromo_size
temp1(k) = pop(i,k);
pop(i,k) = pop(min,k);
pop(min,k) = temp1(k);
end
end
end
for i=1:pop_size
if i==1
fitness_table(i) = fitness_table(i) + fitness_value(i);
else
fitness_table(i) = fitness_table(i-1) + fitness_value(i);
end
end
fitness_table
fitness_avg(G) = fitness_table(pop_size)/pop_size;
if fitness_value(pop_size) > best_fitness
best_fitness = fitness_value(pop_size);
best_generation = G;
for j=1:chromo_size
best_indivial(j) = pop(pop_size,j);
end
end
clear i;
clear j;
clear k;
clear min;
clear temp;
clear temp1;
選擇操作：
%輪盤賭選擇操作
%pop_size: 種群大小
%chromo_size: 染色體長度
%cross_rate: 是否精英選擇
function selection(pop_size, chromo_size, elitism)
global pop;
global fitness_table;
for i=1:pop_size
r = rand * fitness_table(pop_size);
first = 1;
last = pop_size;
mid = round((last+first)/2);
idx = -1;
while (first <= last) && (idx == -1)
if r > fitness_table(mid)
first = mid;
elseif r < fitness_table(mid)
last = mid;
else
idx = mid;
break;
end
mid = round((last+first)/2);
if (last - first) == 1
idx = last;
break;
end
end
for j=1:chromo_size
pop_new(i,j)=pop(idx,j);
end
end
if elitism
p = pop_size-1;
else
p = pop_size;
end
for i=1:p
for j=1:chromo_size
pop(i,j) = pop_new(i,j);
end
end
clear i;
clear j;
clear pop_new;
clear first;
clear last;
clear idx;
clear mid;
交叉操作：
%單點交叉操作
%pop_size: 種群大小
%chromo_size: 染色體長度
%cross_rate: 交叉概率
function crossover(pop_size, chromo_size, cross_rate)
global pop;
for i=1:2:pop_size
if(rand < cross_rate)
cross_pos = round(rand * chromo_size);
if or (cross_pos == 0, cross_pos == 1)
continue;
end
for j=cross_pos:chromo_size
temp = pop(i,j);
pop(i,j) = pop(i+1,j);
pop(i+1,j) = temp;
end
end
end
clear i;
clear j;
clear temp;
clear cross_pos;
變異操作：
%單點變異操作
%pop_size: 種群大小
%chromo_size: 染色體長度
%cross_rate: 變異概率
function mutation(pop_size, chromo_size, mutate_rate)
global pop;
for i=1:pop_size
if rand < mutate_rate
mutate_pos = round(rand*chromo_size);
if mutate_pos == 0
continue;
end
pop(i,mutate_pos) = 1 - pop(i, mutate_pos);
end
end
clear i;
clear mutate_pos;
列印演算法迭代過程：
%列印演算法迭代過程
%generation_size: 迭代次數
function plotGA(generation_size)
global fitness_avg;
x = 1:1:generation_size;
y = fitness_avg;
plot(x,y)
演算法主函數：
%遺傳演算法主函數
%pop_size: 輸入種群大小
%chromo_size: 輸入染色體長度
%generation_size: 輸入迭代次數
%cross_rate: 輸入交叉概率
%cross_rate: 輸入變異概率
%elitism: 輸入是否精英選擇
%m: 輸出最佳個體
%n: 輸出最佳適應度
%p: 輸出最佳個體出現代
%q: 輸出最佳個體自變數值
function [m,n,p,q] = GeneticAlgorithm(pop_size, chromo_size, generation_size, cross_rate, mutate_rate, elitism)
global G ; %當前代
global fitness_value;%當前代適應度矩陣
global best_fitness;%歷代最佳適應值
global fitness_avg;%歷代平均適應值矩陣
global best_indivial;%歷代最佳個體
global best_generation;%最佳個體出現代
fitness_avg = zeros(generation_size,1);
disp "hhee"
fitness_value(pop_size) = 0.;
best_fitness = 0.;
best_generation = 0;
initilize(pop_size, chromo_size);%初始化
for G=1:generation_size
fitness(pop_size, chromo_size); %計算適應度
rank(pop_size, chromo_size); %對個體按適應度大小進行排序
selection(pop_size, chromo_size, elitism);%選擇操作
crossover(pop_size, chromo_size, cross_rate);%交叉操作
mutation(pop_size, chromo_size, mutate_rate);%變異操作
end
plotGA(generation_size);%列印演算法迭代過程
m = best_indivial;%獲得最佳個體
n = best_fitness;%獲得最佳適應度
p = best_generation;%獲得最佳個體出現代
%獲得最佳個體變數值，對不同的優化目標，此處需要改寫
q = 0.;
for j=1:chromo_size
if best_indivial(j) == 1
q = q+2^(j-1);
end
end
q = -1+q*(3.-(-1.))/(2^chromo_size-1);
clear i;
clear j;
2. 案例研究
對上一節中的函數進行優化，設置遺傳演算法相關參數，程序如下
function run_ga()
elitism = true;%選擇精英操作
pop_size = 20;%種群大小
chromo_size = 16;%染色體大小
generation_size = 200;%迭代次數
cross_rate = 0.6;%交叉概率
mutate_rate = 0.01;%變異概率
[m,n,p,q] = GeneticAlgorithm(pop_size, chromo_size, generation_size, cross_rate, mutate_rate,elitism);
disp "最優個體"
m
disp "最優適應度"
n
disp "最優個體對應自變數值"
q
disp "得到最優結果的代數"
p
clear;
結果如下：
"最優個體"
m =
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0
"最優適應度"
n =
4.0000
"最優個體對應自變數值"
q =
1.0000
"得到最優結果的代數"
p =
74
此結果非常准確。
Ⅶ 利用遺傳演算法求解區間[0, 31]上的二次函數y=x 2次方 的最大值
靠 你也太懶了
Ⅷ 遺傳演算法 簡單程序應用
import java.awt.BorderLayout;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import javax.swing.JButton;
import javax.swing.JFrame;
import javax.swing.JLabel;
import javax.swing.JPanel;
import javax.swing.JScrollPane;
import javax.swing.JTextArea;
import javax.swing.JTextField;
class Best {
public int generations; //最佳適應值代號
public String str; //最佳染色體
public double fitness; //最佳適應值
}
public class SGAFrame extends JFrame {
private JTextArea textArea;
private String str = "";
private Best best = null; //最佳染色體
private String[] ipop = new String[10]; //染色體
private int gernation = 0; //染色體代號
public static final int GENE = 22; //基因數
/**
* Launch the application
* @param args
*/
public static void main(String args[]) {
try {
SGAFrame frame = new SGAFrame();
frame.setVisible(true);
} catch (Exception e) {
e.printStackTrace();
}
}
/**
* Create the frame
*/
public SGAFrame() {
super();
this.ipop = inialPops();
getContentPane().setLayout(null);
setBounds(100, 100, 461, 277);
setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
final JLabel label = new JLabel();
label.setText("X的區間:");
label.setBounds(23, 10, 88, 15);
getContentPane().add(label);
final JLabel label_1 = new JLabel();
label_1.setText("[-255,255]");
label_1.setBounds(92, 10, 84, 15);
getContentPane().add(label_1);
final JButton button = new JButton();
button.addActionListener(new ActionListener() {
public void actionPerformed(final ActionEvent e) {
SGAFrame s = new SGAFrame();
str = str + s.process() + "\n";
textArea.setText(str);
}
});
button.setText("求最小值");
button.setBounds(323, 27, 99, 23);
getContentPane().add(button);
final JLabel label_2 = new JLabel();
label_2.setText("利用標准遺傳演算法求解函數f(x)=(x-5)*(x-5)的最小值:");
label_2.setBounds(23, 31, 318, 15);
getContentPane().add(label_2);
final JPanel panel = new JPanel();
panel.setLayout(new BorderLayout());
panel.setBounds(23, 65, 399, 164);
getContentPane().add(panel);
final JScrollPane scrollPane = new JScrollPane();
panel.add(scrollPane, BorderLayout.CENTER);
textArea = new JTextArea();
scrollPane.setViewportView(textArea);
//
}
/**
* 初始化一條染色體（用二進制字元串表示）
* @return 一條染色體
*/
private String inialPop() {
String res = "";
for (int i = 0; i < GENE; i++) {
if (Math.random() > 0.5) {
res += "0";
} else {
res += "1";
}
}
return res;
}
/**
* 初始化一組染色體
* @return 染色體組
*/
private String[] inialPops() {
String[] ipop = new String[10];
for (int i = 0; i < 10; i++) {
ipop[i] = inialPop();
}
return ipop;
}
/**
* 將染色體轉換成x的值
* @param str 染色體
* @return 染色體的適應值
*/
private double calculatefitnessvalue(String str) {
int b = Integer.parseInt(str, 2);
//String str1 = "" + "/n";
double x = -255 + b * (255 - (-255)) / (Math.pow(2, GENE) - 1);
//System.out.println("X = " + x);
double fitness = -(x - 5) * (x - 5);
//System.out.println("f(x)=" + fitness);
//str1 = str1 + "X=" + x + "/n"
//+ "f(x)=" + "fitness" + "/n";
//textArea.setText(str1);
return fitness;
}
/**
* 計算群體上每個個體的適應度值;
* 按由個體適應度值所決定的某個規則選擇將進入下一代的個體;
*/
private void select() {
double evals[] = new double[10]; // 所有染色體適應值
double p[] = new double[10]; // 各染色體選擇概率
double q[] = new double[10]; // 累計概率
double F = 0; // 累計適應值總和
for (int i = 0; i < 10; i++) {
evals[i] = calculatefitnessvalue(ipop[i]);
if (best == null) {
best = new Best();
best.fitness = evals[i];
best.generations = 0;
best.str = ipop[i];
} else {
if (evals[i] > best.fitness) // 最好的記錄下來
{
best.fitness = evals[i];
best.generations = gernation;
best.str = ipop[i];
}
}
F = F + evals[i]; // 所有染色體適應值總和
}
for (int i = 0; i < 10; i++) {
p[i] = evals[i] / F;
if (i == 0)
q[i] = p[i];
else {
q[i] = q[i - 1] + p[i];
}
}
for (int i = 0; i < 10; i++) {
double r = Math.random();
if (r <= q[0]) {
ipop[i] = ipop[0];
} else {
for (int j = 1; j < 10; j++) {
if (r < q[j]) {
ipop[i] = ipop[j];
break;
}
}
}
}
}
/**
* 交叉操作
* 交叉率為25%，平均為25%的染色體進行交叉
*/
private void cross() {
String temp1, temp2;
for (int i = 0; i < 10; i++) {
if (Math.random() < 0.25) {
double r = Math.random();
int pos = (int) (Math.round(r * 1000)) % GENE;
if (pos == 0) {
pos = 1;
}
temp1 = ipop[i].substring(0, pos)
+ ipop[(i + 1) % 10].substring(pos);
temp2 = ipop[(i + 1) % 10].substring(0, pos)
+ ipop[i].substring(pos);
ipop[i] = temp1;
ipop[(i + 1) / 10] = temp2;
}
}
}
/**
* 基因突變操作
* 1%基因變異m*pop_size 共180個基因，為了使每個基因都有相同機會發生變異,
* 需要產生[1--180]上均勻分布的
*/
private void mutation() {
for (int i = 0; i < 4; i++) {
int num = (int) (Math.random() * GENE * 10 + 1);
int chromosomeNum = (int) (num / GENE) + 1; // 染色體號
int mutationNum = num - (chromosomeNum - 1) * GENE; // 基因號
if (mutationNum == 0)
mutationNum = 1;
chromosomeNum = chromosomeNum - 1;
if (chromosomeNum >= 10)
chromosomeNum = 9;
//System.out.println("變異前" + ipop[chromosomeNum]);
String temp;
if (ipop[chromosomeNum].charAt(mutationNum - 1) == '0') {
if (mutationNum == 1) {
temp = "1" + ipop[chromosomeNum].substring
(mutationNum);
} else {
if (mutationNum != GENE) {
temp = ipop[chromosomeNum].substring(0, mutationNum -
1) + "1" + ipop
[chromosomeNum].substring(mutationNum);
} else {
temp = ipop[chromosomeNum].substring(0, mutationNum -
1) + "1";
}
}
} else {
if (mutationNum == 1) {
temp = "0" + ipop[chromosomeNum].substring
(mutationNum);
} else {
if (mutationNum != GENE) {
temp = ipop[chromosomeNum].substring(0, mutationNum -
1) + "0" + ipop
[chromosomeNum].substring(mutationNum);
} else {
temp = ipop[chromosomeNum].substring(0, mutationNum -
1) + "1";
}
}
}
ipop[chromosomeNum] = temp;
//System.out.println("變異後" + ipop[chromosomeNum]);
}
}
/**
* 執行遺傳演算法
*/
public String process() {
String str = "";
for (int i = 0; i < 10000; i++) {
this.select();
this.cross();
this.mutation();
gernation = i;
}
str = "最小值" + best.fitness + ",第" + best.generations + "個染色體";
return str;
}
}
Ⅸ 進化演算法的基本步驟
進化計算是基於自然選擇和自然遺傳等生物進化機制的一種搜索演算法。與普通的搜索方法一樣，進化計算也是一種迭代演算法，不同的是進化計算在最優解的搜索過程中，一般是從原問題的一組解出發改進到另一組較好的解，再從這組改進的解出發進一步改進。而且在進化問題中，要求當原問題的優化模型建立後，還必須對原問題的解進行編碼。進化計算在搜索過程中利用結構化和隨機性的信息，使最滿足目標的決策獲得最大的生存可能，是一種概率型的演算法。
一般來說，進化計算的求解包括以下幾個步驟：給定一組初始解；評價當前這組解的性能；從當前這組解中選擇一定數量的解作為迭代後的解的基礎；再對其進行操作，得到迭代後的解；若這些解滿足要求則停止，否則將這些迭代得到的解作為當前解重新操作。
以遺傳演算法為例，其工作步驟可概括為：
（1） 對工作對象——字元串用二進制的0/1或其它進制字元編碼 。
（2） 根據字元串的長度L，隨即產生L個字元組成初始個體。
（3） 計算適應度。適應度是衡量個體優劣的標志，通常是所研究問題的目標函數。
（4） 通過復制，將優良個體插入下一代新群體中，體現「優勝劣汰」的原則。
（5） 交換字元，產生新個體。交換點的位置是隨機決定的
（6） 對某個字元進行補運算，將字元1變為0，或將0變為1，這是產生新個體的另一種方法，突變字元的位置也是隨機決定的。
（7） 遺傳演算法是一個反復迭代的過程，每次迭代期間，要執行適應度計算、復制、交換、突變等操作，直至滿足終止條件。
將其用形式化語言表達，則為：假設α∈I記為個體，I記為個體空間。適應度函數記為Φ：I→R。在第t代，群體P(t)={a1(t),a2(t)，…，an(t)}經過復制r(reproction)、交換c(crossover)及突變m(mutation)轉換成下一代群體。這里r、c、m均指宏運算元，把舊群體變換為新群體。L：I→{True, Flase}記為終止准則。利用上述符號，遺傳演算法可描述為：
t=0
initialize P(0):={ a1(0),a2(0)，…，an(0)};
while(l(P(t))≠True) do
evaluate P(t):{ Φ(a1(t)), Φ(a2(t))，…，Φ(an(t))};
reproction: P′(t):=r(P(t));
crossover: P″(t):=c(P′(t));
mutation: P(t+1):= m(P″(t));
t=t+1;
end