離散群體智能算法的研究與應(yīng)用.pdf

1、最優(yōu)化問題是人們在科學(xué)研究、工程技術(shù)和經(jīng)濟(jì)管理等諸多領(lǐng)域中經(jīng)常碰到的問題，其目的是從眾多備選方案中選擇出使目標(biāo)函數(shù)達(dá)到最小或最大的方案。優(yōu)化方法涉及的應(yīng)用領(lǐng)域很廣，問題種類與性質(zhì)繁多，根據(jù)不同的原則可以給出不同的分類。根據(jù)決策變量的取值類型，可分為函數(shù)優(yōu)化問題與組合優(yōu)化問題（又稱離散優(yōu)化問題）。離散優(yōu)化問題是一類重要的優(yōu)化問題，隨著計(jì)算機(jī)科學(xué)、管理科學(xué)和現(xiàn)代化生產(chǎn)技術(shù)等的日益發(fā)展，這類問題與日俱增，且其大部分都是NP—hard問題。這些

2、問題正越來越受到運(yùn)籌學(xué)、應(yīng)用數(shù)學(xué)、計(jì)算機(jī)科學(xué)及管理科學(xué)等諸多學(xué)科的高度重視。很長時(shí)間以來，人們試圖尋找解決各種組合問題的有效算法。長期的努力在此問題上取得了一定的成效，但NP問題仍然是21世紀(jì)一個(gè)最具挑戰(zhàn)性的科學(xué)難題，是在理論信息學(xué)中計(jì)算復(fù)雜度理論領(lǐng)域里至今沒有解決的問題。 群體智能優(yōu)化方法是一個(gè)新興的研究領(lǐng)域，為復(fù)雜優(yōu)化問題的求解提供了一個(gè)有效手段，已引起相關(guān)領(lǐng)域?qū)W者的廣泛關(guān)注。其中有代表性的有意大利學(xué)者M(jìn)arco Dorig

3、o于1991年提出的蟻群優(yōu)化方法和1995年James Kennedy和Russell Eberhart基于對鳥群、魚群捕食行為的模擬，提出的粒子群優(yōu)化方法。由于這些方法概念簡明、所需設(shè)置的參數(shù)較少、實(shí)現(xiàn)方便，特別用以解決復(fù)雜的組合優(yōu)化問題具有優(yōu)越性，迅速得到國際優(yōu)化計(jì)算領(lǐng)域的認(rèn)可，并在工程設(shè)計(jì)、生產(chǎn)優(yōu)化等應(yīng)用領(lǐng)域取得成功的應(yīng)用。論文首先系統(tǒng)深入地分析了離散粒子群算法的本質(zhì)，構(gòu)建了一種簡便高效的二元離散粒子群算法。然后，提出了一種全新的

4、求解線性順序問題的離散粒子群算法。其次，對置換流水車間調(diào)度問題初始解集的各種構(gòu)建方法進(jìn)行了比較分析。最后，提出了一種能夠減少早熟現(xiàn)象的并行蟻群算法。 論文的主要研究工作與創(chuàng)新點(diǎn)歸納如下： 1、對“離散型粒子群算法的本質(zhì)”進(jìn)行了探索。通過對經(jīng)典的離散型粒子群算法中各部件進(jìn)行拆分和分析；并在分析的基礎(chǔ)上，對這些部件以一種全新的方式重新組合起來，構(gòu)建了一種簡便高效的離散粒子群算法。新算法中每個(gè)粒子的新位置僅同其當(dāng)前位置、其前一

5、個(gè)位置、其歷史最優(yōu)位置和其鄰域內(nèi)的歷史最優(yōu)位置有關(guān)。對于各元素僅用0和1表示的二值問題，在這些位置，這些元素要么是0，要么是1。粒子中各元素在新位置取0或者1的概率，僅同以上位置該元素取0或者1的比例相關(guān)；即各元素在新位置的取值正比例于其當(dāng)前位置、其歷史最優(yōu)位置和其鄰域內(nèi)的歷史最優(yōu)位置的取值，而負(fù)比例于其前一個(gè)位置的取值。該算法無需涉及在離散型粒子群算法中難以解釋的“速度”的概念，沒有使用sigmoid函數(shù)，無需對任何變量值施加變化范圍

6、限制，僅使用基于值比例的概率，公式簡潔易于理解。該探索提供了一種窺視二元離散粒子群算法的新角度，為未來進(jìn)一步探索離散粒子群算法的本質(zhì)提供了一個(gè)基點(diǎn)。在De Jong Test Suite測試集上，運(yùn)行該離散粒子群算法，并與經(jīng)典的離散粒子群算法進(jìn)行比較。測試表明，提出的算法簡便高效。 另外，還在算法中引入了一個(gè)領(lǐng)袖粒子（Queen Informant）。該粒子使用單獨(dú)的類似蟻群信息素的更新規(guī)則，并向所有其它粒子提供信息；而僅有當(dāng)前

7、全局歷史最優(yōu)解向其提供信息。該粒子類似量子，有兩部分組成，其各元素兩個(gè)值分別表示該元素取0和1的比例概率。在算法中加入領(lǐng)袖粒子，將其運(yùn)行結(jié)果同先前的運(yùn)行結(jié)果和經(jīng)典算法的運(yùn)行結(jié)果進(jìn)行比較。實(shí)證表明，領(lǐng)袖粒子的引入有效地加快了算法的收斂速度，且沒有增加函數(shù)的評估計(jì)算量。 2、求解線性順序問題（Linear Order Problem，LOP）的離散粒子群算法。線性順序問題是一種NP—hard的組合優(yōu)化問題，其每個(gè)解可用一個(gè)“n個(gè)數(shù)的

8、排列”來表示。他讓某矩陣的行和列同時(shí)使用這個(gè)排列順序，使得該矩陣主對角線以上元素值的總和最大化。論文提出了一種簡便的離散粒子群算法，無需交換、交叉、變異、插入、刪除等算子，僅需在每個(gè)粒子中存儲(chǔ)各元素在其排列中的位置，而不是排列本身。將這些位置看成可以左右移動(dòng)的；每個(gè)粒子的速度是由其元素左右移動(dòng)形成的，從而對粒子的速度有一個(gè)清晰直觀的解釋。并用連續(xù)型的粒子群算法更新每個(gè)元素在其排列中的位置，然后用排序的方式確定各元素在排列中的相對位置即可

9、。將該算法同基于交換算子的粒子群算法在標(biāo)準(zhǔn)LOLIB測試集上進(jìn)行比較，表明該算法具有強(qiáng)大的優(yōu)勢。該方法適用于解元素在解排列中的絕對位置比相對位置更為重要的各種組合優(yōu)化問題。 3、對置換流水車間調(diào)度問題（Permutation Flowshop Scheduling Problem，PFSP）初始解集構(gòu)建方法的比較分析。群體智能算法解決優(yōu)化問題的第一個(gè)步驟是創(chuàng)建一個(gè)初始解集。需要一定數(shù)量的初始解集的群體智能算法包括遺傳算法（Gen

10、etic Algorithm，GA）、發(fā)散搜索算法（Scatter Search，SS）、粒子群優(yōu)化算法（Particle Swarm Optimization，PSO），Memetic算法（Memetic Algorithm，MA），差分進(jìn)化算法（Differential Evolution Algorithm，DE）等等。這些方法都已被用于求解該問題。如何創(chuàng)建一個(gè)高質(zhì)量高多樣性的初始解集以便減少求解的整體運(yùn)行時(shí)間，始終是一個(gè)待解決的

11、問題。對置換流水車間調(diào)度問題，先前的初始解比較研究僅限于創(chuàng)建出單個(gè)解的方法之間的解質(zhì)量比較分析。論文將各種初始解集構(gòu)建方法應(yīng)用到Taillard提出的PFSP測試集上（共120個(gè)算例），比較它們產(chǎn)生的初始解集的質(zhì)量，并用各種距離測度比較解集的多樣性，從而為求解PFSP問題的群體智能算法的進(jìn)一步改進(jìn)提供了基點(diǎn)。一個(gè)有效的算法在很大程度上依賴于好的合適的初始解集，您可以根據(jù)這些初始解集構(gòu)建方法的特性和您的算法自身的特點(diǎn)，選擇合適的初始解集構(gòu)

12、建方法。 4、基于信息素交叉算子和排斥算子的并行蟻群算法。在并行蟻群算法中，多個(gè)蟻群同時(shí)并行存在。本算法充分利用了這個(gè)特點(diǎn)，提出了一種減少算法過早局部收斂的辦法。它引入了兩個(gè)新算子：信息素交叉算子和排斥算子。算法采用主/從模式、星形拓?fù)溥B接；主機(jī)位于中心位置。最初，多個(gè)蟻群同時(shí)被隨機(jī)初始化，然后始終同時(shí)并行運(yùn)行。每個(gè)子種群都是一個(gè)可以獨(dú)立運(yùn)行的蟻群優(yōu)化系統(tǒng)，它們擁有屬于自己的信息素矩陣和α、β、ρ等參數(shù)。當(dāng)主機(jī)檢測到某個(gè)蟻群已陷