Heuristic Search Strategies for Solving Combinatorial Optimization Problems

다국어 초록 (Multilingual Abstract)

In combinatorial optimization problems, there is a discrete set of alternative solution values from which a maximum or minimum value is sought. Applications occur in many areas of computer science. as well as such diverse fields as engineering and operations research. Commonly occurring models involve routing and scheduling, allocation, assignments of tasks and agents, and transshipment patterns. It is typically the case that algorithms that yield a guaranteed optimal solution to a combinatorial optimization problem require CPU time that is an exponential function of a problem size measure. Thus, at least for problems of realistic size, it is common to apply an algorithms that runs in polynomial time and yields a solution which is not guaranteed to be optimal, but yields acceptable results. Such algorithms are known as heuristic search algorithms or approximation algorithms
In recent years, artificial intelligent methods such as neural network, genetic algorithms, tabu search and rule-based search have emerged as major heuristic strategies for solving combinatorial optimization problems. This paper presents overviews and establises of these methods. The methods are viewed as metastrategies, in the sense that they impart properties of intelligent control to search processes. From an artificial intelligence view, the strategies are symbolic methods that at least partially
capture two major characteristics of human intelligence : learning and adaptation. The methods operate from a hig level of abstraction that can be applied to entire categories of problems.