王會(huì)穎

(1.合肥工業(yè)大學(xué)管理學(xué)院，安徽合肥230009；2.教育部過(guò)程優(yōu)化與智能決策重點(diǎn)實(shí)驗(yàn)室，安徽合肥230009；3.安徽財(cái)貿(mào)職業(yè)學(xué)院電子信息系，安徽合肥230601)

摘要：人工魚群算法(AFSA)是一新型仿生優(yōu)化算法，已成功地應(yīng)用于求解很多組合優(yōu)化難題。但人工魚群算法對(duì)這些問(wèn)題的求解主要是在集中式串行的環(huán)境下，而云計(jì)算環(huán)境下應(yīng)用人工魚群算法分布式并行對(duì)問(wèn)題進(jìn)行求解的研究很少。該文應(yīng)用云計(jì)算技術(shù)將人工魚群算法并行化，將人工魚群算法和遺傳算法融合，顯著提高了算法求得全局最優(yōu)解的能力。仿真實(shí)驗(yàn)取得了較好的結(jié)果。關(guān)鍵詞：云計(jì)算；MapReduce編程模式；人工魚群算法；遺傳算法

中圖分類號(hào)：TP18文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1009-3044(2012)18-4486-04

Research on Artificial Fish School Algorithm in Cloud Computing

WANG Hui-ying1,2,3

(1.School of Management, Hefei University of Technology, Hefei 230009, China; 2.Key Laboratory of Process Optimization and Intelli? gent Decision-making, Ministry of Education, Hefei 230009, China；3.Department of Electronics and Information, Anhui Finance & Trade Vocational College, Hefei 230601, China)

Abstract: The artificial fish school algorithm (AFSA) is a nove1 bio-inspired optimizing method and was applied successfully to hard com? binational optimization problems. But it solves the problems mainly under the centralized serial environment. The research of the applica? tion of artificial fish school algorithm for distributed parallel problem solving in cloud computing is comparatively little. This paper uses cloud computing to parallel artificial fish school algorithm and combining artificial fish school algorithm with genetic algorithm. it greatly improves the ability of seeking the global excellent result. The simulation results show that the algorithm is more efficient.

Key words: cloud computing; MapReduce; artificial fish school algorithm; genetic algorithm

4.3算法的時(shí)間開銷

云計(jì)算環(huán)境中，任務(wù)執(zhí)行時(shí)間，除求解問(wèn)題所需的時(shí)間外，云計(jì)算框架也要消耗一定的時(shí)間。其耗用的時(shí)間包括：任務(wù)的部署，Map中間結(jié)果的排序、歸類，Reduce結(jié)果的歸并，結(jié)果的輸出及網(wǎng)絡(luò)傳輸?shù)?。?wèn)題求解所需時(shí)間包括：Map和Reduce時(shí)間等。為此，我們研究云計(jì)算環(huán)境中算法運(yùn)行時(shí)各階段的時(shí)間開銷，來(lái)更好地求解問(wèn)題。

選用大規(guī)模任務(wù)實(shí)例30.500-00來(lái)考察算法MIA隨Map數(shù)量變化的情況，Map數(shù)量取10.20.30，其余參數(shù)同上。算法MIA運(yùn)行時(shí)間消耗如表2所示。表2中結(jié)果為連續(xù)運(yùn)行20代，每代各階段的平均值。T1表示任務(wù)開始到Map開始運(yùn)行所消耗的時(shí)間；T2是Map階段的時(shí)間；T3是從Map結(jié)束到Reduce開始的時(shí)間，包括中間結(jié)果的排序、歸類等操作的時(shí)間；T4為Reduce階段的時(shí)間；T5為Reduce結(jié)束到下一任務(wù)開始的時(shí)間，包括Reduce結(jié)果的歸并、輸出等時(shí)間，Total為總時(shí)間。

從表2可以看出，T1、T3、T5在Map數(shù)量變化時(shí)，變化不大，即云計(jì)算框架為實(shí)現(xiàn)任務(wù)的并行，框架所需的時(shí)間基本穩(wěn)定，變化不大；T4為Reduce階段運(yùn)行的時(shí)間，其相對(duì)很?。籘2為Map階段運(yùn)行所占的時(shí)間，其占整個(gè)任務(wù)所需時(shí)間的大部分，且隨Map數(shù)量的變化較大。這些正同問(wèn)題求解過(guò)程相一致，反映問(wèn)題求解的關(guān)鍵，該文對(duì)人工魚群算法所做的工作主要集中在應(yīng)用Map來(lái)并行化人工魚群算法中最耗時(shí)的部分。

文章應(yīng)用云計(jì)算技術(shù)將人工魚群算法并行化，使其運(yùn)行在云計(jì)算環(huán)境中，增強(qiáng)人工魚群算法處理大規(guī)模問(wèn)題的能力。文章提出基于MapReduce的改進(jìn)人工魚群算法MIA，給出其Map函數(shù)和Reduce函數(shù)；并將人工魚群算法和遺傳算法融合，給出算法的框架。改進(jìn)后的算法有效改善人工魚群算法一般僅能得到滿意解域的缺陷。仿真實(shí)驗(yàn)，說(shuō)明了該文算法處理大規(guī)模問(wèn)題的能力和算法改善后的性能，實(shí)驗(yàn)結(jié)果良好。

[1] Ghemawat S, Gobioff H, Leung S T. The Google file system. In: Proc. of the 19th ACM Symp. on Operating Systems Principles[M].New York: ACM Press, 2003.:29-43.

[2] Dean J, Ghemawat S. MapReduce: Simplified data processing on large clusters[C]//Proc. of the 6th Symp. on Operating System Design and Implementation. Berkeley: USENIX Association, 2004:137-150.

[3] Burrows M. The chubby lock service for loosely-coupled distributed systems[C]//Proc. of the 7th USENIX Symp. on Operating Systems Design and Implementation. Berkeley: USENIX Association, 2006:335-350.

[4] Chang F, Dean J, Ghemawat S, et al. Bigtable: A distributed storage system for structured data[C]// Proc. of the 7th USENIX Symp. on Op? erating Systems Design and Implementation. Berkeley: USENIX Association, 2006:205-218.

[5]李曉磊,邵之江,錢積新.一種基于動(dòng)物自治體的尋優(yōu)模式:魚群算法[J].系統(tǒng)工程理論與實(shí)踐, 2002, 22(11):32-38.

[6]李曉磊,路飛,田國(guó)會(huì),等.組合優(yōu)化問(wèn)題的人工魚群算法應(yīng)用[J].山東大學(xué)學(xué)報(bào):工學(xué)版, 2004, 34(5): 64-67.

[7] Multi-Demand Multidimensional Knapsack problem [EB/OL].http://people.brunel.ac.uk/~mastjjb/jeb/orlib/mdmkpinfo.html.