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

项目名称： 关于矩阵乘法问题的演化算法研究

项目编号： No.61472143

项目类型： 面上项目

立项/批准年度： 2015

项目学科： 自动化技术、计算机技术

项目作者： 周育人

作者单位： 中山大学

项目金额： 80万元

中文摘要： 两个矩阵的乘积是计算机科学和数学的一个基本运算，确定两个矩阵乘积所需要的最优（最小）乘法数自然成为算法复杂性理论的重要公开问题之一。本项目研究关于矩阵乘法问题的演化算法，突破目前该问题演化算法研究局限于重现Strassen算法状态，提出使用演化算法求解矩阵乘法的有限群三积容量问题,以及将矩阵乘法的张量积公式构造问题转化为一个优化问题并使用演化算法通过智能搜索求解，探索改进现有的张量积公式，进而改进矩阵乘法阶的上界。针对矩阵乘法问题转换的优化问题具有的高维、高原函数等复杂难解特征，设计特定的方法减小搜索空间，如矩阵分块、分组变异法、合并高斯消除法等；并将这些特定方法与演化算法的编码表示、参数设置、搜索算子和选择方式等有机结合，以有效地求解矩阵乘法问题。本项目既提出了演化算法关于矩阵乘法问题新的应用，又为计算机科学重要问题-矩阵乘法理论问题研究提供了新的方法和途径。

中文关键词： 演化计算；计算智能；矩阵乘法

英文摘要： 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.

英文关键词： evolutionary computation;computational intelligence;matrix mulplication