Multi-heuristic and game approaches in search problems of the graph theory

Abstract

We consider in this paper the adaptation of heuristics used for programming non-deterministic games to the problems of discrete optimization, in particular, some heuristic methods of decision-making in various discrete optimization problems. The object of each of these problems is programming anytime algorithms. Among the problems solved in this paper, there are the classical traveling salesman problem and some connected problems of minimization for nondeterministic finite automata. Considered methods for solving these problems are constructed on the basis of special combination of some heuristics, which belong to some different areas of the theory of artificial intelligence. More precisely, we shall use some modifications of unfinished branch-and-bound method; for the selecting immediate step using some heuristics, we apply dynamic risk functions; simultaneously for the selection of coefficients of the averaging-out, we also use genetic algorithms; and the reductive self-learning by the same genetic methods is also used for the start of unfinished branch-and-bound method again. This combination of heuristics represents a special approach to construction of anytime-algorithms for the discrete optimization problems. This approach can be considered as an alternative to application of methods of linear programming, and to methods of multi-agent optimization, and also to neural networks.