Spectral and eigenfunction properties of a model based in random networks

Published in 24 Thursday

Track

Theory

Based in the Erdos-Renyi [1] model for random networks, we construct a model that describes systems in the transition from regular to chaotic dynamics analyzed in the Random Matrix Theory context [2].We study statistical properties for spectral and eigenfunction using extensive numerical simulations inwhich we nd universal properties for xed average degree E= aN(a and N being the average network connectivity and the network size, respectively). Finally, we demonstrate that the distribution for nearest-neightbor energy-level spacing is well describe by Brody distribution[3].

References

[1] P. Erdos and A. Renyi. The Evolution of Random Graphs.Publ. Math. Inst. Hung. Acad. Sci., 5: 17,1960.

[2] M. L. Metha. Random Matrices.Phys. Rep., 299: 189, 1998.

[3] T. A. Brody. A Statistical Measure for the Repulsion of Energy Levels.Lettere Al Nouvo Cimento, 7:482, 1973.

Read more...

Detecting funnel structures of continuous single-objective optimization problems by means of exploratory landscape analysis

Published in 24 Thursday

Track

Theory

In single-objective optimization, the performance of an optimization algorithm strongly relies on the structure and characteristics of the optimization problem at hand. The knowledge of its structure allows to choose between algorithms, which aim at exploring the entire search space, and algorithms that focus on exploiting the function’s global structure. The latter is advisable, if the underlying structure represents a so-called funnel, i.e. a function whose local optima lead towards the global optimum as exemplarily shown in the second panel of Figure 1. In recent years, the concept of Exploratory Landscape Analysis has evolved [1, 2, 3]. It automatically identifies problem characteristics based on a moderately small initial sample of the objective function. Furthermore, in combination with efficient machine learning techniques,it has proven to be a very effective approach for algorithm selection problems in continuous black-box optimization.

In this work, specific features for detecting funnel structures are introduced and then combined with already existing ones. The entire set is used for fitting different classification models on specifically generated multimodal test instances. All classifiers are binary, i.e. they classify whether the underlying structure of an optimization problem is a funnel or a random structure. The quality of those models is then validated on standard benchmark problems.The ability to detect, whether an unknown black-box optimization problem has the funnel property, can be considered as the first, necessary step for algorithm selection. Therefore, we suggest a two-stage approach when creating the algorithm selection model. First, the unknown optimization instance should be classified into funnel / random. In a second step, this binary feature will be included in the feature set and used for selecting the best optimization algorithm (out of a portfolio of algorithms) for that specific instance.

References

[1] B. Bischl, O. Mersmann, H. Trautmann, and M. Preuss. Algorithm selection based on exploratory landscape analysis and cost-sensitive learning.Proceedings of the 14th Annual Conference on Genetic and Evolutionary Computation (GECCO ’12), 313–320, 2012.

[2] P. Kerschke, M. Preuss, C. Hernández, O. Schütze, J. Sun, C. Grimme, G. Rudolph, B. Bischl, andH. Trautmann. Cell Mapping Techniques for Exploratory Landscape Analysis.EVOLVE – A Bridge between Probability, Set Oriented Numerics, and Evolutionary Computation V, 288:115–131, 2014.

[3] P. Kerschke, M. Preuss, S. Wessing, and H. Trautmann. Detecting Funnel Structures by Means of Exploratory Landscape Analysis.Proceedings of the 17th Annual Conference on Genetic and EvolutionaryComputation (GECCO ’15), 265–272, 2015.

Read more...
Subscribe to this RSS feed