[python] 基因演算法探討數字遮罩的最佳解

前言

在 facebook 上，python taiwan 出現一個討論

 

楊文誠
這是我學校作業,但是我真的看不懂,可以幫我翻譯一下嗎?拜託~~
我連我要幹嘛都不知道了......

圖1：一個學生來問作業的解答，引起廣泛的討論。[1]

題目是找出合乎一個範圍內的數字，以它跟某一特定的數字作 or 運算可得到的值越大越好，而其本身越小越好。這可以當成是一個尋找遮罩的問題。

雖然有留言說已經有各種解法出現在 ptt 上(可見不只一個人來討解答)，我就愛自己試一試。題目有附註說，用蠻力法要扣30分，但是我很難界定蠻力法是什麼樣子？難道不能把 i in range(L, U+1) 都算過一遍嗎？

遇到這種問題，當我沒辦法直覺想到演算法，就會交給上天/上帝，也就是基因演算法。誰叫這題目正好命中基因演算法的解形式呢！

人工智慧演算法，通常應用在正規演算法找不到或是正規演算法要算很久的情況。如果把所有解都算過一遍以得到最佳解都來得及，為什麼要用人工智慧得到可能最佳解呢？所以現在人工智慧演算法已經不流行了。在運算力如此可怕的時代，想用人工智慧演算法的人，準確的說會使用基因演算法的人，大概就像我這樣把演算法丟給上帝的懶墮蟲吧。我猜 ptt 的各種解法應該不會有用基因演算法的，因為不保證答案會對喔！可以說根本是來搞笑的！(若說是做先期研究的開路先鋒，就好聽很多。)

在這次的文章裡，可以好好體會了一下基因演算法的眉眉角角，在實際應用上會增加不少經驗值。同時，我也在這次的研究中，學到用基因演算法的方法論來研究問題、優化演算法。

第一章 基因演算法的基礎

基因演算法是模仿生物演化的理論，留下好基因，求得最佳解的一種演算方法。它從基因的互換、突變，來得到新的基因，透過適應性的評估哪些是決定比較好的基因並留下，再進行基因的互換、突變以得到新的基因，不斷重復這過程，直到滿意為止。

以上是理論，那實務上真的要解決問題，要面對的是先回答另一些問題：

1. 基因的形式為何？
2. 基因的互換方式為何？
3. 基因的突變方式為何？
4. 適應性如何評估？
5. 要留下多少基因？
6. 要看幾代？

這些問題，也就是問題之前的問題，是演算法之外的事，一般是不會在教科書上教的。多數的教科書，多是只給了一兩個範例，但是沒有說為什麼要這麼問這些問題。多把文章重點放在解釋基因演算法的原理或實作的程式碼。反而上述的幾個問題該「如何回答這些問題」成為了實務上最難解的問題。有些時候上面的六個問題沒有答案，就不能用基因演算法了。而這些答案都是 case by case，領域不同、題目不同，則答案就不同。甚至答案可以有很多，得看實際執行後的結果及效率來決定答案好不好，是不是最佳。經驗也會影響答案的內容，而且答案的內容也會影響實作，在這麼交互影響之下，答案討論起來是很繁瑣又不具通用性，或許是教科書不寫的原因吧？但是重申一次在實務上，這很重要！

我這裡按順序說明我對於各個問題的初步答案，第一個問題，基因的形式，在這裡剛好就是 mask 的樣子，由一串0與1組合而成的字串，不過為了計算方便，把它轉成 32-bit 的正整數數字，也剛好合題目的需求。剩下的問題，答案先暫時決定如下：

• 基因的互換方式：暫定為「最佳基因的前半部加本次最佳基因的後半部」。
• 基因的突變方式：暫定為「隨機挑一個bit，0、1互換」
• 適應性評估：正好為題目需求，與 mask 運算完的數字越大越好，而 mask 本身則是越小越好。那就是按運算完的數字排列，挑最大的，若運算完數字同樣大小，則按 mask 本身數字挑比較小的。
• 留下多少基因：跟基因互換有關聯，暫定為「已知最佳基因，與本次獲得最佳基因」，因此只有兩個。
• 暫定1000代

第二章 完全亂數與暴力法的差別

在決定前一章的六個問題後，我開始實作我的演算法。程式中有一些基礎函式要先做：

import random
string_length = 32

def _bin_string(num):
    # bin(63) => '0b111111'
    return bin(num)[2:].zfill(string_length)

def _invert_at(s, index):
    return bin(int(s, 2) ^ 2 ** (index))[2:].zfill(string_length)

def _int_from_bin(s):
    return int(s, 2)

def score(num):
    '''分數函數'''
    return num | N

def f1(num1, num2):
    '''交配'''
    s1 = _bin_string(num1)
    s2 = _bin_string(num2)
    return _int_from_bin(s1[0:16] + s2[16:32])

def f2(num):
    '''突變'''
    i = random.randint(0, 31)
    s = _bin_string(num)
    ss = _invert_at(s, i)
    return _int_from_bin(ss)

def is_acceptable(num):
    '''存活函數'''
    if num > U:
        return False
    elif num < L:
        return False
    else:
        return True

接下來才是依照問題寫好的基因演算法：

L = 201310
U = 3567891
N = 30951344

p1 = L
p2 = U

i = 0
for j in range(1000):

    m1 = f1(p1, p2))
    m2 = f2(m1)

    if not is_acceptable(m1):
        print 'skip m1', j, m1
        continue
    if not is_acceptable(m2):
        print 'skip m2', j, m2
        continue

    score0 = score(p1)
    score1 = score(m1)
    score2 = score(m2)
    if score1 > score2:
        d = m1
    elif score1 < score2:
        d = m2
    else:
        d = min(m1, m2)
    score3 = score(d)
    if score0 > score3:
        p2 = d
    elif score0 < score3:
        p2 = p1
        p1 = d
    else:
        p1 = min(p1, d)
        p2 = max(p1, d)

    i += 1
    print j, p1, p2

print i, p1, p2

 

第一次執行，咦！沒有輸出。經過檢查，m1 不在 LU 的範圍內，所以完全得不到存活的子代基因，遇到這麼不順利的情況，非改不可。把 m1 的產生方式改成 f2(f1(p1, p2))，經過 10 次(每次 1000 代)測試，發現平均有存活的子代基因約 430 次左右，當然答案都不一樣，10 次得到最好的解是 mask 2603087，分數是 33554431。

那麼暴力法呢？程式如下：

p1 = L

for j in range(L, U + 1):

    score0 = score(p1)
    score1 = score(j)
    if score0 > score1:
        pass
    elif score0 < score1:
        p1 = j
    else:
        p1 = min(p1, j)

    print p1, score(p1), j

超級短的程式，得到的結果是 mask 2603087，分數是 33554431。

在觀察基因演算法給出的 10 次答案的時候發現，在求適應性分數來說，幾乎 10 次有 9 次的分數是正解。但是求 mask 的部份，卻不一定會是正確答案。拿這個答案交出去可能不會得分。或許，我再多跑幾次，可能得到更好的 mask，可能得到更差的 mask，但實務上來說，若我不跑一次暴力法，我永遠不會知道 mask 是不是最小，score 是不是最大。能不能接受基因演算法的答案，真的是看情況。

另一方面，兩者的執行環境都在 windows 的 console 下跑，並且取消所有迴圈中的 print，若不取消，暴力法的執行時間被 print 拖累太多太多，我認為不公平。最後結果是暴力法的時間是0:00:01.95，而基因演算法的時間是 0:00:00.14，約為暴力法的 7% 的執行時間。

第三章 從基因演算法的角度思考優化

在第二章中雖然基因演算法有得到答案，但其實是不確定是否為最佳答案。假設答案是不能接受這種不確定性，那如何思考更好的演算法，可以在可忍容的資源下把所有可能的答案都算過一遍？從基因演算法的角度出發就是要問如何更有效率的演化？提高演化效率的方向有，(1)基因的存活率、(2)基因交配的方法、(3)基因突變的方法。這三個方向不完全是獨立的，它們之前會隨問題而有不同程度的某種關聯性。

隨機挑選子代

首先從提升存活率來看，之前的子代產生是經由交配、突變產生，有時子代會跑出規定的上下限而直接淘汰。是否能直接從解集合裡產生子代，以提升存活率，進而能更廣泛提取驗證子代呢？首先試試不經交配、突變，直接亂數選取子代的效果。

f4_i = range(L, U + 1)
def f4(num, restart=False):
    '''不經交配、突變，直接亂數選取子代'''
    global f4_i
    if len(f4_i) == 0:
        raise Exception('len(f4_i) == 0')
    if restart:
        f4_i = range(L, U + 1)
    i = random.randint(0, len(f4_i) - 1)
    si = f4_i[i]
    del f4_i[i]
    return si

改寫原先程式，把存活函數拿掉，避免產生重覆的子代：

from datetime import datetime
fnstart = datetime.now()
'''不經交配、突變，直接亂數選取子代'''
result = []
p1 = L
p2 = U
for k in range(10):
    i = 0
    for j in range(1000):

        m1 = f4(p1)
        m2 = f4(p1)

        score0 = score(p1)
        score1 = score(m1)
        score2 = score(m2)
        if score1 > score2:
            d = m1
        elif score1 < score2:
            d = m2
        else:
            d = min(m1, m2)
        score3 = score(d)
        if score0 > score3:
            p2 = d
        elif score0 < score3:
            p2 = p1
            p1 = d
        else:
            p1 = min(p1, d)
            p2 = max(p1, d)

        i += 1
        #print j, p1, p2

    #print i, p1, p2
    result.append([p1, score(p1)])

print 'execute time', datetime.now() - fnstart

def cmp_result(x, y):
    if x[1] != y[1]:
        return y[1] - x[1]
    else:
        return x[0] - y[0]
print sorted(result, cmp_result)

結果，執行時間變長了，都是 10 * 1000 的迴圈，用掉約 37 秒。得到的答案更不正確。

execute time 0:00:37.332000
[[2603343, 33554431], [2603343, 33554431], [2603343, 33554431], [2603343, 33554431], [2603343, 3554431], [2603343, 33554431], [2603343, 33554431], [2603343, 33554431], [3128447, 33554431], 2620006, 33554422]]

首先，維護解集合的代價太高，在這例子中，高過低存活率的計算代價。另外得到的答案變異數變大，暗示前次基因的交配策略，在選擇子代中有顯著的助益。這是個很重要的暗示。

找出基因固定段

由前段知道交配策略有顯著助益，因此朝向基因段交互關係研究。

L、U、N 三個數的2進位表示為：

L = 00000000000000110001001001011110
U = 00000000001101100111000100010011
N = 00000001110110000100011110110000

從問題的本質來看，N 與 mask 作用後要最大，最好是 mask 都為 1，但是 mask 又要最小，策略就是 mask 把 N 的 0 的地方換成 1 的是最有效率。

U = 00000000001101100111000100010011
M = 11111110001001111011100001001111 (第一步)

然而，因為有 L、U 作為存活函數的參數，是解集合的上下限，在比 U 最前面的 1 更前面的 0 是不可以變動。所以 M 要把比 U 最高位 1 之前的 1 全變成 0：

U = 00000000001101100111000100010011 (有點對不齊)
M = 00000000001001111011100001001111 (第二步)

因此，基因交配以最佳解的前半部為子代的前半部，是把比較小的 M 留下來，正好是提高演化效率的方法，算是誤打誤撞。不過，在了解 N 、 M 及 U 的關係之後，可以把 M 的基因分成兩段：

M[0:U_first_1_pos+1] 這一段是固定不動，會維持較小的 M，並且有合理的天然上限，交配、突變時會增加存活率。
M[U_first_1_pos+1:] 這一段就是可以改變的基因段。

在第二步這裡得到的 M 是可以得到最高分數的 M，如果它滿足 L <= M <= U，那麼答案就得到了。這裡，又不小心地得到了跟暴力演算法一樣的答案 M = 00000000001001111011100001001111 = 2603087。

如果情況不是呢？那就要在 M[U_first_1_pos+1:] 這一段基因裡變化。

在 M[U_first_1_pos+1:] 的優化

在變動段的基因段裡，依然照著最佳演化的目標前進，繼續觀察 N、M 的關係。

00000001110110000100011110110000 (N)
00000000001001111011100001001111 (M)

第二步得到的 M，在它不滿足 L <= M <= U 的條件下，必須要改變某些基因，讓它符合 L <= M <= U。在所有的基因的變化會有幾種可能，它的影響如下：

1. N:0, M:0，把 M 的 0 變成 1 ==> 分數變大，mask 變大。
2. N:1, M:1，把 M 的 1 變成 0 ==> 分數不變，mask 變小。
3. N:0, M:1，把 M 的 1 變成 0 ==> 分數變小，mask 變小。
4. N:1, M:0，把 M 的 0 變成 1 ==> 分數不變，mask 變大。

也因此，上面的情況裡，優先測試的是 2 (當 M > U) 或 4 (當 M < L)。若都無法找到滿足 L <= M <= U 的解，則再嘗試 1 (當 M < L) 或 3 (當 M > U) 。但是在第二步得到的 M，不會有第 1 種及第 2 種情況。也就是只剩下第 3 種(分數變小，mask 變小)、第 4 種(分數不變，mask 變大)。所以到了這裡可以明確的說：

當 M > U 的時候，採取「尋找 N:0, M:1 的 bit，把 M 那邊的 bit 反轉」的策略進行演化。

當 M < L 的時候，採取「尋找 N:1, M:0 的 bit，把 M 那邊的 bit 反轉」的策略進行演化。

這樣的基因組應該全部列舉出來了吧？仍然以例題為例，有13個 bit 是 N:0, M:1，所以有 2^13 = 8192 種變化。而 N:1, M:0 有 9 個 bit，所以有 2^9 = 512 種變化。如果仔細想想，又可以再使用 L, U 去掉不合適的基因。可以更準確。不論 L, U, N 怎麼變化，依照步驟到這裡的全列舉，已經會是很小的範圍了。

結尾

在這個題目中，用了基因演算法，一不小心就在短時間內得到不錯的答案。以找到答案為前提之下，基因演算法可以提供一個初步的探索。而以尋找問題解法為目的的時候，也可以從基因演算法的角度出發，思考基因的最佳演進方向及演進方法。在探求的過程中，把問題的解決方法思考出來，也算是一個很好的訓練解析問題的方法。人工智慧演算法不是沒用，只是式微。跟老兵一樣？

參考：

[1] [https://www.facebook.com/photo.php?fbid=552537671495061&set=gm.10152422989873438&type=1&relevant_count=1&ref=nf]