Doctoral Dissertations

Date of Award

12-2009

Degree Type

Dissertation

Degree Name

Doctor of Philosophy

Major

Computer Science

Major Professor

Michael D. Vose

Committee Members

Bruce MacLennan, Mongi Abidi, Sergey Gavrilets

Abstract

Many of the most challenging problems in modern science lie at the interface of several fields. To study these problems, there is a pressing need for trans-disciplinary research incorporating computational and mathematical models. This dissertation presents a selection of new computational and mathematical techniques applied to biological simulations and problem solving: (i) The dynamics of alliance formation in primates are studied using a continuous time individual-based model. It is observed that increasing the cognitive abilities of individuals stabilizes alliances in a phase transition-like manner. Moreover, with strong cultural transmission an egalitarian regime is established in a few generations. (ii) A putative case of hybrid speciation in three species of Heliconius butterflies is studied using a spatial, genetically explicit, individual-based simulation. Given the ecological and selective pressures observed, the hybrid origin of Heliconius heurippa is supported by the model. However, the coexistence of the parental species and the hybrid species is only transient in the simulation. (iii) Optimization and computational techniques were developed during the implementation of a model of adaptive radiation in Anolis lizards. An efficient and accurate numerical integration routine was developed and a parallel implementation was ran on Kraken, Cray’s XT5 supercomputer. These procedures improved the simulation’s running time by several orders of magnitude. (iv) Optimizations, both in execution time and memory usage, are proposed for some genetic operators extensively used in evolutionary algorithms and biological simulations. Speed-up ranging from two-fold to several orders of magnitude is achieved. A statistical analysis was conducted to ensure the reliability of the methods. (v) No-Free-Lunch (NFL) theorems are theoretical results concerning the performance of heuristic optimization algorithms. The characterization of function sets for which the Focused NFL theorem holds is shown. A generalization of NFL results to random algorithms is proven, as well as a new NFL theorem for random algorithms over arbitrary benchmarks.

dissertation.tex (32 kB)
Source TeX file of main document

cug.tex (26 kB)
Source TeX file of Chapter 4

allies.tex (34 kB)
Source TeX file of Chapter 2

allies_SI2.tex (35 kB)
Source TeX file of Chapter 2 (sup. info.)

approval.tex (1 kB)
Source TeX file of the approval sheet

coal.bib (32 kB)
Source TeX file of coalitions bibliography

ecol_spec.bib (26 kB)
Source TeX file of ecological speciation bibliography

genetics.tex (33 kB)
Source TeX file of Chapter 5

heli.bib (17 kB)
Source TeX file of Heliconius bibliography

hybrids.tex (81 kB)
Source TeX file of Chapter 3

kniga.bib (180 kB)
Source TeX file of miscellaneous bibliography

mach.bib (11 kB)
Source TeX file of Machiavellian intelligence bibliography

nfl.bib (13 kB)
Source TeX file of No-free-lunch and operators bibliography

sniche.bib (23 kB)
Source TeX file of niche bibliography

Figures.zip (4904 kB)
Figures

Files over 3MB may be slow to open. For best results, right-click and select "save as..."

Share

COinS