• 中国计算机学会会刊
  • 中国科技核心期刊
  • 中文核心期刊

计算机工程与科学 ›› 2021, Vol. 43 ›› Issue (12): 2131-2138.

• 高性能计算 • 上一篇    下一篇

关于矩阵乘法问题的人工蜂群优化算法研究

庄鹤林1,杨火根1,夏小云2,廖伟志2   

  1. (1.江西理工大学理学院,江西 赣州 341000;2.嘉兴学院信息科学与工程学院,浙江 嘉兴 314001)

  • 收稿日期:2020-08-16 修回日期:2020-11-18 接受日期:2021-12-25 出版日期:2021-12-25 发布日期:2021-12-31
  • 基金资助:
    国家自然科学基金(61703183,12161043);浙江省公益技术应用研究计划项目(LGG19F030010);江西省自然科学基金(20192BAB201007)

Artificial bee colony algorithm for matrix multiplication problem

ZHUANG He-lin1,YANG Huo-gen1,XIA Xiao-yun2,LIAO Wei-zhi2   

  1. (1.School of Sciences,Jiangxi University of Science and Technology,Ganzhou 341000;

    2.College of Information Science and Engineering,Jiaxing University,Jiaxing 314001,China)

  • Received:2020-08-16 Revised:2020-11-18 Accepted:2021-12-25 Online:2021-12-25 Published:2021-12-31

摘要: 矩阵乘法运算作为计算机科学和数学的一个基本运算,在科学研究和工程计算中有着广泛的应用。确定2个矩阵乘积所需要的最小乘法数是当今计算机代数中一直未能求解的重要问题之一。通过将矩阵乘法问题建模为一个组合优化问题,采用人工蜂群启发式搜索算法进行矩阵乘法问题求解。对人工蜂群算法进行了改进,给出一种绕圈遍历方法,避免了对同一个解的相同邻域的重复搜索。通过在2×2矩阵乘法问题上的数值实验验证了算法的有效性,所提算法能够快速地找到2×2矩阵分解的乘积方法。


关键词: 快速矩阵乘法算法, Strassen算法, 人工蜂群算法, 劣质解, 绕圈遍历

Abstract: As a basic operation in computer science and mathematics, matrix multiplication is widely used in scientific research and engineering calculation. Determining the minimum number of multipliers required for computing the product of two matrices is one of the most important problems that have not been solved in computer algebra. In this paper, the matrix multiplication problem is modeled as a combinational optimization problem, and then the matrix multiplication problem is solved by the artificial bee colony heuristic search algorithm. An improved artificial bee colony algorithm with a circle traversal method is proposed to avoid repeated searches for the same neighborhood of a solution. The effectiveness of the proposed algorithm is verified by numerical experiments on the 2×2 matrix multiplication problem. Experimental results show that the proposed algorithm can quickly find the product method of 2×2 matrix decomposition.


Key words: fast matrix multiplication algorithm, Strassen algorithm, artificial bee colony algorithm, inferior solution, circle traversal