Questions tagged [local-search]
For questions related to local search algorithms used in AI (e.g. 2-opt or hill climbing).
10 questions
1
vote
0
answers
34
views
CSP heuristic to simultaneously reduce conflicts and find near optimal assignment
I am trying to design a good heuristic to solve a constraint satisfaction problem (CSP). I think that a possible heuristic to use is
$$h_1(\text{state}) = \text{number of conflicts in state}$$
However,...
- 11
6
votes
1
answer
3k
views
What is the difference between Stochastic Hill Climbing and Simulated Annealing?
I am reading about local search: hill climbing, and its types, and simulated annealing
One of the hill climbing versions is "stochastic hill climbing", which has the following definition:
...
- 217
1
vote
0
answers
438
views
Can we solve an $8 \times 8$ sliding puzzle using hill climbing?
Can we solve an $8 \times 8$ sliding puzzle using a random-restart hill climbing technique (steepest-ascent)? If yes, how much computing power will this need? And what is the maximum $n \times n$ that ...
- 11
8
votes
2
answers
482
views
How can I solve the zero subset sum problem with hill climbing?
I want to solve the zero subset sum problem with the hill-climbing algorithm, but I am not sure I found a good state space for this.
Here is the problem: consider we have a set of numbers and we want ...
- 181
2
votes
2
answers
426
views
Why is a mix of greedy and random usually "best" for stochastic local search?
I read that a mix of "greedy" and "random" are ideal for stochastic local search (SLS), but I'm not sure why. It mentioned that the greedy finds the local minima and the randomness avoids getting ...
- 351
3
votes
1
answer
1k
views
Why does the hill climbing algorithm only produce a local maximum?
Apparently, the hill climbing algorithm just produces a local maximum, and not necessarily a global optimum. It's stuck on a local maximum. Why does hill climbing algorithm only produce a local ...
- 61
4
votes
1
answer
255
views
What is the basic purpose of local search methods?
I read about the hill climbing algorithms, the simulating annealing algorithm, but I am confused. What is the basic purpose of local search methods?
- 315
7
votes
1
answer
16k
views
What is an objective function?
Local search algorithms are useful for solving pure optimization problems, in which the aim is to find the best state according to an objective function.
My question is what is the objective function?
- 566
6
votes
1
answer
11k
views
What is the difference between local search and global search algorithms?
What is the difference between local search and global (or complete) search algorithms?
- 171
8
votes
2
answers
415
views
Are there local search algorithms that make use of memory to give better solutions?
I have been studying local search algorithms such as greedy hill-climbing, stochastic hill-climbing, simulated annealing, etc. I have noticed that most of these methods take up very little memory as ...
- 81