# Genetic Algorithm for the Retailers' Shelf Space Allocation Profit Maximization Problem
## 5 Genetic Algorithm
### Improvement
#### 5.6.2 Shelf Profit Increasing  
This part uses general steps in order to increase shelf profit. In this part of the paper, the following notation will be used:  
* \(a_{i}\)--the ratio of the shelf \(i\) (\(i=1,\dots,S\)).
* \(a_{j}\)--the ratio of the product\(j\) (\(j=1,\dots,P\)).  
In the increasing shelf profit step, the improvement procedure is modified as follows:  
1. Select the shelf with the lowest shelf ratio.  
Shelf ratio equals:  
\[a_{i}=\frac{\sum\limits_{j=1}^{p}u_{j}(f_{ij}+c_{ij}+n_{ij})}{s_{i}^{I}}\]  
Product ratio which is placed on this shelf equals:  
\[a_{j}=\frac{u_{j}}{w_{j}}\]  
If there is no improvement of the GA fitness function on the last step, select any regular shelf except the shelf which was under improvement on the previous step.  
Bad products are \(a_{j}\leq a_{i}\).  
Good products are \(a_{j}>a_{i}\).  
Apply the appropriate product movement between shelves in order to increase the shelf ratio \(a_{i}\).  
Remove duplicates from the set of generated solutions.  
Evaluate the set of solutions.  
In the free shelf space reduction step, the improvement procedure is modified as follows:  
Select the shelf with the lowest total products width (maximum free space on the shelf).  
If there is no improvement of the GA fitness function in the last step, select any regular shelf except the shelf which was under improvement in the previous step. Compare the product width with the average products width on the shelf.  
Bad products are \(w_{j}>\frac{\sum\limits_{j=1}^{p}x_{ij}w_{j}}{\sum\limits_{j=1}^{p}x_{ij}}\).  
Good products are \(w_{j}\leq\frac{\sum\limits_{j=1}^{p}x_{ij}w_{j}}{\sum\limits_{j=1}^{p}x_{ij}}\).  
Apply the appropriate product movement between shelves in order to reduce free shelf space.  
Remove duplicates from the set of generated solutions.  
Evaluate the set of solutions.  
Evaluation and correction is performed as follows. First, the algorithm deletes the redundant product item from the shelves where the constraints are not met. Next, it adds missing product items to the shelves where values are less than the lower bound. Later, it adds as many items as possible, where the criteria are met, based on the selected algorithm.  
Suppose the GA fitness function is not improved compared to the previous step. In that case, a set of different individuals is generated by the pallet-like recursive algorithm, which is added to the solution set. For this reason, distinct product to shelf allocation variants is used. Next, a part of the obligatory set of product items is extracted, reducing the remaining space on the shelf. The remaining space on the shelf and the remaining part of the set of products are processed recursively like a pallet. Next, the solution is corrected. A set of solutions generated by all the list algorithms is also added to the individuals set. In ordinary cases, where GA fitness function is improved on each step, solutions are corrected only via HUPWDR-F1 algorithm. At each step, it is possible for excess solutions to be generated. Therefore, duplicates and the least profitable solutions are excluded from the set, in order not to waste time on correcting them, the necessary number of possible solutions are generated on the improvement step steering by the GA parameters.  
Inside the improvement procedure, evaluation is based on the shelf ratio to the shelf length:  
\[\max\sum_{i=1}^{S}\frac{\sum\limits_{j=1}^{P}u_{j}(f_{ij}+c_{ij}+n_{ij})}{s_{i}^ {l}}\]  
However, when the improved procedure has finished generating the solution set, the evaluation is based on the shelf ratio to the actually occupied space on the shelf.  
\[\max\sum_{i=1}^{S}\frac{\sum\limits_{j=1}^{P}u_{j}(f_{ij}+c_{ij}+n_{ij})}{\sum \limits_{j=1}^{P}w_{j}}\]  
After the solution correction, the evaluation is performed using the total profit on all shelves.  
\[\max\sum_{i=1}^{S}\sum\limits_{j=1}^{P}u_{j}(f_{ij}+c_{ij}+n_{ij})\]