metaheuristic_designer.benchmarks.classic_problems module

class ThreeSAT(clauses)

Bases: ObjectiveFunc

This is the 3-SAT problem that consist in finding if a logical expression given in 3CNF (conjunctive normal form with 3 variables per clause) is satisfiable, in other words, if there is a combination of boolean variables that makes it true.

Format based on https://www.cs.ubc.ca/%7Ehoos/SATLIB/benchm.html

Parameters:

clauses: ndarray

A representation of the clauses that defines the logical expression, this will be a matrix of size (n,3), where each component is the index (starting at 1) of the variable in this clause, negation is represented as negative numbers.

For example, the expression (¬a ∨ b ∨ ¬c) ∧ (a ∨ ¬b ∨ d) is represented as [[-1, 2, -3], [1, -2, 4]]

Attributes:

params

Access parameter values by attribute-style lookup.

Methods

__call__(population)	Shorthand for executing the objective function on a vector.
add_parameter_constraints(...)	Attach extra constraint handlers for extended encodings (e.g., PSO).
calculate_fitness(population)	Evaluate fitness for the whole population.
get_params()	Return a copy of the current parameter dictionary.
get_state()	Return a dictionary with the current configuration.
objective(solution)	Calculates the percentage of clauses satisfied in the logical expression.
repair_population(population)	Transforms an invalid vector into one that satisfies the restrictions of the problem.
restart()	Reset the evaluation counter to zero.
store_kwargs([progress])	Store keyword arguments and evaluate them at the given progress.
update(progress)	Re-evaluate all stored parameters at the current progress.
update_kwargs([progress])	Add or replace parameters and immediately evaluate them.

from_cnf_file

static from_cnf_file(path)

objective(solution)

Calculates the percentage of clauses satisfied in the logical expression.

Parameters:

solution: ndarray

A binary vector representing the value of each binary variable.

Returns:

perc_satisfied:

The percentage of clauses satisfied with this assignment of variables.

class BinKnapsack(cost, value, max_weight)

Bases: ObjectiveFunc

This is the 0-1 Knapsack problem that consist in choosing from set of elements which have a certain cost and value to maximize the value without reaching a weight threshold.

Parameters:

cost: ndarray

The cost associated to each of the elements.

value: ndarray

The value associated to each of the elements.

max_weight: float

The maximum weight.

Attributes:

params

Access parameter values by attribute-style lookup.

Methods

__call__(population)	Shorthand for executing the objective function on a vector.
add_parameter_constraints(...)	Attach extra constraint handlers for extended encodings (e.g., PSO).
calculate_fitness(population)	Evaluate fitness for the whole population.
get_params()	Return a copy of the current parameter dictionary.
get_state()	Return a dictionary with the current configuration.
objective(solution)	Calculates the total value of the selection of elements.
repair_population(population)	Transforms an invalid vector into one that satisfies the restrictions of the problem.
restart()	Reset the evaluation counter to zero.
store_kwargs([progress])	Store keyword arguments and evaluate them at the given progress.
update(progress)	Re-evaluate all stored parameters at the current progress.
update_kwargs([progress])	Add or replace parameters and immediately evaluate them.

repair_solution

objective(solution)

Calculates the total value of the selection of elements. If the weight is higher than the maximum weight, the value is replaced by the negative weight of the elements.

Parameters:

solution: ndarray

A binary vector deciding whether to choose or not each element.

Returns:

value: float

The total value of the objects.

repair_solution(solution)

class MaxClique(adjacency_matrix)

Bases: ObjectiveFunc

This is the Maximum clique problem which consists on finding the size of the largest subgraph that has all its nodes interconnected (a clique).

Parameters:

adjacency_matrix: ndarray

The adjacency matrix of the graph.

Attributes:

params

Access parameter values by attribute-style lookup.

Methods

__call__(population)	Shorthand for executing the objective function on a vector.
add_parameter_constraints(...)	Attach extra constraint handlers for extended encodings (e.g., PSO).
calculate_fitness(population)	Evaluate fitness for the whole population.
get_params()	Return a copy of the current parameter dictionary.
get_state()	Return a dictionary with the current configuration.
objective(solution)
repair_population(population)	Transforms an invalid vector into one that satisfies the restrictions of the problem.
restart()	Reset the evaluation counter to zero.
store_kwargs([progress])	Store keyword arguments and evaluate them at the given progress.
update(progress)	Re-evaluate all stored parameters at the current progress.
update_kwargs([progress])	Add or replace parameters and immediately evaluate them.

objective(solution)

Parameters:

solution: ndarray

A sequence of nodes that will be read from left to right, starting from the first node that creates a clique of size 0, checking if adding a new node from the sequence produces a clique of a larger size. If this is not the case the algorithm ends.

Returns:

clique_size: int

The size of the clique generated with this sequence

class TSP(adjacency_matrix, name=None, mode='min')

Bases: ObjectiveFunc

Attributes:

params

Access parameter values by attribute-style lookup.

Parameters:

• adjacency_matrix (ndarray[tuple[int, int], floating] | ndarray[tuple[int, int], integer] | ndarray[tuple[int, int], uint8 | bool])

• name (str)

• mode (str)

Methods

__call__(population)	Shorthand for executing the objective function on a vector.
add_parameter_constraints(...)	Attach extra constraint handlers for extended encodings (e.g., PSO).
calculate_fitness(population)	Evaluate fitness for the whole population.
from_csv(problem_path[, name, mode])	Constructs the objective function from a .csv file.
get_params()	Return a copy of the current parameter dictionary.
get_state()	Return a dictionary with the current configuration.
objective(solutions)	Implementation of the objective function.
repair_population(population)	Transforms an invalid vector into one that satisfies the restrictions of the problem.
restart()	Reset the evaluation counter to zero.
store_kwargs([progress])	Store keyword arguments and evaluate them at the given progress.
update(progress)	Re-evaluate all stored parameters at the current progress.
update_kwargs([progress])	Add or replace parameters and immediately evaluate them.

classmethod from_csv(problem_path, name=None, mode='min')

Constructs the objective function from a .csv file.

Parameters:

problem_pathPath

Path to the .csv file containing the weights of each edge. The expected format of the file is a table with 3 columns: Edge 1, Edge 2, Weights

namestr, optional

Name to use when showing the user which function is being optimized, by default None

modestr, optional

Optimization mode to use, by default “min”

Returns:

An object of type TSP (Objective function on vectors)

Parameters:

• problem_path (Path)

• name (str | None)

• mode (str)

objective(solutions)

Implementation of the objective function.

Return type:

ndarray[tuple[int], floating] | ndarray[tuple[int], integer] | ndarray[tuple[int], uint8 | bool]

Parameters:

solution: Any

The solution for which the fitness will be calculated.

Returns:

objective_value: VectorLike | ScalarLike

Value of the objective function given a solution.

Parameters:

solutions (ndarray[tuple[int, int], floating] | ndarray[tuple[int, int], integer] | ndarray[tuple[int, int], uint8 | bool])