Login / Register to comment

Series Hybrid vs. Parallel Hybrid

April 18, 2012 by Ron Averill

Hybrid refers to something that is made up of two or more diverse ingredients. The goal in combining them is to capture and merge the advantages of each ingredient, while overcoming any disadvantages. But ingredients can be combined in many ways, resulting in considerable variation in performance depending on how they are combined.

In optimization search algorithms, as with electric vehicles, there are two main categories of hybrids: series and parallel. To better understand the basic differences between the series and parallel hybrid approaches, let’s consider a simple illustration.

Passing batonSuppose a team of people needs to carry an object a long distance. In a series hybrid strategy, one person will carry the object for a while, and then someone else will take the load and carry it a bit further. This “tag team” approach continues until the required distance is covered. This series approach might work well if the object is lightweight and small. But if the object is heavy or awkwardly shaped, then it will be difficult for one person to carry it even a short distance, if he or she can move it at all.

RowersIn this situation, it is clearly more effective for two or more people to carry the object together in a parallel hybrid approach. By working together in a well-coordinated effort, the load can be shared in a way that allows each participant to contribute to the task. Each contribution, however small, reduces the load on other team members, allowing the group to carry the load faster and further with less fatigue. Drivers of horse-drawn wagons, dog sleds and Christmas sleighs discovered this truth a long time ago.

Series hybrid optimization
Turning our attention to optimization, a series hybrid algorithm is developed by starting with one search algorithm, and then switching to another one (using a different strategy than that of the first algorithm) to continue the search. There is no limit to the number of different search strategies that can be used in this sequential manner.

Typically, a series hybrid algorithm begins with a search method that is good at global exploration, such as a Genetic Algorithm, and ends with a local refinement strategy, such as a gradient-based algorithm. Various other search methods can be sandwiched between these two. On some problems, this type of series optimization algorithm has been shown to perform reasonably well compared to monolithic (single-strategy) algorithms, when an appropriate set of algorithms and tuning parameters has been chosen.

How well a series hybrid optimization strategy performs depends on the specific algorithms and tuning parameters used at each stage of the search. Because each algorithm is working alone, the progress made at any time depends on how effective the selected method is for that problem and what it does with the information provided by previous search methods.

As I’ve mentioned in other posts, it is usually impossible to know which algorithms or values of tuning parameters will work well on a problem before it is solved. So, series hybrid algorithms have the same fatal flaw as most monolithic strategies, except the number of unknowns is now multiplied by the number of different strategies used.

Moreover, additional unknowns are introduced, such as the order of the strategies and when to stop one strategy in favor of another. Default values for these parameters may or may not work well for your current problem.

Parallel hybrid optimization
Parallel hybrid algorithms, like SHERPA (in HEEDS® MDO), overcome many of the shortcomings of series hybrid algorithms. In this strategy, multiple optimization methods actually work simultaneously to solve a problem in a collaborative fashion. Rather than contributing sequentially, these methods work together to search a design space and identify optimized solutions, like many hands helping to carry a heavy load.

As with any good team, a parallel hybrid algorithm requires good leadership, communication, coordination, and accountability. These attributes are built into the algorithm’s infrastructure from the start.

Instead of separately exploring and refining at different stages of a search, a parallel hybrid algorithm enables these two essential activities to take place concurrently and synergistically! This not only speeds up the search but also makes it more likely to find the global optimum.

In a series hybrid algorithm, the search history can be used to determine which individual algorithm(s) made the most meaningful contribution to the search. But this is not possible with a parallel hybrid algorithm, because each algorithm behaves very differently as part of a team than it would individually.

Nevertheless, there are ways to hold an individual search strategy accountable for its contributions within a parallel hybrid algorithm, and those methods that do not contribute enough over time can be replaced by new methods or have their resources transferred to existing methods that are contributing at a higher level.

The characteristics of a well-designed parallel hybrid optimization algorithm include shared discovery, intellectual diversity, synergistic search, and greater robustness. Oh, and better designs, faster!