# An Iterative Optimization Algorithm for Planning Spacecraft Pathways Through Asteroids
## 4 The Algorithm Fat-RLS  
The Fast Adaptive Tabu-based Randomized Local Search (FAT-RLS), proposed in [21], is a meta-heuristic algorithm tailored for solving costly black-box permutation problems. It builds upon the traditional framework of randomized local search, to which it introduces two key enhancements: an adaptive strategy to adjust its perturbation strength, and a tabu-based methodology that prevents the repetition of redundant perturbations. Randomized local search (RLS) consists of a trajectory-based approach that iteratively evolves a solution of the problem at hand. At each iteration, the current solution is compared to one of its neighbors selected at random. If the objective value is improved, the trial neighbor replaces the current solution for the next iteration. Despite its straightforward nature, RLS has been widely investigated within the theoretical framework of evolutionary computation [35], but it is less frequently applied in practical situations. We opted to utilize RLS as the search mechanism for our proposed algorithm due to its highly exploitative nature and the fact that it only requires a single evaluation of the objective function per iteration. This characteristic makes RLS particularly suited for maximizing the effectiveness of the limited evaluation budget in costly black-box scenarios. Additionally, each iteration merely involves applying a movement operator to the current solution, resulting in minimal computational overhead. This advantage is especially significant when compared to the computational demands of model learning and updating processes found in Bayesian methods such as those described in [36; 37]. As our primary focus is on the ARP, which can be classified as a permutation ordering problem (as outlined in Section 3), we utilize insertion moves to perturb the solutions. For an ARP instance of size \(n\) and a solution \(\sigma\in\Sigma_{n}\), an insertion move \((i,j)\), where \(i,j\in[n]\), entails shifting the element \(\sigma(i)\) to position \(j\) within \(\sigma\). Let \(\pi\) represent the permutation resulting from applying the insertion \((i,j)\) to \(\sigma\), in the case of a forward insertion, where \(i<j\), the transformation can be expressed as  
\[\pi(k)= \begin{cases}\sigma(k)&\text{if }k<i\text{ or }k>j,\\ \sigma(k+1)&\text{if }i\leq k<j,\\ \sigma(i)&\text{if }k=j.\end{cases}  \tag{4}\]  
Incontrast, for a backward insertion, where \(i>j\), the transformation is given by  
\[\pi(k)= \begin{cases}\sigma(k)&\text{if }k<j\text{ or }k>i,\\ \sigma(k-1)&\text{if }j<k\leq i,\\ \sigma(i)&\text{if }k=j.\end{cases}  \tag{5}\]  
To make clearer how insertions work, we provide two illustrative examples in Figure 1.  
Equations (4) and (5) illustrate that an insertion move \((i,j)\) rearranges \(|i-j|+1\) items within a permutation, which makes the insertion effectively equivalent to a sequence of \(|i-j|\) adjacent swaps. In the case of forward insertions, as shown in Equation (4) (with the backward insertion case being similar), the insertion \((i,j)\) corresponds to the following series of \(|i-j|\) adjacent swaps:  
\[\text{AdjSwap}(i,i+1),\ \text{AdjSwap}(i+1,i+2),\ \ldots,\ \text{AdjSwap}(j-1,j).\]  
A notable implication is that the Kendall's-\(\tau\) distance between \(\pi\) and \(\sigma\) (i.e., the number of discordant pairs of elements in the two permutations) equals \(|i-j|\). Consequently, we define \(d=|i-j|\) as the perturbation strength for a generic insertion \((i,j)\). In FAT-RLS, instead of randomly choosing a single insertion move, as is typical in traditional randomized local search methods, we regulate the perturbation strength \(d\) at each iteration. Specifically, FAT-RLS implements an adaptive perturbation strength strategy that requires two hyperparameters: the _initial perturbation strength_\(d_{\text{ini}}\) and the _steepness factor_\(\beta\). Initially, the perturbation strength \(d\) is set to \(d_{\text{ini}}\). FAT-RLS then perturbs the current solution by randomly selecting an insertion move \((i,j)\) such that \(|i-j|=d\).