# Sequential Memetic Algorithm Optimization for Allocation Planning in Hostelry Establishments
## 3 Sequential Optimization
### Chair Allocation Optimization
However, the design of these algorithms is an arduous task, as these methodologies must prove an equal exploration of the whole space of solutions in order to provide the diversity required for solving the problem [46]. Nevertheless, due to the limited and discontinuous feasible region of the MDP codification, the implementation of domain-specific MA is required to attain the desired solution. Therefore, in this paper, a novel crossover and mutation operator are proposed for attaining a constrained GA optimization of the MDP for the first time in the authors' knowledge. The proposed crossover operator, detailed in Algorithm 3, aims to provide a sufficient genetic drift without incurring excessive diversification, which could imperil the algorithm's convergence with the optimal solution. The proposed algorithm adapts the multiple-point crossover operator into a variable segmentation process for operating within the constant number of restrictions [47]. The algorithm starts by initializing the new population of individuals, defined as offspring, which share the codification of the old population but are initialized with all zeros. For each pair of individuals within the population and the offspring (i.e., the progenitors and descendants), the algorithms trace different segments for reallocating the bits within the fathers to the descendants. Each segment is determined by its origin point, its length, and its final point. The origin point is determined randomly among each possible bit position that has not been selected or that has been in a previous segment. The length of the segment is calculated through the following equation in order to avoid overflow of the parents' descendants with their own:  
\[L=min\{N-max\{\sum D_{1},\sum D_{2}\},L_{0}\} \tag{15}\]  
where \(L\) is the segment length; \(N\) is the number of chairs (i.e., the total number); \(D_{1}\) and \(D_{2}\) represent the two formed descendants from each pair of progenitors, with the binary codification proposed for the CLP and \(L_{0}\) being a hyperparameter for initializing the default length. Once setting the origin point and length of the segment, the end point is deduced from the individual bit positions, as represented in Figure 6.  
```
1 Offspring \(\leftarrow\) Initialize the offspring population and null values;
2 for(Father\({}_{1}\), Father\({}_{2}\)), (Child\({}_{1}\), Child\({}_{2}\)) in Population, Offspringdo
3 whilemax(sum(Child\({}_{1}\)), sum(Child\({}_{2}\)) \(<\) Chair Numberdo
4 Segment Length \(\leftarrow\) min(ChairNumber \(-\) max(sum(Child\({}_{1}\)), sum(Child\({}_{2}\))), Default Length);
5 Segment Origin \(\leftarrow\) Random, available position within the Fathers;
6 Segment End \(\leftarrow\) Finish position of segment, surpassing any discontinuities derived from previous segments or the Fathers length (Segment Origin, Segment Length);
7 Pass bits within the Segment from Fathers to Children, the assignment order is determined from a random variable. The Segment positions are now restricted;
8
9 end for
10 if\(min(sum(Child\({}_{1}\)), sum(Child\({}_{2}\)) \(<\) Chair Numberthen
11 Pending Child \(\leftarrow\) Select the Child with the least number of ones;
12 Pending Child(where(\(abs\)(Father\({}_{1}\) - Father\({}_{2}\)) \()\) \(=\) 1) \(\leftarrow\) 1;
13 whilesum(Pending Child) \(<\) Chair Numberdo
14 Random Father \(\leftarrow\) Random selection of Fathers;
15 Bit Position \(\leftarrow\) Random choice from where(\(abs\)(PendingChild\({}_{1}\) - RandomFarther)) \(==\) 1;
16
17 Pending Child(Bit Position) \(\leftarrow\) 1;
18
19 end while
20
21 end while
```  
**Algorithm 3**Pseudocode of the variable segmentation-designed crossover operator for the CLP optimization (_Population_, _Num Chairs_). The segment advances through each individual binary codification in a given direction, each bit representing a unit of length. The segment may surpass previously segmented bits and can link the end and the beginning of the genotype.