# An Application of an Unequal-Area Facilities Layout Problem with Fixed-Shape Facilities
## 3 A Genetic Algorithm (GA) for the UA-Flp
### Crossover and Mutation Operations  
The propose GA generates a number of solutions (chromosomes) and adds them to the new generation of chromosomes \(P_{g}\), where \(g\) is the current generation (iteration) of  
Figure 2: Flow diagram of the stages of the proposed GA.  
the GA. At the initial iteration (\(g=0\)), the GA starts by randomly generating the initial population of chromosomes (\(P_{0}\)). More specifically, each chromosome in \(P_{0}\) is generated randomly, and the TWD and _plant floor feasibility_ status is evaluated by constructing the layout using BSH. On the other hand, each solution in \(P_{g}\), for \(g>0\), is either randomly generated (i.e., mutation operation is used), or it is generated from two chromosomes (solutions), randomly selected from population \(P_{g-1}\) (i.e., crossover operation is used). The chromosomes obtained by applying crossover operation inherit features from both parent chromosomes. At each generation \(g\) of the GA, \(Max\_Num\_Cross\) chromosomes are generated using crossover operation, but only \(Gen\_Size\) (\(Gen\_Size\) < \(Max\_Num\_Cross\)) best chromosomes are kept in the new generation \(P_{g}\). The generated chromosome is added to \(P_{g}\), only if it is better than the worst chromosome in \(P_{g}\) and a chromosome similar to \(\pi\) has not already been added to \(P_{g}\). After the new population \(P_{g}\), for \(g>0\), is generated, \(Num\_Rand\_Chrom\) (\(Num\_Rand\_Chrom\) < \(Gen\_Size\)) chromosomes are randomly generated (mutation operation), and replace the worst chromosomes in \(P_{g}\). The chromosomes in each generation \(P_{g}\) are stored in such a way, that higher quality chromosomes precede lower quality chromosomes as in Drezner [27]. The stopping criterion for the proposed GA is the maximum amount of time \(Max\_Duration\), to run the heuristic.  
As in most GAs, where the chromosome represents a permutation of numbers, as in the proposed GA, the crossover operation may produce infeasible chromosomes, if a technique is not used to generate feasible chromosomes. The following technique is used to generate feasible chromosome \(\pi\), when performing the crossover operation to parents \(\pi^{1}\) and \(\pi^{2}\):  
Step 0:  Set \(k1=0.2N\), \(k2=0.5N\), \(cross\_point=1\), and \(num\_cross\_points=0\).  
Step 1:  Set num_cross_points = num_cross_points + 1.  
Add crossover point \(cross\_point\) to vector \(cross\_points\).  
Set \(cross\_point=cross\_point+\) Random number between \(k1\) and \(k2\).  
If \(cross\_point\geq N\), then go to Step 2.  
Else go to Step 1.  
Step 2:  Set \(cross\_point=N\) and \(num\_cross\_points=num\_cross\_points+1\).  
Add crossover point \(cross\_point\) to vector \(cross\_points\).  
Set \(r=1\).  
Step 3:  Copy the genes (facilities) \(cross\_points\), through \(cross\_points_{r+1}\) from chromosome \(\pi^{1}\) to the same positions in chromosome \(\pi\).  
Set \(r=r+2\).  
If \(r<num\_cross\_points\), go to Step 3.  
Else go to Step 4.  
Copy all the facilities in chromosome \(\pi^{2}\) which have not been copied from \(\pi^{1}\) into positions in \(\pi\) which have not been filled, while preserving the precedence order of facilities in \(\pi^{2}\).