A comparative study on the performance of dissortative mating and immigrants-based strategies for evolutionary dynamic optimization

Traditional Genetic Algorithms (GAs) mating schemes select individuals for crossover independently of their genotypic or phenotypic similarities. In Nature, this behavior is known as random mating. However, non-random protocols, in which individuals mate according to their kinship or likeness, are more common in natural species. Previous studies indicate that when applied to GAs, dissortative mating - a type of non-random mating in which individuals are chosen according to their similarities - may improve their performance (on both speed and reliability). Dissortative mating maintains genetic diversity at a higher level during the run, a fact that is frequently observed as a possible cause of dissortative GAs’ ability to escape local optima. Dynamic optimization demands a special attention when designing and tuning a GA, since diversity plays an even more crucial role than it does when tackling static ones. This paper investigates the behavior of the Adaptive Dissortative Mating GA (ADMGA) in dynamic problems and compares it to GAs based on random immigrants. ADMGA selects parents according to their Hamming distance, via a self-adjustable threshold value. The method, by keeping population diversity during the run, provides an effective means to deal with dynamic problems. Tests conducted with dynamic trap functions and dynamic versions of Road Royal and knapsack problems indicate that ADMGA is able to outperform other GAs on a wide range of tests, being particularly effective when the frequency of changes is low. Specifically, ADMGA outperforms two state-of-the-art algorithms on many dynamic scenarios. In addition, and unlike preceding dissortative mating GAs and other evolutionary techniques for dynamic optimization, ADMGA self-regulates the intensity of the mating restrictions and does not increase the set of parameters in GAs, thus being easier to tune.     

Discussion on paper “A Robust Real-Time Ellipse Detector” by Zhang and Liu

We correct a fundamental formula from paper “A Robust Real-Time Ellipse Detector” by Zhang and Liu published in journal “Pattern Recognition” in 2005.     

Randomization can be a healer: consensus with dynamic omission failures

Wireless ad-hoc networks are being increasingly used in diverse contexts, ranging from casual meetings to disaster recovery operations. A promising approach is to model these networks as distributed systems prone to dynamic communication failures. This captures transitory disconnections in communication due to phenomena like interference and collisions, and permits an efficient use of the wireless broadcasting medium. This model, however, is bound by the impossibility result of Santoro and Widmayer, which states that, even with strong synchrony assumptions, there is no deterministic solution to any non-trivial form of agreement if n ? 1 or more messages can be lost per communication round in a system with n processes. In this paper we propose a novel way to circumvent this impossibility result by employing randomization. We present a consensus protocol that ensures safety in the presence of an unrestricted number of omission faults, and guarantees progress in rounds where such faults are bounded by ${f \,{\leq}\,\lceil \frac{n}{2} \rceil (n\,{-}\,k)\,{+}\,k\,{-}\,2}$ , where k is the number of processes required to decide, eventually assuring termination with probability 1.     

Towards human motion capture from a camera mounted on a mobile robot

This article describes a multiple feature data fusion applied to a particle filter for marker-less human motion capture (HMC) by using a single camera devoted to an assistant mobile robot. Particle filters have proved to be well suited to this robotic context. Like numerous approaches, the principle relies on the projection of the model's silhouette of the tracked human limbs and appearance features located on the model surface, to validate the particles (associated configurations) which correspond to the best model-to-image fits. Our particle filter based HMC system is improved and extended in two ways. First, our estimation process is based on the so-called AUXILIARY scheme which has been surprisingly seldom exploited for tracking purpose. This scheme is shown to outperform conventional particle filters as it limits drastically the well-known burst in term of particles when considering high dimensional state-space. The second line of investigation concerns data fusion. Data fusion is considered both in the importance and measurement functions with some degree of adaptability depending on the current human posture and the environmental context encountered by the robot. Implementation and experiments on indoor sequences acquired by an assistant mobile robot highlight the relevance and versatility of our HMC system. Extensions are finally discussed.     

<Emphasis Type="Italic">hp</Emphasis>-Version <Emphasis Type="Italic">a priori</Emphasis> Error Analysis of Interior Penalty Discontinuous Galerkin Finite Element Approximations to the Biharmonic Equation

We consider the symmetric formulation of the interior penalty discontinuous Galerkin finite element method for the numerical solution of the biharmonic equation with Dirichlet boundary conditions in a bounded polyhedral domain in . For a shape-regular family of meshes consisting of parallelepipeds, we derive hp-version a priori bounds on the global error measured in the L² norm and in broken Sobolev norms. Using these, we obtain hp-version bounds on the error in linear functionals of the solution. The bounds are optimal with respect to the mesh size h and suboptimal with respect to the degree of the piecewise polynomial approximation p. The theoretical results are confirmed by numerical experiments, and some practical applications in Poisson–Kirchhoff thin plate theory are presented.     

A theoretical and empirical investigation of multi‐item on‐line auctions

In this paper we explore and analyze the structure of Internet auctions from an analytical and an empirical perspective. Such web‐based auctions are rapidly emerging as a mercantile process of choice in the electronic marketplace. We observe current Internet auctions for one‐time products, such as rapidly aging hardware, and analyze them within the framework of the existing auction theory. While traditional auction theory focuses on single‐item auctions, we observe that a majority of on‐line auctions are multi‐item auctions. A significant contribution of this work is the theoretical derivation of the structure of the winning bids in multi‐item progressive on‐line auctions. Additionally, for comparative purposes, we explore the structural characteristics of alternative multi‐item auction mechanisms proposed in the auction theory. We derive hypotheses based on our analytical results and compare two different types of auction mechanisms. We test the traditional auction theory assumption regarding the homogeneity of bidders and present the first ever empirically derived classification and performance‐comparison of on‐line bidders. We test our hypotheses using real‐world empirical data obtained by tracking a premier web‐based auction site. Statistical analysis of the data indicates that firms may gain by choosing alternative auction mechanisms. We also provide directions for further exploration of this emerging but important dimension of electronic commerce. This revised version was published online in July 2006 with corrections to the Cover Date.     

Development of an Autonomous Robot for Gas Storage Spheres Inspection

Inspection for corrosion of gas storage spheres at the welding seam lines must be done periodically. Until now this inspection is being done manually and has a high cost associated to it and a high risk of inspection personel injuries. The Brazilian Petroleum Company, Petrobras, is seeking cost reduction and personel safety by the use of autonomous robot technology. This paper presents the development of a robot capable of autonomously follow a welding line and transporting corrosion measurement sensors. The robot uses a pair of sensors each composed of a laser source and a video camera that allows the estimation of the center of the welding line. The mechanical robot uses four magnetic wheels to adhere to the sphere’s surface and was constructed in a way that always three wheels are in contact with the sphere’s metallic surface which guarantees enough magnetic atraction to hold the robot in the sphere’s surface all the time. Additionally, an independently actuated table for attaching the corrosion inspection sensors was included for small position corrections. Tests were conducted at the laboratory and in a real sphere showing the validity of the proposed approach and implementation.     

Integration of virtual and real environments for engineering service-oriented manufacturing systems

Engineering frameworks are currently required to support the easy, low-cost, modular and integrated development of manufacturing systems addressing the emergent requirements of re-configurability, responsiveness and robustness. This paper discusses the integration of 2D/3D digital software tools with Petri net based service-oriented frameworks to allow the design, configuration, analysis, validation, simulation, monitoring and control of manufacturing systems in a virtual environment and its posterior smooth migration into the real ??physical?? environment. An experimental case study was implemented to validate the proposed concepts, using the Continuum platform to design, compose, analyze, validate and simulate the Petri nets based service-oriented manufacturing control system, and the Delmia Automation^TM software suite to support the rapid prototyping and the easy simulation of the designed control solution. The experimental results prove several aspects of the proposed approach, notably the smooth migration between the design and the operation phases, one of the main objectives of the work.     

Acoustic evaluation and adjustment of an open-plan office through architectural design and noise control

Arranging office space into a single open room offers advantages in terms of easy exchange of information and interaction among coworkers, but reduces privacy and acoustic comfort. Thus, the purpose of this work was to evaluate the acoustic quality of a real open-plan office and to propose changes in the room to improve the acoustic conditioning of this office. The computational model of the office under study was calibrated based on RT and STI measurements. Predictions were made of the RT and STI, which generated the radius of distraction r(D), and the rate of spatial decay of sound pressure levels per distance doubling DL(2) in the real conditions of the office and after modifications of the room. The insertion of dividers between work stations and an increase in the ceiling's sound absorption improved the acoustic conditions in the office under study.     

A New Approximation Algorithm for Finding Heavy Planar Subgraphs

We provide the first nontrivial approximation algorithm for MAXIMUM WEIGHT PLANAR SUBGRAPH, the NP-hard problem of finding a heaviest planar subgraph in an edge-weighted graph G . This problem has applications in circuit layout, facility layout, and graph drawing. No previous algorithm for MAXIMUM WEIGHT PLANAR SUBGRAPH had a performance ratio exceeding 1/3 , which is obtained by any algorithm that produces a maximum weight spanning tree in G . Based on the Berman—Ramaiyer Steiner tree algorithm, the new algorithm has performance ratio at least 1/3+1/72 and at most 5/12 . We also show that if G is complete and its edge weights satisfy the triangle inequality, then the performance ratio is at least 3/8 . Furthermore, we derive the first nontrivial performance ratio (7/12 instead of 1/2 ) for the NP-hard SC MAXIMUM WEIGHT OUTERPLANAR SUBGRAPH problem.