競(jìng)選算法及其應(yīng)用分析

《競(jìng)選算法及其應(yīng)用分析》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫(kù)。

1、廣東r[業(yè)大學(xué)碩十論文現(xiàn)代啟發(fā)式算法為禁忌算法。在每次迭代中，也是由某當(dāng)代點(diǎn)的鄰域來(lái)得到下一代最優(yōu)可能點(diǎn)。不同的是，該算法保存一個(gè)禁忌表，在禁忌表中出現(xiàn)的點(diǎn)不允許出現(xiàn)在下一代點(diǎn)中，這樣就可以避免算法陷入局部最優(yōu)。還有一種很重要的算法為基于群體(population)的算法。該類算法為概率算法，候選解作為群體中的個(gè)體被保存下來(lái)。典型的，遺傳算法、粒子群算法和蟻群算法都屬于這類算法。遺傳算法口1是以決策變量的編碼作為運(yùn)算對(duì)象，直接以目標(biāo)函數(shù)作為搜索信息，可同時(shí)在多點(diǎn)進(jìn)行信息搜索，具有天生的并行性，使用概率搜索技術(shù)，增加了其搜索過(guò)程的靈活性。粒子群算法?初始化為一群

2、隨機(jī)粒子(隨機(jī)解)，然后通過(guò)迭代找到最優(yōu)解，在每一次迭代中，粒子通過(guò)跟蹤兩個(gè)“極值"來(lái)更新自己，另一個(gè)極值是整個(gè)種群目前找到的最優(yōu)解，粒子群算法具有收斂快的特點(diǎn)。蟻群算法?中螞蟻運(yùn)動(dòng)時(shí)會(huì)在路徑上釋放出信息素尋找路徑，螞蟻之間交換著路徑信息，通過(guò)信息素的作用使整個(gè)蟻群的行為具有非常高的自組織性，最終通過(guò)蟻群的集體自催化行為找出最優(yōu)路徑，蟻群算法具有很強(qiáng)的發(fā)現(xiàn)較好解的能力，最早成功應(yīng)用于解決N-P難題中著名的旅行商問(wèn)題。本文所要研究的競(jìng)選算法也為基于群體的算法。1．2競(jìng)選算法競(jìng)選算法¨1是一種原創(chuàng)性的算法，是新型的啟發(fā)式算法，人們通過(guò)模擬自然界和人類社會(huì)的各種行為

3、、特征和機(jī)制，提出了一些具有優(yōu)秀搜索能力的現(xiàn)代優(yōu)化算法一一啟發(fā)式優(yōu)化算法，正如模仿物種進(jìn)化的遺傳算法、模擬金屬冷卻過(guò)程的退火算法、模擬螞蟻覓食過(guò)程的蟻群算法、模擬鳥(niǎo)類或魚(yú)群生活行為的粒子群算法、模擬人類和動(dòng)物記憶功能的禁忌搜索算法等一樣，競(jìng)選算法也是模擬人類的競(jìng)選活動(dòng)而設(shè)計(jì)出來(lái)的，其搜索機(jī)制模擬競(jìng)選活動(dòng)中對(duì)更高支持率的追求動(dòng)機(jī)。競(jìng)選算法將搜索空間比擬成選民，競(jìng)選人是當(dāng)前解。競(jìng)選人的支持率通過(guò)對(duì)選民的抽樣調(diào)查來(lái)估算，選民的支持根據(jù)競(jìng)選人對(duì)選民的影響按比例分配給各個(gè)競(jìng)選人，根據(jù)支持的分布計(jì)算出支持率重心，即下一個(gè)競(jìng)選地點(diǎn)，如此反復(fù)進(jìn)行的搜索，最終達(dá)到具有最高支持的

4、競(jìng)選地點(diǎn)，即全局最優(yōu)解。2第一章緒論競(jìng)選算法和遺傳算法有很多共同之處。兩者都隨機(jī)初始化種群，都使用評(píng)估值來(lái)評(píng)價(jià)系統(tǒng)，而且都根據(jù)評(píng)估值來(lái)進(jìn)行一定的隨機(jī)搜索。競(jìng)選算法與遺傳算法的信息共享機(jī)制是很不同的。在遺傳算法中，染色體互相共享信息，所以整個(gè)種群的移動(dòng)是比較均勻的向最優(yōu)區(qū)域移動(dòng)。在競(jìng)選算法中，距離當(dāng)前解距離近的信息以大權(quán)重傳給下一循環(huán)，屬于集中式的信息流動(dòng)，整個(gè)搜索更新過(guò)程可能以更快的速度收斂。通過(guò)使用遺傳算法的標(biāo)準(zhǔn)性能測(cè)試函數(shù)，對(duì)競(jìng)選算法進(jìn)行了驗(yàn)算，證明算法高效可行。體現(xiàn)了競(jìng)選算法收斂快；齊次(只使用當(dāng)前循環(huán)的信息)；參數(shù)多，靈活的優(yōu)點(diǎn)。是一個(gè)有發(fā)展前景的優(yōu)化

5、算法。目前，競(jìng)選算法已應(yīng)用在圖像處理¨1和機(jī)械設(shè)計(jì)n¨引等優(yōu)化問(wèn)題上，顯示了良好的優(yōu)化效果。1．3相關(guān)應(yīng)用問(wèn)題的研究概況1．3．1車(chē)間調(diào)度問(wèn)題車(chē)間調(diào)度問(wèn)題是一個(gè)古老而又傳統(tǒng)的問(wèn)題，對(duì)它的研究始于20世紀(jì)50年代，早在1954年Johnson對(duì)兩臺(tái)機(jī)床FlowShop型調(diào)度問(wèn)題進(jìn)行了研究后，提出了解決n／2／F／Cmax和部分特殊n／3／F／Cmax問(wèn)題的優(yōu)化算法，這代表調(diào)度理論研究的開(kāi)始，以后它便開(kāi)始了對(duì)調(diào)度問(wèn)題進(jìn)行了廣泛研究‘91。60—70年代建立了調(diào)度理論的主體(經(jīng)典調(diào)度理論)，并重視調(diào)度復(fù)雜性的研究。由于調(diào)度問(wèn)題是制造系統(tǒng)中最基本，最重要而又最復(fù)雜的問(wèn)

6、題之一，國(guó)內(nèi)外無(wú)數(shù)的學(xué)者對(duì)其進(jìn)行了廣泛的探討和研究，也提出了各種各樣的算法，建立了不同的理論框架模型。車(chē)間調(diào)度問(wèn)題的復(fù)雜性，各種不同的具體問(wèn)題往往有很多不同的解決方法，因此需要從策略上去考慮車(chē)間調(diào)度問(wèn)題，形成各種研究方法策略以指導(dǎo)對(duì)車(chē)間調(diào)度的研究。七十年代，人們開(kāi)始了算法復(fù)雜性的研究，多數(shù)調(diào)度問(wèn)題被證明屬于N．P完全問(wèn)題或N．P難問(wèn)題，難以找到多項(xiàng)式算法，因此開(kāi)始關(guān)注啟發(fā)式算法。Panwalka總結(jié)和歸納出了113條調(diào)度規(guī)則，并對(duì)其進(jìn)行了分類。七十年代末期，經(jīng)典調(diào)度理論趨向成熟。隨著70年代后期各類調(diào)度廣東工業(yè)大學(xué)碩士論文問(wèn)題與調(diào)度理論研究的深入及各種雜交學(xué)科

7、的發(fā)展，又涌現(xiàn)出了許多新的車(chē)間調(diào)度理論與方法，如：基于運(yùn)籌學(xué)方法、基于控制的方法、基于啟發(fā)式規(guī)則的調(diào)度方法、基于人工智能的方法、基于知識(shí)的調(diào)度方法、確定性最優(yōu)化方法、整數(shù)規(guī)劃、仿真調(diào)度方法等n01。八十年代初期，Stephen等從三個(gè)方面對(duì)調(diào)度進(jìn)行了重新考察，對(duì)未來(lái)發(fā)展做了分析和預(yù)測(cè)，認(rèn)為理論與實(shí)際的結(jié)合將會(huì)成為研究熱點(diǎn)。這個(gè)富有挑戰(zhàn)性的課題吸引了機(jī)械、計(jì)算機(jī)、管理等諸多領(lǐng)域的學(xué)者，許多跨學(xué)科的方法被應(yīng)用到研究中。其中最引人注目的就是以Carnegie．Melton大學(xué)的M．Fox為代表的學(xué)者們開(kāi)展的基于約束傳播的ISIS研究，它標(biāo)志了人工智能開(kāi)始真正應(yīng)用于調(diào)

8、度問(wèn)題。八十年代后期，Rodarnme