程序代碼里的優(yōu)選實(shí)驗(yàn)

陳凱

算法對(duì)世界的巨大改變無(wú)可否認(rèn)，然而對(duì)于知識(shí)技術(shù)水平有限的初學(xué)者來說，某些算法具體實(shí)現(xiàn)的復(fù)雜性確實(shí)令人望而生畏，即便大致了解了某個(gè)著名的算法的基本原理，或者在工作、生活中使用到了該算法的成果，也很難從代碼實(shí)現(xiàn)的角度去體驗(yàn)、實(shí)證算法的作用，更遑論要結(jié)合實(shí)際問題做需求分析并編寫出有實(shí)用價(jià)值的程序了。以遺傳算法為例，它涉及到情境創(chuàng)設(shè)、基因編碼、適應(yīng)度函數(shù)評(píng)分、選擇函數(shù)設(shè)置、基因重組、基因變異等諸多步驟，且每個(gè)步驟都對(duì)應(yīng)著相當(dāng)多的程序代碼量，教學(xué)者的任務(wù)一方面是盡量嘗試設(shè)計(jì)簡(jiǎn)單有趣的任務(wù)情境，另一方面是將復(fù)雜的算法自頂向下分解成小任務(wù)，通過每個(gè)小任務(wù)的編碼實(shí)證，讓學(xué)習(xí)者體會(huì)這一段代碼所體現(xiàn)出來的思想方法。上一期文章《程序代碼里的遺傳》所介紹的內(nèi)容重點(diǎn)在于如何將情境創(chuàng)設(shè)和基因編碼過程變得有趣形象，本期文章所介紹的活動(dòng)內(nèi)容，是在人工干預(yù)的條件下，讓隨機(jī)圖形變得越來越像某種圖形，重點(diǎn)在于如何將基因重組變異的過程直觀顯現(xiàn)出來。

為了簡(jiǎn)單起見，筆者在本文的例子中，用8×8的點(diǎn)陣組成簡(jiǎn)單的圖形，希望借助人工選擇，使得初始的隨機(jī)生成圖形一代代產(chǎn)生變化，并越來越像某個(gè)數(shù)字。例如，一開始的時(shí)候，圖形可能是如圖1所示的樣子。

然后，下一代圖形會(huì)在上一代圖形的基礎(chǔ)上發(fā)生變化，在逐代人工優(yōu)選操作下，圖形變得越來越像數(shù)字“2”（如圖2）。

代碼作用概述

實(shí)驗(yàn)中被栽培的“物種”個(gè)體就是這個(gè)由8行8列星號(hào)組成的圖形（注意并不是每個(gè)星號(hào)都代表一個(gè)個(gè)體），該物種個(gè)體生長(zhǎng)的模樣和它的基因有關(guān)，為了簡(jiǎn)化問題，筆者直接用一個(gè)64位由空格和星號(hào)組成的字符串代表基因，圖形生成也很簡(jiǎn)單，只要將作為基因的每8個(gè)字符換行打印即可。

從上頁(yè)圖3代碼中可以看出，物種個(gè)體基因的64個(gè)字符完全是隨機(jī)生成的。seed函數(shù)的作用是生成不同的隨機(jī)種子，實(shí)驗(yàn)時(shí)，也可以改變seed函數(shù)的參數(shù)來得到不同的隨機(jī)序列；randint函數(shù)的作用是生成具體的隨機(jī)整數(shù)，括號(hào)里的參數(shù)是0和1，于是得到的隨機(jī)數(shù)不是0就是1；arr數(shù)組的作用是存放10個(gè)不同個(gè)體的基因。最后，用print語(yǔ)句將字符串以數(shù)組的形式，分8行打印出來，打印出的圖案如上頁(yè)圖4所示。

這10個(gè)圖案的形狀完全是隨機(jī)的，可以借助人工選擇操作來有傾向性地改變它們后代的模樣。雖然說真正的遺傳算法需要進(jìn)行適應(yīng)度評(píng)分，但本文例子的重點(diǎn)是觀察遺傳變異中物種的演化，所以就以人工選擇的方式來大幅度簡(jiǎn)化問題。假如生成圖形的最終目標(biāo)是“3”，那么可以優(yōu)選兩個(gè)看上去已經(jīng)具備有發(fā)展成“3”潛質(zhì)的圖形，如圖4中的2號(hào)個(gè)體圖形和9號(hào)個(gè)體圖形，選擇完成后，程序代碼會(huì)將這兩個(gè)個(gè)體的基因進(jìn)行混合。

從圖5代碼中可以看出，兩個(gè)基因混合的方法也很簡(jiǎn)單，如果兩個(gè)基因的同一位字符是相同的，那就繼續(xù)繼承這個(gè)字符，如果兩個(gè)基因的同一位字符不同，那就以各百分之五十的概率，隨機(jī)生成一個(gè)字符。通過這個(gè)方法得到0號(hào)個(gè)體并打印出來（如圖6）。

新一代的0號(hào)個(gè)體是2號(hào)個(gè)體和9號(hào)個(gè)體的后代，這個(gè)0號(hào)個(gè)體看上去有點(diǎn)像數(shù)字“5”而不是數(shù)字“3”，不過沒有關(guān)系，我們還能以這個(gè)個(gè)體為藍(lán)本，生成另外9個(gè)變異的個(gè)體，變異方式也是隨機(jī)。

為了能夠在教學(xué)中將基因重組和變異兩個(gè)概念分別講述，案例中重組和變異的代碼明顯分成兩段，實(shí)際上，變異也可以直接在基因重組時(shí)發(fā)生，那樣就更接近現(xiàn)實(shí)中的遺傳變異現(xiàn)象。從圖7代碼中可以看出，大部分的基因會(huì)按原樣繼承下去，但小部分基因，存在一定概率發(fā)生變異。想象一下，如果沒有變異現(xiàn)象，那么每個(gè)個(gè)體都會(huì)被固化在初始的形狀中，這樣也就失去了進(jìn)化的可能。

另外，下一代個(gè)體的變異最好要具有一定差異，從而能呈現(xiàn)出多樣性的發(fā)展。為了能夠體現(xiàn)變異的差異性，此處做了一個(gè)十分簡(jiǎn)單的設(shè)定：從1號(hào)個(gè)體到9號(hào)個(gè)體，編號(hào)小的個(gè)體基因中空格多，而編號(hào)大的個(gè)體基因中星號(hào)多（如下頁(yè)圖8）。

接下來，就可以反復(fù)人工選出兩個(gè)最優(yōu)個(gè)體，讓它們繁殖生成下一代。

用以體驗(yàn)遺傳算法的代碼就此完成，筆者用它來生成了四個(gè)不同的數(shù)字（如下頁(yè)圖9）。

實(shí)踐、思考與討論

圍繞實(shí)現(xiàn)算法的代碼，可以安排一些有趣的實(shí)驗(yàn)，考慮到憑空編寫代碼難度太高，可以引導(dǎo)學(xué)習(xí)者修改部分代碼并驗(yàn)證效果。例如，可以將點(diǎn)陣擴(kuò)大，或者一次繁殖生成更多的個(gè)體，讓實(shí)驗(yàn)者能夠選出多個(gè)優(yōu)秀個(gè)體來進(jìn)行基因重組和變異。

下面幾個(gè)問題，就值得投入更多時(shí)間去思考，相關(guān)實(shí)驗(yàn)也涉及到更多的代碼改編量，可以作為研究性、探究性學(xué)習(xí)的內(nèi)容。

首先，實(shí)驗(yàn)者可能發(fā)現(xiàn)，一個(gè)問題是用這段代碼生成直線圖案（如數(shù)字1或者7）非常困難，由于隨機(jī)變異的作用，圖案的邊緣很難做到平滑齊整，不是這里多一塊，就是那里少一塊，本文的案例中，圖案本質(zhì)上是由一維字符串直接對(duì)應(yīng)生成的，若要讓遺傳變異生成平滑齊整的邊緣，就不得不考慮每一點(diǎn)與上下左右其他點(diǎn)的關(guān)系；另一個(gè)問題是每次變異都是以一個(gè)點(diǎn)為單位取隨機(jī)值，而不是以一塊區(qū)域?yàn)閱挝蝗‰S機(jī)值，但一維的數(shù)據(jù)很難對(duì)應(yīng)圖形中的某一塊區(qū)域。以上兩個(gè)問題，都需要引入二維數(shù)組來解決。

其次，對(duì)于某些圖案，如數(shù)字或字母圖案，空白區(qū)域和涂黑區(qū)域的分界是很明顯的，圖案中的點(diǎn)最好是要么聚集在一起，要么不要出現(xiàn)，然而案例中的代碼卻無(wú)法實(shí)現(xiàn)這樣的需求。例如，圖10中的數(shù)字“5”，就因?yàn)橛疑蟼?cè)多了一點(diǎn)而不完美。

盡管它的下一代還會(huì)變異，然而即便這個(gè)多余的點(diǎn)消失了，其他空白處仍然有一定概率冒出不合適的點(diǎn)來。所以有必要改變代碼，讓點(diǎn)的生成和消失與周邊點(diǎn)存在一定依賴，從而使得某些區(qū)域的圖案保持更多穩(wěn)定性；然而，為了在變異中獲得一定的多樣性，又要允許某些個(gè)體的區(qū)域變化有比較大的隨意性。兩者如何平衡，是個(gè)很大的研究課題。

最后一個(gè)問題大概是最重要的：如果沒有人工選擇，計(jì)算機(jī)怎樣才能知道哪些圖案更像數(shù)字？這其實(shí)是在問，怎么編寫一個(gè)適應(yīng)度函數(shù)，讓那些看上去像數(shù)字的圖案評(píng)分更高？對(duì)于這個(gè)問題，最簡(jiǎn)單的處理方法是，預(yù)先建立一個(gè)數(shù)字圖案的點(diǎn)陣，借助代碼逐個(gè)比對(duì)各個(gè)像素是否相同，由此給出適應(yīng)度評(píng)分。但仔細(xì)一想，卻發(fā)現(xiàn)這樣做除了可以作為算法設(shè)計(jì)及代碼編寫訓(xùn)練的實(shí)例外，沒有什么現(xiàn)實(shí)價(jià)值，因?yàn)榧热粓D案已經(jīng)被規(guī)定好了，又為什么要讓遺傳算法再費(fèi)時(shí)費(fèi)力地去生成相同的圖案？人們的真實(shí)需求，大致是希望代碼能自動(dòng)識(shí)別出圖形中的數(shù)字吧。然而，這個(gè)問題不是單純的遺傳算法能夠解決的，它和圖像識(shí)別、大數(shù)據(jù)等領(lǐng)域的知識(shí)產(chǎn)生了關(guān)聯(lián)，等待著懷有好奇心的學(xué)習(xí)者去深入探索研究。endprint