Fourth-Year Design Project, Part 5: Attempting the Partitioned Guided Improvement Algorithm
In the previous post, I covered the overlapping guided improvement algorithm (OGIA), which is the first of our group’s two multi-threaded approaches. We saw some dramatic improvements, but found that there is still a lot of duplicate work.
The subject of our next few posts is the partitioned guided improvement algorithm, our other multi-threaded approach. In contrast to OGIA, we trade simplicity for the guarantee that no duplicate solutions are found. In this post specifically, we will cover a little background, the inspiration behind this algorithm, and finally, a mistake we made.
Again, before continuing, you may want to refresh your memory on multi-objective optimization and the guided improvement algorithm (GIA).
Background
There were other groups before ours that worked with Professor Rayside to improve the guided improvement algorithm. In fact, all the other improvement ideas I have covered so far (incremental and checkpointed solving, and OGIA) originated from these groups or other collaborators. In contrast, the partitioned guided improvement algorithm (PGIA) was an idea we developed on our own, though the concept of “dividing the search space” is not an original idea.
Recall how we can plot solutions on a graph. This graph represents a search space of solutions, with a dimension (or axis on the graph) for each objective in the problem.1 The basic concept of PGIA, then, is to divide the search space into regions that can be searched in parallel.2
The interesting question is how we can divide the search space. Ideally, we want to divide the search space so that a locally optimal solution in a region is globally optimal for the whole problem. If we have this property, we can treat each region as a separate problem, search the regions in parallel, and then combine the solutions. We would not have to worry about duplicate solutions, or solutions from one region dominating solutions from another region.
I’ve illustrated some of the previous attempts to divide the search space. In
these examples, we’re dealing with two metrics (m1 and m2), so the search space
is two-dimensional.
Unfortunately, none of the attempts to divide the search space work, as locally optimal solutions may not be globally optimal. To demonstrate this, each diagram contains two solutions. One, marked with a dot, is locally optimal, but not globally optimal. The other, marked with an X, is both locally and globally optimal. The region it dominates is shaded, so we can see how it dominates the other solution.
A locally optimal solution that is not globally optimal is problematic for a few reasons. First, we wasted some work, finding a solution that we must discard. Also, the regions are no longer independent. Finally, we no longer have the property that the algorithm yields solutions as they are found. We have additional work to determine if a solution is actually globally optimal, which can only be done after all regions have been searched.
Our group picked up the work around this point. We were wondering how expensive the additional work would be, and if it even mattered in the long run. We were also wondering if we could minimize wasted work by finding “safe” regions, where locally optimal solutions were always globally optimal. We likely would have continued in this direction, if not for a key observation we made.
The key observation
The inspiration came when we drew the graph slightly differently. Normally, when a Pareto point is found, we would shade the region dominated by that Pareto point and exclude it from the search. However, we can shade and exclude another region—the “empty” area that dominates the Pareto point. There can be no solutions in that region, since we failed to find one while climbing up to the Pareto front.
By drawing the graph this way, we can think of the first Pareto point as splitting the search space into four regions, with two regions immediately excluded. This leaves two regions we have to search in. Furthermore, in both regions, a locally optimal solution is also globally optimal. In other words, we now have two independent regions that we can search in parallel.
We could also recursively apply this algorithm to each of the regions, as shown below.
However, this raises a few issues. If we keep recursively splitting, the number
of regions increases exponentially. We may require a lot of overhead in our
implementation to manage these regions. We may produce many small regions and
spend a lot of effort, only to find no solutions.3 Even if we split the search space only once, the number of
regions grows exponentially as we increase the number of objectives; for
N objectives, we will get 2N – 2 regions.
We started thinking about how we could handle these issues, but abandoned them when we discovered a serious problem.4
Discovering a flaw in the algorithm
Some of our test cases were failing. We examined the simplest failing test, a problem with three objectives. The regions were being divided properly and the solutions found were all locally optimal. However, compared to GIA, there was an extra solution that was not globally optimal. Our claim that locally optimal solutions are globally optimal was incorrect.
To see how this might be possible, let’s look at the test case. With three objectives, the number of regions to search in is 23 – 2 = 6. Our constraints will be given in terms of the first Pareto point the algorithm found, which is P = (10, 11, 9). The constraints will be of the form {(m1, m2, m3) such that m1 ■ 10, m2 ■ 11, m3 ■ 9}, where ■ is ≥ for “better than or equal” or < for “worse than”. For shorthand, I’ll simply write (■10, ■11, ■9).
In the table below, I’ve listed the constraints for each of the regions, as well as the metric points of the locally optimal metric solutions in each region. In this particular problem, we found one locally optimal solution in each region.
| Region | Constraint | Metric points of locally optimal solutions |
|---|---|---|
| A | (<10, <11, <9) | Excluded; all solutions dominated by P |
| B | (<10, <11, ≥9) | (9, 8, 12) |
| C | (<10, ≥11, <9) | (7, 13, 8) |
| D | (<10, ≥11, ≥9) | (6, 12, 12) |
| E | (≥10, <11, <9) | (14, 10, 8) |
| F | (≥10, <11, ≥9) | (11, 9, 10) |
| G | (≥10, ≥11, <9) | (11, 14, 8) |
| H | (≥10, ≥11, ≥9) | None; no solutions dominate P |
As expected, the metric points obey the constraints. They are also locally
optimal, though I have not shown the (locally) dominated metric points. However,
note that the metric point (7, 13, 8) is dominated by (11, 14, 8), which is
from a different region. In fact, for any given point in Region C, it is
possible a better one exists in Region G—we simply take the same metric
values, but set the first one to be greater than or equal to 10. Of course, that
point is only a valid solution if it meets the problem constraints, so it may
not actually exist. The possibility of its existence is the problem, since we
cannot guarantee the point in Region C is globally optimal.
Unfortunately, we cannot simply ignore Region C, just because we might be able
to find a better solution in Region G. For example, suppose the locally optimal
metric point in Region G is (11, 14, 8), and the locally optimal metric point
in Region C is (7, 15, 8). Neither solution dominates the other.
This is our dilemma: some locally optimal solutions are globally optimal, but not all locally optimal solutions are globally optimal.
Before we conclude this post, it’s interesting—and constructive—to examine why the algorithm worked with two objectives. Consider the diagram below, where we have a locally optimal solution in Region B. I’ve marked the area where we have to search to find a better solution, and it overlaps regions B and D. Thus, the only way to find a better solution in a different region is to find one in Region D. However, this is impossible, because Region D is empty. Therefore, any locally optimal solution in Region B is globally optimal. (A similar argument applies to Region C.)
Conclusion
In this post, I introduced the partitioned guided improvement algorithm, an attempt to divide the search space into regions that can be searched in parallel. We discussed some of the previous attempts, as well as the inspiration behind PGIA. Unfortunately, as presented, PGIA only works for bi-objective problems.
In the next part, we’ll continue our discussion of the partitioned guided improvement algorithm. We’ll see how the algorithm can be fixed so it works with any number of objectives.
I would like to thank Talha Khalid and Chris Kleynhans for proofreading this post.
Notes
^ Visualizing the search space for a bi-objective problem is straightforward, since the search space is a plane. A problem with three objectives is harder to visualize, but still feasible. Unsurprisingly, trying to visualize four or more dimensions is extremely difficult, if not impossible.
^ In one of the notes left behind was the warning “Beware: ideas that seem to intuitively work in two dimensions do not always generalize to three or more dimensions.”
^ In early prototypes, we observed that recursively splitting the search space helped with performance, but after a while, performance degraded. We suspect that the exponential number of regions, along with empty regions requiring effort, is the cause.
^ While working on this post, I managed to find some very old code from previous groups. It appears they had the same idea we had of splitting the search space. However, at the top of the file was the comment “Has correctness problems,” so I suspect we both encountered the same problem.