A particle swarm optimization based memetic algorithm for dynamic optimization problems. (English) Zbl 1205.68498
Summary: Recently, there has been an increasing concern from the evolutionary computation community on dynamic optimization problems since many real-world optimization problems are dynamic. This paper investigates a Particle Swarm Optimization (PSO) based memetic algorithm that hybridizes PSO with a local search technique for dynamic optimization problems. Within the framework of the proposed algorithm, a local version of PSO with a ring-shape topology structure is used as the global search operator and a fuzzy cognition local search method is proposed as the local search technique. In addition, a self-organized random immigrants scheme is extended into our proposed algorithm in order to further enhance its exploration capacity for new peaks in the search space. Experimental study over the moving peaks benchmark problem shows that the proposed PSO-based memetic algorithm is robust and adaptable in dynamic environments.
MSC:
| 68W05 | Nonnumerical algorithms |
| 68T05 | Learning and adaptive systems in artificial intelligence |
| 90C39 | Dynamic programming |
Keywords:
particle swarm optimization; memetic algorithm; dynamic optimization problem; self-organized random immigrants; Fuzzy cognition local searchReferences:
| [1] | Blackwell TM, Bentley P (2002) Dynamic search with charged swarms. In: Proceedings of the 2002 genetic and evolutionary computation conference, pp 19–26 |
| [2] | Blackwell TM, Branke J (2006) Multiswarms, exclusion, and anti-convergence in dynamic environments. IEEE Trans Evol Comput 10(4):459–472 · doi:10.1109/TEVC.2005.857074 |
| [3] | Branke J. The moving peaks benchmark website. Online: http://www.aifb.unikarl-sruhe.de/jbr/MovPeaks |
| [4] | Branke J (1999) Memory enhanced evolutionary algorithms for changing optimization problems. In: Proceedings of the 1999 congress on evolutionary computation, pp 1875–1882 |
| [5] | Branke J, Kaubler T, Schmidt C, Schmeck H (2000) A multi-population approach to dynamic optimization problems. In: Proceedings of the 4th international conference on adaptive computing in design and manufacturing, pp 299–308 |
| [6] | Carlisle A, Dozier G (2000) Adapting particle swarm optimization to dynamic environments. In: Proceedings of the 2000 international conference on artificial intelligence, pp 429–434 |
| [7] | Cobb HG (1990) An investigation into the use of hypermutation as an adaptive operator in genetic algorithms having continuous, time-dependent nonstationary environment. Technical report AIC-90-001, Naval Research Laboratory, Washington |
| [8] | Eberhart RC, Shi Y (2001) Tracking and optimizing dynamic systems with particle swarms. In: Proceedings of the 2001 IEEE congress on evolutionary computation, pp 94–97 |
| [9] | Gallardo JE, Cotta C, Ferandez AJ (2007) On the hybridization of memetic algorithms with branch-and-bound techniques. IEEE Trans Syst Man Cybern B 37(1):77–83 · doi:10.1109/TSMCB.2006.883266 |
| [10] | Goh CK, Tan KC (2009) A competitive-cooperation coevolutionary paradigm for dynamic multi-objective optimization. IEEE Trans Evol Comput 13(1):103–127 · doi:10.1109/TEVC.2008.920671 |
| [11] | Grefenstette JJ (1992) Genetic algorithms for changing environments. In: Proceedings of the 2nd international conference on parallel problem solving from nature, pp 137–144 |
| [12] | Hatzakis I, Wallace D (2006) Dynamic multi-objective optimization with evolutionary algorithms: a forward-looking approach. In: Proceedings of the 2006 genetic and evolutionary computation conference, pp 1201–1208 |
| [13] | Hu X, Eberhart R (2002) Adaptive particle swarm optimization: detection and response to dynamic systems. In: Proceedings of the 2002 IEEE congress on evolutionary computation, pp 1666–1670 |
| [14] | Ishibuchi H, Yoshida T, Murata T (2003) Balance between genetic search and local search in memetic algorithms for multiobjective permutation flowshop scheduling. IEEE Trans Evol Comput 7(2):204–223 · doi:10.1109/TEVC.2003.810752 |
| [15] | Janson S, Middendorf M (2006) A hierarchical particle swarm optimizer for noisy and dynamic environments. Genet Program Evolvable Mach 7(3):329–354 · doi:10.1007/s10710-006-9014-6 |
| [16] | Jin Y, Branke J (2005) Evolutionary pptimization in uncertain environments–a survey. IEEE Trans Evol Comput 9(3): 303–317 · doi:10.1109/TEVC.2005.846356 |
| [17] | Kennedy J (1997) The particle swarm: social adaptation of knowledge. In: Proceedings of the IEEE international conference on evolutionary computation, pp 303–308 |
| [18] | Krasnogor N, Smith JE (2005) A tutorial for competent memetic algorithms: model, taxonomy and design issues. IEEE Trans Evol Comput 9(5):474–488 · doi:10.1109/TEVC.2005.850260 |
| [19] | Li X, Dam KH (2003) Comparing particles swarms for tracking extrema in dynamic environments. In: Proceedings of the IEEE 2003 congress on evolutionary computation, pp 1772–1779 |
| [20] | Liu D, Tan KC, Goh CK, Ho WK (2007a) A multiobjective memetic algorithm based on particle swarm optimization. IEEE Trans Syst Man Cybern B 37(1):42–50 · doi:10.1109/TSMCB.2006.883270 |
| [21] | Liu B, Wang L, Jin YH (2007b) An effective PSO-based memetic algorithm for flow shop scheduling. IEEE Trans Syst Man Cybern B 37(1):18–27 · doi:10.1109/TSMCB.2006.883272 |
| [22] | Liu L, Yang S, Wang D (2008) Compound particle swarm optimization in dynamic environments. In: Proceedins of the evoworkshops 2008, pp 616–625 |
| [23] | Man S, Liang Y, Leung KS, Lee KH, Mok TSK (2007) A memetic algorithm for multiple-drug cancer chemotherapy schedule optimization. IEEE Trans Syst Man Cybern B 37(1):84–91 · doi:10.1109/TSMCB.2006.883265 |
| [24] | 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–458 · doi:10.1109/TEVC.2005.859468 |
| [25] | Petalas YG, Parsopoulos KE, Vrahatis MN (2007) Memetic particle swarm optimization. Ann Oper Res 156:99–127 · Zbl 1145.90108 · doi:10.1007/s10479-007-0224-y |
| [26] | Smith JE (2007) Coevolving memetic algorithms: a review and progress report. IEEE Trans SMC B 37(1):6–17 |
| [27] | Tang M, Yao X (2007) A memetic algorithm for VLSI floorplanning. IEEE Trans Syst Man Cybern B 37(1):62–69 · doi:10.1109/TSMCB.2006.883268 |
| [28] | Tang J, Lim MH, Ong Y-S (2007) Diversity-adaptive parallel memetic algorithm for solving large scale combinatorial optimization problems. Soft Comput 11(10):957–971 · doi:10.1007/s00500-006-0139-6 |
| [29] | Tinos R, Yang S (2007) A self-organizing random immigrants genetic algorithm for dynamic optimization problems. Genet Program Evolvable Mach 8(3):255–286 · doi:10.1007/s10710-007-9024-z |
| [30] | Uyar AS, Harmanci AE (2005) A new population based adaptive dominance change mechanism for diploid genetic algorithms in dynamic environments. Soft Comput 9(11):803–815 · Zbl 1084.68896 · doi:10.1007/s00500-004-0421-4 |
| [31] | van den Bergh F (2002) An analysis of particle swarm optimizers. PhD thesis, University of Pretoria, South Africa |
| [32] | Wang H, Wang D (2006) An improved primal-dual genetic algorithm for optimization in dynamic environments. In: Proceedings of the 13th international conference on neural information processing, part III, pp 836–844 |
| [33] | Wang H, Wang D, Yang S (2007) Triggered memory-based swarm optimization in dynamic environments. In: Proceedings of the evoworkshop 2007, pp 637–646 |
| [34] | Wang H, Yang S, Ip WH, Wang D (2009a) Adaptive primal-dual genetic algorithms in dynamic environments. IEEE Trans Syst Man Cybern B 39(6):1348–1361 · doi:10.1109/TSMCB.2009.2015281 |
| [35] | Wang H, Yang S, Wang D (2009b) A memetic algorithm with adaptive hill climbing strategy for dynamic optimization problems. Soft Comput 13(8–9):763–780 · doi:10.1007/s00500-008-0347-3 |
| [36] | Yang S (2003) Non-stationary problem optimization using the primal-dual genetic algorithm. In: Proceedingds of the 2003 congress on evolutionary computation, vol 3, pp 2246–2253 |
| [37] | Yang S (2008) Genetic algorithms with memory and elitism based immigrants in dynamic environments. Evol Comput 16(3):385–416 · doi:10.1162/evco.2008.16.3.385 |
| [38] | Yang S, Yao X (2005) Experimental study on population-based incremental learning algorithms for dynamic optimization problems. Soft Comput 9(11):815–834 · Zbl 1086.68596 · doi:10.1007/s00500-004-0422-3 |
| [39] | Yang S, Yao X (2008) Population-based incremental learning with associative memory for dynamic environments. IEEE Trans Evol Comput 12(5):542–561 · doi:10.1109/TEVC.2007.913070 |
| [40] | Yang S, Ong Y-S, Jin Y (eds) (2007) Evolutionary computation in dynamic and uncertain environments. Springer, Berlin · Zbl 1139.68048 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
