# A Hybrid Discrete Memetic Algorithm for Solving Flow-Shop Scheduling Problems
## 4 Discrete Bacterial Memetic Evolutionary Algorithm (DBMEA)
### Steps of the Bacterial Mutation Procedure  
The bacterial mutation operates on the whole population [64]. The number of segments derives from the length of a bacterium and the length of the segment:  
\[N_{seg}=\left\lfloor\frac{|P_{0}|}{I_{seg}}\right\rfloor \tag{8}\]  
The number of segments equals the lower bound of a bacterium's length divided by the segment's length. For all of the permutations of the population, a random number \(r,\ r\in[0;1]\) is chosen. If this random number is below the coherent segment loose rate \(R\), the bacterium undergoes a coherent segment mutation; if it is greater than or equal to this value, the bacterium is operated on by a loose segment mutation. Each mutation algorithm is called on a bacterium \(N_{seg}\) times. The segment length shifts the segments for the coherent segment mutation in each iteration. Every part of the bacterium is mutated. Noshifting is needed for the loose segment mutation since its random permutation generation provides an even distribution of segments across the bacterium. The original bacterium gets overridden if the mutation algorithm generates a better alternative. * \(P\): the population consisting of permutations;
* \(P_{0}\): the first bacterium of the population;
* \(N_{mutants}\): the number of mutants generated for each mutation operation;
* \(I_{seg}\): the length of the segment to be mutated;
* \(N_{seg}\): the number of segments for each bacterium;
* R: the cohesive/loose rate;
* \(x\): an element of \(P\) population;
* \(x^{\prime}\): a mutant of \(x\);
* \(f\): the objective function. ```
\(P\) = createRandomPopulation(\(N_{ind}\)) \(x^{*}=\min\{f(x_{i}):x_{i}\in P\}\) \(N_{notImp}=0\) while\(N_{notImp}<N_{term}\)do \(P^{\prime}=bacterial Mutation(P,N_{mutants},I_{seg})\) \(P^{\prime\prime}=localSearch(P^{\prime})\) \(P^{\prime\prime\prime}=geneTransfer(P^{\prime\prime},N_{inf},I_{trans})\) \(x=\min\{f(x_{i}):x_{i}\in P^{\prime\prime\prime}\}\) if\(x<x^{*}\)then \(x^{*}=x\) else \(N_{notImp}=N_{notImp}+1\) endif \(P=P^{\prime\prime\prime}\) endwhile return\(x^{*}\)
```  
**Algorithm 1** Discrete bacterial memetic algorithm  
Figure 5 shows how cohesive segments are chosen for mutation. The segment gets shifted across the entire bacterium without overlap. The starting index of the segment is calculated with the following equation:  
\[S_{seg}=i\cdot I_{seg} \tag{9}\]  
The entire bacterium gets optimized locally. In Figure 4(a), we see the first iteration when the iteration counter is 0. The segment starts at the first element of the permutation (index 0). Therefore, if the segment length is 3, the cohesive segment on which the algorithm operates is the first three elements of the permutation. For the next segment, the iteration counter is increased by one. Thus, the segment under mutation starts at the fourth element of the permutation (index 3). We continue this process until we run out of whole segments with \(I_{seg}\) lengths. Figure 4(d) illustrates all the cohesive segments chosen in Algorithm 2, if \(|x|=9\) and \(I_{seg}=3\). ```
\(N_{seg}=\lfloor\frac{P_{0}}{l_{seg}}\rfloor\) for all\(x\) in \(P\)do \(r=\) random number between 0 and 1 if\(r<k\)then for\(i=0\) to \(N_{seg}\)do \(S_{seg}=l_{seg}\cdot i\) \(x^{\prime}=\) coherentSegmentMutation(\(x\), \(S_{seg}\), \(l_{seg}\), \(N_{mutants}\)) if\(f(x^{\prime})<f(x)\)then \(x=x^{\prime}\) endif endfor else for\(i=0\) to \(N_{seg}\)do \(x^{\prime}=\) looseSegmentMutation(\(x\), \(l_{seg}\), \(N_{mutants}\)) if\(f(x^{\prime})<f(x)\)then \(x=x^{\prime}\) endif endfor endif endfor return\(P\)
```  
**Algorithm 2** Bacterial mutation process  
Algorithm 3 depicts the process of coherent segment mutation. This operation is applied to an individual element of the population. In total, the \(N_{mutants}\) number of mutants is generated by changing the order of elements in a given coherent segment. \(S_{seg}\) is the index where the segment starts. \(l_{seg}\) is the length of the segment. \(x\) is the bacterium on which the mutation occurs.