Gintautas Dzemyda Institute of Mathematics and Informatics Akademijos St. 4, 2600 Vilnius, Lithuania
[email protected] Abstract The results presented in this paper make up the basis for a new way of analyzing extremal problems. A new phenomenon that characterizes an extremal problem has been discovered. The paper tries to reveal fields of application of this phenomenon. The method of animated visual analysis, based on the knowledge discovery in the set of observations of the objective function of the problem interactively, has been developed. The aim of analysis is to find a direction in the definition domain such that maximizes the mean absolute difference between two values of the objective function calculated at randomly selected points in this direction, or (and) maximizes the mean absolute difference per distance unit of the objective function values calculated at two randomly selected points in this direction. The presented approach requires generating many data sets. Sometimes such a generation is very computation-expensive. Therefore, the ideas discussed in this paper may be applied in the case where the investigator wants not only to solve the extremal problem, but also to discover additional knowledge of it. Keywords: Optimization, visual analysis, animation, data analysis, knowledge discovery 1. Introduction Complex problems of computer-aided design and control arise with a rapid development of modern technologies. The search for optimal solutions acquires here an essential significance. Investigations in this area are pursued in two directions: development of new optimization methods as well as software that would embrace various realizations of the methods developed. The key aim is solution of any arising problem as soon as possible and with the least efforts. When selecting a proper strategy of optimization, the knowledge of the extremal problem (the objective function, variables, and constraints) is of utmost importance. On the basis of the knowledge we choose a concrete method(or methods) for optimization. Most frequently, however, minimal knowledge of the problem to be optimized is used, i.e. as much as it is necessary for solving the problem (not necessarily in the most efficient way). With the view of improving the optimization efficiency, it is expedient to develop special methods and strategies for knowledge discovery about the optimization problem. Knowledge discovery is the non-trivial extraction of implicit, previously unknown,and potentially useful information from data (see [1,2]). The term of knowledge discovery was introduced in [1] referring to the analysis of databases.The concept of knowledge discovery is extended to the analysis of information structures in [3]. By information structure we mean here a set of data (and knowledge, in certain cases) linked up in a certain way, the analysis of which can give us some new knowledge on an optimization problem and can help to solve the problem. The information structure may also cover other structures, simpler ones. The main tasks in recent research are the search for information structures and their analysis strategies aimed at increasing the optimization efficiency and development of software that assists in the knowledge discovery. Visualization is a powerful means to support optimization modeling, solution, and analysis. It uses interactive computer graphics to provide the insight of complicated extremal problems, models or systems. A broad survey on the use of visualization in optimization is given in [4]. Contrary to the static graphics,animation gives the illusion of motion. It can also help algorithm designers to understand the behavior of their algorithms, modelers their models, and decision makers their problems. The author in [4] touches the role of animation in the process of optimization, too. Two ways of application of the animation are reviewed in [4]: algorithm animation, i.e. demonstration of the behavior of execution of an algorithm (
