Spread spectrum audio watermarking (SSW) is one of the most secure techniques of audio watermarking. SSW hides information by spreading their spectrum which is called watermark and adds it to a host signal as a watermarked signal. Spreading spectrum is done by a pseudonoise (PN) sequence. In conventional SSW approaches, the receiver must know the PN sequence used at the transmitter as well as the location of the watermark in watermarked signal for detecting hidden information. This method is attributed high security features, since any unauthorized user who does not access this information cannot detect any hidden information. Detection of the PN sequence is the key factor for detection of hidden information from SSW. Although PN sequence detection is possible by using heuristic approaches such as evolutionary algorithms, due to the high computational cost of this task, such heuristic tends to become too expensive (computationally speaking), which can turn it impractical. Much of the computational complexity involved in the use of evolutionary algorithms as an optimization tool is due to the fitness function evaluation that may either be very difficult to define or be computationally very expensive. This paper proposes the use of fitness granulation to recover a PN sequence with a chip period equal to 63, 127, 255 bits. This is a new application of authors’ earlier work on adaptive fitness function approximation with fuzzy supervisory. With the proposed approach, the expensive fitness evaluation step is replaced by an approximate model. The approach is then compared with standard application of evolutionary algorithms; statistical analysis confirms that the proposed approach demonstrates an ability to reduce the computational complexity of the design problem without sacrificing performance.