Scientific Journals and Yearbooks Published at SAS

Article List

Computing and Informatics


Volume 28, 2009, No. 2

Content:


  History-based Self-Organizing Traffic Lights
J.C. Burguillo, P.S. Rodriguez, E. Costa, F. Gil

Self-organization, adaptive systems, urban traffic control, traffic modeling, multi-agent systems, NetLogo

Managing traffic in cities is nowadays a complex problem involving considerable physical and economical resources. Multi-agent Systems (MAS) consist of a set of distributed, usually co-operating, agents that act autonomously. The traffic in a city can be simulated by a MAS with different agents, cars and traffic lights, that interact to obtain an overall goal: to reduce average waiting times for the traffic users. In this paper, we describe an agent-based simulator to model traffic in cities. Using this simulator, we present a self-organizing solution to efficiently manage urban traffic. We compare our proposal with recent approaches, providing better results than classical and alternative self-organizing methods, with lower resources and investments.

Computing and Informatics. Volume 28, 2009, No. 2: 157-168.

 
  Optimization of Quadratic Assignment Problem Using Self Organising Migrating Algorithm
D. Davendra, I. Zelinka

Self organizing migrating algorithm, quadratic assignment problem, combinatorial optimization

This paper introduces the primary research involving Self Organinsing Migrating Algorithm (SOMA) to the permutative problem of Quadratic Assignment. SOMA is transformed from its canonical form to successfully solve permutative optimization problems. Conversion and repairment routines are added to the generic SOMA. The results presented outline the high effectiveness of SOMA for solving QAP problems.

Computing and Informatics. Volume 28, 2009, No. 2: 169-180.

 
  Global Impact Balancing in the Hierarchic Genetic Search
P. Jojczyk, R. Schaffer

The new Globally Balanced Hierarchic Genetic Strategy (GB-HGS) was introduced as a tool for solving difficult global optimization problems. This strategy provides a multi-deme economic stochastic search with an adaptive accuracy that allows many local extremes of the objective to be found. The strategy was designed according to the Multi Agent System (MAS) paradigm. The novelty of GB-HGS derives from its control of the search impact performed by various demes on the basis of the global information gathered and exchanged among the computing agents. This mechanism is applied together with the local profiling of the computational process already used in the previous versions of hierarchic genetic computations. The new strategy exhibits better efficiency, especially in the second phase of computations, when the promising regions containing the global extremes are encountered.

Computing and Informatics. Volume 28, 2009, No. 2: 181-193.

 
  Plateau Problem in the Watershed Transform
J. Nikodem

Mathematical morphology, watershed transform, watershed definition, plateau reduction

The watershed transform is one of best known and widely used methods for image segmentation in mathematical morphology. Since the definition, deriving from geology and nature observation is quite intuitive and straightforward to implement; many fast and powerful algorithms for watershed transform have already been presented. However, there still occur problems when one wishes to achieve a precise solution on blurred or noised image. The same range of problems is faced when a plateau occurs in the image. In this paper several methods for plateau reduction are discussed and some novel ideas proposed. All algorithms are performed on a set of both natural and synthetic images.

Computing and Informatics. Volume 28, 2009, No. 2: 195-207.

 
  Application of a Hierarchical Chromosome Based Genetic Algorithm to the Problem of Finding Optimal Initial Meshes for the Self-Adaptive hp-FEM
A. Paszynska, M. Paszynski

Finite element method, hp adaptivity, genetic algorithms

The paper presents an algorithm for finding the optimal initial mesh for the self-adaptive hp Finite Element Method (hp-FEM) calculations. We propose the application of the hierarchical chromosome based genetic algorithm for optimal selection of the initial mesh. The selection of the optimal initial mesh will optimize the convergence rate of the numerical error of the solution over the sequence of meshes generated by the self-adaptive hp-FEM. This is especially true in the case when material data are selected as a result of some stochastic algorithm and it is not possible to design optimal initial mesh by hand. The algorithm has been tested on the non-stationary mass transport problem modeling phase transition phenomenon.

Computing and Informatics. Volume 28, 2009, No. 2: 209-223.

 
  The LEM3 System for Multitype Evolutionary Optimization
J. Wojtusiak

Evolutionary computation, learnable evolution model, machine learning, multitype optimization, representation space

LEM3 is the newest version of the learnable evolution model (LEM), a non-Darwinian evolutionary computation methodology that employs machine learning to guide evolutionary processes. Due to the deep integration of different modes of operation, several novel elements in its algorithm, and the use of the advanced machine learning system AQ21, the LEM3 system is a highly efficient and effective implementation of the methodology. LEM3 is particularly attractive for multitype optimization because it supports, and treats accordingly, different attribute types for describing candidate solutions in the population. These attribute types are nominal, ordinal, structured, cyclic, interval, and ratio. Application to optimization of parameters of a complex system illustrates multitype optimization problem.

Computing and Informatics. Volume 28, 2009, No. 2: 225-236.

 
  A Tabu Search Algorithm for Scheduling Independent Jobs in Computational Grids
F. Xhafa, J. Carretero, B. Dorronsoro, E. Alba

Job scheduling, computational grid, tabu search

The efficient allocation of jobs to grid resources is indispensable for high performance grid-based applications, and it is a computationally hard problem even when there are no dependencies among jobs. We present in this paper a new tabu search (TS) algorithm for the problem of batch job scheduling on computational grids. We define it as a bi-objective optimization problem, consisting of the minimization of the makespan and flowtime. Our TS is validated versus three other algorithms in the literature for a classical benchmark. We additionally consider some more realistic benchmarks with larger size instances in static and dynamic environments. We show that our TS clearly outperforms the compared algorithms.

Computing and Informatics. Volume 28, 2009, No. 2: 237-250.

 
  Evaluation Measures for Text Summarization
J. Steinberger, K. Jezek

Text summarization, automatic extract, summary evaluation, latent semantic analysis, singular value decomposition

We explain the ideas of automatic text summarization approaches and the taxonomy of summary evaluation methods. Moreover, we propose a new evaluation measure for assessing the quality of a summary. The core of the measure is covered by Latent Semantic Analysis (LSA) which can capture the main topics of a document. The summarization systems are ranked according to the similarity of the main topics of their summaries and their reference documents. Results show a high correlation between human rankings and the LSA-based evaluation measure. The measure is designed to compare a summary with its full text. It can compare a summary with a human written abstract as well; however, in this case using a standard ROUGE measure gives more precise results. Nevertheless, if abstracts are not available for a given corpus, using the LSA-based measure is an appropriate choice.

Computing and Informatics. Volume 28, 2009, No. 2: 251-275.