Radial Search: A Simple Solution Approach to Hard Combinatorial Problems

摘要

We introduce a simple approach to rinding approximate solutions to combinatorial problems. This approach called the Radial Search (RS) uses the concept of rings which define the location and size of search areas around current good solutions. It iteratively modifies the radii of these rings, and generates new centres, in order to cover the search space. A concentration step corresponds to choosing a solution as the centre of a new ring. An expansion step corresponds to the exploration around a given centre by increasing and reducing the radius of the ring until a better solution than the centre is found. This dynamic process of concentration and expansion of the search is repeated until a stopping condition is met. A detailed description of RS, a discussion of its similarities and differences with current known methods, and its performance on TSP and QAP problems are given.