The parameter-less genetic algorithm in practice

doi:10.1016/j.ins.2003.03.029

Information Sciences

Volume 167, Issues 1–4, 2 December 2004, Pages 217-232

https://doi.org/10.1016/j.ins.2003.03.029 Get rights and content

Abstract

The parameter-less genetic algorithm was introduced a couple of years ago as a way to simplify genetic algorithm operation by incorporating knowledge of parameter selection and population sizing theory in the genetic algorithm itself. This paper shows how that technique can be used in practice by applying it to a network expansion problem. The existence of the parameter-less genetic algorithm stresses the fact that some problems need more processing power than others. Such observation leads to the development of a problem difficulty measure which is also introduced in this paper. The measure can be useful for comparing the difficulty of real-world problems.

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.¹ 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)

T. Cormen et al.
Introduction to Algorithms
(1993)
M.R. Garey et al.
Computers and Intractability: A Guide to the Theory of NP-completeness
(1979)
D.E. Goldberg et al.
Genetic algorithms, noise, and the sizing of populations
Complex Systems
(1992)
D.E. Goldberg 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...
G.R. Harik et al.
The gambler's ruin problem, genetic algorithms, and the sizing of populations
G.R. Harik et al.
A parameter-less genetic algorithm

There are more references available in the full text version of this article.

Cited by (71)

Nearshore submerged wave farm optimisation: A multi-objective approach
2022, Applied Ocean Research
To be commercially viable, wave energy converters (WECs) will need to be deployed in arrays or “wave farms” to generate significant amounts of energy and to have the costs of these farms minimised. However, when designing a wave farm, there are a number of trade-offs to be made between competing objectives; for example, between the power production potential and installation costs, with the optimal design for one objective not necessarily favourable for the other. In this study, we developed a multi-objective optimisation methodology to allow rigorous evaluation of the trade-offs amongst multiple objectives. We demonstrate the methodology for four objectives: (1) maximising power production, (2) minimising the foundation loads, (3) minimising the number of foundations and (4) minimising the total export cable length required. However, the method is flexible and can be used for optimising a range of other parameters. A case study examining multi-objective optimisation of a wave farm using the developed probability-based evolutionary strategy was conducted for a proposed development site in Albany, Western Australia. The wave farms were composed of 5, 10 and 20 fully submerged cylindrical point-absorber type WECs similar to Carnegie Clean Energy's CETO-6 device. Simulations show that the optimal layouts preferring maximum power formed a single line perpendicular to the predominant wave direction; the optimal layouts preferring minimum cable length and a minimum number of foundations form multiple lines; whereas the optimal layouts preferring minimum foundation loads formed multiple lines in line with the predominant wave direction. By applying a cost model and non-dominated sorting, the methodology allowed us to quantify the trade-offs between power production and cost.
Reinforcement-Learning designs droplet microfluidic networks
2022, Computers and Chemical Engineering
Droplet microfluidics provides a platform for realizing programmable and flexible devices for performing diverse process operations on a single chip. Although recent developments have incorporated basic functionalities in droplet-based devices such as droplet sorting, sequencing, synchronization, etc., the design of microfluidic networks for specific functionalities remains to be of research interest. This requires the development of integrated devices that can perform complex operations and incorporate multiple functionalities on a single microfluidic chip. In this work, a state-of-the-art Reinforcement-learning (RL) algorithm based on Temporal-difference Q-learning is used to identify discrete microfluidic networks for a given functionality. This is the first time that a machine learning-based approach is deployed for discovering integrated network designs. The implementation of the algorithm has been illustrated through a combinatorial sorting problem, where the objective is to sort all the incoming droplet sequences at the inlet for two distinct droplet types. The algorithm identifies unapparent network designs using RL-based decisions in a microfluidic network space. The superiority of the RL-based algorithm is established against random search based on execution time, and against Genetic Algorithms (GA) based on solution quality. This work could be a first step towards achieving the ultimate goal of developing an unified droplet microfluidic design framework that can cater to a large number of drops and varying functionalities.
Population Size Influence on the Efficiency of Evolutionary Algorithms to Design Water Networks
2017, Procedia Engineering
The optimal sizing in water distribution networks (WDN) is of great interest because it allows the selection of alternative economical solutions that ensure design requirements at nodes (demands and pressure) and at lines (velocities). Among all the available design methodologies, this work analyzes those based on evolutionary algorithms (EAs).
EAs are a combination of deterministic and random approaches, and the performance of the algorithm depends on the searching process. Each EA features specific parameters, and a proper calibration helps to reduce the randomness factor and improves the effectiveness of the search for minima. More specifically, the only common parameter to all techniques is the initial size of the random population (P). It is well known that population size should be large enough to guarantee the diversity of solutions and must grow with the number of decision variables. However, the larger the population size, the slower the convergence process.
This work attempts to determine the population size that yields better solutions in less time. In order to get that, the work applies a method based on the concept of efficiency (E) of an algorithm. This efficiency relates the quality of the obtained solution with the computational effort that every EA requires to find the final design solution. This ratio E also represents an objective indicator to compare the performance of different algorithms applied to WDN optimization.
The proposed methodology is applied to the pipe-sizing problem of three medium-sized benchmark networks, such as Hanoi, New York Tunnel and GoYang networks. Thus, from the currently available algorithms, this work includes evolutionary methodologies based on a Pseudo-Genetic Algorithm (PGA), Particle Swarm Optimization (PSO) and Harmony Search (HS).
First, the different algorithm parameters for each network are calibrated. The values used for every EA are those that have been calculated in previous works. Secondly, specific parameters remain constant and the population size is modified. After more than 500,000 simulations, the influence of the population size is statistically analyzed in the final solutions. Finally, the efficiency was analyzed for each network and algorithm. The results ensure the best possible configuration based on the quality of the solutions and the convergence speed of the algorithm, depending of the population size.
Using characteristics of the optimisation problem to determine the Genetic Algorithm population size when the number of evaluations is limited
2015, Environmental Modelling and Software
Citation 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.
The Genetic Algorithm (GA) parameter values that result in the best possible solutions being found are generally problem specific, and therefore expected to be related to the characteristics of the fitness function. In this work, statistics that characterise the fitness function have been related to the convergence of a GA population due to the repetitive application of tournament selection. Assuming that this operator has the dominant influence on the variance of the population, and that the computational time available is limited, the result can be used to determine a suitable population size. The methodology developed has been compared to other GA calibration methodologies, and was found to be the best of the different methods considered across a range of stopping criteria and problem formulations. This result demonstrates the potential usefulness of fitness function characteristics to inform the configuration of GAs, and in turn find the best possible solutions.
A New Bipolar Approach Based on the Rooster Algorithm Developed for Utilize in Optimization Problems
2024, SSRN
Comparison of optimization approaches on linear quadratic regulator design for trajectory tracking of a quadrotor
2024, Evolutionary Intelligence

View all citing articles on Scopus

View full text

The parameter-less genetic algorithm in practice

Abstract

Introduction

Section snippets

Background

A network expansion problem

Parameter-less GA application

Towards an empirical measure of problem difficulty

Extensions

Summary and conclusions

Acknowledgements

Introduction to Algorithms

Computers and Intractability: A Guide to the Theory of NP-completeness

Genetic algorithms, noise, and the sizing of populations

Complex Systems

Toward a better understanding of mixing in genetic algorithms

Journal of the Society of Instrument and Control Engineers

The gambler's ruin problem, genetic algorithms, and the sizing of populations

A parameter-less genetic algorithm