Binary Optimization Problems

The pycellga.problems.single_objective.discrete.binary package provides a set of binary, single-objective benchmark functions. These discrete problems are commonly used to assess the performance of optimization algorithms on binary-encoded solutions. Each function presents unique challenges, such as local optima, multimodality, and rugged landscapes.

Count SAT

A binary satisfaction problem, often used to evaluate an algorithm’s ability to solve constraint satisfaction problems in a discrete search space.

class CountSat(n_var: int = 20)[source]

Bases: AbstractProblem

CountSat function implementation for optimization problems.

The CountSat function is used for testing optimization algorithms, particularly those involving satisfiability problems.

n_var

The number of variables (chromosome length) for the problem.

Type:: int

gen_type

The type of genes used in the problem, set to BINARY.

Type:: GeneType

xl

Lower bounds for binary variables, fixed to 0.

Type:: int

xu

Upper bounds for binary variables, fixed to 1.

Type:: int

f(x: List[int]) → float[source]: Calculates the CountSat function value for a given list of binary variables.

evaluate(x: List[int], out: dict, \*args, \*\*kwargs) → None[source]: Pymoo-compatible evaluation method for batch processing.

__init__(n_var: int = 20)[source]

Initialize the CountSat problem.

Parameters:: n_var (int, optional) – Number of binary variables (chromosome length) for the problem, by default 20.

evaluate(x: List[int], out: dict, *args, **kwargs) → None[source]

Evaluate function for compatibility with pymoo’s optimizer.

Parameters:

x (numpy.ndarray) – Array of input variables.
out (dict) – Dictionary to store the output fitness values.

f(x: List[int]) → float[source]

Calculate the CountSat function value for a given list of binary variables.

Parameters:: x (list) – A list of binary variables.
Returns:: The normalized CountSat function value.
Return type:: float

Error Correcting Codes Design Problem (ECC)

The ECC problem tests the efficiency of algorithms in solving problems related to error-correcting codes, which have discrete solution spaces and are commonly encountered in communication systems.

class Ecc(n_var: int = 144)[source]

Bases: AbstractProblem

Error Correcting Codes Design Problem (ECC) function implementation for optimization problems.

The ECC function is used for testing optimization algorithms, particularly those involving error-correcting codes.

n_var

Number of binary variables, typically 144.

Type:: int

gen_type

The type of genes used in the problem, set to BINARY.

Type:: GeneType

xl

Lower bounds for binary variables, fixed to 0.

Type:: int

xu

Upper bounds for binary variables, fixed to 1.

Type:: int

f(x: List[int]) → float[source]: Calculates the ECC function value for a given list of binary variables.

evaluate(x: List[int], out: dict, \*args, \*\*kwargs) → None[source]: Pymoo-compatible evaluation method for batch processing.

__init__(n_var: int = 144)[source]

Initialize the ECC problem.

Parameters:: n_var (int, optional) – Number of binary variables for the problem, by default 144.

evaluate(x: List[int], out: dict, *args, **kwargs) → None[source]

Evaluate function for compatibility with pymoo’s optimizer.

Parameters:

x (numpy.ndarray) – Array of input variables.
out (dict) – Dictionary to store the output fitness values.

f(x: List[int]) → float[source]

Calculate the ECC function value for a given list of binary variables.

Parameters:: x (list) – A list of binary variables.
Returns:: The ECC function value, rounded to four decimal places.
Return type:: float

Frequency Modulation Sounds Problem (FMS)

A binary version of the Frequency Modulation Sounds function, used to evaluate robustness and efficiency in finding optimal solutions within a binary space.

class Fms(n_var: int = 192)[source]

Bases: AbstractProblem

Frequency Modulation Sound (FMS) function implementation for optimization problems.

The FMS function is used for testing optimization algorithms, particularly those involving frequency modulation sound.

n_var

The number of binary variables for the problem, typically 192.

Type:: int

gen_type

The type of genes used in the problem, set to BINARY.

Type:: GeneType

xl

Lower bounds for binary variables, fixed to 0.

Type:: int

xu

Upper bounds for binary variables, fixed to 1.

Type:: int

f(x: List[int]) → float[source]: Calculates the FMS function value for a given list of binary variables.

evaluate(x: List[int], out: dict, \*args, \*\*kwargs) → None[source]: Pymoo-compatible evaluation method for batch processing.

__init__(n_var: int = 192)[source]

Initialize the FMS problem.

Parameters:: n_var (int, optional) – Number of binary variables for the problem, by default 192.

evaluate(x: List[int], out: dict, *args, **kwargs) → None[source]

Evaluate function for compatibility with pymoo’s optimizer.

Parameters:

x (numpy.ndarray) – Array of input variables.
out (dict) – Dictionary to store the output fitness values.

f(x: List[int]) → float[source]

Calculate the FMS function value for a given list of binary variables.

Parameters:: x (list) – A list of binary variables.
Returns:: The FMS function value.
Return type:: float

Max-Cut (100 nodes)

A max-cut problem involving 100 nodes, often used in graph partitioning. This problem challenges algorithms in finding optimal binary partitions.

class Maxcut100[source]

Bases: AbstractProblem

A class to represent the Maximum Cut (MAXCUT) problem for 100 nodes.

problema

A matrix representing the weights between nodes in the MAXCUT problem.

Type:: list of list of float

__init__()[source]

Initialize the AbstractProblem with gene type, variable count, and bounds.

Parameters:

gen_type (Any) – The type of genes used in the problem (e.g., REAL, BINARY).
n_var (int) – The number of design variables.
xl (float) – The lower bound for the design variables.
xu (float) – The upper bound for the design variables.

evaluate(x, out, *args, **kwargs)[source]

Evaluates the Maxcut problem for a given solution x.

Parameters:

x (ndarray) – Decision variable matrix (each row is a solution vector).
out (dict) – Output dictionary where results will be stored.

f(x)[source]

Fitness function for the Maxcut problem. Calculates the cut value of the given binary solution vector x.

Parameters:: x (list of int) – Binary vector representing the solution.
Returns:: The fitness value (cut value).
Return type:: float

Max-Cut (20 nodes, Density 0.1)

A max-cut problem with 20 nodes and a sparsity factor of 0.1. Suitable for testing performance on sparse graphs with limited connections.

class Maxcut20_01[source]

Bases: AbstractProblem

Maximum Cut (MAXCUT) function implementation for optimization problems.

The MAXCUT function evaluates the fitness of a binary partition of nodes based on edge weights. It is used to test optimization algorithms, particularly for maximum cut problems.

problema

Adjacency matrix representing edge weights between nodes.

Type:: list of list of float

f(x: list) → float[source]: Calculates the MAXCUT function value for a given list of binary variables.

evaluate(x: list, out: dict) → None[source]: Pymoo-compatible evaluation method for batch processing.

__init__()[source]: Initialize the MAXCUT problem with binary variables and adjacency matrix.

evaluate(x: List[int], out: dict, *args, **kwargs) → None[source]

Evaluate function for compatibility with pymoo’s optimizer.

Parameters:

x (numpy.ndarray) – Array of input variables.
out (dict) – Dictionary to store the output fitness values.

f(x: List[int]) → float[source]

Calculate the MAXCUT function value for a given list of binary variables.

Parameters:: x (list) – A list of binary variables representing node partitions.
Returns:: The MAXCUT function value representing the total weight of edges cut by the partition.
Return type:: float

Max-Cut (20 nodes, Density 0.9)

A denser version of the max-cut problem with a density of 0.9, requiring algorithms to manage numerous connections and find optimal partitions.

class Maxcut20_09[source]

Bases: AbstractProblem

Maximum Cut (MAXCUT) function for optimization on a 20-node graph.

This class evaluates the cut value by summing weights of edges between nodes in different partitions defined by binary variables.

problema

Adjacency matrix representing edge weights between nodes.

Type:: list of list of float

f(x: List[int]) → float[source]: Calculates the MAXCUT function value for a given list of binary variables.

evaluate(x: List[int], out: dict) → None[source]: Pymoo-compatible evaluation method for batch processing.

__init__()[source]: Initialize the MAXCUT problem with binary variables and adjacency matrix.

evaluate(x: List[int], out: dict, *args, **kwargs) → None[source]

Evaluate function for compatibility with pymoo’s optimizer.

Parameters:

x (numpy.ndarray) – Array of input variables.
out (dict) – Dictionary to store the output fitness values.

f(x: List[int]) → float[source]

Calculate the MAXCUT function value for a given list of binary variables.

Parameters:: x (List[int]) – A list of binary variables representing node partitions.
Returns:: The MAXCUT function value representing the total weight of edges cut by the partition.
Return type:: float

Massively Multimodal Deceptive Problem (MMDP)

A challenging binary problem with deceptive local optima, commonly used to assess an algorithm’s ability to escape local traps in a binary landscape.

class Mmdp[source]

Bases: AbstractProblem

Represents the Massively Multimodal Deceptive Problem (MMDP).

The MMDP is designed to deceive genetic algorithms by having multiple local optima. The problem is characterized by a chromosome length of 240 and a maximum fitness value of 40.

gen_type

Type of genes used in the problem (binary in this case).

Type:: GeneType

n_var

The number of design variables (240 for MMDP).

Type:: int

xl

The lower bound for the design variables (0 for binary genes).

Type:: float

xu

The upper bound for the design variables (1 for binary genes).

Type:: float

f(x: list) → float[source]: Evaluates the fitness of a given chromosome.

__init__()[source]: Initializes the MMDP problem with binary genes, 240 design variables, and predefined bounds.

f(x: List[int]) → float[source]

Evaluates the fitness of a given chromosome for the MMDP.

The fitness function is calculated based on the number of ones in each of the 40 subproblems, each of length 6.

Parameters:: x (List[int]) – A list representing the chromosome, where each element is a binary value (0 or 1).
Returns:: The normalized fitness value of the chromosome, rounded to three decimal places.
Return type:: float

One-Max Problem

A classic benchmark in binary optimization, where the objective is to maximize the number of ones in a binary string. This problem tests the algorithm’s ability to drive binary values towards an optimum.

class OneMax(n_var: int = 100)[source]

Bases: AbstractProblem

Represents the OneMax problem.

The OneMax problem is a simple genetic algorithm benchmark problem where the fitness of a chromosome is the sum of its bits.

gen_type

Type of genes used in the problem (binary in this case).

Type:: GeneType

n_var

The number of design variables (default is 100).

Type:: int

xl

The lower bound for the design variables (0 for binary genes).

Type:: float

xu

The upper bound for the design variables (1 for binary genes).

Type:: float

f(x: list) → float[source]: Evaluates the fitness of a given chromosome.

__init__(n_var: int = 100)[source]

Initialize the OneMax problem with a default number of variables (100) and binary gene bounds.

Parameters:: n_var (int, optional) – Number of design variables (default is 100).

f(x: List[int]) → float[source]

Evaluates the fitness of a given chromosome for the OneMax problem.

The fitness function is the sum of all bits in the chromosome.

Parameters:: x (List[int]) – A list representing the chromosome, where each element is a binary value (0 or 1).
Returns:: The fitness value of the chromosome, which is the sum of its bits.
Return type:: float

Peak Problem

A binary optimization problem featuring multiple peaks. This problem is suitable for evaluating an algorithm’s performance in a rugged binary landscape with multiple local optima.

class Peak(n_var: int = 100)[source]

Bases: AbstractProblem

Represents the Peak problem.

The Peak problem evaluates the fitness of a chromosome based on its distance to a set of target peaks.

gen_type

Type of genes used in the problem (binary in this case).

Type:: GeneType

n_var

The number of design variables (chromosome length, default is 100).

Type:: int

xl

The lower bounds for the design variables (0 for binary genes).

Type:: float

xu

The upper bounds for the design variables (1 for binary genes).

Type:: float

f(x: list) → float[source]: Evaluates the fitness of a given chromosome.

__init__(n_var: int = 100)[source]

Initialize the Peak problem with a default number of variables (100) and binary gene bounds.

Parameters:: n_var (int, optional) – Number of design variables (default is 100).

f(x: List[int]) → float[source]

Evaluates the fitness of a given chromosome for the Peak problem.

The fitness function calculates the distance between the given chromosome and a set of randomly generated target peaks.

Parameters:: x (list) – A list representing the chromosome, where each element is a binary value (0 or 1).
Returns:: The fitness value of the chromosome, normalized to a range of 0.0 to 1.0.
Return type:: float