Fundamenta Informaticae - Volume 119, issue 1

Authors: Riff, Maria Cristina

Article Type: Other

DOI: 10.3233/FI-2012-724

Citation: Fundamenta Informaticae, vol. 119, no. 1, pp. i-ii, 2012

Authors: Dorzán, Maria Gisela | Gagliardi, Edilma Olinda | Leguizamón, Mario Guillermo | Hernández Peñalver, Gregorio

Article Type: Research Article

Abstract: Globally optimal triangulations and pseudo-triangulations are difficult to be found by deterministic methods as, for most type of criteria, no polynomial algorithm is known. In this work, we consider the Minimum Weight Triangulation (MWT) and Minimum Weight Pseudo-Triangulation (MWPT) problems of a given set of n points in the plane. This paper shows how the Ant Colony Optimization (ACO) metaheuristic can be used to find high quality triangulations and pseudo-triangulations of minimum weight. For the experimental study presented here we have created a set of instances for MWT and MWPT problems since no reference to benchmarks for these problems were …found in the literature. Through the experimental evaluation, we assess the applicability of the ACO metaheuristic for MWT and MWPT problems considering greedy and Simulated Annealing algorithms. Show more

Keywords: Triangulation, Pseudo-Triangulation, Minimum Weight, Computational Geometry, ACO Metaheuristic

DOI: 10.3233/FI-2012-725

Citation: Fundamenta Informaticae, vol. 119, no. 1, pp. 1-27, 2012

Authors: Garrido, Pablo | Castro, Carlos

Article Type: Research Article

Abstract: We present a self-adaptive hyper-heuristic capable of solving static and dynamic instances of the capacitated vehicle routing problem. The hyper-heuristic manages a generic sequence of constructive and perturbative low-level heuristics, which are gradually applied to construct or improve partial routes. We present some design considerations to allow the collaboration among heuristics, and to find the most promising sequence. The search process is carried out by applying a set of operators which constructs new sequences of heuristics, i.e., solving strategies. We have used a general and low-computational cost parameter control strategy, based on simple reinforcement learning ideas, to assign non-arbitrary reward/penalty …values and guide the selection of operators. Our approach has been tested using some standard state-of-the-art benchmarks, which present different topologies and dynamic properties, and we have compared it with previous hyper-heuristics and several well-known methods proposed in the literature. The experimental results have shown that our approach is able to attain quite stable and good quality solutions after solving various problems, and to adapt to dynamic scenarios more naturally than other methods. Particularly, in the dynamic case we have obtained high-quality solutions when compared with other algorithms in the literature. Thus, we conclude that our self-adaptive hyper-heuristic is an interesting approach for solving vehicle routing problems as it has been able (1) to guide the search for appropriate operators, and (2) to adapt itself to particular states of the problem by choosing a suitable combination of heuristics. Show more

Keywords: Hyper-heuristics, Heuristic Search, Vehicle Routing Problems, Metaheuristics, Parameter Control, Reinforcement Learning

DOI: 10.3233/FI-2012-726

Citation: Fundamenta Informaticae, vol. 119, no. 1, pp. 29-60, 2012

Authors: Hristea, Florentina | Colhon, Mihaela

Article Type: Research Article

Abstract: The present paper concentrates on the issue of feature selection for unsupervised word sense disambiguation (WSD) performed with an underlying Naïve Bayes model. It introduces dependency-based feature selection which, to our knowledge, is used for the first time in conjunction with the Naïve Bayes model acting as clustering technique. Construction of the dependency-based semantic space required for the proposed task is discussed. The resulting disambiguation method, representing an extension of the method introduced in [15], lies at the border between unsupervised and knowledge-based techniques. Syntactic knowledge provided by dependency relations (and exemplified in the case of adjectives) is hereby compared …to semantic knowledge offered by the semantic network WordNet (and examined in [15]). Our conclusion is that the Naïve Bayes model reacts well in the presence of syntactic knowledge of this type and that dependency-based feature selection is a reliable alternative to the WordNet-based semantic one. Show more

Keywords: Unsupervised word sense disambiguation, Bayesian classification, The EM algorithm, WordNet, Dependency relations, Dependency-based feature selection

DOI: 10.3233/FI-2012-727

Citation: Fundamenta Informaticae, vol. 119, no. 1, pp. 61-86, 2012

Authors: Hummel, Szczepan | Skrzypczak, Michał

Article Type: Research Article

Abstract: This work shows that for each i ∈ ω there exists a $\Sigma ^1_i$-hard ω-word language definable in Monadic Second Order Logic extended with the unbounding quantifier (MSO+U). This quantifier was introduced by Bojańczyk to express some asymptotic properties. Since it is not hard to see that each language expressible in MSO+U is projective, our finding solves the topological complexity of MSO+U. The result can immediately be transferred from ω-words to infinite labelled trees. As a consequence of the topological hardness we note that no alternating automaton with a Borel acceptance condition — or even with an acceptance condition of …a bounded projective complexity — can capture all of MSO+U. The same holds for deterministic and nondeterministic automata since they are special cases of alternating ones. We also give exact topological complexities of related classes of languages recognized by nondeterministic ωB-, ωS- and ωBS-automata studied by Bojańczyk and Colcombet. Furthermore, we show that corresponding alternating automata have higher topological complexity than nondeterministic ones — they inhabit all finite levels of the Borel hierarchy. The paper is an extended journal version of [8]. The main theorem of that article is strengthened here. Show more

Keywords: MSO+U, ωBS-automata, topological complexity, projective hierarchy, Borel hierarchy

DOI: 10.3233/FI-2012-728

Citation: Fundamenta Informaticae, vol. 119, no. 1, pp. 87-111, 2012

Authors: Schaefer, Gerald | Hu, Qinghua | Zhou, Huiyu | Peters, James F. | Hassanien, Aboul Ella

Article Type: Research Article

Abstract: Colour quantisation algorithms are essential for displaying true colour images using a limited palette of distinct colours. The choice of a good colour palette is crucial as it directly determines the quality of the resulting image. Colour quantisation can also be seen as a clustering problem where the task is to identify those clusters that best represent the colours in an image. In this paper we propose rough c-means and fuzzy rough c-means clustering algorithms for colour quantisation of images. Both approaches utilise the concept of lower and upper approximations of clusters to define palette colours. While in the rough …c-means approach cluster centroids are refined iteratively through a linear combination of elements of the lower and upper approximations, the fuzzy rough c-means technique assigns variable membership values to the elements in the boundary region which in turn are incorporated into the calculation of cluster centres. Experimental results on a standard set of images show that these approaches performs significantly better than other, purpose built colour quantisation algorithms. Show more

Keywords: colour quantisation, clustering, rough c-means

DOI: 10.3233/FI-2012-729

Citation: Fundamenta Informaticae, vol. 119, no. 1, pp. 113-120, 2012