A knowledge-based evolution strategy for the multi-objective minimum spanning tree problem

A fast Knowledge-based Evolution Strategy, KES, for the multi-objective minimum spanning tree, is presented. The proposed algorithm is validated, for the bi-objective case, with an exhaustive search for small problems (4-10 nodes), and compared with a deterministic algorithm, EPDA and NSGA-II for larger problems (up to 100 nodes) using benchmark hard instances. Experimental results show that KES finds the true Pareto fronts for small instances of the problem and calculates good approximation Pareto sets for larger instances tested. It is shown that the fronts calculated by YES are superior to NSGA-II fronts and almost as good as those established by EPDA. KES is designed to be scalable to multi-objective problems and fast due to its small complexity.

A hybridised evolutionary algorithm for multi-criterion minimum spanning tree problems

A hybridised and Knowledge-based Evolutionary Algorithm (KEA) is applied to the multi-criterion minimum spanning tree problems. Hybridisation is used across its three phases. In the first phase a deterministic single objective optimization algorithm finds the extreme points of the Pareto front. In the second phase a K-best approach finds the first neighbours of the extreme points, which serve as an elitist parent population to an evolutionary algorithm in the third phase. A knowledge-based mutation operator is applied in each generation to reproduce individuals that are at least as good as the unique parent. The advantages of KEA over previous algorithms include its speed (making it applicable to large real-world problems), its scalability to more than two criteria, and its ability to find both the supported and unsupported optimal solutions.

A reconstructed Siberian High index since A. D. 1599 from Eurasian and North American tree rings

The long-term variability of the Siberian High, the dominant Northern Hemisphere anticyclone during winter, is largely unknown. To investigate how this feature varied prior to the instrumental record, we present a reconstruction of a Dec-Feb Siberian High (SH) index based on Eurasian and North American tree rings. Spanning 1599-1980, it provides information on SH variability over the past four centuries. A decline in the instrumental SH index since the late 1970s, related to Eurasian warming, is the most striking feature over the past four hundred years. It is associated with a highly significant (p < 0.0001) step change in 1989. Significant similar to 3-4 yr spectral peaks in the reconstruction fall within the range of variability of the East Asian winter monsoon (which has also declined recently) and lend further support to proposed relationships between these largescale features of the climate system.

Patterns of pollen and seed dispersal in a small, fragmented population of the wind-pollinated tree Araucaria angustifolia in southern Brazil

Paternity analysis based on eight microsatellite loci was used to investigate pollen and seed dispersal patterns of the dioecious wind- pollinated tree, Araucaria angustifolia. The study sites were a 5.4 ha isolated forest fragment and a small tree group situated 1.7 km away, located in Paran alpha State, Brazil. In the forest fragment, 121 males, 99 females, 66 seedlings and 92 juveniles were mapped and genotyped, together with 210 seeds. In the tree group, nine male and two female adults were mapped and genotyped, together with 20 seeds. Paternity analysis within the forest fragment indicated that at least 4% of the seeds, 3% of the seedlings and 7% of the juveniles were fertilized by pollen from trees in the adjacent group, and 6% of the seeds were fertilized by pollen from trees outside these stands. The average pollination distance within the forest fragment was 83 m; when the tree group was included the pollination distance was 2006m. The average number of effective pollen donors was estimated as 12.6. Mother- trees within the fragment could be assigned to all seedlings and juveniles, suggesting an absence of seed immigration. The distance of seedlings and juveniles from their assigned mother- trees ranged from 0.35 to 291m ( with an average of 83m). Significant spatial genetic structure among adult trees, seedlings, and juveniles was detected up to 50m, indicating seed dispersal over a short distance. The effective pollination neighborhood ranged from 0.4 to 3.3 ha. The results suggest that seed dispersal is restricted but that there is longdistance pollen dispersal between the forest fragment and the tree group; thus, the two stands of trees are not isolated.

Wiggle-match dating of tree-ring sequences

Given the non-monotonic form of the radiocarbon calibration curve, the precision of single C-14 dates on the calendar timescale will always be limited. One way around this limitation is through comparison of time-series, which should exhibit the same irregular patterning as the calibration curve. This approach can be employed most directly in the case of wood samples with many years growth present (but not able to be dated by dendrochronology), where the tree-ring series of unknown date can be compared against the similarly constructed C-14 calibration curve built from known-age wood. This process of curve-fitting has come to be called "wiggle-matching." In this paper, we look at the requirements for getting good precision by this method: sequence length, sampling frequency, and measurement precision. We also look at 3 case studies: one a piece of wood which has been independently dendrochronologically dated, and two others of unknown age relating to archaeological activity at Silchester, UK (Roman) and Miletos, Anatolia (relating to the volcanic eruption at Thera).

Competition in tree row agroforestry systems. 3. Soil water distribution and dynamics

The purpose of this study was to test the hypothesis that soil water content would vary spatially with distance from a tree row and that the effect would differ according to tree species. A field study was conducted on a kaolinitic Oxisol in the sub-humid highlands of western Kenya to compare soil water distribution and dynamics in a maize monoculture with that under maize (Zea mays L.) intercropped with a 3-year-old tree row of Grevillea robusta A. Cunn. Ex R. Br. (grevillea) and hedgerow of Senna spectabilis DC. (senna). Soil water content was measured at weekly intervals during one cropping season using a neutron probe. Measurements were made from 20 cm to a depth of 225 cm at distances of 75, 150, 300 and 525 cm from the tree rows. The amount of water stored was greater under the sole maize crop than the agroforestry systems, especially the grevillea-maize system. Stored soil water in the grevillea-maize system increased with increasing distance from the tree row but in the senna-maize system, it decreased between 75 and 300 cm from the hedgerow. Soil water content increased least and more slowly early in the season in the grevillea-maize system, and drying was also evident as the frequency of rain declined. Soil water content at the end of the cropping season was similar to that at the start of the season in the grevillea-maize system, but about 50 and 80 mm greater in the senna-maize and sole maize systems, respectively. The seasonal water balance showed there was 140 mm, of drainage from the sole maize system. A similar amount was lost from the agroforestry systems (about 160 mm in the grevillea-maize system and 145 mm in the senna-maize system) through drainage or tree uptake. The possible benefits of reduced soil evaporation and crop transpiration close to a tree row were not evident in the grevillea-maize system, but appeared to greatly compensate for water uptake losses in the senna-maize system. Grevillea, managed as a tree row, reduced stored soil water to a greater extent than senna, managed as a hedgerow.

Tree Inscriptions: restoring a lost facet of the Graeco-Roman epigraphic habit

This article for the first time considers all extant ancient evidence for the habit of carving inscriptions on tree trunks. It emerges a picture that bears remarkable resemblances to what is known from the habit of graffiti writing (with important addition to that latter field to be derived from the findings), for individual and technical texts.

Dynamic load balancing in parallel KD-tree k-means

One among the most influential and popular data mining methods is the k-Means algorithm for cluster analysis. Techniques for improving the efficiency of k-Means have been largely explored in two main directions. The amount of computation can be significantly reduced by adopting geometrical constraints and an efficient data structure, notably a multidimensional binary search tree (KD-Tree). These techniques allow to reduce the number of distance computations the algorithm performs at each iteration. A second direction is parallel processing, where data and computation loads are distributed over many processing nodes. However, little work has been done to provide a parallel formulation of the efficient sequential techniques based on KD-Trees. Such approaches are expected to have an irregular distribution of computation load and can suffer from load imbalance. This issue has so far limited the adoption of these efficient k-Means variants in parallel computing environments. In this work, we provide a parallel formulation of the KD-Tree based k-Means algorithm for distributed memory systems and address its load balancing issue. Three solutions have been developed and tested. Two approaches are based on a static partitioning of the data set and a third solution incorporates a dynamic load balancing policy.

Efficient tree construction for the multicast problem

A new heuristic for the Steiner Minimal Tree problem is presented here. The method described is based on the detection of particular sets of nodes in networks, the “Hot Spot” sets, which are used to obtain better approximations of the optimal solutions. An algorithm is also proposed which is capable of improving the solutions obtained by classical heuristics, by means of a stirring process of the nodes in solution trees. Classical heuristics and an enumerative method are used CIS comparison terms in the experimental analysis which demonstrates the goodness of the heuristic discussed in this paper.

Efficient tree construction for the multicast problem

A new heuristic for the Steiner minimal tree problem is presented. The method described is based on the detection of particular sets of nodes in networks, the “hot spot” sets, which are used to obtain better approximations of the optimal solutions. An algorithm is also proposed which is capable of improving the solutions obtained by classical heuristics, by means of a stirring process of the nodes in solution trees. Classical heuristics and an enumerative method are used as comparison terms in the experimental analysis which demonstrates the capability of the heuristic discussed