2013年12月2日 星期一

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

前言

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

 

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

1391532_552537671495061_279533194_n

圖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]

沒有留言:

張貼留言