Implementation of an Evolutionary Computing approach to the Multiway Number Partitioning problem.

Let $k$ be a positive integer and $\bar{x} = {x_1, \ldots, x_n}$ a non-empty list of positive numbers. A $k$-partition of $\bar{x}$ consists of $k$ lists (blocks), $\bar{y}^1 = {y_1^1, \ldots, y_{n_1}^1}$, $\bar{y}^2 = {y_1^2, \ldots, y_{n_2}^2}$, $\ldots$, $\bar{y}^k = {y_1^k, \ldots, y_{n_k}^k}$, such that:

• the concatenation of the blocks, ${y_1^1, \ldots, y_{n_1}^1, y_1^2, \ldots, y_{n_2}^2, \ldots, y_1^k, \ldots, y_{n_k}^k}$, is a permutation of the original list $\bar{x}$;
• and, in particular, $n_1 + n_2 + \ldots + n_k = n$.

A $k$-partition $\bar{y}^1$, $\bar{y}^2$, $\ldots$, $\bar{y}^k$ is said to be perfect if all its blocks have the same sum:

$$\sum \bar{y}^1 = \sum \bar{y}^2 = \ldots = \bar{y}^k = \frac{\sum \bar{x}}{k} = \textrm{perf}(\bar{x}, k).$$

1. The list ${1,1,1,1,2,5,5,8}$ admits the perfect $3$-partition: ${5,1,1}$, ${2,5,1}$, ${8}$, where each block sums to $8$;
2. The list ${3,4,5,6}$ does not admit any perfect $3$-partition, but admits a perfect $2$-partition composed by the blocks ${3,6}$, ${4,5}$.

This problem is known to be NP-complete.

In this repository, we implemented (in Mathematica) an algorithm that computes a solution (exact or approximate) for the aforementioned problem by resorting to an evolutionary computing approach.

Given $k$ and $\bar{x}$, we simulate the evolution of a population initially composed of NInd individuals until the moment TFim. Each individual is a $k$-partition of $\bar{x}$. The evolution of the population will depend on the fitness of the individuals, which will be maximal in the case of a perfect $k$-partition of $\bar{x}$. The program terminates by exhibiting the exact solution (if it is found at some point of the evolution process) or the best approximate solutions in the final population of the simulation.

During the simulation, the population evolves through 3 processes: mutação, reprodução and morte, modeled by random laws that depend on the parameters TMut, TRep, TMor (respectively).

Each individual:

• has a unique identifier and there may be more than one individual with the same $k$-partition;
• stores the information about its perfect blocks (whose sum is $\textrm{perf}(\bar{x}, k$) and of the time instant in which those blocks were formed.

Unsuitability Coefficient:

Instead of using a fitness function that we want to maximize, we use an unsuitability coefficient (UC) that we want to minimize. For a given individual, at a given time instant, whose $k$-partition is composed by the blocks $\bar{y}^1$, $\bar{y}^2$, $\ldots$, $\bar{y}^k$, then we have:

$$UC = \frac{\sum_{i=1}^k |\bar{y}^i - \textrm{perf}(\bar{x}, k)|}{k}.$$

Initialization:

At the beginning of the simulation, each individual in the initial population is associated with a random $k$-partition. This random $k$-partition is generated by randomly assigning (following an uniform distribution) each element of $\bar{x}$ to a block (from $1$ to $k$).

Evolutionary Events:

• Mutação (mutation, in English): of each individual, whose frequency is an exponential random variable with expected value TMut, and whose occurrence changes the individual's partition in the following way:

  • Pick randomly and uniformly two blocks $\bar{y}^&gt;$ and $\bar{y}^&lt;$ of the current partition such that $\sum \bar{y}^> > \textrm{perf}(\bar{x}, k)> \sum \bar{y}^<$;
  • Compute $\textrm{dif} = \sum \bar{y}^> - \sum \bar{y}^<$;
  • Pick randomly and uniformly a value $x$ from $\bar{y}^>$;
  • Pick randomly and uniformly sucessive values $x'$ from $\bar{y}^&lt;$ while there are values in the block not selected yet and the sum of all the $x'$ is inferior to $x-\frac{\textrm{dif}}{2}$;
  • The value $x$ is transferred to the block $\bar{y}^&lt;$ and all the values $x'$ are transferred to $\bar{y}^&gt;$.

• Reprodução (reproduction, in English): from individuals pai (father) and mãe (mother) randomly and uniformly picked from the population, whose frequency is an exponential random variable with expected value TRep, and whose occurrence results in the nascimento (birth) of a new individual; this new individual is added to the population according to the following rules:

  • In the case in which the pai's $k$-partition does not contain any perfect block, the event has no event (there is no nascimento); otherwise, pick randomly and uniformly one of the pai's perfect blocks;
  • If the selected pai's perfect block can not be reconstructed with the elements from the mãe's imperfect blocks, the event has no effect (there is no nascimento); otherwise, the reprodução generates to a filho (child), whose $k$-partition contains the pai's perfect block and all the mãe's perfect blocks; the remaining elements of $\bar{x}$ are randomly and uniformly distributed by the available blocks;
  • The formation instants of the perfect blocks from the parents are kept by the filho.

• Morte (death, in English): global, whose frequency is an exponential random variable with expected value TMor, and whose occurrence results in the simultaneous elimination of all the individuals in the population:

  • whose $k$-partition has at least one perfect block;
  • whose most recent perfect block has an age greater than twice the formation instant of its oldest perfect block.

  In the case of getting an empty population after this event, it is repopulated with random individuals obtained just as in the initial population.

The main script is Simulador.nb. The several objects that the main script makes use of are in remaining ".m" files (CAP.m, Eventos.m, ExponencialAleatória.m, Indivíduos.m, Partição.m and População.m).

We apologize for having the variable names in Portuguese. We hope that their translation here helps in its understanding.