遺傳程式設計服務和自動程式設計服務

武漢大學軟體工程國家重點實驗室 康立山 陳毓屏 李元香

自動程式設計是電腦科學的中心目標之一。早在1959年,Arthur Samuel就指出,自動

程式設計涉及的問題是怎樣使電腦去做所需做的事,而無須精確地告訴它怎樣去做。30多

年來,人們一直在為實現自動程式設計而奮鬥。

1992年,美國Stanford大學的J.Koza出版了專著《遺傳程式設計(Genetic Programming

:On the Programming of Computers by Means of Natural Selection)》,介紹用自然選擇

的方法進行電腦程式設計。1994年,他又出版了《遺傳程式設計(二):可重用程式的自動發

現(Genetic Programming II:Automatic Discovery of Reusable Programs)》,開創了用遺

傳演算法實現程式設計自動化的新局面,為程式設計自動化帶來了一線曙光。

遺傳程式設計已引起電腦科學與技術界的關注,並有許多應用。

一、遺傳程式設計

遺傳程式設計是學習和借鑒大自然的演化規律、特別是生物的演化規律來解決各種計算

問題的自動程式設計的方法學。為了闡述什麼是自動程式設計,我們先引入程式結構(Progr

am Structure,PS)的概念。

1976年,N.Wirth曾用下面的公式來表示電腦程式:演算法+資料結構=程式(Algorithms+

Data Structures=Programs)。因此,一個電腦程式可以用一個S(運算式)或一棵樹來表示

。例如,計算f(x)=(x+0.1×sin2x)/cos 的程式的運算式為:(2x×sin0.1×x+xcos/)。

從程式樹結構表示可以看出,一個電腦程式是由兩種基本程式集合的元素複合而成的

。一個是運算集合,如樹中的非葉節點:+、-、×、/(算術運算)與cos、sin(函數運算),它們

用來描述一個演算法;另一個是資料集合,如樹中的葉節點:2、0.1、x(INTEGER、REAL),它們用

來組成資料結構。

我們把一種程式設計語言的運算集合(包括其內部函數及副程式庫)記作O,把它的資料集

合(包括資料結構)記作D。任何一種程式設計語言都必須提供其運算集合O與資料集合D。程

序設計語言越高級,所提供的運算集合與資料集合的內容越豐富,且運算集合與資料集合的複

合映射形成的程式成份也越複雜。從程式樹來看這種複合映射的例子,+、-、×、/都是二元

運算,即(a+b)、(a-b)、(a×b)與(a/b)。

我們把一種程式設計語言的程式結構定義為它的運算集合與資料集合的複合體,即PS=O

οD。由於D中可包含邏輯型與字元型等資料,O中可包含(ifthen)與while等操作,所以程式結構包含了該語言的全部基本程式成份,反映了該語言的全部功能。一個問題的程式結構由該問題的資料結構及求解問題的演算法來決定,它通常是PS的一個子集合。也就是說,一個問題的求解程式只使用該語言的部分功能。

Koza選擇Lisp作為GP的程式設計語言。有了程式結構的概念,在前文介紹的演化演算法的

基礎上,即可討論自動程式設計(Automatic Programming,AP)。可以用下面的公式來概括自

動程式設計的思想:EA+PS=AP(演化演算法+程式結構=自動程式設計)。

Holland的標準遺傳演算法中的遺傳群體是由一些二進位字元串組成的;而GP或AP的遺傳群

體是由一些電腦程式組成的,即由PS的元素形成的程式樹組成。AP從以PS的元素隨機地構成電腦程式的原生軟體開始,應用畜牧學原理繁殖一個新的(常常是改進了的)電腦程式群體。這種繁殖應用達爾文的"適者生存、不適者淘汰"的原理,以一種領域無關的方式(EA)

進行,即模擬大自然中的遺傳操作:複製、雜交(有性重組)與變異。雜交運算用來創造有效的

子代程式(由PS的元素組成);變異運算用來創造新的程式,並防止過早收斂。所以,AP就是把

PS的高階語言符號表示與EA的智慧演算法(一種以適應性驅動的、具有自適應、自組織、自學

習與自優化特徵的高效隨機搜索演算法)結合起來,即AP=EA+PS。一個求解(或近似求解)給定問題的電腦程式往往就從這個過程中產生。

下面給出GP繁殖求解問題的電腦程式的步驟:

(1)用問題的運算(∈O)與資料(∈D)隨機地複合(即用PS的元素)產生一個初始電腦程

序群體。

(2)迭代地實施下述步驟,直到滿足終止條件。

(1)執行群體中的每個程式,並根據其適應性給它指定一個適應值。

(2)應用下述三種遺傳運算元創建一個新的電腦程式群體(這些運算元作用在那些根據其適

應概率從已有群體中選出來的個體上)。

·繁殖:複製一個已有的電腦程式到新群體中。

·雜交:從兩個已有程式中隨機地選其部分進行重組,創造兩個新的程式加到新群體中。

·變異:隨機改變一個現存程式的隨機選取部分,創造一個新程式加到新群體中。

(3)從電腦程式群體中識別最好的程式,作為這次運行GP的結果,它可能是問題的一個

解或近似解。

上述過程是實現自動程式設計的基本框架,對不同的問題,它們的差別可以很大。首先,

對不同的問題,其運算集合與資料集合不同。Koza分別稱之為問題的函數集合F與端點集合T

,一般有F O與T D。一般說來,問題的程式結構越簡單,即|F|與|T|越小,問題的程式空間

越小,GP求解也就相對容易一些。

程式空間的完備性建立在程式結構的完備性理論的基礎上。一個問題的程式結構一般是

該程式語言的程式結構的一個子集。這方面有許多理論問題需要進一步研究。

驅動程式不斷演化的動力是根據適應函數給群體中的每個電腦程式評分,即計算其適

應值。它通常由一組訓練資料(輸入,輸出)來測試。成功率高的個體,其適應值也高。針對不

同問題選取合理的適應函數是使AP獲得成功的一項關鍵技術。

為了提高自動程式設計的效率,Koza引入了一種關鍵技術:自動定義函數,以實現可重用

程式的自動發現。

二、遺傳程式設計的並行處理

平行計算技術的發展為自動化程式設計提供了物質基礎。遺傳程式設計的內在並行性為

高效地利用平行計算最新成就來實現程式設計自動化提供了可能。自動程式設計是以計算智

能來取代人的智能。應用EA進行自動程式設計的代價是電腦資源的高消費。

現在來分析前面描述的用GP繁殖電腦程式的演算法的並行性。演算法的控制參數如下:

·電腦程式群體的規模N(即群體所含程式個數)。

·遺傳運算元的分佈概率:繁殖概率Pr,雜交概率Pc與變異概率Pm。

·演化的代數g。

演算法的並行度取決於問題的群體規模N。演算法的粒度取決於程式長度、程式測試集的大

小、程式評估方法及遺傳運算元的計算複雜性等。

演算法的性質除依賴於並行度與粒度外,也依賴於遺傳運算元的分佈概率Pr、Pc與Pm。由於

它們一般均大於零,所以演算法不是完全同步的。

從演算法的計算步驟可以看出,產生初始群體的過程是完全並行的,並行度=N。計算個體的

適應值也是完全並行的,並行度=N。進行遺傳操作的過程也是完全並行的,但由於雜交運算是

對兩個個體進行的,所以並行度≤N。

由此可見,該演算法是非同步並行的,所以適合在大規模MIMD電腦系統及分散式電腦系統

上執行。Koza在電路自動設計中採用的最大群體規模N=64萬,遺傳運算元的概率分別為Pr=10%

,Pc=89%,Pm=1%。他們用一台由64個PowerPC 601(80MHz)處理機組成的中等粒度的並行Pary

stec電腦系統執行,64個處理機每個計算1萬個個體,所以這種方法稱作分散式演化演算法。

由此可見,用大規模並行MIMD系統來實現自動程式設計是高效率的,即可充分發揮大規模

平行電腦系統在自動程式設計中的作用。實際上,規模較大的問題,其自動程式設計一般只

有採用並行處理方式才可能完成。遺傳程式設計演算法是平行計算環境下的產物。可以預言,

自動程式設計方法將隨著平行計算的飛速發展而發展。

三、自動程式設計的實例

在第三屆IEEE演化計算國際會議上,Koza等發表了一篇論文,以細胞自動機、分子生物學

與電子電路合成等問題為例,將GP演化出的電腦程式與人編寫的程式進行比較。對這些問

題,他們用GP演化出來的電腦程式產生的結果比人對同一問題編寫的程式的結果還要好一

些。他們較詳細地介紹了GP是怎樣解決電子電路合成問題的,如交叉濾波器(低頻揚聲器與高

頻揚聲器)的設計、低通濾波器和放大器的設計,以及非對稱帶通濾波器的設計。應用GP既演

化出了所期望的電子電路拓撲,也演化出了每個元件的規格。

下面介紹武漢大學軟體工程國家重點實驗室提出的複雜系統演化建模理論,他們應用自

動程式設計研製成功了基於演化計算的自適應複雜函數建模軟體。該軟體具有"計算智慧"—自適應、自組織、自學習和自優化的功能。用戶只需提供樣品資料表{(xi1,xi2,…,xin,

yi);(i=1,2,…,m)}及所期望模型的精度,無需提供任何數學知識,應用智慧建模軟體,電腦

即可自動給出滿足用戶需求的數學模型。

例如, 應用該軟體做三峽大壩處的岩石結構分析時, 所給的資料如下:

@@27107000.GIF;表1@@

用戶要求由此找到五類岩石結構y與它們的移動率x1、結合率x2、強度x3、變形係數x4

的關係。電腦求得下述模型:

@@27107001.GIF;算式1@@

f2(x)=1.69+x1-x42+0.258x3-1

f3(x)=2+x1-x4+0.225x3-1

f4(x)=ln(5.09x2+0.39+12.78x1/x3)

f5(x)=exp(1.50(cos x3-cos x1)+cos(1.7132))

由電腦找到的這五個模型,都滿足用戶要求的精確度,這是數學家與岩土力學家很難構

思出來的。有人把該軟體稱為"傻瓜建模軟體",使用該軟體就像使用"傻瓜相機"一樣。因此

,遺傳程式設計給程式設計自動化帶來了一線曙光。