基于鞅方法的雞群優(yōu)化算法收斂性分析

摘" 要：針對雞群優(yōu)化（chicken swarm optimization，CSO）算法已有的收斂性分析結果屬于弱收斂，不能保證算法能在有限步內(nèi)收斂到問題的全局最優(yōu)這一不足，提出了運用鞅方法來研究CSO算法的全局收斂性.首先，基于CSO算法的相關定義，建立CSO算法的馬爾可夫（Markov）鏈模型，分析其Markov性質(zhì)；其次，將具有最小適應度值的雞群狀態(tài)序列轉(zhuǎn)化成上鞅，利用上鞅收斂定理和Egoroff定理證明了CSO算法的幾乎處處強收斂性和一致收斂性，進而得出了當雞群狀態(tài)空間有限時，CSO算法能確保在有限步內(nèi)收斂到問題的全局最優(yōu)這一結論；最后，在仿真實驗中成功驗證了理論證明的正確性，并發(fā)現(xiàn)CSO算法比其他算法具有更強的尋優(yōu)能力和更高的收斂精度.

關鍵詞：CSO算法；Markov鏈；上鞅收斂定理；Egoroff定理；幾乎處處強收斂；一致收斂

中圖分類號：TP301.6;TP18""" ""文獻標志碼：A文章編號：1000-2367（2024）06-0080-08

雞群優(yōu)化算法［1］（簡稱雞群算法）屬于群智能優(yōu)化算法中的一種，主要通過模擬雞群中的等級秩序和覓食行為，利用雞的群體智能來解決優(yōu)化問題.相較于粒子群優(yōu)化［2］（particle swarm optimization，PSO）算法、差分進化［3］（differential evolution，DE）算法，其具有參數(shù)少、收斂速度快、簡單易操作等特點［4］.目前，CSO算法已被成功地應用到了車間調(diào)度、路徑規(guī)劃、圖像分類、資源分配等領域［5］中，并且根據(jù)實際問題的特殊性，出現(xiàn)了一大批CSO改進算法［6-8］.不難發(fā)現(xiàn)，由于發(fā)展時間較短，CSO算法改進與應用雖然已有了不少研究成果，但與其他算法相比，它在數(shù)學理論方面的研究還比較少，特別是關于算法的收斂性研究仍不多見，因此在一定程度上也限制了CSO算法的改進和應用.

作為一種常用來分析群智能算法收斂性的數(shù)學工具，隨機搜索算法的收斂準則已成功運用到了蝙蝠算法（bat algorithm，BA）［9］、灰狼優(yōu)化（grey wolf optimization，GWO）算法［10］和螢火蟲算法（firefly algorithm，F(xiàn)A）［11］等算法的收斂性證明中.同樣地，文獻［12］通過建立CSO算法的Markov鏈模型，并結合該收斂準則，證明了CSO算法能收斂到問題的全局最優(yōu).然而，上述證明方法存在如下不足：一是通過該方法進行收斂性理論分析時過程較為復雜，且得到的收斂結果屬于依概率收斂，在弱大數(shù)定律范疇中；二是無法確保CSO算法能在有限步內(nèi)收斂到問題的全局最優(yōu).針對這兩點，本文基于CSO算法的Markov鏈模型，提出了用鞅方法代替Markov鏈的遍歷性分析來研究CSO算法的全局收斂性.不僅有效簡化了CSO算法全局收斂性理論分析的過程，而且還成功證明了當雞群狀態(tài)空間有限時，CSO算法能確保在有限步內(nèi)以概率1收斂到問題的全局最優(yōu).

收稿日期：2023-05-04;修回日期：2023-07-04.

基金項目：國家自然科學基金（12361057）；貴州省數(shù)據(jù)驅(qū)動建模學習與優(yōu)化創(chuàng)新團隊項目（黔科合平臺人才［2020］5016）.

作者簡介：周婷婷（1998-），女，貴州遵義人，貴州大學碩士研究生，研究方向為智能優(yōu)化算法、生物與醫(yī)學統(tǒng)計，E-mail：3075055469@qq.com.

通信作者：戴家佳（1976-），女，貴州貴陽人，貴州大學教授，博士，研究方向為生物與醫(yī)學統(tǒng)計、生存分析，E-mail：jjdai@gzu.edu.cn.

引用本文：周婷婷，戴家佳.基于鞅方法的雞群優(yōu)化算法收斂性分析［J］.河南師范大學學報（自然科學版），2024，52（6）：80-87.（Zhou Tingting，Dai Jiajia.Convergence analysis of chicken swarm optimization algorithm based on martingale method［J］.Journal of Henan Normal University（Natural Science Edition），2024，52（6）：80-87.DOI：10.16366/j.cnki.1000-2367.2023.05.04.0002.）

1" CSO算法

CSO算法綜合了PSO算法、DE算法的優(yōu)點，是通過4條規(guī)則將雞群中的等級秩序和覓食行為理想化，從而建立數(shù)學模型來求解優(yōu)化問題.本文考慮最小值優(yōu)化問題，即：min F（x），F(xiàn)（x）0.（1）

CSO算法在優(yōu)化問題的求解空間中隨機生成N只雞形成雞群x=（x1，x2，…，xN）.雞群中第i只雞在D維空間中所處的位置表示為：xi=（xi1，xi2，…，xiD）T，i=1，2，…，N.xi是優(yōu)化問題在解空間中的一個潛在解，每只雞通過適應度函數(shù)f（xi）求出適應度值.由于適應度函數(shù)是定義在解空間上的任意非負實值函數(shù)，基于式（1），在解空間上定義的適應度函數(shù)就是目標函數(shù).

雞群中共有N只雞，其中公雞有Nr只、母雞有Nh只、小雞有Nc只、母雞媽媽有Nm只，且NmNh，Nr+Nh+Nc=N.第i只雞在第j維空間中第t次迭代的位置為xji（t）.因為不同種類的雞有不同的運動規(guī)律，故3種雞的位置更新策略也各不相同.

公雞的位置更新策略為：xji（t+1）=xji（t）×（1+R），（2）

σ2=1，fifk，exp［（fk-fi）|fi|+ε］，其他，" k=1，2，…，N且k≠i.（3）

式中：R是服從N（0，σ2）的隨機數(shù)；f為對應x的適應度值；ε是一個充分小的正數(shù)，用來避免式（3）中分母為0；k是所有公雞中除了i后的任一只公雞.

母雞的位置更新策略為：xji（t+1）=xji（t）+B1×V1×［xjr1（t）-xji（t）］+B2×V2×［xjr2（t）-xji（t）］，（4）

B1=exp［（fi-fr1）|fi|+ε］，（5）

B2=exp（fr2-fi）.（6）

式中：r1是與第i只母雞同在一個子群里的公雞；r2是整個雞群里的任意一只公雞或母雞，且r1≠r2；B1、B2為常數(shù)，取值范圍為（0，1）；V1、V2是服從［0，1］之間均勻分布的隨機數(shù).

小雞的位置更新策略為：xji（t+1）=xji（t）+FL×［xjm（t）-xji（t）］.（7）

式中：m是第i只小雞的母雞媽媽；FL是跟隨系數(shù)，為小雞跟著母雞媽媽覓食時母雞媽媽的位置對小雞位置的影響因子，取值范圍為（0，2）.

2" CSO算法的Markov鏈模型

Markov 鏈是對隨機過程進行分析的重要手段，指的是系統(tǒng)在任一時刻所處狀態(tài)組成的 Markov 隨機序列.下面先給出一些CSO算法的相關定義，以便建立其 Markov 鏈模型.

定義1" 在CSO算法中，雞群中每只雞覓食時所處的位置構成了雞個體狀態(tài)，記為x，x∈C，C是可行解空間，一只雞的全部可能狀態(tài)組成了雞個體狀態(tài)空間，記為：x=｛x|x∈C｝.所有雞個體狀態(tài)就組成了雞群狀態(tài)，記為：θ=（x1，x2，…，xi），1iN.（8）

故雞群狀態(tài)空間記為：Θ=｛θ=（x1，x2，…，xN）|xi∈C，1iN｝.（9）

式中：xi為第i只雞的狀態(tài)，N為種群大小."""""""""""""""""""""""""""""""""""""""""""

定義2" 對于任意兩狀態(tài)xi∈θ，xj∈θ，CSO算法迭代過程中雞個體從狀態(tài)xi一步轉(zhuǎn)移到狀態(tài)xj，記為Tθ（xi）=xj.

定理1" CSO算法中，雞個體從狀態(tài)xi轉(zhuǎn)移到xj的一步轉(zhuǎn)移概率為：

P｛Tθ（xi）=xj｝=Pr｛Tθ（xi）=xj｝，公雞，Ph｛Tθ（xi）=xj｝，母雞，Pc｛Tθ（xi）=xj｝，小雞.（10）

證明" 過程詳見參考文獻［12］中的定理1.

由于CSO算法中公雞、母雞和小雞有不同的位置更新策略，故它們從狀態(tài)xi轉(zhuǎn)移到xj也有著不同的一步轉(zhuǎn)移概率.公雞的一步轉(zhuǎn)移概率為：

Pr｛Tθ（xi）=xj｝=1|xi×R|，xj∈［xi，xi+xi×R］，0，其他.（11）

母雞的一步轉(zhuǎn)移概率為：Ph｛Tθ（xi）=xj｝=1|S1×V1×（xr1-xi）+S2×V2×（xr2-xi）|，xj∈［xi，xi+S1×V1×（xr1-xi）+S2×V2×（xr2-xi）］，0，其他.（12）

小雞的一步轉(zhuǎn)移概率為：Pc｛Tθ（xi）=xj｝=1|FL×（xm-xi）|，xj∈［xi，xi+FL×（xm-xi）］，0，其他.（13）

定義3" CSO算法中對于θi∈Θ，θj∈Θ，雞群狀態(tài)θi一步轉(zhuǎn)移到θj記為TΘ（θi）=θj，則其一步轉(zhuǎn)移概率為：P｛TΘ（θi）=θj｝=∏Nk=1P｛Tθ（xik）=xjk｝.（14）

定義4（Markov鏈）［13］" 設｛Xn，n∈T｝為一列取值離散的隨機變量，參數(shù)集T為離散的時間序列，即T={0，1，2，…}，全體隨機變量Xn所對應取值組成的離散狀態(tài)空間為I=｛i0，i1，i2，…｝.若對任意的狀態(tài)i0，i1，i2，…，in+1∈I和整數(shù)n∈T滿足如下條件概率：P｛Xn+1=in+1|X0=i0X1=i1，…，Xn=in｝=P｛Xn+1=in+1|Xn=in｝，（15）

則稱｛Xn，n∈T｝為Markov鏈.

定理2" CSO算法中的雞群狀態(tài)序列｛θ（t），t0｝是有限齊次Markov鏈.

證明" 對于θ（t）∈Θ，θ（t+1）∈Θ，根據(jù)定義3，其一步轉(zhuǎn)移概率P｛Tθ（θ（t））=θ（t+1）｝由雞群內(nèi)所有雞的轉(zhuǎn)移概率P｛Tθ（x（t））=x（t+1）｝決定.根據(jù)定理1，可知雞群內(nèi)任意雞的狀態(tài)轉(zhuǎn)移概率P｛Tθ（x（t））=x（t+1）｝僅與t時刻的狀態(tài)x（t）以及式（2）～（7）中隨機數(shù)R、V1、V2，常數(shù)B1、B2，第i只母雞有關的公雞xr1，雞群中隨機選擇的公雞或母雞個體xr2，跟隨系數(shù)FL和與小雞的母雞媽媽xm有關.所以一步轉(zhuǎn)移概率P｛TΘ（θ（t））=θ（t+1）｝也僅與t時刻的狀態(tài)式（2）～（7）中的相關參數(shù)有關，而與t時刻無關，即：雞群狀態(tài)序列｛θ（t），t0｝具有Markov性；對于任何優(yōu)化算法來說，其搜索空間都是有限的，因此CSO算法中每只雞的狀態(tài)xi也都是有限的.而雞群狀態(tài)空間Θ又由N只雞的狀態(tài)共同組成，故Θ也是有限的；再根據(jù)定理1可知，狀態(tài)轉(zhuǎn)移概率P｛Tθ（x（t））=x（t+1）｝僅與時刻的狀態(tài)x（t）有關，而與t時刻無關.故雞群狀態(tài)序列｛θ（t），t0｝是有限齊次Markov鏈.證畢.

3" CSO算法的全局收斂性分析

3.1" 基礎理論

定義5［14］" 若G=｛x*|x∈Θ，f（x*）f（x）｝為雞群狀態(tài)序列｛θ（t），t0｝的全局最優(yōu)狀態(tài)集，如果limt→∞" P｛［θ（t）∩G≠］｝=1（limt→∞" P｛［θ（t）G］｝=1），則稱雞群狀態(tài)序列｛θ（t），t0｝依概率弱（強）收斂到全局最優(yōu)狀態(tài)集G；如果P｛limt→∞［θ（t）∩G≠］｝=1（P｛limt→∞［θ（t）G］｝=1），則稱序列｛θ（t），t0｝幾乎處處弱（強）收斂到全局最優(yōu)狀態(tài)集G.

定理3" 雞群狀態(tài)序列｛θ（t），t0｝的4種收斂性有如下關系：（1）幾乎處處強收斂幾乎處處弱收斂依概率弱收斂；（2）幾乎處處強收斂依概率強收斂依概率弱收斂.

證明" 由［θ（t）G］［θ（t）∩G≠］可知，P｛［θ（t）G］｝P｛［θ（t）∩G≠］｝，所以依概率強收斂可推出依概率弱收斂，幾乎處處強收斂可推出幾乎處處弱收斂.又因limt→∞［θ（t）∩G≠］=∪∞t=1∩∞k=t［θ（t）∩G≠］，由概率的單調(diào)性可得：P｛limt→∞［θ（t）∩G≠］｝=limt→∞" P｛［∩∞k=tθ（t）∩G≠］｝limt→∞" P｛［θ（t）∩G≠］｝.所以幾乎處處弱收斂可推出依概率弱收斂.同理可得，幾乎處處強收斂可推出依概率強收斂.證畢.

定義6［15］" 如果對i∈E，有∑j∈Epij=1，稱狀態(tài)空間E為閉集.

定義7［15］" 如果閉集E有真閉子集，則稱E為可約的，反之稱E不可約.

命題1" 雞群狀態(tài)空間Θ是一個閉集.

證明" 根據(jù)定理2，雞群狀態(tài)序列｛θ（t），t0｝是有限齊次Markov鏈，故有i∈Θ，∑j∈ΘPij=1.根據(jù)定義6，可知Θ是一個閉集.證畢.

命題2" 在CSO算法中，全局最優(yōu)狀態(tài)集G是狀態(tài)空間Θ上的一個真閉子集.

證明" 首先，當G=Θ時，Θ中的每一個解都是最優(yōu)解，優(yōu)化問題沒有討論意義，故本文是基于GΘ來討論優(yōu)化問題.其次，對于θi∈G，θj≠G，θj∈Θ.由定義3可知，TΘ（θi）=θj的轉(zhuǎn)移概率為：P｛TΘ（θi）=θj｝=∏Nn=1P｛Tθ（xin）=xjn｝.若在G中至少有1只雞的狀態(tài)達到了最優(yōu)，令x*～xi0n為最優(yōu)狀態(tài)，那么有xi0n∈G，使得P｛Tθ（xi0n）=xj0n｝=0，此時P｛TΘ（θi）=θj｝=0.故G是Θ上的一個真閉子集.證畢.

命題3" 雞群狀態(tài)空間Θ是可約的.

證明" 首先從命題1可以知道整個雞群狀態(tài)空間Θ是一個最大的閉集.其次由命題2可知，雞群的全局最優(yōu)狀態(tài)集G是狀態(tài)空間Θ上的一個真閉子集.最后由定義7可知雞群狀態(tài)空間Θ是可約的.證畢.

3.2" CSO算法的幾乎處處強收斂性分析

由于利用群智能算法求解優(yōu)化問題的過程是一個迭代尋優(yōu)的過程，所以可把它轉(zhuǎn)換成一類收斂問題，利用鞅的收斂定理對其過程進行理論分析.本文考慮的是目標函數(shù)為最小值的情況，即所求雞群的適應度值越小越好，故只有找到全局最小適應度值時，才能得到全局最優(yōu)狀態(tài)集（全局最優(yōu)解）.假若雞群在第t次迭代時得到的最佳個體適應度值達到全局最優(yōu)狀態(tài)集所對應的最小適應度值f（θ*），即：f（θt）=f（θ*），那么在第t次迭代之后的任何一次迭代中雞群的最佳個體的適應度值都不會大于全局最優(yōu)解所對應的最小適應度值f（θ*），即下一次迭代時雞群的最小適應度值關于當前迭代雞群的條件期望不大于當前迭代雞群的最小適應度值.因此可把雞群的最小適應度函數(shù)f（θt）轉(zhuǎn)變?yōu)橐粋€上鞅，將研究雞群狀態(tài)序列｛θ（t），t0｝的收斂性轉(zhuǎn)化為研究f（θt）的收斂性.根據(jù)定理3可以知道，幾乎處處強收斂是強于依概率收斂的，故接下來本文將通過利用上鞅的性質(zhì)和上鞅收斂定理來證明CSO算法的幾乎處處強收斂性.

定義8［15］" 如果隨機過程｛Yk，k0｝與｛Xk，k0｝滿足以下條件：（1）E（|Yk|）＜∞；（2）E（Yk+1|X0，X1，…，Xk）Yk（或E（Yk+1|X0，X1，…，Xk）Yk）；（3）Yk是X0，X1，…，Xk的函數(shù)；則稱隨機過程｛Yk，k0｝是關于｛Xk，k0｝的上鞅（或下鞅）.

引理1（下鞅收斂定理）［15］" 若隨機過程｛Yk，k0｝是一個下鞅，且滿足sup E|Yk|＜∞，則一定存在一個隨機變量Y*∈｛Yk，k0｝使得E|Y*|＜∞，且｛Yk，k0｝以概率1收斂至Y*，即：P｛limt→∞" Yk=Y*｝=1.

引理2［15］" 引理1的結論對上鞅也成立.

定理4" 隨機過程｛f（θt），t0｝關于｛θt，t0｝是一個非負有界上鞅函數(shù)列，即對任意t0，則有E［f（θt+1）|θ0，θ1，…，θt］f（θt）.

證明" 由于適應度函數(shù)是定義在解空間上的任意非負實值函數(shù)，故f（θt）0.又因CSO算法保證了下一次迭代時雞群的最小適應度值不會大于當前迭代雞群的最小適應度值，所以可以得到：f（θt+1）f（θt）f（θt-1），所以｛f（θt），t0｝是非負有界的.再根據(jù)定理2的馬爾可夫性可得：E［f（θt+1）|θ0，θ1，…，θt］=E［f（θt+1）|θt］.（16）

因此只需證明對任意x∈Θ有：E［f（θt+1）|θt=x］f（x），（17）

根據(jù)式（17）和隨機過程的相關理論知識，式（17）不等號左邊可以轉(zhuǎn)化為：E［f（θt+1）|θt=x］=∑y∈Θf（y）P（θt+1=y|θt=x），（18）

因此需要證明的式（17）就轉(zhuǎn)化成：∑y∈Θf（y）P（θt+1=y|θt=x）f（x）.（19）

由于任意群狀態(tài)x之后的群狀態(tài)都存在：f（θt+1=y）f（θt=x），y∈Θ，可得：∑y∈Θf（y）P（θt+1=y|θt=x）∑y∈Θf（x）P（θt+1=y|θt=x）f（x）∑y∈ΘP（θt+1=y|θt=x）f（x）.（20）

由于Θ是一個閉集，故∑y∈ΘP（θt+1=y|θt=x）=1，所以式（20）成立.綜上，可以證得隨機過程｛f（θt），t0｝關于｛θt，t0｝是一個非負有界上鞅函數(shù)列.證畢.

定理5" 如果非負有界上鞅函數(shù)列｛f（θt），t0｝滿足sup E|f（θt）|＜∞，那么當t→∞時，一定存在一個群狀態(tài)隨機變量θ*∈｛θt，t0｝使得雞群狀態(tài)序列｛θt，t0｝收斂，即P｛limt→∞" θt=θ*｝=1.

證明" 由于優(yōu)化問題的全局最小適應度值f（θ*）存在（否則優(yōu)化問題無意義），則有：f（θ*）f（θt）＜∞，根據(jù)數(shù)學期望的性質(zhì)有：E［f（θ*）］E［f（θt）］＜∞，所以sup E|f（θt）|＜∞.又根據(jù)引理2，當t→∞時，一定存在f（θ*）∈｛f（θt），t0｝，使得｛f（θt），t0｝以概率1收斂到f（θ*）.相應地，當t→∞時，存在θ*∈｛θt，t0｝，使得｛θt，t0｝以概率1收斂到θ*，即P｛limt→∞" θt=θ*｝=1.證畢.

由定理5中可知，若θ*的取值是在全局最優(yōu)狀態(tài)集G中，則CSO算法將幾乎處處強收斂至全局最優(yōu).因此在定理4和定理5的條件下，記P*t=min P（θt+1|θt）為CSO算法從狀態(tài)θt轉(zhuǎn)移到θt+1的最小轉(zhuǎn)移概率，從而引出要證的定理6.

定理6" 當∑∞t=1P*t=∞時，P｛limt→∞（θtG）｝=1，即CSO算法以概率1幾乎處處強收斂到全局最優(yōu).

證明" 令Mt=｛θt∩G=|θt=a，t0｝=｛f（θt）≠f（θ*）｝，Nt=｛θt+1∩G≠|(zhì)θt+1=b，t0｝=｛f（θt）=f（θ*）｝.再令β=min｛|f（a）-f（b）|f（a）≠f（b）｝，則存在一個正實數(shù)λ，使得f（a）-f（b）λβ.由條件期望的性質(zhì)可得：

E［f（θt）］-E［f（θt+1）］=E［f（θt）］-E｛E［f（θt+1|θt）］｝=∑a∈ΘP（θt=a）｛f（θt）-

E［f（θt+1|θt=a）］｝=∑a∈ΘP（θt=a）∑b∈ΘP（b|a）［f（a）-f（b）］.

根據(jù)P*t=min P（θt+1|θt），t0與以下兩個不等式：∑a∈ΘP（b|a）P（b|a），∑a∈ΘP（θt=a）∑a∩G=P（θt=a），代入可得：E［f（θt）］-E［f（θt+1）］∑a∈ΘP（θt=a）∑b∈ΘP（b|a）λβ∑a∈ΘP（θt=a）P（b|a）λβ∑a∈ΘP（θt=a）λβP*t∑a∩G=P（θt=a）λβP*tλβP*tP（Mt），對上式中的t從1到N求和可得：E［f（θ1）］E［f（θ1）］-E［f（θN+1）］λβ∑Nt=1P（Mt）P*t，當N→∞時，可得∑∞t=1P（Mt）P*t＜∞.當∑∞t=1P*t=∞時，P（Mt）→0，有P｛limt→∞ f（θt）≠f（θ*），t0｝=0或P｛limt→∞ f（θt）=f（θ*），t0｝=1，即：P｛limt→∞ θt∩G=|θt=a，t0｝=0或P｛limt→∞ θtG|θt=a，t0｝=1.當t→∞時，雞群狀態(tài)序列｛θt，t0｝收斂至群狀態(tài)隨機變量θ*.此外，θ*∈｛θt，t0｝且θ*的取值在全局最優(yōu)狀態(tài)集G中.即：當∑∞t=1P*t=∞時，CSO算法幾乎處處強收斂到全局最優(yōu).證畢.

3.3" CSO算法的一致收斂性分析

定義9（一致收斂）［16］" 設在同一個可測集F上有函數(shù)列｛fn（x），n∈N｝和函數(shù)f（x），ε＞0，N（ε）＞0，使得當nN（ε）時，對x∈F，都有|fn（x）-f（x）|＜ε，則稱在F上有函數(shù)列｛fn（x）｝一致收斂于f（x）.

引理3（Egoroff定理）［16］" 若μ（A）＜∞，｛fn（x），n∈N｝是可測集A上幾乎處處有限并可測的函數(shù)列，它在A上幾乎處處收斂于函數(shù)f（x），即：limn→∞ fn（x）=f（x）.則對每個ε＞0，存在可測集AcA，使得在Ac上函數(shù)列｛fn（x），n∈N｝一致收斂至函數(shù)f（x）.

定理7" 函數(shù)列｛f（θt），t0｝一致收斂于函數(shù)f（θ*）.

證明" 因雞群狀態(tài)空間Θ是有限的，故|Θ|中僅包含有限個不同的點.又因｛f（θt），t0｝是非負有界上鞅，所以其極限幾乎處處存在且是有界的.由定理5可知，limt→∞ f（θt）=f（θ*），因此根據(jù)引理3可推出函數(shù)列｛f（θt），t0｝具有一致收斂性，即對ε＞0，N（ε）＞0，使得當tN（ε）時，對θ∈G，GΘ，有|f（θt）-f（θ*）|＜ε.所以，函數(shù)列｛f（θt），t0｝一致收斂于函數(shù)f（θ*），由此可推出θt（ε）G.也就是說，能確保在有限步數(shù)N（ε）內(nèi)，CSO算法以概率1收斂到全局最優(yōu).一致收斂性具有“有限終止”的特點，因此它是強于幾乎處處強收斂性的.證畢.

4" CSO算法的實驗與分析

為了驗證本文理論證明的正確性及比較各算法的收斂性能和特點，本節(jié)決定對DE算法、PSO算法和CSO算法進行仿真實驗，即：選取具有不同特征的16個標準測試函數(shù)，再利用DE、PSO和CSO分別對它們進行重復30次的尋優(yōu)計算，再從平均值、標準差、平均耗時3個方面來進行算法間的比較.其中，算法的收斂精度和尋優(yōu)能力體現(xiàn)在平均值上，算法抗局部極值的能力和穩(wěn)定性體現(xiàn)在標準差上，算法的快速性體現(xiàn)在平均耗時上.在16個標準測試函數(shù)中，F(xiàn)1～F4是單峰函數(shù)，分別是Sphere，Schwefel's 2.22，Rosenbrock，Quartic，且最優(yōu)值都為0.單峰函數(shù)能很好地測試算法的收斂精度和尋優(yōu)能力；F5～F10是多峰函數(shù)，分別是Rastrigin，Griewank，Beale，Schaffer，Kowalik，Branin，且Rastrigin，Griewank，Beale，Schaffer的最優(yōu)值為0，Kowalik和Branin的最優(yōu)值分別為0.000 3和0.398 0.多峰函數(shù)能很好地展現(xiàn)算法的全局搜索能力以及避免局部最優(yōu)的能力；F11～F16是固定維多峰函數(shù)，分別是2維的Shekel's Foxholes，Drop-Wave，Three-hump Camel，Levy N.13，4維的Styblinski-Tang和6維的Powell，且Shekel's Foxholes的最優(yōu)值為1，Drop-Wave的最優(yōu)值為-1，Three-hump Camel，Levy N.13和 Powell的最優(yōu)值為0，Styblinski-Tang的最優(yōu)值為-156.664 0.固定維多峰函數(shù)能很好地衡量算法在低維時的全局搜索能力.

此外，為了方便對算法進行比較，決定把3個算法的通用參數(shù)設置一樣，固定維度除外，即：最大迭代次數(shù)M=1 000，種群大小N=30，維度D=30.3個算法的其他參數(shù)設置如下，CSO算法：Nr=0.2N，Nh=0.6N，Nm=0.1Nh，Nc=N-Nr-Nh，G=10，F(xiàn)L∈［0.5，0.9］;PSO算法：c1=c2=2，w=0.75;DE算法：F=0.5，CR=0.3，Xmin=-30，Xmax=30.在仿真實驗中，若實驗運行結果與函數(shù)的最優(yōu)值相差小于10-8，就認為尋優(yōu)成功.表1為實驗運行得到的最終結果，并用粗體來標出每個測試函數(shù)中平均值、標準差、平均耗時的最優(yōu)值.

在表1中，CSO算法在函數(shù)F1，F(xiàn)2，F(xiàn)7，F(xiàn)8，F(xiàn)10，F(xiàn)12，F(xiàn)13，F(xiàn)14和F16上都找到了它們的全局最小值，這表明CSO算法在有限的迭代次數(shù)內(nèi)可以收斂到問題的全局最優(yōu)，從而驗證本文定理7中所得到的結論.從收斂精度和尋優(yōu)能力來看，與其他兩種算法相比，CSO算法在F1，F(xiàn)2，F(xiàn)3，F(xiàn)4，F(xiàn)5，F(xiàn)7，F(xiàn)8，F(xiàn)10，F(xiàn)12，F(xiàn)13，F(xiàn)14上收斂精度最高，尋優(yōu)能力最強.雖然DE算法的收斂精度和尋優(yōu)能力在函數(shù)F6，F(xiàn)9，F(xiàn)11，F(xiàn)15和F16上是最高的，但CSO算法所得到的結果僅次于它.從對抗局部極值的能力和算法的穩(wěn)定性來看，相較于PSO算法和DE算法，CSO算法在函數(shù)F1，F(xiàn)2，F(xiàn)3，F(xiàn)4，F(xiàn)5，F(xiàn)7，F(xiàn)8，F(xiàn)12，F(xiàn)13，F(xiàn)14上抗局部極值能力較強，穩(wěn)定性較好.而在F6，F(xiàn)9，F(xiàn)10，F(xiàn)11，F(xiàn)15和F16上，CSO算法的抗局部極值能力和穩(wěn)定性稍差一點，在3種算法中居于第2.對于所有的標準測試函數(shù)，從平均耗時上看，PSO 算法平均耗時最短，CSO 算法的平均耗時要稍大于DE 算法的平均耗時.總的來說，CSO算法的收斂性能要好于DE算法和PSO算法，同時還有著較好的抗局部極值能力和穩(wěn)定性.雖然在計算時間上要稍弱于其他算法，但是對于計算時間要求不是特別高的優(yōu)化問題，CSO 算法比其他兩種算法明顯在應用上更具有優(yōu)勢.

5" 結" 論

本文在CSO算法Markov鏈模型的基礎上，通過一系列的定義、定理把具有最小適應度值的雞群狀態(tài)序列轉(zhuǎn)化成一個上鞅，利用鞅方法證明了CSO算法的幾乎處處強收斂性，進一步也證明了CSO算法的一致收斂性.此外，仿真實驗也成功驗證了本文理論證明的正確性并體現(xiàn)出了CSO算法的特點.與現(xiàn)有的結論相比，得到了CSO算法更強的收斂性證明結果，這將對未來CSO算法的改進和應用提供更多的理論基礎.下一步將對CSO算法的改進優(yōu)化進行研究，并利用鞅方法對改進的CSO算法進行更深入的收斂性理論分析.

參" 考" 文" 獻

［1］ ""MENG X B，LIU Y，GAO X Z，et al.A new bio-inspired algorithm：chicken swarm optimization［C］// International Conference in Swarm Intelligence.Cham：Springer，2014：86-94.

［2］李冰曉，萬睿之，朱永杰，等.基于種群分區(qū)的多策略綜合粒子群優(yōu)化算法［J］.河南師范大學學報（自然科學版），2022，50（3）：85-94.

LI B X，WAN R Z，ZHU Y J，et al.Multi-strategy comprehensive article swarm optimization algorithm based on population partition［J］.Journal of Henan Normal University（Natural Science Edition），2022，50（3）：85-94.

［3］方景遠，季益勝，趙新超.基于高斯分布估計的對位差分進化算法［J］.河南師范大學學報（自然科學版），2021，49（3）：27-32.

FANG J Y，JI Y S，ZHAO X C.Opposition-based differential evolution algorithm with Gaussian distribution estimation［J］.Journal of Henan Normal University（Natural Science Edition），2021，49（3）：27-32.

［4］郭堃，薛太林，耿杰，等.基于改進雞群算法的無功優(yōu)化綜合分析［J］.電氣自動化，2021，43（6）：36-38.

GUO K，XUE T L，GENG J，et al.Comprehensive analysis of reactive power OptimizationBased on improved chicken population algorithm［J］.Electrical Automation，2021，43（6）：36-38.

［5］寇德昌.改進的雞群算法及其應用［D］.北京：北京建筑大學，2021.

［6］王英聰，劉馳，王延峰.基于刺激-響應機制的改進雞群算法［J］.控制與決策，2023，38（1）：58-66.

WANG Y C，LIU C，WANG Y F.Chicken swarm optimization algorithm based on stimulus-response mechanism［J］.Control and Decision，2023，38（1）：58-66.

［7］楊菊蜻，張達敏，張慕雪，等.一種混合改進的雞群優(yōu)化算法［J］.計算機應用研究，2018，35（11）：3290-3293.

YANG J Q，ZHANG D M，ZHANG M X，et al.Hybrid improved for chicken swarm optimization algorithm［J］.Application Research of Computers，2018，35（11）：3290-3293.

［8］李春紅，陸安江，邵麗萍.基于線性遞減權值更新的雞群算法［J］.智能計算機與應用，2020，10（2）：43-47.

LI C H，LU A J，SHAO L P.Rooster algorithm based on linear decrement weight update［J］.Intelligent Computer and Applications，2020，10（2）：43-47.

［9］尚俊娜，程濤，岳克強，等.蝙蝠算法的Markov鏈模型分析［J］.計算機工程，2017，43（7）：198-202.

SHANG J N，CHENG T，YUE K Q，et al.Markov chain model analysis of bat algorithm［J］.Computer Engineering，2017，43（7）：198-202.

［10］張孟健，龍道銀，王霄，等.基于馬爾科夫鏈的灰狼優(yōu)化算法收斂性研究［J］.電子學報，2020，48（8）：1587-1595.

ZHANG M J，LONG D Y，WANG X，et al.Research on convergence of grey wolf optimization algorithm based on Markov chain［J］.Acta Electronica Sinica，2020，48（8）：1587-1595.

［11］張大力，夏紅偉，張朝興，等.改進螢火蟲算法及其收斂性分析［J］.系統(tǒng)工程與電子技術，2022，44（4）：1291-1300.

ZHANG D L，XIA H W，ZHANG C X，et al.Improved firefly algorithm and its convergence analysis［J］.Systems Engineering and Electronics，2022，44（4）：1291-1300.

［12］吳定會，孔飛，紀志成.雞群算法的收斂性分析［J］.中南大學學報（自然科學版），2017，48（8）：2105-2112.

WU D H，KONG F，JI Z C.Convergence analysis of chicken swarm optimization algorithm［J］.Journal of Central South University（Science and Technology），2017，48（8）：2105-2112.

［13］錢偉民，梁漢營，楊國慶.應用隨機過程［M］.北京：高等教育出版社，2014.

［14］張文修，梁怡.遺傳算法的數(shù)學基礎［M］.西安：西安交通大學出版社，2000.

［15］LAWLER G F.Introduction to stochastic processes［M］.2nd ed.London：CRC Press，2006.

［16］程其襄，張奠宙，魏國強，等.實變函數(shù)與泛函分析基礎［M］.2版.北京：高等教育出版社，2003.

Convergence analysis of chicken swarm optimization algorithm based on martingale method

Zhou Tingting， Dai Jiajia

（School of Mathematics and Statistics， Guizhou University， Guiyang 550025， China）

Abstract： The most convergence analysis on chicken swarm optimization（CSO） algorithm belonged to weak convergence， and it cannot infer in general that the CSO algorithm would be convergent to a global optimum in a finite number of evolution steps. In order to make up for this deficiency， a martingale method was proposed to study the global convergence of CSO algorithm. Firstly， based on relevant definitions of CSO algorithm， the Markov chain model of CSO algorithm was established， and its Markov properties were analyzed. Secondly， the chicken swarm state sequence with the minimum fitness value was transformed into a supermartingale. By using the supermartingale convergence theorem and the Egoroff's theorem， it was proved that the CSO algorithm had almost surely strong convergence and uniform convergence. Furthermore， it was concluded that the CSO algorithm can surely convergence to a global optimum in a finite number of evolution steps when the chicken swarm state space was finite. Finally， the validity of the theoretical proofs were verified successfully in the simulation experiment， and it was found that the CSO algorithm had stronger ability to search for excellence and higher convergence accuracy than PSO algorithm and DE algorithm.

Keywords： chicken swarm optimization（CSO） algorithm; Markov chain; supermartingale convergence theorem;Egoroff's theorem; almost sure strong convergence; uniform convergence

［責任編校" 陳留院" 趙曉華］