  The search for binary sequences with low peak sidelobe level value represents
a formidable computational problem. To locate better sequences for this
problem, we designed a stochastic algorithm that uses two fitness functions. In
these fitness functions, the value of the autocorrelation function has a
different impact on the final fitness value. It is defined with the value of
the exponent over the autocorrelation function values. Each function is used in
the corresponding optimization phase, and the optimization process switches
between these two phases until the stopping condition is satisfied. The
proposed algorithm was implemented using the compute unified device
architecture and therefore allowed us to exploit the computational power of
graphics processing units. This algorithm was tested on sequences with lengths
$L = 2^m - 1$, for $14 \le m \le 20$. From the obtained results it is evident
that the usage of two fitness functions improved the efficiency of the
algorithm significantly, new-best known solutions were achieved, and the
achieved PSL values were significantly less than $\sqrt{L}$.
