1-2/2007 Advances in Artificial Intelligence

Contents:

• J.Duda, A Critical Review of the Newest Biologically-Inspired Algorithms for the Flowshop Scheduling Problem - abstract | full text
• K.Jassem, T.Kowalski, Machine Translation Using Scarce Bilingual Corpora - abstract | full text
• L.Kobylinski, K.Walczak, Class Association Rules with Occurrence Count in Image Classification - abstract | full text
• W.Kosinski, U.Markowska-Kaczmar, An Evolutionary Algorithm Determining a Defuzzyfication Functional - abstract | full text
• J.L.Kulikowski, Adaptive Reordering of Observation Space to Improve Pattern Recognition - abstract | full text
• H.Kwasnicka, P.Wozniak, EMOT - an Evolutionary Approach to 3D Computer Animation - abstract | full text
• L.Machnik, A Document Clustering Method Based on Ant Algorithms - abstract | full text
• L.Malazizi, D.Neagu, Q.Chaudhry, An Algorithm for Data Quality Assessment in Predictive Toxicology - abstract | full text
• S.Margenov, Y.Vutov, Preconditioning of Voxel FEM Elliptic Systems - abstract | full text
• M.Xu, J.Dong, Generating New Styles of Chinese Strokes Based on Statistical Model - abstract | full text
• M.Norberciak, A Hybrid Method for Solving Timetabling Problems Based on the Evolutionary Approach - abstract | full text
• M.Piasecki, Polish Tagger TaKIPI: Rule Based Construction and Optimisation - abstract | full text
• J.Tvrdik, Differential Evolution with Competitive Setting of Control Parameters - abstract | full text

Abstracts:

• J.Duda, A Critical Review of the Newest Biologically-Inspired Algorithms for the Flowshop Scheduling Problem

  The three most recent bio-inspired heuristics proposed in the OR literature for solving the flowshop scheduling problem are revised in the paper. All of these algorithms use local search procedures to improve solutions achieved by the main procedure. The author tries to asses the gains from hybridizing such heuristics with local search procedures. The achieved results confirm that simple local search algorithms can compete successfully with much complex hybrids.

• K.Jassem, T.Kowalski, Machine Translation Using Scarce Bilingual Corpora

  We propose a method for automatic extraction of translation rules suitable for a rule-based machine translation system by using a target language syntactic parser and scarce bilingual resources as linguistic knowledge sources. We propose an algorithm that assembles translation rules in order to translate an input sentence.

• L.Kobylinski, K.Walczak, Class Association Rules with Occurrence Count in Image Classification

  The concept of utilizing association rules for classification has emerged in recent years. This approach has often proved to be more efficient and accurate than traditional techniques. In this paper we extend the existing associative classifier building algorithms and apply them to the problem of image classification. We describe a set of photographs with features calculated on the basis of their color and texture characteristics and experiment with different types of rules which use the information about the existence of a particular feature in an image, its occurrence count and spatial proximity to classify the images accurately. We suggest using association rules more closely tied to the nature of the image data and compare the results with those of classification with simpler rules, taking into consideration only the existence of a particular feature on an image.

• W.Kosinski, U.Markowska-Kaczmar, An Evolutionary Algorithm Determining a Defuzzyfication Functional

  Order fuzzy numbers are defined that make it possible to deal with fuzzy inputs quantitatively, exactly in the same way as with real numbers, together with four algebraic operations. An approximation formula is given for a defuzzyfication functional that plays the main role when dealing with fuzzy controllers and fuzzy inference systems. A dedicated evolutionary algorithm is presented in order to determine the form of a functional when a training set is given. The form of a genotype composed of three types of chromosomes and the fitness function are given and Genetic operators are proposed.

• J.L.Kulikowski, Adaptive Reordering of Observation Space to Improve Pattern Recognition

  The problem of observation space reordering is presented as a novel approach to pattern recognition based on non-parametric, combinatorial statistical tests. It consists in linearly ordering the elements of a discrete multi-dimensional observation space along a curve such that elements belonging to different similarity classes are as close to each other as possible, the similarity classes are mutually separated, and the length of the curve is kept to minimum. The problem is NP-difficult and it is shown how its approximate solution can be reached by a series of transformations improving the initial lexicographic linear order of a discrete observation space. Recommendations are formulated for linear order improvement leading to a pattern recognition algorithm based on serial statistical test.

• H.Kwasnicka, P.Wozniak, EMOT - an Evolutionary Approach to 3D Computer Animation

  Key-framing and Inverse Kinematics are popular animation methods, but new approaches are still developed. We propose a new evolutionary method of creating animation - the EMOT (Evolutionary MOTion) system. It enables automation of motion of animated characters and uses a new evolutionary approach - Gene Expression Programming (GEP). Characters are controlled by computer programs, an animator providing the way of motion's evaluation. GEP works with a randomly selected initial population, using directed but random selection. Experiments have shown that the proposed method is capable of developing robust controllers.

• L.Machnik, A Document Clustering Method Based on Ant Algorithms

  Ant Algorithms, particularly the Ant Colony Optimization (ACO) metaheuristic, are universal, flexible and scalable because they are based on multi-agent cooperation. The increased demand for effective methods of managing large collections of documents is a sufficient stimulus to place the research on new applications of ant-based systems in the area of text document processing. The author presents an implementation of such a technique in the area of document clustering. Details of the ACO document clustering method and results of experiments are presented.

• L.Malazizi, D.Neagu, Q.Chaudhry, An Algorithm for Data Quality Assessment in Predictive Toxicology

  Lack of the quality of the information that is integrated from heterogeneous sources is an important issue in many scientific domains. In toxicology the importance is even greater since the data is used for Quantitative Structure Activity Relationship (QSAR) modeling for prediction of chemical toxicity of new compounds. Much work has been done on QSARs but little attention has been paid to the quality of the data used. The underlying concept points to the absence of the quality criteria framework in this domain. This paper presents a review on some of the existing data quality assessment methods in various domains and their relevance and possible application to predictive toxicology, highlights number of data quality deficiencies from experimental work on internal data and also proposes some quality metrics and an algorithm for assessing data quality concluded from the results.

• S.Margenov, Y.Vutov, Preconditioning of Voxel FEM Elliptic Systems

  The presented comparative analysis concerns two iterative solvers for large-scale linear systems related to μFEM simulation of human bones. The considered scalar elliptic problems represent the strongly heterogeneous structure of real bone specimens. The voxel data are obtained with high resolution computer tomography. Non-conforming Rannacher-Turek finite elements are used to discretize of the considered elliptic problem. The preconditioned conjugate gradient method is known to be the best tool for efficient solution of large-scale symmetric systems with sparse positive definite matrices. Here, the performance of two preconditioners is studied, namely modified incomplete Cholesky factorization, MIC(0), and algebraic multigrid. The comparative analysis is mostly based on the computing times to run the sequential codes. The number of iterations for both preconditioners is also discussed. Finally, numerical tests of a novel parallel MIC(0) code are presented. The obtained parallel speed-ups and efficiencies illustrate the scope of efficient applications for real-life large-scale problems.

• M.Xu, J.Dong, Generating New Styles of Chinese Strokes Based on Statistical Model

  Chinese calligraphy is one of the most important Chinese arts: a form of entertainment as well as an embodiment of figurative thinking. In this paper, a statistical model-based approach to generating new styles of Chinese character strokes is proposed. Original calligraphy samples are aligned in a common co-ordinate frame and a training set consisting of landmarks is generated semi-automatically. The most significant features of the training set are extracted and a statistical model is built in order to generate strokes in new styles. The Bezier curve is used to fit the discrete contour data.

• M.Norberciak, A Hybrid Method for Solving Timetabling Problems Based on the Evolutionary Approach

  Timetabling problems are often difficult and time-consuming to solve. Most of the methods of solving these problems are limited to one problem instance or class. This paper describes a universal method for solving large, highly constrained timetabling problems in various domains. The solution is based on an evolutionary algorithm framework and employs tabu search to quicken the solution finding process. Hyper-heuristics are used to establish the algorithm's operating parameters. The method has been used to solve three timetabling problems with promising results of extensive experiments.

• M.Piasecki, Polish Tagger TaKIPI: Rule Based Construction and Optimisation

  A large number of different tags, limited corpora and the free word order are the main causes of low accuracy of tagging in Polish (automatic disambiguation of morphological descriptions) by applying commonly used techniques based on stochastic modelling. In the paper the rule-based architecture of the TaKIPI Polish tagger combining handwritten and automatically extracted rules is presented. The possibilities of optimisation of its parameters and component are discussed, including the possibility of using different methods of rules extraction, than C4.5 Decision Trees applied initially. The main goal of this paper is to explore a range of promising rule-based classifiers and investigate their impact on the accuracy of tagging. Simple techniques of combing classifiers are also tested. The performed experiments have shown that even a simple combination of different classifiers can increase the tagger's accuracy by almost one percent.

• J.Tvrdik, Differential Evolution with Competitive Setting of Control Parameters

  This paper is focused on the adaptation of control parameters in differential evolution. Competition of various control parameter settings was proposed in order to ensure self-adaptation of parameter values in the search process. Several variants of such algorithm were tested on six functions at four levels of the search-space dimension. The competitive variants of differential evolution have proved to be more reliable and less time-consuming than the standard differential evolution. The competitive variants have also outperformed other tested algorithms in their reliability and convergence rate.