# An Iterative Optimization Algorithm for Planning Spacecraft Pathways Through Asteroids
## 2 Permutation Optimization Problems  
Permutations are flexible algebraic structures that have applications across numerous domains due to their ability to model various concepts, such as orderings, rankings, one-to-one mappings between sets, and tours or cycles within a given set of locations. Permutations, typically referred to using Greek letters like \(\sigma\) or \(\pi\), can be formally defined as bijective functions mapping the set of the first \(n\) natural numbers, i.e., \([n]=\{1,2,\ldots,n\}\)onto itself. While multiple notations for permutations exist, the widely used _single-line notation_ expresses a permutation \(\sigma\) as a sequence of all different items, as follows:  
\[\sigma=\langle\sigma(1),\sigma(2),\ldots,\sigma(n)\rangle, \tag{1}\]  
where \(\sigma(i)\in[n]\) denotes the item at position \(i\in[n]\) in the sequence, and it holds that \(\sigma(i)\
eq\sigma(j)\) for any choice of \(i,j\in[n]\) such that \(i\
eq j\). There are \(n!\) permutations of length \(n\) and their set is denoted as \(\Sigma_{n}\), which is also referred to as the _symmetric group_. Indeed, \(\Sigma_{n}\) is a group in the algebraic sense because there exists a binary operation between permutations, known as _composition_, that is associative and admits an identity element along with an inverse for every permutation. Given \(\sigma,\pi\in\Sigma_{n}\), their composition \(\sigma\pi\) is defined as \(\sigma\pi(i)=\sigma(\pi(i))\) for all \(i\in[n]\). The identity permutation is usually denoted as \(\iota=\langle 1,\ldots,n\rangle\), while the inverse of \(\sigma\) is the permutation \(\sigma^{-1}\) that satisfies the equivalences \(\sigma^{-1}\sigma=\sigma\sigma^{-1}=\iota\). Note that, in general, the commutative property does not hold for all the permutations of \(\Sigma_{n}\), therefore the group is not Abelian. Nevertheless, this group structure is a fundamental characteristic of permutations that has recently also been used for the development of both swarm and evolutionary algorithms [22; 23]. The objective of a permutation optimization problem is to either minimize or maximize a real-valued function \(f:\Sigma_{n}\to\mathbb{R}\). Because of the combinatorial nature of the domain of the objective function, permutation problems do not admit gradient-based algorithms (though model-based gradient search methods are however possible [24]). Additionally, often real-world objective functions require running simulations or experiments that cannot be expressed in closed analytical form, thus resulting in black-box optimization problems. In these cases, an effective algorithm can only gain knowledge about the problem at hand by testing various permutation solutions and observing the corresponding objective values. Even worse, black-box objective functions are often expensive to evaluate (in terms of time, memory, and other resources); therefore, a good algorithm should be able to locate a satisfactory solution in a limited number of function evaluations. Though being in a black-box context, it is often possible to exploit the problem description in order to infer the key features of a permutation that are relevant for the problem. In fact, permutation problems can be broadly classified into two main categories:  
* _Ordering problems_, where the goal is to find the optimal arrangement of items within a set \(A\);
* _Assignment problems_, whose objective is to determine the best one-to-one mapping between two equally sized sets \(A\) and \(B\). Based on this classification, it is often possible to choose a movement operator or another operator (for example, exchange moves for assignment problems or insertions for ordering problems [25]). Similar choices can be inferred also for crossovers or other meta-heuristic operators [26]. Though these two categories may not cover every possible permutation problem, they encompass the most commonly encountered ones in the scientific literature.