An objective-guided multi-strategy evolutionary algorithm for multi-objective coalition formation

The coalition formation (CF) problem is crucial for reasonably organizing agents with diverse and complementary capabilities to address complex scenarios in collaborative environments. While CF has received some research attention, the multi-objective coalition formation (MOCF) problem remains relatively unexplored and presents significant challenges. In the context of disaster relief and emergency response, this paper delves into the MOCF problem and constructs the mathematical model, which minimizes both the latest arrival time and the total cost of coalition members under mission-specific capability constraints. To tackle this, this paper proposes an innovative objective-guided multi-strategy evolutionary algorithm (OGMSEA) for effective capability aggregation regarding mission requirements and objective trade-offs, which leverages the problem characteristics of multiple objectives and lower-bound constraints. The initialization strategies leverage various objective weights to generate a uniformly distributed and extensive set of initial solutions. The repair strategies restore unsatisfied coalitions by evaluating the alignment of idle agents with the remaining capability requirements and optimization objectives. The restart strategies reconstruct repetitive solutions to maintain the population diversity. Comprehensive experiments demonstrate OGMSEA's superior performance in terms of applicability and adaptability, better achieving inverted generational distance and hypervolume metrics across 135 various cases compared with advanced algorithms. In large-scale complex scenarios (e.g., more than 100 agents, 10 missions, and a demand-supply ratio on capabilities of 0.5), OGMSEA consistently achieves a high-quality Pareto front due to its well-designed strategies. Additionally, a forest fire scenario is constructed and addressed by forming firefighting coalitions, demonstrating the practical applicability of this study.