Integrating evolutionary algorithms with large language models for enhanced problem solving

Abstract

Evolutionary computation (EC) is a computational method motivated by biological evolution and has been widely recognized for its effectiveness in solving complex and computationally expensive optimization problems. Recent advancements in Large Language Models (LLMs) have empowered Automatic Heuristic Design (AHD), a field dedicated to the automated creation of effective heuristics for a given problem, to process natural language descriptions and code, enabling generations of diverse algorithms through evolutionary operations. However, previously proposed frameworks of AHD could easily suffer from premature convergence due to their inability to capture the contextual information of the iterative optimization process and to diversify the population. Furthermore, only partial information about the thinking process of LLM could be captured despite its automatic operations of generating codes.

Devised to handle those gaps, this is the first study that applies Parrondo's paradox-inspired evolutionary computation in AHD, unveiling the potential avenue for the application of Parrondo's paradox in the engineering field. This study introduces a novel LLM-empowered AHD designed to extend the search capability by commanding rational inference and random operations. This was achieved by the introduction of the essence of Parrondo's paradox, a superficially paradoxical phenomenon that the synthesis of two losing games in a certain manner can yield a winning outcome. PPLLM outperformed the earlier LLM-empowered AHDs: those empirical results underscore the efficacy of incorporating both rational and random search mechanisms to maintain solution diversity and escape premature convergence in AHD.