0

I am learning about the GRASP (Greedy Randomized Adaptive Search) meta-heuristics.

From what I understood, GRASP is based on two main phases. The first one:

Construct a initial solution based on a greedy and random strategy

and the second one:

Construct a local search on the previous found solution

The question that I have is for the first phase. Do I have to create a feasible solution?

Am I allowed maybe to create an infeasible solution in the first phase of the algorithm, and then use local search to find a feasible solution?

EDIT:

Basically I have the Weighted Partial Max SAT problem. The idea is that I have to maximize the sum of all the satisfied soft clauses, while at the same time satisfying all hard clauses.

What I was thinking is to create an initial solution (maybe infeasible) that tries to maximize the number of satisfied soft clauses. After that I want to use a local search to optimize the solution even more, or make it feasible if necessary.

I want to know if that is a valid strategy, because the initial construction may create an infeasible solution.

Community
  • 1
lhahn
  • 113
  • 5
  • Could you explain what precisely you mean by “feasible solution” in contrast to an ordinary “solution”? In the GRASP strategy, the initial solution must solve the problem, i.e. be valid and feasible, but not necessarily locally optimal. E.g. when using GRASP to do pathfinding, the initial solution must be any path connecting the start with the end location, and the local search is then used to optimize this path. A not-correct solution (e.g. a path that ends at some other location) is not useful, since a local search cannot derive a correct solution from it. – amon Jun 28 '15 at 15:53
  • I'll edit with a better explanation. – lhahn Jun 28 '15 at 16:03

0 Answers0