Logo PTI Logo FedCSIS

Proceedings of the 21st Conference on Computer Science and Intelligence Systems (FedCSIS)

Annals of Computer Science and Information Systems, Volume 47

Preserving Optimization Algorithm Expertise by means of Executable Algorithm Knowledge Graphs: A Worked Example on the TSP

, , ,

DOI: http://dx.doi.org/10.15439/2026F2986

Citation: Camilo Chacón Sartori, , ,

Full text

Abstract. Procedural knowledge and expertise in algorithm design are usually hidden in source code and reproduced for each new optimization problem. In this work, we deal with the important question of how to store and encode this expertise in a reusable way. This is done by so-called Generative Executable Algorithm Knowledge Graphs (GEAKGs), which store expertise as a typed, executable graph: nodes are algorithmic roles that hold validated operators, edges encode admissible compositions, learned pheromone weights record effective sequences, and a deterministic Symbolic Executor produces solutions by traversal with no runtime language-model calls. This paper is a worked example. We construct a GEAKG for the Traveling Salesman Problem step by step---deriving an eleven-role schema, generating and validating executable operators, assembling an ontologyconstrained topology, and learning edge weights with the MAX--MIN Ant System---and then run it. The frozen snapshot returns feasible solutions across three model scales, including a fully local model, and reaches single-digit-percent optimality gaps at zero deployment tokens. A controlled check confirms that the ontology constraint lowers the search gap by concentrating it on valid transitions. The cross-domain transfer study is deferred to the companion full version; the goal here is a reproducible recipe for building and executing this representation on a single domain.

References

  1. C. Chacón Sartori, J. H. García, A. V. Tomut, and C. Blum, “GEAKG: Generative executable algorithm knowledge graphs,” arXiv preprint https://arxiv.org/abs/2603.27922, 2026.
  2. A. Hogan, E. Blomqvist, M. Cochez et al., “Knowledge graphs,” ACM Computing Surveys, vol. 54, no. 4, pp. 1–37, 2021.
  3. M. Dorigo and T. Stützle, Ant Colony Optimization. MIT Press, 2004.
  4. T. Stützle and H. H. Hoos, “MAX–MIN ant system,” Future Generation Computer Systems, vol. 16, no. 8, pp. 889–914, 2000.
  5. N. van Stein and T. Bäck, “LLaMEA: A large language model evolutionary algorithm for automatically generating metaheuristics,” IEEE Transactions on Evolutionary Computation, vol. 29, no. 2, pp. 331–345, 2025.
  6. B. Romera-Paredes, M. Barekatain, A. Novikov et al., “Mathematical discoveries from program search with large language models,” Nature, vol. 625, pp. 468–475, 2024.
  7. F. Liu, X. Tong, M. Yuan, X. Lin, F. Luo, Z. Wang, Z. Lu, and Q. Zhang, “Evolution of heuristics: Towards efficient automatic algorithm design using large language model,” in Proc. Int. Conf. on Machine Learning (ICML), 2024, pp. 32 201–32 223.
  8. H. Ye, J. Wang, Z. Cao, F. Berto, C. Hua, H. Kim, J. Park, and G. Song, “ReEvo: Large language models as hyper-heuristics with reflective evolution,” in Advances in Neural Information Processing Systems (NeurIPS), 2024.
  9. H. R. Lourenço, O. C. Martin, and T. Stützle, “Iterated local search: Framework and applications,” in Handbook of metaheuristics. Springer, 2019, pp. 129–168.
  10. G. Reinelt, “TSPLIB—a traveling salesman problem library,” ORSA Journal on Computing, vol. 3, no. 4, pp. 376–384, 1991.