An empirical study on GAs “without parameters”Th. Bäck1,2 and A.E. Eiben1,3 and N.A.L. van der Vaart 11 Leiden University, 2 ICD Dortmund, 3 Free University AmsterdamAbstract. In this paper we implement GAs that have one or more parameters thatare adjusted during the run. In particular we use an existing self-adaptive mutationrate mechanism, propose a new mechanism for self-adaptive crossover rates, andredesign an existing variable population size model. We compare the simple GA withGAs featuring only one of the parameter adjusting mechanisms and with a GA thatapplies all three mechanisms - and is therefore almost “parameterless”. Theexperimental results on a carefully designed test suite indicate the superiority of theparameterless GA and give a hint on the power of adapting the population size.IntroductionTraditional genetic algorithms have parameters that must be specified before theGA is run on a problem. The most important parameters are the strategy or controlparameters: population size (N), mutation rate (pm), and crossover rate (pc). Theoptimum setting of these parameters can be different for each problem. Moreover, theoptimal values can be different in different phases of one single run on a givenproblem. Setting parameter values correctly is, therefore, a hard task. In general, thereare two major forms of setting parameter values: parameter tuning and parametercontrol [EHM99]. Parameter tuning is the usual approach of finding good parametervalues before the run of the GA and then these static values are used during the wholerun. Parameter control is different because it changes initial parameter values duringthe run. Parameter control itself has three variants: deterministic, adaptive and self-adaptive. Deterministic means that parameters are changed according to a rule whichuses no feedback from the GA, usually it is some sort of time-varying scheme. Foradaptive control, feedback does take place and the values are changed in direction ormagnitude depending on this feedback. Self-adaptivity is the idea of evolution of theparameters of evolution; the values are encoded into the chromosomes and are alsosubject to mutation, crossover and selection. The better parameter values will survivebecause they produce better offspring. Throughout this paper we maintain thisterminology and use the term self-adjusting if we do not want or cannot specify whichform of parameter control is used.The main objective of this paper is to investigate the feasibility of eliminating thethree main parameters, N, pm, and pc. That is, we are looking for experimentalevidence on the performance of a parameterless GA. The race is not won in advanceby any of the GA variants, for we are dealing with a clear trade-off situation. On theone hand, on-line parameter adjustment causes a learning overhead, that is the GA issolving a problem and is learning good parameter values at the same time. This mightcause a performance decrease w.r.t. using steady parameters. On the other hand,adjustable parameters provide the GA with valuable flexibility. If the GA can adjustits parameters (sub)optimally it might cause increased efficiency. A priori it cannot bepredicted which effect will influence the GA performance more.Previous research on the mutation rate (pm), crossover rate (pc) and population size(N), has focused on either adapting/self-adapting one of these parameters or onadjusting two or all of these parameters in a non self-adaptive fashion (i.e. adaptive ordynamic parameters). As for crossover there has not been previous research on self-adapting the crossover rate. The technical research objectives here are threefold.1. Designing and investigating a new method for self-adapting the crossover rate.2. Investigating the effect of self-adjusting the parameters pm, pc and N separately; aself-adaptive pm, a self-adaptive pc and an adaptive N. (Notice that a self-adaptivepopulation size wouldn’t make much sense.)3. Investigating the combined use of self-adjusting pm, pc and N within a completelyself-adjusting GA.Test suiteTo gain relevant experimental feedback we have carefully chosen a number of testfunctions. For selecting the test function we followed the guidelines after [WMRD95,BäMi97] and required that the test suite should1) include a few unimodal functions for comparison of efficiency (convergencevelocity),2) contain nonlinear, nonseparable problems,3) contain scalable functions,4) have a standard form,5) include a few multimodal functions of different complexity with a largenumber of local optima,6) not have only multimodal functions that have a regular arrangement of localoptima, (because this might favour GA-operators that exploit the regularity),7) contain high-dimensional functions, because these are better representativesof real-world applications.The following test suite of five functions conforms to the rules listed above: f1 isthe sphere model after De Jong [DeJo75], f2 is the generalized Rosenbrock function[Rose60,HoBä91], f3 is the generalized Ackley function [Ackl87,BäSc93], f4 is thegeneralized Rastrigin function [TöZi89,HoBä91], and f5 is the fully deceptive six-bitfunction [Deb97] (this is the only function in the test set that uses 6 bits/variable). Inorder to comply to a standard form; they all have dimension n=10 and use 20bits/variable (except f5).∑==niixxf121)(( )∑−=+−+−=1122122)1()(100)(niiiixxxxfexnxnxfniinii++−−−=∑∑==20)2cos(1exp12.0exp20)(1123π( )∑=−+=niiixxnxf124)2cos(1010)(π∑=∈−≤−−=niiiiiiigenesofisxxifxxifxnxf15’1#,4)4(400.14)4(492.0)(fAlgorithmsThe basic traditional GA used for this research is a steady-state GA using Graycoding, a mutation rate of pm = 1/l, and a crossover rate of pc = 0.90. The populationsize is N = 60. The chromosome length will be 220 bits (80 bits for f5), which consistsof 10x20=200 bits (10x6=60 bits for f5) for the ten function variables (dimensionn=10) and at the end 2x10=20 bits for the two self-adaptive parameters pm and pc.Although the pm and pc are not used by the TGA, they are added and calculated fortwo reasons. The first reason is that, compared to the other GA’s, any (dis)advantagefrom a different length of the bitstring is ruled out. Second reason is that now,