# Search on an NK Landscape with Swarm Intelligence: Limitations and Future Research Opportunities
## 2 NK Landscape
### Mathematical Development of NK  
In the strategy and organization literature, an NK landscape is usually described by a set of binary choices. As a result, the landscape is a high-dimensional hypercube. [PERSON] (2018) gives an example of three major components of a computer: the screen, CPU, and battery. These three components are interdependent. His diagram is reproduced here in Figure 1.  
In Figure 1, the arrows represent the direction of influence. The battery depends on the screen, the CPU depends on the battery, and the screen depends on the CPU. These interdependencies are  
Each node, from \([0,0,0]\) to \([1,1,1]\), represents each component's state. In this binary setting, there are only two states (e.g., on or off).  
If we examine \(x_{1}\) (screen), since we know it is influenced by only \(x_{3}\) (CPU), we should have the following information for fitness \(\phi_{1}(x_{1},x_{3})\). Similarly, we have \(\phi_{2}(x_{2},x_{1})\) and \(\phi_{3}(x_{3},x_{2})\). Simply speaking, each sub-fitness function \(\phi_{i}\) is evaluated for all components that influence component \(i\). We write it out explicitly as follows:  
\[\phi_{1}(x_{1},x_{3})=\left\{\begin{array}{ll}\phi_{1}(0,0)\\ \phi_{1}(0,1)\\ \phi_{1}(1,0)\\ \phi_{1}(1,1)\end{array}\right.\phi_{2}(x_{2},x_{1})=\left\{\begin{array}{ ll}\phi_{2}(0,0)\\ \phi_{2}(0,1)\\ \phi_{2}(1,0)\\ \phi_{2}(1,1)\end{array}\right.\phi_{3}(x_{3},x_{2})=\left\{\begin{array}{ ll}\phi_{3}(0,0)\\ \phi_{3}(0,1)\\ \phi_{3}(1,0)\\ \phi_{3}(1,1)\end{array}\right. \tag{2}\]  
\[\phi(x_{1},x_{2},x_{3})=\phi_{1}(x_{1},x_{3})+\phi_{2}(x_{2},x_{1})+\phi_{3}(x _{3},x_{2}) \tag{3}\]  
For example,  
\[\phi(1,0,1)=\phi_{1}(1,1)+\phi_{2}(0,1)+\phi_{3}(1,0) \tag{4}\]  
The entire landscape is the hypercube, which includes all the possible points, as demonstrated in Figure 2. The fitness values are presented in parentheses (the global peak is 0.6333 at 1, 1, 1). The major drawback of Figure 2 is that the landscape it represents cannot be visualized.  
In a general sense, the fitness function of any choice of policy can be written as:  
\[\phi(x_{1},\cdots,x_{N})=\frac{1}{N}\sum_{i=1}^{N}\phi_{i}(x_{i}\in I_{i}) \tag{5}\]  
where \(x_{i}=0,\ 1\) and \(I_{i}\) represents the \(i\)th row of the interaction matrix \(I\).  
Once the number of components is greater than 3, it is not possible to graphically draw the hypercube. Furthermore, the hypercube cannot present a visual of the landscape. As a result, it is common in the NK landscape literature to collapse the N-dimensional hypercube  
Figure 2: An example of a binary 3-dimensional NK landscape. Note: The battery (\(x_{1}\)) depends on the screen, the CPU (\(x_{2}\)) depends on the battery, and the screen (\(x_{3}\)) depends on CPU. The fitness values are presented in parentheses (the global peak is 0.6333 at 1, 1, 1).  
into a three-dimensional landscape, which can then be visualized, as in Figure 3[10]. However, the usual description of a 3-D collapsed landscape often seen in the literature is not an actual collapse of the hypercube but rather an imaginary portrait to mimic the ruggedness of the landscape [11]. As seen in Figure 3, high \(K\) results in a rugged landscape, while low \(K\) results in a smooth landscape.  
In this paper, we first follow [PERSON] and [PERSON] [3] and use \(N=6\) to demonstrate our swarm simulations. We set up two cases: \(K=2\) to represent a few interdependencies, and \(K=5\) to represent the maximum interdependencies.  
For example, when \(N=6\), then there are \(2^{6}=64\) choices from \([0,\,0,\,0,\,0,\,0]\) to \([1,\,1,\,1,\,1,\,1]\) (or 0-63 in decimal representation). Hence, there are 64 fitness values, one for each choice. In other words, this is a six-dimensional hypercube. Each sub-fitness function \(\phi_{i}\) is used as in Equation (5).