Abstract
Metameric problems are variable-length optimization problems whose representations take on an at least partially segmented structure. This is referred to as a metameric representation. Frequently, each of these segments defines one of a number of analogous components in the solution. Examples include the nodes in a coverage network or turbines in a wind farm. Locating optimal solutions requires, in part, determining the optimal number of components. Evolutionary algorithms can be applied but require modifications to the traditional fixed-length operators. This study proposes a new selection operator for metameric problems: length niching selection. First, the population is partitioned into several niches based on solution length. A window function determines at which lengths a niche is formed. Local selection is then applied within each niche independently, resulting in a new parent population formed by a diverse set of solution lengths. A coverage and a wind farm problem are used to demonstrate the effectiveness of the new operator.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Notes
This work is adapted from the doctoral dissertation submitted by the primary author to Michigan State University (Ryerkerk 2018).
Source code is available at: https://github.com/ryerkerk/metameric.
References
Abdollahzadeh S, Navimipour NJ (2016) Deployment strategies in the wireless sensor network: a comprehensive review. Comput Commun 91–92:1–16
Bacardit J, Garrell JM (2007) Bloat control and generalization pressure using the minimum description length principle for a Pittsburgh approach learning classifier system. In: Kovacs T, Llorà X, Takadama K, Lanzi PL, Stolzmann W, Wilson SW (eds) Learning classifier systems, revised selected papers of the international workshop on learning classifier systems 2003–2005, vol 4399. Lecture notes in computer science. Springer, Berlin, pp 59–79
Bandyopadhyay S, Murthy CA, Pal SK (2000) VGA-classifier: design and applications. IEEE Trans Syst Man Cybern B Cybern 30(6):890–895
Bassett JK, De Jong KA (2000) Evolving behaviors for cooperating agents. In: Proceedings of the 12th international symposium on methodologies of intelligent systems (ISMIS). Springer, Berlin, pp 157–165
Cerrone C, Cerulli R, Gaudioso M (2016) Omega one multi ethnic genetic approach. Optim Lett 10(2):309–324
Chang CS, Sim SS (1997) Optimising train movements through coast control using genetic algorithms. IEE Proc-Electr Power Appl 144(1):65–73
Chen Y, Mahalec V, Chen Y, Liu X, He R, Sun K (2015) Reconfiguration of satellite orbit for cooperative observation using variable-size multi-objective differential evolution. Eur J Oper Res 242(1):10–20
Cussat-Blanc S, Harrington K, Pollack J (2015) Gene regulatory network evolution through augmenting topologies. IEEE Trans Evol Comput 19(6):823–837
Dinh HQ, Aubert N, Noman N, Fujii T, Rondelez Y, Iba H (2015) An effective method for evolving reaction networks in synthetic biochemical systems. IEEE Trans Evol Comput 19(3):374–386
Eiben AE, Smith JE (2003) Introduction to evolutionary computing. Springer, Berlin
Fei Z, Li B, Yang S, Xing C, Chen H, Hanzo L (2017) A survey of multi-objective optimization in wireless sensor networks: metrics, algorithms and open problems. IEEE Commun Surv Tutor 19(1):550–586
González JS, Payán MB, Riquelme-Santos JM (2012) Optimization of wind farm turbine layout including decision making under risk. IEEE Syst J 6(1):94–102
González JS, Payán MB, Riquelme-Santos JM, González-Longatt F (2014) A review and recent developments in the optimal wind-turbine micro-siting problem. Renew Sustain Energy Rev 30:133–144
Grady SA, Hussaini MY, Abdullah MM (2005) Placement of wind turbines using genetic algorithms. Renew Energy 30(2):259–270
Grimbleby JB (2000) Automatic analogue circuit synthesis using genetic algorithms. IEE Proc-Circuit Devices Syst 147(6):319–323
Herbert-Acero JF, Probst O, Réthoré PE, Larsen GC, Castillo-Villar KK (2014) A review of methodological approaches for the design and optimization of wind farms. Energies 7(11):6930–7016
Jensen NO (1983) A note on wind generator interaction. Tech. rep. Riso-M-2411, Risø National Laboratory, Roskilde
Jourdan DB, de Weck OL (2004) Multi-objective genetic algorithm for the automated planning of a wireless sensor network to monitor a critical facility. In: Proceedings of SPIE on sensors, and command, control, communications, and intelligence (C3I) technologies for homeland security and homeland defense III, vol 5403, pp 565–575
Katic I, Højstrup J, Jensen NO (1987) A simple model for cluster efficiency. In: Proceedings of the European wind energy association conference and exhibition (EWEC), A. Raguzzi, pp 407–410
Keller D (2011) Global laminate optimization on geometrically partitioned shell structures. Struct Multidiscip Optim 43(3):353–368
Khan SA, Rehman S (2013) Iterative non-deterministic algorithms in on-shore wind farm design: a brief survey. Renew Sustain Energy Rev 19:370–384
Lakshmi K, Rama Mohan Rao A (2013) Multi-objective optimal design of laminated composite skirt using hybrid NSGA. Meccanica 48(6):1431–1450
Le Riche R, Haftka RT (1995) Improved genetic algorithm for minimum thickness composite laminate design. Compos Eng 5(2):143–161
Luna F, Durillo JJ, Nebro AJ, Alba E (2010) Evolutionary algorithms for solving the automatic cell planning problem: a survey. Eng Optim 42(7):671–690
Manos S, Large M, Poladian L (2007) Evolutionary design of single-mode microstructured polymer optical fibres using an artificial embryogeny representation. In: Proceedings of the 9th annual conference companion on genetic and evolutionary computation (GECCO). ACM, pp 2549–2556
Molina G, Alba E, Talbi EG (2008) Optimal sensor network layout using multi-objective metaheuristics. J Univers Comput Sci 14(15):2549–2565
Mosetti G, Poloni C, Diviacco B (1994) Optimization of wind turbine positioning in large windfarms by means of a genetic algorithm. J Wind Eng Ind Aerodyn 51(1):105–116
Palmes P, Hayasaka T, Usui S (2005) Mutation-based genetic neural network. IEEE Trans Neural Netw 16(3):587–600
Poli R, Langdon WB, McPhee NF, Koza JR (2008) A field guide to genetic programming. Lulu Enterprises, London
Ryerkerk ML (2018) Metameric representations in evolutionary algorithms. PhD dissertation, Michigan State University, East Lansing
Ryerkerk ML, Averill RC, Deb K, Goodman ED (2017) Solving metameric variable-length optimization problems using genetic algorithms. Genet Program Evolvable Mach 18(2):247–277
Ryerkerk ML, Averill RC, Deb K, Goodman ED (2019) A survey of evolutionary algorithms using metameric representations. Genet Program Evolvable Mach 20(4):441–478
Stanley KO (2007) Compositional pattern producing networks: a novel abstraction of development. Genet Program Evolvable Mach 8(2):131–162
Stanley KO, Miikkulainen R (2002) Evolving neural networks through augmenting topologies. Evol Comput 10(2):99–127
Stanley KO, D’Ambrosio DB, Gauci J (2009) A hypercube-based encoding for evolving large-scale neural networks. Artif Life 15(2):185–212
Sun Y, Xue B, Zhang M (2017) Evolving deep convolutional neural networks for image classification. ArXiv:1710.10741
Ting CK, Lee CN, Chang HC, Wu JS (2009) Wireless heterogeneous transmitter placement using multiobjective variable-length genetic algorithm. IEEE Trans Syst Man Cybern B Cybern 39(4):945–958
Whitley D, Starkweather T, Bogart C (1990) Genetic algorithms and neural networks: optimizing connections and connectivity. Parallel Comput 14(3):347–361
Whitley D, Rana S, Heckendorn RB (1999) The island model genetic algorithm: on separability, population size and convergence. J Comput Inf Technol 7(1):33–47
Wu AS, Schultz AC, Agah A (1999) Evolving control for distributed micro air vehicles. In: Proceedings of the 1999 IEEE international symposium on computational intelligence in robotics and automation (CIRA), IEEE, pp 174–179
Acknowledgements
This material is based in part upon work supported by the National Science Foundation under Cooperative Agreement No. DBI-0939454 to BEACON Center for the Study of Evolution in Action. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation. This research was developed with funding from the Defense Advanced Research Projects Agency (DARPA). The views, opinions, and/or findings expressed are those of the author and should not be interpreted as representing the official views or policies of the Department of Defense or the U.S. Government. This work was supported in part by Michigan State University through computational resources provided by the Institute for Cyber-Enabled Research.
Author information
Authors and Affiliations
Corresponding author
Ethics declarations
Conflict of interest
The authors declare that they have no conflict of interest.
Ethical approval
This article does not contain any studies with human participants or animals performed by any of the authors.
Additional information
Communicated by V. Loia.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Ryerkerk, M., Averill, R., Deb, K. et al. A novel selection mechanism for evolutionary algorithms with metameric variable-length representations. Soft Comput 24, 16439–16452 (2020). https://doi.org/10.1007/s00500-020-04953-1
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00500-020-04953-1