譯自 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點分數，你可以試試這個數字。

從進化的角度看，這會推動基因減去多餘的重量，它們只需要小的修改，而不應殺掉一個可能很強的基因。

待續