halting on sub-optimal solution

classic Classic list List threaded Threaded
2 messages Options
Reply | Threaded
Open this post in threaded view
|

halting on sub-optimal solution

nkgxgongxi
Hi everyone,

Could anyone help me by providing me some advice on how to make the searching more efficient?

I wrote a program based on OptaPlanner to solve a scheduling problem, and I knew the expected optimal solution. My program runs well to keep finding better solution, however, when it comes to a solution which is really close to the optimal one, the program just halts there. I mean, it keeps searching, but can't reach the optimal even after 10hrs of running time.

I am currently using tabu search and simulate Annealing to control the local search, and I have tried several different combinations of parameters, but there is no improvement found.

I will appreciate your help.

Regards,
Gong
Reply | Threaded
Open this post in threaded view
|

Re: [rules-users] halting on sub-optimal solution - OptaPlanner

ge0ffrey
Administrator
It might be stuck in a local optima, some things to check:

A) Read the section "score trap" in the docs, to verify you don't have a
score trap

B) The default move types (<changeMoveSelector> and <swapMoveSelector>)
aren't strong enough to escape local optima.
B1) Try adding a <pillarSwapMoveSelector>.
I am adding a pillarChangeMove for 6.1.0.Beta4, and probably also
support for selecting subpillars.
B2) Take a look at that suboptimal best solution and figure out what
course-grained move it needs to do to escape the local optima.
Then either creates a custom Move (see docs "MoveListFactory")
B3) or compose the build-in ones with <cartesianProductMoveSelector> and
mimicSelection.

C) For very small datasets, tabu search's entity size can be too large
(especially with subchain move selectors and pillar move selectors).
Tabu ratio (see docs) is a way around that.

D) If your dataset is really small, you can always just switch to brute
force
or the much faster branchAndBound (as of 6.1.0.Beta3).
Note: neither scale to medium/big datasets.

HTH

On 02-05-14 17:06, nkgxgongxi wrote:

> Hi everyone,
>
> Could anyone help me by providing me some advice on how to make the
> searching more efficient?
>
> I wrote a program based on OptaPlanner to solve a scheduling problem, and I
> knew the expected optimal solution. My program runs well to keep finding
> better solution, however, when it comes to a solution which is really close
> to the optimal one, the program just halts there. I mean, it keeps
> searching, but can't reach the optimal even after 10hrs of running time.
>
> I am currently using tabu search and simulate Annealing to control the local
> search, and I have tried several different combinations of parameters, but
> there is no improvement found.
>
> I will appreciate your help.
>
> Regards,
> Gong
>
>
>
> --
> View this message in context: http://drools.46999.n3.nabble.com/halting-on-sub-optimal-solution-tp4029411.html
> Sent from the Drools: User forum mailing list archive at Nabble.com.
> _______________________________________________
> rules-users mailing list
> [hidden email]
> https://lists.jboss.org/mailman/listinfo/rules-users
>


_______________________________________________
rules-users mailing list
[hidden email]
https://lists.jboss.org/mailman/listinfo/rules-users