Top

Soft Computing

Published in:

01-01-2012 | Original Paper

Theoretical basis of parameter tuning for finding optima near the boundaries of search spaces in real-coded genetic algorithms

Author: Hiroshi Someya

Published in: Soft Computing | Issue 1/2012

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

search-config

AI-assisted search

Off

Abstract

Studies on parameter tuning in evolutionary algorithms are essential for achieving efficient adaptive searches. This paper discusses parameter tuning in real-valued crossover operators theoretically. The theoretical analysis is devoted to improving robustness of real-coded genetic algorithms (RCGAs) for finding optima near the boundaries of bounded search spaces, which can be found in most real-world applications. The proposed technique for crossover-parameter tuning is expressed mathematically, and thus enables us to control the dispersion of child distribution quantitatively. The universal applicability and effect have been confirmed theoretically and verified empirically with five crossover operators. Statistical properties of several practical RCGAs are also investigated numerically. Performance comparison with various parameter values has been conducted on test functions with the optima placed not only at the center but also in a corner of the search space. Although the parameter-tuning technique is fairly simple, the experimental results have shown the great effectiveness.

previous article Study on semiparametric Wilcoxon fuzzy neural networks

next article Performance analysis in soccer: a Cartesian coordinates based approach using RoboCup data

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 "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

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

Available only for authorised users

Or preservation of statistics.

This equation is different from the relationship presented in Kimura et al. (2000). According to the first author Kimura’s private advice, they have assumed that parent vectors are independent random variables that satisfy \(E({{{\user2{x}_{\theta}^{(i)}}{\user2{x}_{\theta}^{(j\neq i){\rm T}}}}})={\user2{g}_{\theta}\user2{g}_{\theta}}^{{\rm T}}\) under the assumption of an infinite parent population, unlike in this paper.

This equation is different from the relationship presented in Higuchi et al. (2000). In their paper, each parent was assumed to be an independent sample from an infinite parent population satisfying \(E(({\user2{x}_{\theta}^{(i)}}-\user2{g}_{\theta}) ({\user2{x}_{\theta}^{({j\neq i})}}-\user2{g}_{\theta})^{{\rm T}})=0,\) unlike in this paper.

BNDX had been called NDX until 1997.

Experiments with BNDX and TMX have not been conducted because they seem somewhat obsolete and are used only with other search operators in hybrid RCGAs.

Akimoto Y, Sakuma J, Ono I, Kobayashi S (2009) Adaptation of expansion rate for real-coded crossovers. In: Proceedings of the genetic and evolutionary computation conference (GECCO-2009), ACM SIGEVO, Montréal, Canada, pp 739–746

Beyer HG (1999) On the dynamics of EAs without selection. In: Banzhaf W, Reeves C (eds) Foundations of genetic algorithms 5 (FOGA-98), Morgan Kaufmann Publishers, Inc., San Francisco, pp 5–26

Beyer HG, Deb K (2001) On self-adaptive features in real-parameter evolutionary algorithms. IEEE Trans Evol Comput 5(3):250–270CrossRef

Coello CAC (2002) Theoretical and numerical constraint-handling techniques used with evolutionary algorithms: a survey of the state of the art. Comput Methods Appl Mech Eng 191(11–12):1245–1287. doi:10.1016/S0045-7825(01)00323-1 CrossRefMATH

Deb K (2000) An efficient constraint handling method for genetic algorithms. Comput Methods Appl Mech Eng 186:311–338. doi:10.1016/S0045-7825(99)00389-8 CrossRefMATH

Eiben A, Michalewicz Z, Schoenauer M, Smith J (2007) Parameter control in evolutionary algorithms. In: Lobo FG, Lima CF, Michalewicz Z (eds) Parameter setting in evolutionary algorithms, studies in computational intelligence, vol 54. Springer, Berlin, pp 19–46. doi:10.1007/978-3-540-69432-8_2

Eshelman LJ, Mathias KE, Schaffer JD (1997) Crossover operator biases: exploiting the population distribution. In: Proceedings of the 7th international conference on genetic algorithms (ICGA’97), Morgan Kaufmann, San Francisco, CA, USA, pp 354–361

Goldberg DE (1989) Genetic algorithms in search, optimization, and machine learning. Addison Wesley, Reading

Herrera F, Lozano M (2005) Special issue on real coded genetic algorithms: operators, models and foundations. Soft Comput 9(4):223–323CrossRef

Herrera F, Lozano M, Verdegay JL (1998) Tackling real-coded genetic algorithms: operators and tools for behavioural analysis. Artif Intell Rev 12(4):265–319CrossRefMATH

Herrera F, Lozano M, Sánchez AM (2003) A taxonomy for the crossover operator for real-coded genetic algorithms: an experimental study. Int J Intell Syst 18(3):309–338CrossRefMATH

Higuchi T, Tsutsui S, Yamamura M (2000) Theoretical analysis of simplex crossover for real-coded genetic algorithms. In: Schoenauer M, Deb K, Rudolph G, Yao X, Lutton E, Merelo JJ, Schwefel HP (eds) Proceedings of the sixth international conference on parallel problem solving from nature—PPSN VI. Lecture Notes in Computer Science, vol 1917. Springer, Berlin, pp 365–374

Hoel PG (1976) Elementary statistics, 4th edn. Wiley, New York

Kimura S, Ono I, Kita H, Kobayashi S (2000) An extension of UNDX based on guidelines for designing crossover operators: proposition and evaluation of ENDX. Trans Soc Instrum Control Eng 36(12):1162–1171 (in Japanese with English abstract)

Kirkpatrick S, Gelatt C, Vecchi M (1983) Optimization by simulated annealing. Science 220(4598):671–680CrossRefMATHMathSciNet

Kita H, Yamamura M (1999) A functional specialization hypothesis for designing genetic algorithms. In: Proceedings of IEEE international conference on systems, man and cybernetics (SMC’99), IEEE, Tokyo, Japan, pp III–579–584

Kita H, Ono I, Kobayashi S (1998) Theoretical analysis of the unimodal normal distribution crossover for real-coded genetic algorithms. In: Proceedings of 1998 international conference on evolutionary computation, pp 529–534

Kita H, Ono I, Kobayashi S (1999) Multi-parental extension of the unimodal normal distribution crossover for real-coded genetic algorithms. In: Proceedings of IEEE congress on evolutionary computation (CEC 1999), pp 1581–1587

Larrañaga P, Lozano JA (eds) (2002) Estimation of distribution algorithms. Kluwer, Norwell

Michalewicz Z, Janikow CZ (1991) Handling constraints in genetic algorithms. In: Belew RK, Booker LB (eds) Proceedings of the fourth international conference on genetic algorithms (ICGA-91), Morgan Kaufmann, San Diego, CA, USA, pp 151–157

Mühlenbein H, Mahining T, Rodriguez AO (1999) Schemata, distributions and graphical models in evolutionary optimization. Heuristics 5:215–247CrossRefMATH

Ono I, Kobayashi S (1997) A real-coded genetic algorithm for function optimization using unimodal normal distribution crossover. In: Proceedings of the 7th international conference on genetic algorithms (ICGA’97), Morgan Kaufmann, San Francisco, CA, USA, pp 246–253

Ono I, Yamamura M, Kobayashi S (1996) A genetic algorithm with characteristic preservation for function optimization. In: Proceedings of the 4th international conference on soft computing—IIZUKA’96 methodologies for the conception, design, and application of intelligent systems, Iizuka, Fukuoka, Japan, pp 511–514

Ono I, Kita H, Kobayashi S (1999) A robust real-coded genetic algorithm using unimodal normal distribution crossover augmented by uniform crossover: effects of self-adaptation of crossover probabilities. In: Banzhaf W, Daida JM, Eiben AE, Garzon MH, Honavar V, Jakiela MJ, Smith RE (eds) Proceedings of the genetic and evolutionary computation conference (GECCO’99), Orlando, Florida, USA, pp 496–503

Sakuma J, Kobayashi S (2001) Extrapolation-directed crossover for real-coded GA: overcoming deceptive phenomena by extrapolative search. In: Proceedings of IEEE congress on evolutionary computation (CEC 2001), Seoul, Korea, pp 655–662

Sakuma J, Kobayashi S (2002) Extrapolation-directed crossover considering sampling bias in real-coded genetic algorithm. Trans Jpn Soc Artif Intell 17(6):699–707 (in Japanese with English abstract)CrossRef

Satoh H, Yamamura M, Kobayashi S (1996) Minimal generation gap model for GAs considering both exploration and exploitation. In: Proceedings of the 4th international conference on soft computing—IIZUKA’96 methodologies for the conception, design, and application of intelligent systems, Iizuka, Fukuoka, Japan, pp 494–497

Someya H (2007) Promising search regions of crossover operators for function optimization. In: Proceedings of the 20th international conference on industrial, engineering & other applications of applied intelligent systems: IEA/AIE 2007. Lecture Notes in Artificial Intelligence, vol 4570: New Trends in Applied Artificial Intelligence, pp 434–443

Someya H (2008a) Parameter tuning of real-valued crossover operators for statistics preservation. In: Proceedings of the seventh international conference on simulated evolution and learning: SEAL 2008. Lecture Notes in Computer Science, vol 5361: Simulated Evolution and Learning. Melbourne, Australia, pp 269–278. doi:10.1007/978-3-540-89694-4_28

Someya H (2008b) Theoretical parameter value for appropriate population variance of the distribution of children in real-coded GA. In: Proceedings of IEEE congress on evolutionary computation (CEC 2008) as part of the IEEE world congress on computational intelligence (WCCI 2008), IEEE, Hong Kong, pp 2722–2729

Someya H, Yamamura M (2001) Genetic algorithm with search area adaptation for the function optimization and its experimental analysis. In: Proceedings of IEEE congress on evolutionary computation (CEC 2001), Seoul, Korea, pp 933–940

Someya H, Yamamura M (2002) Robust evolutionary algorithms with toroidal search space conversion for function optimization. In: Proceedings of the genetic and evolutionary computation conference 2002, pp 553–560

Someya H, Yamamura M (2005) A robust real-coded evolutionary algorithm with toroidal search space conversion. In: Herrera and Lozano (2005), pp 254–269

Tang K, Yao X, Suganthan PN, MacNish C, Chen YP, Chen CM, Yang Z (2008) Benchmark functions for the CEC’2008 special session and competition on large scale global optimization. Tech. rep., IEEE congress on evolutionary computation: CEC 2008 (Proceedings of the IEEE world congress on computational intelligence: WCCI 2008), Hong Kong

Tsutsui S (1998) Multi-parent recombination in genetic algorithms with search space boundary extension by mirroring. In: Proceedings of the fifth international conference on parallel problem solving from nature (PPSN V), pp 428–437

Tsutsui S (2000) Sampling bias and search space boundary extension in real coded genetic algorithms. In: Whitley LD, Goldberg DE, Cantú-Paz E, Spector L, Parmee IC, Beyer HG (eds) Proceedings of the genetic and evolutionary computation conference (GECCO’00), Las Vegas, Nevada, USA, pp 211–218

Tsutsui S, Goldberg DE (2001) Search space boundary extension method in real-coded genetic algorithms. Inform Sci 133(3–4):229–247CrossRefMATH

Tsutsui S, Yamamura M, Higuchi T (1999) Multi-parent recombination with simplex crossover in real coded genetic algorithms. In: Banzhaf W, Daida JM, Eiben AE, Garzon MH, Honavar V, Jakiela MJ, Smith RE (eds) Proceedings of the genetic and evolutionary computation conference (GECCO’99), Orlando, Florida, USA, pp 657–664

Title: Theoretical basis of parameter tuning for finding optima near the boundaries of search spaces in real-coded genetic algorithms
Author: Hiroshi Someya
Publication date: 01-01-2012
Publisher: Springer-Verlag
Published in: Soft Computing / Issue 1/2012
Print ISSN: 1432-7643
Electronic ISSN: 1433-7479
DOI: https://doi.org/10.1007/s00500-011-0732-1

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 "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 1/2012

Bayesian estimation based on vague lifetime data

Performance analysis in soccer: a Cartesian coordinates based approach using RoboCup data

A new approach to obtain algebraic solution of interval linear systems

Fuzzy sets and cut systems in a category of sets with similarity relations

Manufacturing process performance evaluation for fuzzy data based on loss-based capability index

Assimilating and integrating network signals for solving some complex problems with a multiscale neural architecture

Premium Partner