基于量子遗传算法优化的空间魔法波形装置动态网格坐标误差分析

张凌寒，陆思良

基于量子遗传算法优化的空间魔法波形装置动态网格坐标误差分析

张凌寒，陆思良

（安徽大学 电气工程与自动化学院，合肥 230601）

研究了一种基于量子遗传算法的空间魔法波形装置的动态网格坐标误差优化计算。空间魔法波形是一种由等长木棍在三维空间拼接成动态网络并由绳索驱动的用于科普演示的装置，木棍网络的每个节点坐标的计算对于装置整体的设计和组装有重要意义。引入一种将量子计算概念（量子态、量子门、量子状态特性、概率幅等）融合到传统遗传算法中的优化算法——量子遗传算法，用量子位表示基因，再利用量子信息的叠加性使每个量子位表达基因的可能性相同，进而通过基因位的旋转完成基因的变异，每次完成变异后判断适应度是否满足条件，满足条件的解将持续更新，在不停地迭代计算下求出最终的最优解。利用量子遗传算法计算变化后的空间魔法波形木棍网络节点的坐标比使用传统遗传算法和蒙特卡洛算法时的平均精度分别降低了0.0270%和0.0458%，该算法的使用提高了在机械设计、制造工艺、计量测试中坐标求解的精度。

量子遗传算法；空间魔法波形；凸轮机构；坐标误差优化计算；适度函数

坐标误差是机械工程、力学等相关学科的重要影响因素，并且一直是机械设计、制造工艺、计量测试中的重要研究内容。坐标误差中的优化分析问题通常采用智能算法解决，如：遗传算法。这是一种借鉴生物学中遗传、突变、自然选择和杂交等现象的优化算法，具有收敛性好、过程简单等优点。它不仅应用于坐标误差的分析优化，还成功应用于很多领域的优化问题，沙勇[1]设计了一种基于遗传算法的机器人路径规划方案，更好地解决了机器人实际路径优化问题；陈昊等[2]提出一种基于混合遗传算法下的有轨制导车辆动态调度模型，对不同方案求解时的实用性和有效性更强；金昕等[3]设计了一种改进的多种群遗传算法，在集成车间调度模型中更快地得到更好的优化调度结果。

因传统遗传算法存在搜索时间长，交叉变异过于随机等不足，鉴于此，本文引入量子遗传算法（Quantum Genetic Algorithm，QGA）这一种将量子计算与遗传算法相结合的智能优化算法，它具有随机性小、鲁棒性高等优点，将量子态、量子门、量子状态特性、概率幅等量子领域的概念，融合到传统的遗传算法中，用量子位表示基因，再利用量子信息的叠加性使每个量子位表达基因的可能性相同，进而通过基因位的旋转完成基因的变异，每次完成变异后判断适应度是否满足条件，满足条件的解将持续更新，在不停地迭代计算下求出最终的最优解。近年来，量子遗传算法在优化领域的应用比起传统遗传算法更加广泛，赵辉[4]提出了基于混合量子遗传算法的外贸企业物流配送车辆优化调度算法，可以更好地进行车辆路径规划能力；凌煜凡等[5]研究了量子遗传算法在反应堆流量分区问题上的收敛性分析，相比于传统的遗传算法能更快地搜索到最优分区结果；周浩等[6]提出一种基于量子遗传算法的耕地系统安全评价方法，为长株潭地区耕地保护及社会经济高质量发展提供理论支撑；黄景光等[7]提出了一种基于量子遗传算法的阻抗修正时的限过流保护方法，能够有效提升保护过程中的选择性和速动性；缪麟等[8]提出了一种基于量子遗传算法的离轴反射光学系统设计方法，为自由曲面离轴反射光学系统提供像质良好、特定布局的初始结构；冯建鑫等[9]利用量子遗传算法对模糊自整定PID控制器参数进行优化，提高了系统的动态性能和适应性。

本文基于空间魔法波形这一装置，用量子遗传算法进行装置的坐标误差优化计算，凸显量子遗传算法相比于传统遗传算法的优势，同时也可以给相关机构设计和开发提供新思路。

1 问题分析

1.1 空间魔法波形动态网格的结构

空间魔法波形是一种由等长木棍在三维空间拼接成动态网络结构，并由凸轮机构和绳索驱动的用于科普演示的装置。竖直轴凸轮机构与水平轴凸轮机构相同，放置在相互垂直的方向上。木棍网络的每个节点竖直方向系有驱动绳索，绳索驱动的上下伸缩由水平和竖直两个方向的凸轮机构的周期运动合成。等长木棍网格机构由多根长度、质量相同的木棍，头尾相接或呈90°角相连组成一个网络，且每根木棍可围绕连接处做一定幅度摆动，通过绳索驱动装置带动每个节点进行幅度不同的伸缩，形成一个曲面，进行坐标误差优化计算的坐标正是基于此曲面。装置如图1所示，主要包含从上到下的4个部分：（1）水平轴凸轮机构；（2）竖直轴凸轮机构；（3）绳索驱动结构；（4）等长木棍网格结构。

图1 一种9×9木棍网络结构的空间魔法波形

图2 凸轮的结构参数示意图

1.2 装置的运动原理

水平凸轮机构和竖直凸轮机构运动原理相同，皆是通过凸轮的转动拉扯圈状绳索，进而带动可活动杆来回运动，最终引起木棍网络中节点抬升的高度不同，形成不同的曲面。凸轮运动到如图3(a)所示位置时，绳索被向下拉扯，进而带动可活动杆向右移动；当凸轮运动到图3(b)所示位置时，绳索被拉扯的幅度较小，此时可活动杆相对于图3(a)时的位置向左移动。

图3 凸轮绳索驱动杆运动示意图

木棍网络发生变化后，每个节点上升的高度可以进行精确计算。如图4所示，以靠外侧的一根绳索为例，最上端竖直绳索固定层与水平轴凸轮机构的距离为1，水平轴凸轮机构与竖直轴凸轮机构之间的距离为2，竖直轴向杆与等长木棍网络之间的距离为，从最上端竖直绳索固定层到下端木棍网络的绳索总长度不变：

原连接处A0上升到移动后的连接处A1的距离Δ为

1.3 木棍网络的坐标误差来源

由于木棍组成的网络具有不可压缩性，因此网格从平面变成曲面时，在水平投影上会存在整体收缩现象。如图5所示，计算得知，长度为1.6m的网格形成截面为正弦波的曲面时，两端分别有0.032 m的收缩。为此，精确计算每一个木棍网络节点的实际空间位置及其坐标误差优化计算对于演示装置的设计和组装有重要意义。鉴于木棍网络节点数目较多，且收缩变形在三维空间中出现，因此通过解析建模的方法计算坐标十分困难。为此，本文采用量子遗传算法进行网格曲面节点的坐标误差优化计算，并用传统遗传算法和蒙特卡洛算法同时求解节点坐标进行精度对比。

图5 网络整体收缩趋势示意图

2 基于量子遗传算法的坐标误差分析

2.1 量子遗传算法

量子遗传算法[10]是一种基于量子计算的遗传算法，在遗传编码中引入量子的态矢量，用量子逻辑门来实现染色体的演化，进而实现目标优化的算法。

量子叠加态是QGA的基础，其中一个量子比特的叠加态的表示为

QGA的最小单元是一个量子比特，一个染色体可以由如下矩阵表示：

每个量子被观测后，由和组成的量子比特叠加态马上随机变成0态或者1态，基因也因此变成二进制形式，且最小单位为1个比特，只能取到0或者1，式(4)中代表的染色体长度可以用×来表示。

QGA中量子门更新的作用可对比传统遗传算法中的变异或交叉操作，效果类似。量子门在演化操作中扮演执行机构这一角色，执行机构种类有很多，为适配量子遗传算法的计算特点，选择量子旋转门这一执行机构，其计算方法为

将量子比特（式(5)）右乘式(7)，更新旋转角度，得到新的量子比特，计算过程如下：

旋转角使用的是一种与优化问题无关的、通用的调整策略，如表1所示。

表1 旋转角策略选择

QGA的步骤：

(4)记录下最优的个体和其相对应的适应度；

(5)判断计算过程是否可以结束，若满足终止条件，则停止，否则继续进行计算；

(8)利用量子旋转门对个体进行调整，得到一个新种群；

(9)记录下最优的个体和其相对应的适应度；

(10)迭代次数加1，返回步骤(5)。

量子遗传算法求解流程如图6所示。

图6 量子遗传算法求解流程

2.2 坐标误差优化计算

为更加准确地进行木棍网络所形成的动态网格的坐标误差优化计算，建立了各节点位置发生变化之前的初始状态模型。设置轴为横轴，轴为纵轴，为了方便坐标轴设计和计算，让整个结构上下颠倒，也就是绳子从=0这个平面上“下垂”到=4左右的平面上，如图7所示。

图7 木棍网络初始状态

每个凸轮的运动轨迹函数融合成木棍网格结构的三维曲面函数，随着凸轮的运动和绳索驱动装置的带动，每个点的位置会随之发生变化，但竖直绳索长和木棍网络中每个木棍的长度不变，这也是求解节点实际坐标过程中的限制条件。网格是9×9规格，即9行9列，81个点，64个网格。为了方便节点的表示，给每个节点标记序号，按照从左到右，从上到下依次标记为1到81，木棍网络的俯视图和节点的序号标记如图8所示。

鉴于每个节点时刻在运动，且这些节点的运动又互相关联，因此需要假设木棍网络中心的节点没有伸缩变形，即木棍网络中心的绳索恒定为垂线，此时，可根据限制条件由内而外的逐个求解节点的坐标。求解的限制条件包括：(1)每根竖直绳索长度不变；(2)相邻节点与节点之间的空间距离（即连接相邻两节点之间的木棍长度）。此外，还需给上述限制条件设置合理的误差范围，本文设置的误差为0.001 m，即1mm，若计算求解过程中，节点坐标误差在所设置误差范围之内，则认为该解满足条件。

2.3 适度函数和目标函数

量子遗传算法中使用适应度[12]这个概念来度量群体中全部个体在进行优化计算时可能达到或接近于最优解的好坏程度。适应度比较高的个体就有相对较高的概率遗传到下一代；而适应度较低的个体只有相对较小的概率遗传到下一代。度量个体适应度的函数被称为适应度函数（Fitness Function）。遗传算法中以个体适应度的大小评定各个个体的优劣程度，从而决定其遗传机会的大小。

图8 9×9木棍网络的俯视图及节点序号

目标函数是用变量表示的目标形式，本文的目标函数Fit()：

图9 节点25与节点24、34的空间距离在z=0平面的投影

在本文中，目标函数总取非负值，并且是以求函数最小值为优化目标，故可直接利用目标函数值作为个体的适应度。目标函数的值越趋近于0，适应度就越高，求得的节点坐标就越准确。节点41的投影即原点的坐标已知，为求得全部的节点坐标，需先求投影在坐标轴上的节点坐标，从节点41开始往四周求其余各节点的坐标。

3 结果分析

本文在用量子遗传算法优化计算实际坐标的过程中，经实验测试200代左右进化曲线收敛，所以设置每次运算500代，以确保更准确，而且为了结果更具有代表性，选取4个象限的点作为代表，以下是点25、31、65、81坐标在500代计算后的进化曲线。

图10 点25坐标的量子遗传算法进化曲线

图11 点65坐标的量子遗传算法进化曲线

图12 点31坐标的量子遗传算法进化曲线

图13 点81坐标的量子遗传算法进化曲线

本文还以传统遗传算法和蒙特卡洛算法[13]（Monte Carlo Method，MCM）求得的坐标作为对比。蒙特卡洛算法是一种数值模拟算法，把概率现象作为研究对象，对于统计性质的问题可以直接解决，所求解的误差与问题维数无关，可以比较快速且直接地求出大致结果。在使用蒙特卡洛算法求节点坐标时，在给定范围的三维立方体空间中随机生成一个坐标，通过计算生成所有满足前文两点限制条件的坐标后，再做平均，以平均坐标作为所求点的实际坐标，和量子遗传算法求得的更为精细的坐标对比。

表2是使用3种算法计算得到的点25、31、65、81的实际坐标及误差。因为绳长是不变的，所以坐标误差可以用求得的实际坐标的竖坐标值和绳长计算表示：

表2 量子遗传算法与蒙特卡洛法求解点25、31、65、81坐标及误差

4 结论

针对空间魔法波形木棍网络形成的动态网格坐标求解及误差分析，以最大精度为优化目标，提出一种基于量子遗传算法的坐标误差优化计算方法，并得到如下结论：

量子遗传算法相比于传统的遗传算法搜索时间短，交叉变异操作相对稳定的优点，将量子的态矢量表达引入遗传编码，利用量子逻辑门来实现染色体的演化，取得了比传统遗传算法更好的效果，弥补了因个别数值的选取而引起的算法不收敛这一不足，增加了算法的鲁棒性；以空间魔法动态网格坐标误差最小为优化目标，以另外两种算法求得的坐标和绳长进行误差对比，结果显示，3种算法的平均误差分别为0.0155%、0.0425%、0.0613%，利用量子遗传算法计算的坐标比传统遗传算法和蒙特卡洛法的平均误差分别降低了0.0270%和0.0458%，提高了坐标求解的精度。

[1] 沙勇. 基于遗传算法机器人路径规划研究[J]. 齐齐哈尔大学学报（自然科学版），2021, 37(05): 55-56, 66.

[2] 陈昊，梅学婷，苏晓艳，等. 基于混合遗传算法下的RGV动态调度模型[J]. 齐齐哈尔大学学报（自然科学版），2019, 35(05): 8-14, 30.

[3] 金昕，王雷. 基于多种群遗传算法的AGV约束的柔性作业车间调度研究[J]. 常州工学院学报，2021, 34(01): 16-21.

[4] 赵辉. 基于混合量子遗传算法的外贸企业物流配送车辆优化调度[J]. 齐齐哈尔大学学报（自然科学版），2021, 37(01): 26-30, 5.

[5] 凌煜凡，代圣齐，赵鹏程，等. 铅铋反应堆堆芯流量分区智能优化方法研究[J]. 核动力工程，2022, 43(03): 53-57.

[6] 周浩，胡凌，陈竹书. 基于量子遗传投影寻踪的长株潭地区耕地系统安全评价[J]. 农业机械学报，2022, 53(08): 268-274, 302.

[7] 黄景光，李浙栋，张宇鹏，等. 计及后备保护优化级数的改进阻抗修正反时限过流保护整定方法[J]. 电网技术，2022, 46(07): 2768-2777.

[8] 缪麟，田博宇，孙年春，等. 基于量子遗传算法的自由曲面离轴反射光学系统设计[J]. 红外与激光工程，2021, 50(12): 303-311.

[9] 冯建鑫，王强，王雅雷，等. 基于改进量子遗传算法的超声电机模糊PID控制[J]. 吉林大学学报（工学版），2021, 51(06): 1990-1996.

[10] 陈恒宇，丁唯一，殷寰宇，等. 基于量子遗传算法的回焊炉参数设定[J]. 重庆理工大学学报（自然科学），2021, 35(09): 248-55.

[11] 马书民，戎子睿，林湘宁，等. 计及多类装置协同的直流偏磁治理设备全局优化配置研究[J]. 中国电机工程学报，2020, 40(14): 4387-4399, 4720.

[12] 吉建华，苗长云，李现国，等. 基于PSO带式输送机PID控制器参数智能整定的适应度函数设计[J/OL]. 机械工程学报：1-13[2022-11-23].http://kns.cnki.net/kcms/detail/11.2187.TH.20220526.1849.118.html.

[13] 朱宇，赵祥模，徐志刚，等. 基于蒙特卡洛模拟的无人车高速公路变道虚拟测试场景自动生成算法[J]. 中国公路学报，2022, 35(03): 89-100.

Analysis of dynamic grid coordinate error of spatial magic waveform device based on quantum genetic algorithm optimization

ZHANG Ling-han，LU Si-liang

(School of Electrical Engineering and Automation, Anhui University, Hefei 230601, China)

In this paper, the optimal calculation of dynamic grid coordinate error for a kind of spatial magic waveform device based on quantum genetic algorithm (QGA) is studied. The space magic waveform is a dynamic network of equal-length wooden sticks stitched together at the 3D and driven by ropes for popular science demonstrations. The calculation of the coordinates of each node of the stick network is very important for the design and assembly of the whole device. The QGA optimization algorithm integrates the concepts of quantum computation (quantum states, quantum gates, properties of quantum states, probability amplitudes, etc.) into the traditional genetic algorithm. The superposition of quantum information leads to a fact that each qubit expression gene has the same possibility, and then the gene variation can be completed through the rotation of the qubit. In each completion of the mutation, the variated gene judges whether the fitness meets the conditions. The solution is updated continuously to satisfy the condition, and the final optimal solution is obtained by iterative calculation. Experimental results indicate that average error of the proposed QGA method decreases by 0.0270% and 0.0458% as compared with that of the traditional genetic algorithm and Monte Carlo method, respectively. The proposed algorithm shows great potentials in the optimization calculation in the fields of mechanical design, manufacturing process, and measurement.

quantum genetic algorithm；space magic waveform；cam mechanism；coordinate error optimal computation；fitness function

TH13

A

1007-984X(2023)03-0006-08

2022-11-23

国家自然科学基金（52075002）

张凌寒（1999-），男，山东烟台人，本科，主要从事机电系统设计研究，Z21301152@stu.ahu.edu.cn。

陆思良（1987-），男，广西钦州人，博士，副教授，主要从事工业自动化研究，silianglu@ahu.edu.cn。