This paper introduces the Metacognitive LLM-Based Architecture (MeLA), a novel paradigm for automated heuristic design (AHD). Unlike existing evolutionary methods that directly evolve the heuristic code itself, MeLA evolves directional prompts that guide a large-scale language model (LLM) to generate heuristics. This "prompt evolution" process is driven by a novel metacognitive framework that systematically refines the generation strategy by analyzing performance feedback. MeLA's architecture integrates a problem analyzer that constructs initial strategic prompts, an error diagnosis system that corrects faulty code, and a metacognitive search engine that iteratively optimizes the prompts based on heuristic efficiency. In comprehensive experiments on benchmark and real-world problems, MeLA consistently outperforms existing state-of-the-art methods, generating more effective and robust heuristics. Ultimately, this study demonstrates the potential of using cognitive science as a blueprint for AI architecture, demonstrating that LLM can metacognitively guide problem-solving processes, opening up a more robust and interpretable path to AHD.
