How Good are Genetic Algorithms at Finding Large Cliques: An Experimental Study

This paper investigates the power of genetic algorithms at solving the MAX-CLIQUE problem. We measure the performance of a standard genetic algorithm on an elementary set of problem instances consisting of embedded cliques in random graphs. We indicate the need for improvement, and introduce a new genetic algorithm, the multi-phase annealed GA, which exhibits superior performance on the same problem set. As we scale up the problem size and test on \hard" benchmark instances, we notice a degraded performance in the algorithm caused by premature convergence to local minima. To alleviate this problem, a sequence of modi cations are implemented ranging from changes in input representation to systematic local search. The most recent version, called union GA, incorporates the features of union cross-over, greedy replacement, and diversity enhancement. It shows a marked speed-up in the number of iterations required to find a given solution, as well as some improvement in the clique size found. We discuss issues related to the SIMD implementation of the genetic algorithms on a Thinking Machines CM-5, which was necessitated by the intrinsically high time complexity (O(n3)) of the serial algorithm for computing one iteration. Our preliminary conclusions are: (1) a genetic algorithm needs to be heavily customized to work "well" for the clique problem; (2) a GA is computationally very expensive, and its use is only recommended if it is known to find larger cliques than other algorithms; (3) although our customization e ort is bringing forth continued improvements, there is no clear evidence, at this time, that a GA will have better success in circumventing local minima.

A FLOW-THROUGH ACOUSTIC WAVEGUIDE FOR TWO-PHASE BUBBLY FLOW VOID FRACTION MEASUREMENT

In the Spallation Neutron Source (SNS) facility at Oak Ridge National Laboratory (ORNL), the deposition of a high-energy proton beam into the liquid mercury target forms bubbles whose asymmetric collapse cause Cavitation Damage Erosion (CDE) to the container walls, thereby reducing its usable lifetime. One proposed solution for mitigation of this damage is to inject a population of microbubbles into the mercury, yielding a compliant and attenuative medium that will reduce the resulting cavitation damage. This potential solution presents the task of creating a diagnostic tool to monitor bubble population in the mercury flow in order to correlate void fraction and damage. Details of an acoustic waveguide for the eventual measurement of two-phase mercury-helium flow void fraction are discussed. The assembly’s waveguide is a vertically oriented stainless steel cylinder with 5.08cm ID, 1.27cm wall thickness and 40cm length. For water experiments, a 2.54cm thick stainless steel plate at the bottom supports the fluid, provides an acoustically rigid boundary condition, and is the mounting point for a hydrophone. A port near the bottom is the inlet for the fluid of interest. A spillover reservoir welded to the upper portion of the main tube allows for a flow-through design, yielding a pressure release top boundary condition for the waveguide. A cover on the reservoir supports an electrodynamic shaker that is driven by linear frequency sweeps to excite the tube. The hydrophone captures the frequency response of the waveguide. The sound speed of the flowing medium is calculated, assuming a linear dependence of axial mode number on modal frequency (plane wave). Assuming that the medium has an effective-mixture sound speed, and that it contains bubbles which are much smaller than the resonance radii at the highest frequency of interest (Wood’s limit), the void fraction of the flow is calculated. Results for water and bubbly water of varying void fraction are presented, and serve to demonstrate the accuracy and precision of the apparatus.

Multi-scale 3D Scene Flow from Binocular Stereo Sequences

Scene flow methods estimate the three-dimensional motion field for points in the world, using multi-camera video data. Such methods combine multi-view reconstruction with motion estimation approaches. This paper describes an alternative formulation for dense scene flow estimation that provides convincing results using only two cameras by fusing stereo and optical flow estimation into a single coherent framework. To handle the aperture problems inherent in the estimation task, a multi-scale method along with a novel adaptive smoothing technique is used to gain a regularized solution. This combined approach both preserves discontinuities and prevents over-regularization-two problems commonly associated with basic multi-scale approaches. Internally, the framework generates probability distributions for optical flow and disparity. Taking into account the uncertainty in the intermediate stages allows for more reliable estimation of the 3D scene flow than standard stereo and optical flow methods allow. Experiments with synthetic and real test data demonstrate the effectiveness of the approach.

Multi-Scale 3D Scene Flow from Binocular Stereo Sequences

Scene flow methods estimate the three-dimensional motion field for points in the world, using multi-camera video data. Such methods combine multi-view reconstruction with motion estimation. This paper describes an alternative formulation for dense scene flow estimation that provides reliable results using only two cameras by fusing stereo and optical flow estimation into a single coherent framework. Internally, the proposed algorithm generates probability distributions for optical flow and disparity. Taking into account the uncertainty in the intermediate stages allows for more reliable estimation of the 3D scene flow than previous methods allow. To handle the aperture problems inherent in the estimation of optical flow and disparity, a multi-scale method along with a novel region-based technique is used within a regularized solution. This combined approach both preserves discontinuities and prevents over-regularization – two problems commonly associated with the basic multi-scale approaches. Experiments with synthetic and real test data demonstrate the strength of the proposed approach.