關於矩陣乘法問題的演化算法研究

《關於矩陣乘法問題的演化算法研究》是依託中山大學，由周育人擔任項目負責人的面上項目。

基本介紹

• 中文名：關於矩陣乘法問題的演化算法研究
• 項目類別：面上項目
• 項目負責人：周育人
• 依託單位：中山大學

中文摘要

兩個矩陣的乘積是計算機科學和數學的一個基本運算，確定兩個矩陣乘積所需要的最優（最小）乘法數自然成為算法複雜性理論的重要公開問題之一。本項目研究關於矩陣乘法問題的演化算法，突破目前該問題演化算法研究局限於重現Strassen算法狀態，提出使用演化算法求解矩陣乘法的有限群三積容量問題,以及將矩陣乘法的張量積公式構造問題轉化為一個最佳化問題並使用演化算法通過智慧型搜尋求解，探索改進現有的張量積公式，進而改進矩陣乘法階的上界。針對矩陣乘法問題轉換的最佳化問題具有的高維、高原函式等複雜難解特徵，設計特定的方法減小搜尋空間，如矩陣分塊、分組變異法、合併高斯消除法等；並將這些特定方法與演化算法的編碼表示、參數設定、搜尋運算元和選擇方式等有機結合，以有效地求解矩陣乘法問題。本項目既提出了演化算法關於矩陣乘法問題新的套用，又為計算機科學重要問題-矩陣乘法理論問題研究提供了新的方法和途徑。

結題摘要

矩陣乘法是計算機科學和數學的一個基本運算，確定兩個矩陣乘積所需要的最優乘法數自然成為算法複雜性理論的重要公開問題之一。本項目研究關於矩陣乘法問題的演化算法，提出使用演化算法求解矩陣乘法的有限群三積容量問題，以及將矩陣乘法的張量積公式構造問題轉化為一個最佳化問題並使用演化算法通過智慧型搜尋求解。本項目既提出演化算法關於矩陣乘法問題新的套用，又能為矩陣乘法理論問題研究提供新的方法和途徑。其研究具有重大的理論價值和現實意義。 本項目在2015年1月至2018年12年執行期間，按照原定的研究計畫展開研究，在演化算法在矩陣乘法的套用、以及演化算法的算法設計與理論分析等方面取得了多項重要的研究成果。從理論層面上研究了有限群三積容量問題，利用已有的理論知識證明了TPP三元組的若干新性質；提出了多種高效搜尋算法（包括確定性的快速搜尋算法、隨機搜尋算法、蟻群算法、基於局部搜尋和重啟機制的演化算法）來高效地搜尋TPP三元組，新的高效搜尋算法在有效性、魯棒性和計算效率之間取得了良好的均衡，並能夠有效地解決高階群的三積容量問題，在高階群上尋找到的TPP三元組有望能夠為矩陣乘法的指數提供新的下界；研究了Coppersmith-Winograd算法的偶數階張量積問題，把偶數階張量積的程式建模為一個約束最佳化問題，對其中的4階張量積問題進行了轉化，並利用多目標最佳化技術設計了一種基於支配的約束最佳化演化算法，該研究是將演化算法用於求解矩陣乘法的張量積問題的先行者，並且所設計的算法能夠求出比該問題的已知最優解更優的解。除此之外，本項目還從非支配排序、重組運算元等方面對已有演化算法進行了性能改進，採用不同的關鍵技術構造了多種新型算法框架，並且對各類算法在圖的最大割問題、斯坦納樹問題等問題上的性能表現進行了理論分析。 在項目期間總共發表24篇學術論文，其中有20篇SCI論文。主要成果發表在SCI一區期刊《IEEE Transactions on Evolutionary Computation》、SCI一區期刊《IEEE Transactions on Cybernetics》、CCF-A類期刊《ACM Transactions on Software Engineering and Methodology》等相關領域重要國際刊物上。所完成的研究工作受到國內外同行的關注和引用。