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(design_variables=20)[source]

Bases: AbstractProblem

CountSat function implementation for optimization problems.

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

design_variables

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

Type:

int

bounds

The bounds for each binary variable, typically [(0, 1), (0, 1), …] for binary inputs.

Type:

list of tuple

objectives

Number of objectives, set to 1 for single-objective optimization.

Type:

int

f(x: list) → float[source]

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

__init__(design_variables=20)[source]

Initialize the problem with variables, bounds, objectives, and constraints.

Parameters:

  • design_variables (int or List[str]) – If an integer, it specifies the number of design variables. If a list of strings, it specifies the names of design variables.

  • bounds (List[Tuple[float, float]]) – Bounds for each design variable as (min, max).

  • objectives (str, int, or List[str]) – Objectives for optimization, e.g., “minimize” or “maximize”.

  • constraints (str, int, or List[str], optional) – Constraints for the problem (default is an empty list).

evaluate(x, out, *args, **kwargs)[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) → 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

ECC Problem

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(design_variables=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.

design_variables

Number of binary variables, typically 144.

Type:

int

bounds

Bounds for each variable, typically [(0, 1)] * 144 for binary inputs.

Type:

list of tuple

objectives

Number of objectives, set to 1 for single-objective optimization.

Type:

int

__init__(design_variables=144)[source]

Initialize the problem with variables, bounds, objectives, and constraints.

Parameters:

  • design_variables (int or List[str]) – If an integer, it specifies the number of design variables. If a list of strings, it specifies the names of design variables.

  • bounds (List[Tuple[float, float]]) – Bounds for each design variable as (min, max).

  • objectives (str, int, or List[str]) – Objectives for optimization, e.g., “minimize” or “maximize”.

  • constraints (str, int, or List[str], optional) – Constraints for the problem (default is an empty list).

f(x: list) → float[source]

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

Parameters:

x (list) – A list of binary variables.

Returns:

The ECC function value, rounded to four decimal places.

Return type:

float

Fletcher-Powell (FMS) Binary Problem

A binary version of the Fletcher-Powell function, used to evaluate robustness and efficiency in finding optimal solutions within a binary space.

class Fms(design_variables=192, bounds=[(0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1)], objectives=1)[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.

design_variables

The number of variables for the problem.

Type:

int

bounds

The bounds for each variable.

Type:

list of tuple

objectives

Number of objectives, set to 1 for single-objective optimization.

Type:

int

f(x: list) → float[source]

Calculates the FMS function value for a given list of variables.

Notes

Length of chromosomes = 192 Maximum Fitness Value = 0.01 Maximum Fitness Value Error = 10^-2

__init__(design_variables=192, bounds=[(0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1)], objectives=1)[source]

Initialize the problem with variables, bounds, objectives, and constraints.

Parameters:

  • design_variables (int or List[str]) – If an integer, it specifies the number of design variables. If a list of strings, it specifies the names of design variables.

  • bounds (List[Tuple[float, float]]) – Bounds for each design variable as (min, max).

  • objectives (str, int, or List[str]) – Objectives for optimization, e.g., “minimize” or “maximize”.

  • constraints (str, int, or List[str], optional) – Constraints for the problem (default is an empty list).

evaluate(x, out, *args, **kwargs)[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) → float[source]

Calculate the FMS function value for a given list of 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

f(x: list) → float[source]

Calculates the fitness value of a given chromosome for the Maxcut problem.

__init__()[source]

Initialize the problem with variables, bounds, objectives, and constraints.

Parameters:

  • design_variables (int or List[str]) – If an integer, it specifies the number of design variables. If a list of strings, it specifies the names of design variables.

  • bounds (List[Tuple[float, float]]) – Bounds for each design variable as (min, max).

  • objectives (str, int, or List[str]) – Objectives for optimization, e.g., “minimize” or “maximize”.

  • constraints (str, int, or List[str], optional) – Constraints for the problem (default is an empty list).

f(x: list) → float[source]

Calculates the fitness value of a given chromosome for the Maxcut problem.

Parameters:

x (list) – A list representing a chromosome.

Returns:

The fitness value of the chromosome.

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(design_variables=20, bounds=None, objectives=1)[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.

__init__(design_variables=20, bounds=None, objectives=1)[source]

Initialize the problem with variables, bounds, objectives, and constraints.

Parameters:

  • design_variables (int or List[str]) – If an integer, it specifies the number of design variables. If a list of strings, it specifies the names of design variables.

  • bounds (List[Tuple[float, float]]) – Bounds for each design variable as (min, max).

  • objectives (str, int, or List[str]) – Objectives for optimization, e.g., “minimize” or “maximize”.

  • constraints (str, int, or List[str], optional) – Constraints for the problem (default is an empty list).

evaluate(x, out, *args, **kwargs)[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) → 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(design_variables=20, bounds=None, objectives=1)[source]

Bases: AbstractProblem

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

This class is used to evaluate 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) → float[source]

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

__init__(design_variables=20, bounds=None, objectives=1)[source]

Initialize the problem with variables, bounds, objectives, and constraints.

Parameters:

  • design_variables (int or List[str]) – If an integer, it specifies the number of design variables. If a list of strings, it specifies the names of design variables.

  • bounds (List[Tuple[float, float]]) – Bounds for each design variable as (min, max).

  • objectives (str, int, or List[str]) – Objectives for optimization, e.g., “minimize” or “maximize”.

  • constraints (str, int, or List[str], optional) – Constraints for the problem (default is an empty list).

evaluate(x, out, *args, **kwargs)[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) → 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

Multi-modal 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.

design_variables

Names of the design variables (in this case, binary chromosome genes).

Type:

List[str]

bounds

Bounds for each design variable (0 or 1).

Type:

List[Tuple[float, float]]

objectives

Objectives for optimization, e.g., “maximize” in this case.

Type:

List[str]

constraints

Any constraints for the optimization problem.

Type:

List[str]

f(x: list) → float[source]

Evaluates the fitness of a given chromosome.

Notes

# Length of chromosomes = 240 # Maximum Fitness Value = 40

__init__()[source]

Initializes the MMDP problem with predefined design variables, bounds, objectives, and constraints.

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(design_variables: int = 100, bounds: List[Tuple[float, float]] = [(0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1)], objectives: List[str] = ['maximize'], constraints: List[str] = [])[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.

design_variables

Number of design variables (chromosome length).

Type:

int

bounds

Bounds for each design variable as (min, max).

Type:

List[Tuple[float, float]]

objectives

Objectives for optimization, e.g., “maximize”.

Type:

List[str]

constraints

Any constraints for the optimization problem.

Type:

List[str]

f(x: list) → float[source]

Evaluates the fitness of a given chromosome.

__init__(design_variables: int = 100, bounds: List[Tuple[float, float]] = [(0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1)], objectives: List[str] = ['maximize'], constraints: List[str] = [])[source]

Initialize the OneMax problem with default design variables, bounds, objectives, and optional constraints.

Parameters:

  • design_variables (int, optional) – Number of design variables (default is 100).

  • bounds (List[Tuple[float, float]], optional) – Bounds for each design variable in (min, max) format (default is [(0, 1)] * 100).

  • objectives (List[str], optional) – Objectives for optimization, e.g., “maximize” (default is [“maximize”]).

  • constraints (List[str], optional) – Constraints for the problem (default is an empty list).

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[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.

design_variables

Names of the design variables.

Type:

List[str]

bounds

Bounds for each design variable as (min, max).

Type:

List[Tuple[float, float]]

objectives

Objectives for optimization, e.g., “minimize” or “maximize”.

Type:

List[str]

constraints

Any constraints for the optimization problem.

Type:

List[str]

f(x: list) → float[source]

Evaluates the fitness of a given chromosome.

Notes

# Length of chromosomes = 100 # Maximum Fitness Value = 1.0

__init__()[source]

Initializes the Peak problem with default values.

evaluate(x, out, *args, **kwargs)[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]

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