程序代碼里的優選實驗

陳凱

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

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

然后，下一代圖形會在上一代圖形的基礎上發生變化，在逐代人工優選操作下，圖形變得越來越像數字“2”（如圖2）。

代碼作用概述

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

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

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

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

新一代的0號個體是2號個體和9號個體的后代，這個0號個體看上去有點像數字“5”而不是數字“3”，不過沒有關系，我們還能以這個個體為藍本，生成另外9個變異的個體，變異方式也是隨機。

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

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

接下來，就可以反復人工選出兩個最優個體，讓它們繁殖生成下一代。

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

實踐、思考與討論

圍繞實現算法的代碼，可以安排一些有趣的實驗，考慮到憑空編寫代碼難度太高，可以引導學習者修改部分代碼并驗證效果。例如，可以將點陣擴大，或者一次繁殖生成更多的個體，讓實驗者能夠選出多個優秀個體來進行基因重組和變異。

下面幾個問題，就值得投入更多時間去思考，相關實驗也涉及到更多的代碼改編量，可以作為研究性、探究性學習的內容。

首先，實驗者可能發現，一個問題是用這段代碼生成直線圖案（如數字1或者7）非常困難，由于隨機變異的作用，圖案的邊緣很難做到平滑齊整，不是這里多一塊，就是那里少一塊，本文的案例中，圖案本質上是由一維字符串直接對應生成的，若要讓遺傳變異生成平滑齊整的邊緣，就不得不考慮每一點與上下左右其他點的關系；另一個問題是每次變異都是以一個點為單位取隨機值，而不是以一塊區域為單位取隨機值，但一維的數據很難對應圖形中的某一塊區域。以上兩個問題，都需要引入二維數組來解決。

其次，對于某些圖案，如數字或字母圖案，空白區域和涂黑區域的分界是很明顯的，圖案中的點最好是要么聚集在一起，要么不要出現，然而案例中的代碼卻無法實現這樣的需求。例如，圖10中的數字“5”，就因為右上側多了一點而不完美。

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

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