0000000000132209
AUTHOR
Johannes J. Schneider
Influence of rounding errors on the quality of heuristic optimization algorithms
Abstract Search space smoothing and related heuristic optimization algorithms provide an alternative approach to simulated annealing and its variants: while simulated annealing traverses barriers in the energy landscape at finite temperatures, search space smoothing intends to remove these barriers, so that a greedy algorithm is sufficient to find the global minimum. Several formulas for smoothing the energy landscape have already been applied, one of them making use of the finite numerical precision on a computer. In this paper, we thoroughly investigate the effect of finite numerical accuracy on the quality of results achieved with heuristic optimization algorithms. We present computation…
THE INFLUENCE OF CONTRARIANS AND OPPORTUNISTS ON THE STABILITY OF A DEMOCRACY IN THE SZNAJD MODEL
Sznajd-Weron and Sznajd introduced a model investigating the democratic development in a closed community. This model is based on the USDF-principle ("united we stand, divided we fall"). However, it faces the problem that the system tends either to a dictatorship (i.e., 100% pro or 100% contra) or to a stalemate state (i.e., exactly 50% pro, 50% contra). Based on their model, I will show that a democratic system keeps alive due to the existence of both opportunists and persons in opposition.
Statistical analysis of financial returns for a multiagent order book model of asset trading
We recently introduced a realistic order book model [T. Preis, Europhys. Lett. 75, 510 (2006)] which is able to generate the stylized facts of financial markets. We analyze this model in detail, explain the consequences of the use of different groups of traders, and focus on the foundation of a nontrivial Hurst exponent based on the introduction of a market trend. Our order book model supports the theoretical argument that a nontrivial Hurst exponent implies not necessarily long-term correlations. A coupling of the order placement depth to the market trend can produce fat tails, which can be described by a truncated Lévy distribution.
Investigation of acceptance simulated annealing — A simplified approach to adaptive cooling schedules
Abstract Simulated annealing is the classic physical optimization algorithm, which has been applied to a large variety of problems for many years. Over time, several adaptive mechanisms for decreasing the temperature and thus controlling the acceptance of deteriorations have been developed, based on the measurement of the mean value and the variance of the energy. Here we propose a new simplified approach in which we consider the probability of accepting deteriorations as the main control parameter and derive the temperature by averaging over the last few deteriorations stored in a memory. We present results for the traveling salesman problem and demonstrate, how the amount of data retained…
Accelerated fluctuation analysis by graphic cards and complex pattern formation in financial markets
The compute unified device architecture is an almost conventional programming approach for managing computations on a graphics processing unit (GPU) as a data-parallel computing device. With a maximum number of 240 cores in combination with a high memory bandwidth, a recent GPU offers resources for computational physics. We apply this technology to methods of fluctuation analysis, which includes determination of the scaling behavior of a stochastic process and the equilibrium autocorrelation function. Additionally, the recently introduced pattern formation conformity (Preis T et al 2008 Europhys. Lett. 82 68005), which quantifies pattern-based complex short-time correlations of a time serie…
THE IMPACT OF ELECTION RESULTS ON THE MEMBER NUMBERS OF THE LARGE PARTIES IN BAVARIA AND GERMANY
In this paper, we investigate the relations between the numbers of members of various parties and their results in the elections in Bavaria and in Germany. Deriving from the finding that there is a strong time-delayed correlation between these data-sets for the two largest parties in Bavaria, we show in a simulation based on the Sznajd model that such a correlation leads to very stable majorities, just as in Bavaria.
On the problem of finding a suitable distribution of students to universities in Germany
For many years, the problem of how to distribute students to the various universities in Germany according to the preferences of the students has remained unsolved. Various approaches, like the centralized method to let a central agency organize the distribution to the various universities or the decentralized method to let the students apply directly at their preferred universities, turned out to lead to a significant fraction of frustrated students ending up at universities not being on their preference list or even not having a place to study at all. With our centralized approach, we are able to decrease the fraction of frustrated students as well as the bureaucratic expenses for applica…
Investigation of Simulated Trading — A multi agent based trading system for optimization purposes
Abstract Some years ago, Bachem, Hochstattler, and Malich proposed a heuristic algorithm called Simulated Trading for the optimization of vehicle routing problems. Computational agents place buy-orders and sell-orders for customers to be handled at a virtual financial market, the prices of the orders depending on the costs of inserting the customer in the tour or for his removal. According to a proposed rule set, the financial market creates a buy-and-sell graph for the various orders in the order book, intending to optimize the overall system. Here I present a thorough investigation for the application of this algorithm to the traveling salesman problem.
The democracy–ochlocracy–dictatorship transition in the Sznajd model and in the Ising model
Abstract Since its introduction in 2000, the Sznajd model has been assumed to simulate a democratic community with two parties. The main flaw in this model is that a Sznajd system freezes in the long term in a non-democratic state, which can be either a dictatorship or a stalemate configuration. Here we show that the Sznajd model has better to be considered as a transition model, transferring a democratic system already at the beginning of a simulation via an ochlocratic scenario, i.e., a regime in which several mobs rule, to a dictatorship, thus reproducing the corresponding Aristotelian theory.
Selfish vs. Unselfish Optimization of Network Creation
We investigate several variants of a network creation model: a group of agents builds up a network between them while trying to keep the costs of this network small. The cost function consists of two addends, namely (i) a constant amount for each edge an agent buys and (ii) the minimum number of hops it takes sending messages to other agents. Despite the simplicity of this model, various complex network structures emerge depending on the weight between the two addends of the cost function and on the selfish or unselfish behaviour of the agents.
Ultrametricity property of energy landscapes of multidisperse packing problems
We consider the problem of finding the densest closed packing of hard disks with proposed different radii in a circular environment, such that the radius of the circumcircle is minimal. The subspace of the quasioptimum configurations of this problem exhibits the property of ultrametricity.
SCALING LAWS FOR THE LIFETIMES OF GOVERNMENTS IN THE SZNAJD DEMOCRACY
We investigate the lifetimes of governments in the original and a randomized one-dimensional Sznajd model. We find various scaling laws for the lifetime of the democracy and for the reigning time of governments in this model, depending on the system size N.
TWO-LANE TRAFFIC WITH PLACES OF OBSTRUCTION TO TRAFFIC
As the Nagel–Schreckenberg model (NaSch model) became known as a realistic approach to describe traffic flow on single-lane streets, this model was extended to two-lane traffic by several groups. On the base of our two-lane model, we will now investigate the impact of a place of obstruction, e.g., because of road works, on partial fractions, densities and mean velocities.
HOW SMART DOES AN AGENT NEED TO BE?
The classic distributed computation is done by atoms, molecules or spins in vast numbers, each equipped with nothing more than the knowledge of their immediate neighborhood and the rules of statistical mechanics. These agents, 1023 or more, are able to form liquids and solids from gases, realize extremely complex ordered states, such as liquid crystals, and even decode encrypted messages. We will describe a study done for a sensor-array "challenge problem" in which we have based our approach on old-fashioned simulated annealing to accomplish target acquisition and tracking under the rules of statistical mechanics. We believe the many additional constraints that occur in the real problem ca…
How fair is an equitable distribution?
Envy is a rather complex and irrational emotion. In general, it is very difficult to obtain a measure of this feeling, but in an economical context envy becomes an observable which can be measured. When various individuals compare their possessions, envy arises due to the inequality of their different allocations of commodities and different preferences. In this paper we show that an equitable distribution of goods does not guarantee a state of fairness between agents and in general that envy cannot be controlled by tuning the distribution of goods.
Multi-agent-based Order Book Model of financial markets
We introduce a simple model for simulating financial markets, based on an order book, in which several agents trade one asset at a virtual exchange continuously. For a stationary market the structure of the model, the order flow rates of the different kinds of order types and the used price time priority matching algorithm produce only a diffusive price behavior. We show that a market trend, i.e. an asymmetric order flow of any type, leads to a non-trivial Hurst exponent for the price development, but not to "fat-tailed" return distributions. When one additionally couples the order entry depth to the prevailing trend, also the stylized empirical fact of "fat tails" can be reproduced by our …
Fluctuation patterns in high-frequency financial asset returns
We introduce a new method for quantifying pattern-based complex short-time correlations of a time series. Our correlation measure is 1 for a perfectly correlated and 0 for a random walk time series. When we apply this method to high-frequency time series data of the German DAX future, we find clear correlations on short time scales. In order to subtract trivial autocorrelation parts from the pattern conformity, we introduce a simple model for reproducing the antipersistent regime and use alternatively level 1 quotes. When we remove the pattern conformity of this stochastic process from the original data, remaining pattern-based correlations can be observed.
GPU accelerated Monte Carlo simulation of the 2D and 3D Ising model
The compute unified device architecture (CUDA) is a programming approach for performing scientific calculations on a graphics processing unit (GPU) as a data-parallel computing device. The programming interface allows to implement algorithms using extensions to standard C language. With continuously increased number of cores in combination with a high memory bandwidth, a recent GPU offers incredible resources for general purpose computing. First, we apply this new technology to Monte Carlo simulations of the two dimensional ferromagnetic square lattice Ising model. By implementing a variant of the checkerboard algorithm, results are obtained up to 60 times faster on the GPU than on a curren…
INVESTIGATION OF ELECTION RESULTS, NUMBERS OF PARTY MEMBERS, AND OPINION POLLS IN GERMANY
Our publication focuses on two different but related topics in politics: in the first part of this publication, we investigate the influence of election results in the elections for the parliaments of the German states and for the German Diet (federal parliament) on the member numbers of the largest parties in the various states. In the second part of this publication, we consider the correlations between opinion polls and election results and focus on the question whether real election results can be predicted by opinion polls.
Packing a multidisperse system of hard disks in a circular environment.
We consider the problem of finding the densest closed packing of hard disks with proposed different radii in a circular environment, such that the radius of the circumcircle is minimal. With our approach, we are able to find denser packings for various problem instances than known from the literature. Both for the dynamics of the simulation and for the optimum values of the radii of the circumcircles, we find various scaling laws.