nach oben

Erschienen in:

2020 | OriginalPaper | Buchkapitel

COEBA: A Coevolutionary Bat Algorithm for Discrete Evolutionary Multitasking

verfasst von : Eneko Osaba, Javier Del Ser, Xin-She Yang, Andres Iglesias, Akemi Galvez

Erschienen in: Computational Science – ICCS 2020

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Multitasking optimization is an emerging research field which has attracted lot of attention in the scientific community. The main purpose of this paradigm is how to solve multiple optimization problems or tasks simultaneously by conducting a single search process. The main catalyst for reaching this objective is to exploit possible synergies and complementarities among the tasks to be optimized, helping each other by virtue of the transfer of knowledge among them (thereby being referred to as Transfer Optimization). In this context, Evolutionary Multitasking addresses Transfer Optimization problems by resorting to concepts from Evolutionary Computation for simultaneous solving the tasks at hand. This work contributes to this trend by proposing a novel algorithmic scheme for dealing with multitasking environments. The proposed approach, coined as Coevolutionary Bat Algorithm, finds its inspiration in concepts from both co-evolutionary strategies and the metaheuristic Bat Algorithm. We compare the performance of our proposed method with that of its Multifactorial Evolutionary Algorithm counterpart over 15 different multitasking setups, composed by eight reference instances of the discrete Traveling Salesman Problem. The experimentation and results stemming therefrom support the main hypothesis of this study: the proposed Coevolutionary Bat Algorithm is a promising meta-heuristic for solving Evolutionary Multitasking scenarios.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

Vorheriges Kapitel Ant Colony Optimization Implementation for Reversible Synthesis in Walsh-Hadamard Domain

Nächstes Kapitel Convex Polygon Packing Based Meshing Algorithm for Modeling of Rock and Porous Media

Bäck, T., Fogel, D.B., Michalewicz, Z.: Handbook of Evolutionary Computation. CRC Press (1997)

Bali, K.K., Ong, Y.S., Gupta, A., Tan, P.S.: Multifactorial evolutionary algorithm with online transfer parameter estimation: MFEA-II. IEEE Trans. Evol. Comput. 24(1), 69–83 (2020)CrossRef

Bellmore, M., Nemhauser, G.L.: The traveling salesman problem: a survey. Oper. Res. 16(3), 538–558 (1968)MathSciNetCrossRef

Caruana, R.: Multitask learning. Mach. Learn. 28(1), 41–75 (1997)MathSciNetCrossRef

Cheng, M.Y., Gupta, A., Ong, Y.S., Ni, Z.W.: Coevolutionary multitasking for concurrent global optimization: with case studies in complex engineering design. Eng. Appl. Artif. Intell. 64, 13–24 (2017)CrossRef

Da, B., et al.: Evolutionary multitasking for single-objective continuous optimization: benchmark problems, performance metric, and baseline results. arXiv preprint arXiv:1706.03470 (2017)

Davis, L.: Job shop scheduling with genetic algorithms. In: International Conference on Genetic Algorithms and their Applications, vol. 140 (1985)

Ser, J., et al.: Bio-inspired computation: where we stand and what’s next. Swarm Evol. Comput. 48, 220–250 (2019)CrossRef

Dorigo, M., Gambardella, L.M.: Ant colony system: a cooperative learning approach to the traveling salesman problem. IEEE Trans. Evol. Comput. 1(1), 53–66 (1997)CrossRef

10.

Feng, L., et al.: An empirical study of multifactorial PSO and multifactorial DE. In: IEEE Congress on Evolutionary Computation, pp. 921–928 (2017)

11.

Feng, L., Ong, Y.S., Tan, A.H., Tsang, I.W.: Memes as building blocks: a case study on evolutionary optimization+ transfer learning for routing problems. Memetic Comput. 7(3), 159–180 (2015)CrossRef

12.

Fister Jr., I., Yang, X.S., Fister, I., Brest, J., Fister, D.: A brief review of nature-inspired algorithms for optimization/kratki pregled algoritmov po vzoru iz narave za optimizacijo. Elektrotehniski Vestnik 80(3), 116 (2013)

13.

Gendreau, M., Laporte, G., Semet, F.: A tabu search heuristic for the undirected selective travelling salesman problem. Eur. J. Oper. Res. 106(2), 539–545 (1998)CrossRef

14.

Gong, M., Tang, Z., Li, H., Zhang, J.: Evolutionary multitasking with dynamic resource allocating strategy. IEEE Trans. Evol. Comput. 23(5), 858–869 (2019)CrossRef

15.

Grefenstette, J., Gopal, R., Rosmaita, B., Van Gucht, D.: Genetic algorithms for the traveling salesman problem. In: Proceedings of the first International Conference on Genetic Algorithms and their Applications, pp. 160–168. Lawrence Erlbaum, New Jersey (1985)

16.

Gupta, A., Ong, Y.S.: Genetic transfer or population diversification? Deciphering the secret ingredients of evolutionary multitask optimization. In: IEEE Symposium Series on Computational Intelligence, pp. 1–7 (2016)

17.

Gupta, A., Ong, Y.S., Feng, L.: Multifactorial evolution: toward evolutionary multitasking. IEEE Trans. Evol. Comput. 20(3), 343–357 (2015)CrossRef

18.

Gupta, A., Ong, Y.S., Feng, L., Tan, K.C.: Multiobjective multifactorial optimization in evolutionary multitasking. IEEE Trans. Cybern. 47(7), 1652–1665 (2016)CrossRef

19.

Ibrahim, S., Thangamani, M.: Enhanced singular value decomposition for prediction of drugs and diseases with hepatocellular carcinoma based on multi-source bat algorithm based random walk. Measurement 141, 176–183 (2019)CrossRef

20.

Kumbharana, S.N., Pandey, G.M.: Solving travelling salesman problem using firefly algorithm. Int. J. Res. Sci. Adv. Technol. 2(2), 53–57 (2013)

21.

Lawler, E.L., Lenstra, J.K., Kan, A.R., Shmoys, D.B.: The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization. Wiley, New York (1985)MATH

22.

Li, G., Zhang, Q., Gao, W.: Multipopulation evolution framework for multifactorial optimization. In: Genetic and Evolutionary Computation Conference Companion, pp. 215–216 (2018)

23.

Lin, S.: Computer solutions of the traveling salesman problem. Bell Syst. Tech. J. 44(10), 2245–2269 (1965)MathSciNetCrossRef

24.

Lu, Y., Jiang, T.: Bi-population based discrete bat algorithm for the low-carbon job shop scheduling problem. IEEE Access 7, 14513–14522 (2019)CrossRef

25.

Luque, G., Alba, E.: Parallel Genetic Algorithms: Theory and Real World Applications, vol. 367. Springer, Heidelberg (2011)CrossRef

26.

Miller, C.E., Tucker, A.W., Zemlin, R.A.: Integer programming formulation of traveling salesman problems. J. ACM 7(4), 326–329 (1960)MathSciNetCrossRef

27.

Ong, Y.-S.: Towards evolutionary multitasking: a new paradigm in evolutionary computation. In: Senthilkumar, M., Ramasamy, V., Sheen, S., Veeramani, C., Bonato, A., Batten, L. (eds.) Computational Intelligence, Cyber Security and Computational Models. AISC, vol. 412, pp. 25–26. Springer, Singapore (2016). https://doi.org/10.1007/978-981-10-0251-9_3CrossRef

28.

Ong, Y.S., Gupta, A.: Evolutionary multitasking: a computer science view of cognitive multitasking. Cogn. Comput. 8(2), 125–142 (2016)CrossRef

29.

Osaba, E., Carballedo, R., Diaz, F., Onieva, E., Masegosa, A., Perallos, A.: Good practice proposal for the implementation, presentation, and comparison of metaheuristics for solving routing problems. Neurocomputing 271, 2–8 (2018)CrossRef

30.

Osaba, E., Del Ser, J., Sadollah, A., Bilbao, M.N., Camacho, D.: A discrete water cycle algorithm for solving the symmetric and asymmetric traveling salesman problem. Appl. Soft Comput. 71, 277–290 (2018)CrossRef

31.

Osaba, E., Yang, X.S., Diaz, F., Lopez-Garcia, P., Carballedo, R.: An improved discrete bat algorithm for symmetric and asymmetric traveling salesman problems. Eng. Appl. Artif. Intell. 48, 59–71 (2016)CrossRef

32.

Osaba, E., Yang, X.S., Fister Jr., I., Del Ser, J., Lopez-Garcia, P., Vazquez-Pardavila, A.J.: A discrete and improved bat algorithm for solving a medical goods distribution problem with pharmacological waste collection. Swarm Evol. Comput. 44, 273–286 (2019)CrossRef

33.

Ouaarab, A., Ahiod, B., Yang, X.: Discrete cuckoo search algorithm for the travelling salesman problem. Neural Comput. Appl. 24, 1659–1669 (2013). https://doi.org/10.1007/s00521-013-1402-2CrossRef

34.

Pan, S.J., Yang, Q.: A survey on transfer learning. IEEE Trans. Knowl. Data Eng. 22(10), 1345–1359 (2009)CrossRef

35.

Precup, R.E., David, R.C.: Nature-Inspired Optimization Algorithms for Fuzzy Controlled Servo Systems. Butterworth-Heinemann (2019)

36.

Reinelt, G.: TSPLIB: a traveling salesman problem library. ORSA J. Comput. 3(4), 376–384 (1991)CrossRef

37.

Song, H., Qin, A., Tsai, P.W., Liang, J.: Multitasking multi-swarm optimization. In: IEEE Congress on Evolutionary Computation, pp. 1937–1944 (2019)

38.

Wang, C., Ma, H., Chen, G., Hartmann, S.: Evolutionary multitasking for semantic web service composition. arXiv preprint arXiv:1902.06370 (2019)

39.

Wen, Y.W., Ting, C.K.: Parting ways and reallocating resources in evolutionary multitasking. In: IEEE Congress on Evolutionary Computation, pp. 2404–2411 (2017)

40.

Xiao, H., Yokoya, G., Hatanaka, T.: Multifactorial PSO-FA hybrid algorithm for multiple car design benchmark. In: IEEE International Conference on Systems, Man and Cybernetics, pp. 1926–1931 (2019)

41.

Yang, X.S.: A new metaheuristic bat-inspired algorithm. In: González, J.R., Pelta, D.A., Cruz, C., Terrazas, G., Krasnogor, N. (eds.) Nature Inspired Cooperative Strategies for Optimization (NICSO 2010). Studies in Computational Intelligence, vol 284. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-12538-6_6

42.

Yang, X.S., He, X.: Bat algorithm: literature review and applications. Int. J. Bio-Inspired Comput. 5(3), 141–149 (2013)CrossRef

43.

Yu, Y., Zhu, A., Zhu, Z., Lin, Q., Yin, J., Ma, X.: Multifactorial differential evolution with opposition-based learning for multi-tasking optimization. In: IEEE Congress on Evolutionary Computation, pp. 1898–1905 (2019)

44.

Yuan, Y., Ong, Y.S., Gupta, A., Tan, P.S., Xu, H.: Evolutionary multitasking in permutation-based combinatorial optimization problems: realization with TSP, QAP, LOP, and JSP. In: IEEE Region 10 Conference, pp. 3157–3164 (2016)

45.

Zheng, X., Lei, Y., Gong, M., Tang, Z.: Multifactorial brain storm optimization algorithm. In: Gong, M., Pan, L., Song, T., Zhang, G. (eds.) BIC-TA 2016. CCIS, vol. 682, pp. 47–53. Springer, Singapore (2016). https://doi.org/10.1007/978-981-10-3614-9_6CrossRef

46.

Zhou, L., et al.: Towards effective mutation for knowledge transfer in multifactorial differential evolution. In: IEEE Congress on Evolutionary Computation, pp. 1541–1547 (2019)

47.

Zhou, L., Feng, L., Zhong, J., Ong, Y.S., Zhu, Z., Sha, E.: Evolutionary multitasking in combinatorial search spaces: a case study in capacitated vehicle routing problem. In: IEEE Symposium on Computational Intelligence, pp. 1–8 (2016)

Titel: COEBA: A Coevolutionary Bat Algorithm for Discrete Evolutionary Multitasking
verfasst von: Eneko Osaba
Javier Del Ser
Xin-She Yang
Andres Iglesias
Akemi Galvez
Verlag: Springer International Publishing
Buch: Computational Science – ICCS 2020
Print ISBN: 978-3-030-50425-0

Electronic ISBN: 978-3-030-50426-7

Copyright-Jahr: 2020
DOI: https://doi.org/10.1007/978-3-030-50426-7_19

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"