关于矩阵乘法问题的演化算法研究

The product of two matrices is a basic operation in computer science and mathematics, and finding the optimal value of the exponent of square matrix multiplication is naturally one of the most important open problems in algebraic complexity. This project aims at designing evolutionary algorithms to solve the optimization problem introduced by the exponent of square matrix rather than to reproduce Strassen algorithm. We present an evolutionary algorithm for triple product property triples which can be used to bound the exponent of matrix multiplication. We also will convert the construction of tensor form of matrix multiplication into a combinatorial optimization problem, which may be used to get a bound on the exponent of square matrix multiplication. Since the difficulty in solving this optimization problem is caused by problem dimension and plateau objective function, we will develop problem-specific methods such as partitioned matrix, group mutation and combining Gaussian eliminations to decrease the objective function value and shrink the search space. Then we incorporate problem-specific methods with algorithmic features of evolutionary algorithms, e.g. parameter setting, representations, search operations and selection, with the ultimate goal of designing efficient evolutionary algorithms for the matrix multiplication problem. This project presents a new application of evolutionary algorithms and provides a new method to investigate the exponent of matrix multiplication.

两个矩阵的乘积是计算机科学和数学的一个基本运算，确定两个矩阵乘积所需要的最优（最小）乘法数自然成为算法复杂性理论的重要公开问题之一。本项目研究关于矩阵乘法问题的演化算法，突破目前该问题演化算法研究局限于重现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》等相关领域重要国际刊物上。所完成的研究工作受到国内外同行的关注和引用。