Contracts¶
Contracts are used to check the pre and post conditions of functions to make sure that the evolutionary algorithm remains constrained within the solution space.
All contracts used by all functions are listed here. It is highly recommended that similar functions that are implemented in the future implement similar contracts. This will be explained further as each contract is explaioned.
GA.py¶
The main GA driver has the following contracts. It is highly recommended that any GA implemented to maximize the fitness score should implement these contracts.
The main GA runner¶
Preconditions¶
kwargs
should be suppliedkwargs
is a dict mapping argument names (strings) to argument values- The maximum number of generations allowed is greater than 0
Postconditions¶
kwargs
should not be changed- At least one of the following two conditions must hold
- the fitness of the fittest individual (being returned) is at least
targetscore
- the current generation count is equal to the maximum number of generations allowed
- the fitness of the fittest individual (being returned) is at least
the maximum number of generations allowed is greater than 0
Individual.py¶
The following contracts must be followed for any implementation of the Individual
class
Individual.__hash__(self, other)
¶
Preconditions¶
None
Postconditions¶
- an
int
should be returned self
should not be changed
In addition to these, the current implementation has the following methods implemented:
Individual.__eq__(self, other)
¶
Preconditions¶
other
should be an instance ofIndividual
Postconditions¶
other
should not be changedself
should not be changed
Individual.__setitem__(self, index, obj)
¶
Preconditions¶
- Exactly one of the following two conditions must be satisfied:
- 0 <=
index
<= len(self.chromosomes) - len(self.chromosomes)*-1 >= index >= -1
- 0 <=
Postconditions¶
- The object at
self.chromosomes[index]
should beobj
Individual.__contains__(self, chromosome)
¶
Preconditions¶
None
Postconditions¶
self
should not be changedchromosome
should not be changed
population.py¶
The following contracts are applied to the functions in population.py
genPop(N, chromGenfuncs, chromGenParams)
¶
Preconditions¶
- N >= 0
chromGenfuncs
is a list- Every entry in
chromGenfuncs
is a function chromGenParamss
is a list- The lengths of
chromGenfuncs
andchromGenParams
are equal
Postconditions¶
- The inputs are unchanged
- Function returns a list
- The length of the returned list is
N
- The returned list contains exactly 1 of each item i.e. no two items in the returned list are equal
genCharsChrom(l, chars)
¶
Preconditions¶
l
is an integerchars
is an instance of some class that implements__getitem__
chars
is an instance of some class that implements__len__
len(chars)
is greater than 0
Postconditions¶
- The inputs are unchanged
- Function returns a list
- The length of the returned list is
l
- Every element in the returned list exists in
chars
score.py¶
score(p, scorefuncs, scorefuncparams, SCORES)
¶
Preconditions¶
p
is an instance ofIndividual
scorefuncs
is a list of functionsscorefuncparams
is a list of tuples- The lengths of
scorefuncs
andscorefuncparams
are equal SCORES
is a dictionary
Postconditions¶
The inputs are unchanged
p
is inSCORES
- Exactly one of the following two conditions are met:
p
was inSCORES
before this function was called and the number of entries inSCORES
has not changedp
was not inSCORES
before this function was called and the number of entries inSCORES
has increased by exactly 1
scoreOnes(p)
¶
Preconditions¶
p
is list- All elements in
p
are strings of length exactly 1 - All elements in
p
are either ‘0’ or ‘1’
Postconditions¶
p
is unchaged- An integer is returned
- The value returned is at least 0
scoreTSP(tour, DIST)¶
- post:
- isinstance(__return__, float)
- post[tour, DIST]:
- __old__.tour == tour __old__.DIST == DIST
Preconditions¶
tour
is a listDIST
is a dictionary- All elements in
tour
are integers - All keys in
DIST
are integers - All values in
DIST
are dictionaries - Every key in every value of
DIST
is an integer - Every value in every value of
DIST
is a float
Loop Invariant¶
answer
(the value to be returned is at most 0 and monotonously decreases
Postconditions¶
- The inputs are unchanged
- The function returns a float
getRouletteWheel(pop, SCORES)¶
Preconditions¶
pop
is a list of instances ofIndividual
SCORES
is a dictionary- Every element in
pop
is a key inSCORES
Postconditions¶
- The inputs are unchanged
- A list of 3-tuples of type (Individual, float, float) is returned
- The length of the returned list is equal to the length of
pop
- The first element of every tuple in the returned list exists in
pop
- The second float is smaller than the third float in every tuple in the returned list
rouletteWheelSelect(wheel, s=None)¶
Preconditions¶
wheel
is a list of 3-tuples which satisfy all the following conditions- The first element is an instance of
Individual
- The last two elements are floats
- The first float is smaller than the second
- The first element is an instance of
- Exactly one of the following two conditions are met:
s
is a floats
is None
Postconditions:¶
- The inputs are unchanged
- An instance of
Individual
is returned
tournamentSelect(pop, T, w, n, scorefunc, scoreparams)¶
Preconditions¶
pop
is a list of instances ofIndividual
T
is an integerw
is an integern
is an integerw
is at mostn
n%w
is exactly 0n
is at mostT
scoreparams
is a tuple
Postconditions¶
- The inputs are unchanged
- A list of
n
instances ofIndividual
is returned
crossover.py¶
The following contracts are implemented for the crossover functions.
crossOnes(p1, p2, chrom)¶
injectionco(p1, p2, chrom)¶
twoChildCrossover(p1,p2, crossfuncs, crossparams)¶
Preconditions¶
p1
andp2
are instances ofIndividual
p1
andp2
are of exactly equal length- The number of elements in
crossfuncs
is exactly equal to the length ofp1
(and therefore ofp2
) - The number of elements in
crossfuncs
is exactly equal to the number of elements incrossparams
- Every element in
crossparams
is a tuple
Postconditions¶
- The inputs are unchanged
- A tuple of two elements of type
Individual
is returned - Each of the returned children has the same number of chromosomes as the parents
- Each chromosome in each of the children has the same length as the corresponding chromosome of both parents
oneChildCrossover(p1,p2, crossfuncs, crossparams)¶
Preconditions¶
p1
andp2
are instances ofIndividual
p1
andp2
are of exactly equal length- The number of elements in
crossfuncs
is exactly equal to the length ofp1
(and therefore ofp2
) - The number of elements in
crossfuncs
is exactly equal to the number of elements incrossparams
- Every element in
crossparams
is a tuple
Postconditions¶
- The inputs are unchanged
- A tuple of one element of type
Individual
is returned - The returned child has the same number of chromosomes as the parents
- Each chromosome in the child has the same length as the corresponding chromosome of both parents
muatation.py¶
mutateSingleAllele(p, chrom, chars)¶
Preconditions¶
p
is an instance ofIndividual
chrom
is an integerThe value of each gene in the
chrom
th chromosome ofp
exists inchars
- Exactly one of the following two conditions must be satisfied:
- 0 <=
index
<= len(self.chromosomes) - len(self.chromosomes)*-1 >= index >= -1
- 0 <=
Postconditions¶
- The inputs are unchanged
- A new instance of
Individual
is returned - The
chrom
th chromosome of the returned individual is not equal to thechrom
th chromosome ofp
- All other chromosomes of the returned individual are exactly the same as the corresponding chromosome of
p
swapmut(p, chrom)¶
Preconditions¶
p
is an instance ofIndividual
chrom
is an integer- Exactly one of the following two conditions are satisfied:
- 0 <=
chrom
<=len(p.chromosomes)
len(self.chromosomes)*-1
>=index
>= -1
- 0 <=
Postconditions¶
- The inputs are unchaged
- An instance of
Individual
is returned - All values in the
chrom
th chromosome ofp
are present in thechrom
th chromosome of the output individual - The
chrom
th chromosomes of the output individual andp
are not equal - There are exactly two genes in the
chrom
th chromome ofp
and the returned individual, whose values differ
revmut(p, chrom)¶
Preconditions¶
p
is an instance ofIndividual
chrom
is an integer- Exactly one of the following two conditions are satisfied:
- 0 <=
chrom
<=len(p.chromosomes)
len(self.chromosomes)*-1
>=index
>= -1
- 0 <=
Postconditions¶
- The inputs are unchaged
- An instance of
Individual
is returned - All values in the
chrom
th chromosome ofp
are present in the`chrom
th chromosome of the output individual - The
chrom
th chromosomes of the output individual andp
are not equal
shufflemut(p, chrom)¶
- post[p, chrom]:
- __old__.p == p __old__.chrom == chrom isinstance(__return__, Individual) __return__.chromosomes[chrom] != p.chromosomes[chrom] forall(p.chromosomes[chrom], lambda e: e in __return__.chromosomes[chrom]) forall(__return__.chromosomes[chrom], lambda e: e in p.chromosomes[chrom])
Preconditions¶
p
is an instance ofIndividual
chrom
is an integer- Exactly one of the following two conditions are satisfied:
- 0 <=
chrom
<=len(p.chromosomes)
len(self.chromosomes)*-1
>=index
>= -1
- 0 <=
Postconditions¶
- The inputs are unchaged
- An instance of
Individual
is returned - All values in the
chrom
th chromosome ofp
are present in the`chrom
th chromosome of the output individual - The
chrom
th chromosomes of the output individual andp
are not equal - The length of the
chrom
th chromosome of the returned individual is exactly equal to the length of thechrom
th chromosome ofp