# Adaptive Gene Level Mutation
## 4 Heuristically Partially Solvable Problems with Unknown Optimum  
As we saw earlier, locus mutation works well with a partially solvable problem outperforming the traditional approach using gene level information. Although Locus mutation is only applicable for partially solvable problems e.g., N-Queens problem [33], heuristic partial solution can be sufficient which can only be inferred with a comprehensive understanding of the problem. One of the most elusive problem is traveling salesmen problem (finding the shortest route to visit a set of cities), where the optimal solution is undefined making the optimization process interminable, and a heuristic threshold has to be used. In the N-Queens problem, calculating the partial solution was a straight forward process which is the number of queens hitting the current gene taking all the other genes into consideration. Having us doing so in the traveling salesman problem (TSP) [34] requires a modification signifying the distance between the current gene (city) and the next gene with contrast to its distance with the other genes. Since traditionally the fitness of the entire chromosome relies solely on the distance between each gene and its next neighbor without taking into account any other genes, we came up with a new idea which we will call normalized comparative loss to calculate the partial fitness of each gene taking into consideration all other genes. Figure 1: Potential chromosome for 8-Queens Problem where queen 1 is hitting queen 8, and two queens (2, 3) are hitting each other and also hitting two other queens (4, 7) yielding a loss of 4 where the four hitting pairs are ([1, 8], [2, 3], [2, 4], [3, 7]). An example has been depicted in Figure 2 showing a simple example of TSP problem with 10 cities. Each city has two indices, the first index indicates the order of the city in the candidate chromosome [6 3 4 9 5 1 10 7 8 2] and the second one refers to the actual label of the city e.g., the first gene in our chromosome has the label \((1,6)\). To explain the partial fitness value of a gene, we have used the same candidate chromosome but focused on the penultimate gene, gene \((9,8)\), as in Figure 3. This gene refers to the city number 8 which is located at the gene before the last gene in the candidate solution. The red line depicts the relevant connection between our gene and gene number two; the last gene in the current chromosome and the next neighboring gene. The gene which is the farthest away from our gene of interest has been linked to our gene with green line, while the blue line portrays the closest gene. Using the three previously mentioned distances;the pertinent distance between the current gene and next gene, the distance between the current gene and the gene which is farthest away from the current gene and the distance between the current gene and the gene which is closest to the current gene; we can calculate a heuristic partial fitness as in Equation (7) where \(i\) is the concerned gene while _MinDistance_ and _MaxDistance_ give us respectively the minimum and the maximum distance between gene \(i\) and the other genes. \[PF_{i}=\frac{Distance(i,i+1)-MinDistance(i)}{MaxDistance(i)-MinDistance( i)} \tag{7}\]  
Before moving to the results section demonstrating the effectiveness of locus mutation, we will substantiate the advantage of using locus mutation by applying Wilcoxon test which is a non-parametric statistical test used to determine if two sets of distributions are different from each other in a statistically significant manner. We investigated a TSP instance with 48 cities, 1000 chromosomes, 20 generations. We used the same initial population for baseline and locus mutation then stored the evolved two populations after the 20 th generation. Figure 4 demonstrates the distribution of the fitness of the chromosomes for the initial population, the 20 th baseline population and the 20 th locus population.