Abstract
We study the behavior and performance of island-based multimemetic algorithms, namely memetic algorithms which explicitly represent and evolve memes alongside solutions, in unstable computational environments whose topology is modeled as scale-free networks, a pattern of connectivity observed in real-world networks, such as peer-to-peer systems. We consider the utilization of self-balancing strategies in order to efficiently adjust population sizes to cope with the phenomenon of churn, as well as the dynamic re-wiring of connections in order to deal with connectivity losses caused by node failures. A broad experimental evaluation on different problems and computational scenarios featuring diverse volatility conditions shows that the combination of these two strategies leads to more robust performances, in particular in situations in which churn rates are large.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Alba, E.: Parallel Metaheuristics: A New Class of Algorithms. Wiley-Interscience, Hoboken (2005)
Albert, R., Barabási, A.L.: Statistical mechanics of complex networks. Rev. Mod. Phys. 74(1), 47–97 (2002)
Bronevich, A.G., Meyer, W.: Load balancing algorithms based on gradient methods and their analysis through algebraic graph theory. J. Parallel Distrib. Comput. 68(2), 209–220 (2008)
Deb, K., Goldberg, D.E.: Analyzing deception in trap functions. In: Whitley, L.D. (ed.) Second Workshop on Foundations of Genetic Algorithms, pp. 93–108. Morgan Kaufmann, Vail (1993)
Goldberg, D.E., Deb, K., Horn, J.: Massive multimodality, deception, and genetic algorithms. In: Männer, R., Manderick, B. (eds.) Parallel Problem Solving from Nature - PPSN II, pp. 37–48. Elsevier, Brussels (1992)
Gorges-Schleuter, M.: ASPARAGOS: an asynchronous parallel genetic optimization strategy. In: Schaffer, J.D. (ed.) Third International Conference on Genetic Algorithms, pp. 422–427. Morgan Kaufmann, San Francisco (1989)
Grefenstette, J.: Genetic algorithms for changing environments. In: Männer, R., Manderick, B. (eds.) Parallel Problem Solving from Nature II, pp. 137–144. Elsevier, Brussels (1992)
Hidalgo, J.I., Lanchares, J., Fernández de Vega, F., Lombraña, D.: Is the island model fault tolerant? In: Proceedings of the 9th Annual Conference Companion on Genetic and Evolutionary Computation, GECCO 2007, pp. 2737–2744. ACM, New York, NY, USA (2007)
Holme, P., Kim, B.J.: Growing scale-free networks with tunable clustering. Phys. Rev. E 65, 026107 (2002)
Jelasity, M., van Steen, M.: Large-scale newscast computing on the Internet. Technical report IR-503. Vrije Universiteit Amsterdam, Department of Computer Science, Amsterdam, The Netherlands (October 2002)
Krasnogor, N., Blackburne, B.P., Burke, E.K., Hirst, J.D.: Multimeme algorithms for protein structure prediction. In: Guervós, J.J.M., Adamidis, P.A., Beyer, H.-G., Fernández-Villacañas, J.-L., Schwefel, H.-P. (eds.) PPSN 2002. LNCS, vol. 2439, pp. 769–778. Springer, Heidelberg (2002)
Liu, C., White, R.W., Dumais, S.: Understanding web browsing behaviors through weibull analysis of dwell time. In: Proceedings of the 33rd International ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR 2010, pp. 379–386. ACM, New York, NY, USA (2010)
Lüling, R., Monien, B., Ramme, F.: Load balancing in large networks: a comparative study. In: Third IEEE Symposium on Parallel and Distributed Processing, pp. 686–689. IEEE (December 1991)
Milojičić, D.S., Kalogeraki, V., Lukose, R., Nagaraja, K., Pruyne, J., Richard, B., Rollins, S., Xu, Z.: Peer-to-peer computing. Technical report. HPL-2002-57, Hewlett-Packard Labs (2002)
Neri, F., Cotta, C.: Memetic algorithms and memetic computing optimization: a literature review. Swarm Evol. Comput. 2, 1–14 (2012)
Nogueras, R., Cotta, C.: An analysis of migration strategies in island-based multimemetic algorithms. In: Bartz-Beielstein, T., Branke, J., Filipič, B., Smith, J. (eds.) PPSN 2014. LNCS, vol. 8672, pp. 731–740. Springer, Heidelberg (2014)
Ong, Y.S., Lim, M.H., Chen, X.: Memetic computation-past, present and future. IEEE Comput. Intell. Mag. 5(2), 24–31 (2010)
Sarmenta, L.F.: Bayanihan: web-based volunteer computing using java. In: Masunaga, Y., Katayama, T., Tsukamoto, M. (eds.) WWCA 1998. Lecture Notes in Computer Science, vol. 1368, pp. 444–461. Springer, Berlin Heidelberg (1998)
Smith, J.E.: Self-adaptation in evolutionary algorithms for combinatorial optimisation. In: Cotta, C., Sevaux, M., Sörensen, K. (eds.) Adaptive and Multilevel Metaheuristics, Studies in Computational Intelligence, vol. 136, pp. 31–57. Springer, Heidelberg (2008)
Tanese, R.: Distributed genetic algorithms. In: 3rd International Conference on Genetic Algorithms, pp. 434–439. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA (1989)
Watson, R.A., Hornby, G.S., Pollack, J.B.: Modeling building-block interdependency. In: Eiben, A.E., Bäck, T., Schoenauer, M., Schwefel, H.-P. (eds.) PPSN 1998. LNCS, vol. 1498, pp. 97–106. Springer, Heidelberg (1998)
Zambonelli, F.: Exploiting biased load information in direct-neighbour load balancing policies. Parallel Comput. 25(6), 745–766 (1999)
Acknowledgements
Thanks are due to the reviewers for useful suggestions. This work is partially supported by MICINN project ANYSELF (TIN2011-28627-C04-01), by Junta de Andalucía project P10-TIC-6083 (DNEMESIS) and by Universidad de Málaga, Campus de Excelencia Internacional Andalucía Tech.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
A Test Suite
A Test Suite
Deb’s 4-bit fully deceptive function (TRAP) is defined as \(f_{trap}(s) = 0.6 - 0.2\cdot u(s)\) for \(u(s)<4\) and \(f_{trap}(s) = 1\) for \(u(s)=4\), where \(u(s_1\cdots s_i)=\sum _js_j\) is the number of 1 s in binary string \(s\). A higher-order problem is built by concatenating \(k\) such blocks.
The Hierarchical if-and-only-if (HIFF) function is a recursive epistatic function for binary strings of \(2^k\) bits by means of two auxiliary functions \(f\) and \(t\) defined as
-
\(f(a,b) = 1\) for \(a=b\ne \bullet \) and \(f(a,b)=0\) otherwise.
-
\(t(a,b) = a\) if \(a=b\) and \(t(a,b)=\bullet \) otherwise.
These two functions are used as follows:
where \(b'_i=t(b_{2i-1}, b_{2i})\) and \(\mathrm{HIFF}_0(\cdot ) = 1\).
The basic MMDP block is defined for 6-bit strings as \(f_{mmdp}(s) = 1\) for \(u(s) \in \{0,6\}\), \(f_{mmdp}(s) = 0\) for \(u(s) \in \{1,5\}\), \(f_{mmdp}(s) = 0.360384\) for \(u(s) \in \{2,4\}\) and \(f_{mmdp}(s) = 0.640576\) for \(u(s) =3\). We concatenate \(k\) copies of this basic block to create a harder problem.
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Nogueras, R., Cotta, C. (2015). Self-Balancing Multimemetic Algorithms in Dynamic Scale-Free Networks. In: Mora, A., Squillero, G. (eds) Applications of Evolutionary Computation. EvoApplications 2015. Lecture Notes in Computer Science(), vol 9028. Springer, Cham. https://doi.org/10.1007/978-3-319-16549-3_15
Download citation
DOI: https://doi.org/10.1007/978-3-319-16549-3_15
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-16548-6
Online ISBN: 978-3-319-16549-3
eBook Packages: Computer ScienceComputer Science (R0)