Fitness Functions¶

Classes for defining fitness functions.

class OneMax[source]¶

Fitness function for One Max optimization problem. Evaluates the fitness of an n-dimensional state vector $x = [x_{0}, x_{1}, \ldots, x_{n-1}]$ as:

$Fitness(x) = \sum_{i = 0}^{n-1}x_{i}$

Example

>>> import mlrose
>>> import numpy as np
>>> fitness = mlrose.OneMax()
>>> state = np.array([0, 1, 0, 1, 1, 1, 1])
>>> fitness.evaluate(state)
5

Note

The One Max fitness function is suitable for use in either discrete or continuous-state optimization problems.

evaluate(state)[source]¶

Evaluate the fitness of a state vector.

Parameters:	state (array) – State array for evaluation.
Returns:	fitness (float) – Value of fitness function.

class FlipFlop[source]¶

Fitness function for Flip Flop optimization problem. Evaluates the fitness of a state vector $x$ as the total number of pairs of consecutive elements of $x$ , ( $x_{i}$ and $x_{i+1}$ ) where $x_{i} \neq x_{i+1}$ .

Example

>>> import mlrose
>>> import numpy as np
>>> fitness = mlrose.FlipFlop()
>>> state = np.array([0, 1, 0, 1, 1, 1, 1])
>>> fitness.evaluate(state)
3

Note

The Flip Flop fitness function is suitable for use in discrete-state optimization problems only.

evaluate(state)[source]¶

Evaluate the fitness of a state vector.

Parameters:	state (array) – State array for evaluation.
Returns:	fitness (float) – Value of fitness function.

class FourPeaks(t_pct=0.1)[source]¶

Fitness function for Four Peaks optimization problem. Evaluates the fitness of an n-dimensional state vector $x$ , given parameter T, as:

$Fitness(x, T) = \max(tail(0, x), head(1, x)) + R(x, T)$

where:

$tail(b, x)$ is the number of trailing b’s in $x$ ;
$head(b, x)$ is the number of leading b’s in $x$ ;
$R(x, T) = n$ , if $tail(0, x) > T$ and $head(1, x) > T$ ; and
$R(x, T) = 0$ , otherwise.

Parameters:	t_pct (float, default: 0.1) – Threshold parameter (T) for Four Peaks fitness function, expressed as a percentage of the state space dimension, n (i.e. $T = t_{pct} \times n$ ).

Example

>>> import mlrose
>>> import numpy as np
>>> fitness = mlrose.FourPeaks(t_pct=0.15)
>>> state = np.array([1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0])
>>> fitness.evaluate(state)
16

References

De Bonet, J., C. Isbell, and P. Viola (1997). MIMIC: Finding Optima by Estimating Probability Densities. In Advances in Neural Information Processing Systems (NIPS) 9, pp. 424–430.

Note

The Four Peaks fitness function is suitable for use in bit-string (discrete-state with max_val = 2) optimization problems only.

evaluate(state)[source]¶

Evaluate the fitness of a state vector.

Parameters:	state (array) – State array for evaluation.
Returns:	fitness (float.) – Value of fitness function.

class SixPeaks(t_pct=0.1)[source]¶

Fitness function for Six Peaks optimization problem. Evaluates the fitness of an n-dimensional state vector $x$ , given parameter T, as:

$Fitness(x, T) = \max(tail(0, x), head(1, x)) + R(x, T)$

where:

$tail(b, x)$ is the number of trailing b’s in $x$ ;
$head(b, x)$ is the number of leading b’s in $x$ ;
$R(x, T) = n$ , if ( $tail(0, x) > T$ and $head(1, x) > T$ ) or ( $tail(1, x) > T$ and $head(0, x) > T$ ); and
$R(x, T) = 0$ , otherwise.

Parameters:	t_pct (float, default: 0.1) – Threshold parameter (T) for Six Peaks fitness function, expressed as a percentage of the state space dimension, n (i.e. $T = t_{pct} \times n$ ).

Example

>>> import mlrose
>>> import numpy as np
>>> fitness = mlrose.SixPeaks(t_pct=0.15)
>>> state = np.array([0, 0, 0, 1, 0, 1, 1, 0, 1, 1, 1, 1])
>>> fitness.evaluate(state)
12

References

De Bonet, J., C. Isbell, and P. Viola (1997). MIMIC: Finding Optima by Estimating Probability Densities. In Advances in Neural Information Processing Systems (NIPS) 9, pp. 424–430.

Note

The Six Peaks fitness function is suitable for use in bit-string (discrete-state with max_val = 2) optimization problems only.

evaluate(state)[source]¶

Evaluate the fitness of a state vector.

Parameters:	state (array) – State array for evaluation.
Returns:	fitness (float) – Value of fitness function.

class ContinuousPeaks(t_pct=0.1)[source]¶

Fitness function for Continuous Peaks optimization problem. Evaluates the fitness of an n-dimensional state vector $x$ , given parameter T, as:

$Fitness(x, T) = \max(max\_run(0, x), max\_run(1, x)) + R(x, T)$

where:

$max\_run(b, x)$ is the length of the maximum run of b’s in $x$ ;
$R(x, T) = n$ , if ( $max\_run(0, x) > T$ and $max\_run(1, x) > T$ ); and
$R(x, T) = 0$ , otherwise.

Parameters:	t_pct (float, default: 0.1) – Threshold parameter (T) for Continuous Peaks fitness function, expressed as a percentage of the state space dimension, n (i.e. $T = t_{pct} \times n$ ).

Example

>>> import mlrose
>>> import numpy as np
>>> fitness = mlrose.ContinuousPeaks(t_pct=0.15)
>>> state = np.array([0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 1])
>>> fitness.evaluate(state)
17

Note

The Continuous Peaks fitness function is suitable for use in bit-string (discrete-state with max_val = 2) optimization problems only.

evaluate(state)[source]¶

Evaluate the fitness of a state vector.

Parameters:	state (array) – State array for evaluation.
Returns:	fitness (float) – Value of fitness function.

class Knapsack(weights, values, max_weight_pct=0.35)[source]¶

Fitness function for Knapsack optimization problem. Given a set of n items, where item i has known weight $w_{i}$ and known value $v_{i}$ ; and maximum knapsack capacity, $W$ , the Knapsack fitness function evaluates the fitness of a state vector $x = [x_{0}, x_{1}, \ldots, x_{n-1}]$ as:

$Fitness(x) = \sum_{i = 0}^{n-1}v_{i}x_{i}, \text{ if} \sum_{i = 0}^{n-1}w_{i}x_{i} \leq W, \text{ and 0, otherwise,}$

where $x_{i}$ denotes the number of copies of item i included in the knapsack.

Parameters:	weights (list) – List of weights for each of the n items. values (list) – List of values for each of the n items. max_weight_pct (float, default: 0.35) – Parameter used to set maximum capacity of knapsack (W) as a percentage of the total of the weights list ( $W =$ max_weight_pct $\times$ total_weight).

Example

>>> import mlrose
>>> import numpy as np
>>> weights = [10, 5, 2, 8, 15]
>>> values = [1, 2, 3, 4, 5]
>>> max_weight_pct = 0.6
>>> fitness = mlrose.Knapsack(weights, values, max_weight_pct)
>>> state = np.array([1, 0, 2, 1, 0])
>>> fitness.evaluate(state)
11

Note

The Knapsack fitness function is suitable for use in discrete-state optimization problems only.

evaluate(state)[source]¶

Evaluate the fitness of a state vector.

Parameters:	state (array) – State array for evaluation. Must be the same length as the weights and values arrays.
Returns:	fitness (float) – Value of fitness function.

class TravellingSales(coords=None, distances=None)[source]¶

Fitness function for Travelling Salesman optimization problem. Evaluates the fitness of a tour of n nodes, represented by state vector $x$ , giving the order in which the nodes are visited, as the total distance travelled on the tour (including the distance travelled between the final node in the state vector and the first node in the state vector during the return leg of the tour). Each node must be visited exactly once for a tour to be considered valid.

Parameters:

coords (list of pairs, default: None) – Ordered list of the (x, y) coordinates of all nodes (where element i gives the coordinates of node i). This assumes that travel between all pairs of nodes is possible. If this is not the case, then use distances instead.
distances (list of triples, default: None) – List giving the distances, d, between all pairs of nodes, u and v, for which travel is possible, with each list item in the form (u, v, d). Order of the nodes does not matter, so (u, v, d) and (v, u, d) are considered to be the same. If a pair is missing from the list, it is assumed that travel between the two nodes is not possible. This argument is ignored if coords is not None.

Examples

>>> import mlrose
>>> import numpy as np
>>> coords = [(0, 0), (3, 0), (3, 2), (2, 4), (1, 3)]
>>> dists = [(0, 1, 3), (0, 2, 5), (0, 3, 1), (0, 4, 7), (1, 3, 6),
             (4, 1, 9), (2, 3, 8), (2, 4, 2), (3, 2, 8), (3, 4, 4)]
>>> fitness_coords = mlrose.TravellingSales(coords=coords)
>>> state = np.array([0, 1, 4, 3, 2])
>>> fitness_coords.evaluate(state)
13.86138...
>>> fitness_dists = mlrose.TravellingSales(distances=dists)
>>> fitness_dists.evaluate(state)
29

Note

The TravellingSales fitness function is suitable for use in travelling salesperson (tsp) optimization problems only.
It is necessary to specify at least one of coords and distances in initializing a TravellingSales fitness function object.

evaluate(state)[source]¶

Evaluate the fitness of a state vector.

Parameters:	state (array) – State array for evaluation. Each integer between 0 and (len(state) - 1), inclusive must appear exactly once in the array.
Returns:	fitness (float) – Value of fitness function. Returns `np.inf` if travel between two consecutive nodes on the tour is not possible.

class Queens[source]¶

Fitness function for N-Queens optimization problem. Evaluates the fitness of an n-dimensional state vector $x = [x_{0}, x_{1}, \ldots, x_{n-1}]$ , where $x_{i}$ represents the row position (between 0 and n-1, inclusive) of the ‘queen’ in column i, as the number of pairs of attacking queens.

Example

>>> import mlrose
>>> import numpy as np
>>> fitness = mlrose.Queens()
>>> state = np.array([1, 4, 1, 3, 5, 5, 2, 7])
>>> fitness.evaluate(state)
6

References

Russell, S. and P. Norvig (2010). Artificial Intelligence: A Modern Approach, 3rd edition. Prentice Hall, New Jersey, USA.

Note

The Queens fitness function is suitable for use in discrete-state optimization problems only.

evaluate(state)[source]¶

Evaluate the fitness of a state vector.

Parameters:	state (array) – State array for evaluation.
Returns:	fitness (float) – Value of fitness function.

class MaxKColor(edges)[source]¶

Fitness function for Max-k color optimization problem. Evaluates the fitness of an n-dimensional state vector $x = [x_{0}, x_{1}, \ldots, x_{n-1}]$ , where $x_{i}$ represents the color of node i, as the number of pairs of adjacent nodes of the same color.

Parameters:	edges (list of pairs) – List of all pairs of connected nodes. Order does not matter, so (a, b) and (b, a) are considered to be the same.

Example

>>> import mlrose
>>> import numpy as np
>>> edges = [(0, 1), (0, 2), (0, 4), (1, 3), (2, 0), (2, 3), (3, 4)]
>>> fitness = mlrose.MaxKColor(edges)
>>> state = np.array([0, 1, 0, 1, 1])
>>> fitness.evaluate(state)
3

Note

The MaxKColor fitness function is suitable for use in discrete-state optimization problems only.

evaluate(state)[source]¶

Evaluate the fitness of a state vector.

Parameters:	state (array) – State array for evaluation.
Returns:	fitness (float) – Value of fitness function.

class CustomFitness(fitness_fn, problem_type='either', **kwargs)[source]¶

Class for generating your own fitness function.

Parameters:

fitness_fn (callable) – Function for calculating fitness of a state with the signature fitness_fn(state, **kwargs).
problem_type (string, default: ‘either’) – Specifies problem type as ‘discrete’, ‘continuous’, ‘tsp’ or ‘either’ (denoting either discrete or continuous).
kwargs (additional arguments) – Additional parameters to be passed to the fitness function.

Example

>>> import mlrose
>>> import numpy as np
>>> def cust_fn(state, c): return c*np.sum(state)
>>> kwargs = {'c': 10}
>>> fitness = mlrose.CustomFitness(cust_fn, **kwargs)
>>> state = np.array([1, 2, 3, 4, 5])
>>> fitness.evaluate(state)
150

evaluate(state)[source]¶

Evaluate the fitness of a state vector.

Parameters:	state (array) – State array for evaluation.
Returns:	fitness (float) – Value of fitness function.