基于量子遺傳的超參數自動調優算法的設計與實現

吳浩楠 高宏

摘?要：機器學習伴隨著海量數據的支持以及強大的計算能力為其提供了強有力的保證下不斷地向前發展，訓練過程變得更加高效便捷。在此基礎上，機器學習算法的超參數對其性能的影響是非常巨大的，因此對眾多的超參數進行優化選擇就自然有了強烈的需求。由此本文提出了一種基于量子遺傳的超參數自動調優算法，實驗表明，在針對多種機器學習模型的超參數調優問題上，既解決了一般隨機算法的不穩定性的問題，也解決了一般進化算法迭代緩慢、收斂速度較低的問題，并且通過實驗結果表明取得了不錯的效果。

關鍵詞： 超參數調優;遺傳算法;量子遺傳算法;機器學習

文章編號： 2095-2163（2021）01-0170-06 中圖分類號：TP181 文獻標志碼：A

【Abstract】With the development of big data and the improvement of computing power， machine learning has been continuously developing， and the training process has become more efficient and convenient. On this basis， the hyper-parameter of machine learning algorithms has a great impact on their performance， so there is a strong demand for optimizing and selecting a large number of hyper-parameter. Thus this paper puts forward a kind of automatic tuning super parameter based on Quantum Genetic Algorithm. The experiments show that for a variety of machine learning model on the above parameters tuning problem，the instability of both randomized algorithms of the general problem is solved， also the problems of slow iteration and low convergence speed of the general evolutionary algorithm are solved， therefore good results have been achieved.

【Key words】hyper-parameter tuning; Genetic Algorithm; Quantum Genetic Algorithm; machine learning

0 引?言

如今，海量數據的支持以及強大的計算能力為機器學習的不斷發展提供了有效保證，使其訓練過程變得更加高效、便捷。在此基礎上，一個機器學習算法的超參數就成為影響算法性能優劣的重要因素。如何在復雜的參數空間中選擇出一組超參數使得機器學習算法的性能得到最大的提升，是機器學習領域長期以來一類備受關注的研究問題，超參數優化問題也是在此背景下才得以提出。

研究初期，一般需要相關的工作人員通過已有的經驗對超參數進行調節，或者是由設計者給出建議的超參數的配置選擇。但在模型復雜以及超參數眾多的情況下，就隨即對超參數進行自動化調優有了強烈的需求。故而，對于機器學習算法未來走向實用，設計出一個超參數自動調優算法則有著至關重要的現實意義[1]。

早期，網格搜索（Grid Search）是超參數優化算法中常用的技術。但是網格搜索方式的效率是很低下的，其本質是屬于窮舉的方法，只不過是帶有一定的步長。超參數的搜索空間，會隨著待優化參數的增加，而呈指數型增長[2]。文獻[3]中討論了一種隨機搜索策略，并通過實驗表明，與網格搜索方法相比，該方法有著更高的效率。文獻[4]還提出了TPE算法，解決了機器學習超參數優化問題，該算法是基于模型的全局優化并且是樹形結構的。此外，貝葉斯優化也是該領域較經典的超參數優化算法，具體就是一種快速求解昂貴函數極值問題的優化方法[5]。

在國內的有關超參數優化的文獻中，大多是利用進化算法來進行機器學習模型的超參數調優。例如，文獻[6]中的超參數優化方法是模擬退火算法;文獻[7]中，運用遺傳算法來解決機器學習模型支持向量機（SVM）的超參數優化問題;此外常見的還有粒子群優化算法[8]。實際上在處理超參數優化問題時可將其視作針對昂貴函數來進行優化。并且進化算法中大部分都是基于種群的，當種群規模較大時則會同時伴生著與算法性能效率相關的問題。因此，本文擬基于一種量子遺傳算法，其類屬于進化算法，來提出主要研究內容，即一種基于量子遺傳的超參數自動調優算法。通過實驗表明，本文提出的算法在解決機器學習模型的超參數優化問題的同時，在對比實驗中還取得了性能和效率上的提升。

1 超參數優化問題表述

超參數優化的思想對機器學習的調參有著重要意義，對于其他復雜的系統結構，當研究過程需要優化這一類黑箱模型結構時，都可以借鑒超參數優化的思想來解決系統的結構優化問題。本文研發設計的基于量子遺傳的超參數優化算法是應用于解決傳統機器學習模型的超參數調優問題。如圖1所示。由圖1可知，主要是模擬了超參數優化問題的大致過程。

研究可知，該問題的本質就是為機器學習模型找到一組較好的超參數配置，使得機器學習模型在測試集合上的泛化誤差達到最小。此后提到的相關實驗過程及結果是基于GBDT機器模型來進行的超參數調優相關實驗。GBDT是常用傳統機器學習模型，可解決大部分機器學習中分類和回歸問題，與其相關的超參數分為2類：boosting框架參數，弱學習器即CART回歸樹相關的重要參數。相關超參數見表1。

2 基于量子遺傳的超參數調優算法

2.1 量子遺傳算法

量子遺傳算法源于量子計算，同時也是一種進化算法。量子遺傳算法在本質上還是一個基于概率的隨機搜索算法[9]。

在探討量子遺傳算法前，則需要了解一些與量子計算相關的知識作為理論基礎。首先，要知道量子位是量子計算中存儲信息的最小單元，量子位可以表示為：αβ，其中滿足α2+β2=1。接下來是量子門，在量子遺傳算法中量子位是可以通過量子門來改變的，將其引入不僅使得算法具備了開發和探索的能力，還使得算法能夠最終走向收斂[10-11]。量子門是一個2×2階的可逆矩陣U，量子門一般通過如下矩陣變換更新量子位，設新的量子位為αiβi，那么：

接下來在量子位的基礎上，又引出了量子染色體的概念，每一個染色體都是由式（2）中的一系列量子位組成的，即：

量子遺傳算法的大致流程，參見算法1。

算法1 量子遺傳算法

輸入：種群大小N，算法的終止條件（比如迭代次數等）

輸出：集合B中表現最好的樣本

Step 1 生成輸入指定大小量子染色體種群Q（t），并對其進行初始化操作。

Step 2 將種群Q（t）中每一個量子染色體通過規則進行轉換為一個二進制串，形成一個新的二進制串的集合P（t）。

Step 3 對P（t）中的每個樣本通過目標函數進行評價。

Step 4 將Step 3中表現最優的樣本添加到集合B中。

while（如果未滿足終止條件）

{

Step 5 進行下一次迭代，令t=t+1，對量子染色體種群Q（t-1）進行Step 2的操作，從而形新一輪的P（t）。

Step 6 對P（t）中的每個樣本通過目標函數進行評價。

Step 7 將Step 6中表現最優的樣本添加到集合B中。

Step 8 將種群Q（t）通過量子門的旋轉進行更新進化。

}

2.2 基于量子遺傳的超參數調優算法

在本小節中，給出算法的基本框架見算法2。

算法2 基于量子遺傳的超參數調優算法

輸入：待優化機器學習模型M，數據集X，種群大小N，這里設置為1，待優化的超參數的參數空間，算法的終止條件（比如迭代次數等）

輸出：集合B中表現最好的樣本

Step 1 生成指定規模大小量子染色體種群Q（t），并對其進行初始化操作。將輸出集合B置為空集。通過超參數的類型及參數空間決定量子染色體的總長度。

Step 2 將種群Q（t）中每一個量子染色體通過規則進行轉換為一個二進制串，形成一個新的二進制串的集合P（t）。

Step 3 對P（t）中的每個樣本通過目標函數進行評價。將每個二進制串解碼為一組賦有特定取值的超參數配置。評估機器學習模型M在此超參數配置下進行訓練后，在測試集上的性能指標，并將該結果作為目標函數的輸出。

Step 4 將Step 3中表現最優的樣本添加到集合B中。

while（如果未滿足終止條件）

{

Step 5 進行下一次迭代，令t=t+1，對種群Q（t-1）重復上述Step 2中操作，生成新一輪的集合P（t）。

Step 6 重復Step 3對P（t）中的樣本進行評價。

Step 7 重復Step 4更新集合B。

Step 8 將種群Q（t）通過量子門的旋轉進行更新進化。

}

這里，對于算法2中的關鍵步驟含義擬做出分析詳述如下。

Step 1中，本質是在對每個超參數進行編碼操作，進而決定量子染色體的總長度。研究中是基于以下方案來確定量子染色體的總長度。超參數一般有2種類型：離散、連續。假設某個超參數是離散類型的，并且只有3種取值，這時通過2位量子位就可以編碼表示該參數的所有狀態。例如可以用00，01，10分別對應表示該超參數的一種狀態。相應地，對于編碼為11的狀態，算法中的規定是：可以對其進行隨機變異，使其轉變為上述三種編碼狀態中的任意一種。而對于連續型超參數來說，例如某超參數取值范圍在區間[a，b]，可以根據研究中自定義的精度來將其分割成k份。那么就需要N位來編碼這個超參數，這里N需要滿足如下條件：

Step 2的本質就是在對量子染色體進行一個轉換，將其轉換為一個二進制串。具體實現過程為：針對量子染色體中的每一位，都要先生成一個隨機數r，取值在[0，1]之間，若rα2，則該位置為0，否則置為1。下面將舉例說明上述操作。例如，某條量子染色體可以表示為1212，1212，1212，針對其中的每一位量子位隨機生成的數字為0.3、0.7、0.2，那么對該量子染色體進行觀察操作后，得到的二進制串可以表示為[0，1，0]。與此過程相似，還將對每個量子染色體都重復進行上述觀察操作，最后形成了上述算法中提到的種群?P（t）。

Step 3在本質上是對每一個在Step 2中轉換好的二進制串進行解碼操作，將其翻譯為每一個超參數所對應的實際取值。具體操作為：由于此前提到過超參數分為離散型和連續型兩種，那么過程中的解碼操作也相應地分為2種。

總地來說，對于超參數是離散型情況下的解碼，可以提前定義一張映射表。其中，key對應的是Step 2中轉換的二進制串中的某一段，value對應的是該段二進制串在事先定義好的映射表中對應的實際值。而當超參數是連續型的情況時，可以通過式（4）來進行計算：

其中，x為代表該超參數那段的二進制串對應的十進制數;a和b分別表示該參數取值范圍的上限和下限;N表示該段二進制染色體的總體長度，而等式左側的x即為連續型超參數通過解碼操作后計算得到的實際取值。

Step 4則是執行Step 3后，在比較后記錄下有著較好適應度的個體。

Step 7的本質就是利用此前涉及到的量子旋轉門，來對舊的量子染色體進行更新進化，形成新一輪的量子染色體，在量子遺傳算法中，由于量子編碼作用下的染色體不再是單一的純態，遺傳處理中不能繼續僅僅采用傳統的選擇/交叉/變異等操作，而是要采用量子旋轉門作用于量子染色體的基態，使其相互干涉，相位發生變化，從而改變概率幅的分布。綜上論述可知，量子旋轉門的設計是整個算法框架里的核心步驟。對其實現過程將依次展開如下論述。

前文提到過，每一個量子位是通過量子旋轉門進行更新的，對此可表示為：

進一步，旋轉門U可表示為：

其中，θ表示本次的旋轉角度，該值大小與符號在量子位的更新過程中占據著舉足輕重的地位。研究中給出了量子位的旋轉演示如圖2所示。

由圖2可知，θi的正負情況將決定量子門的旋轉方向。若θi為正，更新后的量子比特位α將會減小，相應地將提高其為1的概率;相反，若θi為負，更新后的量子比特位α將會增大，相應地將提高其為0的概率。這里，對θi的設計可表述為：

其中，Δθi表示旋轉角度大小;s（αi，βi）表示其正負情況，設ri和bi分別表示當前個體和當前最優個體的第i個量子位的二進制取值，則此時對應的θi可通過對表2的計算得到。

2.3 基于量子遺傳的超參數調優算法的改進及完善

依據2.2節提出的基于量子遺傳的超參數調優算法框架，本文對該算法進行了改進與完善。如前所述，該算法中量子旋轉門的設計是整個算法框架的重中之重，故而嘗試將原有的量子位更新方法改為了如下形式：

上述量子門為Hardmard門，也叫做相位門。使用此方式對量子位操作時，可以改變旋轉相位，也可以進行將量子位旋轉90°的操作。該方式實現了遺傳算法中經常會提到的變異操作，因此就通過將原算法中的量子旋轉操作改為使用Hardmard門，實現對量子染色體的變異，這就在一定程度上避免早熟現象的發生。

此外，對算法過程的完善操作即是在最后加入了量子災變過程。也就是說，當運算中連續多次都沒有進化發生后，此時就要引發量子災變過程，將新一輪的量子染色體重新初始化初值，再繼續正常向下運行算法，如此即可在一定程度上避免陷入局部最優。本文提出的基于量子遺傳的超參數調優算法的流程如圖3所示。

3 實驗

為了驗證本文提出算法的有效性，本小節擬進行一些對比實驗。首先是與基因遺傳算法（GA）的執行測試結果進行比較，2種算法執行過程中的迭代收斂曲線如圖4所示。橫坐標表示迭代次數，縱坐標表示模型在每輪迭代訓練后的執行性能。

由圖4可以看出，基于量子遺傳的參數優化算法收斂速度要快于GA算法，并且最終都使得機器學習模型在優化結束后獲得較好的性能。

接下來是與模擬退火搜索算法相比較，結果如圖5所示。圖5中實線表達的是本文所提出算法的實驗結果。橫坐標表示實驗次數，縱坐標表示每次實驗后模型在優化算法執行過程中達到的最好性能。

從圖5分析可知，由于對比算法存在一定概率隨機搜索，即使得相比之下本文提出的優化算法的執行結果明顯更加穩定。

同時，還與概率隨機搜索算法進行對照，研究得到的算法時間復雜度的結果對比見表3。

由表3可以看出，本文提出的調優算法在時間復雜度上與隨機搜索算法相差無幾，并就之前提到的基于種群的進化算法的時間效率問題得到了很好的解決。

最后，將本文算法應用在其他的模型優化場景中進行測試，測試結果見圖6。

由圖6可知，本文提出的優化算法應用在其他傳統機器學習模型的超參數優化問題中也有良好表現。

4 結束語

本文提出了一種基于量子遺傳的超參數自動調優算法。

首先，該算法是結合了進化算法和概率隨機搜索兩者的核心思想。進化算法在使用時大部分是基于種群的方法，比如一些進化遺傳算法，粒子群優化算法等，如果把種群個數設置為?1，這些算法就失去了作用，因其每次迭代需要互相之間的信息交互。但是量子遺傳與之不同的地方就在于，該算法是由相互獨立的每個個體組成，每次更新均是通過旋轉門來實現的，所以當種群的規模為1時，算法也可以正常執行。所以本文所提算法在時間復雜度上與前者近似，兩者均為在每一輪迭代中進行一次模型性能評估，這也解決了一般進化算法迭代緩慢、收斂速度較低的問題。

其次，本文算法也繼承了遺傳進化算法的特性，量子染色體通過旋轉門的操作使得每個量子位都在朝著好的方向進化，如此一來就使得相比于前者來說，算法的執行結果更加穩定。

同時，本文算法在其他模型優化問題中有較好的表現，說明本文算法也具有一定的通用性。

最后，通過實驗結果分析表明，本文算法在解決超參數調優問題上具有可行性及有效性。而將該算法思想應用于解決更多的超參數優化問題場景上，則是未來后續工作中的重點研究內容。

參考文獻

[1]陸高. 基于智能計算的超參數優化及其應用研究[D]. 西安：西安電子科技大學，2018.

[2]LERMAN P M. Fitting segmented regression models by grid search[J]. Applied Statistics，1980，29（1）：77-84.

[3]BERGSTRA J， BENGIO Y. Random search for hyper-parameter optimization[J]. Journal of Machine Learning Research， 2012， 13（10）：281-305.

[4]BERGSTRA J S， BARDENET R， BENGIO Y， et al. Algorithms for hyper-parameter optimization[C]//25th Annual Conference on Neural Information Processing Systems（NIPS 2011）. Granada， Spain：dblp， 2011： 2546-2554.

[5]BROCHU E， CORA V M， De FREITAS N. A tutorial on Bayesian optimization of expensive cost functions， with application to active user modeling and hierarchical reinforcement learning[J]. arXiv preprint arXiv：1012.2599， 2010.

[6]燕飛， 秦世引. 一種基于模擬退火的支持向量機超參數優化算法[J]. 航天控制， 2008，26（5）：7-11，17.

[7]唐靜， 胡云安， 肖支才. 基于遺傳算法的電路故障診斷超參數優化算法框架[J]. 計算機工程與應用， 2012， 48（3）：13-16.

[8]GUO X C， YANG J H， WU C G， et al. A novel LS-SVMs hyper-parameter selection based on particle swarm optimization[J]. Neurocomputing， 2008， 71（16-18）：3211-3215.

[9]焦李成， 李陽陽， 劉芳，等. 量子計算、優化與學習[M]. 北京： 科學出版社， 2017.

[10]周傳華，錢峰. 改進量子遺傳算法及其應用[J]. 計算機應用，2008，28（2）：286-288.

[11]張秋艷，王默玉，申曉留，等.基于災變因子的量子遺傳算法研究[J].計算機與數字工程，2019，47（7）：1591-1595.