英特爾“演化算法”新框架：29個Python代碼塊，自動生成新算法

本文介紹一種自動算法發現器（AAD），這是一種用於合成高複雜度計算程序的演化算法框架。此前的演化算法依賴於客觀的適應函數，這在給算法設計上增加了難度。

本文提出的AAD採用問題式引導演化過程（PGE），這需要將一組問題一起引入，針對更簡單問題發現解決方案，用於解決同一組問題中的更復雜的問題。 PGE還支持幾種新的進化策略，並自然地應用於高性能計算（HPC）技術。

AAD可以為29個數組/向量問題生成Python代碼，範圍從min，max，reverse到更具挑戰性的問題，如排序和矩陣向量乘法。此外，AAD顯示出對受限環境/受限輸入的強適應性，以及針對“開箱即用”的問題的解決能力。

AAD是將相對簡單的問題解決組件自動組合程序，可以實現搜索由這些組件的所有可能排列所組成的整個空間，然後尋找滿足給定要求的解決方案。目前已經提出了許多這樣的搜索策略（例如枚舉，基於演繹，約束求解，隨機）來應對這類挑戰。

使用AAD的分類算法代碼塊示例

本文提出了一種基於演化算法的搜索策略，將其AAD中實現。AAD可以基於Python的子集作為語法結構，組合成複雜度相對較高的程序（循環，嵌套塊，嵌套函數調用等），並生成可執行的Python代碼。在本文中使用AAD來發現數組/向量問題的算法解決方案。

總的來說，AAD實現了以下目標：

• 使用問題導向型的演化策略來消除算法中的目標函數。
• 使用多樣化的演化策略（多環境解決方案，異花授粉和聯合演化），並通過廣泛的實驗評估其有效性。
• 利用AAD解決通用Python語言中的29個數組/向量問題，表明演化算法能夠解決複雜的新問題。
• 支持循環模塊，可以發現任何（非零）輸入的算法。

AAD結構設計方案和原理

AAD主要架構示意圖，主要由問題生成器、解決方案生成器和檢測器組成

問題生成器（ProbGen）

我們想要解決的每個問題都從問題生成器開始。 這部分負責：（1）指定輸入和輸出的數量和類型。（2）為給定的問題生成輸入。例如，對於最大查找（Max），問題生成器指定Max將一個數組作為輸入，並生成一個數字作為輸出。另外，當請求為大小為N的問題生成輸入時，會產生一個由N個數字組成的輸入數組。

檢測器（Checker）

檢測器負責接受/拒絕為給定問題生成解決方案。 檢測器使用問題生成器生成的輸入執行生成的程序，並生成輸出。檢測器中包含接受/拒絕輸出的邏輯。因此，檢測器與給定的問題生成器對應，兩者齊頭並進。

檢測器不一定真正需要實現其想要發現的算法。比如，針對“排序問題”的檢測器不必對真的對輸入數組進行排序

解決方案生成器（SolGen）

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

表達式/短語存儲器（ExpStore）

解決方案生成器使用語法構造源程序。 AAD使用的Python語法子集存儲在ExpStore中，如表1所示。在AAD中，語法規則使用類型信息進行擴充。

AAD支持四種數據類型：數字（NUM），布爾數（BOOL），數組（ARR）和數組的數組（AoA），它們可以對矩陣進行建模。此外，表達式的每個操作數都標記為Consumer（只讀），Producer（只寫）或ProdCon（讀-修改-寫）。

演化器（Evolver）

演化器負責對錶達式和短語進行組合，以生成程序（或函數），以解決問題生成器提出的問題。演化器分三個階段構建解決函數（SolFunc）。

• 階段1：構建解決函數
• 階段2：在“生產者”（只寫數據）和“消費者”（只讀數據）間建立聯繫
• 階段3：操作和函數調用突變

檢查輸出

一旦解決函數構建出來，就會執行這個函數，使用Python的exec（）函數生成輸出結果。檢測器負責檢查輸出，判定接受或拒絕輸出。如果第一個輸出被接受，則使用問題生成器生成的更多不同大小的、與輸入測試相同的解決函數。如果檢測器接受了所有測試，則該解決函數即被聲明為該問題的解決方案。上述三個階段構成了一個循序漸進的步驟。

上表所示為在問題集A中的調用者-被調用者的關係。比如SortDesc函數所在的行顯示，SortAsc在57％的解決方案中調用了Max函數，在14％的解決方案中調用了Min函數，以此類推。Min，Max和ReverseArr函數沒有調用任何其他函數。所有其他函數都依賴於一個或多個函數來得到解決方案，顯示出函數組合的重要性。

上表中列出了3組問題以及在基線方法下的步數表現，並將其與四種演化策略下的表現進行了對比。

閱讀更多 編程python新視野 的文章

關鍵字: 英特爾 設計 算法