How to perform local search on simple paths? 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$.
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? 



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.