Random Optimization

Are our random optimization methods better than resource-matched deterministic hillclimbing?

For our deterministic entry, starting with randomized configurations, using a null entry table-driven scheme, we took the best of five iterated next-descent hillclimbing rounds (approximately 40 million total attempts), in both random (mr) and priority order (m) as described in Section 3.3. The random and priority orders of iteration did not register any difference.

Pairwise comparisons consistently showed the iterated next-descent hillclimbing rounds were different than all the randomized methods tested, except the unminimized table-driven schemes (sa1 & sigmet1) in all terms, minimized table-driven schemes (sa1/m & sigmet1/m) in 1999, and the unminimized accept-based adaptive scheme (sa3) in Fall 2000.

On average, the iterated next-descent hillclimbing scores (m & mr) were an order of magnitude greater than all the others, with wider standard deviations (Tables 4.3 through 4.5), forcing us to conclude our randomized methods have a distinct advantage over simple hillclimbing.

Figure 4.2: Mean Rank By Method -- Fall 2000
Figure 4.3: Mean Rank By Method -- Fall 1999
Figure 4.4: Mean Rank By Method -- Fall 1998

Figure 4.5: Average Score By Method -- Fall 2000
Figure 4.6: Average Score By Method -- Fall 1999
Figure 4.7: Average Score By Method -- Fall 1998

download thesis