U-curve: A branch-and-bound optimization algorithm for U-shaped cost functions on Boolean lattices applied to the feature selection problem

This paper presents the formulation of a combinatorial optimization problem with the following characteristics: (i) the search space is the power set of a finite set structured as a Boolean lattice; (ii) the cost function forms a U-shaped curve when applied to any lattice chain. This formulation applies for feature selection in the context of pattern recognition. The known approaches for this problem are branch-and-bound algorithms and heuristics that explore partially the search space. Branch-and-bound algorithms are equivalent to the full search, while heuristics are not. This paper presents a branch-and-bound algorithm that differs from the others known by exploring the lattice structure and the U-shaped chain curves of the search space. The main contribution of this paper is the architecture of this algorithm that is based on the representation and exploration of the search space by new lattice properties proven here. Several experiments, with well known public data, indicate the superiority of the proposed method to the sequential floating forward selection (SFFS), which is a popular heuristic that gives good results in very short computational time. In all experiments, the proposed method got better or equal results in similar or even smaller computational time. (C) 2009 Elsevier Ltd. All rights reserved.

An application of lattice basis reduction to polynomial identities for algebraic structures

The authors` recent classification of trilinear operations includes, among other cases, a fourth family of operations with parameter q epsilon Q boolean OR {infinity}, and weakly commutative and weakly anticommutative operations. These operations satisfy polynomial identities in degree 3 and further identities in degree 5. For each operation, using the row canonical form of the expansion matrix E to find the identities in degree 5 gives extremely complicated results. We use lattice basis reduction to simplify these identities: we compute the Hermite normal form H of E(t), obtain a basis of the nullspace lattice from the last rows of a matrix U for which UE(t) = H, and then use the LLL algorithm to reduce the basis. (C) 2008 Elsevier Inc. All rights reserved.

LATTICE BOLTZMANN METHOD AND CELLULAR AUTOMATA SIMULATION OF PARTICLE MOTION AND DEPOSITION IN 2-D CASE

This technical report discusses the application of the Lattice Boltzmann Method (LBM) and Cellular Automata (CA) simulation in fluid flow and particle deposition. The current work focuses on incompressible flow simulation passing cylinders, in which we incorporate the LBM D2Q9 and CA techniques to simulate the fluid flow and particle loading respectively. For the LBM part, the theories of boundary conditions are studied and verified using the Poiseuille flow test. For the CA part, several models regarding simulation of particles are explained. And a new Digital Differential Analyzer (DDA) algorithm is introduced to simulate particle motion in the Boolean model. The numerical results are compared with a previous probability velocity model by Masselot [Masselot 2000], which shows a satisfactory result.

Reaction-diffusion stochastic lattice model for a predator-prey system

We have the purpose of analyzing the effect of explicit diffusion processes in a predator-prey stochastic lattice model. More precisely we wish to investigate the possible effects due to diffusion upon the thresholds of coexistence of species, i. e., the possible changes in the transition between the active state and the absorbing state devoid of predators. To accomplish this task we have performed time dependent simulations and dynamic mean-field approximations. Our results indicate that the diffusive process can enhance the species coexistence.

Aging and fluctuation-dissipation ratio in a nonequilibrium q-state lattice model

A generalized version of the nonequilibrium linear Glauber model with q states in d dimensions is introduced and analyzed. The model is fully symmetric, its dynamics being invariant under all permutations of the q states. Exact expressions for the two-time autocorrelation and response functions on a d-dimensional lattice are obtained. In the stationary regime, the fluctuation-dissipation theorem holds, while in the transient the aging is observed with the fluctuation-dissipation ratio leading to the value predicted for the linear Glauber model.

Phase diagram of a model for a binary mixture of nematic molecules on a Bethe lattice

We investigate the phase diagram of a discrete version of the Maier-Saupe model with the inclusion of additional degrees of freedom to mimic a distribution of rodlike and disklike molecules. Solutions of this problem on a Bethe lattice come from the analysis of the fixed points of a set of nonlinear recursion relations. Besides the fixed points associated with isotropic and uniaxial nematic structures, there is also a fixed point associated with a biaxial nematic structure. Due to the existence of large overlaps of the stability regions, we resorted to a scheme to calculate the free energy of these structures deep in the interior of a large Cayley tree. Both thermodynamic and dynamic-stability analyses rule out the presence of a biaxial phase, in qualitative agreement with previous mean-field results.

Critical behavior of the susceptible-infected-recovered model on a square lattice

By means of numerical simulations and epidemic analysis, the transition point of the stochastic asynchronous susceptible-infected-recovered model on a square lattice is found to be c(0)=0.176 500 5(10), where c is the probability a chosen infected site spontaneously recovers rather than tries to infect one neighbor. This point corresponds to an infection/recovery rate of lambda(c)=(1-c(0))/c(0)=4.665 71(3) and a net transmissibility of (1-c(0))/(1+3c(0))=0.538 410(2), which falls between the rigorous bounds of the site and bond thresholds. The critical behavior of the model is consistent with the two-dimensional percolation universality class, but local growth probabilities differ from those of dynamic percolation cluster growth, as is demonstrated explicitly.

Probability currents and entropy production in nonequilibrium lattice systems

The structure of probability currents is studied for the dynamical network after consecutive contraction on two-state, nonequilibrium lattice systems. This procedure allows us to investigate the transition rates between configurations on small clusters and highlights some relevant effects of lattice symmetries on the elementary transitions that are responsible for entropy production. A method is suggested to estimate the entropy production for different levels of approximations (cluster sizes) as demonstrated in the two-dimensional contact process with mutation.

Dynamic transitions in a three dimensional associating lattice gas model

The aggregation of interacting Brownian particles in sheared concentrated suspensions is an important issue in colloid and soft matter science per se. Also, it serves as a model to understand biochemical reactions occurring in vivo where both crowding and shear play an important role. We present an effective medium approach within the Smoluchowski equation with shear which allows one to calculate the encounter kinetics through a potential barrier under shear at arbitrary colloid concentrations. Experiments on a model colloidal system in simple shear flow support the validity of the model in the concentration range considered. By generalizing Kramers' rate theory to the presence of shear and collective hydrodynamics, our model explains the significant increase in the shear-induced reaction-limited aggregation kinetics upon increasing the colloid concentration.

Dynamic transitions in a two dimensional associating lattice gas model

Using Monte Carlo simulations we investigate some new aspects of the phase diagram and the behavior of the diffusion coefficient in an associating lattice gas (ALG) model on different regions of the phase diagram. The ALG model combines a two dimensional lattice gas where particles interact through a soft core potential and orientational degrees of freedom. The competition between soft core potential and directional attractive forces results in a high density liquid phase, a low density liquid phase, and a gas phase. Besides anomalies in the behavior of the density with the temperature at constant pressure and of the diffusion coefficient with density at constant temperature are also found. The two liquid phases are separated by a coexistence line that ends in a bicritical point. The low density liquid phase is separated from the gas phase by a coexistence line that ends in tricritical point. The bicritical and tricritical points are linked by a critical lambda-line. The high density liquid phase and the fluid phases are separated by a second critical tau-line. We then investigate how the diffusion coefficient behaves on different regions of the chemical potential-temperature phase diagram. We find that diffusivity undergoes two types of dynamic transitions: a fragile-to-strong transition when the critical lambda-line is crossed by decreasing the temperature at a constant chemical potential; and a strong-to-strong transition when the critical tau-line is crossed by decreasing the temperature at a constant chemical potential.

Anomalous lattice parameter of magnetic semiconductor alloys

The addition of transition metals to III-V semiconductors radically changes their electronic, magnetic, and structural properties. We show by ab initio calculations that in contrast to the conventional semiconductor alloys, the lattice parameter in magnetic semiconductor alloys, including those with diluted concentration, strongly deviates from Vegard's law. We find a direct correlation between the magnetic moment and the anion-transition metal bond lengths and derive a simple and general formula that determines the lattice parameter of a particular magnetic semiconductor by considering both the composition and magnetic moment. This dependence can explain some experimentally observed anomalies and stimulate other kind of investigations.

Soliton dynamics at an interface between a uniform medium and a nonlinear optical lattice

We study trapping and propagation of a matter-wave soliton through the interface between uniform medium and a nonlinear optical lattice. Different regimes for transmission of a broad and a narrow solitons are investigated. Reflections and transmissions of solitons are predicted as a function of the lattice phase. The existence of a threshold in the amplitude of the nonlinear optical lattice, separating the transmission and reflection regimes, is verified. The localized nonlinear surface state, corresponding to the soliton trapped by the interface, is found. Variational approach predictions are confirmed by numerical simulations for the original Gross-Pitaevskii equation with nonlinear periodic potentials.

Magnetoelastic and thermal effects in the BiMn(2)O(5) lattice: A high-resolution x-ray diffraction study

High-resolution synchrotron x-ray diffraction measurements were performed on single crystalline and powder samples of BiMn(2)O(5). A linear temperature dependence of the unit cell volume was found between T(N)=38 and 100 K, suggesting that a low-energy lattice excitation may be responsible for the lattice expansion in this temperature range. Between T(*)similar to 65 K and T(N), all lattice parameters showed incipient magnetoelastic effects, due to short-range spin correlations. An anisotropic strain along the a direction was also observed below T(*). Below T(N), a relatively large contraction of the a parameter following the square of the average sublattice magnetization of Mn was found, indicating that a second-order spin Hamiltonian accounts for the magnetic interactions along this direction. On the other hand, the more complex behaviors found for b and c suggest additional magnetic transitions below T(N) and perhaps higher-order terms in the spin Hamiltonian. Polycrystalline samples grown by distinct routes and with nearly homogeneous crystal structure above T(N) presented structural phase coexistence below T(N), indicating a close competition amongst distinct magnetostructural states in this compound.

Social interaction as a heuristic for combinatorial optimization problems

We investigate the performance of a variant of Axelrod's model for dissemination of culture-the Adaptive Culture Heuristic (ACH)-on solving an NP-Complete optimization problem, namely, the classification of binary input patterns of size F by a Boolean Binary Perceptron. In this heuristic, N agents, characterized by binary strings of length F which represent possible solutions to the optimization problem, are fixed at the sites of a square lattice and interact with their nearest neighbors only. The interactions are such that the agents' strings (or cultures) become more similar to the low-cost strings of their neighbors resulting in the dissemination of these strings across the lattice. Eventually the dynamics freezes into a homogeneous absorbing configuration in which all agents exhibit identical solutions to the optimization problem. We find through extensive simulations that the probability of finding the optimal solution is a function of the reduced variable F/N(1/4) so that the number of agents must increase with the fourth power of the problem size, N proportional to F(4), to guarantee a fixed probability of success. In this case, we find that the relaxation time to reach an absorbing configuration scales with F(6) which can be interpreted as the overall computational cost of the ACH to find an optimal set of weights for a Boolean binary perceptron, given a fixed probability of success.