Schemata Bandits for Binary Encoded Combinatorial Optimisation Problems

摘要

We introduce the schemata bandits algorithm to solve binary combinatorial optimisation problems, like the trap functions and NK landscape, where potential solutions are represented as bit strings. Schemata bandits are influenced by two different areas in machine learning, evolutionary computation and multi-armed bandits. The schemata from the schema theorem for genetic algorithms are structured as hierarchical multi-armed bandits in order to focus the optimisation in promising areas of the search space. The proposed algorithm is not a standard genetic algorithm because there are no genetic operators involved. The schemata bandits are non standard schemata nets because one node can contain one or more schemata and the value of a node is computed using information from the schemata contained in that node. We show the efficiency of the designed algorithms for two binary encoded combinatorial optimisation problems.