李海朋, 李晶皎, 金硕巍, 杨丹
东北大学 信息科学与工程学院, 辽宁 沈阳 110819
收稿日期：2018-04-20
基金项目：国家自然科学基金青年基金资助项目(51607029)。
作者简介：李海朋(1981-), 男, 辽宁沈阳人, 东北大学博士研究生;
李晶皎(1964-), 女, 辽宁沈阳人, 东北大学教授, 博士生导师。

摘要：针对传统遗传算法交叉、变异过程过于繁琐和神经网络在极值判断及收敛速度受限等问题, 提出了一种并行的量子遗传算法优化神经网络权值的算法.首先引入了量子计算的概念, 在量子计算的过程中使用量子旋门实现染色体的训练, 然后引入量子交叉克服了早熟收敛现象, 避免了遗传算法中繁琐的交叉、变异过程.最后设计实现了并行的卷积神经网络, 使用并行量子遗传算法优化了卷积神经网络权值, 实现了并行量子遗传神经网络人脸识别系统.实验结果表明, 相对于原来的遗传算法, 该算法在鲁棒性和实验速度上都有明显的提高.
关键词：多核并行量子计算遗传算法神经网络
Facial Recognition Algorithm Based on Multi-universe Parallel Quantum Genetic Neural Network
LI Hai-peng, LI Jing-jiao, JIN Shuo-wei, YANG Dan
School of Information Science & Engineering, Northeastern University, Shenyang 110819, China
Corresponding author: LI Hai-peng, E-mail: andylip2000@163.com
Abstract: In order to solve the problem that the process of cross and mutation in traditional genetic algorithm is too cumbersome, and the extreme value judgment and the convergence rate is limited, a parallel quantum genetic algorithm(QGA) is proposed to optimize the weights of the neural network. The concept of quantum computing is firstly introduced. In the process of quantum computation, the quantum rotation gate is used to train the chromosomes. Then the quantum cross is introduced to overcome the precocious convergence and to avoid the cumbersome cross and mutation process in the genetic algorithm. Finally, the parallel convolution neural network is designed and implemented. The parallel quantum genetic algorithm is used to optimize the weights of the convolution neural network, and a facial recognition system based on parallel quantum genetic neural network is realized. Experimental results show that compared with the original genetic algorithm, the quantum genetic neural network algorithm has obvious improvements in terms of robustness and processing speed.
Key words: multi-core parallelquantum computinggenetic algorithmneural network
随着现代量子力学的发展, 量子的概念被广泛应用于现代计算机领域.遗传算法是目前用于优化大规模数据求取最优解的经典算法, 将它同量子的概念相结合, 则生成了一种高效的并行量子遗传算法.它不同于传统的遗传算法, 并不以具体的数字或符号来代表遗传算法中的染色体, 而是以量子比特的概率幅来表示染色体的编码.目前量子遗传算法(QGA，quantum genetic algorithm)对于图像处理方面的研究多限于理论, 对现实中多核计算机的针对算法较少.同经典遗传算法相比, 量子遗传算法具有种群样本多样性、全局搜索能力强、计算方法并行性优秀等特点, 但在求解算法优化的问题时, 并未能完全解决收敛速度慢和易陷入局部极值等问题.有大量的学者对QGA的缺陷问题作出了针对性的改进.Zhang等^[1]提出了一种改进的量子遗传算法, 采用一种改进的旋门即H_ε 门对种群中的染色体进行更新, 可以有效地避免早熟收敛.Fu等^[2]则是在文献[1]的研究基础之上提出了一种结合了小生镜淘汰策略的改进型的量子遗传算法, 使得整个种群不断进化直到最优解.Yang等^[3]则提出了一种结合量子宇宙与遗传算法的并行量子遗传算法.而在最近的人脸识别领域，卷积神经网络成为目前最大的热门研究方向.Simonyan等^[4]提出了一种VGG卷积神经网络, 该神经网络最大的缺憾是耗费更多计算资源, 并且使用了更多的参数.而本文提出了一种并行的量子遗传算法来优化VGG神经网络权值的算法, 有效改善了收敛速度和局部极值问题.在实际测试中可以提高整体系统效率的30%~45%.
1 多宇宙并行量子遗传算法并行量子遗传神经网络算法的本质:并行量子遗传算法通过优化并行神经网络的权值和阈值的模式来提高系统效率.量子遗传算法^[5]对比其他优化算法的优势在于引入了量子宇宙的概念, 使之避免了传统遗传算法中繁琐的交叉、变异过程, 取而代之的是相对简单的量子编码和量子旋门策略.使算法达到简洁优化, 避免了繁琐的计算过程.
1.1 量子编码在并行量子遗传神经网络中首先要解决“量子”问题.用量子概念来表示染色体的第一步就需要对具体的染色体数据进行量子编码.在并行量子遗传算法中所采用的是实数编码, 以避免二进制编码带来的编码串过长、神经网络学习精度不高等缺陷.在对比遗传算法中染色体的概念后, 本文提出了并行量子遗传算法中用量子比特来表示染色体的概念.量子比特^[6]是一种随机概率的表述方式, 它表示了多状态叠加的染色体状态, 与传统的量子表示方式不同:传统的量子位采用“0”和“1”两个基本态来描述量子状态，而量子比特采用包括“0”“1”在内的任意态进行线性叠加, 通过最终观测而呈现出“0”“1”态.量子编码是对多状态的基因个体进行编码, 用N个量子比特表示2N个染色体个体, 因此N个量子比特的概率幅可以表示为, 那么含有M个基因染色体的概率可以表示为

(1)

在并行量子遗传神经网络算法中, 采用了经由量子编码后的量子位染色体来表示种群个体, 由于量子编码可以表示任意叠加态的染色体, 所以可以使得算法本身获得良好的收敛性.
在本文中, 并行量子遗传神经网络具体实现如下:
1) 首先定义染色体的数据格式.将VGG网络的权值和阈值按一定的顺序串联，得到预存数组中的分量.
2) 然后定义染色体种群.根据所引用的VGG网络的结构, 将输入层、中间层、输出层间的映射权值按顺序串联成预存数组分量, 再选取N个数组分量组成初始数组, N为染色体量子概率幅的状态数.然后对已经量子编码的染色体群进行量子旋门操作, 以期进一步优化染色体种群.
1.2 量子旋门调整策略在染色体群量子编码之后需要面对的问题就是量子旋门的调整策略问题, 量子旋门是整个染色体群进行演化调整的具体处理器, 也是整个系统的执行中心.其具体执行操作公式为

(2)

式中：α_i和β_i为染色体种群中个体的第i个量子位；θ_i为量子旋转角, 具体大小和方向见表 1.
表 1(Table 1)

表 1 旋转角选择策略Table 1 Choice of rotation angle xi bi f(xi)>f(bi) Δθi s(αiβi) αiβi>0 αiβi < 0 αi=0 βi=0 0 0 False 0 - - - - 0 0 True 0 - - - - 0 1 False δ +1 -1 0 ±1 0 1 True δ -1 +1 0 ±1 1 0 False δ -1 +1 0 ±1 1 0 True δ +1 -1 0 ±1 1 1 False 0 - - - - 1 1 True 0 - - - -

表 1 旋转角选择策略 Table 1 Choice of rotation angle

量子旋转角θ_i=s(α_iβ_i)Δθ_i, s(α_iβ_i)和Δθ_i代表了量子个体旋转方向和旋转角度, 由表 1可知量子旋转角的详细取值范围.本文确定量子旋转角具体数值的主要方法是将量子个体的适应度值f(x_i)与当前的目标值f(b_i)作对比:若前者大于后者, 则调整量子个体中的相应位的量子比特, 使几率幅(α_i, β_i)向着对x_i出现有利的方向演化; 若前者小于后者, 则调整相对应量子比特, 使(α_i, β_i)向着对b_i出现有利的方向演化.
在表 1中, δ代表的是量子个体每次调整的角度大小.δ的值若小会对收敛速度产生影响; 若大会使整个运算结果发散, 过早收敛到局部最优解的位置.所以在本文使用动态调整旋转角的策略:即根据遗传代数的不同, 将δ值的大小在0.1π和0.001π之间动态调整.
多宇宙并行量子遗传神经网络算法采用了量子遗传算法优化神经网络权值方式来优化神经网络的并行算法.量子遗传算法能较快地搜索至神经网络初始权值的最优解附近, 在解空间中定位出一个较好的搜索范围, 而后采用BP神经网络算法使用这个较优的初始权值空间来搜索出待识别的人脸数据的最优解.
1.3 多宇宙间的移民策略和量子交叉在量子遗传算法中最后要解决的就是利用移民策略来进行量子个体交换的问题.在本文所用的QGA算法中, 针对在同一个宇宙内部的量子个体算法采用的是量子旋门调整来搜索最优解, 而在不同的量子宇宙之间则通过采用移民策略来进行量子个体交换, 这样能完整地取得所有的量子个体信息.
本文系统模型为星形宇宙模型^[7], 所采用移民策略为“一对一”模式, 在超星型宇宙模型中一般所采用的移民策略为“一对多”的模式.文中所采用的不同宇宙之间的量子交叉策略如下:
1) 按单个宇宙中染色体种群整体30%概率从染色体种群中选取个体;
2) 对1)中选择的染色体种群分别进行一次测量, 得到一组确定Pa_i和Pb_i, 计算它们的适应度值;
3) 以星形宇宙模型为例, 首先在模型中选取另一个宇宙, 以该宇宙的最终演化目标作为当前个体的演化方向, 然后对选取的量子染色体个体进行一次量子旋门的演化操作;
4) 重复1)~3)操作, 直到全部宇宙都完成量子个体的交叉操作.
本文以星形结构的宇宙模型为例, 宇宙间移民规模选取量子个体全部数目的8%, 移民周期选取每4代移民一次; 不同的宇宙模型之间移民周期为每10代移民一次.量子染色体个体交叉选择概率为30%, 量子染色体个体的变异概率为10%.
2 并行量子遗传神经网络算法研究本文人脸识别系统所采用的训练器是结合量子遗传算法和VGG卷积神经网络的量子遗传神经网络算法, 主要的结合方式是使用量子遗传算法优化卷积神经网络的初始权值, 然后生成多组固定初始权值的VGG卷积神经网络.使用OpenMP和SSE对多组卷积神经网络进行并行优化, 取得最优的卷积神经网络训练器.
2.1 并行量子遗传神经网络算法框架设计本文提出的结合遗传算法优化的卷积神经网络学习方法的基本框架如图 1所示.其中, 卷积神经网络主要由输人层、卷积层、抽样层、全连接层和输出层组成, 其中卷积层和抽样层的数量不定, 由计算任务和计算资源来协调设置.传统卷积神经网络存在的主要问题是学习性能受卷积层和全连接层的初始权重设置的影响较大^[8].针对这一问题, 在本文的卷积神经网络训练过程之初, 对各个卷积层和全连接层的权重使用量子遗传算法优化求解.基本思路是:由这些权重构建量子遗传算法的染色体, 对这些染色体进行量子编码, 然后通过量子旋门的操作来实现初始权值优化.
图 1(Fig. 1)

图 1 结合量子遗传算法的卷积神经网络算法框架Fig.1 Convolution neural network algorithm framework based on quantum genetic algorithm

2.2 VGG卷积神经网络的配置VGG神经网络是由Simonyan和Zisserman实现的卷积神经网络.它最主要的贡献是向人们展示出了网络的深度是算法优良性能的最关键部分^[9].本文所使用的VGG神经网络包含了16个卷积/全连接层.网络的结构非常一致, 从头到尾全部使用的是3×3的卷积和2×2的汇聚，网络结构如图 2所示.
图 2(Fig. 2)

图 2 VGG网络的结构Fig.2 Structure of VGG network

在量子遗传算法优化的卷积神经网络中初始种群中遗传个体染色体的基因记录了相应的模型参数和训练参数, 单个个体其基因序列与神经网络参数中的结构参数相对应, 其中第一层卷积核的数量N₁, 第一层卷积网络的大小为3×3, 第一个抽样层的大小为2×2.第二层卷积核的数量N₂, 第二层卷积网络的大小为3×3, 第二个抽样层的大小为2×2.以此类推VGG共有16层, 正则化因子λ和训练迭代次数I以此对应方式即可获得对应于网络参数的个体基因序列:
2.3 量子遗传算法优化的卷积神经网络算法本文所设计的改进型的量子遗传神经网络人脸识别分类器的基本设计思路是:对上文中初始卷积染色体基因序列进行量子编码, 而后通过量子旋门操作选出N组最优解, 以加权平均的形式选出最后的初始权值.这样通过量子遗传算法来保证神经网络初始权值范围, 避免了局部收敛, 从而克服了神经网络算法对初始权值的依赖.通过这种结合方式改善了算法的收敛性, 大幅提高了算法的整体效率.
并行量子遗传算法优化神经网络权值系数的实现步骤如下:
步骤1? ?通过人脸数据库和待识别人脸来确定神经网络的输入、输出样本集;
步骤2? ?选定卷积神经网络权值系数的量子编码方式;
步骤3? ?对样本空间进行种群规模的设定, 产生初始宇宙种群;
步骤4? ?对步骤3产生的宇宙种群中每一个体进行量子编码;
步骤5? ?通过表 1计算量子旋门的旋转角, 并对种群中的所有个体的概率幅进行量子旋门操作, 得到新一代种群;
步骤6 ? ?对卷积神经网络进行初始训练, 求得N组网络权值所对应的N个网络输出;
步骤7? ?确定好神经网络的目标函数, 然后通过目标函数计算所对应的适应度函数, 利用适应度函数对N个网络进行评价;
步骤8? ?依据步骤7的评价结果在权值样本空间中进行选择操作;
步骤9 ? ?返回步骤4, 直到满足神经网络初始化权值的范围需求, 得到一组优化后的神经网络权系数.
3 对比实验与测试在经过了以上对多维量子遗传神经网络的具体优化分析之后, 本文在多核PC机上进行了具体实验测试.
本次实验所使用的神经网络为上文所述卷积神经网络, 采取多宇宙并行量子遗传算法进行优化.实验中使用ORL人脸数据库, 每人3幅人脸图像共120幅人脸图像用于特征提取, 然后每人5幅共200幅人脸图像用于特征训练, 每人5幅共200幅人脸图像用于人脸识别.实验中首先神经网络分类器采用了两层卷积神经网络作为人脸训练的分类器.输入层节点数是通过PCA算法特征提取出80幅“特征脸”, 由此可确定输入层节点数N₁=80.输出层节点代表人脸识别的最终状态, 由于是针对40个不同个体进行训练, 因此输出层节点数N₃=40.网络的激励函数设定为Sigmoid函数, 学习因子设定为0.5, 训练使用的网络选择为带动量项的神经网络, 动量项因子设定为α=0.5.设定随机数种子为1 270 217 782，占多量子宇宙中交叉个体数目的8%, 移民周期取每隔4代移民一次.最终目标值设定为0.999 9.并行方式采用OpenMP和SSE相结合的方式进行并行优化.
经由系统整体运行结果对比见图 3, 图 4.
图 3(Fig. 3)

图 3 人脸识别系统的运行结果Fig.3 Running results of face recognition system (a)—串行；(b)—使用OpenMP和SSE并行.

图 4(Fig. 4)

图 4 人脸识别系统的各部分运行时间Fig.4 Run time of every part of face recognition system (a)—串行；(b)—使用OpenMP和SSE并行.

将不同模式下的系统运行时间结果对比见表 2.由表 2可知，在同时使用多线程并行(OpenMP)和数据并行(SSE)之后可以将系统整体速度提高5.972倍.由图 4可以看到并行后系统线程的效果提高显著.由此可见经由并行后整体系统运行效果得到极大提升.
表 2(Table 2)

表 2 人脸识别系统的运行时间与运行速度比Table 2 Run time and speed ratio of the facial recognition system 运行 方式 串行 多线程 并行 数据 并行 使用OpenMP 和SSE并行 时间/s 122.609 69.281 32.312 20.531 速度比 1 1.77 3.795 5.972

表 2 人脸识别系统的运行时间与运行速度比 Table 2 Run time and speed ratio of the facial recognition system

4 结语本文提出了一种多宇宙之间并行的量子遗传神经网络算法, 并将之应用于人脸识别算法中.对比单个神经网络的人脸识别系统, 多宇宙并行量子遗传神经网络系统可以有效地在双核计算机上提升效率50%以上, 更可以在四核计算机上提升整体系统训练时间20倍以上.但就识别率而言无论是否使用量子遗传算法优化卷积神经网络最终结果都是90%左右, 这应该和参数设定有关, 若fitness值设定更高则会导致识别率有进一步优化的可能.
参考文献

[1]	Zhang X F, Sui G F, Zheng R, et al. An improved quantum genetic algorithm of quantum revolving gate[J].Computer Engineering, 2013, 39(4): 234–238.
[2]	Fu D S, Zhang R. Research on an improved quantum genetic algorithms[J].Computer Simulation, 2013, 30(12): 321–325.
[3]	Yang J A, Zhuang Z Q, Shi L. Multi-universe parallel genetic algorithms[J].Electronic Journal, 2004, 32(6): 923–928.
[4]	Simonyan K, Zisserman A.Very deep convolutional networks for large-scale image recognition[J].Computer Science, arXiv preprintarXiv: 1409.1556, 2014.
[5]	Gong D W, Sun X Y. Upper bound of crossover and mutation probability of genetic algorithm based on pattern theorem[J].Control and Decision-Making, 2004, 19(5): 554–556.
[6]	Tan C C, Eswaran C. Reconstruction and recognition of face and digit images using autoencoders[J].Neural Comput & Applic, 2010, 19(7): 1069–1079.
[7]	Alyüz N, Gokberk B, Akarun L. Regional registration for expression resistant 3-D face recognition[J].IEEE Transactions on Information Forensics and Security, 2010, 5(3): 425–440.DOI:10.1109/TIFS.2010.2054081
[8]	Hsieh P, Tung P. Shadow compensation based on facial symmetry and image average for robust face recognition[J].Neurocomputing, 2010, 73(13/15): 2708–2717.
[9]	Wang L M, Qiao L L, Wei L J. An optimal learning method of convolutional neural network based on genetic algorithms[J].Computer Engineering and Design, 2017, 38(7): 1946–1950.
[10]	Yang W, Jin L, Tao D, et al. DropSample:a new training method to enhance deep convolutional neural networks for large-scale unconstrained handwritten chinese character recognition[J].Pattern Recognition, 2015, 58(4): 190–203.