Abstract: An important for the scientific as well as the industrial world is the field of combinatorial optimization. These problems arise in many areas of computer science and other disciplines in which computational methods are applied, such as artificial intelligence, operation research, bioinformatics and electronic commerce. Many of combinatorial optimization problems are NP-hard and in this field heuristics often are the only way to solve the problem efficiently, despite the fact that the heuristics represent a class of methods for which in general there is no formal theoretical justification of their performance. A lot of heuristic methods possessing different qualities and characteristics for combinatorial optimization problems were introduced. One of the approaches to the description and analysis of these methods is classification. In the paper a number of different characteristics for which it is possible to classify the heuristics for solving combinatorial optimization problems are proposed. The suggested classification is an extension of the previous work in the area. This work generalizes existing approaches to the heuristics’ classification and provides formal definitions for the algorithms’ characteristics on which the classes are based. The classification describes heuristic methods from different viewpoints. Among main considered aspects is decision making approach, structure complexity, solution spaces utilized, memory presence, trajectory-continuity, search landscape modification, and adaptation presence.

Keywords: combinatorial optimization, classification of methods, heuristics, metaheuristics.

ACM Classification Keywords: G.1.6 Numerical Analysis Optimization, I.2.8 Artificial Intelligence: Problem Solving, Control Methods, and Search – Heuristic methods, General Terms: Algorithms.

Link:

CLASSIFICATION OF HEURISTIC METHODS IN COMBINATORIAL OPTIMIZATION

Sergii Sirenko

http://foibg.com/ijita/vol16/IJITA16-4-p01.pdf