Greedy by Chance - Stochastic Greedy Algorithms

摘要

For many complex combinatorial optimization problems, obtaining good solutions quickly is of value either by itself or as part of an exact algorithm. Greedy algorithms to obtain such solutions are known for many problems. In this paper we present stochastic greedy algorithms which are perturbed versions of standard greedy algorithms, and report on experiments using learned and standard probability distributions conducted on knapsack problems and single machine sequencing problems. The results indicate that the approach produces solutions significantly closer to optimal than the standard greedy approach, and runs quite fast. It can thus be seen in the space of approximate algorithms as falling between the very quick greedy approaches and the relatively slower soft computing approaches like genetic algorithms and simulated annealing.