# An Analysis Of Phase Transition In Nk Landscapes

## Yong  Gao

Joseph Culberson Department of Computing Science University of Alberta Edmonton, Alberta, Canada, T6G 2H1 YGAO@CS.UALBERTA.CA
JOE@CS.UALBERTA.CA

## Abstract

In this paper, we analyze the decision version of the NK landscape model from the perspective of threshold phenomena and phase transitions under two random distributions, the uniform probability model and the fixed ratio model.  For the uniform probability model, we prove that the phase transition is easy in the sense that there is a polynomial algorithm that can solve a random instance of the problem with the probability asymptotic to 1 as the problem size tends to infinity. For the fixed ratio model, we establish several upper bounds for the solubility threshold, and prove that random instances with parameters above these upper bounds can be solved polynomially. This, together with our empirical study for random instances generated below and in the phase transition region, suggests that the phase transition of the fixed ratio model is also easy.

## 1. Introduction

The NK landscape is a fitness landscape model devised by Kauffman (1989). An appealing property of the NK landscape is that the "ruggedness" of the landscape can be tuned by changing some parameters.  Over the years, the NK landscape model itself has been studied from the perspectives of statistics and computational complexity (Weinberger, 1996; Wright, Thompson, & Zhang, 2000). In the study of genetic algorithms, NK landscape models have been used as a prototype and benchmark in the analysis of the performance of different genetic operators and the effects of different encoding methods on the algorithm's performance (Altenberg, 1997; Hordijk, 1997; Jones, 1995).

In the field of combinatorial search and optimization, one of the interesting discoveries is the threshold phenomena and phase transitions. Roughly speaking, a phase transition in combinatorial search refers to the phenomenon that the probability that a random instance of the problem has a solution drops abruptly from 1 to 0 as the order parameter of the random model crosses a critical value called the threshold. Closely related to this phase transition in solubility is the hardness of solving the problems.  There has been strong empirical evidence and theoretical arguments showing that the hardest instances of the problems usually occur around the threshold and instances generated with parameters far away from the threshold are relatively easy. Since the seminal work of Cheeseman et al. (Cheeseman, Kanefsky, & Taylor, 1991), many NP-complete combinatorial search problems have been shown to have the phase transition and the associated easy-hard-easy pattern (Cook & Mitchell, 1997; Culberson & Gent, 2001; Freeman, 1996; Gent, MacIntyre, Prosser, &