Visual interaction to solving complex optimization problems

Abstract

Many real world problems can be described as complex optimization problems. Some of them can be easily formalized and are amenable to an automated solution using some (usually heuristic) optimization algorithm. Other complex problems can not be solved satisfactory by automated algorithms. The reason is that the problems and the corresponding optimization goals can either not be fully formalized or that they vary depending on the user and the task at hand. In both cases, there is no chance to obtain a fully automatic solution of the problem. The only possibility is to make the user an integral part of the process. In this article, we therefore propose an interactive optimization system based on visualization techniques to guide the optimization process of heuristic optimization algorithms. To show the usefulness of our ideas, we provide two example applications: First, we apply the idea in the framework of similarity search in multimedia databases. Since it is difficult to specify the search task, we use visualization techniques to allow an interactive specification. As basis for the automated optimization we use a genetic algorithm. Instead of having an a-priori fully-specified fitness function, however, we let the user interactively determine the fitness of intermediate results based on visualizations of the data. In this way, an optimization with user-dependent and changing optimization goals is possible. The second example is a typical complex optimization problem - the time tabling problem. In most instantiations of the problem, it is not possible to completely specify all constraints, especially the potentially very large number of dependencies and soft constraints. In this application example, we also use visualization techniques in combination with automated optimization to improve the obtained solutions.