您现在的位置:首页 > >

Visualization of Evolutionary Algorithms Real-World Application of Standard Techniques and

发布时间:

Visualization of Evolutionary Algorithms: Real-World Application of Standard Techniques and Multidimensional Visualization
DaimlerChrysler AG, Research and Technology Alt-Moabit 96a, 10559 Berlin, Germany pohlheim@dbag.bln.daimlerbenz.com

Hartmut Pohlheim

1 INTRODUCTION
Evolutionary algorithms work in an algorithmically simple manner. When put to work they produce a vast amount of data. Apart from simple convergence information it is a non-trivial task to extract useful information from those data to provide insight into the state and progress of the evolutionary algorithm. In this presentation we outline a set of standard visualization techniques for di erent data types. These data types and techniques give an instant visual impression of the evolutionary algorithm's progress and the actual state of the population. Hopefully, the proposed set will open up a discussion about necessary and useful visualization techniques between users of evolutionary algorithms. Beside the standard set, an advanced technique for visualizing high-dimensional data is outlined - multidimensional scaling. This techniques can, for instance, be applied to the visualization of the \path through the search space" of the best individuals during an optimization run, and the comparison of multiple runs regarding the variables of individuals and multi criteria objective values (\path through solution space"). The above topics are presented in detail in 4]. In this presentation we only give a short overview of the main ideas of both topics. All methods were selected according to their usefulness for real world applications. We employed these visualization techniques in the course of solving real world problems using evolutionary algorithms and for the analysis of optimization runs. Examples will be shown during the presentation.

2 SET OF STANDARD VISUALIZATION TECHNIQUES
A number of data types and techniques useful for visualizing the state of the population and the progress of

the evolutionary algorithm are proposed. These techniques are simple to calculate and easy to display using standard visualization tools. This set of techniques provides a baseline for understanding the evolutionary process. An overview of the di erent data types and time frames useful for the visualization of evolutionary algorithms is given in Figure 1. The techniques are systematized into categories depending on the time range represented by the data. The rst category encloses methods for visualizing data produced during many generations, thus presenting a picture of the progress or course of the evolutionary algorithm. The second category contains techniques to visualize data produced anew for every generation. These techniques give a picture of the current state of the population. The third category visualizes data of multiple runs, thus comparing di erent evolutionary algorithms. Using this classi cation for each data type proposed a number of techniques can be speci ed and implemented. See 4] for details and examples. For extended applications or special evolutionary algorithms new data types and techniques can be included into this framework (for instance, the advanced handling of multiple objective values (pareto front) or cluster tree analysis for termination). Because of the specialized application these techniques are not part of the standard set. The proposed standard set of visualization techniques is implemented in the Genetic and Evolutionary Algorithm Toolbox for Matlab - GEATbx 2]. A graphical user interface may be used to access all the di erent visualization methods and styles during and after (online and o -line) an optimization. The exibility offered by the user interface and the integration into the GEATbx gives the user a powerful tool, easy to use for the thorough examination and for the detailed documentation of various aspects of the optimization runs.

Figure 1: Data Types and Time Frames of Evolutionary Algorithms for Visualization.

3 MULTIDIMENSIONAL VISUALIZATION
Most of the commonly used techniques for visualization are limited to representing data depending on one or two variables. This is due to the human visual limitation to three dimensions. There are two possible extensions to go beyond this limitation: using color for the fourth dimension and time as the fth dimension. Neither possibility is very common and requires practice, especially if time is used for visualizing the fth dimension. However, if the problem incorporates more than ve dimensions a new method for visualizing arbitrarily high dimensions must be found. For the visualization of multidimensional data a method to transform multidimensional data to a lower dimension is needed, preferably to 2 or 3 dimensions. This transformation should provide a lower-dimensional picture where the dissimilarities between the data points of the multidimensional domain corresponds with the dissimilarities of the lowerdimensional domain. These transformation methods are referred to as multidimensional scaling ( 1], 5]). To measure the dissimilarity, the distance between pairs of data points is used. These distances can be genuine distances in the respective high-dimensional domain, for instance the Euclidean distance. One of the best known methods for multidimensional scaling is Sammon mapping 6]. Examples for the use of multi-dimensional scaling are: visualization of variables of (best) individuals of an optimization run (\path through search space"), visualization of non-dominated solutions in multiobjective optimization - multi criteria objective values (\path through solution space"). The resulting diagrams may produce clearer pictures than visualizing the data directly. Additionally, a com-

parison of the data of multiple optimization runs is possible, a task very di cult using only standard visualization techniques. Please see 4] for examples.

4 REAL-WORLD APPLICATION
During the last years we employed the proposed visualization techniques in the course of solving real world problems. Depending on the problem to solve and the open questions a few methods were selected. These methods supported the analysis of optimization runs. At the same time we could give a visual and compact documentation. Unexpected behaviour and special effects could be easier detected and explained using the graphical representation. Some examples for the employment of visualization techniques to real-world applications will be shown during the presentation.

5 CONCLUDING REMARKS
The proposed set of \standard" visualization techniques for evolutionary algorithms provides a baseline for understanding the evolutionary process. Combined with advanced techniques, powerful visualization tools to aid the designer and user of evolutionary algorithms can be constructed. Multidimensional scaling opens a eld for visualization not only applicable to the domain of evolutionary algorithms. The presented visualization techniques were applied in the course of solving real world problems using evolutionary algorithms. Thus, these techniques are not just proposed, but have been used and proved informative (see 3]). An example implementation of all these and additional techniques can be found in 2].

References
1] T.F. Cox and M.A.A. Cox. Multidimensional Scaling. London: Chapman & Hall, 1994. 2] H. Pohlheim. Genetic and Evolutionary Algorithm Toolbox for Matlab. http://www.geatbx.com/, 19941999. 3] H. Pohlheim. Entwicklung und systemtechnische Anwendung Evolutionarer Algorithmen. Aachen, Germany: Shaker Verlag, 1998. (Development and Engineering Application of Evolutionary Algorithms. in German) 4] H. Pohlheim. Visualization of Evolutionary Algorithms - set of standard techniques and multidimensional visualization. In W. Banzhaf, editor, The Proceedings of the 1999 Genetic and Evolutionary Computation Conference (GECCO'99), San Francisco, CA: Morgan Kaufmann, 1999. 5] B.D. Ripley. Pattern Recognition and Neural Networks. Cambridge, GB: Cambridge University Press, 1996. 6] J. Sammon Jnr. A Nonlinear Mapping for Data Structure Analysis. IEEE Transactions on Computers, vol. C-18, no. 5, pages 401-409, 1969.



热文推荐
猜你喜欢
友情链接: 团党工作范文 工作范文 表格模版 社科文档网 营销文档资料 工程文档大全