Title: Bi-Component Coupled Combinatorial Optimization via LLM-Driven Co-Evolutionary Automated Heuristic Design

Abstract:

Although Large Language Models (LLMs) have demonstrated potential in Automated Heuristic Design (AHD), current approaches generally generate and evolve heuristics as isolated operators or search strategies. This limitation hinders their capacity to effectively model the strong coupling inherent in multiple decision substructures, a characteristic common in complex problems like the Traveling Thief Problem (TTP) and the Traveling Purchaser Problem (TPP). To address this, we introduce CoEvo-AHD, a novel LLM-driven dual-population co-evolutionary framework designed for automated heuristic design in coupled combinatorial optimization.

Departing from previous methods that evolve individual heuristics independently, CoEvo-AHD utilizes LLMs to co-evolve two interrelated operator populations. The framework incorporates a cooperative evaluation mechanism that explicitly accounts for the interactions between route and selection operators. Furthermore, it employs pairwise scoring and synergistic joint crossover techniques to uncover complementary operator logic, facilitating joint improvements across coupled decision subspaces.

Additionally, we have developed a tool-invocation environment library that encapsulates essential core operations, such as local-search delta computation, into callable functions. This design allows LLM-generated operators to leverage standardized interfaces, thereby avoiding the need to implement inefficient and error-prone problem-specific loops. Experimental results on the TTP and TPP indicate that CoEvo-AHD successfully identifies cooperative heuristic combinations, delivering competitive solution quality when compared to traditional heuristic methods.

Source: arXiv Generated at: 2026-06-02 00:00:00 UTC