# Mental Map-Preserving Visualization through a Genetic Algorithm
## 2 Materials and Methods
### Genetic Algorithm
#### 2.5.2 Genetic Operator  
The genetic operator in this paper consists of three methods: Crossover, Mutation and Inversion. Our Inversion and Mutation operators are based on the previous work of [PERSON] et al. [4] on a genetic algorithm graph drawing, as it was proven to help draw large cycles with no chords as convex polygons and can reach an optimum solution faster. Choosing a desirable crossover operator in graph drawing is hard. Here, a desirable crossover should generate an offspring that is similar to its parent. Our crossover operator, called _single-link crossover_, will exchange a chain of connected points, thus inheriting characteristics much better than only exchanging a single point. As shown in Figure 6, both offsprings obtained a much better fitness value as they reduced the edge-crossing while still maintaining some characteristics from their parents. We have two types of mutation operators that will be sequentially applied. The first one, called a nonuniform mutation [4], is defined in Equation (3), where S = (\(v_{1}\), \(v_{2}\),..., \(v_{k}\),..., \(v_{2n}\)) is a chromosome (a node \((x,\ y)\) is (\(v_{1}\), \(v_{2}\)), in this case), and element \(v_{k}\) is selected to be mutated:  
\[v^{\prime}_{k}=\left\{ \begin{array}{ll}v_{k}+\Delta(t,\ b_{k}-v_{k}),\ if\ c=0\\ v_{k}-\Delta(t,pk-a_{k}),\ \ if\ c=1\end{array} \right. \tag{3}\]  
In Equation (3), \(c\) is a random value between 0 or 1, \(t\) is our current generation, [\(a_{k}\), \(b_{k}\)] is the lower and upper bounds for \(v_{k}\) and function \(\Delta(t,\ y)\) returns a value in the range [0, \(y\)], such that the probability of returning 0 increases when the \(t\) value increases. The equation for this function is shown with more detail in Equation (4):  
\[\Delta(t,y)=y\ (1-r)^{(1-\frac{t}{\lambda})^{\lambda}} \tag{4}\]  
where \(T\) is our max number of generations, and \(\lambda\) is our learning parameter chosen by a user. This property of nonuniformity will search a broad area in the initial generation while moving on to the local one in later stages. It tunes the solutions in later stages of evolution. The second one is called the single-vertex neighborhood mutation [4], which chooses a random node and moves it to a random point on a circle of decreasing radii, along with the generation. Suppose vertex \(v_{i}\ (x,\ y)\) is chosen; then, \((x^{\prime},\ y^{\prime})\) is the new coordinate of \(v_{i}\), defined in Equation (5):  
\[\left\{ \begin{array}{ll}x^{\prime}=x+r\cos\theta\\ y^{\prime}=y+r\sin\theta\end{array} \right. \tag{5}\]  
Figure 6: Single-link crossover. where \(r=L\ *\ ((1-t/T)\), and \(\theta\) is a random number between \([0,\ 2\pi]\). \(L\) is the ideal edge length calculated based on the number of nodes, and our drawing size is shown in Equation (6):  
\[L=\frac{L_{0}}{diameter} \tag{6}\]  
where \(L_{0}\) is the maximum length of a side of a square area display, and diameter is the diameter of the visible graph. In other words, the diameter is the distance between the farthest pair of nodes, and we set the value to be \(5+\sqrt{2n}\), where \(n\) is the total number of nodes. This method also has the nonuniformity to make a broad search in the early stages and a more focused search on the later stages. We also implemented a relinking path algorithm at each generation with a certain percentage. Path relinking is a search intensification strategy [15]. With this research, we want to verify if a path relinking could work with GA to get a better drawing result, just like [PERSON] and [PERSON] [10], on a graph drawing by combining Tabu search with path relinking. Figure 7 shows how our relinking path process works. The path relinking algorithm starts with two solutions, a source and a target solution, where the target solution usually has a better fitness value than the source solution. Based on [PERSON] and [PERSON] [10], here, the most distant solution is the one with the maximum summed distance of each node to the node of the best solution.