23th Sept (Sun) Day 11 無題
星期天來點輕鬆的閒話 blog
轉為全職的 Freelancer 的改變
- 睡不定時了（反正一直都睡得少）
- 使用 MBA 的時間多了幾十倍計
- code 寫少了（還沒有開單...）
- 會開多了，estimate 寫多了
- blog 寫多了
- 時間多了
暫時就這些
才開始 freelance 還未滿兩星期
我也不心急錢的問題
眼下正在談的項目都「謹慎樂觀」
有一點後悔的是一直沒其他的被動收入
例如賣 theme ，外包 hosting 之類的
否則現在的工作可以更輕鬆
現在投入時間增加又太忙
還是等十二月過年的時間比較閒的時間才可以專心開發這個方面。
22th Sept (Sat) Day 10 Raspberry Pi 的新超頻模式效能提升 50%，仍可保固
又忘了 weekend 的 daily blog
Weekend 的 blog 還宜容易忘記
http://www.raspberrypi.org/archives/2008
手機都可以超頻年代，Raspberry Pi 都可以。先前官方的超頻方式是修改 config.txt，提升電壓當然可以達成超頻的效果，但你會冋時失去保固，因為芯片的壽命會因而減少。BCM2835 芯片上有一個位元記錄這一個加壓的動作來取消保固。
官方花了很多時間研究電壓和溫度對芯片壽命的影響，所以官方提供一個最新的「高速模式」
，可以使用 cpufreq 驅動來動態超頻和加壓，而且不會失去保固。這是因為驅動只會在繁忙的時候啟動，而且芯片的溫度超過85°C的時候會自動停止，這可以令芯片的壽命維持和原本的一樣。
你可以從五個預設的超頻模式中選一個，最高的頻率可以達到 1GHz。而超頻時的穩定性則取決於你的電源供應。 Quake 3 是官方建議的壓力測試。如果你的 Pi 在超頻後不能啟動，你可以啟動的時候按 shift 鍵停用超頻，就修改你的超頻設定。
效能的提升上，比較超頻的 1GHz 和原生的 700MHz， nbench 測試軟體顯示整數運算有 52% 的提升，浮點有 64% 的提升，55% 內存速度的提升。
固件的其他修改包括：
溫度頻率的 widgets
你可以在 lxde 的任務條看到你的芯片的溫度， cpufreq widget 則顯示芯片的工作頻率。
減低USB中斷頻率
Gordon 在USB驅動中提供的 “FIQ Fix”，減少 USB 中斷，帶來整體大約 10%的效能提升。
WiFi 的支持
如果你的WIFI 驅動是預設的 linux 版本，或基於 RTL8188CUS 芯片的話， WiFi 現在應該可以正常運作，啟動的時候插入 WiFi 模組，執行 startx 然後選 “WiFi Config”，你便可以搜尋無線網絡和輸入你的密碼，不現需要其他的設定了。
提升的音效
新的預設軟體
SmartSim 和 PenguinsPuzzle
如果你正使用舊的 wheezy image，你可以使用 “sudo apt-get update && sudo apt-get upgrade” 來升級
最後感謝 MrEngman 的 wifi 上的貢獻，Dorian Peake 在 cpufreq 和有關溫度的驅動，Dmitry Dudkin 在USB 和 SD card 上的貢獻。
21th Sept (Fri) Day9 Machine learning 202 基因算法4
續上 基因算法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。
20 Sept (Thur) Day8 Machine learning 201 基因算法3
譯自 http://burakkanber.com/blog/machine-learning-genetic-algorithms-in-javas...
今日要看的是基因算法的進階部分，如果你進沒有看過部一和第二部分，我強烈建議你先看過它們。這篇會跳過前兩部的基礎。
題目
你可帶走實驗室中一千個單位重量的元素，元素的價值都不一樣，目標是帶走最貴的元素，同時重量不超過一千單位。價錢的最大化，但同時在重量的限制之下。
這是一個 knapsack http://en.wikipedia.org/wiki/Knapsack_problem 題目，以上的是一個一元題目，意思是唯一的限制是重量，我們可以加入其他的限制，例如體積，但我們還是從簡單的開始。注意的是題目的元素每一款都只有一件，每一件都有一個重量。這題目有其他的變種例如有三件黄金，但我們的條件是每款一件。
為何這個題目如此果難？元素總共有118種，使用暴力列舉的話總共有 2^118 個不同的可能組合。
貪心算法
一個快速的基準是謂的貪心算法。貪心算法拿的是最貴重的元素直至達到重量限制。有時候這個算法都不錯，但當然不是最好的。例如黄金值 $1000，重600單位。但有另一元素 cadmium 值$950 但重量為300單位。還有其他元素是有一定的價值但重量不大。貪心算法會選黄金，珍貴的重量會被佔一大部分。
這個簡單的貪心算法會帶走 $3649 的元素，重998單位
你可能會說，我們可以用找出平均一重量單位價值最高元素的方法，這算法會帶走 $4901 的元素，重969單位。
所以我們有兩個基準，簡單的應該可以打倒 $3649，花點工夫 $4901 都不是問題。
為何貪心算法的效果這樣的好？因為這算法找出的「最高價值重量比」和我們要找的非常相近，但這算法遇上價值和重量相差大的情況便不管用。
基因算法可能會有數世代比貪心算法差，但會基因算法會一個比一個世代好，特別是複雜程度增加的時候。
所以我們在看的是一個相對簡單的題目，但仍比上一個 Hello world 題目複雜，現在開始吧。
關鍵的差別
一些明顯和上一個題目的不同的地方：
- 我們使用過重複的字符，但這次不使用重複的元素
- Hello world 是13個字符長度，但這次帶走的元素的數字是未知
- 我們不知道最高的價值，即最佳點。可能是貪心算法的 4901，可能是 10000，或 23304
基因的表示法
Hello world 中我們使用字符串代表基因，變化是隨機改變一個字符，交配是切開組合兩組基因，這次便有點不同。
這次表示基因的方法有點難道，我們不知道元素的多少，不可以使用固定長度的字符串。
或者我們可以使用 bitmask 的方式，一個位元代表一個元素，共118個位元，1代表帶走，0代表留下：10000011000001000100000010000010010010000
如果題目容許帶走多個相同的元素，表示的方式可以改為4001000020003000100000100000001
Helium, Lithium, Lead, Tin
而上面這一種方式會令交配變得困難，因為要確保交配之後的結果不會有重複的元素出現兩次。
人口超載問題
這題目我們會算出基因的三個參數：重量，價值和分數。其中分數和價值很相似，但分數會計入重量超過限額時候的值。
你可能會問為何我們不直接放棄超載的基因。這或者是很自然的反應，因為超載的基因一定不會是最佳解。但一些只是筲為超載的基因很可能很有用，我們只需要稍為修改一下，這個基因的重量便可能維持在限制之內。
超載的基因帶有很多的可能性，留住它們，加入倒扣分數的條件件，而非都殺掉令它們可以交配，但排在最前的機會便會減低。下面的代碼為超載的基因減50點分數，你可以試試這個數字。
從進化的角度看，這會推動基因減去多餘的重量，它們只需要小的修改，而不應殺掉一個可能很強的基因。
待續
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();
};初始化。
這算法並不快，你可以簡單的找出緩慢的部分改進，我支持你修改我的算法。
以上的代碼其實可以使用任何的其化程式語言完成
