應(yīng)用蟻群算法解決多處理機(jī)調(diào)度問題的研究.pdf

1、并行分布式處理是當(dāng)前計(jì)算機(jī)發(fā)展的主要挑戰(zhàn)問題之一，也是當(dāng)前計(jì)算機(jī)科學(xué)的一個(gè)熱點(diǎn)。在并行分布計(jì)算中，調(diào)度問題是分布計(jì)算的瓶頸問題之一。這個(gè)問題對(duì)發(fā)揮系統(tǒng)的并行計(jì)算能力、提高系統(tǒng)吞吐量具有非常重要的影響。良好的調(diào)度算法可以充分運(yùn)用系統(tǒng)中每個(gè)處理機(jī)的計(jì)算能力，提高并行分布計(jì)算的效率。調(diào)度問題得不到解決，則會(huì)導(dǎo)致分布計(jì)算效率低下。 上世紀(jì)50年代中期創(chuàng)立了仿生學(xué)，蟻群算法正是從仿生學(xué)的機(jī)理中受到啟發(fā)而提出的一種新型進(jìn)化算法和啟發(fā)式隨機(jī)搜

2、索算法。蟻群算法具有分布式、魯棒性好以及易于與其他方法結(jié)合的優(yōu)點(diǎn)。蟻群算法主要用于求解不同的組合優(yōu)化問題。目前蟻群算法的研究已經(jīng)滲透到了多個(gè)應(yīng)用領(lǐng)域，可以解決多維動(dòng)態(tài)組合優(yōu)化問題、離散優(yōu)化問題等。 處理機(jī)調(diào)度問題屬于組合最優(yōu)化問題，更是離散優(yōu)化問題。而蟻群算法在求解離散優(yōu)化問題上的卓越性能為使用蟻群算法求解處理機(jī)調(diào)度問題提供了可行性。 本文主要研究蟻群算法在處理機(jī)調(diào)度問題中的應(yīng)用。文章首先詳細(xì)介紹調(diào)度問題和蟻群算法的定義

3、、模型及其研究現(xiàn)狀等，分析討論了當(dāng)前國內(nèi)外一些求解調(diào)度問題的各類算法，為利用蟻群算法求解處理機(jī)調(diào)度問題提供了一定的理論基礎(chǔ)。 文章的主體部分包括三個(gè)方面：基于蟻群算法求解處理機(jī)調(diào)度問題、基于混合蟻群算法求解處理機(jī)調(diào)度問題以及基于蟻群算法求解實(shí)時(shí)系統(tǒng)中有時(shí)限約束的調(diào)度問題。文章的主要貢獻(xiàn)及創(chuàng)新之處如下所示： 1．文章提出了一種求解多處理機(jī)調(diào)度問題的蟻群優(yōu)化算法。該算法在DAG圖的基礎(chǔ)上，用AOE(Active on Edg

4、e)圖來表示任務(wù)之間拓?fù)漤樞?，圖中的每一邊條代表一個(gè)任務(wù)，邊上的權(quán)重表示該任務(wù)的完成時(shí)間。AOE圖比一般的DAG圖更能表現(xiàn)出任務(wù)之間的優(yōu)先約束關(guān)系，也能更好地貼近蟻群算法的設(shè)計(jì)思路。其次，將關(guān)鍵路徑、任務(wù)的最早開始時(shí)間和任務(wù)的最遲開始時(shí)間等多種因素有機(jī)結(jié)合在一起，設(shè)計(jì)出了概率公式，避免了任務(wù)選擇策略的單一，在一定程度上避免陷入局部最優(yōu)解。最后用任務(wù)之間的“配合程度"來定義信息素. 2．文章提出了一種適合蟻群算法的任務(wù)分配模型(T

5、ask-A1location Model，TAM)，該模型結(jié)合具體類型的處理機(jī)調(diào)度問題的特點(diǎn)，具有很好的可擴(kuò)充性和靈活性。在TAM的基礎(chǔ)上，設(shè)計(jì)了基于TAM的求解處理機(jī)調(diào)度的蟻群算法。為了克服蟻群算法的收斂速度慢、易陷入局部最優(yōu)等局限性，我們?cè)谙伻核惴ㄖ屑尤脒z傳算子，設(shè)計(jì)了一種混合蟻群算法。充分發(fā)揮了兩者的優(yōu)點(diǎn)，既保證了較高的搜索效率，又保證了解的全局最優(yōu)性；最后，在TAM的基礎(chǔ)上，對(duì)動(dòng)態(tài)處理機(jī)調(diào)度算法的設(shè)計(jì)與實(shí)現(xiàn)進(jìn)行了探討，為進(jìn)一步的

6、研究工作奠定了基礎(chǔ)。 3．文章提出一種求解有時(shí)限約束的調(diào)度問題的蟻群算法(The ACO forDeadline Scheduling Problem，簡(jiǎn)稱ADSD)。此算法首先對(duì)任務(wù)集所對(duì)應(yīng)的DAG圖進(jìn)行了擴(kuò)展，得到了擴(kuò)展的DAG圖。根據(jù)這種設(shè)計(jì)，人工螞蟻在圖中遍歷可以得到任務(wù)的拓?fù)湫?；此算法包括兩種優(yōu)化，一方面是任務(wù)列表的優(yōu)化；另一方面是處理機(jī)分配策略的優(yōu)化。由這兩種優(yōu)化衍生出兩種概率公式的設(shè)計(jì)和兩種信息素。算法利用啟發(fā)式信