Finding multiple solutions in job shop scheduling by niching genetic algorithms

The interest in multimodal optimization methods is increasing in the last years. The objective is to find multiple solutions that allow the expert to choose the solution that better adapts to the actual conditions. Niching methods extend genetic algorithms to domains that require the identification of multiple solutions. There are different niching genetic algorithms: sharing, clearing, crowding and sequential, etc. The aim of this study is to study the applicability and the behavior of several niching genetic algorithms in solving job shop scheduling problems, by establishing a criterion in the use of different methods according to the needs of the expert. We will experiment with different instances of this problem, analyzing the behavior of the algorithms from the efficacy and diversity points of view.     

Topic Identification in Dynamical Text by Complexity Pursuit

The problem of analysing dynamically evolving textual data has arisen within the last few years. An example of such data is the discussion appearing in Internet chat lines. In this Letter a recently introduced source separation method, termed as complexity pursuit, is applied to the problem of finding topics in dynamical text and is compared against several blind separation algorithms for the problem considered. Complexity pursuit is a generalisation of projection pursuit to time series and it is able to use both higher-order statistical measures and temporal dependency information in separating the topics. Experimental results on chat line and newsgroup data demonstrate that the minimum complexity time series indeed do correspond to meaningful topics inherent in the dynamical text data, and also suggest the applicability of the method to query-based retrieval from a temporally changing text stream. This revised version was published online in June 2006 with corrections to the Cover Date.     

Selection of Strategies for Collision-free Motion in Multi-manipulator Systems

Strategy-based path planning was introduced by the authors as a way to give robotic manipulators some sort of reactive behaviour in dynamic and unpredictable environments. This approach is based on making robots react to moving obstacles using a restricted subset of the configuration space, and on using an off-line pre-planning stage to choose the restricted subset. In this paper, strategy-based path planning is applied and explored, focusing our attention on the off-line stage. It is applied to the joint motion of two and three robots that perform pick and place tasks sharing common working areas.     

Basic fuzzy logic and <Emphasis Type="Italic">BL</Emphasis>-algebras II

 Three new (easy) results about the computational complexity of basic propositional fuzzy logic BL are presented. An important formula of predicate logic is shown 1-true in all interpretations over saturated BL-chains but is not a BL-1-tautology, i.e. is not 1-true in a safe interpretation over a non-saturated BL-algebra. Partial support of the grant No. A1030004/00 of the Grant Agency of the Academy of Science of the Czech Republic is acknowledged.     

Using Self-Similarity to Cluster Large Data Sets

Clustering is a widely used knowledge discovery technique. It helps uncovering structures in data that were not previously known. The clustering of large data sets has received a lot of attention in recent years, however, clustering is a still a challenging task since many published algorithms fail to do well in scaling with the size of the data set and the number of dimensions that describe the points, or in finding arbitrary shapes of clusters, or dealing effectively with the presence of noise. In this paper, we present a new clustering algorithm, based in self-similarity properties of the data sets. Self-similarity is the property of being invariant with respect to the scale used to look at the data set. While fractals are self-similar at every scale used to look at them, many data sets exhibit self-similarity over a range of scales. Self-similarity can be measured using the fractal dimension. The new algorithm which we call Fractal Clustering (FC) places points incrementally in the cluster for which the change in the fractal dimension after adding the point is the least. This is a very natural way of clustering points, since points in the same cluster have a great degree of self-similarity among them (and much less self-similarity with respect to points in other clusters). FC requires one scan of the data, is suspendable at will, providing the best answer possible at that point, and is incremental. We show via experiments that FC effectively deals with large data sets, high-dimensionality and noise and is capable of recognizing clusters of arbitrary shape.     

Declarative Formalization of Reasoning Strategies: A Case Study on Heuristic Nonlinear Planning

We study the declarative formalization of reasoning strategies by presenting declarative formalizations of: (1) the SNLP algorithm for nonlinear planning, and (2) a particular algorithm for blocks world nonlinear planning proposed in this paper. The formal models of a heuristic forward chaining planner, which can take advantage of declarative formalizations of action selection strategies, and of a reasoning strategy based planner, which can use declarative formalizations of reasoning strategies, are proposed. The effectiveness of these systems is studied from formal and empirical points of view. Empirical results showing how the use of declarative formalizations of reasoning strategies can reduce the amount of search required for solving planning problems (with respect to state of the art planning systems) are presented.     

Migration Processes II: The Discrete Case

Following the study of migration processes in the continuous domain in Part I of this paper, we reformulate the concept of migration in the discrete domain (Z^m) and define Discrete Migration Processes (DMP). We demonstrate that this model is a natural discrete representation of the continuous model and maintains the model's features in a qualitative sense. We show that under discrete migration any discrete set shrinks to a limit in finitely many iterations. The discrete representation provides an advantageous basis for digitally implementing the MP model. Using this implementation we illustrate the discrete migration of various types of sets under various types of constraints.     

Dynamics of coupled and uncoupled two-phase flows in a slab mold

Two-phase flows in a mold of a slab caster are studied using water modeling, particle-image velocimetry (PIV), and computational fluid-dynamics techniques. Two-way coupled flows are observed in liquidgas systems, because both phases influence each other’s momentum transfer. In addition to this concept, PIV measurements indicate the existence of structurally coupled flows, where the velocity vectors of both phases observe similar orientations. When the drag forces of the liquid, exerted on the bubbles, exceed a certain value of the inertial forces of the liquid phase, at high mass loads of gas (ratio of mass flow rates of the gas phase and the liquid phase), the flow becomes structurally coupled. These types of flows promote large oscillations of the meniscus level. Two jets, liquid and bubble, were identified; the latter always reported larger angles than the first, independent of the gas load. Thus, a gas-rich jet is located closer to the lower edge of the submerged entry nozzle (SEN) port, and the liquid-rich jet is found above this position. The liquid-jet angle approaches that of the SEN port when the flow becomes structurally coupled. Structurally uncoupled flows report gas jets that follow torrent-type patterns which are well explained using a multiphase fluid-dynamics model. Structurally coupled flows yield gas jets with a continuous pattern.