Top

Published in:

2018 | OriginalPaper | Chapter

Predictive Memetic Algorithm (PMA) for Combinatorial Optimization in Dynamic Environments

Authors : Stephen M. Akandwanaho, Serestina Viriri

Published in: Computational Collective Intelligence

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

A prediction mechanism for Memetic Algorithm is presented in this paper. The Predictive Memetic Algorithm (PMA) uses a nonlinear regression method to estimate the parameters used by the algorithm to obtain good solutions in a dynamic and stochastic environment. The algorithm is applied to nonlinear data sets and performance is compared with genetic and simulated annealing algorithms. When compared with the existing methods, the proposed method generates a relatively small error difference after prediction thereby proving its superior performance. A dynamic stochastic environment is used for experimentation, so as to determine the efficacy of the algorithm on non-stationary problem environments.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter A Flexible Evolutionary Algorithm for Task Allocation in Multi-robot Team

next chapter Modeling Competitive Game Players with a Positioning Strategy in the Great Turtle Race

Moscato, P.: On evolution, search, optimization, genetic algorithms and martial arts: towards memetic algorithms. Caltech Concurrent Computation Program, pp. 1–67 (1989)

Cassar, I.R., Titus, N.D.: An improved genetic algorithm for designing optimal temporal patterns of neural stimulation. J. Neural Eng. 14, 1–15 (2017)CrossRef

Forbes, N.: Imitation of Life: How Biology is Inspiring Computing, 1st edn. MIT Press, Cambridge (2004)

Dawkins, R.: Universal Darwinism. In: Bendall, D.S. (ed.) Evolution from Molecules to Man, pp. 2–16. Cambridge University Press, Cambridge (1983)

Dawkins, R.: Memes: The New Replicators, 2nd edn, pp. 188–300. Oxford University Press, Oxford (1989)

Merz, P., Freisleben, B.: Memetic algorithms for the traveling salesman problem. J. Complex Syst. 13, 297–345 (1997)MathSciNetMATH

Ishibuchi, H., Yoshida, T., Murata, T.: Balance between genetic search and local search in memetic algorithms for multiobjective permutation flowshop schedulings. IEEE Trans. Evol. Comput. Jpn. 7, 204–223 (2003)CrossRef

Tang, J., Lim, M.H., Ong, Y.S.: Diversity-adaptive parallel memetic algorithm for solving large scale combinatorial optimization problems. Soft Comput. 11, 873–888 (2007)CrossRef

Ishibuchi, H., Yoshida, T., Murata, T.: Balance between genetic search and local search in memetic algorithms for multiobjective permutation flowshop scheduling. IEEE Trans. Evol. Comput. 2, 204–223 (2003)CrossRef

10.

Alkan, A., Ozcan, E.: Memetic algorithms for timetabling. In: IEEE Proceedings of the 2003 Congress on Evolutionary Computation, vol. 2, pp. 1796–1802 (2003)

11.

Burke, E.K., Newall, J.P.: A multi-stage evolutionary algorithm for the timetable problem. IEEE Trans. Evol. Comput. 3, 1085–1092 (1999)CrossRef

12.

Hatzakis, I., Wallace, D.: Dynamic multi-objective optimization with evolutionary algorithms: a forward-looking approach. In: Keijzer, M. (ed.) Proceedings of the 8th Annual Conference on Genetic and Evolutionary Computation, pp. 1201–1208. ACM (2006)

13.

AbdAllah, A.M.F.M., Essam, D.L., Sarker, R.A.: Solving dynamic optimisation problem with variable dimensions. In: Dick, G., et al. (eds.) SEAL 2014. LNCS, vol. 8886, pp. 1–12. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-13563-2_1CrossRef

14.

Zhou, Z., Ong, Y.S., Lim, M.H.: Memetic algorithm using multi-surrogates for computationally expensive optimization problems. Soft Comput. 11, 957–971 (2007)CrossRef

15.

Mavrovouniotis, M., Yang, S.: A memetic ant colony optimization algorithm for the dynamic travelling salesman problem. Soft Comput. 15, 1405–1425 (2011)CrossRef

16.

William, H., Krasnogor, N., Smith, J.E.: Recent Advances in Memetic Algorithms. Springer, Heidelberg (2005). https://doi.org/10.1007/3-540-32363-5CrossRefMATH

17.

Weiss, G.: Timeweaver: a genetic algorithm for identifying predictive patterns in sequences of events. In: Spector, L. (ed.) Proceedings of the Genetic and Evolutionary Computation Conference, pp. 718–725 (1999)

18.

Fang, K.T., Zhang, J.T.: A new algorithm for calculation of estimates of parameters of nonlinear regression modelings. In: Proceedings of International Conference on Optimization Techniques and Applications, pp. 1–8 (1995)

19.

Rawlings, J.O., Pantula, S.G., Dickey, D.A.: Applied Regression Analysis: A Research Tool. Springer, New York (1998). https://doi.org/10.1007/b98890CrossRefMATH

20.

Zhou, A., Jin, Y., Zhang, Q., Sendhoff, B., Tsang, E.: Prediction-based population re-initialization for evolutionary dynamic multi-objective optimization. In: Obayashi, S., Deb, K., Poloni, C., Hiroyasu, T., Murata, T. (eds.) EMO 2007. LNCS, vol. 4403, pp. 832–846. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-70928-2_62CrossRef

21.

Hemert, J.V., Hoyweghen, C.V., Lukshandl, E., Verbeeck, K.: A futurist approach to dynamic environments. In: Branke, J., Back, T. (eds.) Proceedings for Evolutionary Algorithms for Dynamic Optimization Problems at the Genetic and Evolutionary Computation Conference, pp. 1–10 (2001)

22.

Branke, J.: Evolutionary Optimization in Dynamic Environments, vol. 3. Springer, New York (2002). https://doi.org/10.1007/978-1-4615-0911-0CrossRefMATH

23.

Weicker, K.: Evolutionary algorithms and dynamic optimization problems. Ph.D. thesis. University of Stuttgart, Germany (2003)

24.

Stroud, P.D.: Kalman-extended genetic algorithm for search in nonstationary environments with noisy fitness evaluations. IEEE Trans. Evol. Comput. 5, 66–77 (2001)CrossRef

25.

Karaman, A., Uyar, Ş., Eryiğit, G.: The memory indexing evolutionary algorithm for dynamic environments. In: Rothlauf, F., et al. (eds.) EvoWorkshops 2005. LNCS, vol. 3449, pp. 563–573. Springer, Heidelberg (2005). https://doi.org/10.1007/978-3-540-32003-6_59CrossRef

26.

Bosman, P.A.N., La Poutré, H.: Computationally intelligent online dynamic vehicle routing by explicit load prediction in an evolutionary algorithm. In: Runarsson, T.P., Beyer, H.-G., Burke, E., Merelo-Guervós, J.J., Whitley, L.D., Yao, X. (eds.) PPSN 2006. LNCS, vol. 4193, pp. 312–321. Springer, Heidelberg (2006). https://doi.org/10.1007/11844297_32CrossRef

27.

Simoes, A., Costa, E.: Evaluating predictor’s accuracy in evolutionary algorithms for dynamic environments. In: Proceedings of the 11th Annual Conference on Genetic and Evolutionary Computation, pp. 883–890 (2009)

28.

DeJong, K.: Evolutionary computation: a unified approach. J. Evol. Comput. 164–270 (2006)

29.

Kapanoglua, M., Koca, I.O., Erdogmus, S.: Genetic algorithms in parameter estimation for nonlinear regression models: an experimental approach. J. Stat. Comput. Simul. 77, 851–867 (2007)MathSciNetCrossRef

30.

Vollinger, U., Lehmann, E., Rainer, S.: Using memetic algorithms for the solution of technical problems. Int. Sch. Sci. Res. Innov. 3 (2009)

31.

Bu, Z., Zheng, B.: Perspectives in dynamic optimization evolutionary algorithm. In: Cai, Z., Hu, C., Kang, Z., Liu, Y. (eds.) ISICA 2010. LNCS, vol. 6382, pp. 338–348. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-16493-4_35CrossRef

32.

Wang, H., Wang, D., Yang, S.: A memetic algorithm with adaptive hill climbing strategy for dynamic optimization problems. Soft Comput. 13, 763–780 (2008)CrossRef

33.

KJason, B.: Clever Algorithms: Nature-Inspired Programming Recipes. Lulu Enterprises, Morrisville (2011)

34.

Hart, W.E., Krasnogor, N., Smith, J.E.: Memetic evolutionary algorithms. In: Hart, W.E., Smith, J.E., Krasnogor, N. (eds.) Recent Advances in Memetic Algorithms. Studies in Fuzziness and Soft Computing, vol. 166, pp. 3–27. Springer, Heidelberg (2005). https://doi.org/10.1007/3-540-32363-5_1CrossRefMATH

35.

Gen, M., Cheng, R.: Genetic Algorithms and Engineering Optimization. Wiley, Hoboken (2000)

36.

Eiben, A., Hinterding, R., Michalewicz, Z.: Parameter control in evolutionary algorithms. IEEE Comput. Soc. 124–141 (1999)

37.

Gerdes, I., Klawonn, F., Kruse, R.: Evolutionre Algorithmen. Vieweg Verlag, Wiesbaden (2004)CrossRef

38.

Schneburg, E., Heinzmann, F., Feddersen, S.: Genetische Algorithmen und Evolutionsstrategien. Addison-Wesley, Boston (1994)MATH

39.

Weicker, K.: Evolution are Algorithmen, 1st edn. Teubner Verlag, Wiesbaden (2002)MATH

40.

Seber, G.A.F., Wild, C.J.: Nonlinear Regression. Wiley, Hoboken (2003)MATH

41.

Hongfeng, W., Dingwei, W., Shengxiang, Y.: A memetic algorithm with adaptive hill climbing strategy for dynamic optimization problems. Soft Comput. 13, 763–780 (2009)CrossRef

42.

Weicker, K.: Evolutionary algorithms and dynamic optimization problems. Thesis. University of Stuttgart, Germany (2003)

43.

Simoes, A., Costa, E.: Improving memory’s usage in evolutionary algorithms for changing environments. In: IEEE Congress of Evolutionary Computation, pp. 276–283 (2007)

44.

Smyth, G.K.: Nonlinear regression. Encycl. Environ. 3, 1405–1411 (2002)

45.

Fang, K.T., Zhang, J.T.: A new algorithm for calculation of estimates of parameters of nonlinear regression modellings. Acta Math. Appl. Sin. 16, 366–377 (1993)MATH

46.

National Institute of Standards and Technology: Nonlinear Regression. StRD (2018). Accessed http://www.itl.nist.gov/div898/strd/nls/nls_main.shtml

Title: Predictive Memetic Algorithm (PMA) for Combinatorial Optimization in Dynamic Environments
Authors: Stephen M. Akandwanaho
Serestina Viriri
Publisher: Springer International Publishing
Book: Computational Collective Intelligence
Print ISBN: 978-3-319-98445-2

Electronic ISBN: 978-3-319-98446-9

Copyright Year: 2018
DOI: https://doi.org/10.1007/978-3-319-98446-9_10

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner