遺傳算法也成進化算法，該算法受到達爾文進化論的啟發提出的一種啟發式搜索算法。
進化論
種群
生物的進化以群體的形式進行，這樣的一個群體稱為種群。
個體
組成種群的單個生物。
基因
一個遺傳因子。
染色體
包含一組的基因。
生存競爭，適者生存
對環境適應度高的個體參與繁殖的機會比較多，後代就會越來越多。適應度低的個體參與繁殖的機會比較少，後代就會越來越少。
遺傳與變異
新個體會遺傳父母雙方各一部分的基因，同時有一定的概率發生基因變異。
綜述
繁殖過程，會發生基因交叉，基因突變 ，適應度低的個體會被逐步淘汰，而適應度高的個體會越來越多。那麼經過N代的自然選擇後，保存下來的個體都是適應度很高的，其中很可能包含史上產生的適應度最高的那個個體。
遺傳算法
遺傳算法將要解決的問題模擬成一個生物進化的過程，通過複製、交叉、突變等操作產生下一代的解，並逐步淘汰掉適應度函數值低的解，增加適應度函數值高的解。這樣進化N代後就很有可能會進化出適應度函數值很高的個體。下面以0-1揹包問題來講解下遺傳算法的步驟
編碼需要將問題的解編碼成字符串的形式才能使用遺傳算法。最簡單的一種編碼方式是二進制編碼，即將問題的解編碼成二進制位數組的形式。例如，問題的解是整數，那麼可以將其編碼成二進制位數組的形式。將0-1字符串作為0-1揹包問題的解就屬於二進制編碼。
選擇選擇一些染色體來產生下一代。一種常用的選擇策略是比例選擇。也就是輪盤賭算法，如下圖所示
群體中每一染色體指定餅圖中一個小塊。塊的大小與染色體的適應性分數成比例，適應性分數愈高，它在餅圖中對應的小塊所佔面積也愈大。為了選取一個染色體，要做的就是旋轉這個輪子，直到輪盤停止時，看指針停止在哪一塊上，就選中與它對應的那個染色體。
若產生隨機數為0.81，則6號個體被選中。
<code>// 輪盤賭代碼示意
/*
* 按設定的概率，隨機選中一個個體
* P[i]表示第i個個體被選中的概率
*/
int RWS()
{
m =0;
r =Random(0,1); //r為0至1的隨機數
for(i=1;i<=N; i++)
{
/* 產生的隨機數在m~m+P[i]間則認為選中了i
* 因此i被選中的概率是P[i]
*/
m = m + P[i];
if(r<=m) return i;
}
}
/<code>交叉
2條染色體交換部分基因，來構造下一代的2條新的染色體。父輩染色體00000|011100000000|1000011100|000001111110|00101隨機交叉遺傳00000|000001111110|1000011100|011100000000|00101
變異新產生的染色體中的基因會以一定的概率出錯，稱為變異。變異前: 000001110000000010000變異後: 000001110000100010000我們認為染色體交叉的概率為Pc，染色體變異的概率為Pm。適應度函數:用於評價某個染色體的適應度，用f(x)表示。有時需要區分染色體的適應度函數與問題的目標函數。例如：0-1揹包問題的目標函數是所取得物品價值，但將物品價值作為染色體的適應度函數可能並不一定適合。適應度函數與目標函數是正相關的，可對目標函數作一些變形來得到適應度函數。
遺傳算法核心表示
<code>/**
* 交叉遺傳的概率Pc
* 遺傳變異的概率Pm
* 種群規模M
* 終止進化代數G
* 當產生出一個個體的適應度超過給定Tf,則終止進化
*/
步驟1
初始化產生 Pc Pm M G Tf參數並隨機生成第一代種群population,簡稱P1
初始化P = P1
do {
\t計算P中每一個個體的適應度F(i)
\t初始化空種群newP
\tdo {
\t\t根據適應度比例選擇算法選擇出2個個體
\t\tif (rnd1 < Pc) {
\t\t\t進行交叉操作
\t\t}
\t\tif (rnd2 < Pm) { 進行變異操作 } 將兩個操作後的個體放進newP中,即產生的新個體進入新的種群 } until (M個個體被創建) P = newP } until(任何染色體滿足適應度或者繁殖代數>G)
/<code>
在這裡我們看到了，這個隨機選擇以及產生後代的方式需要斟酌，如果設定的不好，那麼很有可能這個種族最後就滅絕了，算個說話也就是我們沒有得到我們的解。大自然這裡還有一個規律叫做：物競天擇 適者生存在我們這裡也需要對算法進行優化：擇優 為了防止進化過程中產生的最優解被交叉和變異所破壞，可以將每一代中的最優解原封不動的複製到下一代中。
具體實例
求 f(x1, x2) = x1^3 + x2^2 + (x1 * (x1 – x2))的最大值，其中x1屬於{-5, -3, 1, 3, 5}, x2屬於{0, 2, 4}當然這個題目解法很多，窮舉方法也非常的迅速。這個例子為了更加透徹的理解遺傳算法。步驟1 編碼我們此處定義隱射關係為[[0] = -5,[1] = -3,[2] = 0,[3] = 1,[4] = 2,[5] = 3,[6] = 4,[7] = 5]8可以用4位二進制表示,而x1和x2則用8位二進制即可完成驗證比如{0110|0110}則表示[x1 = 3, x2 = 4]步驟2 生成種群,注意生成種群的數量以及作用域關係，寫一段js代碼來進行測試
生成個體
步驟3 隨機選擇父代進行通過交叉和變異生成子代（選出適應度較高的進行）
產生多代並得到最後結果
150
代碼示意，因為沒有變異以及編碼是否可以有更好的辦法，所以只為顯示整體過程
<code>console.log("遺傳算法");
var everyone = [];
var number = 200;
function in_array(search, array){
for(var i in array){
if(array[i]==search){
return true;
}
}
return false;
}
var genChromosome = function(scope) {
var timestamp = new Date().getTime();
var index = Math.ceil(Math.random() * timestamp) % scope.length;
var chromosome = scope[index].toString(2);
while (chromosome.length < 4) {
chromosome = "0" + chromosome;
}
return chromosome;
}
// 計算每個的適應度
var calFitness = function(omo) {
var codes = [-5, -3, 0, 1, 2, 3, 4, 5];
var arr1 = [-5, -3, 1, 3, 5];
var arr2 = [0, 2, 4];
var x1 = codes[parseInt(omo.substr(0, 4), 2)];
var x2 = codes[parseInt(omo.substr(4, 4), 2)];
if (x1 != undefined && x2 != undefined && in_array(x1, arr1) && in_array(x2, arr2)) {
return x1 * x1 * x1 + x2 * x2 + (x1 * (x1 - x2));
}
return -9999;
}
function sortNumber(a,b)
{
return a - b
}
$('#genUnit').click(function() {
$('#geti').html('');
var scope1 = [0, 1, 3, 5, 7];
var scope2 = [2, 4, 6];
// 生成50組個體
everyone = [];
for (var i = 0; i < number; i++) {
var new_omo = genChromosome(scope1) + genChromosome(scope2);
everyone.push (new_omo);
}
for (var i = 0; i < everyone.length; i++) {
$('#geti').append(everyone[i] + " ");
if ((i + 1) % 10 == 0) {
$('#geti').append("
");
}
}
});
// 交叉函數
var cross = function(omo1, omo2) {
// 針對這個，四位是一個染色體特徵控制
var ret = "";
var timestamp = new Date().getTime();
var rnd = Math.ceil(Math.random() * timestamp) % 4;
if (rnd <= 1) {
// 互換前四位
for (var i = 0; i < 4; i++) {
var tmp = omo1[i];
omo1[i] = omo2[i];
omo2[i] = tmp;
}
} else if (rnd <= 3) {
// 互換後四位
for (var i = 4; i < 8; i++) {
var tmp = omo1[i];
omo1[i] = omo2[i];
omo2[i] = tmp;
}
}
var rnd_next = Math.ceil(Math.random() * timestamp) % 2;
if (rnd_next == 0) {
ret = omo1;
} else {
ret = omo2;
}
return ret;
}
// 變異函數
var variation = function(omo1, omo2) {
// 變異某一位，然後做交叉運算
// 這裡暫時不需要，所以直接進行選擇
var timestamp = new Date().getTime();
var rnd_next = Math.ceil(Math.random() * timestamp) % 2;
if (rnd_next == 0) {
ret = omo1;
} else {
ret = omo2;
}
return ret;
}
// 判斷結束
var finish = function() {
// 這裡直接看第五十代
}
$('#genNextUnit').click(function() {
if (everyone.length == 0) {
return
}
// 至少5代且滿足best適應值佔75%或最多50代
var g_num = 0;
while (g_num < 50) {
// 假設淘汰20%，最優的保留，剩下隨機
var fitness_score = [];
for (var i = 0; i < everyone.length; i++) {
fitness_score.push(parseInt(calFitness(everyone[i])));
}
fitness_score.sort(sortNumber);
var over = Math.ceil(fitness_score.length * 0.2)
for (var i = 0; i < over; i++) {
fitness_score.shift();
}
var best = fitness_score[fitness_score.length - 1];
// 生成子代
var new_generation = [];
while (new_generation.length < number) {
var curr_unit;
// 選擇
var timestamp = new Date().getTime();
var choose_fitness1 = everyone[Math.ceil(Math.random() * timestamp) % everyone.length];
var choose_fitness2 = everyone[Math.ceil(Math.random() * timestamp) % everyone.length];
if (calFitness(choose_fitness1) == best && calFitness(choose_fitness2) == best) {
// 進行交叉
curr_unit = cross(choose_fitness1, choose_fitness2)
if (Math.ceil(Math.random() * timestamp) % 100 < 2) {
// 進行變異
curr_unit = variation(choose_fitness1, choose_fitness2)
}
} else if (Math.ceil(Math.random() * timestamp) % 100 > 50) {
// 進行交叉
curr_unit = cross(choose_fitness1, choose_fitness2)
// 進行變異
if (Math.ceil(Math.random() * timestamp) % 100 < 2) {
// 進行變異
curr_unit = variation(choose_fitness1, choose_fitness2)
}
}
if (curr_unit != undefined) {
if (calFitness(curr_unit) > -9999) {
new_generation.push(curr_unit);
}
}
}
everyone = new_generation;
g_num = g_num + 1;
}
var fitness_score = [];
for (var i = 0; i < everyone.length; i++) {
fitness_score.push(parseInt(calFitness(everyone[i])));
}
console.log(everyone[0]);
fitness_score.sort(sortNumber);
var best_number = fitness_score[fitness_score.length - 1];
$('#zidai').html(best_number);
// 01110010
});/<code>