Questions tagged [heuristics]
Referring to methods that produce good "approximate" solutions, particularly for np-hard, np-complete, or combinatorial optimization problems.
16
questions
0
votes
0
answers
25
views
Do the class of Construction Heuristic that does or does not change previous decisions have a name?
I'm writing a paper where I am discussing different types of construction heuristics.
One type does not change previous decisions when adding new elements to the solution. I'd call them "...
- 109
0
votes
1
answer
645
views
How to generate neighbors for simulated annealing
I am learning about simulated annealing algorithm and want to create a general purpose one for optimizing continuous functions.
The problem I have is how to generate the neighbor points as candidates. ...
0
votes
2
answers
219
views
Is this a knapsack problem?
I have a set of $K$ keywords. Each of this keywords can have set of bids from $1\$,\dots,N\$$. For each bid for a keyword, it will get a specific amount of clicks and a specific cost. Clicks and Cost ...
- 153
1
vote
2
answers
1k
views
GSA Search Algorithm in C++
Is there any version of GSA (Gravitational Search Algorithm)[1] implemented with C++ or even C#?
What I found was implemented using MATLAB which is not good for me.
[1] Rashedi, Esmat, Hossein ...
- 13
1
vote
1
answer
62
views
Finding optimal point distance to get desired number of random points in an area
I have a random point generator which takes a distance $d$ and fills an area with points such that distance between any two points is no less that $d$:
I need to control the number of points in the ...
- 393
5
votes
1
answer
259
views
Striking examples of success of local search algorithms
In N queens problem https://en.wikipedia.org/wiki/Eight_queens_puzzle, trying to find solution by backtracking encounters difficulties quite fast (even for SWI-Prolog, http://swish.swi-prolog.org/...
- 223
0
votes
1
answer
332
views
Comparing computational complexity of convex optimization and a heuristic algorithm
I am working on a resource allocation problem, which is convex and has several constraints, and I want to compare the computational complexity of the following algorithms.
1) The algorithm that uses ...
- 101
0
votes
2
answers
305
views
Statistical analysis of optimization algorithms
If we optimize some parameter using 4 optimization algorithms, 2 of which are population based (say A and B) and 2 trajectory methods (single point search)(say C and D); what statistical test can be ...
- 1
10
votes
3
answers
5k
views
Sort of problems where SOR is faster than Gauss-Seidel?
Is there any simple rule of thumb to say if it is worth to do SOR instead of Gauss-Seidel? ( and possible way how to estimate realxation parameter $\omega$)
I mean just by looking on the matrix, or ...
- 907
0
votes
1
answer
314
views
Find closest Point based on orientation and Euclidean distance
I have a set of points P1(x1,y1), P2(x2,y2), P3(x3,y3), P4(x4,y4), P5(x5,y5) in the Cartesian plane. I am trying to find the closest point to P1 based on the ...
- 175
0
votes
1
answer
76
views
Extension of research on optimisation to a relatively complex level [closed]
I'm doing research for academic credential on the use of metaheuristic optimisation of building envelopes/enclosures, focusing on the aspect of its thermal performance.
The subject was handled with ...
- 103
4
votes
1
answer
191
views
What strategies one can use to keep maximum number of non attacking pieces on an $n \times n$ chess board? [closed]
What are the strategies one can use to keep maximum number of non attacking pieces (all pieces other than pawn) on an $n\times n$ board? It is like an $n$-queen problem but here instead of only queen ...
- 41
4
votes
1
answer
217
views
Expectation-Maximization and local maxima
The E-M algorithm does not guarantee convergence to global maxima. Following Applet shows this nicely: http://www.cs.cmu.edu/~alad/em/
Is it possible to generate data set, that guarantees reaching ...
- 81
3
votes
2
answers
387
views
How to prove that my problem is np-hard
For an assignment i need to program an application to schedule conversations. Something similar to speeddating or Pta meeting.
The problem is that i know that this is hard to solve, but i dont know if ...
- 131
10
votes
2
answers
4k
views
Meaning of (meta)heuristic methods
For optimization, from Wikipedia:
In computer science, metaheuristic designates a computational method
that optimizes a problem by iteratively trying to improve a candidate
solution with regard ...
- 1,281
7
votes
2
answers
543
views
What heuristics can be used to minimize the asymptotic matrix bandwidth of a 5-point Laplacian discretization?
I can see that there are multiple heuristics to achieve a matrix with minimum bandwidth. As heuristics, they can't guarantee an optimal solution in polynomial time (after all, the problem is NP-...
- 12k