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

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

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

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

（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.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

摘要/Abstract

摘要： 矩阵乘法运算作为计算机科学和数学的一个基本运算，在科学研究和工程计算中有着广泛的应用。确定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

庄鹤林, 杨火根, 夏小云, 廖伟志. 关于矩阵乘法问题的人工蜂群优化算法研究[J]. 计算机工程与科学, 2021, 43(12): 2131-2138.

ZHUANG He-lin, YANG Huo-gen, XIA Xiao-yun, LIAO Wei-zhi. Artificial bee colony algorithm for matrix multiplication problem[J]. Computer Engineering & Science, 2021, 43(12): 2131-2138.

参考文献［20］

［1］	Strassen V. Gaussian elimination is not optimal［J］.Numerische Mathematik,1969,13(4):354-356.
［2］	Coppersmith D,Winograd S.Matrix multiplication via arithmetic progressions［J］.Journal of Symbolic Computation,1990,9(3):251-280.
［3］	Winograd S.On multiplication of 2 × 2 matrices［J］.Linear Algebra and its Applications, 1971,4(4):381-388.
［4］	Laderman J D. A non-commutative algorithm for multiplying 3 × 3 matrices using 23 multiplications［J］.Bulletin of the American Mathematical Society,1976,82(1):126-128.
［5］	Kolen J F,Bruce P.Evolutionary search for matrix multiplication algorithms［C］∥Proc of the 14th International Florida Artificial Intelligence Research Society Conference,2001:161-165.
［6］	Oh S,Moon B R.Automatic reproduction of a genius algorithm:Strassen’s algorithm revisited by genetic search［J］.IEEE Transactions on Evolutionary Computation,2010,14(2):246-251.
［7］	Zhou Y,Lai X,Li Y,et al.Ant colony optimization with combining Gaussian eliminations for matrix multiplication［J］.IEEE Transactions on Cybernetics,2013,43(1):347-357.
［8］	Heule M J H,Kauers M,Seidl M.Local search for fast matrix multiplication［EB/OL］.［2019-05-18］.https:∥arxiv.org/pdf/1903.11391.pdf.
［9］	Gao Wei-feng,Liu San-yuang,Huang Ling-ling.Inspired artificial bee colony algorithm for global optimization problems［J］.Acta Electronica Sinica,2012,40(12):2396-2403.(in Chinese)
［10］	Xia Xiao-yun,Zhou Yu-ren.Advances in theoretical research of ant colony optimization［J］.CAAI Transactions on Intelligent Systems,2016,11(1):27-36.(in Chinese)
［11］	Xia X Y,Zhou Y R.Performance analysis of ACO on the quadratic assignment problem［J］.Chinese Journal of Electronics，2018,27(1):26-34.
［12］	Karaboga D.An idea based on honey bee swarm for numerical optimization［R］．Kayseri:Engineering Faculty Computer Engineering Department,Ereiyes University,2005.
［13］	He Yao, Liu Jian-hua,Yang Rong-hua.Survey on artificial bee colony algorithm［J］.Application Research of Computers,2018,35(5):1281-1286.(in Chinese)
［14］	Zang Pei-quan,Sun Chen-ao,Gu Xiao-feng,et al.An artificial bee colony algorithm with adaptive chemotaxis and guiding factors［J］.Computer Engineering & Science,2015,37(9):1692-1697.(in Chinese)
［15］	Pandiri V,Singh A.An artificial bee colony algorithm with variable degree of perturbation for the generalized covering traveling salesman problem［J］.Applied Soft Computing,2019,78:481-495.
［16］	Liu Xiao-fan,Liu Pei-zhong,Luo Yan-min,et al.Improved artificial bee colony algorithm based on enhanced local search［J］.CAAI Transactions on Intelligent Systems,2017,12(5):684-693.(in Chinese)
［17］	Han Yu-yan, Gong Dun-wei, Zhang Yong. An improved artificial bee colony algorithm for the blocking flowshop scheduling problem［J］.
	China Sciencepaper, 2015,10(14):1688-1695.(in Chinese)
［18］	Xia X Y,Zhou Y R.On the effectiveness of immune inspired mutation operators in some discrete optimization problems［J］.Information Sciences,2018,426:87-100.
［19］	Wang Wen-guo,Wu Zong-yue. Improved artificial bee colony algorithm based on congestion concept［J］.Communications Technology,2016,49(7):867-871.(in Chinese)
［20］	Liang Jing,Ge Yu,Ran Xiao-juan,et al.Improved artificial bee colony algorithm［J］.Application Research of Computers,2015,32(11):3295-3299.(in Chinese)
［21］	Deng S,Zhou Y,Min H,et al.Random search algorithm for 2×2 matrices multiplication problem［C］∥Proc of the 3rd International Workshop on Advanced Computational Intelligence,
20	10:409-413.
［22］	Beheshti Z, Shamsuddin S M H,Hasan S.MPSO:Median- oriented particle swarm optimization［J］.Applied Mathematics & Computation,2013,219(11):5817-5836.
［23］	Li J Z,Zheng S Q,Tan Y.Adaptive fireworks algorithm［C］∥Proc of 2014 IEEE Congress on Evolutionary Computation,2014:3214-3221.
	附中文参考文献：
［9］	高卫峰,刘三阳,黄玲玲.受启发的人工蜂群算法在全局优化问题中的应用［J］.电子学报,2012,40(12):2396-2403.
［10］	夏小云,周育人．蚁群优化算法的理论研究进展［J］.智能系统学报,2016,11(1):27-36.
［13］	何尧,刘建华,杨荣华.人工蜂群算法研究综述［J］.计算机应用研究,2018,35(5):1281-1286.
［14］	臧培荃,孙晨骜,顾晓峰,等.具有自适应趋向性和引导因子的人工蜂群算法［J］.计算机工程与科学,2015,37(9):1692-1697.
［16］	刘晓芳,柳培忠,骆炎民,等.一种增强局部搜索能力的改进人工蜂群算法［J］.智能系统学报,2017,12(5):684-693.
［17］	韩玉艳,巩敦卫,张勇.求解随机阻塞批量流水线调度问题的改进人工蜂群算法［J］.中国科技论文,2015,10(14):1688-1695.
［19］	王文国,吴宗月.一种基于“拥挤度”概念的人工蜂群算法改进［J］.通信技术，2016,49(7):867-871.
［20］	梁静,葛宇,冉晓娟,等.一种人工蜂群算法改进方案［J］.计算机应用研究，2015,32(11):3295-3299.

[1]	包敏泽, 胡秀婷, 谢玉莹, 蒋波. 基于人工蜂群算法的p-center问题求解算法[J]. 计算机工程与科学, 2020, 42(06): 1127-1133.
[2]	赵凤1,2，孔令润1,2，马改妮1,2. 多目标粒子群和人工蜂群混合优化的阈值图像分割算法[J]. 计算机工程与科学, 2020, 42(02): 281-290.
[3]	常小刚1，赵红星2. 动态调节因子的邻域搜索人工蜂群算法[J]. 计算机工程与科学, 2019, 41(04): 673-681.
[4]	高雷阜,王飞. 基于混沌更新策略的蜂群算法在SVM参数优化中的应用[J]. 计算机工程与科学, 2017, 39(01): 199-205.
[5]	徐曼舒，汪继文，邱剑锋，王心灵. 基于改进人工蜂群的模糊C-均值聚类算法[J]. J4, 2016, 38(06): 1238-1243.
[6]	黄文明，徐双双，邓珍荣，雷茜茜. 改进人工蜂群算法优化RBF神经网络的短时交通流预测[J]. J4, 2016, 38(04): 713-719.
[7]	臧培荃，孙晨骜，顾晓峰，吴滨，周长喜. 具有自适应趋向性和引导因子的人工蜂群算法[J]. J4, 2015, 37(09): 1692-1697.
[8]	王志刚. 基于动态搜索策略的人工蜂群算法[J]. J4, 2015, 37(04): 734-739.
[9]	刘婷1，张立毅1,2，张晋斌3. 基于分布估计蜂群算法的多用户检测器[J]. J4, 2014, 36(07): 1316-1323.
[10]	王志刚，夏慧明. 求解车辆路径问题的人工蜂群算法[J]. J4, 2014, 36(06): 1088-1094.