19th Sept (Wed) Machine learning 102

上一部分

開始和結束

初始化人口並不困難,只要填滿隨機的基因。例子中,一個隨機基因和最佳點的距離(費用值)應該是巨大的。下面的代碼的平均費用值達30000之多,但這無相干,這正是進化交配存在的原因。至於停止的時機則比較麻煩。這個例子中比較簡單,基因和目標的基因完全一樣就完成了,即費用值為零。但也有複雜的時候。或者你並不知道最低的值,或者找尋的是最高值,而你事前不知道絕對的最高值。在這些情況之下你需要定義一個完成的條件,可以是任何你想要的條件,例如一千個世代之內,最佳值維持不變。這樣的條件可能令你沒有達到全局的最佳點,但有時候「接近最佳點」已經足夠。我即將會寫另一篇關於使用 PHP基因算法的文章,但些許不同的題目,會應用到以上的「接近最佳點」的概念。

代碼
終於到了代碼的時間,我們會使用物件導向的方法,盡量使用簡單的代碼完成工作。

var Gene = function(code) {
        if (code)
                this.code = code;
        this.cost = 9999;
};
Gene.prototype.code = '';
Gene.prototype.random = function(length) {
        while (length--) {
                this.code += String.fromCharCode(Math.floor(Math.random()*255));
        }
};

簡單的類。使用字符串作為構造構造函數,預設一個高的費用,一個隨機的方法隨機一組基因。
Gene.prototype.calcCost = function(compareTo) {
        var total = 0;
        for(i = 0; i < this.code.length; i++) {
                total += (this.code.charCodeAt(i) - compareTo.charCodeAt(i)) * (this.code.charCodeAt(i) - compareTo.charCodeAt(i));
        }
        this.cost = total;
};

費用函數傳入目標字符串,一個一個比較ASCII ,方根
Gene.prototype.mate = function(gene) {
        var pivot = Math.round(this.code.length / 2) - 1;

        var child1 = this.code.substr(0, pivot) + gene.code.substr(pivot);
        var child2 = gene.code.substr(0, pivot) + this.code.substr(pivot);

        return [new Gene(child1), new Gene(child2)];
};

交配函數傳入另一組基因,找出中間點,切開組合,返回兩組新的基因。
Gene.prototype.mutate = function(chance) {
    if (Math.random() > chance)
            return;

    var index = Math.floor(Math.random()*this.code.length);
    var upOrDown = Math.random()<= 0.5 ? -1 : 1;
    var newChar = String.fromCharCode(this.code.charCodeAt(index) + upOrDown);
    var newString = '';
    for (i = 0; i < this.code.length; i++) {
        if (i == index)
        newString += newChar;
        else
        newString += this.code[i];
    }

    this.code = newString;
}

變化函數傳入變化的機率,如果發生變化的話則隨機抽一個字符變化。變化的算法是隨機ASCII 加或減一。
var Population = function(goal, size) {
        this.members = [];
        this.goal = goal;
        this.generationNumber = 0;
        while (size--) {
                var gene = new Gene();
                gene.random(this.goal.length);
                this.members.push(gene);
        }
};

人口的構造函數傳入目標的字符串和人口的大小,隨機產生人口數量的基因。
Population.prototype.sort = function() {
        this.members.sort(function(a, b) {
                return a.cost - b.cost;
        });
}

人口中的基因需要一個由小至大的費用值排序函數。
Population.prototype.generation = function() {
        for (var i = 0; i < this.members.length; i++) {
                this.members[i].calcCost(this.goal);   
        }

        this.sort();
        this.display();
        var children = this.members[0].mate(this.members[1]);
        this.members.splice(this.members.length - 2, 2, children[0], children[1]);

        for (var i = 0; i < this.members.length; i++) {
                this.members[i].mutate(0.5);
                this.members[i].calcCost(this.goal);
                if (this.members[i].code == this.goal) {
                        this.sort();
                        this.display();
                        return true;
                }
        }
        this.generationNumber++;
        var scope = this;
        setTimeout(function() { scope.generation(); } , 20);
};

人口類中最難明的部份是 generation 函數。display() 會輸出世代中費用最低的基因和完成的時候將世代間最低費用值的變化圖像化,再加入一點時間上的推遟。
這個例子中交配只包括兩個最佳基因,而你絕對可以使用其化的算法。
window.onload = function() {
        var population  = new Population("Hello, world!", 20);
        population.generation();
};

初始化。

這算法並不快,你可以簡單的找出緩慢的部分改進,我支持你修改我的算法。

以上的代碼其實可以使用任何的其化程式語言完成

完整代碼: https://github.com/joetsuihk/machine-learning

Google