# Sequential Memetic Algorithm Optimization for Allocation Planning in Hostelry Establishments
## 3 Sequential Optimization
### Table Distribution Optimization
The cycle of the fitness evaluation and these operators constitute the basic GA optimization, which is complemented in this paper with a specifically designed local search for the TLP, which takes place when certain criteria (i.e., probabilistic, or sequential activation) are met, thus resulting in the proposed LS MA. The proposed local search aims to intensify a reduced sample of individuals from the population set, improving the fitness value of these individuals through a GBLS (Gradient-Based Local Search) procedure [33], thus guiding the optimization into achieving the desired solution. The selection of the local search individuals is performed over a certain pool of individuals from the base population that consists of a combination of the best-adapted individuals and random selections, thus attaining a diverse and elitist sample of the population [34]. From this initial pool, the local search individuals are selected by analyzing the improvement potential of each drafted individual. The improvement potential of each table distribution is measured by the intensity parameter, described through the following expression:  
\[I_{i}=C_{1}\ \delta+C_{2}\ \mu+C_{3}\ n^{-1} \tag{11}\]  
where \(I_{i}\) represents the intensity of the individual \(i\); \(C_{1}\), \(C_{2}\), and \(C_{3}\) are co-factors obtained experimentally, as stated in [35]; \(\delta\), \(n\) and \(m\) are contained within the memory chains of each individual and represent, respectively, the fitness improvement of the last LS, the number of times that the individual have been improved, and the improvement viability, measured as  
\[\mu=\rho\ \sum m_{j}; \tag{12}\]  
where \(\rho\) is the table-moving step and \(m_{j}\) the number of table movements performed within the LS execution \(j\). The memory chains are initialized in default values (i.e., null \(\delta\), \(n\), \(\rho\), \(m\)) at the start of the optimization and are then updated within the LS procedure. Individuals that undergo any alteration in the mutation operator have their memory chains reinitialized; the same procedure is applied to the novel individuals generated in the crossover function. However, preserved individuals in the proposed methodology conserve their memory chains, thus enhancing the LS individual's selection. Once the individuals have been selected, the GBLS is performed for each of the local search individuals, intensifying the respective table distributions through the methodology described in Figure 4.  
The purpose of the GBLS for the TLP is to improve the table distribution by introducing multiple small movements in certain table positions. Each movement is performed based on a step size \(\rho\) and a movement direction. The obtention of the optimal movement direction for each chair constitutes a significant challenge, the presence of obstacles, the minimum distance restriction, and the exceeding number of possible configurations of distributions threaten the viability of any exact procedure [16]. Therefore, an iterative approach is proposed where the direction of movement is computed locally for a single table through the distance gradient of the utmost proximate table:  
\[\
abla d_{i,j}=\left(\frac{x_{i}-x_{j}}{K_{i,j}},\frac{y_{i}-y_{j}}{K_{i,j}}\right) \tag{13}\]  
where \(\
abla d_{i,j}\) obtains the gradient direction from table \(j\) to table \(i\). The resulting direction of movement increases the minimum distance separation of the moved table \(i\) until the minimum distance is measured to another adjacent table \(k\), different from \(j\). Following Figure 4, the iterative algorithm will evaluate the gradient with table \(k\), increasing the minimum distance until a certain number of movements are performed or until the result position is repeated from previous steps. Moreover, the GBLS also aims to assist the table distribution in evading obstacles. When the moving table \(i\) is located within an obstacle, the algorithm computes the gradient for obtaining the direction that distances the table from the obstacle until the table evades the obstacle.