NEW OPTIMIZATION HEURISTICS - THE GREAT DELUGE ALGORITHM AND THE RECORD-TO-RECORD TRAVEL

In a former paper we introduced a very effective new general purpose optimization principle. We compared this method, which we called threshold accepting (TA), with the well-known simulated annealing (SA) method for discrete optimization. The empirical results demonstrated the superiority of the TA algorithm. In further experiments with the TA principle we discovered two new powerful optimization heuristics: The great deluge algorithm (GDA) and the record-to-record travel (RRT). These algorithms resemble in their structure the formerly studied TA and the SA method. The differences lie in their acceptance rules for worse intermediate solutions. Both, the GDA and the RRT, are essentially one-parameter algorithms; i.e., for the achievement of best possible performance, a good choice is necessary only for a single parameter. This is in contrast for instance to the classical AS algorithm, where it is necessary to choose carefully a certain sequence of parameters, the so-called annealing schedule. The quality of the computational results obtained so far by RRT and GDA shows that the new algorithms behave equally well as TA and thus a fortiori better than SA. © 1993 Academic Press, Inc.