Metaheuristic Development

Metaheuristics are often effective at finding solutions to optimization problems of sufficient quality when faced with limited computational resources, such as time and memory. There are many metaheuristics, such as hill climbing and other forms of local search, simulated annealing, genetic algorithms and other forms of evolutionary computation, various stochastic sampling search algorithms, among many others. Metaheuristics are often good problem-independent solvers, requiring mainly mapping solutions to your target problem to an appropriate representation, choosing an operator or operators for that representation, and defining an evaluation function. The metaheuristic then searches for solutions without the need to know specifically about the problem at hand. For example, you can use a genetic algorithm (GA) if you can map solutions to your problem to bit strings, and define a fitness function that evaluates a bit string within the context of your problem. The GA then operates in the same way to solve your problem as it would to solve any other. Metaheuristics also generally provide an anytime property, where it is able to provide some solution in very little time, and solutions of increasing quality the more time is available. My research has lead to the development of new metaheuristics, including Value-Biased Stochastic Sampling (VBSS), and Wasp beHavior Inspired STochastic SampLING (WHISTLING).

Value-Biased Stochastic Sampling

In a stochastic sampling algorithm, randomized solutions to an optimization problem are iteratively generated, with the algorithm returning the best such solution from among N such stochastic solutions. The simplest form of a stochastic sampler is Iterative Sampling (Langley, 1992), which iteratively generates N random solutions to the problem, keeping the best of the N such solutions. It uses no knowledge of the problem other than an objective function that is to be optimized. In Value Biased Stochastic Sampling (VBSS), introduced in my Ph.D. dissertation and also detailed in an article from the Journal of Heuristics titled Enhancing Stochastic Search Performance by Value-Biased Randomization of Heuristics, solutions are stochastically generated with a constructive heuristic used to bias the randomized decisions. For example, if the problem was the traveling salesperson, one possible heuristic that could be used to guide the search is the distance from the current city to the possible city that we are evaluating. The bias function of VBSS would then give a higher weight in the random decision to the cities that are nearest to the current city.

VBSS is closely related to the Heuristic Biased Stochastic Sampling (HBSS) algorithm (Bresina, 1996). The difference is related to how the heuristic is used. HBSS uses the heuristic to rank the choices, and uses a bias function of the ranks; while VBSS uses the heuristic values directly. For example, if there are two choices, HBSS only cares that there are two choices, and which of the two is ranked above the other. The magnitude of the difference of the heuristic values does not matter to HBSS. Whereas, the magnitude of the heuristic values does matter to VBSS. If your heuristic is knowledgeable, then VBSS makes better use of its insight into the problem. In cases where your heuristic is weaker, however, Bresina's HBSS may be better. When we introduced VBSS, we focused on single machine scheduling problems, where there is significant prior work on dispatch scheduling heuristics, some of which are quite strong. In such cases, VBSS's use of the heuristic values provides a more effective way of using a heuristic to guide a randomized search.

WHISTLING

Wasp beHavior Inspired STochastic SampLING is a stochastic sampling algorithm inspired by a computational model of how wasps of the genus Polistes form dominance hierarchies among the members of the colony. In the model of Theraulaz, Goss, Gervet, and Deneubourg (1991), each individual wasp has a so-called force variable. Pairs of wasps engage in dominance contests, with the winner chosen by a probabilistic model. The force values of the two wasps engaged in the contest are adjusted, with some force transferring from the loser to the winner. A hierarchy evolves over time as the wasps of the colony continue to encounter each other and compete for dominance.

Many combinatorial optimization problems involve finding an optimal ordering over a set of elements, such as finding an optimal ordering over a set of cities for an instance of the traveling salesperson problem, or an optimal ordering over a set of jobs or tasks for a scheduling problem. Viewing the dominance contest behavior of wasps as a way of ordering the wasps of the colony, we developed WHISTLING. Initially, we considered how to extend individual dominance contests over a set of elements to be ordered. WHISTLING represents each element of the set (whether they are jobs to be scheduled or something else) with a wasp. Our earliest exploration examined several possible tournament structures for collecting the results of many individual pairwise dominance contests, as explained in the paper Randomizing Dispatch Scheduling Policies from the 2001 AAAI Fall Symposium Series. The full WHISTLING algorithm was fleshed out in a paper at CP 2002 titled Amplification of Search Performance through Randomization of Heuristics. In that paper, in addition to introducing the WHISTLING algorithm, we demonstrated its effectiveness on an NP-Hard scheduling problem, weighted tardiness scheduling with sequence-dependent setups. We also utilized the WHISTLING algorithm as one component of a multirobot space exploration project (Goldberg et al, 2003; Goldberg et al, 2002), specifically using WHISTLING as the scheduler for tasks allocated to a single robot of the multirobot team.

Selected Publications