# Automated Design of CubeSats using Evolutionary Algorithm for Trade Space Selection
## 3 Knapsack Problem in System Design  
The knapsack problem is also relevant for designing systems consisting of multiple subsystems such that its performance is maximized satisfying multiple resource constraints. Considering a system to be composed of \(n\) subsystems with each subsystem, \(i,\ \forall i\in\{1,\ldots,\ n\}\), consisting of \(l_{i}\) options, as shown in Figure 1, each option of the subsystem has a particular value and it requires \(m\) resources. The objective is to pick exactly one option from each subsystem for the maximum total value of the collected items, subject to \(m\) resource constraints of the knapsack (system). This is a variant of the classical 0-1 knapsack problem and is termed the multidimensional multiple-choice knapsack problem (MMKP) [19]. In mathematical notation, let  
Figure 1: Description of a system composed of multiple subsystems and multiple options for each subsystem. \(\left(r_{ij1},\ r_{ij2},\ldots,\ r_{ijm}\right)\) be the value and resource vector of the object \(o_{ij}\), i.e., \(j-\text{th}\) option of the \(j-\text{th}\) subsystem. In addition, assume that \(R=(R_{1},\ R_{2},\ldots,\ R_{m})\) is the resource bound to the knapsack (system). Now, the problem is mathematically expressed as Equation (2). \[\textit{MMKP}=\left\{ \begin{array}{c}\max\sum\limits_{i=1}^{n}\sum\limits_{j =1}^{l_{i}}x_{ij}v_{ij}\\ \text{subject to}\ \sum\limits_{i=1}^{n}\sum\limits_{j=1}^{l_{i}}x_{ij}r_{ijk} \leq R_{k}\ \forall k\in\{1,\ldots,\ m\}\\ x_{ij}\in\{0,\ 1\}\\ \sum\
olimits_{j=1}^{l_{i}}x_{ij}=1\ \forall i\in\{1,\ldots,\ n\}\end{array} \right. \tag{2}\]  
The number of possible designs, \(D\), is the product of the number of options of all \(n\) subsystems; \(D=\prod_{i=1}^{n}l_{i}\), which grows exponentially as the number of subsystems, \(n\), and number of options, \(l_{i}\), increases as shown in Figure 1(a). One way to solve this problem is to use a brute force method by trying all \(D\) possible designs, which is highly inefficient. Other methods include greedy algorithms and dynamic programming [18]. Several heuristic algorithms have also been proposed for MMKP. One such algorithm is based on the Lagrange multiplier method [20]. Other methods include HEU [21], the modified guided local search [22], the modified reactive local search [23], the convex hull-based method [24], and the column generation method [25]. Several exact algorithms have also been proposed such as the branch-and-bound method with linear programming [21] and the EMKP algorithm [26]. Although these algorithms are able to obtain fairly good solutions for small search spaces, they become ineffective due to the _curse of dimensionality_ when approaching practical scenarios, where the number of subsystems and the number of options for each subsystem grows significantly. However, EA provides a way to solve the knapsack problem in linear time. Evolutionary algorithms gain their inspiration from the natural process of evolution and emulate evolution by applying recombination (crossover), mutation, and natural selection on a population [27]. Highly fit individuals from the population are sampled, recombined, and resampled to form offspring of potentially higher fitness. As the evolutionary algorithm progresses through generations, fitter building blocks proliferate and unfit building blocks are culled from the population. In a way, by working with these particular schemata the complexity of the problem is reduced. Instead of building a high-performance individual by trying every conceivable combination, better and better individuals are constructed from the best partial solutions of past sampling. Figure 2: (a) Possible design combinations for varying number of components and options; (b) evolutionary algorithm structure [27]. Evolutionary algorithms (EAs) are a stochastic optimization method that provides an approach to learning by mimicking the metaphor of natural biological evolution or Darwinian evolution.