Browsing by Author "Henriques, Sofia Soares"
Now showing 1 - 2 of 2
Results Per Page
Sort Options
- Heuristics for the Black and White Travelling Salesman ProblemPublication . Henriques, Sofia Soares; Paias, Ana Maria Duarte Silva Alves, 1963-The Black and White Travelling Salesman Problem (BWTSP) constitutes a variant of the Travelling Salesman Problem (TSP). Similarly to the TSP, it is formally defined on a directed graph with a set of vertices V , a set of arcs A and each arc has an associated cost. Each vertex from V is coloured as either black or white, thus V can be partitioned into two subsets W and B, the former containing all white nodes in V and the latter containing all the black ones. The objective of the BWTSP is to determine the Hamiltonian circuit with minimal cost in the graph which satisfies two conditions: it must not contain more than Q white nodes between two consecutive black vertices, and the total length between two consecutive black vertices must not exceed a value L. The BWTSP has real-life applications in the design of telecommunication networks and in the scheduling of aircraft operations. In the computational complexity theory, the BWTSP is classified as an NP-hard problem. This motivates the development of heuristic methods in order to obtain feasible solutions with an associated value close to the global optimum within a reasonable amount of computational time. Our goal is to develop heuristics which can be applied on both symmetric and asymmetric instances of the BWTSP, so that these methods can be used to solve more real-life problems. Due to the additional constraints of the BWTSP in comparison to the classical TSP, determining an initial feasible solution for a given instance of the problem is not a simple task, specially when the values of both parameters Q and L are tight. Therefore, we propose three constructive heuristics for the BWTSP in this dissertation. An Iterated Local Search (ILS) algorithm was proposed as an improvement heuristic. In order to justify our choice of parameters for the algorithm, we compared the performance of the ILS considering different combinations of parameters. Furthermore, we studied in more detail the performance of the ILS we proposed and analysed the differences regarding the quality of the final solutions between symmetric and asymmetric instances.
- Phenotypic and genetic variation for competitive ability and their impact on long-term interactions between spider mitesPublication . Henriques, Sofia Soares; Godinho, Diogo Alexandre Prino Martins; Fragata, Inês Regina Lopes de Mendonça, 1985-Competition is a major driver of population dynamics and species coexistence. Indeed, it affects genetic diversity, either by decreasing it if there is strong niche segregation, reducing the fundamental niche of each species, or by maintaining it if there are strong trade-offs between intraspecific and interspecific competition. In turn, within population diversity is expected to affect the outcome of competition and, thus, the probability of species coexistence. However, empirical tests of how diversity affects competition and how evolving with competitors affects diversity are scarce. In this thesis, we aimed 1) to characterize the individual variation for intra- and interspecific competitive ability in a population of spider mites, 2) predict the impact of individual variation for competitive ability on coexistence with other species, and 3) observe how evolving with competitors affects genetic diversity. For this purpose, we characterized the competitive ability of 29 Tetranychus evansi’ inbred lines originated from one outbred population and used these estimates to predict, through theoretical models, the long-term interactions with Tetranychus urticae (i.e., the likelihood of coexistence). Then, we also conducted a full-sib/half-sib analysis in T. evansi populations that have evolved under heterogeneous conditions alone or in competition with T. urticae. We observed high phenotypic and genetic variation in intra- and interspecific competitive ability among the inbred lines. This individual variation translated into a plethora of possible outcomes ranging from coexistence to extinction of either competitor. Finally, we found significant values of additive genetic variance for competitive ability in populations that have evolved with competitors when exposed to competitive environments. Our results suggest that competitive ability may evolve, facilitating the persistence of populations in dynamic environments and altering the probability of coexistence with heterospecifics. However, evolving in competitive and noncompetitive environments may alter the amount of genetic diversity, having, consequently, an impact on ecological dynamics.