本科畢業(yè)設(shè)計(jì)（論文）題目:基于Gridsim和遺傳算法對(duì)組合雙向拍賣(mài)問(wèn)題的研究姓名2008年6月基于Gridsim和遺傳算法對(duì)組合雙向拍賣(mài)問(wèn)題的研究摘要在計(jì)算機(jī)和網(wǎng)絡(luò)技術(shù)高速發(fā)展的今天，計(jì)算機(jī)的用戶(hù)對(duì)計(jì)算量的需求和擁有呈現(xiàn)一種不合理分配的狀態(tài)：即有些大需求的用戶(hù)擁有資源較少不能滿(mǎn)足需求，而小需求的用戶(hù)使得其擁有的資源閑置。人們希望像家庭用電一樣來(lái)使用計(jì)算資源，這需要通過(guò)網(wǎng)絡(luò)來(lái)完成，如同家庭用電通過(guò)電網(wǎng)來(lái)傳輸。于是越來(lái)越多的人開(kāi)始關(guān)注如何使連入網(wǎng)絡(luò)的計(jì)算機(jī)的資源合理分配。為了在目前的互聯(lián)網(wǎng)狀態(tài)下解決此問(wèn)題，需要推出成熟的新協(xié)議。在這之前，在小范圍內(nèi)的模擬資源調(diào)度是必不可少的。于是網(wǎng)格計(jì)算應(yīng)運(yùn)而生，結(jié)合各種經(jīng)典計(jì)算方法，在此領(lǐng)域中有了很多新的應(yīng)用形式。與此同時(shí)，一些經(jīng)濟(jì)現(xiàn)象也出現(xiàn)在這種資源調(diào)度的過(guò)程里，例如拍賣(mài)。遺傳算法是解決貨郎擔(dān)問(wèn)題(VSP)，車(chē)輛路徑調(diào)度問(wèn)題(VRP)等NP問(wèn)題的成熟算法。本文中需要解決的問(wèn)題也是一個(gè)NP問(wèn)題，故選擇使用遺傳算法作為工具。本文需要解決的問(wèn)題是利用遺傳算法解決組合雙向拍賣(mài)的用戶(hù)和資源的選擇問(wèn)題，再利用由澳大利亞墨爾本大學(xué)RajkumarBuyya領(lǐng)導(dǎo)開(kāi)發(fā)的Gridsim在Java環(huán)境下進(jìn)行資源調(diào)度的仿真。經(jīng)過(guò)多次實(shí)驗(yàn)，以上兩個(gè)問(wèn)題得到了較好的解決。本文對(duì)遺傳算法中的參數(shù)設(shè)置進(jìn)行了多次對(duì)比實(shí)驗(yàn)，得出了特定例子的近似最優(yōu)設(shè)置，為使用遺傳算法解決此類(lèi)問(wèn)題提出了一些建議和方法。關(guān)鍵字網(wǎng)絡(luò)資源調(diào)度網(wǎng)格計(jì)算組合雙向拍賣(mài)遺傳算法GridsimTheDesignandRealizationofInteractiveDemonstrationSystemoftheProtocolofVPN&NATABSTRACTAtpresent,thedistributionofcomputationresourcesamongcomputerusersallovertheworldhasshownaunreasonablestate:thatsomeuserswhohaveheavydemandsowncomparativelylesserresourceswhentheresourcesofusersthathavelittledemandsareleftunused.Peoplewanttoutilizethecomputationresourcesasconvenientaselectricityintheirhouse.Sothereisagrowingnumberofpeoplewhodevotethemselvestofiguringoutthewayofschedulingresourcesofthiskind.Itcanbeimaginedthatanewfully-fledgedprotocolshouldbeappliedtosolvetheproblemabove.Beforethishappened,simulationsofresourceschedulinginanarea-widearerequired.Sogrid-computationhasemergedbecauseofthisopportunityandvariesofapplicationsappearwhenlotsofclassicalgorithmsareaddedin.Simultaneously,someeconomicphenomenonpresentedintheprocessofresourcesscheduling,forinstance,theauction.GeneticalgorithmhavebeenamaturemethodtosolveNPproblemslikeVSPandVRP.Oneprobleminthisarticle,theoptimizingofselectionofusersandresourcesincombinationalauctions,isalsoanNPproblem.ConsideringGAisveryrobustandpopular,sowetakegeneticalgorithmforthetooltoslovetheproblem.Inthisarticle,wefigureoutthewaytodecidewhichusersandresourcessupplierswillbeselectedtojointhefinaltradewithgeneticalgorithm.ThenwestartthetradesimulationofthischosenusersandsuppliersontheplatformofJavacombinewithgridsimwhichhavebeenexploitingbythegroupthatleadedbyRajkumarBuyyainUniversityofMelbourneinAustralia.Thetwomaintargetsaboveareslovedwell,andsomeanalyzationofsolvinguserchoosingproblemsbyusinggeneticalgorithmarepresentedattheend.KEYWORDSResourcesSchedulinginNetworkGridcomputationCombinationalauctionGeneticalgorithmGridsim目錄第一章經(jīng)濟(jì)網(wǎng)絡(luò)簡(jiǎn)介.41.1經(jīng)濟(jì)網(wǎng)絡(luò)研究的起源與應(yīng)用.41.2經(jīng)濟(jì)網(wǎng)絡(luò)研究的最新發(fā)展網(wǎng)格技術(shù).51.3Gridsim開(kāi)發(fā)平臺(tái)簡(jiǎn)介.91.4組合雙向拍賣(mài)簡(jiǎn)介.101.4.1拍賣(mài)的概念.101.4.2拍賣(mài)的競(jìng)價(jià)方式.101.4.3組合雙向拍賣(mài).10第二章基于Gridsim模擬組合雙向拍賣(mài).112.1問(wèn)題描述.112.2解決過(guò)程.122.2.1主要流程.122.2.2body()函數(shù)的設(shè)計(jì).122.3結(jié)果對(duì)比.14第三章遺傳算法簡(jiǎn)介.183.1遺傳算法定義.183.2遺傳算法特點(diǎn).183.3遺傳算法應(yīng)用.193.4遺傳算法現(xiàn)狀.193.5遺傳算法的一般算法.21第四章模擬退火算法簡(jiǎn)介.224.1模擬退火算法簡(jiǎn)介.224.2模擬退火算法的模型.234.3模擬退火算法的簡(jiǎn)單應(yīng)用.244.4模擬退火算法的參數(shù)控制問(wèn)題.25第五章基于遺傳算法解決用戶(hù)資源選擇問(wèn)題.265.1待解決問(wèn)題描述.265.2設(shè)計(jì)思路.265.2.1染色體編碼.265.2.2初始種群選擇.275.2.3適應(yīng)函數(shù)的設(shè)計(jì).275.2.4選擇雙親.285.2.5交配.285.2.6變異及不可行解處理.285.2.7進(jìn)化.285.2.8跳出條件.295.2.9算法描述.295.3實(shí)驗(yàn)分析.295.3.1結(jié)果對(duì)比.295.3.2算法中參數(shù)對(duì)結(jié)果影響的討論.30第一章經(jīng)濟(jì)網(wǎng)絡(luò)簡(jiǎn)介1.1經(jīng)濟(jì)網(wǎng)絡(luò)研究的起源與應(yīng)用在信息量膨脹的今天，網(wǎng)絡(luò)上有關(guān)經(jīng)濟(jì)的搜索量急劇上升。眾多證據(jù)表明，網(wǎng)絡(luò)對(duì)社會(huì)和經(jīng)濟(jì)的推動(dòng)作用是十分重要的。很多著名的例子已經(jīng)說(shuō)明了網(wǎng)絡(luò)在求職上面（Holzer1987,Montgomery1991），交易（Lazerson1993,Nishiguchi1994）,促進(jìn)信貸（McMillanandWoodruff1999），互助保險(xiǎn)（FafchampsandLund2001），以及福利參與（Bertrand,Luttmer,andMullainathan2000）上的積極作用。由于之前極少有對(duì)網(wǎng)絡(luò)具有實(shí)驗(yàn)性工作，漸漸的，經(jīng)濟(jì)網(wǎng)絡(luò)的理論研究引起了人們濃厚的興趣。在當(dāng)時(shí)，關(guān)于網(wǎng)絡(luò)的實(shí)驗(yàn)工作數(shù)量仍然很少，但相關(guān)文獻(xiàn)已經(jīng)開(kāi)始出現(xiàn)。這些論文出現(xiàn)的目的是對(duì)目前存在的實(shí)驗(yàn)性工程的一個(gè)概括，并指出對(duì)該領(lǐng)域未來(lái)研究的一些道路。在實(shí)驗(yàn)室里完成的實(shí)驗(yàn)為分析經(jīng)濟(jì)問(wèn)題提供了一些強(qiáng)大的，有幫助的技術(shù)。實(shí)驗(yàn)的主要優(yōu)點(diǎn)在于控制變量的能力（例如花費(fèi)，信息，時(shí)間等）。這些變量很可能影響個(gè)人和集體的行為，而在現(xiàn)實(shí)中，這些也許是無(wú)法模擬的。博弈理論為特殊模型中的假設(shè)提供了精確的公式，所以和理論模型一樣，這種被設(shè)計(jì)好的實(shí)驗(yàn)對(duì)于使經(jīng)濟(jì)學(xué)變成一個(gè)經(jīng)驗(yàn)主義的科學(xué)來(lái)說(shuō)，是關(guān)鍵的因素。在經(jīng)驗(yàn)主義的經(jīng)濟(jì)學(xué)家發(fā)現(xiàn)經(jīng)濟(jì)網(wǎng)絡(luò)之前，另外的一些社會(huì)學(xué)家已經(jīng)著手調(diào)查各個(gè)領(lǐng)域中現(xiàn)有的網(wǎng)絡(luò)效應(yīng)。也許最早的網(wǎng)絡(luò)實(shí)驗(yàn)就是五十年代早期，在麻省理工的社會(huì)心理學(xué)家AlexBavelas和他的同事進(jìn)行的“MITexperiments”。在這些實(shí)驗(yàn)中，一組中的每個(gè)人都被分配解決一個(gè)問(wèn)題。有代表性的是，每個(gè)人都拿到了一張標(biāo)有很多不同符號(hào)的卡片。他們的任務(wù)是找到所有人都有的一個(gè)符號(hào)。每個(gè)人可以通過(guò)寫(xiě)紙條的方式交流，但僅限于通過(guò)外部設(shè)置好的一個(gè)網(wǎng)絡(luò)來(lái)傳遞信息。Bavelas和他的同事提出了四種網(wǎng)絡(luò)結(jié)構(gòu)：鏈?zhǔn)?，圈式，星式，Y式，后來(lái)發(fā)現(xiàn)，星式和Y式是解決問(wèn)題最快的網(wǎng)絡(luò)。而且如果限定傳送信息的條數(shù)，用這種網(wǎng)絡(luò)可以得到最少的錯(cuò)誤。在接下來(lái)的幾年里，通信的向心性以及網(wǎng)絡(luò)的組成的效果被更加深入的研究。（可以參考Shaw在1964年做的一個(gè)批判性的回顧）。Freeman在19791980年定義并檢測(cè)了三種不同結(jié)構(gòu)的向心性概念，使得此領(lǐng)域的用辭和術(shù)語(yǔ)變得明晰。買(mǎi)賣(mài)網(wǎng)絡(luò)，是經(jīng)濟(jì)網(wǎng)絡(luò)的一個(gè)具體分支，代表了一個(gè)對(duì)經(jīng)濟(jì)無(wú)論從理論還是經(jīng)驗(yàn)的研究都比較新的領(lǐng)域。Kranton和Minehart在早期對(duì)組成特殊網(wǎng)絡(luò)結(jié)構(gòu)中買(mǎi)賣(mài)雙方的個(gè)體行為十分感興趣，并做了研究。Ninshigushi1994年在Japaneseelectronicsindustry，Lazerson1993年在Italiangarmentindustry也做了研究。特別的是，他們想知道是什么使得買(mǎi)賣(mài)雙方各自建立對(duì)多個(gè)交易伙伴的連接關(guān)系；然后評(píng)價(jià)這些網(wǎng)絡(luò)結(jié)構(gòu)是否能夠有效率的工作。1.2經(jīng)濟(jì)網(wǎng)絡(luò)研究的最新發(fā)展網(wǎng)格技術(shù)網(wǎng)絡(luò)的出現(xiàn)，改變了人們使用計(jì)算機(jī)的方式，而Internet的出現(xiàn)，又改變了人們使用網(wǎng)絡(luò)的方式?？v觀互聯(lián)網(wǎng)的發(fā)展歷程，Internet技術(shù)和Web技術(shù)的主要成就是實(shí)現(xiàn)了計(jì)算機(jī)和網(wǎng)頁(yè)的連通，提供收發(fā)郵件、瀏覽和下載網(wǎng)頁(yè)信息等相關(guān)服務(wù)，它所關(guān)注的問(wèn)題是如何使信息傳輸流量更大、傳輸速度更快、傳輸更加安全。而網(wǎng)格技術(shù)則關(guān)注如何有效安全地管理和共享連接到Internet上的各種資源，并提供相應(yīng)的服務(wù)，網(wǎng)格所關(guān)注的問(wèn)題無(wú)論從范圍、程度還是本質(zhì)上都已經(jīng)與互聯(lián)網(wǎng)所關(guān)心的互連問(wèn)題有了很大的不同。網(wǎng)格在連通計(jì)算機(jī)和網(wǎng)頁(yè)的基礎(chǔ)上，還將各種信息資源，例如數(shù)據(jù)庫(kù)、軟件以及各種信息獲取設(shè)備都連接成一個(gè)整體，整個(gè)網(wǎng)絡(luò)如同一臺(tái)巨大無(wú)比的計(jì)算機(jī)，向每個(gè)用戶(hù)提供包括計(jì)算能力、數(shù)據(jù)存儲(chǔ)能力以及各種應(yīng)用工具等一體化的透明服務(wù)。它強(qiáng)調(diào)的是全面地共享資源、全面地應(yīng)用服務(wù)。目前的技術(shù)還沒(méi)有實(shí)現(xiàn)資源層面的全面共享，只是信息的傳輸，所以屬于網(wǎng)絡(luò)技術(shù)，而非網(wǎng)格技術(shù)?；ヂ?lián)網(wǎng)新一次浪潮的實(shí)質(zhì)，就是要將萬(wàn)維網(wǎng)（WorldWideWeb）升華為網(wǎng)格（GreatGlobalGrid），即實(shí)現(xiàn)WWW到GGG的變革。網(wǎng)格作為一個(gè)集成的計(jì)算與資源環(huán)境，能夠吸收各種計(jì)算資源，將它們轉(zhuǎn)化成一種隨處可得的、可靠的、標(biāo)準(zhǔn)的且相對(duì)經(jīng)濟(jì)的計(jì)算能力，其吸收的計(jì)算資源包括各種類(lèi)型的計(jì)算機(jī)、網(wǎng)絡(luò)通信能力、數(shù)據(jù)資料、儀器設(shè)備甚至有操作能力的人等各種相關(guān)資源。網(wǎng)格是借鑒電力網(wǎng)的概念提出的，網(wǎng)格的最終目的是希望用戶(hù)在使用網(wǎng)格計(jì)算能力解決問(wèn)題時(shí)像使用電力一樣方便，用戶(hù)不用去考慮得到的服務(wù)來(lái)自于哪個(gè)地理位置，由什么樣的計(jì)算設(shè)施提供。也就是說(shuō)，網(wǎng)格給最終的使用者提供的是一種通用的計(jì)算能力。電力網(wǎng)中需要有大量的變電站等設(shè)施對(duì)電網(wǎng)進(jìn)行調(diào)控，相應(yīng)的網(wǎng)格中也需要大量的管理站點(diǎn)來(lái)維護(hù)網(wǎng)格的正常運(yùn)行。網(wǎng)格的結(jié)構(gòu)及資源的調(diào)控將更復(fù)雜，需要解決的問(wèn)題也更多。因?yàn)榫W(wǎng)格所關(guān)心的問(wèn)題不再是文件交換，而是直接訪(fǎng)問(wèn)計(jì)算機(jī)、軟件、數(shù)據(jù)和其他資源。這就要求網(wǎng)格具備解決資源與任務(wù)的分配和調(diào)度、安全傳輸與通信實(shí)時(shí)性保障、人與系統(tǒng)以及人與人之間的交互等能力。網(wǎng)格提供的資源是隨時(shí)間動(dòng)態(tài)變化的，原來(lái)?yè)碛械馁Y源或者功能，在下一時(shí)刻可能就會(huì)出現(xiàn)故障或者拒絕被使用，而原來(lái)沒(méi)有的資源，可能隨著時(shí)間的進(jìn)展會(huì)不斷加入進(jìn)來(lái)。一、網(wǎng)絡(luò)的典型體系結(jié)構(gòu)網(wǎng)格技術(shù)不斷地發(fā)展使人們逐漸地意識(shí)到了網(wǎng)格體系結(jié)構(gòu)的重要性。網(wǎng)格體系結(jié)構(gòu)用來(lái)劃分系統(tǒng)的基本組件，指定系統(tǒng)組件的目的和功能，說(shuō)明組件之間如何相互作用，規(guī)定了網(wǎng)格各部分相互的關(guān)系與集成的方法?？梢哉f(shuō)，網(wǎng)格體系結(jié)構(gòu)是網(wǎng)格的骨架和靈魂，是網(wǎng)格技術(shù)中最核心的部分。1五層沙漏結(jié)構(gòu)五層沙漏結(jié)構(gòu)是一種早期的抽象層次結(jié)構(gòu)，以“協(xié)議”為中心，強(qiáng)調(diào)協(xié)議在網(wǎng)格的資源共享和互操作中的地位。通過(guò)協(xié)議實(shí)現(xiàn)一種機(jī)制，使得虛擬組織的用戶(hù)與資源之間可以進(jìn)行資源使用的協(xié)商、建立共享關(guān)系，并且可以進(jìn)一步管理和開(kāi)發(fā)新的共享關(guān)系。這一標(biāo)準(zhǔn)化的開(kāi)放結(jié)構(gòu)對(duì)網(wǎng)格的擴(kuò)展性、互操作性、一致性以及代碼共享都很有好處。圖1為五層沙漏結(jié)構(gòu)的典型結(jié)構(gòu)圖。五層結(jié)構(gòu)之所以形如沙漏，是由各部分協(xié)議數(shù)量的分布不均勻引起的。考慮到核心的移植、升級(jí)的方便性，核心部分的協(xié)議數(shù)量相對(duì)比較少(例如Internet上的TCP和HTTP)，對(duì)于其最