演化,AI的第三條路!(1/2)

演化,AI的第三條路!(1/2)

撰文╱John R. Koza、Martin A. Keane & Matthew J. Streeter|譯者╱鍾樹人|審訂╱李國偉
轉載自《科學人》2003年3月第13期


達爾文式的發明

  • 遺傳規劃利用電腦版本的演化創造出新的發明。這個方法先從數千個隨機產生的檢測物件中,篩選出較好的個體,然後把突變及有性生殖遺傳因子互換等過程應用在這些個體上,以便產生後續的世代。
  • 經過數十個世代後,族群內的個體會愈來愈符合既定的標準。執行到最後,就可收取最好的個體,作為解決問題的答案。
  • 在電子學領域中,這項技術已複製出專利發明,其中有些屬於目前最尖端的研發領域。其他發明包括天線、可識別蛋白質的電腦演算法,以及通用控制器。這些由電腦演化出來的發明中,有些應該可取得專利。
  • 我們預料不出10年,電腦的運算能力應該有足夠的提升,可讓遺傳規劃成為一種常用的桌上型發明機器,並與人類發明家平起平坐地相互競爭。

演化是個強而有力的創造過程。從個別細胞複雜的生化反應到人腦的精密結構,演化所造就的奇蹟,能達到難以想像的複雜度。演化透過突變、有性生殖的遺傳因子重組,以及天擇等數種簡單的過程,反覆進行許多世代之後,完成了豐功偉業。現在,電腦程式設計師也把演化運用在軟體設計上,企圖製造出機器智慧。這項技術稱為「遺傳規劃」(genetic programming),目前已設計出可執行特定功能的電腦程式與電路。

在電子學的領域中,遺傳規劃已經複製出15種先前已取得專利的發明,其中數種當初在各自領域發表時,都被推崇為極具發展潛力的重要發明(見下表)。在現有的這15種發明中,有6種是在2000年1月之後才由大型研究單位取得專利,可見這些發明在兼具科學及實用價值的領域中,代表了目前的尖端研究。這些自動生成的發明中,有些對先前取得專利的發明顯然是侵權,其他的雖然也只是重複先前物件的功能,但是因為是用了新奇的方式達成而被視為新的發明,其中一種甚至比它的先例有明顯的改進。

遺傳規劃也對蛋白質序列進行分類,並在其他各類領域中,製造出足夠與人類較量的成果,譬如天線設計、數學演算法,及通用控制器(見下表)。我們最近才為一種以遺傳方式演化出來的通用控制器申請專利,相較於業界目前慣用的以數學方式推導出來的控制器,我們的控制器性能更為優越。

遺傳規劃第一個實際的商業應用,可能會出現在設計領域。基本上,設計是工程師一天花八小時從事的工作,而演化所做的事也就是設計。設計領域特別適合採用遺傳規劃,因為人們從事設計的目的,是想為難題找出非常好、卻不見得在數學上完美的答案。

一般而言,彼此競爭的考量會引發複雜的取捨過程,而且各個因子之間的最佳平衡狀態,也很難預料。最後,設計通常會變成找尋事物的拓樸排列(而不只是得出一組最佳數字),這正是遺傳規劃十分擅長的工作。

人類工程師看待問題時,經常以理想的數學模型為基礎,所以容易落入窠臼。遺傳規劃的好處,就是不會陷入這種狹窄的思路,演化對於數學原理一無所知,只是單純地試著製造出愈來愈好的結果。因此,我們經常見到演化過程塑造出人類設計師從來不曾想過的、具有原創性的事物。

來自原始的沼澤

不管運用在哪個領域,遺傳規劃都是從「原始的沼澤」開始,沼澤裡包含隨機產生的試驗性「有機體」,以及對有機體所應達成的功能所做的高階描述,也就是用以評估適應度的標準。舉例來說,假設有機體是基本的數學函數,而我們的目的是找出圖形能符合特定曲線的函數。那麼,這個例子裡的有機體,就由數字常數及加減乘除等基本運算所組成。至於函數的適應度,則是視乎函數圖形與目標曲線的符合程度而定。

遺傳規劃程式會評估數學函數族群內每個個體的適應度。由隨機方式製造出來的初始函數,一開始與目標曲線之間的符合度當然會相當低,但其中一些函數的符合度會優於其他函數。遺傳規劃程式往往會去除族群中較差的函數,再把遺傳運算應用在存留下來的函數上,以便製造出函數的後代。最重要的遺傳運算是有性生殖,或稱遺傳因子的「互換」(crossover)。透過這種方式,將適應度較高的有機體彼此配對,就能產出具有親代雙方遺傳物質的後代(見圖一上)。比如,把函數(a+1)-2與1+(a × a)配對,可能促使第一個函數內的(a+1)取代第二個函數內的a,結果產生後代1+[(a+1) × a]。利用這種方式,讓兩個適應度較好的有機體結合彼此的特性,有時可製造出極其優良的後代。

圖一、互換、突變,還是滅絕?(插圖/Bryan Christie Design)

除了有性生殖之外,遺傳規劃也會把大約9%的適應度最好的個體,原原本本地複製到下一代。一般來講,這可確保下一代中最優良的有機體,適應度至少能和上一代媲美。最後,還有大約1%的個體會進行突變。比如說,a+2可能突變為(3 × a)+2。這是希望隨機的改變,能夠進一步改善適應度較高的個體。

上述的遺傳作用,會漸漸改善數學函數族群。這種利用適應度的小變化,讓整個族群在許多世代後發生重大改良的方式,就好像以複利計算小小的利率,可在數十年後讓財富大幅成長一樣。
你可以把這個演化過程,想像成在一個充滿所有可能有機體的空間裡進行搜索。互換運算執行的搜尋方式最具創造力,也因為如此,我們才用互換運算產生每一代裡近90%的後代(見圖一下)。相較之下,突變則傾向在現存的優良個體附近,進行局部搜尋。我們相信,除非是個特別單純的問題,否則太高的突變率,反而會導致演化效率降低。

電腦程式的演化,是個比數學函數複雜的例子。譬如利用迭代法及記憶方式為蛋白質序列進行分類的電腦程式,在此種情況下,遺傳規劃可執行類似生物過程的程序,好比複製基因與刪除基因,以便在演化的程式族群中,製造或刪除子程式、迭代、迴圈與遞迴。演化過程本身會根據解決問題的需要,決定電腦程式的特性及內容。

低通濾波器(low-pass filter)電路就是一個很好的例子,可以讓我們了解遺傳規劃如何設計出類比電路。低通濾波器用於高傳真音響系統,專門傳送極低頻的音波到低音喇叭。想利用遺傳規劃製造出低通濾波器,我們必須指定可用哪些元件來建構電路(比如電阻、電容與感應器),並且定義好候選電路的適應度,就是必須可讓1000赫茲以下的音頻以全功率通過,同時過濾掉高於1000赫茲的所有頻率。

這種製造電路的方式,借用了發育生物學的機制。每個電路一開始就好像一個基本的「胚胎」,包含一個由輸入連接到輸出的線路。這個胚胎電路在建構功能的漸進作用下逐步成長。有些建構功能會在電路中插入特別的元件,有些則會改變不同元件之間的連結模式:譬如可能是複製現有串聯或並聯的電路或元件,也可能把某個點連接到電源、地線,或是增長中的電路裡某個遠處的點。這種發育過程會同時導出電路的拓樸(電路架構的型態),以及有關元件多寡的數值。這個系統可以自動合成電路,卻不必動用到電機工程領域內有關電路合成的任何高階知識。

以這種方式隨機生成的基本電路族群中,大部份個體一開始的作用方式完全不像低通濾波器。但是其中有些電路在輸入及輸出之間存有感應器,因此可輕微阻隔較高音頻的通行。有些電路在輸入及地線之間則存有電容,可稍微吸收掉較高音頻的能量(見圖二)。這類電路被篩選出來配對的機會比其他電路多,結果後來世代中的某些子代就會帶有這兩種特性。針對數值式子的互換與突變運算,能夠調整元件的值,讓截頻點朝向1000赫茲的目標趨近。其他互換與突變作用,則會去除浪費能量的電阻。額外的互換,可以讓感應器與電容的組合成長兩倍或三倍,而製造出AT&T的坎貝爾於1917年取得專利的「階梯結構」。

圖二、低通濾波器的演化(插圖/Bryan Christie Design)

用類似的演化與發育過程組合,也可設計出其他器材。比如天線,就是利用「圖龜」(turtle)自動設計出來的。「圖龜」可根據不同運算的控制(很像LO程式語言的運算),於移動及轉彎時在平面上放下(或不放下)金屬。

用以自動製造控制器的原始材料,包括微分器、積分器與放大器。汽車上的定速控制就是一種基本的控制器,它必須在車速變得太快時減低燃料的進量,或在速度變得太慢時,增加燃料進量。另外,車子對燃料變化的反應會延後,一個好的控制器也必須把這點考慮進去,並且持續監視車速的變化,才能防止車速超過既定目標。通用控制器極為重要,這類控制器可進一步改造,因應各種特定任務的需求,比如用以控制家庭爐灶、工廠製造流程,或是電腦磁碟儲存器的讀寫頭等。小幅改善用以製造控制器的「調諧規則」(tuning rule),都會產生經濟上的龐大節約。

PID控制器是一種常見的控制器,PID三個字母分別代表「比例」(proportional)、「積分」(integral)及「微分」(derivative)三部份。這種控制器於1939年由英國諾夫威治市的帝國化學有限公司的卡倫德與史蒂文森所發明,運用十分廣泛。我們的遺傳規劃程式,已為這個領域演化出兩個明顯的改進。首先,這些程式為PID控制器發展出一組新的調諧規則。從1942年開始,業界就普遍採用一組相當單純而有效的PID控制器調諧規則,這組規則曾在1995年加以改良,不過我們發展出來的調諧規則,比1995年的版本還要好。其次,我們演化出三種新的控制器電路拓樸,性能也比採用舊有調諧規則的PID控制器更好。我們已經為一種採用新規則與新控制器拓樸的應用申請了專利,若如我們所料申請通過,相信那將是第一次由遺傳規劃發明的東西獲得專利。(待續)

(本文由教育部補助「AI報報─AI科普推廣計畫」取得網路轉載授權)

views