Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Phân tích thiết kế tách biệt áp dụng cho hiệu suất của các thuật toán tiến hóa song song
Tóm tắt
Tính toán song song là một phương pháp mạnh mẽ để giảm thời gian tính toán và cải thiện chất lượng các giải pháp của các thuật toán tiến hóa (EA). Ban đầu, các EA song song (PEA) chỉ có thể chạy trên các máy tính song song đắt đỏ và khó tiếp cận. Khi các bộ vi xử lý đa lõi trở nên phổ biến, hiệu suất cải thiện mà các chương trình song song mang lại là động lực lớn cho các EA đòi hỏi tính toán cao chuyển sang hình thức chương trình song song và tận dụng sức mạnh của các lõi đa. Việc triển khai song song mang lại nhiều yếu tố ảnh hưởng đến hiệu suất và do đó làm tăng thêm độ phức tạp trong việc đánh giá PEA. Thống kê có thể hỗ trợ trong nhiệm vụ này và có thể đảm bảo tính có ý nghĩa và đúng đắn của các kết luận với tối thiểu các thử nghiệm, với điều kiện là thiết kế thí nghiệm chính xác được áp dụng. Chúng tôi chỉ ra cách đảm bảo ước tính chính xác về tốc độ tăng và cách áp dụng một thiết kế tách biệt trong phân tích hiệu suất PEA. Hiệu suất và các tác động của yếu tố không giống nhau cho hai hàm kiểm định đã được nghiên cứu trong công việc này. Hàm Rastrigin cho thấy hệ số biến thiên cao hơn hàm Rosenbrock, và các tác động của yếu tố và tương tác về tốc độ gia tăng của thuật toán di truyền song song I (PGA-I) thì khác nhau trong cả hai. Như một nghiên cứu điển hình, chúng tôi đánh giá ảnh hưởng của việc di cư liên quan đến các tham số đối với hiệu suất của thuật toán tiến hóa song song giải quyết hai bài toán chuẩn được thực hiện trên một bộ vi xử lý đa lõi. Chúng tôi đã nỗ lực đặc biệt trong việc áp dụng cẩn thận các khái niệm thống kê trong phát triển phân tích của mình.
Từ khóa
#tính toán song song #thuật toán tiến hóa #hiệu suất #thiết kế tách biệt #Rastrigin #Rosenbrock #di cư #bộ vi xử lý đa lõiTài liệu tham khảo
Chiarandini M, Paquete L, Preuss M, Ridge E: Experiments on metaheuristics: methodological overview and open issues. Technical report DMF-2007–03–003 The Danish Mathematical Society 2007.
Cantú-Paz E: Efficient and accurate parallel genetic algorithms. Kluwer Academic Publishers, Norwell; 2000.
Tomassini M: Spatially structured evolutionary algorithms: artificial evolution in space and time (natural computing series). Springer, Secaucus; 2005.
Alba E: Parallel evolutionary algorithms can achieve super-linear performance. Inf Process Lett 2002, 82(1):7–13. 10.1016/S0020-0190(01)00281-2
Kim H, Bond R: Multicore software technologies. IEEE Signal Process Mag 2009, 26(6):80–89.
Diaz-Frances E, Rubio F: On the existence of a normal approximation to the distribution of the ratio of two independent normal random variables. Stat Pap 2013, 54(2):309–323. 10.1007/s00362-012-0429-2
Qiao CG, Wood GR, Lai CD, Luo DW: Comparison of two common estimators of the ratio of the means of independent normal variables in agricultural research. J Appl Math Decis Sci 2006 2006. doi:10.1155/JAMDS/2006/78375 doi:10.1155/JAMDS/2006/78375
Eiben AE, Smith SK: Parameter tuning for configuring and analyzing evolutionary algorithms. Swarm and Evol Comput 2011, 1: 19–31. 10.1016/j.swevo.2011.02.001
Touati S, Worms J, Briais S: The speedup-test: a statistical methodology for programme speedup analysis and computation. Concurrency and Comput: Practice and Experience 2012, 25(10):1410–1426.
Alba E, Luque G, Nesmachnow S: Parallel metaheuristics: recent advances and new trends. Int Trans Oper Res 2013, 20(1):1–48. doi:10.1111/j.1475–3995.2012.00862.x. doi:10.1111/j.1475-3995.2012.00862.x. 10.1111/j.1475-3995.2012.00862.x
Coy SP, Golden BL, Runger GC, Wasil EA: Using experimental design to find effective parameter settings for heuristics. J Heuristics 2001, 7: 77–97. 10.1023/A:1026569813391 10.1023/A:1026569813391 10.1023/A:1026569813391
Czarn A, MacNish C, Vijayan K, Turlach BA, Gupta R: Statistical exploratory analysis of genetic algorithms. Evol Comput, IEEE Trans 2004, 8(4):405–421. doi:10.1109/TEVC.2004.831262 doi:10.1109/TEVC.2004.831262 10.1109/TEVC.2004.831262
Bartz-Beielstein T: Experimental research in evolutionary computation: the new experimentalism (natural computing series). Springer, Secaucus; 2006.
Rardin RL, Uzsoy R: Experimental evaluation of heuristic optimization algorithms: a tutorial. J Heuristics 2001, 7: 261–304. doi:10.1023/A:1011319115230 doi:10.1023/A:1011319115230 10.1023/A:1011319115230
Shahsavar M, Najafi AA, Niaki STA: Statistical design of genetic algorithms for combinatorial optimization problems. Math Probl Eng 2011, 1–7. doi:10.1155/2011/872415 doi:10.1155/2011/872415
Pinho AFD, Montevechi JAB, Marins FAS: Análise da aplicação de projeto de experimentos nos parâmetros dos algoritmos genéticos. Sistemas & Gestão 2007, 2: 319–331.
Petrovski A, Brownlee AEI, McCall JAW: Statistical optimisation and tuning of GA factors. The 2005 IEEE Congress on Evolutionary Computation (CEC 2005) 2005, 1: 758–764.
Mühlenbein H: Darwin’s continent cycle theory and its simulation by the prisoner’s dilemma. Complex Syst 1991, 5: 459–478.
Hooker J: Needed: an empirical science of algorithms. Oper Res 1994, 42: 201–212. 10.1287/opre.42.2.201
Hooker J: Testing heuristics: we have it all wrong. J Heuristics 1995, 1: 33–42. doi:10.1007/BF02430364 doi:10.1007/BF02430364 10.1007/BF02430364
McGeoch CC: Feature article—toward an experimental method for algorithm simulation. INFORMS J Comput 1996, 8(1):1–15. 10.1287/ijoc.8.1.1
Johnson D: A theoretician’s guide to the experimental analysis of algorithms. Data Structures, Near Neighbor Searches, and Methodology: Fifth and Sixth DIMACS Implementation Challenges 2002, 5: 215–250.
Eiben AE, Jelasity M: A critical note on experimental research methodology in experimental research methodology in EC. Proceedings of the 2002 Congress on Evolutionary Computation (CEC’2002) 2002, 1: 582–587.
Steinberg DM, Hunter WG: Experimental design: review and comment. Technometrics 1984, 26(2):71–97. 10.1080/00401706.1984.10487928
Montgomery DC: Design and analysis of experiments. John Wiley and Sons, Hoboken; 2009.
Barr RS, Golden BL, Kelly JP, Resende MGC, Stewart WR: Designing and reporting on computational experiments with heuristic methods. J Heuristics 1995, 1(1):9–32. 10.1007/BF02430363
Hennessy JL, Patterson DA: Computer architecture: a quantitative approach. Morgan Kaufmann Publishers, San Francisco; 2006.
Mazouz A, Touati SAA, Barthou D: Analysing the variability of openMP programs performances on multicore architectures. Fourth workshop on programmability issues for heterogeneous multicores (MULTIPROG-2011), 2011. Heraklion, 23 Jan 2011 Heraklion, 23 Jan 2011
Barr RS, Hickman BL: Reporting computational experiments with parallel algorithms: Issues, measures, and experts’ opinions. ORSA J Comput Winter 1993, 5: 2–18. 10.1287/ijoc.5.1.2
Montgomery DC, Runger GC: Applied statistics and probability for engineers. 3rd edn. John Wiley & Sons, Danvers; 2003.
R Development Core Team: R: a language and environment for statistical computing. R Foundation for Statistical Computing, Vienna; 2012. . ISBN 3–900051–07–0 http://www.R-project.org/ . ISBN 3-900051-07-0
Box GEP, Hunter JS, Hunter WG: Statistics for experimenters: design, discovery, and innovation. John Wiley & Sons, Hoboken; 2005.
Kutner MH, Neter J, Nachtsheim CJ, Li W: Applied linear statistical models. 5th edn. The McGraw-Hill/Irwin series operations and decision sciences, McGraw-Hill/Irwin, New York; 2005.
Busemeyer JR, Wang YM: Model comparisons and model selections based on generalization criterion methodology. J Math Psychol 2000, 44(1):171–189. 10.1006/jmps.1999.1282
Daniel C: Use of half-normal plots in interpreting factorial two-level experiments. Technometrics 1959, 1(4):311–341. 10.1080/00401706.1959.10489866
Cantú-Paz E: On random numbers and the performance of genetic algorithms. In Proceedings of the genetic and evolutionary computation conference (GECCO 2002). Morgan Kaufmann Publishers, San Francisco; 2002:311–318.
Fog A: Random number generator libraries. 2008–2010, Instructions for the random number generator libraries on . 2010. http://www.agner.org GNU General Public License. Version 2.01. 2010-08-03. Accessed 15 April 2011.
MPICH2: MPICH-2. 2001.http://www.mcs.anl.gov/mpi/mpich2 Argonne National Laboratory, Lemont. . Accessed 20 May 2011.
Buntinas D, Mercier G, Gropp W: Implementation and evaluation of shared-memory communication and synchronization operations in mpich2 using the nemesis communication subsystem. Parallel Comput 2007, 33(9):634–644. doi:10.1016/j.parco.2007.06.003. Selected papers from EuroPVM/MPI 2006 doi:10.1016/j.parco.2007.06.003. Selected papers from EuroPVM/MPI 2006 10.1016/j.parco.2007.06.003
Balaji P, Buntinas D, Goodell D, Gropp W, Hoefler T, Kumar S, Lusk EL, Thakur R, Träff JL: MPI on millions of cores. Parallel Process Lett (PPL) 2011, 21(1):45–60. 10.1142/S0129626411000060
Fox J, Weisberg S: An R companion to applied regression. Sage, Thousand Oaks; 2011. http://socserv.socsci.mcmaster.ca/jfox/Books/Companion
Zeileis A, Hothorn T: Diagnostic checking in regression relationships. R News 2002, 2(3):7–10. http://CRAN.R-project.org/doc/Rnews/
Táng K, Suganthan PN, Yáng Z, Weise T, Lı̌ X: Benchmark functions for the CEC’2010 special session and competition on large-scale global optimization. Technical report, University of Science and Technology of China (USTC) 2010.
Breusch TS, Pagan AR: A simple test for heteroscedasticity and random coefficient variation. Econometrica: J Econometric Soc 1979, 1287–1294.
Jain R: The art of computer systems performance analysis: techniques for experimental design, measurement, simulation, and modeling. John Wiley & Sons Inc, New York; 1991.
Tukey JW: Exploratory data analysis. Addison–Wesley Publishing Company, Boston; 1977.
Conover WJ, Iman RL: Rank transformations as a bridge between parametric and nonparametric statistics. The American Statistician 1981, 35(3):124–129. doi:10.1080/00031305.1981.10479327. http://amstat.tandfonline.com/doi/abs/10.1080/00031305.1981.10479327 doi:10.1080/00031305.1981.10479327.