Dynamic optimization facilitated by the memory tree

详细信息    查看全文

• 作者：Tao Zhu (1)
  Wenjian Luo (1)
  Lihua Yue (1)
  
  1. Anhui Province Key Laboratory of Software Engineering in Computing and Communication ; School of Computer Science and Technology ; University of Science and Technology of China ; Hefei聽 ; 230027 ; Anhui ; China
  
• 关键词：Dynamic optimization problem ; Population ; based algorithms ; Memory ; Memory structure ; Binary space partition tree
• 刊名：Soft Computing - A Fusion of Foundations, Methodologies and Applications
• 出版年：2015
• 出版时间：March 2015
• 年：2015
• 卷：19
• 期：3
• 页码：547-566
• 全文大小：1,774 KB
• 参考文献：1. Barlow GJ (2011) Improving memory for optimization and learning in dynamic environments. Doctoral dissertation, Carnegie Mellon University, Pittsburgh
  2. Bendtsen CN, Krink T (2002) Dynamic memory model for non-stationary optimization. In: Proceedings 2002 Congress Evolutionary Computation, pp 145鈥?50
  3. Bird S, Li X (2006) Enhancing the robustness of a speciation-based pso. In: IEEE Congress on Evolutionary Computation, Vancouver, pp 843鈥?50
  4. Bird S, Li X (2007) Using regression to improve local convergence. In: IEEE Congress on Evolutionary Computation 2007
  5. Blackwell T, Branke J (2006) Multiswarms, exclusion, and anti-convergence in dynamic environments. IEEE Trans Evol Comput 10(4):459鈥?72 CrossRef
  6. Bosman (2005) Learning, anticipation and time deception in evolutionary online dynamic optimization. In: GECCO鈥?5, Washington, pp 39鈥?7
  7. Branke J (1999) Memory enhanced evolutionary algorithms for changing optimization problems. In: The 1999 IEEE Congress on Evolutionary Computation, Washington, pp 1875鈥?882
  8. Branke J (2002) Evolutionary optimization in dynamic environments. Kluwer Academic Publishers, Dordrecht CrossRef
  9. Branke J, Kau脽ler T, Schmidt C, Schmeck H (2000) A multi-population approach to dynamic optimization problems
  10. Brest J, Zamuda A, Boskovic B, Maucec MS, Zumer V (2009) Dynamic optimization using self-adaptive differential evolution. In: The 2009 IEEE Congress on Evolutionary Computation, Trondheim, pp 415鈥?22
  11. Cao Y, Luo W (2010) A novel updating strategy for associative memory scheme in cyclic dynamic environments. In: Proceedings of the Third International Workshop on Advanced Computational Intelligence, Suzhou
  12. Cedeno W, Vemuri VR (1997) On the use of niching for dynamic landscapes. In: The 1997 International Conference on Evolutionary Computation, pp 361鈥?66
  13. Chow CK, Yuen SY (2011) An evolutionary algorithm that makes decision based on the entire previous search history. IEEE Trans Evol Comput 15(6):741鈥?69 CrossRef
  14. Chow CK, Yuen SY (2012) A multiobjective evolutionary algorithm that diversifies population by its density. IEEE Trans Evol Comput 16(2):149鈥?72 CrossRef
  15. Clerc M, Kennedy J (2002) The particle swarm鈥攅xplosion, stability, and convergence in a multidimensional complex space. IEEE Trans Evol Comput 6(1):58鈥?3 CrossRef
  16. Cobb HG (1990) An investigation into the use of hypermutation as an adaptive operator in genetic algorithms having continuous, time-dependent nonstationary environments. Technical Report AIC-90-001, Naval Research Laboratory, Washington
  17. Dasgupta D, McGregor DR (1992) Nonstationary function optimization using the structured genetic algorithm
  18. Eberhart R, Kennedy J (1995) New optimizer using particle swarm theory. In: Proceedings of the 1995 6th International Symposium on Micro Machine and Human Science, Nagoya, pp 39鈥?3
  19. Eggermont J, Lenaerts T (2002) Dynamic optimization using evolutionary algorithms with a case-based, memory
  20. Fred G (1989) Tabu search part i. ORSA J Comput 1(3):190鈥?06 CrossRef
  21. Jin Y, Branke J (2005) Evolutionary optimization in uncertain environments鈥攁 survey. IEEE Trans Evol Comput 9(3):303鈥?17
  22. Karaman A, Uyar S, Eryigit G (2005) The memory indexing evolutionary algorithm for dynamic environments. In: Lecture notes in computer science, vol 3449. Heidelberg, D-69121, Germany, pp 563鈥?73
  23. Kennedy J, Mendes R (2002) Population structure and particle swarm performance. In: The 2002 IEEE Congress on Evolutionary Computation, pp 1671鈥?675
  24. Lee SK, Moon BR (2009) Genetic algorithm with adaptive elitism-based immigrants for dynamic optimization problems. In: The 11th Annual conference on Genetic and evolutionary computation, Montreal, pp 1865鈥?866
  25. Li X (2004) Adaptively choosing neighbourhood bests using species in a particle swarm optimizer for multimodal function optimization. In: Proceedings of Genetic and Evolutionary Computation Conference, pp 105鈥?16
  26. Li X, Branke J, Blackwell T (2006) Particle swarm with speciation and adaptation in a dynamic environment. In: Proceedings of the 8th annual conference on Genetic and evolutionary computation
  27. Li C, Yang S, Nguyen TT, Yu EL, Yao X, Jin Y, Beyer HG, Suganthan PN (2008) Benchmark generator for cec 2009 competition on dynamic optimization. Department of Computer Science, University of Leicester, Technical report, UK
  28. Liu L, Yang S, Wang D (2010) Particle swarm optimization with composite particles in dynamic environments. IEEE Trans Syst Man Cybernet Part B 40(6):1634鈥?648 CrossRef
  29. Mostaghim S, Teich J, Tyagi A (2002) Comparison of data structures for storing pareto-sets in moeas. CEC 鈥?2 1:843鈥?48
  30. Nguyen TT, Yang Z, Bonsall S (2012a) Dynamic time-linkage problems鈥攖he challenges. In: 2012 9th IEEE RIVF International Conference on Computing and Communication Technologies, Research, Innovation, and Vision, Ho Chi Minh City
  31. Nguyen TT, Yang S, Branke J (2012b) Evolutionary dynamic optimization: a survey of the state of the art. Swarm Evol Comput 6:1鈥?4 CrossRef
  32. Parrott D, Li X (2006) Locating and tracking multiple dynamic optima by a particle swarm model using speciation. IEEE Trans Evol Comput 10(4):440鈥?58 CrossRef
  33. Ramsey CL, Grefenstette JJ (1993) Case-based initialization of genetic algorithms. In: the 5th International Conference on Genetic Algorithms, pp 84鈥?1
  34. Richter H, Yang S (2009) Learning behavior in abstract memory schemes for dynamic optimization problems. Soft Comput 13(12):1163鈥?173 CrossRef
  35. Salomon R (1996) Re-evaluating genetic algorithm performance under coordinate rotation of benchmark functions. A survey of some theoretical and practical aspects of genetic algorithms. Biosystems 39(3):263鈥?78 CrossRef
  36. Sch眉tze O (2003) A new data structure for the nondominance problem in multi-objective, Optimization
  37. Sim枚es A, Costa E (2007a) Improving memory鈥檚 usage in evolutionary algorithms for changing environments. In: The 2007 IEEE Congress on Evolutionary Computation, Singapore, pp 276鈥?83
  38. Sim枚es A, Costa E (2007b) Variable-size memory evolutionary algorithm to deal with dynamic environments. In: Applications of evolutionary computing, vol. 4448. Springer, Berlin, pp 617鈥?26
  39. Tin贸s R, Yang S (2007) A self-organizing random immigrants genetic algorithm for dynamic optimization problems. Gen Progr Evolv Mach 8(3):255鈥?86 CrossRef
  40. Urbanowicz RJ, Moore JH (2009) Learning classifier systems: a complete introduction, review, and roadmap. J Artif Evol Appl 2009
  41. Ursem RK (2000) Multinational gas: multimodal optimization techniques in dynamic environments. In: The 2000 Genetic and Evolutionary Computation Conference, vol. 1, Riviera Hotel, Las Vegas, pp 19鈥?6
  42. Uyar AS, Harmanci AE (2005) A new population based adaptive domination change mechanism for diploid genetic algorithms in dynamic environments. Soft Comput 9(11):803鈥?14 CrossRef
  43. Vavak F, Fogarty TC, Jukes K (1996) A genetic algorithm with variable range of local search for tracking changing environments. In: Parallel Problem Solving from, Nature, pp 376鈥?85
  44. Vavak F, Jukes K, Fogarty TC (1997) Learning the local search range for genetic optimisation in nonstationary environments. In: IEEE International Conference on Evolutionary Computation, pp 355鈥?60
  45. Yang S (2003) Non-stationary problem optimization using the primal-dual genetic algorithm. In: the 2003 IEEE Congress On Evolutionary Computation, vol 3, pp 2246鈥?253
  46. Yang S (2005) Memory-based immigrants for genetic algorithms in dynamic environments. In: The 2005 Genetic and Evolutionary Computation Conference, vol 2, Washington, pp 1115鈥?122
  47. Yang S (2007) Genetic algorithms with elitism-based immigrants for chaning optimization problems. In: EvoWorkshops 2007: applications of evolutionary, computing, vol 4448, pp 627鈥?36
  48. Yang S, Tin贸s R (2007) A hybrid immigrants scheme for genetic algorithms in dynamic environments. Intern J Autom Comput 4(3):243鈥?54 CrossRef
  49. Yang S (2008) Genetic algorithms with memory- and elitism-based immigrants in dynamic environments. Evol Comput 16(3):385鈥?16 CrossRef
  50. Yang S, Yao X (2008) Population-based incremental learning with associative memory for dynamic environments. IEEE Trans Evol Comput 12(5):542鈥?61 CrossRef
  51. Yang S, Li C (2010) A clustering particle swarm optimizer for locating and tracking multiple optima in dynamic environments. IEEE Trans Evol Comput 14(6):959鈥?74 CrossRef
  52. Yu EL, Suganthan PN (2009) Evolutionary programming with ensemble of explicit memories for dynamic optimization. In: The 2009 IEEE Congress on Evolutionary Computation, Trondheim, pp 431鈥?38
  53. Yuen SY, Chow CK (2009) A genetic algorithm that adaptively mutates and never revisits. IEEE Trans Evol Comput 13(2):454鈥?72 CrossRef
  54. Zhu T, Luo W, Li Z (2011) An adaptive strategy for updating the memory in evolutionary algorithms for dynamic optimization. In: Proceedings of the 2011 IEEE Symposium on Computational Intelligence in Dynamic and Uncertain Environments, Paris
  
• 刊物类别：Engineering
• 刊物主题：Numerical and Computational Methods in Engineering
  Theory of Computation
  Computing Methodologies
  Mathematical Logic and Foundations
  Control Engineering
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1433-7479

文摘

Memorizing the past information for later environments is an effective and widely employed approach to optimize dynamic problems. Although the existing explicit memories for dynamic optimization differ widely in the literature, all of them organize memory entries in a linear list. This naive structure leads to problems, such as heavy computational overhead and small memory capacity, and thus restricts the performance of the memories. In this paper, the binary space partition tree is adopted to organize the memory entries, and then a memory tree is constructed. The memory tree partitions the search space into regions. In order to make use of the memory tree, a neighbor shift strategy is proposed. When a new individual is generated in a region that has never been visited since the last change, the new individual is shifted to the neighboring memory individual of that region, if it is less fit than the memory individual. The proposed approach can be easily combined with many population-based algorithms for dynamic optimization in the real space. As examples, the proposed approach was combined with a basic particle swarm optimizer and two state-of-the-art dynamic optimizers. The experimental results showed that it significantly enhanced the performance of the three optimizers on various test problems. The proposed approach demonstrates the importance of memory structure in memory approaches.