【正文】 矩陣存儲原因在于其訪問的快捷和方便。最近鄰居表。引入這一結(jié)構(gòu)的目的在于加速螞蟻構(gòu)造解的速度。該表存儲了每個城市距離最近的前1111個鄰居節(jié)點。在城市i的螞蟻優(yōu)先選擇i的鄰居作為候選節(jié)點。這使得螞蟻選擇下一個城市的時間復(fù)雜度降為o(1)，除非i的所有鄰居均已被該螞蟻訪問過。信息素結(jié)構(gòu)因為是多蟻群共享，所以每條邊對應(yīng)的信息量存放在一個n階對稱矩陣pheromone[n][n]中，即τi= τj。在解的構(gòu)造過程中，城市j的螞蟻以某一概率選擇城市j，此概率由[τij]^ α和[τij]^ β定，因為這一表達式的值與α和β有關(guān)，當然若所有蟻群運行完全相同的算法，則其值也會相同，但考慮到不同蟻群使用不同算法或者相同算法有不同的參數(shù)設(shè)置時此值會有差異，所以將其存儲在c個對稱n階矩陣total[cl[n][n]中，C為蟻群個數(shù)。螞蟻結(jié)構(gòu)ACO中螞蟻是最基本的計算實體，它負責解的構(gòu)造、釋放信息素和目標函數(shù)值的計算，因此螞蟻結(jié)構(gòu)中首先要有存放構(gòu)成解的所有節(jié)點的數(shù)組，即tour[n+1]。之所以是n+l，是因為螞蟻最終要回到出發(fā)點，數(shù)組的最后一個元素就是初始節(jié)點，這樣有利于簡化路徑長度的計算。螞蟻結(jié)構(gòu)的另外一個成員就是所得路徑的長度tour_length。除此之外，螞蟻在構(gòu)造解的過程中，選擇下一個城市之前首先要判斷這個城市有沒有走過，因此有數(shù)組visited[n]，用以標識該螞蟻對所有城市訪問情況，如已走過置l，否則為0。這里對多蟻群而言，每個蟻群m只螞蟻，有c個蟻群，所以定義二維數(shù)組ant[cl[m]，因為是共享存儲，所以每個處理器(負責一個蟻群)都可訪問該數(shù)組，蟻群g的第i只螞蟻即ant[g][i]。4．5．2 空間復(fù)雜度對于上面的數(shù)據(jù)結(jié)構(gòu)，并行ACO求解對稱TSP問題時，需要2+c個n階矩陣和一個n*rm個元素的鄰居表，此外每只螞蟻有兩個大小為n+l和rl的數(shù)組來分別存儲路徑節(jié)點和己走過城市，以及一個整型數(shù)存放路徑長度。通常螞蟻的數(shù)量m的值都比較小，因此總的內(nèi)存需求為O(nz)。除了這些主要的數(shù)據(jù)結(jié)構(gòu)，還有一些存放中間結(jié)果的變量及關(guān)于算法性能的統(tǒng)計信息，不過這些結(jié)構(gòu)占用的內(nèi)存相對于蟻群和問題的描述數(shù)據(jù)來說是微乎其微的。更精確的講，假如長整型數(shù)據(jù)占4個字節(jié)，雙精度數(shù)據(jù)占8個字節(jié)，我們在兩個處理器上采用2個線程(即c=2)計算，并令m=n則占用內(nèi)存情況為，距離矩陣4n^2，鄰居列表4n^2，信息素矩陣8n^2，信息素與啟發(fā)信息16n^2，蟻群描述16n^2，這樣粗略估計，并行的兩個蟻群共需內(nèi)存48n^2。比如對于5000個城市的TSP問題，就會占用內(nèi)存1．6G。可見，隨著問題規(guī)模的增大，算法對內(nèi)存的消耗會急劇上升，不過這是ACO算法與生俱來的，而不是并行化造成的，并行化也無法解決這一問題。 時間復(fù)雜度從上面的實現(xiàn)過程可以看出，并行求解的多個蟻群在解的構(gòu)造過程中，每個的計算時間仍為O(n3)，可以說在時間復(fù)雜度方面，并行對串行并沒有本質(zhì)的改變，這是蟻群算法的天性。不過，ACO作為一種啟發(fā)式的不確定算法，對其性能或效率的評價不能僅僅考慮時間因素，更重要的一個因素是解的質(zhì)量，確切的說是通過在給定時間內(nèi)算法所得解以及得到此解所需的迭代次數(shù)來綜合判斷算法的好壞。 并行線程的協(xié)調(diào)因為多個蟻群共享同一個信息素矩陣，因此多個線程對其訪問時必須采取安全的互斥機制，本文中使用傳統(tǒng)的加鎖方法來滿足這種需求，具體到PThread，我們設(shè)置一個鎖變量，通過調(diào)用pthread_mutext_lock和pthread．mutex_unlock函數(shù)對來實現(xiàn)多蟻群對信息素矩陣的互斥訪問。此外，對主線程和從線程的協(xié)作來說，因為信息素的初始化由主線程來完成，我們的實驗均是上述過程執(zhí)行若干次后取平均值，所以主線程也要負責多次信息素的初始化任務(wù)，此外在采用信息素重新初始化機制后，當滿足條件時仍然要喚醒主線程做初始化工作，且最后主線程要后于從線程退出。這些對主從線程的安全同步協(xié)作的要求非常高。本文中為解決上述問題采用了PThread庫的條件變量pthread_cond_t，在從線程執(zhí)行計算的過程中，主線程一直等待在一個條件變量上，直到有線程提出重新初始化時，阻塞從線程而喚醒主線程，待其完成初始化后，廣播信號喚醒所有等待在這個條件變量上的線程，同時阻塞自己。為此程序中設(shè)置了如下變量：int sum_try_counter //實驗總次數(shù)控制int has_init_pheromone //用于判斷信息素是否完成初始化int restart_flag // 控制信息素何時初始化pthread cond t．cond sync //主從線程同步的條件變量從線程的等待實現(xiàn)，當主線程初始化信息素矩陣完成后通過廣播信號量喚醒所有等待的線程，見圖4．10中的master部分。當所有線程都完成一次實驗后，通過調(diào)用sem post函數(shù)來喚醒主線程。proc waitpheromoneInit while(not has_init pheromone) // 信息素尚未完成初始化pthread mutex lock(＆mutex)pthread cond_wait(amp。cond，amp。mutex) //等待pthread mutex lock(＆mutex)end whileend proc 實現(xiàn)過程及算法描述主節(jié)點將ANT—NUM只螞蟻平均分配到各個從節(jié)點，并將距離矩陣廣播到各個從節(jié)點。在每次迭代中，主節(jié)點廣播當前的全局信息素矩陣，各個從節(jié)點利用信息素矩陣，在本地構(gòu)造局部最優(yōu)解，再由主節(jié)點收集各個從節(jié)點的局部最優(yōu)解，以此為依據(jù)，修改全局信息素矩陣。如此迭代多次．直到得到滿意的結(jié)果。 蟻群算法的并行策略并行算法描述：（1）主節(jié)點根據(jù)參與計算的節(jié)點數(shù)，將總共ANT—NUM只螞蟻平均分配到各個從節(jié)點；（2）主節(jié)點計算出城市之間的距離矩陣、能見度矩陣和初始的信息素矩陣，并將距離矩陣、能見度矩陣廣播給各從節(jié)點；（3）從節(jié)點接受廣播的距離矩陣、能見度矩陣，存儲在本地；（4）主節(jié)點廣播信息素矩陣；（5）從節(jié)點接收到廣播的信息素矩陣，存儲在本地；（6）各從節(jié)點根據(jù)本地的距離矩陣和信息素矩陣，由本地的N只螞蟻進行一次循環(huán)，構(gòu)造出局部最優(yōu)解；（7）主節(jié)點收集各從節(jié)點計算得到的局部最優(yōu)解，比較并得出本次循環(huán)的全局最優(yōu)解，根據(jù)信息素更新規(guī)則，更新信息素矩陣；（8）如果滿足結(jié)束條件，則退出；否則轉(zhuǎn)（4）進行下一次迭代。算法流程圖： 蟻群并行算法的流程圖算法執(zhí)行圖如下： 蟻群并行算法的執(zhí)行圖聚類蟻群算法的順序?qū)崿F(xiàn)偽代碼NC = 0。Initializeτij matrixInitialize quadtreeWhile (NCNCMax) and (Not Stagnation Behaviour) Initialize Δτij matrix。For each ant k do Build a job sequence Evaluate solution k on each objective Update Δτij matrix according to solution k。 Insert solution k into the quadtree。Update τij matrix according toΔτij matrixNC = NC + 1。聚類蟻群算法的并行實現(xiàn)偽代碼NC = 0。NumThreads = p。Initialize τij matrix。Initialize the p quadtrees。While (NC NCMax) and (Not Stagnation Behaviour)Initialize the p Δτij matrices。Parallel for with p threadsFor each ant k doBuild a job sequence。Evaluate solution k on each objective。Update Δτij[p] matrix according to the solution k。Insert solution k into the quadtree[p]。Merge the p Δτij matrices in parallel。Update τij matrix according to Δτij matrix。NC = NC + 1。Merge the p quadtrees。5 PACOA性能的仿真研究 實驗介紹本章基于上面的實現(xiàn)，給出了程序的運行結(jié)果，并對幾種并行實現(xiàn)方法做出比較，同時給出與相應(yīng)串行算法的運行結(jié)果的比較。對蟻群算法來說，很難按常規(guī)的并行算法與串行算法的比較方式(加速比)來衡量PACOA與串行ACO孰優(yōu)孰劣，因為蟻群算法作為一種啟發(fā)式算法，它本身必然無法在求出一個解后斷言它就是問題的最優(yōu)解，所以我們不能僅僅從算法得出某些解花費的時間這一個方面判斷，還要同時考慮到解的好壞，所以我們這里在比較并行AC0與串行AC0時，取它們各自運行k次平均解的質(zhì)量。仿真實驗在非專用機群系統(tǒng)上進行，節(jié)點為普通PC機，3．2 GHz處理器, 2．0G內(nèi)存，節(jié)點之間通過10Mbps以太網(wǎng)互聯(lián)，每個節(jié)點均安裝Red hat Linux ，程序設(shè)計工具PThread+gcc+gdb。由于MPICH軟件的自身原因，需要對環(huán)境做一些特殊的配置：在每臺PC機上必須建立相同的用戶名并且口令必須相同；用戶的級別應(yīng)為系統(tǒng)管理員；運行MPI程序時應(yīng)關(guān)閉PC機的防火墻或把要運行的程序添加到防火墻的信任名單中。其它配置按照MPICH手冊進行。聚類技術(shù)要求對所要聚類的對象的屬性是任意的。為了明確清楚，本文采用常規(guī)方法選擇二維數(shù)據(jù)集。把數(shù)據(jù)對象隨機的分布在50*50的二維網(wǎng)格上，用1000只螞蟻在網(wǎng)格上獨立的移動并完成聚類，也就是螞蟻在運動過程中沒有直接相互作用。任意時刻螞蟻都處在某個網(wǎng)格單元中，螞蟻的速度范圍為[2～10]。整個過程采用3*3的網(wǎng)格區(qū)域作為局部面積，該區(qū)域上數(shù)據(jù)對象的多少決定該區(qū)域的密度，并隱含了對象的相似度。如果該區(qū)域上的對象很少，也就是密度低的情況下，螞蟻就可能拾起該區(qū)域內(nèi)的對象，并在密度高且和該對象相似的區(qū)域內(nèi)放下這個對象。所有的螞蟻在網(wǎng)格上移動并執(zhí)行相同的動作（拾起、放下或交換對象）。在分配了網(wǎng)格環(huán)境的同時，然后是進行并行化處理的任務(wù)，分別使用1個處理器，接著使用2個處理器，還要用4，8，16個處理器進行并行的環(huán)境測試，從而達到并行的效果。 仿真實驗結(jié)果與數(shù)據(jù)分析 如下圖四個表的結(jié)果顯示了用1，2，4，8，16個處理器來處理50和80個任務(wù)的并行數(shù)據(jù)集，蟻群的數(shù)量設(shè)置成1000。 使用的參數(shù)表ParameterValueβ2γρm2……8Q100Iterations1000 并行處理50個任務(wù)，100個周期，蟻群數(shù)為1000個 并行處理50個任務(wù)，200個周期，蟻群數(shù)為1000個 并行處理80個任務(wù)，100個周期，蟻群數(shù)為1000個 并行處理80個任務(wù)，200個周期，蟻群數(shù)為1000個 考慮到蟻群規(guī)模的大小，圖一和圖三表明了在相同的參數(shù)下，同時處理80個任務(wù)能夠獲得同時處理50個任務(wù)更好的效率，應(yīng)該相信在并行化的機制下，我們處理更多的任務(wù)將會獲得更好的效率。當然，還要看在現(xiàn)實的工業(yè)調(diào)度的情況，將會對規(guī)模進行一定的限制，所以一開始第一步就應(yīng)該對可行性和性能進行研究，故在未來的工作當中，將把問題的規(guī)模擴展到多于80個任務(wù)。下面兩個圖是處理不同個任務(wù)的執(zhí)行時間對比，依然是100個執(zhí)行周期和1000個蟻群數(shù)量。 并行處理80個任務(wù)，100個周期，1000個蟻群數(shù)量執(zhí)行時間 用四個處理器，100個周期，1000個蟻群的效率 串并行蟻群算法的對比圖可以明顯的看出并行化對蟻群算法的優(yōu)勢所在。為了對不在信息素上的數(shù)據(jù)也能被聚類，可以通過一下兩種方法：（1）確保信息素不斷變化，使每個網(wǎng)格至少有一次能含有信息素；（2）不要讓螞蟻時刻沿著信息素軌跡移動，應(yīng)讓螞蟻頻繁的離開信息素痕跡。對方法（1）中控制信息素不斷變化是不可能的，因為那需要不斷的中斷重建信息素，不但麻煩，而且需要不斷的修改參數(shù)，該方法行不通，因此本文采用方法（2）。試用下面三種措施來考慮：螞蟻的狀態(tài)與它的運動類型相結(jié)合；螞蟻的狀態(tài)與它向外發(fā)射信息素相結(jié)合；螞蟻狀態(tài)、向外發(fā)射信息素及運動類型相結(jié)合。 小結(jié)與參數(shù)分析在上面的仿真實驗中，需要設(shè)定的參數(shù)主要有螞蟻數(shù)量m，全局揮發(fā)因子α，局部揮發(fā)因子ρ，啟發(fā)函數(shù)權(quán)重β，下面對這幾個參數(shù)進行仿真研究。（1）螞蟻數(shù)量mPACOA算法中螞蟻的數(shù)量越多，全局搜索能力就越強，但是算法的計算量與m成正比，螞蟻數(shù)量越多計算量也就越大，為了尋找最佳的螞蟻數(shù)量，分別選取了m=n/10，n/5， n/2，n，2n，5n，10n等參數(shù)進行仿真分析。螞蟻數(shù)量對進化過程的影響是隨著m的增大，優(yōu)化結(jié)果越好；mn時，解的進化狀況普遍比較好，基本收斂于m=n時得到的最優(yōu)解附近，而且m的增大對最優(yōu)解的影響不明顯；當mn時，優(yōu)化結(jié)果迅速惡化，mn，進化過程迅速收斂到不良解；因此，綜合評價，一般選取m=n。（2）參數(shù)α，ρ參數(shù)α，ρ分別代表全局更新規(guī)則和局部更新規(guī)則中信息揮發(fā)程度，為了尋找α和ρ的最佳范圍，分別對α=ρ=，，，，，信息揮發(fā)程度對進化過程影響的結(jié)果是，當參數(shù)α=，，進行較慢；當α=，優(yōu)化結(jié)果較差。在PACOA算法中，優(yōu)化過程是信息素揮發(fā)和信息積累兩種過程共同作用的結(jié)果，增大α，ρ的值，信息素揮發(fā)的越快，可以提高算法的全局搜索能力，但是又會使算法的收斂速度降低；減小α，ρ的值，信息素的揮發(fā)較慢，以前搜索過的