資源描述：
《本科畢業(yè)論文設(shè)計(jì)基于調(diào)度系統(tǒng)本科畢業(yè)設(shè)計(jì)》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫(kù)。
1、1引言社會(huì)在進(jìn)步，科技在發(fā)展，我們將越來(lái)越多的科技產(chǎn)品運(yùn)用于生產(chǎn)，服務(wù)大眾Z中,這極大的推動(dòng)了人們的生活水平，提高了生活的質(zhì)量。然而，當(dāng)高端的生產(chǎn)水平遇到老舊的調(diào)度方式的時(shí)候，造成了一系列低水準(zhǔn)的結(jié)果。調(diào)度是指管理并安排，調(diào)度系統(tǒng)則是指在考慮到系統(tǒng)運(yùn)行吋在不同階段的損耗，消耗時(shí)間不同的因索下，通過(guò)一定的調(diào)度方法，策略，從而實(shí)現(xiàn)對(duì)所研究系統(tǒng)正常運(yùn)行的最少消耗，路程等。調(diào)度系統(tǒng)的使用，提高了處理問(wèn)題的能力，效率，同時(shí)也明顯的減少了資源的損耗。然而，現(xiàn)有的調(diào)度系統(tǒng)是存在有一定的缺陷的，以在多個(gè)相連地點(diǎn)小尋求任意兩點(diǎn)
2、相連的最短路徑為例，當(dāng)?shù)攸c(diǎn)數(shù)較少時(shí)，我們可以挨個(gè)嘗試進(jìn)而進(jìn)行比較得出最優(yōu)解，可是當(dāng)?shù)攸c(diǎn)數(shù)大到一定程度的時(shí)候，窮舉法就不現(xiàn)實(shí)了。這止是調(diào)度系統(tǒng)也存在的問(wèn)題，我們既要求調(diào)度系統(tǒng)做出正確的路徑，同時(shí)要求它在冇效的時(shí)間做出，這就顯然成為了矛盾的所在。沒有窮舉過(guò)自然就無(wú)法說(shuō)某條路徑是最優(yōu)的，因此折屮的辦法就是在有限的時(shí)間里，找到一條較優(yōu)的路徑，而這些正是本課題所研究的。2課題背景2.1什么是調(diào)度系統(tǒng)調(diào)度系統(tǒng)是指應(yīng)用丁?生產(chǎn)生活屮的通過(guò)一定的調(diào)度算法實(shí)現(xiàn)對(duì)目標(biāo)流程的安排及控制，以期望達(dá)到減少損耗，提高效率的目的的系統(tǒng)，隨
3、著社會(huì)科學(xué)技術(shù)的飛速發(fā)展，人們對(duì)高效率生產(chǎn)流程的期待，加速著調(diào)度系統(tǒng)的進(jìn)步。而在調(diào)度系統(tǒng)中，調(diào)度算法又占到了絕對(duì)重要點(diǎn)的比率。因此，一個(gè)好的調(diào)度系統(tǒng)更多又體現(xiàn)在其使用的調(diào)度算法是否適用于對(duì)應(yīng)生產(chǎn)的要求，并需在合理的時(shí)間內(nèi)給出設(shè)計(jì)。2.2禁忌算法的概念搜索是人工智能的一個(gè)基本問(wèn)題，一個(gè)問(wèn)題的求解過(guò)程就是搜索。人工智能在各應(yīng)用領(lǐng)域屮，被廣泛的使用。現(xiàn)在，搜索技術(shù)滲透在各種人工智能系統(tǒng)屮，可以說(shuō)沒有哪一種人工智能的應(yīng)用不用搜索方法。禁忌搜索算法(TabuSearch或TabooSearch,簡(jiǎn)稱TS)的思想最早db
4、Glover(美國(guó)工程院院士，科羅拉多大學(xué)教授)在1977年提出，它是對(duì)局部鄰域搜索的一種擴(kuò)展，是一種全局鄰域搜索算法，是人工智能的一種休現(xiàn)，是一種全局逐步尋優(yōu)算法，是對(duì)人類智力過(guò)程的一種模擬。TS算法通過(guò)引入一個(gè)靈活的存儲(chǔ)結(jié)構(gòu)和相應(yīng)的禁忌準(zhǔn)則來(lái)避免迂回搜索，并通過(guò)藐視準(zhǔn)則來(lái)赦免一些被禁忌的優(yōu)良狀態(tài)，進(jìn)而保證多樣化的有效探索以最終實(shí)現(xiàn)全局優(yōu)化。迄今為止，TS算法在組合優(yōu)化、生產(chǎn)調(diào)度、機(jī)器學(xué)習(xí)、電路設(shè)計(jì)和神經(jīng)網(wǎng)絡(luò)等領(lǐng)域取得了很大的成功，近年來(lái)又在函數(shù)全局優(yōu)化方面得到較多的研究，并大有發(fā)展的趨勢(shì)。2.3鄰域搜索局
5、部鄰域搜索是基于貪婪思想持續(xù)地在當(dāng)前的鄰域屮進(jìn)行搜索，雖然算法通用易實(shí)現(xiàn)，且容易理解，但其搜索性能完全依賴于鄰域結(jié)構(gòu)和初始解，尤其容易陷入局部極小而無(wú)法保證全局優(yōu)化性。這種鄰域搜索方法容易實(shí)現(xiàn)理解，容易實(shí)現(xiàn)，而且具有很好的通用性，但是搜索結(jié)果完全依賴于初始解和鄰域的結(jié)構(gòu)，而且只能搜索到局部最優(yōu)解。為了實(shí)現(xiàn)全局搜索，禁忌搜索采用允許接受劣解來(lái)逃離局部最優(yōu)解。針對(duì)局部領(lǐng)域搜索,為了實(shí)現(xiàn)全局優(yōu)化，可嘗試的途徑冇：以口J控性概率接受劣解來(lái)逃逸局部極小，如模擬退火算法；擴(kuò)大領(lǐng)域搜索結(jié)構(gòu)，如TSP的2?opt擴(kuò)展到k-o
6、pt；多點(diǎn)并行搜索，如進(jìn)化計(jì)算；變結(jié)構(gòu)領(lǐng)域搜索(Mladenovicetal,1997)；另外，就是釆用TS的禁忌策略盡量避免迂回搜索，它是一種確定性的局部極小突跳策略。3禁忌搜索算法3.1算法基本思想禁忌搜索算法的基本思想就是在搜索過(guò)程中將近期的歷史上的搜索過(guò)程存放在禁忌表(TabuList)屮，阻止算法重復(fù)進(jìn)入，這樣就有效地防止了搜索過(guò)程的循環(huán)。禁忌表模仿了人類的記憶功能，禁忌搜索因此得名，所以稱它是一種智能優(yōu)化算法。具體的思路如下：禁忌搜索算法采用了鄰域選優(yōu)的搜索方法，為了能逃離局部最優(yōu)解，算法必須能夠
7、接受劣解，也就是每一次迭代得到的解不必一定優(yōu)于原來(lái)的解。但是。一旦接受了劣解，迭代就可能陷入循環(huán)。為了避免循環(huán)，算法將最近接受的一些移動(dòng)放在禁忌表屮，在以后的迭代屮加以禁止。即只有不在禁忌表屮的較好解(可能比當(dāng)前解差)才能接受作為下一次迭代的初始解。隨著迭代的進(jìn)行，禁忌表不斷更新，經(jīng)過(guò)一定迭代次數(shù)后，最早進(jìn)入禁忌表的移動(dòng)就從禁忌表中解禁退后。為了找到“全局最優(yōu)解”，就不應(yīng)該執(zhí)著于某一個(gè)特定的區(qū)域。局部搜索的缺點(diǎn)就是太貪焚地對(duì)某一個(gè)局部區(qū)域以及其鄰域搜索，導(dǎo)致一葉障目，不見泰山。禁忌搜索就是對(duì)于找到的一部分局部
8、最優(yōu)解，冇意識(shí)地避開它(但不是完全隔絕)，從而獲得更多的搜索區(qū)間。兔子們找到了泰山，它們之中的一只就會(huì)留守在這里，其他的再去別的地方尋找。就這樣，一大圈后，把找到的兒個(gè)山峰一比較，珠穆朗瑪峰脫穎而岀。當(dāng)兔了們?cè)賹ふ业臅r(shí)候，一般地會(huì)有意識(shí)地避開泰山，因?yàn)樗麄冎?，這里已經(jīng)找過(guò)，并且有一只兔子在那里看著了。這就是禁忌搜索中“禁忌表(tabulist)”的含義。那只留在泰山的兔子一般不會(huì)就安家在那里了，它
