基于量子遺傳算法優化的空間魔法波形裝置動態網格坐標誤差分析

張凌寒，陸思良

基于量子遺傳算法優化的空間魔法波形裝置動態網格坐標誤差分析

張凌寒，陸思良

（安徽大學 電氣工程與自動化學院，合肥 230601）

研究了一種基于量子遺傳算法的空間魔法波形裝置的動態網格坐標誤差優化計算?？臻g魔法波形是一種由等長木棍在三維空間拼接成動態網絡并由繩索驅動的用于科普演示的裝置，木棍網絡的每個節點坐標的計算對于裝置整體的設計和組裝有重要意義。引入一種將量子計算概念（量子態、量子門、量子狀態特性、概率幅等）融合到傳統遺傳算法中的優化算法——量子遺傳算法，用量子位表示基因，再利用量子信息的疊加性使每個量子位表達基因的可能性相同，進而通過基因位的旋轉完成基因的變異，每次完成變異后判斷適應度是否滿足條件，滿足條件的解將持續更新，在不停地迭代計算下求出最終的最優解。利用量子遺傳算法計算變化后的空間魔法波形木棍網絡節點的坐標比使用傳統遺傳算法和蒙特卡洛算法時的平均精度分別降低了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。