The parameter-less genetic algorithm in practice
Introduction
The parameter-less genetic algorithm was proposed recently [7]. Its motivation was to make genetic algorithms (GAs) easier to use and to make them available to as large an audience as possible. The need for solving problems occur in a variety of domains and GAs can be useful tools for that purpose. What has been difficult up to now is the interaction between the GA and the user; GAs require the specification of a number of parameters for which users usually do not know how to specify. In other words, the user needs to have a substantial amount of GA expertise in order to apply them in a proper way. But most users are not (and should not be required to be) experts in the field of genetic algorithms. An analogy comes handy here. When people use an electrical appliance, say a toaster, they do not have to know about Ohm's law or about the internal workings of the toaster. Yet, people use toasters everyday, and most of them have never heard about Ohm's law.1 Likewise, with genetic algorithms, users should not need to worry about population sizes, crossover probabilities, and other GA internals. Yet, people should be able to use GAs, even if they do not understand much about how they work.
In the original paper [7], the validity of the parameter-less GA was illustrated on artificial problems. In this paper it is applied to a quasi-real-world problem, a scenario that users are more likely to encounter in practice. Artificial problems are useful for testing GAs under carefully controlled conditions so that specific aspects of the algorithm can be analyzed. If that was not done, it would not be possible to get a better understanding of GAs, and it would not be possible to improve the state of the art in GA technology. However, it is also important to keep an eye on the applications side and see how the GA performs on problems that are not artificially constructed. Moreover, it is important to illustrate how the lessons learned from theory can be transferred to a practical context. That is precisely what we do here.
The paper starts by reviewing the parameter-less genetic algorithm. Then, Section 3 describes the network expansion problem, followed by the application of the parameter-less technique on Section 4. Section 5 presents an empirical measure of problem difficulty. Finally, the paper outlines some extensions to this work.
Section snippets
Background
This section briefly reviews the parameter-less GA. With the parameter-less GA, the user does not need to specify the selection rate, crossover probability and the population size parameters.
A network expansion problem
This section describes a utility network expansion problem. For its exposition we focus on the particular case of an electrical network. Without further considerations, let us describe what the network expansion problem is with an illustrative example shown in Fig. 2. The figure shows a region that does not have electrical facilities, an hypothetical instance of the network expansion problem.
There are four types of entities depicted in the figure: cables, substations, possible transformer
Parameter-less GA application
This section shows the application of the parameter-less GA to the network expansion problem described during the previous section. In particular, the GA is applied to a 60-bit problem instance. It should be stressed that the parameter-less technique relieves the user from having to specify the population size, selection rate, and crossover probability, but it does not relieve the user from specifying the type of GA operators to be used. In fact, the parameter-less technique can be used with
Towards an empirical measure of problem difficulty
During the previous sections we have argued that the amount of computing power that needs to be put in order to solve a problem is related to the problem's difficulty. Different facets of problem difficulty have been pointed out by researchers in the evolutionary computation field. Among these difficulties are isolation, deception, multi-modality, bad building block scaling, and noisy fitness functions.
From a practical perspective it would be nice to estimate the degree of difficulty of a given
Extensions
The parameter-less technique is a step forward towards making GAs easier to use. With it, the user does not need to specify parameters such as population size, selection rate, and crossover probabilities. However, there are still some decisions that the user needs to make. For example, the user must specify an encoding for the problem as well as GA operators. In the example shown in this paper we used a bit string encoding and a uniform crossover operator. Other choices could have been made as
Summary and conclusions
This paper reviewed the parameter-less genetic algorithm and showed a practical application of it to a utility network expansion problem. The problem has characteristics that contrast with those of pure artificial problems, and constitutes a more representative scenario of what users might encounter in practice. Another important contribution of this paper is the introduction of an empirical measure of problem difficulty. The measure is enabled by the existence of the parameter-less GA, and can
Acknowledgements
This work was sponsored in part by the Portuguese Foundation for Science and Technology (FCT/MCT), under grant POSI/SRI/42065/2001 and grant POCTI/MGS/37970/2001.
The work was also sponsored in part by the Air Force Office of Scientific Research, Air Force Materiel Command, USAF, under grants F49620-00-0163, the National Science Foundation under grant DMI-9908252. The US Government is authorized to reproduce and distribute reprints for Government purposes notwithstanding any copyright notation
References (15)
- et al.
Introduction to Algorithms
(1993) - et al.
Computers and Intractability: A Guide to the Theory of NP-completeness
(1979) - et al.
Genetic algorithms, noise, and the sizing of populations
Complex Systems
(1992) - et al.
Toward a better understanding of mixing in genetic algorithms
Journal of the Society of Instrument and Control Engineers
(1993) - G.R. Harik, Linkage learning via probabilistic modeling in the ECGA, IlliGAL Report No. 99010, University of Illinois...
- et al.
The gambler's ruin problem, genetic algorithms, and the sizing of populations
- et al.
A parameter-less genetic algorithm
Cited by (71)
Nearshore submerged wave farm optimisation: A multi-objective approach
2022, Applied Ocean ResearchReinforcement-Learning designs droplet microfluidic networks
2022, Computers and Chemical EngineeringPopulation Size Influence on the Efficiency of Evolutionary Algorithms to Design Water Networks
2017, Procedia EngineeringUsing characteristics of the optimisation problem to determine the Genetic Algorithm population size when the number of evaluations is limited
2015, Environmental Modelling and SoftwareCitation Excerpt :The final method considered was the ‘Parameterless GA calibration method. This GA calibration methodology was first proposed by Harik and Lobo (1999), as well as in a number of subsequent studies (Lobo and Goldberg, 2004; Reed and Yamaguchi, 2004; Minsker, 2005). As is the case in this work, Reed and Yamaguchi (2004) assumed that population size is the key parameter controlling the reliability and efficiency of GAs.
Comparison of optimization approaches on linear quadratic regulator design for trajectory tracking of a quadrotor
2024, Evolutionary Intelligence