摘要：遺傳算法物競(jìng)天擇，適者生存，遺傳算法就是借鑒生物體自然選擇和自然遺傳機(jī)制的隨機(jī)搜索算法。隨機(jī)生成的基因適應(yīng)度的最大值隨機(jī)生成，適應(yīng)度函數(shù)計(jì)算種群中所有對(duì)象的適應(yīng)度及總和，并對(duì)超出的基因進(jìn)行懲罰。

此為《算法的樂(lè)趣》讀書(shū)筆記，我用javascript（ES6）重新實(shí)現(xiàn)算法。

“物競(jìng)天擇，適者生存”，遺傳算法就是借鑒生物體自然選擇和自然遺傳機(jī)制的隨機(jī)搜索算法。算法的關(guān)鍵點(diǎn)有：基因的選擇與編碼、適應(yīng)度評(píng)估函數(shù)與三個(gè)遺傳算子（選擇、交叉和變異）的設(shè)計(jì)。

有一個(gè)背包，最多承重為C=150的物品，現(xiàn)在有7個(gè)物品，編號(hào)為1~7，重量分別是w=[35,30,60,50,40,10,25]，價(jià)值分別是p=[10,40,30,50,35,40,30]，現(xiàn)在從這7個(gè)物品中選擇一個(gè)或多個(gè)裝入背包，要求在物品總重量不超過(guò)C的前提下，所裝入的物品總價(jià)值最高。

該算法采用屬性序列方式對(duì)基因編碼，遺傳算子則使用了比例選擇模式、多點(diǎn)交叉和均勻變異三種方式，麻雀雖小，五臟具全。

var C = 150                            //背包最大承重
var WEIGHT = [35,30,60,50,40,10,25]    //物品重量
var POWER = [10,40,30,50,35,40,30]     //物品價(jià)值
var LEN = 7                            //基因長(zhǎng)度
var maxPower = 0                       //保存最大值方案
var maxGene = []
var maxi = 0;                          //最大值最初出現(xiàn)的進(jìn)化代數(shù)
const POPMAX = 32,                     //種群數(shù)量
    P_XOVER = 0.8,                     //遺傳概率
    P_MUTATION = 0.15,                 //變異概率
    MAXGENERATIONS = 20                //總的進(jìn)化代數(shù)
var pop = []                           //種群所有對(duì)象

基因由7件物品狀態(tài)組成，1表示裝入，0表示不裝入；每個(gè)個(gè)體除了基因外，還有適應(yīng)度、選擇概率和積累選擇概率。類(lèi)定義如下：

class Gene{
    constructor(gene){
        this.gene = gene;            //基因，數(shù)組
        this.fitness = 0;
        this.rf = 0;
        this.cf = 0;
    }
}

每個(gè)個(gè)體選擇隨機(jī)的基因，使用0，1隨機(jī)數(shù)直接填充gene數(shù)組。因?yàn)檫@個(gè)具體問(wèn)題規(guī)模較小，在選擇時(shí)我丟棄了適應(yīng)度較高的方案，以此來(lái)更好的測(cè)試算法的效果。

function initGenes(){
    let count = 0, maxFit = 100;    //隨機(jī)生成的基因適應(yīng)度的最大值
    while(count < POPMAX){
        let tmp = [],pall = 0;
        for(let j = 0; j
適應(yīng)度函數(shù)
計(jì)算種群中所有對(duì)象的適應(yīng)度及總和，并對(duì)超出C的基因進(jìn)行“懲罰”。
function envaluateFitness(max){            //max參數(shù)只是用來(lái)記錄進(jìn)化代數(shù)
    let totalFitness = 0;
    for(let i=0; i C){                    //基因不符合要求，適應(yīng)降到1，讓其自然淘汰
            pop[i].fitness = 1;
        }else{
            if(pop[i].fitness > maxPower){            //保存階段最優(yōu)值
                maxPower = pop[i].fitness;
                maxGene = __.cloneDeep(pop[i].gene);  //使用lodash庫(kù)
                maxi = max;
            }
        }
        totalFitness += pop[i].fitness
    }
    return totalFitness;
}
選擇算子函數(shù)
采用簡(jiǎn)單的輪盤(pán)賭方式進(jìn)行選擇，首先計(jì)算種群中所有個(gè)體的選擇概率和累積概率，然后利用隨機(jī)數(shù)進(jìn)行“輪盤(pán)賭”，挑出幸運(yùn)者作為新種群。這里有個(gè)坑，lodash的cloneDeep直接克隆pop會(huì)有問(wèn)題，出現(xiàn)怪異問(wèn)題，難道是我的對(duì)象層次太深，求解！
function selectBetter(totalFitness){
    let lastCf = 0;
    let newPop = []
    for(let i = 0; i= pop[j].cf && p < pop[j+1].cf){
                    newPop[i] = pop[j+1];
                    break;
                }
            }
        }
    }
    pop = []         //種群替換，坑在這，直接 pop=__.cloneDeep(newPop)不對(duì)，高手給解釋下，誰(shuí)研究過(guò)lodash的源碼？
    for(let i=0; i< newPop.length; i++){    
        pop.push(__.cloneDeep(newPop[i]))
    }
}
交叉算子函數(shù)
交叉算子采用多點(diǎn)交叉策略，對(duì)兩個(gè)隨機(jī)選中的個(gè)體基因進(jìn)行交換，基因交換的位置和個(gè)數(shù)都是隨機(jī)的，使得新個(gè)體的基因更具有隨機(jī)性。
function crossover(){
    let first = -1;
    for(let i=0; i
變異算子函數(shù)
變異算子采用均勻變異的策略，選中個(gè)體基因變異的個(gè)數(shù)與位置都是隨機(jī)選擇的。
function mutation(){
    for(let i=0; i
算法主流程
主流程很簡(jiǎn)單，幾乎是線性的。
initGenes();
var f = envaluateFitness(0)
for(let i=0; i " + maxGene.join(","));
總結(jié)
以前一直覺(jué)得遺傳算法很神秘，因此仔細(xì)研究了一下，覺(jué)得算法的效果很大程度上取決于各種參數(shù)的設(shè)定。另外，也許進(jìn)化過(guò)程中出現(xiàn)過(guò)最優(yōu)值，但最后的種群中也不一定會(huì)有最優(yōu)值存在。真是能用其它方法可以解決時(shí)最好不用它，呵呵！