4
$\begingroup$

I have a local search problem. The set of valid solutions are all the simple paths (i.e. without repeated nodes) from a node $S$ to a node $T$ in a directed graph.

The question is: given a current solution (an $S$-$T$-path), how can I generate a set of neighbour solutions?

To elaborate, I have an optimization (minimization) problem, on which I have to select the "best" path $S$-$T$ path. The evaluation function is complex and can't be evaluated until all the edges in the path are known. This plus the fact that the number of paths is exponential, lead me to draw on local search.

I know how to find an initial solution in polynomial time. The only piece missing in order to be able to use a local search algorithm (i.e. hill climbing) is to be able to generate a set of successors from the current path. I find this not to be trivial because simply switching one random node in the path for one not in it does not necessarily generate a still valid $S$-$T$ path.

Edit: I did not want to enter in the details of my specific problem because I think the question about how to define a relationship of neighbourhood in the space of path graphs is interesting in itself. But since you have asked, this is the evaluation function: $$\mbox{length}(\mbox{path}) \times \sum_{i=1}^n \left ( p_i \times -\mbox{log}_2(p_i) \right )$$, where $p_i$ is the relative frequency of nodes in the path tagged with the number $i$ (every node in the graph is tagged with a number $1..n$.

$\endgroup$
  • $\begingroup$ I asked a similar question here, but it deals with shortest $s$-$t$ paths. $\endgroup$ – Juho May 5 '14 at 16:51
  • 1
    $\begingroup$ Indeed, I intend to use a shortest-path algorithm in order to find a starting solution for the local search in polynomial time. But in my case, the optimal solution is not necessarily a shortest path. $\endgroup$ – nmamg May 5 '14 at 16:54
  • 1
    $\begingroup$ How do you define a local neighbor of a path $P$? $\endgroup$ – Juho May 5 '14 at 17:01
  • 1
    $\begingroup$ It would help if you posted you quality measure; maybe it's possible to derive a local variant that allows application of standard algorithms. As for the local search, I don't know if there are standard ways but it's certainly possible to swap out partial paths. Also, k-shortest paths may be a useful start, in particular if shortest paths are somewhat good (i.e. shortness correlates with quality). Furthermore, did you check that your measure is compatible with hill climbing, or are you okay with suboptimal solutions? Otherwise, full enumeration looms. $\endgroup$ – Raphael May 5 '14 at 17:39
  • 1
    $\begingroup$ How about you use a genetic algorithm for this then? Path are your individuals. You don't need to worry about what exactly a neighbor of a path is, but instead modify subpaths of a path $P$. For mutation, you can use a randomized DFS or something similar. Look for other methods as well, such as ACO. $\endgroup$ – Juho May 6 '14 at 7:40
1
$\begingroup$

I can't comment yet, so I'll post this as an answer:

Assuming you can find the S-T path with a pathfinding algorithm, why not use the same algorithm with an "antiheuristic" topology?

enter image description here

As you increase the "heat," the further away your found paths will be from your initial solution.

Additionally, you could add some grainy noise wavelets, or random hills and valleys, into the landscape to toss things up a little.

But still:

The evaluation function is complex and can't be evaluated until all the edges in the path are known

This is always the case. It is usually better to try and find a proper heuristic/path abstraction than monte-carloing it. I recommend you post more info about your problem.

$\endgroup$
  • $\begingroup$ Hm. depending on the layout of the data you could try a heuristic strategy that simply favours one dominant node, and, when given no choice, picks a node that hasn't been picked yet (preferrably) or fills up the next most dominant node $\endgroup$ – guest May 6 '14 at 19:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.