Christoph Breitschopf: Incremental Optimization with Software Agents, Doctoral thesis, Department of Business Informatics - Software Engineering, Johannes Kepler University Linz, September 2005.
The field of combinatorial optimization has an impressive impact on the efficiency of organizations. Optimization techniques can help increasing productivity, reducing costs and eliminating unintentional redundancies in all kinds of industries. In the recent decades, different types of optimization techniques have been developed. Meta-heuristics have emerged as an effective paradigm for solving large-scale combinatorial optimization problems, as they deliver feasible solutions within reasonable time. These techniques exhibit some generic aspects, but specific implementations must nevertheless be provided for each problem. The development of such algorithms can be time-consuming and often results in code with little or no reuse. For practical use, a general optimization technique is needed in order to develop solvers for real-world problems with as little effort as possible. This thesis introduces an agent-based optimization framework that is able to solve different types of combinatorial optimization problems by coordinating agents that work on a common goal. The framework is independent of the actual problem, supports rapid development of problem-specific solvers, and encapsulates invariant parts from problem-specific ones. It enables the use of different optimization paradigms as well as the combination of existing techniques. The interAgents framework controls the optimization process and enables the user to concentrate on the actual problem without caring about administrative issues. The effort for adapting the framework to new problem classes is rather small as the user has to implement only those features he really needs. The framework has been implemented in C++ with emphasis on portability. This thesis also represents an experience report, as during the development of the framework several ideas came up which had to be discarded later on. It contains hints why an implementation has been done in the documented way as well as how the framework can be adapted effectively to new problem classes. The performance of the interAgents framework is demonstrated by solving two well-known academic problems, the Knapsack Problem and the Traveling Salesman Problem. The framework has been developed in the context of a project accomplished in cooperation with Siemens AG, Corporate Technology, Munich, Germany. Hence, its practical applicability has also successfully been verified with two real-world problems defined by the project partner. The results achieved suggest that the interAgents approach is a promising alternative to existing approaches for dealing with different hard combinatorial optimization problems, offering efficiency and saving development time.