# Genetic Algorithm for the Retailers' Shelf Space Allocation Profit Maximization Problem
## 5 Genetic Algorithm
### Mutation  
The above recombination process generates new sets of chromosomes by taking the high-quality genes from the parent population. The mutation process creates a new gene in the existing chromosome. In the current GA, there are nine mutation techniques, all of which are applied to the individual selected according to the mutation rate.  
In the explanation below, the terms \"all shelves\" and \"all products\" mean that all shelves and all products may be mutated, but the number of changes is limited by the mutation repetition number in the settings, i.e., not all shelves and all products will be mutated because this could destroy the solution. Therefore, before the mutation, the shelf list and product list are randomized so that they start at different places in the chromosome, thus only a few genes are mutated, not all of them. Changes in a product's facings number trigger a recalculation of its cappings and nestings. After addition, the total number of facings cannot exceed \(f_{j}^{\max}\), and the total number of facings after deletion cannot be less than \(f_{j}^{\min}\). Products on which correct modifications cannot be executed so that \(f_{ij}=\left\{f_{j}^{\min}\dots f_{j}^{\max}\right\}\), are omitted.  
The nine mutation algorithms are:  
* Mutation 1 swaps the minimum and maximum facings between products on all shelves. This action is repeated a predefined number of times (choosing max\(\leftrightarrow\)min, second-max\(\leftrightarrow\)second-min, third-max\(\leftrightarrow\)third-min, and so on). Individuals are mutated in accordance with the mutation rate. Next, the minimum and maximum numbers of product facings on the shelf are chosen. The products with the least facings on this shelf increase their facings to the maximum value, and the products with the most facings reduce their facings to the number of the previously found minimum. Swapping facings also includes swapping that product's cappings and nestings, i.e., cappings and nestings are recalculated according to the new facings number.
* Mutation 2 reverses the number of facings of all products (the predefined number of products) on all shelves around. The first product takes the number of facings, cappings and nestings of the last product, and the last product takes the number of facings, cappings and nestings of the first one.
* Mutation 3 left rotates the number of facings, cappings, and nestings of all products (the predefined number of products) on all shelves around the randomly selected product number.  
* Mutation 4 swaps shelves for those products that can be placed on other shelves. This is repeated a predefined number of times, equal to the number of the swapped products.
* Mutation 5 deletes one facing without capping and adds one facing to the products where capping may be placed on all shelves for all products (the predefined number of products).
* Mutation 6 deletes one facing where the numbers of facings equal the upper bound and adds one facing where the numbers of facings equal the lower bound on all shelves for all products (the predefined number of products).
* Mutation 7 is a modification of Mutation 6 that selects not one but a randomly selected number of facings in the diapason \(\left\{1\ldots f_{j}^{\max}-f_{ij}\right\}\) for addition and \(\left\{1\ldots f_{ij}-f_{j}^{\min}\right\}\) for deletion.
* Mutation 8 selects the products with the maximum number of facings on the shelf, deletes one facing from all of them (obviously where \(f_{ij}-1\geq f_{j}^{\min}\)), selects the same number of products in their non-decreasing number of facings order on the same shelf, and adds one facing to them where \(f_{ij}+1\leq f_{j}^{\max}\).
* Mutation 9 is a reversed version of Mutation 8. It selects the products with the minimum number of facings on the shelf, adds one facing to all of them where \(f_{ij}+1\leq f_{j}^{\max}\)selects the same number of products in their non-increasing number of facings order on the same shelf, and deletes one facing from all of them where \(f_{ij}-1\geq f_{j}^{\min}\).