Evolutionary Computation for Multicomponent Problems: Opportunities and Future Directions

Mohammad Reza Bonyadi, Zbigniew Michalewicz, Markus Wagner, Frank NeumannOptimization in Industry 2016 · OpenReview

TL;DR

This paper argues that the field of Evolutionary Computation (EC) has focused too much on single-component problems, leading to a gap between academic research and the complex, interconnected "multicomponent" problems faced by real-world industries. The authors propose that EC is well-suited to tackle these challenges due to its flexibility and encourage more research into modeling and solving problems with interdependencies.

What Problem Does This Paper Address?

For decades, researchers have developed Evolutionary Computation (EC) methods to solve complex optimization problems, often inspired by industry needs. However, the authors observe a disconnect: despite significant progress in EC, its real-world applications haven't kept pace. They identify a key reason for this gap: most research and benchmark problems focus on "single-component" or "single-silo" problems, where a single objective or task is optimized in isolation. In contrast, real-world problems are often "multicomponent," meaning they consist of several interconnected subproblems (components) that influence each other. Optimizing these components independently doesn't necessarily lead to an optimal solution for the overall problem. The paper aims to highlight this mismatch and advocate for a shift in EC research towards multicomponent problems.

Methods

The paper doesn't introduce a new algorithm but rather provides a conceptual framework and motivation for future research. The authors:

  • Revisit the trajectory of EC: They analyze the historical focus of EC research and its alignment with real-world problem complexities.
  • Define "multicomponent problems": They introduce and explain the concept of problems composed of several interdependent subproblems.
  • Illustrate with examples: They use a physical puzzle ("Cast Marble") and two real-world scenarios (water tank delivery and wine supply chain) to demonstrate the nature of multicomponent problems and the dependencies between their components.
  • Propose a definition of dependency: They formally define when one component is dependent on another, focusing on how changing one component's solution affects the best achievable solution for another.
  • Introduce a benchmark problem: They discuss the Traveling Thief Problem (TTP) as an example of a multicomponent benchmark that combines the Traveling Salesman Problem (TSP) and the Knapsack Problem (KP) with a dependency.
  • Discuss modeling challenges: They explore different ways to model multicomponent problems (monolithic vs. component-based) and the implications of dependencies.
  • Suggest EC approaches: They highlight cooperative coevolution as a promising EC paradigm for multicomponent problems.

Datasets

Not discussed in the paper. The paper focuses on conceptualizing multicomponent problems and uses illustrative examples and existing benchmark problems (like TSP and KP, combined in TTP) rather than introducing new datasets for empirical evaluation.

Key Insights and Ideas

  • The "Single-Silo" vs. "Multicomponent" Divide: The core insight is that the EC community's focus on isolated problems (single-silo) has created a gap with the interconnected nature of real-world industrial challenges.
  • Dependencies are Key: The paper emphasizes that dependencies between components are the primary source of complexity in multicomponent problems, making them significantly harder than the sum of their parts.
  • Holistic Treatment is Necessary: Drawing from early Operations Research literature, the authors reiterate that problems require "holistic treatment" and cannot be effectively solved by decomposing them into independent subproblems.
  • Cooperative Coevolution as a Natural Fit: The paper suggests that EC techniques, particularly cooperative coevolution (where multiple subpopulations evolve components and collaborate), are inherently suited to handle the interdependencies in multicomponent problems.
  • Modeling is Crucial and Complex: Modeling multicomponent problems is challenging. Component-based modeling, while more complex to integrate, offers advantages in modularity and leveraging existing knowledge compared to monolithic approaches.
  • Real-world Optimality vs. Model Optimality: The paper acknowledges that true global optimality in real-world scenarios is often less critical than finding good solutions quickly, given that models are simplifications and environments are dynamic.

Key Results

The paper is primarily a conceptual and motivational work, not an empirical study with quantitative results. Its "results" are in the form of insights and arguments:

  • Identification of a research gap: The paper clearly articulates the mismatch between EC research focus and real-world problem complexity.
  • Conceptualization of multicomponent problems: It provides a framework for understanding and discussing these problems.
  • Demonstration of dependencies: Through examples, it illustrates how optimizing components in isolation can fail.
  • Advocacy for EC: It argues that EC's flexibility makes it a strong candidate for solving these complex, interdependent problems.

Limitations and Future Work

Limitations:

  • Lack of Abstract Benchmarks: The authors note a scarcity of abstract benchmark problems that specifically capture the dependencies found in multicomponent real-world scenarios.
  • Theoretical Underpinnings: While cooperative coevolution is suggested, the paper acknowledges that much of the work in this area is "ad hoc" and lacks strong theoretical guidance.
  • Modeling Complexity: The paper highlights the difficulty in accurately modeling multicomponent problems, especially when dependencies are intricate.

Future Work:

  • Developing New Benchmarks: There's a need for abstract problems that effectively represent dependencies to drive research.
  • Systematic Investigation of Dependencies: Research should focus on understanding how dependencies impact algorithm performance and parameter tuning.
  • Exploring Modeling Approaches: Further work is needed on effective ways to model multicomponent problems, potentially leveraging existing knowledge of individual components.
  • Computational Complexity Analysis: Applying computational complexity analysis to multicomponent problems and their interactions is crucial for understanding their hardness and designing efficient algorithms.
  • Feature-Based Analysis: Analyzing the statistical features of underlying subproblems and their interactions could guide algorithm selection and design.
  • Bridging the Gap: The ultimate goal is to close the gap between academic EC research and the practical needs of industries for solving complex, multicomponent problems.

Summary updated

Abstract

Over the past 30 years, many researchers in the field of evolutionary computation have put a lot of effort to introduce various approaches for solving hard problems. Most of these problems have been inspired by major industries so that solving them, by providing either optimal or near optimal solution, was of major significance. Indeed, this was a very promising trajectory as advances in these problem-solving approaches could result in adding values to major industries. In this chapter, we revisit this trajectory to find out whether the attempts that started three decades ago are still aligned with the same goal, as complexities of real-world problems increased significantly. We present some examples of modern real-world problems, discuss why they might be difficult to solve, and whether there is any mismatch between these examples and the problems that are investigated in the evolutionary computation area.
BibTeX
@inproceedings{bonyadi2016evolutionary,
  author = {Mohammad Reza Bonyadi and Zbigniew Michalewicz and Markus Wagner and Frank Neumann},
  title = {{Evolutionary Computation for Multicomponent Problems: Opportunities and Future Directions}},
  booktitle = {Optimization in Industry},
  year = {2016},
  url = {https://openreview.net/forum?id=C7JqD9Sl4k},
}
Figure