## 3 Methods
### Cycle Mutation
#### 3.1.3 Cycle(\(\alpha\))  
The second version of cycle mutation, called Cycle(\(\alpha\)), maximizes the size of the local neighborhood while retaining the local focus of a small cycle length. Cycle(\(\alpha\)) allows any possible cycle length \(k\in[2,n]\), but chooses a smaller cycle length with higher probability than a greater cycle length. Specifically, the probability of choosing cycle length \(k\) is proportional to \(\alpha^{k-2}\). Thus, the probability \(P(k)\) of choosing cycle length \(k\) is  
\[P(k)=\frac{\alpha^{k-2}}{\sum_{l=2}^{n}\alpha^{l-2}}=\frac{\alpha^{k-2}(1- \alpha)}{1-\alpha^{n-1}}. \tag{13}\]  
The \(\alpha\) is a parameter of the operator such that \(0<\alpha<1\). The nearer \(\alpha\) is to 0, the more probabilistic weight is placed upon lower values of \(k\) relative to higher values.  
From this, we can derive a mathematical transformation from uniform random number \(U\in[0.0,1.0)\) to corresponding cycle length \(k\). Choose \(k\) according to the following:  
\[k=\begin{cases}2&\text{if }0\leq U<P(2)\\ j&\text{if }\sum_{i=2}^{j-1}P(i)\leq U<\sum_{i=2}^{j}P(i).\end{cases} \tag{14}\]  
This is equivalent to  
\[k=\operatorname*{argmin}_{j\in[2,n]}\left\{\sum_{i=2}^{j}P(i)\right\}\text{ subject to }\left\{\sum_{i=2}^{j}P(i)>U\right\}. \tag{15}\]Substituting Equation (13) into the constraint and simplifying arrives at  
\[k=\underset{j\in[2,n]}{\text{argmin}}\Bigg{\{}\sum_{i=2}^{j}P(i)\Bigg{\}}\text{ subject to }\bigg{\{}\frac{1-\alpha^{j-1}}{1-\alpha^{n-1}}>U\bigg{\}}. \tag{16}\]  
Solve the constraint for \(j\) to derive  
\[k=\underset{j\in[2,n]}{\text{argmin}}\Bigg{\{}\sum_{i=2}^{j}P(i)\Bigg{\}}\text{ subject to }\bigg{\{}j>\frac{\log(1-(1-\alpha^{n-1})U)}{\log(\alpha)}+1\bigg{\}}. \tag{17}\]  
Since the summation inside the argmin increases as \(j\) increases, this is equivalent to  
\[k=\underset{j\in[2,n]}{\text{min}}\{j\}\text{ subject to }\bigg{\{}j>\frac{\log(1-(1- \alpha^{n-1})U)}{\log(\alpha)}+1\bigg{\}}. \tag{18}\]  
Finally, we compute \(k\) from \(U\) via  
\[k=2+\bigg{[}\frac{\log(1-(1-\alpha^{n-1})U)}{\log(\alpha)}\bigg{]}. \tag{19}\]  
Since \(\alpha\) is a parameter that does not change during the run, and since the permutation length \(n\) is likewise fixed based on the problem instance we are solving, the \((1-\alpha^{n-1})\) and the \(\log(\alpha)\) are constants that can be computed a single time at the start of the run.  
Algorithm 5 shows pseudocode of Cycle(\(\alpha\)). The worst-case runtime is \(O(n)\), which occurs when the random \(k\) equals \(n\), leading lines 3-4 to cost \(O(n)\). The worst case is a rare occurrence. Since mutation is applied a very large number of times during an EA, it is more meaningful to examine the average runtime of mutation. To determine the average runtime, we must first compute the expected cycle length \(E[k]\) as follows:  
\[E[k] =\sum_{k=2}^{n}kP(k) \tag{20}\] \[=\frac{(1-\alpha)}{1-\alpha^{n-1}}\sum_{k=2}^{n}ka^{k-2}\] \[=\frac{2-\alpha+n\alpha^{n}-n\alpha^{n-1}-\alpha^{n-1}}{(1-\alpha )(1-\alpha^{n-1})}\] \[\leq\lim_{n\to\infty}\frac{2-\alpha+n\alpha^{n}-n\alpha^{n-1}- \alpha^{n-1}}{(1-\alpha)(1-\alpha^{n-1})}\] \[=\frac{2-\alpha}{1-\alpha}.\]  
The expected cycle lengths for Cycle(0.25), Cycle(0.5), and Cycle(0.75) are \(E[k]\leq 2\frac{1}{3}\), \(E[k]\leq 3\), and \(E[k]\leq 5\), respectively. The average runtime of Cycle(\(\alpha\)) is therefore \(O(\min(n,(\frac{2-\alpha}{1-\alpha})^{2}))\) due to the call to Sample(\(n,k\)) in line 2 of Algorithm 5.  
```
1:\(k\gets 2+\left[\frac{\log(1-(1-\alpha^{n-1})U)}{\log(\alpha)}\right]\)
2:indexes \(\leftarrow\) Sample(\(n,k\))
3:Shuffle(indexes)
4:CreateCycle(\(p,\text{indexes}\))
```  
**Algorithm 5** CycleMutation(\(p,\alpha\))