JGAP Default Initialisation Configuration

I use JGAP as part of my Crunch clustering tool. For my thesis writeup, I needed to describe the specific parameters to the genetic algorithm it used. This post details how JGAP starts up, and where to find the defaults, what they are and what the values actually mean. These values are probably specific to the version I’m looking at (3.62), although they haven’t changed in roughly 4 years at the time of writing.

Startup

The search parameters are contained in a Configuration object. The configuration is initialised with various parameters and the type of chromosome to produce. The Genotype represents the population, and exposes the GA component to the user (via the evolve and getFittestIndividual methods).

Genotype

Genotypes can be bootstrapped from a Configuration via the randomInitialGenotype method. This constructs the population (which uses randomInitialChromosome to produce random individuals) and returns the initialised Genotype object.

Genotype.evolve()

evolve has three overloaded methods, the two that take arguments internally call the no-argument version.

The evolve method simply obtains an IBreeder object from the Configuration and uses it to construct a new Population, before setting the current population to the newly constructed version.

IBreeder

IBreeders coordinate the evolution step, however they do not actually perform or store any of the genetic operators. These are kept in the Configuration object’s m_geneticOperators field.

GABreeder

The default Breeder used is the GABreeder. The following stages are applied to the population:

Fitness Evaluation

The fitness of each individual in the population is first calculated, using the bulk fitness function, or via updateChromosomes if one isn’t provided.

Natural Selectors (Before Genetic Operators)

Each of the NaturalSelectors registered for application before the genetic operator chain runs is run on the population. The default configuration does not set any of these selectors.

Genetic Operators

Each of the genetic operators registered in the configuration is run, one at a time, in order of addition to the Configuration. Implementation for this step appears in BreederBase.applyGeneticOperators. The genetic operators implement an operate method, which runs over the population. These may only add to the population, however; an operator should never modify an individual in the population. A List of IChromosomes is passed as well as a Population, although this is just a reference to the Population‘s internal list.

DefaultConfiguration uses a Crossover operator, followed by a Mutation operator. Parameters to these are given at the end of this post.

Evaluation

The population is then re-evaluated, as it contains new individuals not present before the first round of selection.

Natural Selectors (After Genetic Operators)

Finally, the new population is produced by applying a NaturalSelector to it. If the selector selects too few individuals, JGAP can optionally fill the remainder with random individuals – change MinimumPopSizePercent to turn this on, but it’s off by default.

The Default JGAP Configuration

DefaultConfiguration sets up the following operator chain:

Genetic Operators

CrossoverOperator:

Rate: 35%, which translates to populationSize * 0.35 crossover operations per generation. Each crossover produces 2 individuals. Crossover point is random.

MutationOperator:

Desired Rate: 12. The rate for this one is a little different; mutation occurs if a random integer between 0 and the rate (12) is 0, thus it equates to a probability of 1/12. This operation is applied to each gene in each element of the population (excluding those produced by crossover), so the rough likelihood of a mutation being applied is (1/rate) * popSize * chromosomeSize. For each gene that is to be mutated, a copy of the whole IChromosome that contains it is made, with the selected Gene mutated via its applyMutation method.

Natural Selector

One selector is defined by default, which is the BestChromosomesSelector. This selector is given the following parameters:

Original Rate: 0.9. 90% of the population size allotted to this selector will actually be used. The selector is elitist, so this will return the top populationSize * 0.9 elements. The remaining 10% is filled by cloning the selected elements, one by one, in order of fitness until the population size reaches the limit.

Doublette Chromosomes Allowed? Yes. Doublettes are equivalent chromosomes (by equals()).

Configuration Parameters

The configuration specifies that the pool of selectors will select 100% of the population size. However, the only selector is configured to produce only 90% of the population size each time.

keepPopulationSizeConstant is also set to true, which dictates that the population is trimmed to size at each iteration. Somewhat counter-intuitively, this does not cause the population size to be increased if it falls below the user supplied value; it doesn’t enforce a minimum, only a maximum

minimumPopSizePercent is set to zero, so random individuals will never be used to fill the population if it declines below the limit (won’t ever happen under these conditions).

So What is the Default?

The default configuration is an elitist ranking selector that clones the top 90% of the user-specified population size, repeating it to fill the rest. Crossover is random point with a rate of populationSize * 0.35. Mutation is random and applied at  to 1 in 12 genes in the whole population (i.e. the rate is dictated by chromosome size * population size / 12).

Restoring sudo access after an Ubuntu upgrade

I recently brought back an old mini ITX box which had an unsupported Ubuntu version on it (last booted well over a year ago). During the upgrade process from Maverick to Natty, one of the scripts asked if I wanted a new /etc/sudoers file. Stupidly, I assumed that my user was in the correct group and took the new one.

On rebooting it turned out that my choice was unwise – I didn’t have sudo access nor did I have the root password for recovery. Unfortunately, the trick of using /bin/bash as an init replacement to get a root shell didn’t work either (it’s a common problem).

The fix was to write a small C program which just executed a script with /bin/sh to replace the sudoers file:

#include<stdio.h>
#include<stdlib.h>
#include<unistd.h>
int main(void){
	execl("/bin/sh", "-e", "/home/mat/replace_sudoers.sh",0);
	return 0;
}

Compile this with gcc: gcc -o replace replace_sudoers.c then create a replace_sudoers.sh with the following contents (with the home directory changed):

echo "Backing up old sudoers"

cp /etc/sudoers /home/mat/old_sudoers
chmod 777 /home/mat/old_sudoers

echo "moving new one"
cp -fr /home/mat/sudoers /etc/sudoers
chown root /etc/sudoers
chmod 0440 /etc/sudoers

echo "moved new sudoers successfully, will halt in 5s"
sleep 5
halt

I replaced my old sudoers with the following bare-bones one:

#/etc/sudoers

Defaults env_reset

root	ALL=(ALL) ALL
mat	ALL=(ALL) ALL
%admin	ALL=(ALL) ALL

Now, at the GRUB boot menu, edit the first kernel entry. Instead of using init=/bin/sh, init=/home/mat/replace can be used which will launch the script and overwrite the old sudoers file. On rebooting, you’ll have your sudo privileges back.