# 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 first mutant has its segment reversed compared to the original. All the other variations have this segment shuffled randomly. Out of all the variations along with the original bacterium \(x\), the best one according to the fitness function \(f\) is chosen and returned. This operation is a simple local search applied to parts of the bacterium. * \(x\): the bacterium to be mutated;
* \(S_{seg}\): the index, where the segment starts;
* \(I_{seg}\): the length of the segment;
* \(x_{r}\): the first bacterium, where the segment is reversed;  
Figure 5: Cohesive segments chosen in Algorithm 2. (**a**) Chosen segment, when \(S_{seg}=l_{seg}\cdot i=0\); (**b**) chosen segment, when \(S_{seg}=l_{seg}\cdot i=3\); (**c**) chosen segment, when \(S_{seg}=l_{seg}\cdot i=6\); and (**d**) all the segments chosen throughout the algorithm. * \(x^{\prime}\): a mutated bacterium;
* \(f\): the objective function. ```
\(x_{r}=\text{reverseSegment}(x\), \(S_{seg}\), \(S_{seg}+I_{seg})\) if\(f(x_{r})<f(x)\)then \(x=x_{r}\) endif for\(i=0\) to \(N_{mutants}-1\)do \(x^{\prime}=\text{shuffleSegment}(x\), \(S_{seg}\), \(S_{seg}+I_{seg})\) if\(f(x^{\prime})<f(x)\)then \(x=x^{\prime}\) endif endfor return\(x\)
```  
**Algorithm 3** Coherent segment mutation  
Figure 6 illustrates the generation of variations on a given bacterium. In the given example, the length of the permutation is \(|x|=9\), the length of the segment is \(I_{seg}=3\), and the starting index is \(S_{seg}=0\). The loose segment mutation operates similarly to the coherent segment mutation (Algorithm 3). The only difference is the non-cohesive segment selection. At the start of the operation, a random segment with length \(I_{seg}\) is chosen from the bacterium \(x\). The segment is first reversed to generate the first mutant. All other mutants have the selected segment shuffled randomly. According to the objective function \(f\), the best one is chosen from all mutants and the original bacterium. Algorithm 4 defines this process. Figure 6: Cohesive segment process in Algorithm 3. Figure 7 illustrates how a loose segment might get chosen. In the example, the length of the permutation is \(|x|=9\); the segment length is \(I_{seg}=3\); the random segment indexes are \(S=1,3,7\); and the segment values are \(V=1,8,7\). Every time the loose segment mutation operation is called, the segment is selected based on values given by a pseudo-random generator. This random selection process ensures an even distribution of segments across the bacterium. This way, non-cohesive parts of the bacterium can get optimized locally. Figure 8 illustrates how a non-cohesive segment depicted in Figure 7 is calculated. The segment elements get reversed to generate the first mutant. The segment gets shuffled to generate all other variations until \(N_{mutants}\) mutants are reached. The coherent segment mutation operation (Algorithm 3) operates on a sequence of indexes, while the loose segment operation (Algorithm 4) breaks the sequence and samples the entire bacterium. Both operations perform a local neighborhood search on their given segment to further improve the bacterium. Figure 7: Example for a segment chosen in loose segment mutation (Algorithm 4).