Evolutionary computation of forests with Degree- and Role-Constrained Minimum Spanning Trees

Finding the degree-constrained minimum spanning tree (DCMST) of a graph is a widely studied NP-hard problem. One of its most important applications is network design. Here we deal with a new variant of the DCMST problem, which consists of finding not only the degree- but also the role-constrained minimum spanning tree (DRCMST), i.e., we add constraints to restrict the role of the nodes in the tree to root, intermediate or leaf node. Furthermore, we do not limit the number of root nodes to one, thereby, generally, building a forest of DRCMSTs. The modeling of network design problems can benefit from the possibility of generating more than one tree and determining the role of the nodes in the network. We propose a novel permutation-based representation to encode these forests. In this new representation, one permutation simultaneously encodes all the trees to be built. We simulate a wide variety of DRCMST problems which we optimize using eight different evolutionary computation algorithms encoding individuals of the population using the proposed representation. The algorithms we use are: estimation of distribution algorithm, generational genetic algorithm, steady-state genetic algorithm, covariance matrix adaptation evolution strategy, differential evolution, elitist evolution strategy, non-elitist evolution strategy and particle swarm optimization. The best results are for the estimation of distribution algorithms and both types of genetic algorithms, although the genetic algorithms are significantly faster.

Computación evolutiva de bosques de expansión mínimos con restricción de grado y de rol

Encontrar el árbol de expansión mínimo con restricción de grado de un grafo (DCMST por sus siglas en inglés) es un problema NP-complejo ampliamente estudiado. Una de sus aplicaciones más importantes es el dise~no de redes. Aquí nosotros tratamos una nueva variante del problema DCMST, que consiste en encontrar el árbol de expansión mínimo no solo con restricciones de grado, sino también con restricciones de rol (DRCMST), es decir, a~nadimos restricciones para restringir el rol que los nodos tienen en el árbol. Estos roles pueden ser nodo raíz, nodo intermedio o nodo hoja. Por otra parte, no limitamos el número de nodos raíz a uno, por lo que, en general, construiremos bosques de DRCMSTs. El modelado en los problemas de dise~no de redes puede beneficiarse de la posibilidad de generar más de un árbol y determinar el rol de los nodos en la red. Proponemos una nueva representación basada en permutaciones para codificar los bosques de DRCMSTs. En esta nueva representación, una permutación codifica simultáneamente todos los árboles que se construirán. Nosotros simulamos una amplia variedad de problemas DRCMST que optimizamos utilizando ocho algoritmos de computación evolutiva diferentes que codifican los individuos de la población utilizando la representación propuesta. Los algoritmos que utilizamos son: algoritmo de estimación de distribuciones (EDA), algoritmo genético generacional (gGA), algoritmo genético de estado estacionario (ssGA), estrategia evolutiva basada en la matriz de covarianzas (CMAES), evolución diferencial (DE), estrategia evolutiva elitista (ElitistES), estrategia evolutiva no elitista (NonElitistES) y optimización por enjambre de partículas (PSO). Los mejores resultados fueron para el algoritmo de estimación de distribuciones utilizado y ambos tipos de algoritmos genéticos, aunque los algoritmos genéticos fueron significativamente más rápidos.---ABSTRACT---Finding the degree-constrained minimum spanning tree (DCMST) of a graph is a widely studied NP-hard problem. One of its most important applications is network design. Here we deal with a new variant of the DCMST problem, which consists of finding not only the degree- but also the role-constrained minimum spanning tree (DRCMST), i.e., we add constraints to restrict the role of the nodes in the tree to root, intermediate or leaf node. Furthermore, we do not limit the number of root nodes to one, thereby, generally, building a forest of DRCMSTs. The modeling of network design problems can benefit from the possibility of generating more than one tree and determining the role of the nodes in the network. We propose a novel permutation-based representation to encode the forest of DRCMSTs. In this new representation, one permutation simultaneously encodes all the trees to be built. We simulate a wide variety of DRCMST problems which we optimize using eight diferent evolutionary computation algorithms encoding individuals of the population using the proposed representation. The algorithms we use are: estimation of distribution algorithm (EDA), generational genetic algorithm (gGA), steady-state genetic algorithm (ssGA), covariance matrix adaptation evolution strategy (CMAES), diferential evolution (DE), elitist evolution strategy (ElististES), non-elitist evolution strategy (NonElististES) and particle swarm optimization (PSO). The best results are for the estimation of distribution algorithm and both types of genetic algorithms, although the genetic algorithms are significantly faster. iv

Using ecological niche models to support tree species selection for forest restoration planning in largely deforested regions

Species selection for forest restoration is often supported by expert knowledge on local distribution patterns of native tree species. This approach is not applicable to largely deforested regions unless enough data on pre-human tree species distribution is available. In such regions, ecological niche models may provide essential information to support species selection in the framework of forest restoration planning. In this study we used ecological niche models to predict habitat suitability for native tree species in "Tierra de Campos" region, an almost totally deforested area of the Duero Basin (Spain). Previously available models provide habitat suitability predictions for dominant native tree species, but including non-dominant tree species in the forest restoration planning may be desirable to promote biodiversity, specially in largely deforested areas were near seed sources are not expected. We used the Forest Map of Spain as species occurrence data source to maximize the number of modeled tree species. Penalized logistic regression was used to train models using climate and lithological predictors. Using model predictions a set of tools were developed to support species selection in forest restoration planning. Model predictions were used to build ordered lists of suitable species for each cell of the study area. The suitable species lists were summarized drawing maps that showed the two most suitable species for each cell. Additionally, potential distribution maps of the suitable species for the study area were drawn. For a scenario with two dominant species, the models predicted a mixed forest (Quercus ilex and a coniferous tree species) for almost one half of the study area. According to the models, 22 non-dominant native tree species are suitable for the study area, with up to six suitable species per cell. The model predictions pointed to Crataegus monogyna, Juniperus communis, J.oxycedrus and J.phoenicea as the most suitable non-dominant native tree species in the study area. Our results encourage further use of ecological niche models for forest restoration planning in largely deforested regions.

DNA methylation and adaptive response in forest tree species

Progressive increase of temperatures as well as longer seasonal drought periods revealed by climate studies correspond to fast environmental changes that forest species face with their actual genetic background. Natural selective processes cannot develop an adaptive response within this time frame. Thus the capability of forest tree species to adapt to the new environments will depend on their genetic background, but also rely on their phenotypic plasticity. Several reports have shown the involvement of epigenetic modifiers as the basis of the phenotypic plasticity, and in particular to the adaptation to abiotic stresses. DNA methylation (methylation of cytosine residues)is one the most important epigenetic modification in eukaryotes. Itis involved in specific biological processes such as gene transcription regulation, gene silencing, mobile element control or genome imprinting.Therefore, there is a great interest in analyzing cytosine methylation levels and distribution within the genome

Is it appropriate protective figure "Plant Micro-Reserves" to protect tree species? The example of Betula pendula subsp. fontqueri in "La Garganta de los Caballeros" (Ávila)

The figure of protection "micro-reserves" was created in the Region of Valencia (ANONYMOUS, 1994) with the aim of protecting endangered plant species. This is one of the areas of greatest floristic richness and uniqueness of the western Mediterranean. In this area rare, endemic or threatened vascular flora has a peculiar distribution: they appear to form small fragments spread over the entire region (LAGUNA, 1994; LAGUNA, 2001) The protection of every these small populations of great scientific value has significant challenges. It doesn´t try to protect every species that set out in Annex IV of the by then existing Law 4 / 1989 (repealed in 2007), or to protect to the most ecological level with the creation of Natural Protected Area but an intermediate level: the plant community of small size. According to the decree: “as Micro-Reserve will be declared the natural parcels of land under 20 hectares that contain a high concentration of rare plants, endemic, threatened or of high scientific interest” (ANONYMOUS, 1994) . Of course, the statement of an area as micro-reserve carries certain prohibitions that are harmful to the vegetal community

Plant regeneration from an endangered valuable cork oak tree by somatic embryogenesis.

Among the several applications of in vitro tissue culture techniques, the conservation of plant germplasm is one of the most widely used. The cork oak is one of the principal tree species in the Western Mediterranean región. Within this área, the Balearic Islands are considered to be a glacial refuge, and therefore a reservoir of genetic resources. A singular tree has been found in the small Minorca Island population. The haplotype of this tree is of Tyrrhenian origin, showing a past link between Minorca and Sardinia. Moreover, this tree do not bear a deletion within an ITS from ribosimic nuclear DNA, which is fairly common in many populations of this species, and indicates that ir may be the descendant of a very ancient population. This tree is currently in a precarious condition, and it has not produced acorns in the last years. Hence there is a clear need of vegetative propagation to conserve this genotype. We have previously developed methods to clone adult cork oak tres by somatic embryogenesis, and therefore the aim of the present work was to clone this singular tree. There braches from the corwn were collected in November 2004, and methods previously described were carried out. By February 2005 somatic embryogenesis was obtained from leaves of the tree with percentages on induction ranging from 17 to 54% depending on the branch, which may show a novel source of variation that requires further study. Spontaneously matured somatic embryos germinated at 46% in average, and the first somatic seedlings from the Alfavaret's cork oak tree were obtained. Therefore, this study shows one of the most relevant applications of somatic embryogenesis: the plant regeneration of valuable genotypes for the in situ and ex situ conservation of forest genetic resources.

Genetic diversity and relationships in accessions from different cultivar groups and origins in the tree tomato (Solanum betaceum Cav.)

Abstract Tree tomato (Solanum betaceum) is an Andean small tree cultivated for its juicy fruits. Little information is available on the characterization of genetic resources and breeding of this neglected crop. We have studied the molecular diversity with AFLP markers using 11 combinations of primers of a collection of 25 S. betaceum accessions belonging to four cultivar groups, most of which had been previously morphologically characterized, as well as one accession of the wild relative S. cajanumense.Atotal of 197 AFLP fragments were scored, of which 84 (43 %) were polymorphic. When excluding S. cajanumense from the analysis, the number of polymorphic AFLP fragments was 78 (40 %). Unique AFLP fingerprints were obtained for every accession, but no AFLP fragments specific and universal to any of the four cultivar groups were found. The total genetic diversity (HT) of cultivated accessions was HT = 0.2904, while for cultivar groups it ranged from HT = 0.1846 in the orange group to HT = 0.2498 in the orange pointed group. Genetic differentiation among cultivar groups (GST) was low (GST = 0.2248), which was matched by low values of genetic distance among cultivar groups. The diversity of collections from Ecuador, which we hypothesize is a center of diversity for tree tomato, was similar to that from other origins (HT = 0.2884 and HT = 0.2645, respectively). Cluster and PCoA analyses clearly separated wild S. cajanumense from the cultivated species. However, materials of different cultivar groups and origins were intermingled in both analyses. The Mantel test correlation coefficient of the matrices of morphological and AFLP distances was low (-0.024) and non-significant. Overall, the results show that a wide diversity is present in each of the cultivar groups, indicate that Ecuador may be regarded as a center of accumulation of diversity for this crop, and confirm that AFLP and morphological characterization data are complementary. The results obtained are of value for the conservation of genetic resources and breeding of tree tomato, as an assessment of the genetic diversity and relationships among differen

Extreme pointer years in tree-ring records of central Spain as evidence of climatic events and the eruption of the Huaynaputina Volcano (Peru, 1600 AD)

The study of pointer years of numerous tree-ring chronologies of the central Iberian Peninsula (Sierra de Guadarrama) could provide complementary information about climate variability over the last 405 yr. In total, 64 pointer years have been identified: 30 negative (representing minimum growths) and 34 positive (representing maximum growths), the most significant of these being 1601, 1963 and 1996 for the negative ones, and 1734 and 1737 for the positive ones. Given that summer precipitation was found to be the most limiting factor for the growth of Pinus in the Sierra de Guadarrama in the second half of the 20th century, it is also an explanatory factor in almost 50% of the extreme growths. Furthermore, these pointer years and intervals are not evenly distributed throughout time. Both in the first half of the 17th and in the second half of 20th, they were more frequent and more extreme and these periods are the most notable for the frequency of negative pointer years in Central Spain. The interval 1600–1602 is of special significance, being one of the most unfavourable for tree growth in the centre of Spain, with 1601 representing the minimum index in the regional chronology. We infer that this special minimum annual increase was the effect of the eruption of Huaynaputina, which occurred in Peru at the beginning of 1600 AD. This is the first time that the effects of this eruption in the tree-ring records of Southern Europe have been demonstrated.

Tree height integrated into pantropical forest biomass estimates

Aboveground tropical tree biomass and carbon storage estimates commonly ignore tree height (H). We estimate the effect of incorporating H on tropics-wide forest biomass estimates in 327 plots across four continents using 42 656 H and diameter measurements and harvested trees from 20 sites to answer the following questions: 1. What is the best H-model form and geographic unit to include in biomass models to minimise site-level uncertainty in estimates of destructive biomass? 2. To what extent does including H estimates derived in (1) reduce uncertainty in biomass estimates across all 327 plots? 3. What effect does accounting for H have on plot- and continental-scale forest biomass estimates? The mean relative error in biomass estimates of destructively harvested trees when including H (mean 0.06), was half that when excluding H (mean 0.13). Power- andWeibull-H models provided the greatest reduction in uncertainty, with regional Weibull-H models preferred because they reduce uncertainty in smaller-diameter classes (?40 cm D) that store about one-third of biomass per hectare in most forests. Propagating the relationships from destructively harvested tree biomass to each of the 327 plots from across the tropics shows that including H reduces errors from 41.8Mgha?1 (range 6.6 to 112.4) to 8.0Mgha?1 (?2.5 to 23.0). For all plots, aboveground live biomass was ?52.2 Mgha?1 (?82.0 to ?20.3 bootstrapped 95%CI), or 13%, lower when including H estimates, with the greatest relative reductions in estimated biomass in forests of the Brazilian Shield, east Africa, and Australia, and relatively little change in the Guiana Shield, central Africa and southeast Asia. Appreciably different stand structure was observed among regions across the tropical continents, with some storing significantly more biomass in small diameter stems, which affects selection of the best height models to reduce uncertainty and biomass reductions due to H. After accounting for variation in H, total biomass per hectare is greatest in Australia, the Guiana Shield, Asia, central and east Africa, and lowest in eastcentral Amazonia, W. Africa, W. Amazonia, and the Brazilian Shield (descending order). Thus, if tropical forests span 1668 million km2 and store 285 Pg C (estimate including H), then applying our regional relationships implies that carbon storage is overestimated by 35 PgC (31?39 bootstrapped 95%CI) if H is ignored, assuming that the sampled plots are an unbiased statistical representation of all tropical forest in terms of biomass and height factors. Our results show that tree H is an important allometric factor that needs to be included in future forest biomass estimates to reduce error in estimates of tropical carbon stocks and emissions due to deforestation.

Nonparametric generalized belief propagation based on pseudo-junction tree for cooperative localization in wireless networks

Non-parametric belief propagation (NBP) is a well-known message passing method for cooperative localization in wireless networks. However, due to the over-counting problem in the networks with loops, NBP’s convergence is not guaranteed, and its estimates are typically less accurate. One solution for this problem is non-parametric generalized belief propagation based on junction tree. However, this method is intractable in large-scale networks due to the high-complexity of the junction tree formation, and the high-dimensionality of the particles. Therefore, in this article, we propose the non-parametric generalized belief propagation based on pseudo-junction tree (NGBP-PJT). The main difference comparing with the standard method is the formation of pseudo-junction tree, which represents the approximated junction tree based on thin graph. In addition, in order to decrease the number of high-dimensional particles, we use more informative importance density function, and reduce the dimensionality of the messages. As by-product, we also propose NBP based on thin graph (NBP-TG), a cheaper variant of NBP, which runs on the same graph as NGBP-PJT. According to our simulation and experimental results, NGBP-PJT method outperforms NBP and NBP-TG in terms of accuracy, computational, and communication cost in reasonably sized networks.

Hybrid analysis of nonlinear circuits: DAE models with indices zero and one

We extend in this paper some previous results concerning the differential-algebraic index of hybrid models of electrical and electronic circuits. Specifically, we present a comprehensive index characterization which holds without passivity requirements, in contrast to previous approaches, and which applies to nonlinear circuits composed of uncoupled, one-port devices. The index conditions, which are stated in terms of the forest structure of certain digraph minors, do not depend on the specific tree chosen in the formulation of the hybrid equations. Additionally, we show how to include memristors in hybrid circuit models; in this direction, we extend the index analysis to circuits including active memristors, which have been recently used in the design of nonlinear oscillators and chaotic circuits. We also discuss the extension of these results to circuits with controlled sources, making our framework of interest in the analysis of circuits with transistors, amplifiers, and other multiterminal devices.

Prototype of EN 301 549 Decision tree

The new European Standard EN 301 549 “Accessibility requirements suitable for public procurement of ICT products and services in Europe” is the response by CEN, CENELEC and ETSI to the European Commission’s Mandate 376. Today, ICT products and services are converging, and the boundaries between product categories are being constantly blurred. For that reason EN 301 549 has been drafted using a feature-based approach, instead of being based on product categories. The result is a standard that can be applied to any ICT product and service, by identifying applicable requirements depending on the features of the ICT. This demonstration presents ongoing work at the research group CETTICO of the Technical University of Madrid. CETTICO is developing a workgroup-based support tool where teams of people can annotate the result of performing a conformity assessment of a given ICT product or service according to the requirements of the EN. One of the functions of the tool is creating evaluation projects. During that task the user defines the features of the corresponding ICT product or service by answering questions presented by the tool. As a result of this process, the tool will create a list of applicable requirements and recommendations.

Tree and grazing influence on herbaceous pasture diversity in the Dehesa agroforestry system

Mediterranean Dehesas are one of the European natural habitat types of Community interest (43/92/EEC Directive), associated to high diversity levels and producer of important goods and services. In this work, tree contribution and grazing influence over pasture alpha diversity in a Dehesa in Central Spain was studied. We analyzed Richness and Shannon-Wiener (SW) indexes on herbaceous layer under 16 holms oak trees (64 sampling units distributed in two directions and in two distances to the trunk) distributed in four different grazing management zones (depending on species and stocking rate). Floristic composition by species or morphospecies and species abundance were analyzed for each sample unit. Linear mixed models (LMM) and generalized linear mixed models (GLMMs) were used to study relationships between alpha diversity measures and independent factors. Edge crown influence showed the highest values of Richness and SW index. No significant differences were found between orientations under tree crown influence. Grazing management had a significant effect over Richness and SW measures, specially the grazing species (cattle or sheep). We preliminary quantify and analyze the interaction of tree stratum and grazing management over herbaceous diversity in a year of extreme climatic conditions.

Active Optical Sensors for Tree Stem Detection and Classification in Nurseries.

Active optical sensing (LIDAR and light curtain transmission) devices mounted on a mobile platform can correctly detect, localize, and classify trees. To conduct an evaluation and comparison of the different sensors, an optical encoder wheel was used for vehicle odometry and provided a measurement of the linear displacement of the prototype vehicle along a row of tree seedlings as a reference for each recorded sensor measurement. The field trials were conducted in a juvenile tree nursery with one-year-old grafted almond trees at Sierra Gold Nurseries, Yuba City, CA, United States. Through these tests and subsequent data processing, each sensor was individually evaluated to characterize their reliability, as well as their advantages and disadvantages for the proposed task. Test results indicated that 95.7% and 99.48% of the trees were successfully detected with the LIDAR and light curtain sensors, respectively. LIDAR correctly classified, between alive or dead tree states at a 93.75% success rate compared to 94.16% for the light curtain sensor. These results can help system designers select the most reliable sensor for the accurate detection and localization of each tree in a nursery, which might allow labor-intensive tasks, such as weeding, to be automated without damaging crops.

A contribution to the optimal numbering of tree structures

This paper develops an automatic procedure for the optimal numbering of members and nodes in tree structures. With it the stiffness matrix is optimally conditioned either if a direct solution algorithm or a frontal one is used to solve the system of equations. In spite of its effectiveness, the procedure is strikingly simple and so is the computer program shown below.