Unreliable Heterogeneous Workers in a Pool-Based Evolutionary Algorithm

详细信息    查看全文

• 作者：Mario García-Valdez (15)
  Juan Julián Merelo Guervós (16)
  Francisco Fernández de Vega (17)
  
• 关键词：Distributed evolutionary algorithms ; Cloud computing
• 刊名：Lecture Notes in Computer Science
• 出版年：2014
• 出版时间：2014
• 年：2014
• 卷：1
• 期：1
• 页码：726-737
• 全文大小：415 KB
• 参考文献：1. Alba, E., Nebro, A.J., Troya, J.M.: Heterogeneous Computing and Parallel Genetic Algorithms. Journal of Parallel and Distributed Computing 62(9), 1362-385 (2002) CrossRef
  2. De Jong, K.A., Potter, M.A., Spears, W.M.: Using problem generators to explore the effects of epistasis. In: B?ck, T., (ed.) ICGA, pp. 338-45. Morgan Kaufmann (1997)
  3. De Jong, K.A., Spears, W.M.: An analysis of the interacting roles of population size and crossover in genetic algorithms. In: Proceedings of the 1st Workshop on Parallel Problem Solving from Nature, PPSN I, pp. 38-7. Springer, London (1991)
  4. Di Martino, S., Ferrucci, F., Maggio, V., Sarro, F.: Towards migrating genetic algorithms for test data generation to the cloud. In: Software Testing in the Cloud: Perspectives on an Emerging Discipline., pp. 113-35. IGI Global (2013)
  5. Fazenda, P., McDermott, J., O’Reilly, U.-M.: A library to run evolutionary algorithms in the cloud using MapReduce. In: Di Chio, C., et al. (eds.) EvoApplications 2012. LNCS, vol. 7248, pp. 416-25. Springer, Heidelberg (2012) CrossRef
  6. Feki, M.S., Nguyen, V.H., Garbey, M.: Parallel genetic algorithm implementation for boinc. In: Chapman, B.M., Desprez, F., Joubert, G.R., Lichnewsky, A., Peters, F.J., Priol, T., (eds.) PARCO, vol. 19. Advances in Parallel Computing, pp. 212-19. IOS Press (2009)
  7. Fortin, F.-A., Rainville, F.-M.D., Gardner, M.-A., Parizeau, M., Gagné, C.: DEAP: Evolutionary algorithms made easy. Journal of Machine Learning Research 13, 2171-175 (2012)
  8. García-Valdez, M., Trujillo, L., Fernández de Vega, F., Merelo Guervós, J.J., Olague, G.: EvoSpace: A Distributed Evolutionary Platform Based on the Tuple Space Model. In: Esparcia-Alcázar, A.I. (ed.) EvoApplications 2013. LNCS, vol. 7835, pp. 499-08. Springer, Heidelberg (2013) CrossRef
  9. Gelernter, D.: Generative communication in linda. ACM Trans. Program. Lang. Syst. 7(1), 80-12 (1985) CrossRef
  10. Kennedy, J., Spears, W.: Matching algorithms to problems: an experimental test of the particle swarm and some genetic algorithms on the multimodal problem generator. In: The 1998 IEEE International Conference on Evolutionary Computation Proceedings of the 1998 IEEE World Congress on Computational Intelligence, pp. 78-3 (May 1998)
  11. Merelo-Guervos, J., Castillo, P., Laredo, J.L.J., Mora Garcia, A., Prieto, A.: Asynchronous distributed genetic algorithms with Javascript and JSON. In: IEEE Congress on Evolutionary Computation, CEC 2008 (IEEE World Congress on Computational Intelligence), pp. 1372-379 (June 2008)
  12. Sherry, D., Veeramachaneni, K., McDermott, J., O’Reilly, U.-M.: Flex-GP: genetic programming on the cloud. In: Di Chio, C., et al. (eds.) EvoApplications 2012. LNCS, vol. 7248, pp. 477-86. Springer, Heidelberg (2012) CrossRef
  
• 作者单位：Mario García-Valdez (15)
  Juan Julián Merelo Guervós (16)
  Francisco Fernández de Vega (17)
  
  15. Instituto Tecnológico de Tijuana, Tijuana, BC, Mexico
  16. Universidad de Granada, Granada, Spain
  17. Grupo de Evolución Artificial, Universidad de Extremadura, Mérida, Spain
  
• ISSN：1611-3349

文摘

In this paper the effect of node unavailability in algorithms using EvoSpace, a pool-based evolutionary algorithm, is assessed. EvoSpace is a framework for developing evolutionary algorithms (EAs) using heterogeneous and unreliable resources. It is based on Linda’s tuple space coordination model. The core elements of EvoSpace are a central repository for the evolving population and remote clients, here called EvoWorkers, which pull random samples of the population to perform on them the basic evolutionary processes (selection, variation and survival), once the work is done, the modified sample is pushed back to the central population. To address the problem of unreliable EvoWorkers, EvoSpace uses a simple re-insertion algorithm using copies of samples stored in a global queue which also prevents the starvation of the population pool. Using a benchmark problem from the P-Peaks problem generator we have compared two approaches: (i) the re-insertion of previous individuals at the cost of keeping copies of each sample, and a common approach of other pool based EAs, (ii) inserting randomly generated individuals. We found that EvoSpace is fault tolerant to highly unreliable resources and also that the re-insertion algorithm is only needed when the population is near the point of starvation.