• 
    

    
    

      99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

      基于人工蜂群算法的p-center問題求解算法*

      2020-06-22 12:49:54包敏澤胡秀婷謝玉瑩
      計算機工程與科學(xué) 2020年6期
      關(guān)鍵詞:蜜源蜂群適應(yīng)度

      包敏澤,胡秀婷,謝玉瑩,蔣 波

      (大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院,遼寧 大連 116026)

      1 引言

      近年來,p-center問題受到了人們的廣泛關(guān)注。所謂p-center問題,是指對給定的n個點,要求計算出p個圓,使得這些圓的并集能夠完全覆蓋所有給定的點,且使得最大圓的直徑達到最小[1]。p-center問題通常限定在平面上,因而也稱之為平面p-center問題,簡稱為p-center問題。p-center問題有2種類型:離散型和連續(xù)型。離散型p-center問題要求計算出的所有圓心均為給定點集中的點,而連續(xù)型p-center問題則沒有該約束,其圓心可在任意位置上。p-center問題不僅是一個理論問題,而且具有很大的實際應(yīng)用價值,其中最大距離最小化的位置分配問題就是一個典型實例,它要求根據(jù)給定的n個位置點,確定p個服務(wù)設(shè)施的位置,并最大限度地減少位置點與其最近服務(wù)設(shè)施間的距離。物流站點、城鎮(zhèn)規(guī)劃、通信基站的設(shè)計等,均可借助該問題的研究結(jié)果,找到高效合理的解決方案。

      平面p-center問題是經(jīng)典的NP難題,求解該問題一般有2種思路:一是確定p的取值,然后在該取值下尋找盡可能高效的精確解;二是探索高效的啟發(fā)式求解策略。當(dāng)p值已知時,p-center問題可在O(n2p-1logn)時間內(nèi)得到解決[2],且當(dāng)p=1時,存在時間復(fù)雜度為O(n)的求解算法[3]。對于p=2的2-center問題,Sharir[4]首先使用參數(shù)搜索范式設(shè)計出了時間復(fù)雜度為O(nlog9n)的近似線性時間的求解算法。后來,Eppstein[5]給出了一種預(yù)期時間復(fù)雜度為O(nlog2n)的隨機算法。Chan[6]優(yōu)化了該算法,在相同時間復(fù)雜度下給出了成功概率更高的隨機算法。同時,Chan也給出了時間復(fù)雜度為O(n(lognlog logn)2)的確定性算法。最近,Tan等人[7]給出了凸位置點集和任意點集2-center問題的新求解算法,其時間復(fù)雜度均為O(nlog2n)。以上這些成果都是圍繞連續(xù)型2-center問題給出的。對于離散型2-center問題,Agarwal等人[8]提出了一個時間復(fù)雜度為O(n4/3log5n)的求解算法。

      針對人工蜂群算法中存在的局部最優(yōu)搜索能力不足等問題,人們從不同角度進行了深入的研究,主要包括2個方面:一是改進人工蜂群算法的搜索策略;二是通過將人工蜂群算法與其他啟發(fā)式算法結(jié)合以優(yōu)化算法性能[17]。例如,2015年,Ozturk等人[18]使用交叉互換操作處理了二進制優(yōu)化問題;2018年,智慧[19]使用與全局最優(yōu)值做交叉的方式來提高算法的探索能力;2019年,肖曉等人[20]在使用交叉算子的同時還引入了高斯變異操作來改進算法性能等。盡管人們選擇的交叉或變異的操作方式不同,但整體思路都是依據(jù)不同算子在相應(yīng)求解問題中的不同表現(xiàn)來提升算法性能。

      本文提出的用于求解平面p-center問題的高效啟發(fā)式算法(BeeGenP),也采用了人工蜂群算法和遺傳算法相結(jié)合的方式,設(shè)計了適合求解該問題的交叉和變異等操作,以改進局部搜索策略,提高算法的搜索能力。同時,為了驗證算法的有效性,構(gòu)造測試數(shù)據(jù),并依據(jù)算法的運行結(jié)果對比分析BeeGenP算法與M-ABC算法[15]的性能。

      研究中,我們約定所有圓心從給定點集中選取,即研究對象是離散型p-center問題。

      2 人工蜂群算法

      人工蜂群算法是典型的仿生群體智能算法[14]。ABC算法包含3個基本要素:蜜源(Food Sources)、雇傭蜂(Employed Foragers)和非雇傭蜂(Unemployed Foragers)。其中,非雇傭蜂包括觀察蜂和偵察蜂。一個蜜源對應(yīng)于求解問題的一個可行解,可以通過適應(yīng)度值來衡量蜜源的質(zhì)量。雇傭蜂與蜜源一一對應(yīng),且在蜜源附近做鄰域搜索,記錄相應(yīng)蜜源的信息,并將信息分享反饋給觀察蜂。觀察蜂依靠雇傭蜂所提供的信息挑選適應(yīng)度較好的蜜源,而偵察蜂則隨機選擇新蜜源。當(dāng)選擇好新蜜源后,則繼續(xù)各自的開采工作。

      令SN表示蜜源個數(shù),即解的個數(shù),也是雇傭蜂和觀察蜂的個數(shù)。假設(shè)用xi表示第i個蜜源的初始解,則xi=(xi1,xi2,…,xiD)是一個D維向量,i=1,2,…,SN,D是問題的維數(shù)。ABC算法包含如下4個基本步驟:

      (1) 在當(dāng)前解空間中隨機初始化種群,并計算解的適應(yīng)度值。

      (2) 雇傭蜂搜索當(dāng)前蜜源的鄰域,每個雇傭蜂根據(jù)式(1)生成一個新的解,即新的蜜源位置并計算適應(yīng)度值,之后根據(jù)貪婪原則選擇適應(yīng)度值大的蜜源加以保留。

      vij=xij+φij(xij-xkj),k≠i

      (1)

      其中,φij是[-1,1]上均勻分布的隨機數(shù),k∈{1,2,…,SN}和j∈{1,2,…,D}都是隨機選取的。雇傭蜂完成搜索后,將蜜源解信息分享給觀察蜂。

      (3) 觀察蜂根據(jù)接收到的信息,通過式(2)的輪盤賭概率選擇一個蜜源,并在該蜜源附近通過式(1)做鄰域搜索以及通過貪婪原則選擇更好的蜜源。

      (2)

      其中,fiti是解的適應(yīng)度值,按式(3)進行計算。

      (3)

      其中,fi是第i個解的目標函數(shù)值。

      (4) 若一個蜜源的解在進行了預(yù)先設(shè)定的有限次探索后其適應(yīng)度值仍沒有提高,那么該蜜源就會被舍棄,且所對應(yīng)的雇傭蜂就會變成偵察蜂,并可通過式(4)隨機搜索新的蜜源。

      xij=Lj+rand(0,1)(Uj-Lj)

      (4)

      其中,xij是新蜜源的第j維分量,rand是(0,1)上均勻分布的隨機數(shù),Uj和Lj分別是第j維分量的上界和下界。

      記錄當(dāng)前所有蜜蜂找到的最優(yōu)蜜源,即局部最優(yōu)解,并重復(fù)上述基本步驟,直到達到最大迭代次數(shù)或小于誤差允許的值,最后輸出全局最優(yōu)解。

      為了克服ABC算法易陷入局部最優(yōu)的缺點,BeeGenP算法引入了GA中的交叉和變異算子。交叉算子每次選取2條染色體進行操作,通過組合兩者的特性以產(chǎn)生新的子代染色體。一種簡單的交叉方式是在雙親染色體上隨機選取一個斷點,并將斷點右部的編碼互換,形成新的后代。適當(dāng)?shù)慕徊媛士傻玫捷^好的解空間,并且降低算法停止在局部最優(yōu)解上的概率。變異算子是讓染色體隨機發(fā)生變化。一種簡單的變異方式是對染色體上的一個或多個基因進行替換,因此變異操作可產(chǎn)生初始種群不具備的基因,或者找到在選擇過程中丟失的基因。

      BeeGenP算法的基本出發(fā)點是在人工蜂群算法的基礎(chǔ)上,利用交叉和變異操作改進算法的局部搜索能力,以便有效地解決p-center問題。

      3 BeeGenP算法的設(shè)計與實現(xiàn)

      BeeGenP算法是結(jié)合ABC算法和GA算法所設(shè)計出的啟發(fā)式算法,用于求解離散型平面p-center問題。假設(shè)在平面上給定點集S和圓的個數(shù)p,希望輸出圓心位置與最大圓的半徑,其中S和p以參數(shù)形式任意給定。下面論述BeeGenP算法的設(shè)計細節(jié),包括解的編碼方式、交叉算子與變異算子、局部搜索方式等,并給出BeeGenP算法的偽代碼及實驗結(jié)果分析。

      3.1 解的編碼方式及其初始化

      不同的解編碼方式可能會導(dǎo)致不同的算子設(shè)計方式,本文選擇隨機鍵編碼方式。隨機鍵最早是在求解旅行商問題TSP(Traveling Salesman Problem)時被引入到GA算法中的。該方法通過一個隨機生成的浮點數(shù)向量來實現(xiàn),使得向量的分量與問題求解點集中的點一一對應(yīng)。GA算法通過改變該浮點數(shù)向量來改變對應(yīng)點的相應(yīng)位置。本文使用n個m位二進制數(shù)代替浮點數(shù),其中n是給定點集中點的個數(shù),2m-1

      Table 1 An example of given point set and corresponding random keys of points表1 給定點集以及相應(yīng)點的隨機鍵示例

      根據(jù)ABC算法的運算要求,算法在開始迭代前需要隨機生成p個解來定義初始雇傭蜂。在隨機鍵編碼方式下,可通過選取最大或者最小的p個二進制數(shù)所對應(yīng)的點作為初始圓心。如在表1的示例中,可選擇(4,5),(21,4),(7,3)為初始圓心。

      3.2 交叉算子

      交叉運算用于提升ABC算法中采蜜蜂的局部搜索能力。交叉運算不僅可以使當(dāng)前解盡可能保留前幾輪較優(yōu)解的良好組合,而且還能使算法具有更強的探索最優(yōu)值的能力。在算法執(zhí)行過程中,采蜜蜂以一定概率通過交叉算子來生成新的解。實驗表明,若交叉率過高,則容易導(dǎo)致解早熟;若交叉率較低,則會導(dǎo)致搜索效率降低。一般而言,交叉率設(shè)置在45%~55%左右。通過本文算法的交叉算子生成新解時,算法會根據(jù)式(2)的輪盤賭方式從歷史最優(yōu)解中選取某個解,并與采蜜蜂當(dāng)前所在的蜜源解做交叉運算,以得到新的解。傳統(tǒng)的交叉運算是任意選取3個隨機整數(shù),并以這3個數(shù)為斷點,將運算雙方的解分成4段,然后交換其中的幾段以生成新的解。本文算法的交叉運算則有所不同,即隨機選取運算對象雙方解的部分元素并組合成新的解。如圖1所示,F(xiàn)ather和Mother分別表示需要做交叉運算的2個對象,其中Fi(1≤i≤p)和Mi(1≤i≤p)均是m位的二進制數(shù);Son表示交叉運算后得到的子代新解。

      Figure 1 A diagram of cross operation圖1 交叉運算示意圖

      3.3 變異算子

      隨著算法的推進,得到的當(dāng)前最優(yōu)解會出現(xiàn)趨于單一化趨勢,容易造成算法過早地收斂于一個局部最優(yōu)解,因而影響了全局最優(yōu)解的產(chǎn)生。變異算子用于增加解搜索空間的多樣性。BeeGenP算法使用了2種變異算子,分別記為X和Y。其中,X將隨機選擇當(dāng)前解中的一個編碼元素并將其刪除,然后隨機選取一個未在當(dāng)前解中出現(xiàn)的點,并將對應(yīng)的編碼添加到當(dāng)前解中,產(chǎn)生一個新解;Y則在當(dāng)前解中隨機選取一個點p1及其相鄰的點p2,根據(jù)式(5)生成點p3。生成點p3后,其對應(yīng)的編碼會隨機替換點p1或點p2所對應(yīng)的編碼,產(chǎn)生一個新的解。

      p3=min(p1,p2)+

      (5)

      對需要做變異運算的解,可任選X或Y做運算,計算新解的適應(yīng)度值并加以判別。

      3.4 算法實現(xiàn)

      BeeGenP算法采用ABC算法的主框架完成基本的迭代過程,該過程包括初始化蜂群、觀察蜂選擇蜜源以及偵察蜂搜索新蜜源的規(guī)則、解的選擇方式、何時舍棄當(dāng)前蜜源與如何判斷算法是否結(jié)束等操作。但是,在采蜜蜂對解的局部搜索過程中,BeeGenP算法將按照一定概率,有的放矢地對當(dāng)前解做交叉或變異運算,以獲得新的局部解。BeeGenP算法的主要步驟如下所示:

      (1) 初始化各類參數(shù),包括蜜蜂的種群數(shù)量,算法迭代次數(shù)的上限,一個蜜源的最大探索次數(shù),以及交叉和變異運算的發(fā)生概率等。

      (2) 初始化蜂群隊列bee_queue、記錄歷史局部最優(yōu)解的隊列his_best、記錄當(dāng)前可探索蜜源的隊列flower_queue以及步數(shù)計數(shù)器iter。

      (3) 步數(shù)計數(shù)器增加1,判斷是否達到最大迭代次數(shù),若達到最大迭代數(shù),則進行步驟(6);否則進行步驟(4)。

      (4) 將當(dāng)前flower_queue中較優(yōu)的解,加入到his_best中。遍歷bee_queue中的成員,做交叉運算或變異運算以獲得局部的新解。若新解適應(yīng)度值優(yōu)于舊解,則用新解替換舊解;否則,舍棄新解,并將蜜源的搜索次數(shù)增加1。將bee_queue中適應(yīng)度值最好的解加入到his_best中,并舍棄已達到最大搜索次數(shù)的蜜源。被舍棄蜜源上的蜜蜂,若轉(zhuǎn)換為觀察蜂,則根據(jù)輪盤賭的方式,在當(dāng)前flower_queue中選擇一個蜜源;若轉(zhuǎn)換為偵察蜂,則根據(jù)規(guī)則生成新的解。

      (5) 根據(jù)bee_queue中蜜蜂所擁有的蜜源,更新flower_queue中的元素,轉(zhuǎn)到步驟(3)。

      (6) 輸出his_best的最優(yōu)解,算法結(jié)束。

      BeeGenP算法的偽代碼如下所示:

      算法BeeGenP

      Input:平面點集S和待求解的中心點數(shù)p。

      Output:點集S的p-center解。

      步驟1初始化各類參數(shù),包括最大迭代次數(shù)CycMax,蜜源的最大探索次數(shù)Limit,蜂群數(shù)量N,交叉算子執(zhí)行的概率cp;

      步驟2sizeS←S包含元素的個數(shù);

      步驟3初始化隊列bee_queue,his_best,flower_queue;

      步驟4 while(bee_queue的長度小于N){

      步驟5add(flower_queue,CreateAns(p,sizeS)); }//生成初始解

      步驟6對flower_queue中的初始解按適應(yīng)度值排序,保留適應(yīng)度值高的N/2個雇傭蜂,并將flower_queue中適應(yīng)度值最好的解加入his_best中;

      步驟7根據(jù)flower_queue中的適應(yīng)度值和輪盤賭概率,讓觀察蜂選擇蜜源,并加入bee_queue中;

      步驟8iter←0;

      步驟9 while(iter

      步驟10for(i←0toN-1){

      步驟11if(bee_queue[i]!= null ){

      步驟12if(random(0,1)

      步驟13根據(jù)輪盤賭的規(guī)則在his_best中選取運算對象fa;

      步驟14son←CrossOver(fa,bee_queue[i],p);}

      步驟15elseson←Variation(bee_queue[i]);//需要執(zhí)行變異操作

      步驟16if(son的適應(yīng)度優(yōu)于bee_queue[i]的適應(yīng)度值){

      步驟17bee_queue[i]=son;}

      步驟18elsebee_queue[i].tail+= 1;}}

      步驟19將bee_quene當(dāng)前解中適應(yīng)度值最好的解加入隊列his_best中;

      步驟20for(i←0toN-1);

      步驟21if(bee_queue[i].tail>Limit){

      步驟22bee_queue[i] = null;}}

      步驟23將flower_queue清空;

      步驟24將bee_queue中非null的元素添加到flower_queue中;

      步驟25for(i←0toN-1){

      步驟26if(bee_queue[i] = null ){

      步驟27轉(zhuǎn)換為偵察蜂選擇蜜源,并加入bee_queue[i];}}

      步驟28iter+= 1;}

      步驟29returnhis_best中適應(yīng)度值最優(yōu)的解

      3.5 實驗結(jié)果分析

      針對無約束p-center問題,盡管M-ABC算法的性能優(yōu)于其它啟發(fā)式算法,但仍然存在一些缺陷。本文通過隨機生成的測試數(shù)據(jù)(共生成了50組樣例),分別測試了BeeGenP算法和M-ABC算法,實驗結(jié)果如表2和表3所示。其中,n是給定點集中點的數(shù)量。

      Table 2 Comparison of the optimal solutions between BeeGenP and M-ABC表2 BeeGenP與M-ABC算法的最優(yōu)解

      Table 3 Comparison of the iterations between BeeGenP and M-ABC表3 BeeGenP與M-ABC的迭代次數(shù)

      表2是確定最大迭代次數(shù)為1 000時2個算法所得到的最優(yōu)解;表3則記錄了當(dāng)趨近收斂于最優(yōu)解時,2個算法的迭代次數(shù)。

      由表2可看出,對于隨機生成的由任意n個點構(gòu)成的點集,BeeGenP算法得到的p-center解中最大圓的半徑普遍小于M-ABC算法的對應(yīng)結(jié)果,這說明BeeGenP算法更有效,它比M-ABC算法具有更強的局部搜索能力。同時,通過表3也可看出,當(dāng)2個算法趨近收斂于最優(yōu)解時,BeeGenP算法所需要的迭代次數(shù)普遍小于M-ABC算法的迭代次數(shù)。

      4 結(jié)束語

      針對離散型平面p-center問題,在人工蜂群算法的基礎(chǔ)上,通過改進局部解的搜索策略,本文提出了新的BeeGenP啟發(fā)式算法。BeeGenP算法采用遺傳算法中的交叉與變異操作產(chǎn)生新的子代解,以此增強算法的搜索能力,并使搜索空間具有多樣性。實驗結(jié)果表明,對于隨機生成的點集和參數(shù)p,BeeGenP算法所求出的最大圓的半徑普遍小于M-ABC算法的對應(yīng)結(jié)果,且當(dāng)算法趨近收斂于最優(yōu)解時,BeeGenP算法的迭代次數(shù)要小于M-ABC算法的迭代次數(shù),改進算法要快于M-ABC算法獲得相應(yīng)的最優(yōu)解。BeeGenP算法不僅具有更強的局部搜索能力,而且也更加高效。

      與所有啟發(fā)式算法一樣,由于p-center問題中求解最大圓半徑時需要遍歷整個點集,故是一個十分耗時的運算。BeeGenP算法的迭代計算也很耗時,尤其是當(dāng)點集規(guī)模和參數(shù)p較大時,運算將更加耗時。一個可行的改進方法是首先采用聚類方法,將給定點集劃分為若干個子集,并將最大圓半徑的搜索問題局限在某子集范圍內(nèi),以此減少計算時間。如何融合聚類算法,并在保障解質(zhì)量的前提下降低算法的耗時,是值得進一步研究的課題。

      猜你喜歡
      蜜源蜂群適應(yīng)度
      貴州寬闊水國家級自然保護區(qū)蜜源植物資源調(diào)查研究*
      改進的自適應(yīng)復(fù)制、交叉和突變遺傳算法
      計算機仿真(2022年8期)2022-09-28 09:53:02
      林下拓蜜源 蜂業(yè)上臺階
      “蜂群”席卷天下
      指示蜜源的導(dǎo)蜜鳥
      基于空調(diào)導(dǎo)風(fēng)板成型工藝的Kriging模型適應(yīng)度研究
      中國塑料(2016年11期)2016-04-16 05:26:02
      改進gbest引導(dǎo)的人工蜂群算法
      蜂群夏季高產(chǎn)管理
      少數(shù)民族大學(xué)生文化適應(yīng)度調(diào)查
      我有我味道
      安塞县| 镇安县| 永康市| 临桂县| 杂多县| 方山县| 邢台市| 电白县| 苏州市| 深圳市| 桐梓县| 新乡县| 遂平县| 玛纳斯县| 普洱| 虞城县| 治多县| 华安县| 合山市| 巴里| 洪雅县| 台东县| 北碚区| 祁门县| 南京市| 耒阳市| 大田县| 叶城县| 商洛市| 来宾市| 山东省| 大兴区| 黔东| 岑溪市| 峨山| 沙坪坝区| 漳州市| 鄄城县| 铜山县| 鹿泉市| 民勤县|