ContinuousMultimodal Global Optimization with Differential Evolution-Based Methods

Metaheuristic methods have become increasingly popular approaches in solving global optimization problems. From a practical viewpoint, it is often desirable to perform multimodal optimization which, enables the search of more than one optimal solution to the task at hand. Population-based metaheuristic methods offer a natural basis for multimodal optimization. The topic has received increasing interest especially in the evolutionary computation community. Several niching approaches have been suggested to allow multimodal optimization using evolutionary algorithms. Most global optimization approaches, including metaheuristics, contain global and local search phases. The requirement to locate several optima sets additional requirements for the design of algorithms to be effective in both respects in the context of multimodal optimization. In this thesis, several different multimodal optimization algorithms are studied in regard to how their implementation in the global and local search phases affect their performance in different problems. The study concentrates especially on variations of the Differential Evolution algorithm and their capabilities in multimodal optimization. To separate the global and local search search phases, three multimodal optimization algorithms are proposed, two of which hybridize the Differential Evolution with a local search method. As the theoretical background behind the operation of metaheuristics is not generally thoroughly understood, the research relies heavily on experimental studies in finding out the properties of different approaches. To achieve reliable experimental information, the experimental environment must be carefully chosen to contain appropriate and adequately varying problems. The available selection of multimodal test problems is, however, rather limited, and no general framework exists. As a part of this thesis, such a framework for generating tunable test functions for evaluating different methods of multimodal optimization experimentally is provided and used for testing the algorithms. The results demonstrate that an efficient local phase is essential for creating efficient multimodal optimization algorithms. Adding a suitable global phase has the potential to boost the performance significantly, but the weak local phase may invalidate the advantages gained from the global phase.

Avian Evolutionary Genomics: Studies of Ficedula Flycatchers

In this thesis, different genetic tools are used to investigate both natural variation and speciation in the Ficedula flycatcher system: pied (Ficedula hypoleuca) and collared (F. albicollis) flycatchers. The molecular evolution of a gene involved in postnatal body growth, GH, has shown high degree of conservation at the mature protein between birds and mammals, whereas the variation observed in its signal peptide seems to be adaptive in pied flycatcher (I & II). Speciation is the process by which reproductive barriers to gene flow evolve between populations, and understanding the mechanisms involved in pre- and post-zygotic isolation have been investigated in Ficedula flycatchers. The Z chromosome have been suggested to be the hotspot for genes involved in speciation, thus sequencing of 13 Z-linked coding genes from the two species in allopatry and sympatry have been conducted (III). Surprisingly, the majority of Z-linked genes seemed to be highly conserved, suggesting instead a potential involvement of regulatory regions. Previous studies have shown that genes involved in hybrid fitness, female preferences and male plumage colouration are sex-linked. Hence, three pigmentation genes have been investigated: MC1R, AGRP, and TYRP1. Of these three genes, TYRP1 was identified as a strong candidate to be associated with black-brown plumage variation in sympatric populations, and hence is a strong candidate for a gene contributing to pre-zygotic isolation (IV). In sympatric areas, where pied and collared flycatchers have overlapping breeding areas, hybridization sometimes occurs leading to the production of unfit hybrids. By using a proteomic approach a novel expression pattern in hybrids was revealed compared to the parental species (V) and differentially expressed proteins subsequently identified by sequence similarity (VI). In conclusion, the Z chromosome appears to play an important role in flycatcher speciation, but probably not at the coding level. In addition the novel expression patterns might give new insights into the maladaptive hybrids.

Increasing the efficiency of disparity computation by interpolation

Tässä diplomityössä tutkitaan dispariteettikartan laskennan tehostamista interpoloimalla. Kolmiomittausta käyttämällä stereokuvasta muodostetaan ensin harva dispariteettikartta, jonka jälkeen koko kuvan kattava dispariteettikartta muodostetaan interpoloimalla. Kolmiomittausta varten täytyy tietää samaa reaalimaailman pistettä vastaavat kuvapisteet molemmissa kameroissa. Huolimatta siitä, että vastaavien pisteiden hakualue voidaan pienentää kahdesta ulottuvuudesta yhteen ulottuvuuteen käyttämällä esimerkiksi epipolaarista geometriaa, on laskennallisesti tehokkaampaa määrittää osa dispariteetikartasta interpoloimalla, kuin etsiä vastaavia kuvapisteitä stereokuvista. Myöskin johtuen stereonäköjärjestelmän kameroiden välisestä etäisyydestä, kaikki kuvien pisteet eivät löydy toisesta kuvasta. Näin ollen on mahdotonta määrittää koko kuvan kattavaa dispariteettikartaa pelkästään vastaavista pisteistä. Vastaavien pisteiden etsimiseen tässä työssä käytetään dynaamista ohjelmointia sekä korrelaatiomenetelmää. Reaalimaailman pinnat ovat yleisesti ottaen jatkuvia, joten geometrisessä mielessä on perusteltua approksimoida kuvien esittämiä pintoja interpoloimalla. On myöskin olemassa tieteellistä näyttöä, jonkamukaan ihmisen stereonäkö interpoloi objektien pintoja.

Ranking-Dominance Relation for (Evolutionary) Multi-Objective Optimization

An alternative relation to Pareto-dominance relation is proposed. The new relation is based on ranking a set of solutions according to each separate objective and an aggregation function to calculate a scalar fitness value for each solution. The relation is called as ranking-dominance and it tries to tackle the curse of dimensionality commonly observedin evolutionary multi-objective optimization. Ranking-dominance can beused to sort a set of solutions even for a large number of objectives when Pareto-dominance relation cannot distinguish solutions from one another anymore. This permits search to advance even with a large number of objectives. It is also shown that ranking-dominance does not violate Pareto-dominance. Results indicate that selection based on ranking-dominance is able to advance search towards the Pareto-front in some cases, where selection based on Pareto-dominance stagnates. However, in some cases it is also possible that search does not proceed into direction of Pareto-front because the ranking-dominance relation permits deterioration of individual objectives. Results also show that when the number of objectives increases, selection based on just Pareto-dominance without diversity maintenance is able to advance search better than with diversity maintenance. Therefore, diversity maintenance is connive at the curse of dimensionality.

Data-parallel computation in parallel and distributed environments

The past few decades have seen a considerable increase in the number of parallel and distributed systems. With the development of more complex applications, the need for more powerful systems has emerged and various parallel and distributed environments have been designed and implemented. Each of the environments, including hardware and software, has unique strengths and weaknesses. There is no single parallel environment that can be identified as the best environment for all applications with respect to hardware and software properties. The main goal of this thesis is to provide a novel way of performing data-parallel computation in parallel and distributed environments by utilizing the best characteristics of difference aspects of parallel computing. For the purpose of this thesis, three aspects of parallel computing were identified and studied. First, three parallel environments (shared memory, distributed memory, and a network of workstations) are evaluated to quantify theirsuitability for different parallel applications. Due to the parallel and distributed nature of the environments, networks connecting the processors in these environments were investigated with respect to their performance characteristics. Second, scheduling algorithms are studied in order to make them more efficient and effective. A concept of application-specific information scheduling is introduced. The application- specific information is data about the workload extractedfrom an application, which is provided to a scheduling algorithm. Three scheduling algorithms are enhanced to utilize the application-specific information to further refine their scheduling properties. A more accurate description of the workload is especially important in cases where the workunits are heterogeneous and the parallel environment is heterogeneous and/or non-dedicated. The results obtained show that the additional information regarding the workload has a positive impact on the performance of applications. Third, a programming paradigm for networks of symmetric multiprocessor (SMP) workstations is introduced. The MPIT programming paradigm incorporates the Message Passing Interface (MPI) with threads to provide a methodology to write parallel applications that efficiently utilize the available resources and minimize the overhead. The MPIT allows for communication and computation to overlap by deploying a dedicated thread for communication. Furthermore, the programming paradigm implements an application-specific scheduling algorithm. The scheduling algorithm is executed by the communication thread. Thus, the scheduling does not affect the execution of the parallel application. Performance results achieved from the MPIT show that considerable improvements over conventional MPI applications are achieved.

Evolutionary computing in search-based software engineering

This master’s thesis aims to study and represent from literature how evolutionary algorithms are used to solve different search and optimisation problems in the area of software engineering. Evolutionary algorithms are methods, which imitate the natural evolution process. An artificial evolution process evaluates fitness of each individual, which are solution candidates. The next population of candidate solutions is formed by using the good properties of the current population by applying different mutation and crossover operations. Different kinds of evolutionary algorithm applications related to software engineering were searched in the literature. Applications were classified and represented. Also the necessary basics about evolutionary algorithms were presented. It was concluded, that majority of evolutionary algorithm applications related to software engineering were about software design or testing. For example, there were applications about classifying software production data, project scheduling, static task scheduling related to parallel computing, allocating modules to subsystems, N-version programming, test data generation and generating an integration test order. Many applications were experimental testing rather than ready for real production use. There were also some Computer Aided Software Engineering tools based on evolutionary algorithms.

Evolutionary Ecology of Mountain Birch in Subarctic Stress Gradients: Interplay of Biotic and Abiotic Factors in Plant-Plant Interactions and Evolutionary Processes

In nature, variation for example in herbivory, wind exposure, moisture and pollution impact often creates variation in physiological stress and plant productivity. This variation is seldom clear-cut, but rather results in clines of decreasing growth and productivity towards the high-stress end. These clines of unidirectionally changing stress are generally known as ‘stress gradients’. Through its effect on plant performance, stress has the capacity to fundamentally alter the ecological relationships between individuals, and through variation in survival and reproduction it also causes evolutionary change, i.e. local adaptations to stress and eventually speciation. In certain conditions local adaptations to environmental stress have been documented in a matter of just a few generations. In plant-plant interactions, intensities of both negative interactions (competition) and positive ones (facilitation) are expected to vary along stress gradients. The stress-gradient hypothesis (SGH) suggests that net facilitation will be strongest in conditions of high biotic and abiotic stress, while a more recent ‘humpback’ model predicts strongest net facilitation at intermediate levels of stress. Plant interactions on stress gradients, however, are affected by a multitude of confounding factors, making studies of facilitation-related theories challenging. Among these factors are plant ontogeny, spatial scale, and local adaptation to stress. The last of these has very rarely been included in facilitation studies, despite the potential co-occurrence of local adaptations and changes in net facilitation in stress gradients. Current theory would predict both competitive effects and facilitative responses to be weakest in populations locally adapted to withstand high abiotic stress. This thesis is based on six experiments, conducted both in greenhouses and in the field in Russia, Norway and Finland, with mountain birch (Betula pubescens subsp. czerepanovii) as the model species. The aims were to study potential local adaptations in multiple stress gradients (both natural and anthropogenic), changes in plant-plant interactions under conditions of varying stress (as predicted by SGH), potential mechanisms behind intraspecific facilitation, and factors confounding plant-plant facilitation, such as spatiotemporal, ontogenetic, and genetic differences. I found rapid evolutionary adaptations (occurring within a time-span of 60 to 70 years) towards heavy-metal resistance around two copper-nickel smelters, a phenomenon that has resulted in a trade-off of decreased performance in pristine conditions. Heavy-metal-adapted individuals had lowered nickel uptake, indicating a possible mechanism behind the detected resistance. Seedlings adapted to heavy-metal toxicity were not co-resistant to others forms of abiotic stress, but showed co-resistance to biotic stress by being consumed to a lesser extent by insect herbivores. Conversely, populations from conditions of high natural stress (wind, drought etc.) showed no local adaptations, despite much longer evolutionary time scales. Due to decreasing emissions, I was unable to test SGH in the pollution gradients. In natural stress gradients, however, plant performance was in accordance with SGH, with the strongest host-seedling facilitation found at the high-stress sites in two different stress gradients. Factors confounding this pattern included (1) plant size / ontogenetic status, with seedling-seedling interactions being competition dominated and host-seedling interactions potentially switching towards competition with seedling growth, and (2) spatial distance, with competition dominating at very short planting distances, and facilitation being strongest at a distance of circa ¼ benefactor height. I found no evidence for changes in facilitation with respect to the evolutionary histories of plant populations. Despite the support for SGH, it may be that the ‘humpback’ model is more relevant when the main stressor is resource-related, while what I studied were the effects of ‘non-resource’ stressors (i.e. heavy-metal pollution and wind). The results have potential practical applications: the utilisation of locally adapted seedlings and plant facilitation may increase the success of future restoration efforts in industrial barrens as well as in other wind-exposed sites. The findings also have implications with regard to the effects of global change in subarctic environments: the documented potential by mountain birch for rapid evolutionary change, together with the general lack of evolutionary ‘dead ends’, due to not (over)specialising to current natural conditions, increase the chances of this crucial forest-forming tree persisting even under the anticipated climate change.

The molecular mechanisms and evolutionary significance of plumage colour variation in pied flycatchers (Ficedula hypoleuca)

A common feature of natural populations is that individuals differ in morphology, physiologyand behavior (i.e .phenotype). A thorough understanding of the molecular mechanisms and evolutionary forces behind this phenotypic variation is a prerequisite for understanding evolution.This thesis examines the molecular mechanism and the roles of the different evolutionary forces in plumage colour variation in pied flycatchers (Ficedulahypoleuca). Malepied flycatchers exhibit marked variation in both pigmentary and structural plumage colourand the trait has repeatedly been suggested to be of adaptive significance. An examination of plumage colour variation on reproductive output trevealed that structural colouration, and more specifically the degree of ultraviolet (UV) reflectance had an effect on number of young sired. Paternity analyses of breeding males revealed that males that had been cuckolded by their social mate tended to be less UV reflectant than males that had not been cuckolded.Neither pigment-based norstructural colouration was found to affect the probability of siring young in other nests. Phenotypic differentiation was found to be markedly greater than differentiation at neutralgenetic markers across the pied flycatcher breeding range. Furthermore patterns of differentiationin phenotypes and selectively neutral genes were not uniform. Outlier tests searching for genomic footprints of selection revealed elevated levels of genetic divergence in a gene associated with feather development (and thus potentially structural colouration) and ultraviolet vision. Th eobserved differentiation in allelic frequencies was particularly pronounced in the Spanish piedflycatcher populations. Examining gene expression during feather development indicated that the TYRP1 gene (known to be involved in the production of black pigment) may be relevant in generating phenotypic variation in pied flycatcher plumage. Also, energy homeostasis related genesfeatured prominently among the genes found to be expressed in one extreme phenotype but not the other. This is of particular interest in light of what is known about the pleiotropy ofthe melanocortin system which underlies brown-black pigment production. The melanocortinsystem is also associated with energy homeostasis (among a number of other physiological functions) and thus the results could be pointing to the signalling function of brown-blackplumage. Plumage colour variation in pied flycatchers, both structural and pigmentary, can thus beconcluded to be exhibiting signals of non-neutral evolution. Structural colouration was found to play a role in sexual selection and putative signals of selection were further detected in acandidate gene for this trait. Evidence for non-neutral evolution of pigmentary colouration was also detected. These findings, together with the fact that preliminary evidence for an energy balance associated signalling function for plumage was found, present good starting points for further investigations into the meaning and mechanisms of plumage colour variation in piedflycatchers.

Optimizing Customer Energy Invoice Calculation with Parallel Computation

Diplomityön tarkoituksena on optimoida asiakkaiden sähkölaskun laskeminen hajautetun laskennan avulla. Älykkäiden etäluettavien energiamittareiden tullessa jokaiseen kotitalouteen, energiayhtiöt velvoitetaan laskemaan asiakkaiden sähkölaskut tuntiperusteiseen mittaustietoon perustuen. Kasvava tiedonmäärä lisää myös tarvittavien laskutehtävien määrää. Työssä arvioidaan vaihtoehtoja hajautetun laskennan toteuttamiseksi ja luodaan tarkempi katsaus pilvilaskennan mahdollisuuksiin. Lisäksi ajettiin simulaatioita, joiden avulla arvioitiin rinnakkaislaskennan ja peräkkäislaskennan eroja. Sähkölaskujen oikeinlaskemisen tueksi kehitettiin mittauspuu-algoritmi.

Incest aversion : the evolutionary roots of individual regulation

Den evolutionära förklaringen till den allmänt utbredda incestaversionen, dvs. motviljan för sex med nära släktingar, försöker besvara såväl frågan om varför incestaversionen gynnats i det naturliga urvalet som frågan om hur denna aversion regleras på individuell nivå. Eftersom inavlade barn har en försämrad biologisk duglighet än andra barn, medför kostnaderna av denna icke-optimala reproduktion ett selektionstryck mot inavel. I en serie studier visade vi att eftersom kvinnor i allmänhet satsar mer biologiska resurser på sina barn än vad män gör, känner kvinnor starkare incestaversion än män och eftersom det endast är fertila kvinnor som riskerar satsa resurser i en inavlad avkomma har även fertila kvinnor högre incestaversion än icke-fertila kvinnor. Vi visade också att de biologiska kostnaderna av inavel inte begränsas till enbart de individer som har incest. Eftersom alla våra biologiska släktingar sannolikt delar våra alleler speglar incestaversionen även de biologiska kostnader som incest mellan våra släktingar medför åt oss. Den psykologiska mekanism med vilken incestsituationer bedöms har hittills varit okänd. I våra studier testades teorin om självreflekterande empati. Enligt den teorin bedöms sådana situationer emotionellt genom att man själv föreställer sig ha sex med motsvarande släkting och känslan som väcks i denna process ger därefter emotionell information till bedömningen av andras incest. I tre delstudier fann vi att självreflektion var positivt associerat med styrkan av aversion gentemot andras incest, vilket stöder teorin om självreflekterande empati.

Achieving EU energy targets – Impacts of evolutionary and revolutionary transition paths on power systems

Ambitious energy targets set by EU put pressures to increase share of renewable electricity supply in this and next decades and therefore, some EU member countries have boosted increasing renewable energy generation capacity by implementing subsidy schemes on national level. In this study, two different change approaches to increase renewable energy supply and increase self-sufficiency of supply are assessed with respect to their impacts on power system, electricity market and electricity generation costs in Finland. It is obtained that the current electricity generation costs are high compared to opportunities of earnings from present-day investor’s perspective. In addition, the growth expectations of consumptions and the price forecasts do not stimulate investing in new generation capacity. Revolutionary transition path is driven by administrative and political interventions to achieve the energy targets. Evolutionary transition path is driven by market-based mechanisms, such as market itself and emission trading scheme. It is obtained in this study that in the revolutionary transition path operation of market-based mechanisms is distorted to some extent and it is likely that this path requires providing more public financial resources compared to evolutionary transition path. In the evolutionary transition path the energy targets are not achieved as quickly but market-based mechanisms function better and investment environment endures more stable compared to revolutionary transition path.