EPrints@IIT Delhi >
Faculty Research Publicatons >
Electrical Engineering >
Please use this identifier to cite or link to this item:
|Title: ||Parallel search-and-learn technique for solving large scale travelling-salesperson problems|
|Authors: ||Ravikumar, C P|
|Keywords: ||combinatorial optimization|
travelling salesperson problem
|Issue Date: ||1994|
|Citation: ||Knowledge-Based Systems, 7(3), 169-176p.|
|Abstract: ||Parallel processing has traditionally been used to achieve higher speed while solving computational problems of large size. The greater availability of parallel and distributed computing opens yet another dimension, where parallel computers can be used to obtain solutions of higher quality than uniprocessor solutions. The paper describes a search-and-learn technique for obtaining high quality solutions to the travelling salesperson problem (TSP). The combinatorial search space is decomposed so that multiple processors can simultaneously look for local optimal solutions in the subspaces. The local optima are then compared to ‘learn’ which moves are good; a move is defined to be good if all the search processes have voted in consensus for the move. On the basis of this learning, the original problem is transformed into a constrained optimization, where a constraint requires a specific edge to be included in the final tour. The constrained optimization problem is modelled as a TSP of smaller size, and is again solved using the parallel search technique. This process is repeated until a TSP of manageable size is reached which can be solved effectively; the tour obtained at this last stage is then expanded retrogressively until the tour for the original problem is obtained.
The search-and-learn algorithm has been implemented on a Meiko transputer array of 32 nodes. The results of the implementation for benchmark problems are described.|
|Appears in Collections:||Electrical Engineering|
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.