This study introduces two heuristic-based solvers inspired by Wolfram’s Elementary Cellular Automaton. The solvers use the automaton rules to solve combinatorial optimization problems using two relatively different strategies. The first solver uses the rules to combine solutions produced by individual heuristics. In contrast, the second uses the rules to combine heuristics and later uses such heuristics to solve the problem. As we can observe, the second solver addresses the solving process indirectly. These solvers were tested on 400 synthetic Knapsack Problem instances and compared against two fundamental heuristics: MAXPW and MINW. Results indicate that while our approach demonstrates some adaptability and generates competitive solutions, it keeps plenty of opportunities for improvement.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Heuristic-Based Optimization Using Elementary Cellular Automata: A Preliminary Study on the Knapsack Problem

  • José Eduardo Zárate-Aranda,
  • José C. Ortiz-Bayliss

摘要

This study introduces two heuristic-based solvers inspired by Wolfram’s Elementary Cellular Automaton. The solvers use the automaton rules to solve combinatorial optimization problems using two relatively different strategies. The first solver uses the rules to combine solutions produced by individual heuristics. In contrast, the second uses the rules to combine heuristics and later uses such heuristics to solve the problem. As we can observe, the second solver addresses the solving process indirectly. These solvers were tested on 400 synthetic Knapsack Problem instances and compared against two fundamental heuristics: MAXPW and MINW. Results indicate that while our approach demonstrates some adaptability and generates competitive solutions, it keeps plenty of opportunities for improvement.