基于M-AFSA的MPRM逻辑电路面积优化

邵艺璇; 何振学; 周宇豪; 霍志胜; 肖利民; 王翔

doi:10.13700/j.bh.1001-5965.2021.0296

基于M-AFSA的MPRM逻辑电路面积优化

doi: 10.13700/j.bh.1001-5965.2021.0296

邵艺璇^{1, 2},
何振学^{1, 2, ,},
周宇豪^{1, 2},
霍志胜³,
肖利民³,
王翔⁴

1.
河北农业大学河北省农业大数据重点实验室，保定 071001
2.
河北农业大学信息科学与技术学院，保定 071001
3.
北京航空航天大学计算机学院，北京 100191
4.
北京航空航天大学电子信息工程学院，北京 100191

基金项目: 国家自然科学基金青年科学基金(62102130)；河北省自然科学基金(F2020204003)；河北省高等学校科学技术研究项目-青年项目(BJ2019008)；河北农业大学引进人才科研专项(YJ201829)；中央引导地方科技发展资助项目(226Z0201G)

详细信息

通讯作者:
E-mail：hezhenxue@buaa.edu.cn

中图分类号: V443；TP391.72
计量
- 文章访问数: 315
- HTML全文浏览量: 92
- PDF下载量: 16
- 被引次数: 0
出版历程
- 收稿日期: 2021-06-03
- 录用日期: 2021-09-23
- 网络出版日期: 2021-10-29
- 整期出版日期: 2023-03-30

Area optimization of MPRM circuits based on M-AFSA

SHAO Yixuan^{1, 2},
HE Zhenxue^{1, 2
, ,},
ZHOU Yuhao^{1, 2},
HUO Zhisheng³,
XIAO Limin³,
WANG Xiang⁴

1.
Key Laboratory of Agricultural Big Data of Hebei Province，Hebei University of Agricultural，Baoding 071001，China
2.
Information Science and Technology，Hebei University of Agricultural，Baoding 071001，China
3.
School of Computer，Beihang University，Beijing 100191，China
4.
School of Electronic and Information Engineering，Beihang University，Beijing 100191，China

Funds: National Natural Science Foundation for Youth (62102130); Natural Science Foundation of Hebei Province (F2020204003); Hebei Youth Talents Support Project (BJ2019008); Introducing Talent Research Project of Hebei Agricultural University (YJ201829); Central Government Guides Local Science and Technology Development Fund Project (226Z0201G)

More Information

Corresponding author: E-mail：hezhenxue@buaa.edu.cn

摘要

摘要:
现有基于传统智能优化算法的MPRM电路面积优化算法存在效果差的问题。由于MPRM电路面积优化属于组合优化问题，先提出一种多策略协同进化人工鱼群算法（M-AFSA），该算法引入基于反向学习的种群初始化策略，以提高种群多样性及初始种群解的质量；引入觅食与追尾交互性策略，以加强人工鱼个体之间的信息交流、提高所提算法的收敛速度；引入自适应扰动策略，以增加人工鱼个体位置变异的随机性、避免所提算法陷入局部最优。此外，提出一种MPRM逻辑电路面积优化方法，利用所提算法来搜索电路面积最小的最佳极性。基于北卡罗莱纳州微电子中心（MCNC）Benchmark电路的实验结果表明：与遗传算法相比，所提算法优化电路平均面积百分比最高为57.24%，平均为39.57%；与人工鱼群算法相比，所提算法优化电路平均面积百分比最高为33.53%，平均为14.54%；与改进的人工鱼群算法相比，所提算法优化电路平均面积百分比最高为30.25%，平均为13.86%。
- 混合极性Reed-Muller电路 /
- 面积优化 /
- 组合优化 /
- 人工鱼群算法 /
- 反向学习
Abstract:
The existing mixed polarity Reed-Muller (MPRM) circuit area optimization algorithms based on the traditional intelligent optimization algorithms have the problem of poor performance. The MPRM circuit’s area optimization is a combinatorial optimization issue, hence an artificial fish swarm algorithm with many strategies (M-AFSA) is initially suggested. In this algorithm, a population initialization strategy based on reverse learning is introduced to improve the population diversity and the quality of the initial population solution; the interactive strategies of foraging and rearing were introduced to enhance the information exchange between the artificial fish individuals and improve the convergence speed of the algorithm; Adaptive perturbation strategy is introduced to increase the randomness of location variation of artificial fish and avoid the algorithm falling into local optimum. Moreover, we present an area optimization method for MPRM logic circuits, which uses the proposed multi-strategy coevolutionary artificial fish swarm algorithm to search for the optimal polarity with the minimum circuit area. The experimental results based on the MCNC Benchmark circuit show that compared with the genetic algorithm, the maximum area saving percentage obtained by this algorithm is 57.24%, and the average area save percentage obtained by this algorithm is 39.57%. Compared with the artificial fish swarm algorithm, the maximum and average area saving percentages obtained by this algorithm are 33.53% and 14.54%, respectively. Compared with the improved artificial fish swarm algorithm, the maximum and average area saving percentages obtained by this algorithm are 30.25% and 13.86%, respectively.
- mixed polarity Reed-Muller circuit /
- area optimization /
- combinatorial optimization /
- artificial fish swarms algorithm /
- opposition-based learn

HTML全文

图 1 M-AFSA流程

Figure 1. Flow chart of M-AFSA

下载: 全尺寸图片幻灯片

图 2 MPRM电路面积优化方法流程

Figure 2. Flow chart of MPRM circuit area optimization method

下载: 全尺寸图片幻灯片

图 3 8种基准电路最小面积优化曲线

Figure 3. Optimization curves of minimum area of eight reference circuit

下载: 全尺寸图片幻灯片

表 1 最优面积数据

Table 1. Optimal area data

MCNC	In	GA	HGA	AFSA	FEAFSA	M-AFSA	S₁/%	S₂/%	S₃/%	S₄/%
p82	5	2	2	2	2	2	0	0	0	0
pope	6	37	37	37	37	37	0	0	0	0
inc	7	18	18	18	18	18	0	0	0	0
luc	8	6	6	6	6	6	0	0	0	0
exps	8	223	204	204	204	204	8.52	0	0	0
newxcpla1	9	29	28	28	28	28	3.45	0	0	0
prom2	9	84	36	36	36	36	57.14	0	0	0
br1	12	175	156	117	117	117	33.14	25.00	0	0
misex3	14	2215	2079	2415	2079	2079	6.14	0	13.91	0
table3	14	3873	3522	2538	2784	2538	34.47	27.94	0	8.84
table5	17	201	201	2	158	145	27.86	27.86	0	8.23

下载: 导出CSV

表 2 平均面积与平均时间数据

Table 2. Average area and average time data

MCNC	In	GA		HGA		AFSA		FEAFSA		M-AFSA		S₅/%	S₆/%	S₇/%	S₈/%
MCNC	In	A_ave	T_ave/s	A_ave	T_ave/s	A_ave	T_ave/s	A_ave	T_ave/s	A_ave	T_ave/s	S₅/%	S₆/%	S₇/%	S₈/%
p82	5	3.00	0.45	2.00	0.43	2.00	0.19	2.00	0.04	2.00	0.02	33.00	0	0	0
pope	6	42.20	0.51	37.00	0.54	37.20	0.08	37.65	0.21	37.00	0.18	12.32	0	0.54	1.73
inc	7	29.30	0.51	18.33	0.51	23.90	0.04	19.15	0.10	18.35	0.10	37.37	−0.11	23.22	4.18
luc	8	7.80	0.45	6.00	0.47	8.15	0.02	7.60	0.03	6.00	0.02	23.08	0	26.38	21.05
exps	8	275.50	0.91	207.87	0.90	234.75	0.14	241.80	0.17	206.45	0.57	25.06	0.68	12.06	14.62
newxcpla1	9	57.00	1.05	29.87	1.04	33.2	0.52	37.75	1.98	30.05	1.39	47.28	−0.60	9.49	20.40
prom2	9	130.85	0.84	44.00	0.88	68.80	0.23	67.50	0.17	55.95	0.65	57.24	−27.1	18.68	17.11
br1	12	277.40	0.81	176.33	0.81	168.05	0.19	197.75	0.28	142.00	0.38	48.81	19.47	15.50	28.19
misex3	14	3110.45	13.82	2079.00	16.20	2886.55	16.51	2495.90	27.32	2145.35	24.51	31.03	−3.19	25.68	14.05
table3	14	5446.05	675.63	3522.00	1057.66	3092.00	98.47	3392.00	152.21	3038.65	889.99	44.20	13.72	1.73	10.42
table5	17	347.85	24.78	228.93	61.92	198.90	1.90	192.15	3.12	183.75	23.54	47.18	19.74	7.62	4.37

下载: 导出CSV

参考文献(19)

[1]	HE Z X, XIAO L M, GU F, et al. EDOA: An efficient delay optimization approach for mixed-polarity Reed-Muller logic circuits under the unit delay model[J]. Frontiers of Computer Science, 2019, 13(5): 1102-1115. doi: 10.1007/s11704-017-6279-2
[2]	HE Z X, PAN Y H, WANG K J, et al. Area optimization for MPRM logic circuits based on improved multiple disturbances fireworks algorithm[J]. Applied Mathematics and Computation, 2021, 399: 126008. doi: 10.1016/j.amc.2021.126008
[3]	HE Z X, LIU J, XIAO L M, et al. A polarity optimization algorithm taking into account polarity conversion sequence[J]. IEEE Access, 2019, 7: 54809-54818. doi: 10.1109/ACCESS.2019.2911355
[4]	卜登立. 基于混合遗传算法的MPRM最小化[J]. 浙江大学学报(理学版), 2016, 43(2): 184-189. BU D L. Hybrid genetic algorithm for MPRM minimization[J]. Journal of Zhejiang University (Science Edition), 2016, 43(2): 184-189(in Chinese).
[5]	CHEN C D, LIN B, ZHU M, et al. Verification method for area optimization of mixed-polarity reed-muller logic circuits[J]. Journal of Engineering Science and Technology Review, 2018, 11(1): 28-34. doi: 10.25103/jestr.111.04
[6]	俞海珍, 汪鹏君, 张会红, 等. 基于三值多样性粒子群算法的MPRM电路综合优化[J]. 电子学报, 2017, 45(7): 1601-1607. doi: 10.3969/j.issn.0372-2112.2017.07.008 YU H Z, WANG P J, ZHANG H H, et al. Optimization of MPRM circuits based on ternary diversity particle swarm optimization[J]. Acta Electronica Sinica, 2017, 45(7): 1601-1607(in Chinese). doi: 10.3969/j.issn.0372-2112.2017.07.008
[7]	ZONG Y S, HUANG G Y. Application of artificial fish swarm optimization semi-supervised kernel fuzzy clustering algorithm in network intrusion[J]. Journal of Intelligent & Fuzzy Systems, 2020, 39(2): 1619-1626.
[8]	ZHOU X B, YU X, ZHANG Y M, et al. Trajectory planning and tracking strategy applied to an unmanned ground vehicle in the presence of obstacles[J]. IEEE Transactions on Automation Science and Engineering, 2021, 18(4): 1575-1589. doi: 10.1109/TASE.2020.3010887
[9]	LIU Q, ODAKA T, KUROIWA J, et al. An artificial fish swarm algorithm for the multicast routing problem[J]. IEICE Transactions on Communications, 2014, 97(5): 996-1011. doi: 10.1587/transcom.E97.B.996
[10]	FEI T, ZHANG L Y. Application of BFO-AFSA to location of distribution centre[J]. Cluster Computing, 2017, 20(4): 3459-3474. doi: 10.1007/s10586-017-1144-5
[11]	LI M, XU J. An AFSA-inspired vector energy routing algorithm based on fluid mechanics[J]. Tehnicki Vjesnik, 2020, 27(1): 290-296.
[12]	LIU Y, WANG J, SHAHBAZZADE S. The improved AFSA algorithm for the berth allocation and quay crane assignment problem[J]. Cluster Computing, 2019, 22(2): 3665-3672.
[13]	CHEN Y G, ZHU J Y, WAN L, et al. ACOA-AFSA fusion dynamic coded cooperation routing for different scale multi-hop underwater acoustic sensor networks[J]. IEEE Access, 2020, 8: 186773-186788. doi: 10.1109/ACCESS.2020.3029533
[14]	WANG S H, ZHANG Z S, REN Y P, et al. UAV photogrammetry and AFSA-Elman neural network in slopes displacement monitoring and forecasting[J]. KSCE Journal of Civil Engineering, 2020, 24(1): 19-29. doi: 10.1007/s12205-020-1697-3
[15]	LI J P, DONG P W, ZHENG C, et al. PSO-AFSA global maximum power point tracking algorithm with adaptive evolutionary strategy for PV system[C]// Recent Advances in Intelligent Information Hiding and Multimedia Signal Processing. Berlin: Springer, 2019: 60-67.
[16]	李迎, 张璟, 刘庆, 等. 求解大规模多背包问题的高级人工鱼群算法[J]. 系统工程与电子技术, 2018, 40(3): 710-716. doi: 10.3969/j.issn.1001-506X.2018.03.34 LI Y, ZHANG J, LIU Q, et al. Advanced artificial fish swarm algorithm for large scale multiple knapsack problem[J]. Systems Engineering and Electronics, 2018, 40(3): 710-716(in Chinese). doi: 10.3969/j.issn.1001-506X.2018.03.34
[17]	夏平凡, 倪志伟, 朱旭辉. 基于烟花进化人工鱼群算法和多重分形的属性选择方法在空气质量预测中应用[J]. 系统科学与数学, 2020, 40(7): 1157-1177. doi: 10.12341/jssms13917 XIA P F, NI Z W, ZHU X H. Attribute selection method based on fireworks evolution artificial fish swarm algorithm and multi-fractal dimension with its application in air quality prediction[J]. Journal of Systems Science and Mathematical Sciences, 2020, 40(7): 1157-1177(in Chinese). doi: 10.12341/jssms13917
[18]	李晓磊, 钱积新. 基于分解协调的人工鱼群优化算法研究[J]. 电路与系统学报, 2003(1): 1-6. LI X L, QIAN J X. Studies on artificial fish swarm optimization algorithm based on decomposition and coordination techniques[J]. Journal of Circuits and Systems, 2003(1): 1-6(in Chinese).
[19]	RAHNAMAYAN S, TIZHOOSH H R, SALAMA M M A. Opposition-based differential evolution[J]. IEEE Transactions on Evolutionary Computation, 2008, 12(1): 64-79. doi: 10.1109/TEVC.2007.894200