量子遺傳算法在多目標分配中的應用探討

摘 要:多目標分配目前是最優化領域中的一個重要研究方向。遺傳算法是一種借鑒生物界自然選擇和遺傳機制的高度并行、隨機、自適應的全局優化搜索算法，近年來，基于遺傳算法的多目標分配應用研究在過程工程領域越來越受重視。本論文提出了用量子遺傳算法處理和解決多目標分配問題，有一定的工程價值。

關鍵詞:量子遺傳算法;多目標分配;最優化

中圖分類號:TP18 文獻標識碼:A 文章編號:1674-7712 (2012) 12-0176-01

一、引言

遺傳算法不同于傳統尋優算法的特點在于:遺傳算法在尋優過程中，僅需要得到適應度函數的值作為尋優的依據;同時使用概率性的變換規則，而不是確定性的變換規則;遺傳算法適應度函數的計算相對于尋優過程是獨立的;算法面對的是參數的編碼集合，而并非參數集合本身，通用性強。它尤其適用于處理傳統優化算法難于解決的復雜和非線性問題。[1]

目前，GA已經在很多領域得到成功應用，但隨著問題規模的不斷擴大和搜索空間的更加復雜，GA在求解很多具體問題時往往并不能表現出其優越性。于是，近年來便出現了遺傳算法與其它理論相結合的實踐，其中遺傳算法與量子理論的結合是一個嶄新的、極富前景和創意的嘗試。

量子遺傳算法QGA是量子計算特性與遺傳算法相結合的產物。基于量子比特的疊加性和相干性，在遺傳算法中借鑒量子比特的概念，引入了量子比特染色體。由于量子比特染色體能夠表征疊加態，比傳統GA具有更好的種群多樣性，同時QGA也會具有更好的收斂性，因此在求解優化問題時，QGA在收斂速度、尋優能力方面比GA都將有較大的提高。QGA的出現結合了量子計算和遺傳算法各自的優勢，具有很高的理論價值和發展潛力。

本論文提出用量子遺傳算法處理和解決多目標分配問題，為多目標問題的解決提供一種新的思路。

二、量子遺傳算法

在傳統計算機中，信息存儲是以二進制來表示，不是“0”就是“1”態，但是在量子計算機中，充當信息存儲單元的物質是一個雙態量子系統，稱為量子比特(qubit)，量子比特與比特不同之就在于它可以同時處在兩個量子態的疊加態，量子進化算法建立在量子的態矢量表述基礎上，將量子比幾率幅表示應用于染色體的編碼，使得一條染色體可以表示個態的疊加，并利用量子旋轉門更新染色體，從而使個體進達到優化目標的目的。

一個 位的量子位染色體就是一個量子位串，其表示如下:

其中 。在多目標優化中，一個量子染色體代表一個決策向量，在量子態中一個 位的量子染色體可以表達 個態，采用這種編碼方式使得一個染色體可以同時表達多個態的疊加，使得量子進化算法比傳統遺傳算法擁有更好的多樣性特征。

為了實現個體的進化，經典進化算法中通過染色體的交叉、變異操作推進種群的演化，而對量子進化算法而言，量子染色體的調整主要是通過量子旋轉門實現的，算法流程如下:

(1)進化代數初始化: ;

(2)初始化種群 ，生成并評價 ;

(3)保存 中的最優解 ;

(4) ;

(5)由 生成 ;

(6)個體交叉、變異等操作，生成新的 (此步可省評價);

(7)評價 ，得到當前代的最優解 ;

(8)比較 與 得到量子概率門 ，保存最優解于 ;

(9)停機條件 當滿足停機條件時，輸出當前最優個體，算法結束，否則繼續;

(10)以 更新 ，轉到4)。

三、基于量子遺傳算法的多目標分配應用

如今為了滿足市場的需要，很多工廠的生產種類多、生產量大，從而設置了不同的生產車間，根據產品的性質分配生產車間合理與否直接影響工廠的經濟收益，這同樣可采用遺傳算法的目標分配方法進行分配。

模型構建:設工廠有i個生產車間。 為在第i個車間生產第j種產品的收益， 為第j種產品的需求量;如果第j種產品被選中，則 為在第i個車間生產該產品的總收益。由題意知為求解 最大問題。

仿真實例:設有10個生產車間，要生產15種產品，用Matlab程序編程，設定40個粒子，迭代200次，代溝0.9。運行結果如下:

此圖表明經200次迭代后的目標分配方案為:第1種產品由第3個車間生產，以此類推，車間5生產第2種產品，車間8生產第3種產品，……。次方案對應的車間總收益值為2.7030e+003，成功進行了多目標分配問題的解決。

四、結論

基于量子遺傳算法的多目標分配，為多目標分配突破傳統尋優模式找到了一個可行的解決方法。根據這種方法實驗，仿真結果可以看出，基本符合要求，并且能夠在一定的時間內得到最優的分配方案，因此，本文在探索多目標分配問題上找到了一種新的解決思路。

參考文獻:

[1]吉根林.遺傳算法研究綜述[J].計算機應用與軟件，2004，21(2):69-73

[2]肖曉偉，肖迪.多目標優化問題的研究概述[J].計算機應用研究，2011，3，28(3):805-808

[3]原銀忠，韓傳久.用遺傳算法實現防空導彈體系的目標分配[J].火力與指揮控制，2008，3，33(3):80-83

[4]郭張龍，李為民，王剛.基于遺傳算法的目標分配問題的研究[J].現代防御技術，2002，6:0172-0180

[5]孫祥，徐流美.matlab7.0基礎教程[M].北京:清華大學出版社，2005