# Fragile Watermarking of 3D Models in a Transformed Domain
## 4 Genetic Algorithms  
A Genetic Algorithm (GA) is a computing paradigm that simulates, in a simplified manner, the evolution and selection processes of natural species.  
It may be used in solving non-linear optimizations problems when they may be coded in a set of parameters, and it is possible to define a function, called the fitness (function), that measures how close a solution is to the optimum.  
A set of instantiated parameters describing the problem at hand is called the individuals: these parameters are put in a sequence similar to a chromosome, which is distinctive for its individual and defines it. Moreover, a fitness function is defined to evaluate the quality of the individual in terms of approximating the optimal solution.  
A set of individuals, i.e., a population, is evolved in a way similar to the development of natural species. They mate, reproduce, and possibly have random modifications of their genes.  
A chromosome codes a sequence of parameters, typically binary or integer numbers or a mix of them (but any type of data could be used in principle) with the constraint that the operations on them keep the data types consistent in the resulting chromosomes.  
A population of individuals is created and (randomly) initialized; in general, a population of a hundred chromosomes is considered adequate.  
Then, the GA goes through an iterative process, and in every cycle, the population is evolved according to the following steps:  
* selection: pairs of individuals are mated for the following reproduction operation; individuals may be selected randomly or given priority depending on fitness; many strategies can be adopted, like roulette wheel or tournament selection [22];
* crossover: the previously selected pairs of chromosomes are mated by exchanging some (homologous) parts of their chromosomes with probability \(p_{c}\); one or more \"cutting\" points are randomly chosen, and the genes between pairs of such points are exchanged to define two new offspring;
* mutation: with the aim of better exploring the solution space, each chromosome is mutated with probability \(p_{m}\); mutation is performed by choosing at random one of the parameters coded in the chromosome and altering it by a random quantity;
* population update: to generate a new population and to keep the number of individuals constant, a selection among the individuals in the set composed by the old population and the new offspring should be performed; many different strategies could be adopted, e.g., two individuals in the set are randomly chosen, and the one with the best fitness is moved to the new population, repeating this process until the output population reaches the desired cardinality.  
The described cycle is performed until a termination condition is met. In general, to avoid infinite cycles, an upper limit to the number of generations is fixed. Furthermore, the cycle may be terminated when at least one of the individual's fitness drops below (in this case, the lower the fitness, the better the individual) a pre-defined threshold. In both cases, the GA returns the best individual, representing the near-optimal solution it was able to find. For a deeper insight into GAs, see [22; 23].  
As will be shown in the following Section 5, to minimize the embedding noise due to watermark embedding, the watermark bits are stored, modifying the less significant part of the floating point numbers representing the 3D model vertex coordinates. This is obtained by considering the bytes encoding these floating point numbers as unsigned integers and changing the less significant bytes. This mode of operation results in a minimization problem in a non-linear space, a task where GAs, among other algorithms, are flexible and efficient to implement and apply.