Wednesday, February 19, 2014

Outlier hypercube refinement optimization with example

I'll explain this optimization method with an example I made up, suppose you have two points and you want to find a path connecting them of length 10 when the straight line distance between them is 5. Further restrictions are that you will make your path with 6 segments, and that you want the x values of these 5 middle points to be increasing from left to right and the y values greater or equal to the starting points.
The first step of this method is to divide the search space up very roughly, To this end, I started with a further restriction that every point also be on an integer grid, and it seemed sensible to make this grid from bottom left to top right (0,0) to (5,5) in size. One can see that there would be 6*6*6*6 or 1296 possibilities to test on this grid, so I wrote a program that tested the 1296 possibilities keeping the top 5% of solutions. Meaning the 60 possibilities on this grid that came the closest in total arc length to 10 without going over 10. These 60 possibilities look like this:
This is a random selection of 13 of the top 60 solutions. Because of the constraints the x values of each solution had to be (0,1,2,3,4,5) but it was easy to see that these top 10% solutions all fell underneath the y values (0,3,4,4,3,0). So visually that cut down the search space like so:
This cuts the actually good range of the solutions to 400 possibilities or 1/3 of the original search space.
So now I looked over that range but in intervals of (1/2) instead of integer values.
Now I found that the best 10 solutions were all within 1/10000 of length 10 so I stopped. But if I wanted to be more precise the best solutions were within the red rectangles which would further cut down the search space. The black dots are one of the very best solutions found so far, there were 6 that were tied for the best:
[ ((0, 0), (1.5, 2.5), (2.5, 4.0), (3.5, 4.0), (4.5, 1.0), (5, 0)))]
which has length: 9.99856323407292

So I think this method of roughly dividing the search space, looking at the top small percentage of solutions, then refining the search space based on the extreme values of those solutions and searching that space with more refinement works well to cut down on the amount of time needed to find a very good solution.

No comments:

Post a Comment