續上 基因算法3
首先看看元素表，我使用了 PHP 來建立一個隨機的重量和價值，(範圍 1 – 500) ，格式為 JSON。以下是其中一點部份：
"Hydrogen":{
"weight":389,
"value":400},
"Helium":{
"weight":309,
"value":380},
"Lithium":{
"weight":339,
"value":424},
"Beryllium":{
"weight":405,
"value":387},
"Boron":{
"weight":12,
"value":174},如此類推
然後一個類，三個簡單的方法：
function length(obj) {
var length = 0;
for (var i in obj)
length++;
return length;
}
function clone(obj) {
obj = JSON.parse(JSON.stringify(obj));
return obj;
}
function pickRandomProperty(obj) {
var result;
var count = 0;
for (var prop in obj)
if (Math.random() < 1 / ++count)
result = prop;
return result;
}「length」屬性只對 arrays，所以我們需要另一個對物件用的 length()。
clone() 函數是令物件之間不使用指針複製
最後一個函數是隨機選一個物件，返回物件的 key。
基因函數
var Chromosome = function(members) {
this.members = members;
for (var element in this.members)
{
if (typeof this.members[element]['active'] == 'undefined')
{
this.members[element]['active'] = Math.round( Math.random() );
}
}
this.mutate();
this.calcScore();
};
Chromosome.prototype.weight = 0;
Chromosome.prototype.value = 0;
Chromosome.prototype.members = [];
Chromosome.prototype.maxWeight = 1000;
Chromosome.prototype.mutationRate = 0.7;
Chromosome.prototype.score = 0;基因類的結構函數傳入 ‘members’。傳入的或者是一列元素(建立全新的基因的時候) 或者傳入交配的結果。
如果’active’ 未定義的話，結構函數會隨機「帶走」元素，這樣隨機建立的元素便已經指定一組帶走元素的可能性，而交配的基因便不會修改「帶走」的元素。
還定義一些參數， mutationRate 是基因變化的概率
Chromosome.prototype.mutate = function() {
if (Math.random() > this.mutationRate)
return false;
var element = pickRandomProperty(this.members);
this.members[element]['active'] = Number(! this.members[element]['active']);
};變化的方法和 “Hello, World!” 的題目最相似，如果基因是會變化的話，隨機選一個元素，反轉‘active’ 屬性。
Chromosome.prototype.calcScore = function() {
if (this.score)
return this.score;
this.value = 0;
this.weight = 0;
this.score = 0;
for (var element in this.members)
{
if (this.members[element]['active'])
{
this.value += this.members[element]['value'];
this.weight += this.members[element]['weight'];
}
}
this.score = this.value;
if (this.weight > this.maxWeight)
{
this.score -= (this.weight - this.maxWeight) * 50;
}
return this.score;
};calcScore 方法先用一個小的效能提升手段，如果先前已經算過分數 (score)，便使用緩存的分數。
再看看每一個元素，將分數，重量加起來。每一個超重的單位減 50 點分數
Chromosome.prototype.mateWith = function(other) {
var child1 = {};
var child2 = {};
var pivot = Math.round( Math.random() * (length(this.members) - 1) );
var i = 0;
for (var element in elements)
{
if (i < pivot)
{
child1[element] = clone(this.members[element]);
child2[element] = clone(other.members[element]);
}
else
{
child2[element] = clone(this.members[element]);
child1[element] = clone(other.members[element]);
}
i++;
}
child1 = new Chromosome(child1);
child2 = new Chromosome(child2);
return [child1, child2];
};“Hello, World!” 的題目交配使用字符串中間的點切開，這次我們則選一個隨機的點切開。
這為全個算法加仕一點隨意性，也可以避開局部的最佳點。
當選了最佳點，切開兩個基因再組合，使用基因的結構函數然後返回它們。
人口
var Population = function(elements, size)
{
if ( ! size )
size = 20;
this.elements = elements;
this.size = size;
this.fill();
};
Population.prototype.elitism = 0.2;
Population.prototype.chromosomes = [];
Population.prototype.size = 100;
Population.prototype.elements = false;人口的結構函數是簡單的，給它一列元素和人口的數量。 ‘elitism’ 參數是能傳到下一代基因仍然生存的概率
Population.prototype.fill = function() {
while (this.chromosomes.length < this.size)
{
if (this.chromosomes.length < this.size / 3)
{
this.chromosomes.push( new Chromosome( clone(this.elements) ) );
}
else
{
this.mate();
}
}
};fill 方法是初始化人口，也用作入填入死去基因的空缺。一小段的代碼決定填入隨機的基因或者使用交配產生下一代。如果我們的人口是 20，首 6 個基因會是隨機的，其餘都為交配。如人口降至 30% 以下，全新的隨機基因會填入直至達到基因之間能交配為止。
‘this.chromosomes.length’ 是一個差的 while loop。如果你使用一個大的人口值的話，緩存基因的長度吧
Population.prototype.sort = function() {
this.chromosomes.sort(function(a, b) { return b.calcScore() - a.calcScore(); });
};
Population.prototype.kill = function() {
var target = Math.floor( this.elitism * this.chromosomes.length );
while (this.chromosomes.length > target)
{
this.chromosomes.pop();
}
};sort 函數只是一個幫手，我們使用 calcScore 而非直接存取 ‘score’ 。如果 score 還未被計算的話，便計一下，如果已經算了，calcScore 便直接返回 score
排序之後， kill 方法除掉最差的基因，直至達到 elitism 的值
Population.prototype.mate = function() {
var key1 = pickRandomProperty(this.chromosomes);
var key2 = key1;
while (key2 == key1)
{
key2 = pickRandomProperty(this.chromosomes);
}
var children = this.chromosomes[key1].mateWith(this.chromosomes[key2]);
this.chromosomes = this.chromosomes.concat(children);
};交配的方法是 kill 之後一定會使用的，所以交配的都是選過的基因，(例子中是最好的 20%)。不再是交配最好的兩條基因，我們隨機選兩條作交配，當然也不可以自己跟自己交配。
同樣的，這樣可以帶入更多的隨機性，避免首兩個基因一直橫跨多個世代， “Hello, World!” 的題目其實時有出現，現在修正過來。
Population.prototype.generation = function(log) {
this.sort();
this.kill();
this.mate();
this.fill();
this.sort();
};定義一個「世代」，首先基因使用分數排序，除去最弱的。再來的有點特別，先交配再填入(fill)，但其實 fill 都會使用交配方法。先使用交配的原因是如果 elitism 是小於 0.3，我們需要交配一次確保一個可能的 bug， 使用隨機的基因「污染」了人口。這完全取決於 elitism 的值， 在 0.3 以上你不會有這個問題，不需要先交配再填入，因為填入已經為你準備好。但如果 elitism = 0.2，我們要先交配優質的基因，而非 fill() 中隨機的基因。
最後，再排一次序，我們其實不需要這樣做，但這對除錯的幫助很大。
執行和停止
我們已經提過，我們不知道這題目的最佳解，所以也不知道何時應該停止。
我們使用的方法是一百個世代都沒有進步便停止，稱為 “threshold”
Population.prototype.run = function(threshold, noImprovement, lastScore, i) {
if ( ! threshold )
threshold = 1000;
if ( ! noImprovement )
noImprovement = 0;
if ( ! lastScore )
lastScore = false;
if ( ! i )
i = 0;
if (noImprovement < threshold)
{
lastScore = this.chromosomes[0].calcScore();
this.generation();
if (lastScore >= this.chromosomes[0].calcScore())
{
noImprovement++;
}
else
{
noImprovement = 0;
}
i++;
if (i % 10 == 0)
this.display(i, noImprovement);
var scope = this;
setTimeout(function() { scope.run(threshold, noImprovement, lastScore, i) }, 1);
return false;
}
this.display(i, noImprovement);
};run 方法是一個逐步的函數，但也不一定需要，原因是在一個快速的回圈中寫入 DOM 沒有用， DOM 不會更新直至執行完結
要避開 DOM 的限制，我們使用一個短的 setTimeout 然後 run() 方法呼叫自己直至完成，但一般來說，這個函數可以使用一個 while loop 但你便要使用 console.log 或者等 loop 完成弓才可以看到結果
除了 DOM 的問題之外， run 方法是簡單的。比較上一個世代的最佳基因，有進步的話便重新定義 ‘noImprovement’ 。如果 noImprovement 已經等於 threshold 便停止。
執行
一個10世代的基因可以輕易打倒第一個貪心算法，50世代可以打倒使用平均值的貪心算法，有一些元素的設定會令使用平均值的貪心算法已經是最佳解，有些則完全相反。我們並沒有完全一擊打倒平均值的貪心算法，但可以明顯的勝過它。
最佳解似乎是 5968 重 998。
