Dynamic problems (environments) will be defined in this project as the ones in which either a structure of the problem or its parameterization are changing with time. This instability of problem definition requires a certain degree of self-adaptation of the solving method in response to changes in the problem’s definition. Despite their frequent occurrence, dynamic problems are, in general, hard to tackle and there is a shortage of suitable methods for solving them.

The focus of proposed research is on simulation-based metaheuristics, which are currently widely applied to solving (static instances of) optimization problems. In particular the Ant Systems (AS), Particle Swarm Optimization (PSO) and the Upper Confidence Bounds Applied to Trees (UCT) optimization methods will be thoroughly analyzed in the initial stage of the project with respect to their applicability to the problems (environments) varying over time. In effect, the above-mentioned methods will be deeply modified so as to be able to efficiently handle dynamic aspects of a problem being solved. It is worth underlining that proposed adaptations will be problem-independent and autonomous. Hence, the new methods will be widely applicable and their usage will not require human intervention of any kind.

The methods will be tested on two types of problems: a collection of Dynamic Capacitated Vehicle Routing Problems (DCVRP) and the so-called General Game Playing (GGP) problem. The former ones are well-known examples of dynamic problems having practical relevance. DCVRP are generally hard to approach due to varying value of the target (cost) function (being a consequence of changes in demands) and/or modifications to the problem’s structure (due to adding new customers or deleting some of the existing ones along with cancelling their orders). One of the particularly interesting aspects of DCVRP is the problem of traffic jams, whose occurrence usually forces adequate adaptation of the currently best solution, as well as, online re-structuring of the problem-related knowledge possessed by the solving system in a way that complies to the new road conditions.

The other interesting and challenging application domain for adaptive metaheuristics considered in this research – the GGP – consists in building universal artificial agents capable of playing any game within a certain genre (multiplayer, perfect-information, synchronous, deterministic games), on the assumption that only the rules of the game to be played, specified in the logic-based Game Description Language (GDL), are provided at runtime. In order to perform well GGP agents must employ various AI techniques related to knowledge representation, learning, reasoning and decision-making in an integrated manner. Due to the variety of possible games (including both the well-known ones, e.g. chess, checkers or tic-tac-toe, and completely unknown games defined ad-hoc for the purpose of the GGP contests) the metaheuristic approach implemented by an agent must be universal and flexible on the one hand, but at the same time capable of recognizing and utilizing game-specific aspects and details.