|
  • 進化計算:設計信息的永動机?

    羅伯特J.馬克斯二世I

     

    進化計算,以達爾文進化論為模型,是种有用的工程器具,能夠創造意想不到、富有見解和聰明的結論。因此,進化計算常被描繪成智能和信息免費資源的形象。然而,實現進化計算程序的設計需要灌輸程序目標相關的隱式信息。這种信息協調進化搜索性能,對成功的搜索進行監管。

     

    計算智能

     

    五十年前,羅斯W.阿什比曾問道:“國際象棋机器能戰胜其制造者嗎?”(《大不列顛科學哲學期刊》,1952年)。今天我們知道确實可以。一個更相關的問題是“計算机程序能生成比輸入信息更多的信息嗎?”進化計算表面來看,似乎是個候選范例。但就“不勞而獲”而言,進化計算不屬于此類范例。

     

    二十世紀60年代進化計算的先驅們主張計算机進化競爭會克服生物實驗室中論證達爾文進化論的一切困難。達爾文進化論的證明“從誕生就有缺陷,因為并沒有發現什么恰當的實驗能夠決定這种進化是可能的以及它是在四處受控的狀態下是如何進展的。”(N.A.巴利塞力,《理論生物學報》,1962年)。“總体來看,通過深思熟慮建立可控制的實驗,使用某一种類的生物器官,檢驗此种類進化論假說通常是不可能或不可行的。我們試圖通過构建代表我們希望研究的進化系統的模型,來部分地繞過這個難點,并使用它們來至少檢驗我們觀點的理論正确性。”(J.L. 克羅斯比, 《進化論研究中的計算机》, 牛津科學進展, 1967年)

     

    工程設計

     

    今天,進化計算很大程度上在工程設計和問題解決領域得到應用。設計以确立目標或設計標的為開始。可行的模型是可以從一系列有利的范式中挑選出來的。設計由所選模型內參數值的識別組成。設計被定義為模型界線內“射程值的明智操作”(蘭德爾吉恩,2005年)。搜索運算法則在計算机輔助下進行該操作。

     

    考慮一個煮雞蛋的方法的簡單例子。我們的問題涵蓋如下几點:

     

    我們是把雞蛋先放在冷水中再煮呢,還是直接把它放在開水中煮呢?(兩种選擇)

    我們要煮多久雞蛋呢?

    我們是把鍋挪開火爐讓水變冷,把雞蛋放在盤子里變冷,還是立刻把雞蛋放在冷水中呢?(三种選擇)

    在第一步有兩种選擇,第三步有三种選擇。就第二步煮雞蛋的時間長短來看,我們假設從三十秒到三分鍾每個十五秒都有一個選擇:0:30, 0:45, 1:00, …, 3:00。在這個時間間隔內共有十一种選擇。因此,可能的方法總共有2x11x3=66种。雖然我們确定了搜索空間,但是仍不能确定設計標准,也就是說,什么是最佳方法呢? 假設我來品嘗雞蛋,就其味道從1到100進行打分。這种對66种方法中的每個都進行的測量,就是方法的适切性。任何分值高于90的方法都符合設計標准。設計目標就是識別滿足設計標准的方法。

     

    假設你從未做過飯,對哪個菜譜最佳沒有絲毫的概念。我們應用伯努利不充分理由原則,即在缺乏任何預先知識之時,我們必須假設所有的菜譜都具有成為最佳菜譜的同等可能性。一個菜譜必須被假定跟別的同樣好。為找到最佳的菜譜,必須將所有66种菜譜都嘗試。找到最佳菜譜的一种方法是反复嘗試。如果這种反复嘗試可以在電腦上進行,試驗就可能很快完成。假設我們在電腦上模擬煮雞蛋和結果的适切性,那么,通過對所有66种菜譜進行評估,我們很快就可以确定哪一种是最佳菜單。查看所有可能的解決方案被稱為窮舉搜索。不幸的是,搜索問題跨度不足,對平均合理尺度的問題并不可行。如果我們有一百個變量,而不只是三個,每個變量又有十种可能的結果,搜索空間元素的數目就成了10^100(即10要自乘100次),這個數目比宇宙中原子的總量還要大。這种情況下,窮舉搜索就不可行了。

     

    在搜索問題上,我們將伯努利僅僅通過向搜索過程灌輸信息的不充分理由原則排除于外。信息可以是顯式的,就拿雞蛋來說吧,化學知識告訴我們把煮熟的雞蛋放在冷水里會推遲最終使雞蛋發出類似硫磺那种气味味道的化學反應。假設硫磺的气味有損于适切性,我們就可以排除一個搜索變量,將搜索總量減少到44個菜譜。反之,信息也可以是隱式的,比如,你可能也知道,十個著名的煮雞蛋手,其中兩個把生雞蛋放在冷水中,其余八個放在開水中。這個信息會引導你將菜譜搜索首先确定在滿足設計標准較大机率的一方。

     

    隱式信息需求

     

    純粹理論上的考慮表明,倘若有足夠快的電腦、足夠長的時間,對一個空間進行搜索是可以成功發現最佳解決方案的。但是,這是“猴子在打字机上”的無稽之談。這個故事理論來說似是而非,認為如果有足夠多的猴子用足夠長的時間隨意擊打鍵盤上的字母,那么歷史上所有偉大的著作都會最終產生。如果有足夠多的猴子用足夠長的時間隨意擊打鍵盤上的字母,那么歷史上所有偉大的著作,諸如《白鯨記》(1,170,200英文字符)、《羅賓漢的故事》(1,435,800英文字符)、《圣經》(詹姆士國王版)(不含空格3,556,480英文字母)都會最終產生。然而,閉合宇宙的有限性使之成為不可能。

     

    在一個龐大非結构化的搜索空間尋找一种簡單的解決方案被稱為“在干草堆中的針”的問題。在大小适度的情況下,基本上是不可行的。從二十六個字母的字母表中隨意選擇字母,寫成《圣經》(詹姆士國王版)的机率是26^3,556,480 = 3.8 10^5,032,323。這個數字极大,非語言所能形容。如果宇宙中所有的物質 (10^58 千克)從大爆炸伊始(200億年)每一秒被轉化成能量(E = mc^2)一百億次,所有的能量被用來發送短信能達到最低的字節限度(即ln(2) kT = 2.9 10^-21 焦爾/字節), 那么在《圣經》(詹姆士國王版)產生之時會有 10^88條短信。如果我們把這個數字与宇宙中原子的數目相乘( 10^78 個原子),會得到10^166條信息,与所需要的10^5,032,323還是相形見絀。

     

    讓我們試個更為适度的問題:短語

     

    IN*THE*BEGINNING*GOD*CREATED(起初,上帝創造)

     

    (我們可以用“天和地”來完成這個短語,但是數字就會變得太大。) 在此,有二十七個可能的字符(二十六個字母和一個空格)和一個長達二十八個字符的字符串。猴子寫成這個句子的机率是27^28 = 1.20 10^40比一. 這個數字不算大,我們能夠想象出來。猴子打二十八個字母和打這兩個特殊單詞的机率与在一万億短吨鐵中找一個原子的机率相同。[使用阿伏加德羅數,我們可以計算2728個原子 (每6.022 10^23原子 1 摩爾)(1摩爾55.845克)(每907,185克1短吨) = 1.22 10^12短吨。]

     

    量子計算机通過開方使同等搜索數量得到減少(HO等,《IEEE TRANS. AUT. CONT. 》, 2003年5月, 第783頁), 但是在閉合宇宙的資源之外問題仍然存在,信息必須要輸入到搜索程序中。

     

    在一個空間結构缺乏強制的非結构性空間即使為很小的問題進行搜索,在計算上也是被禁止的。早期的結构要求包括梯度有效性、适切性二階導數最佳方案依賴性、凸面、單峰适切性函數。(玻爾默曼等,《進化進程的整体性質》,1966年;納什,《順序無約束极小化技術》(修改版),《運籌學》,1998年) 最近,由設計可用性准則強加的隱式信息需求業已受到無免費午餐定理(沃伯特等, 《IEEE TRANS. 進化計算》, 1997年) 的強調,這個定理認為“除非你對所研究的問題有假設在先,否則不管多复雜,沒有什么搜索策略可以比任何其他的策略運行的更好”(HO op. cit.)無免費午餐定理“指出問題的具体知識合并為[最优化或搜索]行為運算法則的重要性。”(沃伯特, op. cit.)

     

    信息來源

     

    進化論搜索的一個共同結构是強加性适切性函數,其中每套參數的設計价值被賦予一個數值。越大越适切,越大越好。最优化問題就是要使适切性函數最大化。補償函數雖然相似,但是要需要最小化。在計算早期,我的工程師同事描述了他作為補償函數藝術家進行搜索時充當的角色。他為發揮其領域專長使補償函數藝術化而感自豪。由設計工程師開發的結构化搜索模型,從某种意義上來說是個好模型。對坏模型的參數進行探查,不管有多徹底,都不會產生可行性設計。相反,通過另一种方式,一個构思聰穎的模型則會以較快的速度產生較好的解決方案。

     

    下面是一個研究結构的簡單例子。讓我們來選擇較為通用、較為常見的字母而不是隨意選擇字母。如果我們隨意選擇字母,那么每個字母都有1/27 = 3.7個百分點被選中。在英語中,字母“e”的使用頻率為10個百分點,空格符則為20個百分點。如果我們根据字母的使用頻率選擇字母,那么在選擇IN*THE*BEGINNING*GOD*CREATED(起初,上帝創造)的可能机率是其原始大小的一百万分之五(0.0005%),從1.2 10^40到5.35 10^34。這個數字仍然很大:一万億吨鐵降到了550万吨。如果我們使用連字頻率,就能降得更低。(連字指經常出現的字母組合;比如,連字“e_”,“_”表示空格,是英語中最為常見的字符配對。)三連字頻率則會使机率降到更低。

     

    探索空間的微調

     

    搜索空間被施加的隱式結构越多,搜索變得越來越容易。而更為有趣的是,對于适度長的信息,如果目標信息并不与搜索空間結构相匹配,信息就不能被發現。(帕普里斯, 《概率》,《隨机變量和隨机程序》,1991年)

     

    探索空間微調定理 帶着產生某种信息的傾向來建构搜索空間。如果目標并不与這种先置傾向相匹配,那么發現的可能性將為零。

     

    這個定理,在不同文本的信息理論中長期流傳、廣為人知,是強大數律的直接推論。比如,如果我們构造一個搜索空間給“e”10個百分點,那么一條長達一万的信息中包含的“e 's”數量將會极其接近1000。全篇沒有一個“e's” 怪書《加斯比》被發現的可能性微乎其微。

     

    构建搜索空間也降低其有效尺度。搜索空間由各可能性次序組成。在一個被构建的空間里,讓我們配上所有會傾向搜索空間子集結构的可能性次序。對于字母表建构頻率,我們所搜尋的所有著名小說,除了《加斯比》,都位于或接近這個子集。

     

    假如搜索空間的結构越多,所加入的信息就越多。譬如,三連字就增加了比連字更多的信息。

     

    逐漸縮小的子集定理 隨着次序長度的增加,隨着所加結构信息的增多,搜索子集元素的百分比會降到零。

     

    因此,不僅构建搜索空間局限于遵循空間結构的解決方案,而且隨着信息長度的增長解決方案的數目在搜索空間所占的比例逐步減小。(同上)

     

    最后的思考

     

    搜索空間要求搜索運算法則的重建要切實可行。這就包含對一個既定的設計目標進行進化搜索。被加入的結构信息需要隱式灌輸到搜索空間,并被用來引導所求結果的處理程序。就某一精确識別階段來說,目標是具体的;或者在其經過的此類有意義的階段諸如拼寫和語法檢查階段,目標又是概括的。無論在何种情況下,還沒有什么永動机能夠設計出進化計算所產生的信息。

     

    簡介: 羅伯特J馬克斯二世是貝勒大學工程學系杰出的工程學教授和研究生主管,電气和電子工程師協會(IEEE)和美國光學學會會員。馬克斯教授曾獲電气和電子工程師協會百年慶典紀念章,在電气和電子工程師協會神經网絡學會和電气和電子工程師協會計算智能學會擔任講師,表現出色。馬克斯博士還擔當過電气和電子工程師協會神經网絡理事會(今學會)的首任主席。其出版物多達300种,多數极好,其中八篇論文被杰出論文集再版。他獲得過三項美國人工神經网絡和信息處理領域專利。