張敏輝　楊劍

摘 要：隨著科技的快速發(fā)展，大數(shù)據(jù)時(shí)代已經(jīng)到來(lái)。對(duì)于大數(shù)據(jù)的分析與處理推動(dòng)社會(huì)經(jīng)濟(jì)的不斷發(fā)展，在大數(shù)據(jù)背景下，數(shù)據(jù)規(guī)模、處理難點(diǎn)的優(yōu)化問(wèn)題也變得更加多樣化，進(jìn)而使優(yōu)化方法成為人們?nèi)找骊P(guān)注的焦點(diǎn)。一種新型的計(jì)算技術(shù)——群智能算法，運(yùn)用高效的優(yōu)化算法對(duì)自然界社會(huì)性生物群體進(jìn)行模擬，解決各個(gè)領(lǐng)域的實(shí)際問(wèn)題。本文提出群智能算法中的自適應(yīng)優(yōu)化算法——粒子群算法，詳細(xì)分析粒子群算法的原理，為了提高全局搜索能力及計(jì)算效率，本文加入了種群自適應(yīng)增加/刪除個(gè)體數(shù)目方法有效改進(jìn)種群多樣化，提高收斂速度及質(zhì)量?；谶壿嬎怪B模型的算子設(shè)計(jì)有效地增強(qiáng)了粒子群的多樣性，自適應(yīng)控制策略更具有一般性特征，可更好地應(yīng)用到不同的群智能算法中，解決大數(shù)據(jù)問(wèn)題的優(yōu)化性。

關(guān)鍵詞：大數(shù)據(jù)； 智能算法； 優(yōu)化； 粒子群

Abstract： With the rapid development of science and technology， the era of big data has come. The analysis and processing of big data will promote the continuous development of society and economics. In the background of big data， the optimization of data size and processing difficulties has become more diversified， and the optimization method has become the focus of people's attention. A new computing technology， group intelligence algorithm， is used to simulate the social biological groups in nature by using efficient optimization algorithms to solve practical problems in various fields. In this paper， an adaptive optimization algorithm， particle swarm optimization （PSO） algorithm， is proposed. The principle of particle swarm optimization is analyzed in detail. In order to improve the global search ability and efficiency， this paper adds a population adaptive increase / delete individual number method to improve the population diversity and improve the convergence speed and quality. The operator design based on the logistic model can effectively enhance the diversity of the particle swarm. The adaptive control strategy has more general characteristics， and can be better applied to different swarm intelligence algorithms for better solving the optimization of big data problems.

Key words： big data； intelligent algorithm； optimization； particle swarm

引言

隨著社會(huì)科技與經(jīng)濟(jì)的發(fā)展，優(yōu)化在計(jì)算機(jī)等相關(guān)領(lǐng)域占有重要地位。群智能算法作為一種全新的演化算法作用于科學(xué)計(jì)算和解決社會(huì)經(jīng)濟(jì)中[1]。國(guó)外對(duì)于群智能領(lǐng)域的研究較早，美國(guó)科學(xué)家Kennedy和Eberhart提出全新的群智能進(jìn)化計(jì)算思想—粒子群優(yōu)化模型。該模型模仿群體的社會(huì)認(rèn)知過(guò)程，對(duì)抽象概念進(jìn)行建模[2]；Eberhart R 與Shi Y 對(duì)粒子群算法進(jìn)行研究，對(duì)應(yīng)用與資源進(jìn)行總結(jié)歸納，討論慣性權(quán)重、動(dòng)態(tài)跟蹤系統(tǒng)與影響因子[3]；Settles M等將遺傳算法與粒子群算法在神經(jīng)網(wǎng)絡(luò)的性能方面進(jìn)行對(duì)比，粒子群算法在小型網(wǎng)絡(luò)性能中表現(xiàn)更好[4]。中國(guó)對(duì)于優(yōu)化問(wèn)題的研究起步較晚，王勇等人提出用微調(diào)機(jī)制改進(jìn)粒子群算法，用以提高算法的局部搜索能力，改進(jìn)粒子相似度過(guò)高的缺陷[5]；郭文忠通過(guò)研究遺傳算法的2點(diǎn)變異與交叉算子，提出混合粒子優(yōu)化算法，用于解決電路規(guī)劃問(wèn)題[6]。

由于種群規(guī)模小導(dǎo)致種群搜索能力差，反之種群規(guī)模的擴(kuò)大使得搜索范圍擴(kuò)大，提高了局部?jī)?yōu)越性，但也減慢了收斂速度，因此基于優(yōu)化問(wèn)題，文章提出一種種群規(guī)模自適應(yīng)控制算法，能夠有效地測(cè)試出傳統(tǒng)粒子群算法的函數(shù)性能。

1 群智能算法—種群規(guī)模自適應(yīng)優(yōu)化算法

1.1 種群增長(zhǎng)模型

1.1.1 種群指數(shù)式增長(zhǎng)

一種“J”型增長(zhǎng)是在理想種群環(huán)境下隨種群密度變化而增長(zhǎng)的種群指數(shù)增長(zhǎng)。其增長(zhǎng)方式分為指數(shù)增長(zhǎng)和幾何增長(zhǎng)，用方程dN/dt=rN來(lái)表示[7]，式中，dN/dt為某種群點(diǎn)時(shí)間的瞬時(shí)增長(zhǎng)率；最大潛力種群增長(zhǎng)率用r表示；N表示點(diǎn)時(shí)間的種群大小。假設(shè)在理想狀態(tài)下，自然種群可在短時(shí)間呈現(xiàn)指數(shù)似的增長(zhǎng)，且種群個(gè)體呈稟增長(zhǎng)率增長(zhǎng)，導(dǎo)致規(guī)模增大。有研究發(fā)現(xiàn)，沒(méi)有一種種群是無(wú)休止增長(zhǎng)的，都存在一定的局限性，受種群規(guī)模、密度、濃度等因素制約，因此，種群增長(zhǎng)可達(dá)到一定的上限。

1.1.2 種群的邏輯斯諦增長(zhǎng)

種群的邏輯斯諦增長(zhǎng)用“S”型增長(zhǎng)來(lái)表示[8]?！癝”型增長(zhǎng)的表現(xiàn)方式為由慢到快的逐漸式增長(zhǎng)。由于受到外界因素的干擾，種群的增長(zhǎng)速度隨之下降，越來(lái)越靠近漸近線發(fā)展，此條漸近線稱之為環(huán)境容納量，用K來(lái)表示，也就意味著種群可以達(dá)到最大密度。在自然環(huán)境中，絕大部分種群是按照“S”型增長(zhǎng)的。

“S”型增長(zhǎng)用數(shù)學(xué)方程式表示：

dN/dt=rN（K-N/K）（1）

種群的增長(zhǎng)曲線成“S”型，該曲線的特點(diǎn)表示當(dāng)種群數(shù)量達(dá)到環(huán)境容納量K之后，增長(zhǎng)將會(huì)停止并保持穩(wěn)定?！癝”型種群的增長(zhǎng)曲線具有以下特點(diǎn)：

（1）種群在開(kāi)始進(jìn)入某區(qū)域時(shí)，會(huì)進(jìn)行短時(shí)期的調(diào)整，以適應(yīng)該區(qū)域的增長(zhǎng)環(huán)境。因此，該時(shí)期的種群呈現(xiàn)零增長(zhǎng)態(tài)勢(shì)，個(gè)體不繁殖。

（2）隨著環(huán)境的改善，營(yíng)養(yǎng)物質(zhì)日益豐富，種群已適應(yīng)了該環(huán)境并開(kāi)始劇烈增長(zhǎng)。導(dǎo)致種群密度增加，數(shù)量以等比形式增加（2n），此階段生長(zhǎng)曲線“J”表現(xiàn)為對(duì)數(shù)上升。

（3）由于種群密度增大，進(jìn)而營(yíng)養(yǎng)物質(zhì)消耗殆盡，種群進(jìn)入穩(wěn)定狀態(tài)。隨著外界環(huán)境的阻力增大，種群間競(jìng)爭(zhēng)更加激烈，密度達(dá)到最大量時(shí)，種群不再增長(zhǎng)。

1.2 種群規(guī)模自適應(yīng)粒子群算法研究

1.2.1 種群自適應(yīng)增加/刪除個(gè)體數(shù)目方法

種群的規(guī)模動(dòng)態(tài)變化，不僅能提高搜索數(shù)據(jù)能力還能提高計(jì)算效率。一旦加入適合增加或者刪除算子，將有效地增加種群多樣性，迅速提高收斂速度和搜索質(zhì)量。接下來(lái)介紹自適應(yīng)增加或者刪除個(gè)體方法。

（1）基于Logistic模型的自適應(yīng)增加/刪除個(gè)體方法

對(duì)于單個(gè)種群個(gè)體來(lái)講，在進(jìn)入初始區(qū)域會(huì)對(duì)環(huán)境有一個(gè)短暫的適應(yīng)過(guò)程，此時(shí)種群的增長(zhǎng)率較低；經(jīng)過(guò)適應(yīng)階段之后，種群進(jìn)入快速增長(zhǎng)時(shí)期，單個(gè)個(gè)體會(huì)以等比例形式增加；而進(jìn)入穩(wěn)定期，種群增加相對(duì)劇烈，種群密度也達(dá)到最大值，種群將不再增長(zhǎng)。然而種群個(gè)體的減少在生長(zhǎng)初期表現(xiàn)的并不明顯，由于生長(zhǎng)環(huán)境相對(duì)優(yōu)越，種群密度小，適合種群增長(zhǎng)；進(jìn)入快速發(fā)育期，數(shù)量發(fā)展迅速，進(jìn)入穩(wěn)定期后，種群競(jìng)爭(zhēng)激烈，環(huán)境越來(lái)越差，導(dǎo)致個(gè)體死亡數(shù)量隨之增加。

①基于Logistic模型的內(nèi)在增長(zhǎng)算子

種群個(gè)體的增加對(duì)生長(zhǎng)率產(chǎn)生的抑制效應(yīng)為1/K，設(shè)種群最大規(guī)模為K，種群數(shù)量為 N，個(gè)體所占空間為N/K，其余空間為（1-N/K），既而定義內(nèi)在增長(zhǎng)算子為（1-N/K）。

由方程可知，在初始階段，種群密度小的前提下，種群容納量的上限與種群的增長(zhǎng)率成正比：隨著種群密度的增大，種群的死亡率增加，距離上限K越近，死亡率越高。因此，當(dāng)N=K時(shí)，死亡率接近1。

②基于Logistic模型的內(nèi)在減少算子

內(nèi)在減少算子用N/K來(lái)表示，其意義在于，當(dāng)種群密度較小時(shí)，種群的可容納量與種群的減少率成反比：也就是說(shuō)種群密度增大，種群的減少率加快，接近容納量上限K時(shí)，減少率最大，因此N=K時(shí)，減少率接近1。

③定義種群波動(dòng)算子

在一段時(shí)間內(nèi)，種群在沒(méi)有適合種群覓食點(diǎn)的情況下，會(huì)通過(guò)提高減少率來(lái)適應(yīng)種群環(huán)境。也就是說(shuō)，在穩(wěn)定期后，種群數(shù)量巨多，營(yíng)養(yǎng)物質(zhì)供不應(yīng)求，導(dǎo)致個(gè)體在營(yíng)養(yǎng)消耗殆盡的前提下，死亡率會(huì)增加。然而，在種群減少的同時(shí)，相應(yīng)的種群密度也會(huì)減小，有新的營(yíng)養(yǎng)物產(chǎn)生的話，種群的生長(zhǎng)率又會(huì)增加，進(jìn)而形成動(dòng)態(tài)平衡現(xiàn)象。

（2）外部環(huán)境影響

在大自然的生態(tài)系統(tǒng)中，生存環(huán)境與種群發(fā)展規(guī)模相互制約。由于Logistic模型的局限性，不能全面反應(yīng)制約種群規(guī)模發(fā)展的環(huán)境因素，因此，定義外部環(huán)境算子可更好地反映種群的增長(zhǎng)規(guī)律。

（3）定義外部環(huán)境算子

外部環(huán)境影響率為F（t），假設(shè)F（t）>0.5，環(huán)境變化隨著時(shí)間而改善，種群增長(zhǎng)速度變快；反之F（t）<0.5，環(huán)境隨時(shí)間變的惡劣，種群的增長(zhǎng)速度則會(huì)減慢。

1.2.2 種群規(guī)模自適應(yīng)粒子群算法描述

粒子群算法是由Kennedy和Eberhart提出的智能進(jìn)化算法，是基于鳥類聚集與覓食的社會(huì)性行為的算法。在粒子群算法中，將粒子置于一個(gè)搜索空間中，每個(gè)粒子都具有適應(yīng)度值，單個(gè)粒子的最佳位置和全局最佳位置與速度進(jìn)行不斷更新，粒子群隨著最優(yōu)的方向移動(dòng)。粒子群作為整體像鳥兒合作覓食一樣，尋找到目標(biāo)函數(shù)的最優(yōu)點(diǎn)。粒子群算法是基于迭代的優(yōu)化算法，用于優(yōu)化搜索空間。對(duì)于粒子群的數(shù)學(xué)描述如下[9]：

由m個(gè)粒子組成的種群以一定的速度飛翔，單個(gè)粒子以個(gè)體最優(yōu)和全局最優(yōu)位置進(jìn)行不斷更新。三維向量組成的粒子為[10]：

初始位置：

將APOS與POS算法進(jìn)行對(duì)比，在函數(shù)的求解精度以及收斂速度方面，APOS算法均高于POS算法。對(duì)種群的自適應(yīng)能力進(jìn)行調(diào)整，測(cè)試數(shù)量有所減少，有效地提高了CPU的計(jì)算速度，更新了效率。使用自適應(yīng)增加/刪除個(gè)體的方法，增強(qiáng)了算法的有效性及適應(yīng)性。APSO與PSO測(cè)試結(jié)果見(jiàn)表2。

2 結(jié)束語(yǔ)

本文提出的種群規(guī)模自適應(yīng)控制方法，通過(guò)基于Logistic模型的自適應(yīng)增加/刪除個(gè)體方法，包括算法中的內(nèi)增長(zhǎng)算子、內(nèi)在減少算子、波動(dòng)算子和外部環(huán)境算子的環(huán)境，其測(cè)試在速度收斂、求解以及結(jié)果的魯棒性方面都高于粒子群算法。該算子有效地增強(qiáng)了原粒子群的多樣性，使得自適應(yīng)控制策略更具一般性，能更好地適用于各種群智能算法中。

智能群算法可廣泛地應(yīng)用于大數(shù)據(jù)背景下的數(shù)據(jù)分析問(wèn)題，利用數(shù)據(jù)分析提高對(duì)全局的搜索能力；可有效地解決數(shù)學(xué)模型所遇到的問(wèn)題，提高數(shù)據(jù)處理能力。群智能算法在不斷更新優(yōu)化的同時(shí)，也使得該算法速度不斷提高，能更好地應(yīng)用到實(shí)際中，將對(duì)數(shù)據(jù)挖掘技術(shù)發(fā)揮重要的作用。

參考文獻(xiàn)

[1] 王元卓，靳小龍，程學(xué)旗. 網(wǎng)絡(luò)大數(shù)據(jù)：現(xiàn)狀與展望[J]. 計(jì)算機(jī)學(xué)報(bào)，2013，36（6）：1125-1138.

[2] PRADHAN B. A comparative study on the predictive ability of the decision tree， support vector machine and neuro-fuzzy models in landslide susceptibility mapping using GIS[J]. Computers & Geosciences， 2013， 51： 350-365.

[3] HE Liang， Van den BERG J. Meso-scale planning for multi-agent navigation[C]// 2013 IEEE International Conference on Robotics and Automation （ICRA）. Karlsruhe， Germany：IEEE， 2013： 2839-2844.

[4] 吳建輝， 章兢， 李仁發(fā)， 等. 多子種群微粒群免疫算法及其在函數(shù)優(yōu)化中應(yīng)用[J]. 計(jì)算機(jī)研究與發(fā)展， 2012， 49（9）： 1883-1898.

[5] 胡旺， YEN G G，張?chǎng)? 基于Pareto熵的多目標(biāo)粒子群優(yōu)化算法[J]. 軟件學(xué)報(bào)， 2014，25（5）： 1025-1050.

[6] 徐曉晴， 朱慶保. 動(dòng)態(tài)環(huán)境下基于多人工魚群算法和避碰規(guī)則庫(kù)的機(jī)器人路徑規(guī)劃[J]. 電子學(xué)報(bào)， 2012， 40（8）： 1694-1700.

[7] ZHANG Peng， LIU Hong， DING Yanhui. Dynamic bee colony algorithm based on multi-species co-evolution[J]. Applied intelligence， 2014， 40（3）： 427-440.

[8] GETZIN S， WEIGAND K， WIEGAND T， et al. Adopting a spatially explicit perspective to study the mysterious fairy circles of Namibia[J]. Ecography， 2015， 38（1）： 1-11.

[9] 夏亞梅， 程渤， 陳俊亮， 等. 基于改進(jìn)蟻群算法的服務(wù)組合優(yōu)化[J]. 計(jì)算機(jī)學(xué)報(bào)， 2012，35（2）： 270-281.

[10]GANDOMI A H， YUN Gunjin， YANG Xinshe， et al. Chaos-enhanced accelerated particle swarm optimization[J]. Communications in Nonlinear Science and Numerical Simulation， 2013， 18（2）： 327-340.