遺傳算法簡述

遺傳算法也成進化算法，該算法受到達爾文進化論的啟發提出的一種啟發式搜索算法。

進化論

種群

生物的進化以群體的形式進行，這樣的一個群體稱為種群。

個體

組成種群的單個生物。

基因

一個遺傳因子。

染色體

包含一組的基因。

生存競爭，適者生存

對環境適應度高的個體參與繁殖的機會比較多，後代就會越來越多。適應度低的個體參與繁殖的機會比較少，後代就會越來越少。

遺傳與變異

新個體會遺傳父母雙方各一部分的基因，同時有一定的概率發生基因變異。

綜述

繁殖過程，會發生基因交叉，基因突變 ，適應度低的個體會被逐步淘汰，而適應度高的個體會越來越多。那麼經過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>

閱讀更多 袁博讀書 的文章

關鍵字: 算法 遺傳 查爾斯·達爾文