Only a few mathematically proven bounds on the runtime behavior of Ant Colony Optimization (ACO) have been reported. To alleviate this situation, we investigate the ACO variant we call Bivalent ACO ( BACO ) that uses exactly two pheromone values. We provide and successfully apply a Markov chain-based approach to calculate the expected optimization time, i.e., the expected number of iterations until an adjustable quality \(\kappa\) of the solution is reached and the algorithm terminates. This approach allows to derive exact formulas for the expected optimization time and its variance for the problems Sorting and LeadingOnes . It turns out that the ratio of the two pheromone values significantly governs the runtime behavior of BACO . We present tight bounds \(\Theta(\kappa\cdot n^{2})\) for Sorting with a specifically chosen objective function and \(\Theta(\kappa\cdot n)\) for LeadingOnes . We show that, despite having a drastically simplified ant algorithm with respect to the influence of the pheromones on the solving process, the known bound on the expected optimization time for the problem LeadingOnes ( \(\mathcal{O}(n^{2})\) ) can be re-produced. Experiments validate our theoretical findings.

So far, only few bounds on the runtime behavior of Ant Colony Optimization (ACO) have been reported. To alleviate this situation, we investigate the ACO variant we call Bivalent ACO (BACO) that uses exactly two pheromone values. We provide and successfully apply a new Markov chain-based approach to calculate the expected optimization time, i. e., the expected number of iterations until the algorithm terminates. This approach allows to derive exact formulæ for the expected optimization time for the problems Sorting and LeadingOnes. It turns out that the ratio of the two pheromone values significantly governs the runtime behavior of BACO. To the best of our knowledge, for the first time, we can present tight bounds for Sorting (Θ(n3)) with a specifically chosen objective function and prove the missing lower bound Ω(n2) for LeadingOnes which, thus, is tightly bounded by Θ(n2). We show that despite we have a drastically simplified ant algorithm with respect to the influence of the pheromones on the solving process, known bounds on the expected optimization time for the problems OneMax (O(n log n)) and LeadingOnes (O(n2)) can be re-produced as a by-product of our approach. Experiments validate our theoretical findings.

Abstract Meta-heuristics are powerful tools for solving optimization problems whose structural properties are unknown or cannot be exploited algorithmically. We propose such a meta-heuristic for a large class of optimization problems over discrete domains based on the particle swarm optimization (PSO) paradigm. We provide a comprehensive formal analysis of the performance of this algorithm on certain “easy” reference problems in a black-box setting, namely the sorting problem and the problem OneMax. In our analysis we use a Markov model of the proposed algorithm to obtain upper and lower bounds on its expected optimization time. Our bounds are essentially tight with respect to the Markov model. We show that for a suitable choice of algorithm parameters the expected optimization time is comparable to that of known algorithms and, furthermore, for other parameter regimes, the algorithm behaves less greedy and more explorative, which can be desirable in practice in order to escape local optima. Our analysis provides a precise insight on the tradeoff between optimization time and exploration. To obtain our results we introduce the notion of indistinguishability of states of a Markov chain and provide bounds on the solution of a recurrence equation with non-constant coefficients by integration.

We present the analysis of a discrete particle swarm optimization (PSO) algorithm that works on a significantly large class of discrete optimization problems. Assuming a black-box setting, we prove upper and lower bounds on the expected number of function evaluations required by the proposed algorithm to solve the sorting problem and the problem of maximizing the number of ones in a bitstring, i.e., the function OneMax. We show that depending on the probability of moving towards the attractor, the expected optimization time may be polynomial or exponential. The cornerstone of our analysis are Theta-bounds on the expected time it takes until the PSO returns to the attractor. We obtain these bounds by solving linear recurrence equations with constant and non-constant coefficients. We also introduce a useful indistinguishability property of states of a Markov chain in order to obtain lower bounds on the expected optimization time of our proposed PSO algorithm.

Imaging techniques are an excellent example for the continuous improvement of medical possibilities by technical innovation. One particularly relevant field of research is multimodal registration, where data sets must be aligned in order to make their structures overlay. The overlay of the image positions is reached by optimizing a similarity metric. A commonly used measure applied in this process is the normalized mutual information, which also will be used in this paper. Due to iteratively improving this function value, a transformation can be determined, which adapts the data in order to make the images overlap each other as accurately as possible. For this improvement process, different mathematical optimization methods are in use. One approach is Particle Swarm Optimization (PSO), a nature-inspired optimization technique. In the present work, four variants of the PSO algorithm are presented and applied to medical image data. Although classical PSO with standard parameters is shown to have some limitations, considerable improvement can be obtained by the modification of the calculation rules, the choice of the parameter values and the choice of the objective function. Our experimental results illustrate the substantial potential of PSO for this type of application.

Particle swarm optimization (PSO) is a popular nature-inspired meta-heuristic for solving continuous optimization problems. Although this technique is widely used, up to now only some partial aspects of the method have been formally investigated. In particular, while it is well-studied how to let the swarm converge to a single point in the search space, no general theoretical statements about this point or on the best position any particle has found have been known. For a very general class of objective functions, we provide for the first time results about the quality of the solution found. We show that a slightly adapted PSO almost surely finds a local optimum by investigating the newly defined potential of the swarm. The potential drops when the swarm approaches the point of convergence, but increases if the swarm remains close to a point that is not a local optimum, meaning that the swarm charges potential and continues its movement.

Particle swarm optimization (PSO) is a nature-inspired technique for solving continuous optimization problems. For a fixed optimization problem, the quality of the found solution depends significantly on the choice of the algorithmic PSO parameters such as the inertia weight and the acceleration coefficients. It is a challenging task to choose appropriate values for these parameters by hand or mathematically. In this paper, a novel self-optimizing particle swarm optimizer with multiple adaptation layers is introduced. In the new algorithm, adaptation takes place on both particle and subswarm level. The new idea of using virtual parameter swarms which hold modifiable parameter configurations each is introduced. The algorithmic PSO parameters can be mutated by using, for instance, well-known techniques from the field of evolutionary algorithms, in order to allow fine-granular parameter adaptation to the problem at hand. The new algorithm is experimentally evaluated, and compared to a standard PSO and the Tribes algorithm. The experimental study shows that our new algorithm is highly competitive to previously suggested approaches.

The interaction among particles is a vital aspect of Particle Swarm Optimization. As such, it has a strong influence on the swarm's success. In this study various approaches regarding the particles' communication behavior and their relationship are examined, as well as possibilities to combine the approaches. A new variant of the popular FIPS algorithm, the so-called Ranked FIPS, is introduced, which resolves specific shortcomings of the traditional FIPS. As all tested PSO variants feature distinct strengths and weaknesses, a new adaptive strategy is proposed which operates on dissimiliarly configured subswarms. The exchange between these subswarms is solely based on particle migration. The combination of the Ranked FIPS and other strategies within the so called Particle Swarm Optimizer with Migration achieves a very good, yet remarkably reliable performance over a wide range of recognized benchmark problems.

When applying particle swarm optimization (PSO) to real world optimization problems, often boundary constraints have to be taken into account. In this paper, we show that the bound handling mechanism essentially influences the swarm behavior, especially in high-dimensional search spaces. In our theoretical analysis, we prove that all particles are initialized very close to the boundary with overwhelming probability, and that the global guide is expected to leave the search space in every forth dimension. Afterwards, we investigate the initialization process when optimizing the sphere function, a widely used benchmark, in more detail in order to provide a first step towards explaining previously observed phenomena. Moreover, we present a broad experimental study of commonly applied bound handling mechanisms on a variety of benchmark functions which is useful for choosing an appropriate strategy in real world applications. Finally, we derive some guidelines for the practical application of the PSO algorithm in high-dimensional bounded search spaces

We present a new data structure for rendering highly complex virtual environments of arbitrary topology. The special feature of our approach is that it allows an interactive navigation in very large scenes (30 GB/400 million polygons in our benchmark scenes) that cannot be stored in main memory, but only on a local or remote hard disk. Furthermore, it allows interactive rendering of substantially more complex scenes by instantiating objects.For the computation of an approximate image of the scene, a sampling technique is used. In the preprocessing, a so-called sample tree is built whose nodes contain randomly selected polygons from the scene. This tree only uses space that is linear in the number of polygons. In order to produce an image of the scene, the tree is traversed and polygons stored in the visited nodes are rendered. During the interactive walkthrough, parts of the sample tree are loaded from local or remote hard disk.We implemented our algorithm in a prototypical walkthrough system. Analysis and experiments show that the quality of our images is comparable to images computed by the conventional z-buffer algorithm regardless of the scene topology.

Sorting long sequences of keys is a problem that occurs in many different applications. For embedded systems, a uniprocessor software solution is often not applicable due to the low performance, while realizing multiprocessor sorting methods on parallel computers is much too expensive with respect to power consumption, physical weight, and cost. We investigate cost/performance tradeoffs for hybrid sorting algorithms that use a mixture of sequential merge sort and systolic insertion sort techniques. We propose a scalable architecture for integer sorting that consists of a uniprocessor and an FPGA-based parallel systolic co-processor. Speedups obtained analytically and experimentally and depending on hardware (cost) constraints are determined as a function of time constants of the uniprocessor and the co-processor.

We consider comparator networks M that are used repeatedly: while the output produced by M is not sorted, it is fed again into M . Sorting algorithms working in this way are called periodic . The number of parallel steps performed during a single run of M is called its period , the sorting time of M is the total number of parallel steps that are necessary to sort in the worst case. Periodic sorting networks have the advantage that they need little hardware (control logic, wiring, area) and that they are adaptive. We are interested in comparator networks of a constant period, due to their potential applications in hardware design. Previously, very little was known on such networks. The fastest solutions required time O(n ε ) where the depth was roughly 1/ε. We introduce a general method called periodification scheme that converts automatically an arbitrary sorting network that sorts n items in time T(n ) and that has layout area A(n ) into a sorting network that has period 5, sorts ***( n • T ( n ) items in time O(T( )• log n ), and has layout area O(A(n) ) • T(n )). In particular, applying this scheme to Batcher's algorithms, we get practical period 5 comparator networks that sort in time O (log 3 n ). For theoretical interest, one may use the AKS netork resulting in a period 5 comparator network with runtime O (log 2 n ).

We develop a general technique for the quantitative analysis of iterative distributed load balancing schemes. We illustrate the technique by studying two simple, intuitively appealing models that are prevalent in the literature: the diffusive paradigm, and periodic balancing circuits (or the dimension exchange paradigm). It is well known that such load balancing schemes can be roughly modeled by Markov chains, but also that this approximation can be quite inaccurate. Our main contribution is an effective way of characterizing the deviation between the actual loads and the distribution generated by a related Markov chain, in terms of a natural quantity which we call the local divergence. We apply this technique to obtain bounds on the number of rounds required to achieve coarse balancing in general networks, cycles and meshes in these models. For balancing circuits, we also present bounds for the stronger requirement of perfect balancing, or counting.

Article Optimal trade-offs between size and slowdown for universal parallel networks Share on Authors: Friedhelm Meyer auf der Heide Dept. of Mathematics and Computer Science and Heinz Nixdorf Institute, University of Paderborn, D-33095 Paderborn, Germany Dept. of Mathematics and Computer Science and Heinz Nixdorf Institute, University of Paderborn, D-33095 Paderborn, GermanyView Profile , Martin Storch Dept. of Mathematics and Computer Science and Heinz Nixdorf Institute, University of Paderborn, D-33095 Paderborn, Germany Dept. of Mathematics and Computer Science and Heinz Nixdorf Institute, University of Paderborn, D-33095 Paderborn, GermanyView Profile , Rolf Wanka Dept. of Mathematics and Computer Science and Heinz Nixdorf Institute, University of Paderborn, D-33095 Paderborn, Germany Dept. of Mathematics and Computer Science and Heinz Nixdorf Institute, University of Paderborn, D-33095 Paderborn, GermanyView Profile Authors Info & Claims SPAA '95: Proceedings of the seventh annual ACM symposium on Parallel algorithms and architecturesJuly 1995 Pages 119–128https://doi.org/10.1145/215399.215430Online:20 July 1995Publication History 1citation174DownloadsMetricsTotal Citations1Total Downloads174Last 12 Months3Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

A periodic comparator network has depth (or period) k, if for every t>k, the compare-exchange operations performed at step t are executed between exactly the same registers as at step t-k. We introduce a general method that converts an arbitrary comparator network that sorts n items in time T(n) and that has layout area A into a periodic sorting network of depth 5 that sorts /spl Theta/(n/spl middot/T(n)) items in time O(T(n)/spl middot/log n) and has layout area O(A/spl middot/T(n)). This scheme applied to the AKS network yields a depth 5 periodic comparator network that sorts in time O(log/sup 2/ n). More practical networks with runtime O(log/sup 3/ n) can be obtained from Batcher's networks. Developing the techniques for the main result, we improve some previous results: Let us fix a d/spl isin/N. Then we can construct a network of depth 3 based on a d-dimensional mesh sorting n items in time O(n/sup 1/d//spl middot/log/sup O(d/) n).>