Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2411.05263 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913580974080000 |
|---|---|
| author | Wallace, Mark G. |
| author_facet | Wallace, Mark G. |
| contents | This paper investigates what properties a neighbourhood requires to support beneficial local search. We show that neighbourhood locality, and a reduction in cost probability towards the optimum, support a proof that search among neighbours is more likely to find an improving solution in a single search step than blind search. This is the first paper to introduce such a proof. The concepts underlying these properties are illustrated on a satisfiability problem class, and on travelling salesman problems. Secondly, for a given cost target t, we investigate a combination of blind search and local descent termed local blind descent, and present various conditions under which the expected number of steps to reach a cost better than t using local blind descent, is proven to be smaller than with blind search. Experiments indicate that local blind descent, given target cost t, should switch to local descent at a starting cost that reduces as t approaches the optimum. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_05263 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Minimal Conditions for Beneficial Neighbourhood Search and Local Descent Wallace, Mark G. Artificial Intelligence This paper investigates what properties a neighbourhood requires to support beneficial local search. We show that neighbourhood locality, and a reduction in cost probability towards the optimum, support a proof that search among neighbours is more likely to find an improving solution in a single search step than blind search. This is the first paper to introduce such a proof. The concepts underlying these properties are illustrated on a satisfiability problem class, and on travelling salesman problems. Secondly, for a given cost target t, we investigate a combination of blind search and local descent termed local blind descent, and present various conditions under which the expected number of steps to reach a cost better than t using local blind descent, is proven to be smaller than with blind search. Experiments indicate that local blind descent, given target cost t, should switch to local descent at a starting cost that reduces as t approaches the optimum. |
| title | Minimal Conditions for Beneficial Neighbourhood Search and Local Descent |
| topic | Artificial Intelligence |
| url | https://arxiv.org/abs/2411.05263 |