摘 要：分析了非線性互補(bǔ)問(wèn)題求解困難，利用粒子群算法并結(jié)合極大熵函數(shù)法給出了該類問(wèn)題的一種新的有效算法。該算法首先利用極大熵函數(shù)將非線性互補(bǔ)問(wèn)題轉(zhuǎn)化為一個(gè)無(wú)約束最優(yōu)化問(wèn)題，然后應(yīng)用粒子群算法來(lái)優(yōu)化該問(wèn)題，計(jì)算機(jī)程序?qū)崿F(xiàn)表明該算法是有效的。

關(guān)鍵詞：計(jì)算機(jī)實(shí)現(xiàn)；非線性互補(bǔ)問(wèn)題；粒子群算法

中圖分類號(hào)：O224 文獻(xiàn)標(biāo)識(shí)碼：A

Abstract：According to a class of nonlinear complementary problems difficult a new evolution algorithm is proposed this algorithm combines with maximum entropy function method.Firstly，the maximum entropy function is used to transform the nonlinear complementary problems into unconstrained optimization problem.Then particle swarm optimization algorithm（PSO） is applied to solving the unconstrained optimization problem.Lastly，computer procedure realization show that the proposed new algorithm has effectiveness.

Keywords：computer realization；nonlinear complementary problem；PSO

1 引言（Introduction）

經(jīng)典的非線性互補(bǔ)問(wèn)題[1]就是求一個(gè)向量使得

互補(bǔ)問(wèn)題是數(shù)學(xué)規(guī)劃的一個(gè)基本問(wèn)題，在工程和經(jīng)濟(jì)等領(lǐng)域也有重要應(yīng)用[3-5]，其算法研究引起廣泛重視[6]：如非光滑法、內(nèi)點(diǎn)法等。內(nèi)點(diǎn)法對(duì)單調(diào)的互補(bǔ)問(wèn)題具有多項(xiàng)式復(fù)雜界限，即算法的執(zhí)行時(shí)間在最壞的情況下為問(wèn)題規(guī)模的多項(xiàng)式函數(shù)。但在計(jì)算機(jī)不易實(shí)現(xiàn)，原因是初始點(diǎn)難以找到。非光滑牛頓法是將互補(bǔ)問(wèn)題通過(guò)NCP函數(shù)轉(zhuǎn)化為解方程組的問(wèn)題，它的奇妙之處在于將包含等式和不等式的三個(gè)條件化為只含一個(gè)等式的問(wèn)題，但基于可微的NCP函數(shù)的方程組在退化解處（互補(bǔ)問(wèn)題（1）的退化解是指對(duì)某坐標(biāo)下標(biāo)有）的雅可比矩陣是奇異的[7]，這樣牛頓法的局部快速收斂性不再具備。總的來(lái)說(shuō)，目前這些算法都需要計(jì)算梯度，且需要給定初始點(diǎn)，并且針對(duì)解不唯一的互補(bǔ)問(wèn)題，傳統(tǒng)算法無(wú)法同時(shí)找到多個(gè)最優(yōu)解。利用NCP函數(shù)把NCP（F）轉(zhuǎn)化為非線性方程組的方法頗受青睞。如果函數(shù)滿足條件

性質(zhì)3：若二次連續(xù)可微，在光滑，則二階連續(xù)可微且也為二次連續(xù)可微函數(shù)。

對(duì)于問(wèn)題（6）我們采用粒子群優(yōu)化算法[10，11]。粒子群優(yōu)化（Particle Swarm Optimization，簡(jiǎn)稱PSO）算法是由kennedy和Eberhart[12]于1995年提出，該方法對(duì)優(yōu)化目標(biāo)函數(shù)的連續(xù)可微性沒(méi)有要求，且不需要給定初始點(diǎn)和梯度信息，簡(jiǎn)單易行，且收斂速度快，受到國(guó)內(nèi)外學(xué)者的廣泛關(guān)注。

2 粒子群算法（Particle Swarm Optimization algorithm（PSO））

文獻(xiàn)[13]從量子力學(xué)角度，在標(biāo)準(zhǔn)PSO基礎(chǔ)上提出量子粒子群算法（，

）。在中，由于粒子滿足聚離態(tài)性質(zhì)不同，粒子在整個(gè)可行解空間搜索尋求全局最優(yōu)解。中，粒子群中每個(gè)粒子必須收斂于各自的隨機(jī)點(diǎn)為粒子維數(shù)，粒子群按式（8）式（11）移動(dòng)。

其中，為第個(gè)粒子在迭代中位置；為第個(gè)粒子本身所找到的局部最優(yōu)位置；為整個(gè)種群目前找到的全局最優(yōu)位置；為第個(gè)粒子最優(yōu)位置中心；都是隨機(jī)數(shù)；為收縮擴(kuò)張系數(shù)，

為粒子當(dāng)前迭代數(shù)；為種群規(guī)模，為最大迭代代數(shù)。

3 數(shù)值模擬（Numerical Simulation）

為了測(cè)試本文算法的求解性能，下面選擇經(jīng)典非線性互補(bǔ)問(wèn)題，這些算例均來(lái)自MCPLIB算例庫(kù)，其意義在文獻(xiàn) [14]中有所闡述。

本文參數(shù)設(shè)置如下：，，，程序由matlab編程，并在普通PC機(jī)上運(yùn)行（CPU2.00GHz，內(nèi)存1024MB），算法運(yùn)行100次，取平均計(jì)算結(jié)果。限于篇幅，表1給出其中運(yùn)行結(jié)果。

4 結(jié)論（Conclusion）

本文提出了混合量子粒子群優(yōu)化算法來(lái)求解非線性互補(bǔ)問(wèn)題。該方法主要是利用進(jìn)化算法處理優(yōu)化問(wèn)題，計(jì)算結(jié)果更可靠。另外本文算法給求解非線性互補(bǔ)問(wèn)題提供一種新途徑，對(duì)于線性互補(bǔ)問(wèn)題同樣適用，同時(shí)也拓展了群智能優(yōu)化算法適用范圍。數(shù)值實(shí)驗(yàn)表明新算法的有效性。

參考文獻(xiàn)（References）

[1] Harker P T，Pang Js.Finite-dimensional Variational inequality and nonliner complementarity problems， a survey review of theory，algorithms and applications[J].Math Prog，1990：161-220.

[2] F.Facchinei，J.S.Rang，F(xiàn)inite-demensional Variational inequalities and complenentarity problems Spring-Verlag NewYork，Inc.，2003.

[3] F.Faechinei and J-S.Pang，F(xiàn)inite-dimensional variationaline inequalities and complementarity probles，Springer-Verlag，NewYork，2003.endprint

[4] G.Isac.Complementarity problems，Springer-verlag，Berlin，1992.

[5] M.Cferris and J.S.pang，Engineering and ecomic aplications of complementarity problems，SIAM J.Review，39（1997），669-713.

[6] 修乃華，高自友.互補(bǔ)問(wèn)題算法的新進(jìn)展[J].數(shù)學(xué)進(jìn)展，1999，28（3）：193-210.

[7] Wright S.J An infeasible-interior-point algorithm for linear complementarity problems[J].Mathematical programming Newton，1994，64：29-51.

[8] 李興斯.一類不可微優(yōu)化問(wèn)題的有效解法.中國(guó)科學(xué)（A輯），1994，4（2）：371-377.

[9] 李興斯.解非線性極大極小問(wèn)題的凝聚函數(shù)方法[J].計(jì)算結(jié)構(gòu)力學(xué)及其應(yīng)用，1991（8）：85-92.

[10] He Q，WangL.An effective co-evolutionary particle swarm.optimization for constrained engineering design problems[J].Engineering Applications of Artifical Intelligence，2007，20（1）：89-99.

[11] Runarsson T P，Yao X.Stochastic ranking for constrained evolutionary optimization [J].IEEE Trans，Evol.Comput，2000，4（3）：284-294.

[12] Kennedy J，Eberhart R.particle swarm optimization [C]IEEE.International conference on Neural Networks，Peth，Australia，1995：1942-1948.

[13] Sun.Jun，Xu Feng-bin，Xu Wen-bo.Particle Swarm optimization with particles having quantum behavior[C].proc of congress on Evolutionary computation，2004：325-331.

[14] J.S.Pang and L.Qi Nonsmooth equations：motivation and algorithm，SIAM Optim.3，1993：443-465.

作者簡(jiǎn)介：

朱鐵鋒（1979-），男，碩士，講師.研究領(lǐng)域：計(jì)算數(shù)學(xué)，程序?qū)崿F(xiàn).endprint

[4] G.Isac.Complementarity problems，Springer-verlag，Berlin，1992.

[5] M.Cferris and J.S.pang，Engineering and ecomic aplications of complementarity problems，SIAM J.Review，39（1997），669-713.

[6] 修乃華，高自友.互補(bǔ)問(wèn)題算法的新進(jìn)展[J].數(shù)學(xué)進(jìn)展，1999，28（3）：193-210.

[7] Wright S.J An infeasible-interior-point algorithm for linear complementarity problems[J].Mathematical programming Newton，1994，64：29-51.

[8] 李興斯.一類不可微優(yōu)化問(wèn)題的有效解法.中國(guó)科學(xué)（A輯），1994，4（2）：371-377.

[9] 李興斯.解非線性極大極小問(wèn)題的凝聚函數(shù)方法[J].計(jì)算結(jié)構(gòu)力學(xué)及其應(yīng)用，1991（8）：85-92.

[10] He Q，WangL.An effective co-evolutionary particle swarm.optimization for constrained engineering design problems[J].Engineering Applications of Artifical Intelligence，2007，20（1）：89-99.

[11] Runarsson T P，Yao X.Stochastic ranking for constrained evolutionary optimization [J].IEEE Trans，Evol.Comput，2000，4（3）：284-294.

[12] Kennedy J，Eberhart R.particle swarm optimization [C]IEEE.International conference on Neural Networks，Peth，Australia，1995：1942-1948.

[13] Sun.Jun，Xu Feng-bin，Xu Wen-bo.Particle Swarm optimization with particles having quantum behavior[C].proc of congress on Evolutionary computation，2004：325-331.

[14] J.S.Pang and L.Qi Nonsmooth equations：motivation and algorithm，SIAM Optim.3，1993：443-465.

作者簡(jiǎn)介：

朱鐵鋒（1979-），男，碩士，講師.研究領(lǐng)域：計(jì)算數(shù)學(xué)，程序?qū)崿F(xiàn).endprint

[4] G.Isac.Complementarity problems，Springer-verlag，Berlin，1992.

[5] M.Cferris and J.S.pang，Engineering and ecomic aplications of complementarity problems，SIAM J.Review，39（1997），669-713.

[6] 修乃華，高自友.互補(bǔ)問(wèn)題算法的新進(jìn)展[J].數(shù)學(xué)進(jìn)展，1999，28（3）：193-210.

[7] Wright S.J An infeasible-interior-point algorithm for linear complementarity problems[J].Mathematical programming Newton，1994，64：29-51.

[8] 李興斯.一類不可微優(yōu)化問(wèn)題的有效解法.中國(guó)科學(xué)（A輯），1994，4（2）：371-377.

[9] 李興斯.解非線性極大極小問(wèn)題的凝聚函數(shù)方法[J].計(jì)算結(jié)構(gòu)力學(xué)及其應(yīng)用，1991（8）：85-92.

[10] He Q，WangL.An effective co-evolutionary particle swarm.optimization for constrained engineering design problems[J].Engineering Applications of Artifical Intelligence，2007，20（1）：89-99.

[11] Runarsson T P，Yao X.Stochastic ranking for constrained evolutionary optimization [J].IEEE Trans，Evol.Comput，2000，4（3）：284-294.

[12] Kennedy J，Eberhart R.particle swarm optimization [C]IEEE.International conference on Neural Networks，Peth，Australia，1995：1942-1948.

[13] Sun.Jun，Xu Feng-bin，Xu Wen-bo.Particle Swarm optimization with particles having quantum behavior[C].proc of congress on Evolutionary computation，2004：325-331.

[14] J.S.Pang and L.Qi Nonsmooth equations：motivation and algorithm，SIAM Optim.3，1993：443-465.

作者簡(jiǎn)介：

朱鐵鋒（1979-），男，碩士，講師.研究領(lǐng)域：計(jì)算數(shù)學(xué)，程序?qū)崿F(xiàn).endprint