組合29個(gè)簡(jiǎn)單Python代碼塊，自動(dòng)發(fā)現(xiàn)新算法

英特爾的研究人員提出一種新的自動(dòng)算法生成器（AAD），利用演化算法框架，以Python語(yǔ)言的基本子集作為語(yǔ)法架構(gòu)，能夠?qū)?9個(gè)數(shù)組/向量問(wèn)題的代碼塊進(jìn)行組合，通過(guò)學(xué)習(xí)，自動(dòng)生成更復(fù)雜問(wèn)題的解決方案。

本文介紹一種自動(dòng)算法發(fā)現(xiàn)器（AAD），這是一種用于合成高復(fù)雜度計(jì)算程序的演化算法框架。此前的演化算法依賴(lài)于客觀的適應(yīng)函數(shù)，這在給算法設(shè)計(jì)上增加了難度。

本文提出的AAD采用問(wèn)題式引導(dǎo)演化過(guò)程（PGE），這需要將一組問(wèn)題一起引入，針對(duì)更簡(jiǎn)單問(wèn)題發(fā)現(xiàn)解決方案，用于解決同一組問(wèn)題中的更復(fù)雜的問(wèn)題。PGE還支持幾種新的進(jìn)化策略，并自然地應(yīng)用于高性能計(jì)算（HPC）技術(shù)。

AAD可以為29個(gè)數(shù)組/向量問(wèn)題生成Python代碼，范圍從min，max，reverse到更具挑戰(zhàn)性的問(wèn)題，如排序和矩陣向量乘法。此外，AAD顯示出對(duì)受限環(huán)境/受限輸入的強(qiáng)適應(yīng)性，以及針對(duì)“開(kāi)箱即用”的問(wèn)題的解決能力。

AAD是將相對(duì)簡(jiǎn)單的問(wèn)題解決組件自動(dòng)組合程序，可以實(shí)現(xiàn)搜索由這些組件的所有可能排列所組成的整個(gè)空間，然后尋找滿足給定要求的解決方案。目前已經(jīng)提出了許多這樣的搜索策略（例如枚舉，基于演繹，約束求解，隨機(jī)）來(lái)應(yīng)對(duì)這類(lèi)挑戰(zhàn)。

使用AAD的分類(lèi)算法代碼塊示例

本文提出了一種基于演化算法的搜索策略，將其AAD中實(shí)現(xiàn)。AAD可以基于Python的子集作為語(yǔ)法結(jié)構(gòu)，組合成復(fù)雜度相對(duì)較高的程序（循環(huán)，嵌套塊，嵌套函數(shù)調(diào)用等），并生成可執(zhí)行的Python代碼。在本文中使用AAD來(lái)發(fā)現(xiàn)數(shù)組/向量問(wèn)題的算法解決方案。

總的來(lái)說(shuō)，AAD實(shí)現(xiàn)了以下目標(biāo)：

使用問(wèn)題導(dǎo)向型的演化策略來(lái)消除算法中的目標(biāo)函數(shù)。

使用多樣化的演化策略（多環(huán)境解決方案，異花授粉和聯(lián)合演化），并通過(guò)廣泛的實(shí)驗(yàn)評(píng)估其有效性。

利用AAD解決通用Python語(yǔ)言中的29個(gè)數(shù)組/向量問(wèn)題，表明演化算法能夠解決復(fù)雜的新問(wèn)題。

支持循環(huán)模塊，可以發(fā)現(xiàn)任何（非零）輸入的算法。

AAD結(jié)構(gòu)設(shè)計(jì)方案和原理

AAD主要架構(gòu)示意圖，主要由問(wèn)題生成器、解決方案生成器和檢測(cè)器組成

問(wèn)題生成器（ProbGen）

我們想要解決的每個(gè)問(wèn)題都從問(wèn)題生成器開(kāi)始。這部分負(fù)責(zé)：（1）指定輸入和輸出的數(shù)量和類(lèi)型。（2）為給定的問(wèn)題生成輸入。例如，對(duì)于最大查找（Max），問(wèn)題生成器指定Max將一個(gè)數(shù)組作為輸入，并生成一個(gè)數(shù)字作為輸出。另外，當(dāng)請(qǐng)求為大小為N的問(wèn)題生成輸入時(shí)，會(huì)產(chǎn)生一個(gè)由N個(gè)數(shù)字組成的輸入數(shù)組。

檢測(cè)器（Checker）

檢測(cè)器負(fù)責(zé)接受/拒絕為給定問(wèn)題生成解決方案。檢測(cè)器使用問(wèn)題生成器生成的輸入執(zhí)行生成的程序，并生成輸出。檢測(cè)器中包含接受/拒絕輸出的邏輯。因此，檢測(cè)器與給定的問(wèn)題生成器對(duì)應(yīng)，兩者齊頭并進(jìn)。

檢測(cè)器不一定真正需要實(shí)現(xiàn)其想要發(fā)現(xiàn)的算法。比如，針對(duì)“排序問(wèn)題”的檢測(cè)器不必對(duì)真的對(duì)輸入數(shù)組進(jìn)行排序，而是可以比較輸出數(shù)組中的每?jī)蓚€(gè)相鄰元素，并查看這兩個(gè)元素是否按預(yù)期順序排列。一旦檢測(cè)到未排序數(shù)據(jù)對(duì)，檢測(cè)器會(huì)做出“失敗”的聲明。如果每對(duì)相鄰元素都是有序的，并且輸出數(shù)組中包含的元素與輸入數(shù)組完全相同，則檢測(cè)器宣布可接受該解決方案。

解決方案生成器（SolGen）

SolGen主要由兩部分組成：（1）表達(dá)式/短語(yǔ)存儲(chǔ)，以及（2）演化器。

表達(dá)式/短語(yǔ)存儲(chǔ)器（ExpStore）

解決方案生成器使用語(yǔ)法構(gòu)造源程序。AAD使用的Python語(yǔ)法子集存儲(chǔ)在ExpStore中，如表1所示。在AAD中，語(yǔ)法規(guī)則使用類(lèi)型信息進(jìn)行擴(kuò)充。

AAD支持四種數(shù)據(jù)類(lèi)型：數(shù)字（NUM），布爾數(shù)（BOOL），數(shù)組（ARR）和數(shù)組的數(shù)組（AoA），它們可以對(duì)矩陣進(jìn)行建模。此外，表達(dá)式的每個(gè)操作數(shù)都標(biāo)記為Consumer（只讀），Producer（只寫(xiě)）或ProdCon（讀-修改-寫(xiě)）。

演化器（Evolver）

演化器負(fù)責(zé)對(duì)表達(dá)式和短語(yǔ)進(jìn)行組合，以生成程序（或函數(shù)），以解決問(wèn)題生成器提出的問(wèn)題。演化器分三個(gè)階段構(gòu)建解決函數(shù)（SolFunc）。

階段1：構(gòu)建解決函數(shù)

階段2：在“生產(chǎn)者”（只寫(xiě)數(shù)據(jù)）和“消費(fèi)者”（只讀數(shù)據(jù)）間建立聯(lián)系

階段3：操作和函數(shù)調(diào)用突變

檢查輸出

一旦解決函數(shù)構(gòu)建出來(lái)，就會(huì)執(zhí)行這個(gè)函數(shù)，使用Python的exec（）函數(shù)生成輸出結(jié)果。檢測(cè)器負(fù)責(zé)檢查輸出，判定接受或拒絕輸出。如果第一個(gè)輸出被接受，則使用問(wèn)題生成器生成的更多不同大小的、與輸入測(cè)試相同的解決函數(shù)。如果檢測(cè)器接受了所有測(cè)試，則該解決函數(shù)即被聲明為該問(wèn)題的解決方案。上述三個(gè)階段構(gòu)成了一個(gè)循序漸進(jìn)的步驟。

上表所示為在問(wèn)題集A中的調(diào)用者-被調(diào)用者的關(guān)系。比如SortDesc函數(shù)所在的行顯示，SortAsc在57％的解決方案中調(diào)用了Max函數(shù)，在14％的解決方案中調(diào)用了Min函數(shù)，以此類(lèi)推。Min，Max和ReverseArr函數(shù)沒(méi)有調(diào)用任何其他函數(shù)。所有其他函數(shù)都依賴(lài)于一個(gè)或多個(gè)函數(shù)來(lái)得到解決方案，顯示出函數(shù)組合的重要性。

上表中列出了3組問(wèn)題以及在基線方法下的步數(shù)表現(xiàn)，并將其與四種演化策略下的表現(xiàn)進(jìn)行了對(duì)比。

未來(lái)前景與應(yīng)用方向

從概念上講，AAD也可用于程序翻譯。對(duì)于用C語(yǔ)言，匯編語(yǔ)言甚至二進(jìn)制語(yǔ)言編寫(xiě)的程序，可以執(zhí)行該實(shí)例作為AAD的檢測(cè)器來(lái)生成Python（或類(lèi)似語(yǔ)言）代碼。這種方式與僅通過(guò)觀察另一個(gè)對(duì)象行為，來(lái)構(gòu)建自身行為方式的機(jī)器學(xué)習(xí)算法類(lèi)似。很明顯，本文中使用的Python代碼可以被視為“Python到Python”的翻譯，因?yàn)椴煌臋z測(cè)器對(duì)應(yīng)了不同的Python實(shí)現(xiàn)。

AAD可能不僅僅是一個(gè)程序合成器。它還可以用來(lái)獲取機(jī)器的內(nèi)在知識(shí)。通過(guò)調(diào)用-被調(diào)用關(guān)系圖和父子圖捕捉不同問(wèn)題之間的內(nèi)在關(guān)系。這些關(guān)系是由AAD本身發(fā)現(xiàn)的，并且可以被認(rèn)為是不同操作之間的聯(lián)想記憶的一種表示，其形式與人類(lèi)大腦構(gòu)造和機(jī)制類(lèi)似。

由于AAD可以通過(guò)引入越來(lái)越多的問(wèn)題來(lái)增加知識(shí)儲(chǔ)備的擴(kuò)展，通過(guò)適當(dāng)?shù)闹笇?dǎo)機(jī)制，就可以引導(dǎo)系統(tǒng)獲取大量技能（算法），并自己構(gòu)建知識(shí)表示。就像我們?cè)谧约汉⒆舆€小時(shí)，向TA們提出許多問(wèn)題和挑戰(zhàn)，目的是為了引導(dǎo)孩子們獲得大量技能和知識(shí)。

AAD是用于綜合高復(fù)雜度程序的演化框架，它以Python語(yǔ)言的基本子集作為語(yǔ)法架構(gòu)。使用AAD能夠?qū)?9個(gè)數(shù)組/向量問(wèn)題的代碼塊進(jìn)行組合，其中既有最大值、最小值，矩陣翻轉(zhuǎn)這類(lèi)簡(jiǎn)單問(wèn)題，也有更具挑戰(zhàn)性的問(wèn)題，如排序和矩陣向量乘法等，對(duì)于輸入沒(méi)有大小限制。

我們?cè)u(píng)估了解決這些問(wèn)題策略的有效性，并證明了AAD具備解決“開(kāi)箱即用”問(wèn)題的能力。為了應(yīng)對(duì)復(fù)雜需求帶來(lái)的各種挑戰(zhàn)，AAD工具還能實(shí)現(xiàn)與高性能計(jì)算（HPC）技術(shù)的結(jié)合?？偟膩?lái)說(shuō)，與現(xiàn)有技術(shù)相比，采用PGE的演化算法能夠解決類(lèi)似或更高復(fù)雜性的問(wèn)題。