| 作成者 |
|
|
|
|
|
|
|
| 本文言語 |
|
| 出版者 |
|
| 発行日 |
|
| 収録物名 |
|
| 巻 |
|
| 開始ページ |
|
| 終了ページ |
|
| 出版タイプ |
|
| アクセス権 |
|
| 関連DOI |
|
| 関連DOI |
|
|
|
|
|
|
|
| 関連URI |
|
|
|
|
|
|
|
| 関連URI |
|
| 関連HDL |
|
| 関連情報 |
|
|
|
|
|
|
|
| 概要 |
To practically solve NP-hard combinatorial optimizationproblems, local search algorithms and their parallel implementations on PVM or MPI have been frequently discussed. Since a huge number of neighbo...rs may be examined to discover a locally optimal neighbor in each of local search calls, many of parallelization schemes, excluding so-called the multi-start parallel scheme, try to extract parallelism from a local search by distributing the examinations of neighbors to processors. However, in straightforward implementations, when the next local search starts, all the processors will be assigned to the neighbors of the latest solution, and the results of all (but one) examinations in the previous local search are thus discarded in vain, despite that they would contain useful information on further search. This paper explores the possibility of extracting information even from unsuccessful neighbor examinations in a systematic way to boost parallel local search algorithms. Our key concept is neighborhood composition. We demonstrate how this idea improves parallel implementations on PVM, by taking as examples well-known local search algorithms for the Traveling Salesman Problem.続きを見る
|
Mendeley出力
