基于mpi的海量數(shù)據(jù)分析方法研究版

NP關(guān)鍵字：，MPIWiththearrivaloftheeconomicglobalization,therapiddevelopmentofelectronicinformationtechnology,arapidincreaseintheuseofcomputerusers,theinformationera,sothattheinformationdataincrease,massivedataprocessinghas eaveryimportanttechniqueinthefieldoftheinformation.Knapsackproblemnowiswidelyusedinvarioustechnicalfields,thispaperistakingthisasthebreakthroughpoint,andusetheparallelalgorithmarestudiedandaseriesofKnapsackproblemisanapplicationofawiderangeofissues.AsanNPcompleteproblem,andputsforwardtheknapsackproblemisfound,causetherelatedresearchonmanyaspects,andalloftheresearchisthehotresearchfield,boththetheoreticalresearchandpracticalresearch.Manynumericalmethodstosolveknapsackproblem,knapsackprobleminrealitytherearemanyrestrictions,butintheorytosolvetheknapsackproblem,itcanbesolveddirectly.Withthedevelopmentofsociety,therapiddevelopmentofelectronicinformationtechnology,thedataamount,theamountofinformationintherapidgrowth,sothatallofthedata,theamountofinformationinthedevelopmenttothemassivedata,whichleadstosolveproblemsinreality,needalargescaleandmorerestrictedconditions,italsoledtoalotofresearchalgorithm,willnotsolvetheknapsackproblem.Inthispaper,combinedwiththemassivedataparallelprocessingmethodbasedonMPI,inordertosolvetheknapsackproblem.:parallelgeneticalgorithm,knapsackproblem,MPIalgorithm,mass 第一章緒 課題來源及研究意 課題來 課題研究意 國內(nèi)外現(xiàn) 背包問題研究展現(xiàn) 國內(nèi)外相關(guān)研究存在的問 結(jié) 第二章開發(fā)環(huán)境及涉及技 消息傳遞接 MPI編程基本概 MPI基本數(shù)據(jù)類 MPI消 MPI通 MPI的C語言 MPI工具介 MPICH2簡 MPICH2特 并行計算簡 本章小 第三章遺傳算 遺傳算法概 遺傳算法求解步 算法描 算法流程 遺傳算法的主要應(yīng) 并行遺傳算法實現(xiàn)方 本章小 第四章并行遺傳算法求解背包問題探 問題提 相關(guān)算法分 回溯 動態(tài)規(guī) 貪心策 建模分 遺傳算法因子分 4.4.1編 選擇操 交叉操 變 遷移因 算法實 流程 算法偽代 子種群通信結(jié) 第五章仿真實 實驗數(shù) 測試環(huán) 硬件環(huán) 軟件環(huán) 實驗結(jié)果及分 并行度對種群大小選擇的影 并行度對交叉概率選擇的影 并行度對變異概率選擇的影 并行度對最大進化代數(shù)選擇的影 本章小 第六章總結(jié)與展 總 研究工作展 第一章得以解決并行分布式算法在解決一些問題時需要一血因子合理的利用因子，ixi=1[1]。NP遺傳算法是一種搜索型算法，是利用人工墨跡和自然選擇的一個過程。通常是用數(shù)學(xué)算法來模擬這個過程的的進化論中說到適者生存優(yōu)勝劣汰。 一個數(shù)值來衡量的適應(yīng)能力[2]。，續(xù)取得更大的發(fā)展直到1974年和米對背包問題的研究終于取得突破提出了背包問題的可分性可以用分直接定法來求解幾年后提出“核”，都對并行編程技術(shù)做出了突出貢獻，在此我們選取具有規(guī)范標準、技術(shù)成MPI及C1993MPIMPi，MPI一種語言，它是一個標準的消息傳遞接口庫，MPI有著許多消息傳遞系統(tǒng)的優(yōu)勢，作MPIMPI點通信，一種是集合通信[11]。MPICFortranMPI129MPI30MPIMPI進程：一個獨立參與通信的MPIMPIMPI_為開頭，后面所接的一般為C2.1MPIMPIMPI2.1并且，MPI2.2消息消息表情是用來區(qū)分通信中出現(xiàn)的相同類型的消息。如下表顯示，帶上PAQXPBQY表2.3消息使MPIn-12.4MPI表2.5MPI2.5MPIMPIMPIMPI圖2.2MPI_Buffer_attchMPI_Buffer_detach圖2.3MPI圖2.4圖2.5區(qū)的數(shù)據(jù)已經(jīng)完整，可以被正確。RootRoot2.6MPIMPICMPI_Init：MPI2.7MPIMPI_Finalize：MPI2.8MPIm_rank：2.9MPIm_size：2.10MPIMPI_Get_processor_name：表2.11MPIMPI_send：2.12MPIMPI_Recv：source[5]2.13MPIMPIMPICH2CMPICH2MPI-1.MPI-2MPICH2跨平臺：可用于共享系統(tǒng)、桌面系統(tǒng)、多處理器系統(tǒng)MPI并行計算的研究領(lǐng)域很廣泛，在很多領(lǐng)域都有涉及和研究，主要研究的領(lǐng)域就是空間領(lǐng)域。并行計算分為兩種，一種是數(shù)據(jù)并行，一種是任務(wù)并行。數(shù)據(jù)并行在處理分析問題方面上，要比較容易使用，因為它是用化大為小，化繁為簡的原則來進行解決和分析問題的，所以要簡單容易的多。空間并行導(dǎo)致產(chǎn)生了兩種并行機：單指令流多數(shù)據(jù)流和多指令多數(shù)據(jù)流。我們一般常用的并不是這兩種，一般我們比MIMD向量處理機、工作站機群、大規(guī)模并行處理機、分布式共享處理機。(3)MPIMPI等進化計算理論協(xié)同作用度越來越高，能共同作用解決的問題。EP和ES和遺算法有很多相似的地方、也有著不一樣的特點，他們都可以用來對自然界生物的進化機理做計算機仿真實驗，他們的發(fā)展過程很接近，當前，大量的研究目標在于關(guān)于這個三個算法的對比以及能否更好的結(jié)合三者來解決實際問題。三是遺傳算法的并行化研究逐漸開始。這一研究對于遺傳算法研究起到了很大的促進作用，另外并行計算的發(fā)展促進新一代智能計算機體系結(jié)構(gòu)的研究。四是基于遺傳算法的努力學(xué)2005年，等通過對并行遺傳算法得到研究和分析，最終求解出了TSP問第二步編碼：產(chǎn)生，常用方法為二進制編碼。長度為代表第i ，xi=0表示該物品不取，xi=1表示該物品放入背包

nnFxi*

=1或0(i= 第四步適應(yīng)度評價：計算當前的適應(yīng)度值個子，交叉點k在[1，n-1]之間；在收斂前或者最大進化代數(shù)之內(nèi)，重復(fù)步驟四~七步，最終的到最優(yōu)解[6]3.13.1島嶼模式。每個處理器獨立的進行進化，并在相鄰處理器間進行最優(yōu)互相傳[7]第四章O（n*2nO（n*mn，mO（n*logn切記最小進化代數(shù)設(shè)置太小，當最大進化代數(shù)打到一定的數(shù)值時，要估4.1圖4.1本文采用{0，1}二進制編碼，利用一維數(shù)組對應(yīng)存放物品的重量信息和物品價值信息，利用一維數(shù)組表示二值進制串，串中位的取值為0或者1。在二進制串對為值為1表示該物品選中，值為0表示放棄該物品。如二進制串<0100100010101>表示選取第、、、 、件物品放入背包。長度為l的二進制 函數(shù)0.73，個被選中；產(chǎn)生隨機數(shù)0.32，則第一個被選中。算法流程圖如下所示表4.1賭選法概率計圖4.2算法概率計兩個父如下父 00110101父 10101011選取交叉點位置在3，進行交叉得到兩個子，如下子100101011子210110101采用二進制編碼進行編碼，會導(dǎo)致便已操作在對應(yīng)取反。而每條上的每個都會依據(jù)變異該路隨即進行變異的。遍歷的每一個位產(chǎn)生隨機數(shù)匹配變異概率如相等則發(fā)生變異操作。如下，變異第2、5位：變異 010111100變異 000101100他子種送來的；二選取子種群中最優(yōu)的進行發(fā)送，并接收。第法隨機性太強，如果選取的適應(yīng)度偏低不僅不能加快算法進化的速，可能會導(dǎo)致最優(yōu)擴散太快，導(dǎo)致局部收斂過快，不能求得理想的最優(yōu)解。本文提出選取子種群中次優(yōu)的作為遷移因子在各個子種群間交流序存放在數(shù)組中，即在數(shù)組首端，最優(yōu)在數(shù)組尾端。4.6結(jié)構(gòu)圖如圖4.9實驗，對的數(shù)據(jù)進行相關(guān)分析。 （該數(shù)據(jù)即為遺傳算法中個數(shù))背包容量：2000；物品的價值及物品的重量從1G的文件中，物品的價值和重量有如下限制：所使用的MPI工具為較成MPICH2。PC（續(xù)實驗結(jié)束后收集仿真數(shù)據(jù)然后利用工具來繪制與數(shù)據(jù)相關(guān)的圖表種群大小是指參與進化的數(shù)目，它是算法進化的重要因素。實驗數(shù)據(jù)設(shè)定：交叉概率p_c=0.6；變異概率p_m=0.05；長度l_chrom=100；最大進化1105.35.1；算法進化過程叉率的大小取決于交叉概率的選定，交叉概率是影響算法收斂；5.45.4（續(xù)5.2收斂。實驗數(shù)據(jù)設(shè)定：種群大小pop_size=600；交叉概率p_c=0.6；長度105.55.5（續(xù)5.3l_chrom100；pop_size=600；p_c=0.6。最大進化代105.65.4結(jié)果分析：從圖5.4、可以看出，當進化代數(shù)過小的情況下，理想的最優(yōu)解不能的進行了仿真實驗完成了并行算法的研究解決的問題主要有以下幾個方面 MPIMPIMPI 另外，本的研究和撰寫得以順利進行，必須要感謝我的大學(xué)同學(xué)以及其他朋（4：405~407MarloS,TothP.AnApperB