佳點集遺傳算法及其在ＰＩＤ控制中的應用
2009-01-01 00:00:00彭勇施寧林滸
計算機應用研究 2009年2期
(1.中國科學院 研究生院， 北京 100049；2.中國科學院 沈陽計算技術研究所， 沈陽 110171；3.中國人民解放軍炮兵學院， 合肥 230031)
摘 要：傳統遺傳算法具有收斂速度慢、局部尋優能力較差且容易出現“早熟”等現象，運用數論中的佳點集理論與方法對其進行改進。改進的算法通過生成一種具有良好多樣性的均勻初始種群，構造出新型的佳點交叉算子和變異算子，使得在進化過程中子代可以更好地繼承父代的優良特性，有效地改善了傳統算法的全局收斂速度，避免了“早熟”現象的發生。將此改進算法應用于工業PID控制器的參數尋優，仿真結果顯示出佳點集遺傳算法明顯提高了搜索速度，系統的動態性能和穩定性也有明顯改善。
關鍵詞：佳點集；遺傳算法；比例微積分控制器;參數尋優
中圖分類號：TP18；TP273 文獻標志碼：A
文章編號：10013695(2009)02052403
Goodpoint set genetic algorithm and its application to PID controllers
PENG Yong1，2，SHI Ning3，LIN Hu2
(1.Graduate School， Chinese Academy of Sciences， Beijing 100049， China;2.Shenyang Institute of Computing Technology， Chinese Academy of Sciences， Shenyang 110171， China;3.Artillery Academy of PLA of China， Hefei 230031， China)
Abstract:On the basis of goodpoint theory，this paper proposed an improved approach to overcome the shortcomings of slowconvergence， incapability of optimization in the local area and easypremature with traditional genetic algorithm.Of the goodpoint set GA， the offspring could inherit the excellent gene from parents under the effect of an initial population established with diversity， newly designed crossover operator and mutation operator. The improved algorithm has superiority in speed， accuracy and overcoming premature. The simulation results show that the PID controller designed upon the goodpoint set GA greatly improves the search speed， and is of good dynamic quality and stability.
Key words:goodpoint set; genetic algorithm; PID controller; parameteroptimization
0 引言
PID控制器由于結構簡單、適應性好、魯棒性強等特點，被廣泛應用于機電、冶金、機械、化工等行業中。隨著被控對象復雜程度的加深，PID控制參數尋優問題日趨突出，傳統的ISTE最優設定法、繼電器法、專家整定法、衰減曲線等方法均存在一定的局限性，如專家整定法需要太多的經驗，經驗依賴于知識庫，而知識庫的建立又非常耗時；繼電器法容易使被控系統產生振蕩。采用具有全局搜索能力的算法來解決參數尋優問題是一種可行的方法，如模擬退火算法、遺傳算法等，但是在實際應用過程中傳統的遺傳算法具有收斂速度慢、局部尋優能力差，而且容易出現“早熟”現象。本文根據數論中佳點集的理論與方法，設計出均勻分布于解空間的初始種群和基于佳點的交叉算子和變異算子，提高了傳統遺傳算法的性能，并將其用于PID參數尋優。
1 傳統遺傳算法特點
遺傳算法是借鑒生物界自然選擇和自然遺傳機制的隨機化搜索算法，由美國芝加哥大學J. Holland教授于1975年提出[1]。該算法的基本思想是基于自然界優勝劣汰的生物進化原理。它根據自然界中個體通過選擇、交叉和變異等遺傳行為后，能保留下適應性強的個體并繼續繁衍，淘汰適應度低的個體，使整個群體得到進化。遺傳算法具有自適應性、領域知識無關性和容易實現并行的優點被大量引用來求解一些大規模復雜的數據，取得了很好的效果。
2 佳點集遺傳算法
2.1 佳點集的基本定義與性質[2]
a）設Gs是S維歐氏空間的單位立方體，即x∈Gs，x=(x1，x2，…，xs)，其中0≤xi≤1（i=1，2，…，s）。
b）設Gs中有含n點的點集，Pn(k)={x(n)1(k)，…，x(n)s(k)}，其中
1≤i≤s，1≤k≤N ，0≤x(n)i(k)≤1。
c）對Gs中的點r=(r1，r2，…，rs)，令Nn(r1，r2，…，rs)表示Pn(k)中滿足下面不等式組的點的個數，0≤x(n)i(k)≤1，1≤i≤s。記φ(n)=supr∈Gs|Nn(r)/n-|r||，|r|=r1r2… rs，則稱點集Pn(k)有偏差φ(n)。若對任意n，均有φ(n)=o(1)，則稱Pn(k)在Gs上是一致分布且偏差為φ(n)。
d）令r∈Gs，ε為任意小的正數，形為Pn(k)={({r1*k}，…{rs*k})}(1≤k≤n)的偏差φ(n)滿足φ(n)=C(r，ε)n-1+ε(其中C(r，ε)是只與r，ε有關的常數)，則稱Pn(k)為佳點集，r為佳點。
e）取rk={2 cos (2πk/p)}，1≤k≤n，p是滿足(p-3)/2≥s的最小素數，則r為佳點。取rk={ek}，1≤k≤s，則r也是佳點(分圓域)。
定理1 令Pn(k)(1≤k≤n)具有偏差φ(n)，f∈Bs(s維囿變函數類)，則
|∫Gsf(x)dx-1/nnk=1f(Pn(k))|≤V(f)φ(n)(1)
其中：V(f)是f的全變差。
定理2 若式（1）對所有f∈Bs皆成立，則Pn(k)(1≤k≤n)為有偏差不超過φ(n)的點集。
定理3 若f(x)滿足|f|≤L，|f/xi|≤L，
1≤i≤s，|2f/xixj|≤L，1≤i≤j≤s，…，|sf/xixs|≤L，用給定n點的函數值構成的任何加權和來近似計算函數在Gs上的積分，誤差都不能希望比o(n-1)更小。
這個性質正是上面點集稱為佳點集的由來。由定理1~3可知，用佳點集來進行近似積分，其誤差的階與n有關而與空間的維數t無關，這為高維的近似計算提供了一個非常優越的算法。由以上的性質可知，若限定取n點，用其上函數值的線性組合來近似對應的積分值，則佳點集方法提供了一個最好的方法。
2.2 佳點集遺傳算法[3]
佳點集遺傳算法改進之處是初始種群的生成與交叉、變異算子的設計，選擇算子與適應度函數的設計與傳統遺傳算法類似，文中繼續選用輪盤賭選擇機制，適應度函數則根據PID控制器的規律設計。下面介紹的是基于佳點集的遺傳算法的改進策略。
1）編碼與初始種群設計 設種群規模為N的染色體集合A，AiN={ai1，ai2，…，ais}，i=1，2，…，N。首先在s維歐氏空間H中取N點的佳點集。s維空間H中取佳點集的方法如下：
在s維空間H中取佳點集PN(i)={{r1*i}，{r2*i}，…，{rs*i}}，i=1，2，…，N。其中rk={2 cos(2πk/p)}，1≤k≤s，p是滿足(p-3)/2≥s的最小素數，{a}表示取a的小數部分。
可選的編碼方式有如下三種[4]：
a)當aik(k=1，2，…，s；i=1，2，…，N)為一位二進制時，取aik=[{rk*i}]。[a]表示a的小數部分小于0.5則取0；否則取1。
b)當aik(k=1，2，…，s；i=1，2，…，N)為m位二進制時，取aik=αk+{rk*i}*(βk-αk)，這里αk≤αik≤βk；然后根據二進制編碼方法將aik轉換為二進制編碼。
c)當aik(k=1，2，…，s；i=1，2，…，N)為實數編碼時，取aik=αk+{rk*i}*(βk-αk)即可，這里αk≤αik≤βk。
2） 交叉 Ai和Aj為選中進行交叉的父本，Ai=(ai1，ai2，…，aiL)，Aj=(aj1，aj2，…，ajL)，做出Ai和Aj的模式；J是Ai和Aj的分量不同位置集合J={t|ait≠ajt，1≤t≤L}。記J的元素為t1，t2，…，ts，且t1＜t2＜…＜ts，在s維空間取佳點集Pn(i)={({rt1*i}，…，rts*i)}，1≤i≤n，rtk={2 cos(2πk/p)}(1≤k≤s)，p是滿足(p-3)/2≥s是滿足的最小素數，{a}表示取a的小數部分。
令Bk=(bk1，bk2，…，bkL)為交叉后產生的染色體，則bkm=aimmJ
[{rtj*k}]m=tj∈J。其中：1≤k≤n，1≤m≤L，1≤j≤s。
上面就是用佳點集方法在s維歐氏空間的單位立方體Gs中產生佳點，進而決定子代中不確定的基因。這種交叉操作稱為佳點集交叉操作。
3）變異 對隨機選出的變異個體，先隨機選擇兩個基因位，對這兩點之間的基因按交叉算子中描述的不同位重排的方法進行變異。
4）測試用例
3.1 算法描述
1)編碼與初始種群設計 按照佳點集方法產生初始種群，采用第二種編碼方法進行編碼。
2)選擇 復制選擇采用輪盤賭機制，以概率fi/Ni=1fi取到染色體Ai；生存選擇采用父子混合選擇策略，“杰出者”將直接進入下一代。
3)交叉、變異 采用佳點交叉、變異算子。
4)適應度函數[5] J=∫∞0(w1|e(t)|+w2u2(t)+w4|ey(t)|)dt+w3tu。其中：e(t)為系統誤差；u(t)為控制器輸出；tu為上升時間；w1、w2、w3、w4為權值；ey(t)=y(t)-y(t-1)；y(t)為被控對象輸出。
3.2 佳點集遺傳算子的理論分析
根據佳點集理論的改進遺傳算法的初始種群設計和遺傳算子的特點，下面對其進行分析：
定理4 鐘開萊、Kiefer[2]。設x1，x2，…，xn為i.i.d.Dt上的均勻分布及pn={x1，x2，…，xn}，則pn的偏差D(n，pn)=O(n-1/2(log log n)1/2)成立的概率為1。
定理4說明在對一位置均勻分布的對象用隨機方法取n點，它們的偏差一般為O(n-1/2)，若用佳點集法取n點，其偏差為O(n-1+ε)，兩者相差平方次。也就是說，用佳點集法要比用隨機法的偏差小得多，這就是佳點集理論對遺傳算法初始種群進行均勻設計以及為什么用佳點集法收斂得快的理論依據。
圖1~4是使用MATLAB 7.0繪出的隨機法與佳點集法產生的初始種群對比圖。
由對比圖可以看出，隨機法產生的數據雜亂無章，有重疊點；而佳點集方法產生的初始種群分布均勻，體現了佳點集法設計初始種群的優越性。
定理5 模式定理[1，6]。遺傳算法中，在選擇、交叉和變異算子的作用下，具有低階、短的定義距長度，且平均適應度高于種群平均適應度的模式在子代中將以指數次增長。
模式定理說明：在種群進化初期，由于模式的階低、定義距的長度短，算法具有很快的收斂速度，隨著算法的進行，種群模式的階、定義距的長度增加，這樣在進化的后期算法收斂速度減緩，且較難收斂于全局最優解。
基于佳點集的交叉算子強調的是，隱含在某一模式中的個體與其他個體進行交叉操作時，此模式能夠在交叉操作中生存下來的條件就是參與交叉的另一個體也含在此模式中。因此父代中的模式能否生存下來決定于該模式對應的特色模式的適應度。在進化過程中，模式的階、定義距的長度都有增長的趨勢。
結論：佳點集遺傳算法在進化過程中，高于平均適應度的染色體集合的平均適應度的特色模式將按指數次增長（退化為普通模式），與模式的階、定義距相關性不明顯，這使得在進化的后期，佳點集遺傳算法仍然有較快的收斂速度。
3.3 基于佳點集算子的實驗數據分析
1）仿真對象 G1(s)=400/s2+50 s，G2(s)=523 500/s3+280.35 s2+10 s+1，輸入指令為單位階躍信號，采樣時間是1 ms。所采用的衡量函數為J=∫∞0(w1|e(t)|+w2u2(t)+w4|ey(t)|dt+w3tu，加入了懲罰功能，將超調量作為最優指標的一項。
2）仿真條件及結果 種群規模為popsize=30，染色體長度是lchrom=30[7]（每10位分別表
4 結束語
佳點集遺傳算法是使用數論中的佳點集理論與方法對傳統遺傳算法進行改進得出的。該算法設計出了具有良好多樣性且均勻分布于解空間的種群，構造出佳點交叉算子和變異算子，使得在收斂速度上優于傳統遺傳算法，又避免了傳統遺傳算法易陷入局部最優的缺陷。仿真實驗表明，佳點集遺傳算法有效地提高了參數尋優的速度與精度，是一種有效、實用的PID參數優化方法。
參考文獻：
［1］
陳國良，王煦法，莊鎮全．遺傳算法及其應用[M].北京:人民郵電出版社，1996.
[2]華羅庚，王元.數論在近代分析中的應用[M].北京:科學出版社，1978.
[3]張鈴，張鈸.佳點集遺傳算法[J].計算機學報，2001，24(9):917922.
[4]李志俊，程家興.免疫佳點集算法[J].計算機工程與應用，2007，43(28)：3740.
[5]劉金琨.先進PID控制MATLAB仿真[M].北京:電子工業出版社，2004.
[6]HOLLAND J H.Adaptation in natural and artificial systems [M].[S.l.]:University of Michigan Press， 1975.
[7]MENG Xiangzhong，SONG Baoye.Fast genetic algorithms used for PID parameter optimization[C]//Proc of IEEE International Confe-rence on Automation and Logistics.Jinan:[s.n.]，2007:21442148.
[8]周洪波，齊占慶，衡強，等.一種改進的遺傳算法及其在PID控制中的應用[J].控制工程，2007，14(9):589591.
