S-PUT - Data Storage for Social Networks: A Socially Aware Approach - page 29

in METIS; a different assignment can be obtained by using a different value for the
seed. This set of assignments is used to populate the first generation of EA. The
cardinality of this set is equal to the “population size,” an input parameter for the
EA process, explained in what follows.

3.2.2 Final Partitioning

EA is an iterative process of generations, starting with an initial population in the
first generation and iteratively improving the population from one generation to
the next. The evolution of the population is driven by three main mechanisms:
recombination, mutation, and selection. Recombination and mutation create the
necessary diversity, thus facilitating novelty in the population. After recombination
and mutation, a selection step takes places to select the best-quality individuals for
the next-generation's population. A fitness function is used to determine the quality
of each individual.
Among many evolutionary algorithms, the Non-dominated Sorting Genetic
Algorithm-II (NSGA-II) [ 10 ] and Strength Pareto Evolutionary Algorithm 2 (SPEA2)
[ 40 ] are de facto for solving multi-objective optimization problems. Although either
can work in S-PUT for its evolution process, here we describe this process using
SPEA2, which we have evaluated with some encouraging preliminary results.
Using SPEA2 as EA for the partitioning problem, a population is represented by a
set of individuals, each being a base-M string of length N , s 1 s 2 :::s N , representing
a possible partition assignment: user i is assigned to server s i . For example, for a
network of 1,000 nodes to be partitioned across 16 servers, an individual is an array
of 1,000 integers, each having a value between 0 and 15. For the recombination
mechanism, which creates two new individuals, called offsprings, replacing two
parent individuals selected randomly from the current population, we use the Two-
Point Recombination Mode (the other modes provided by SPEA2 are One-Point
Recombination and Uniform Recombination). Suppose that the two parents are
s 1 s 2 :::s N and s 1 s 2 :::s 0 N . First, two random positions in the string are chosen, i
and j (1<i <j <N). Then, the offsprings are s 1 :::s i 1 s i :::s j s j C 1 :::s N
and s 1 :::s i 1 s i :::s j s j C 1 :::s 0 N . For the mutation mechanism, a new offspring
is created replacing a parent individual by assigning a random value to each of a
number of random positions in the parent array. Hence, an offspring of s 1 s 2 :::s N
can be s 1 ::s i 1 ts i C 1 :::s N if one bit needs to be mutated, where i 2 Œ1; N and
t 2 Œ0; M 1 are both chosen at random. When applied to a population of size si z e,
the number of parent couples in the recombination step and the number of single
parents in the mutation step are size p recombination and size p mutation , respectively,
where p recombination and p mutation are probabilities given as input parameters to the
EA. For mutation, the number of bits (i.e., genes in biological terminology) that
need mutating is N p gene mutation where p gene mutation is another probability serving

as input for the EA.