Multi-Objective Genetic Algorithms for the Single Allocation Hub Location Problem

Hub Location Problems play vital economic roles in transportation and telecommunication networks where goods or people must be efficiently transferred from an origin to a destination point whilst direct origin-destination links are impractical. This work investigates the single allocation hub location problem, and proposes a genetic algorithm (GA) approach for it. The effectiveness of using a single-objective criterion measure for the problem is first explored. Next, a multi-objective GA employing various fitness evaluation strategies such as Pareto ranking, sum of ranks, and weighted sum strategies is presented. The effectiveness of the multi-objective GA is shown by comparison with an Integer Programming strategy, the only other multi-objective approach found in the literature for this problem. Lastly, two new crossover operators are proposed and an empirical study is done using small to large problem instances of the Civil Aeronautics Board (CAB) and Australian Post (AP) data sets.

Perceived effectiveness of alternative programming : a case study /

The topic of this research was alternative programming in secondary public education. The purpose of this research was to explore the perceived effectiveness of two public secondary programs that are aJternative to mainstream or "regular" education. Two case study sites were used to research diverse ends of the aJtemative programming continuum. The first case study demonstrated a gifted program and the second demonstrated a behavioral program. Student needs were examined in terms of academic needs, emotional needs, career needs, and social needs. Research conducted in these sites examined how the students, teachers, onsite staff, and program administrators perceived that individual needs were met and unmet in these two programs. The study was qualitative and exploratory, using deductive and inductive research techniques. Similar themes of best practice that were identified in the case study sites aided in the development of a teaching and learning model. Four themes were identified as important within the case study sites. These themes included the commitment and motivation of teachers and the support of administration in the gifted program, and the importance of location and the flow of information and communication in the behavior program. Six themes emerged that were similar across the case study sites. These themes included the individual nature of programming, recognition of student achievement, the alternative program as a place of safety and community, importance of interpersonal capacity, priority of basic needs, and, finally, matching student capacity with program expectations. The model incorporates these themes and is designed as a resource for teachers, program administrators, parents, and policy makers of alternative educational programs.

Body size in the field cricket Gryllus integer (Orthoptera : Gryllidae) :heritability and male mating success

The influence of male body weight on the aggressive and mating behaviour of male Gryllus integer was studied under laboratory conditions. The relationship between adult age and weight was first determined; female weight increased and male weight decreased with age. Virgin males that had been isolated since the adult molt were paired for similar age and a difference in weight of greater than 200 mg. Paired males and a virgin female were observed in a glass arena for 24 minutes or until a mating occurred. Larger males mated significantly more often than smaller males. Larger males attacked more often, were more successful in aggressive encounters and had more contact with the female. Males that did not mate had lower rates of courtship and mounts than males that mated. Females in trials that did not result in a mating were signifcantly heavier than females in trials that resulted in a mating. Larger males that mated were significantly closer in weight to the weight of the female than larger males in trials that did not result in a mating. Larger males in trials that did not result in a mating had higher rates of aggressive stridulation than larger males that mated. Male weight is therefore important in mating success; fitness traits should theoretically show low genetic variability. However, significant heritability values were found for live weight, dry weight, head width, pronotum width and length, hind femur length and forewing length when estimated from the regression of offspring on mid-parent values, offspring and female and male values separately and full-sib correlations. The heritability of hind femur width was significant when estimated from the regression of offspring on male parent and from full-sib correlations. Heritability estimates of forewing length were significantly higher when estimated from the regression of offspring on female parent than when estimated from the regression of offspring on male parent. High phenotypic, genetic and environmental correlations were found between all pairs of traits. Data on male mating success and the heritability of fitness traits were discussed in terms of the maintenance of genetic variability.

Heritability of multiple mating by female field crickets, Gryllus integer (Orthoptera: Gryllidae)

The heritability of multiple mating in female Gryllus integer crickets was studied. Two preliminary experiments were conducted to determine when females first mate following the post-imaginal moult and to ascertain whether constant exposure to males affects female mating rate. Female Q. integer first mated at an average age of 3.6 days (S.D. = 2.3, Range = 0-8 days) . Exposing female crickets to courting males 24 hr daily did not significantly alter mating rates from those females in contact with males for only 5 hr per day. A heritability value of 0.690 ± 0.283 was calculated for multiple mating behavior in female Q. integer using a parent-offspring regression approach. Parental females mated between land 30 times (x 9.8, S . D. = 6. 6 ) and offspring matings ranged from 0 to 26 times (x 7 .3, S.D. = 3.4). Multiple mating is probably a sexually selected trait which functions as a mechanism of female choice and increases reproductive success through increased offspring production. Classical theory suggests that traits intimately related with fitness should exhibit negligible heritable variation. However, this study has shown that multiple mating, a trait closely linked with reproductive fitness, exhibits substantial heritability. These results are in concordance with a growing body of empirical evidence suggesting many fitness traits in natural populations demonstrate heritabilities far removed from zero. Various mechanisms which may maintain heritable variation for female multiple mating in wild, outbred Q. integer populations are discussed.

Mating behaviours of the field cricket (Gryllus integer) at different levels of male density

The reproductive behaviour of the field cricket, Gryllus integer, was systematically observed in indoor arenas to determine the extent of female Choice and male-male competition at different sex ratios representing two male densities (12:6 and 6:6). The costs and benefits to males and females in those two densities were analyzed according to the theory of the evolution o£ leks. Observations were conducted during the dark hours when most calling occurred since hourly rates of courtship song and mating did not fluctuate significantly over a 24 h period. Female mating rates were not significantly different between densities, therefore males at high densities were not advantaged because of increased female tendencies to mate when social stimulation was increased. Mean rates of acoustical signalling (calling and courtin"g) did not differ significantly between densities. Mean rates of fighting by males at the high density were significantly greater than those of males at the low density. Mating benefits associated with callin~courting and fighting were measured. Mating rates did not vary with rates of calling at either density. Calling was not a prerequisite to mating. Courtship song preceded all matings. There was a significant power fit between male mating and courting rates, and male mating and fighting rates at the low, but not at the high, density. Density differences in the benefits associated with increased courting and fighting may relate, in part, to greater economic defensibility and monopoly of females due to reduced male competition at the low density. Dominant males may be preferentially chosen by females or better able to monopolize mating opportunities than subordinate males. Three criteria were used to determine whether dominant males were preferentially chosen by females. The number of matings by males who won fights (within 30 min of mating) was significantly greater than the number of matings by males who were defeated in such fights. Mating rates did not vary significantly with rates of winning at either density. There was a significant power fit between male mating rates and the percentage of fights a male won (irrespective of his fighting-frequency) at the low density. The mean duration a male guarded the female after mating did not vary significantly between densities. There was a significant linear relationship between the duration a spermatophore was retained and the duration a male guarded the female after mating. Courtship song apparently stimulated spermatophore removal. Male guarding involved inter-male aggression and reduced courtship attempts by other males. Males at the high density received no apparent reproductive benefits associated with increased social stimulation. Conclusive evidence for preferential choice of males by females, using the criteria examined here, is lacking. Males at the lower density had fewer competitors and could monopolize females more effectively.

Sperm utilization patterns in Gryllus integer (orthoptera: gryllidae

Sperm competition is the competition for fertilizations between ejaculates, within a female, following multiple mating. There are four sperm utilization or precedence patterns: first male precedence, where the first male to mate fertilizes most of the eggs laid by a female; last male precedence, where the last male to mate fertilizes most of the eggs laid by a female; "all-or-none" pattern, where sperm from either male fertilizes all the eggs laid by a female but which male's sperm that is used is random; or sperm mixing, where sperm from each male is used equally in fertilizing eggs laid by a female. Intermediate utilization patterns are also possible. Sperm competition occurs in a wide variety of insect species as well as other animals. This study was undertaken to study sperm competition in the field cricket, Gryllus integer. Four experiments were conducted: a radiation and sterilization experiment, a diapause experiment, and 2 competition experiments. It was found that 7,000 rad of gamma radiation sterilized adult ~ integer males. There was no diapause in the laboratory in ~ integer eggs. In the first competition experiment, three groups of females were used: females mated with a normal male, then with a second normal male (NN group); females mated with a normal male, and then with a sterile male (NR group); and females mated with a sterile male, and then with a normal male (RN group). The results obtained from this experiment showed that the mean proportion of eggs hatched was significantly different between 3 groups of females, with the proportion hatched much greater in the NN group than in either the NR or RN groups. The pattern for the proportion of eggs hatched following a double mating most closely resembled a pattern expected if sperm mixing is occurring. Results obtained in the replicate competition experiment showed that the mean proportion of eggs hatched for the females in the NR group was significantly lower than the proportion hatched in the other two groups. This also supports a model of sperm mixing as a precedence pattern. Values calculated following Boorman and Parker (1976), for the proportion of eggs fertilized by the second male to mate following a double mating, were 0.57 in competition experiment 1 and 0.62 in the replicate. These values indicate that sperm mixing occurs in~ integer.

The effect of diet and parasite load on female phonotaxis in the Texas field cricket, Gryllus integer

Female crickets respond selectively to variations in species-specific male calling songs. This selectivity has been shown to be age-dependent; older females are less choosy. However, female quality should also affect female selectivity. The effect of female quality on mate choice was examined in Gryllus integer by comparing the phonotactic responses of females on different diets and with different parasite loads to various synthetic models of conspecific calling song. Test females were virgin, 11-14 days old, and had been maintained on one of five diets varying in protein and fat content. Phonotaxis was quantified using a non-compensating Kugel treadmill which generates vector scores incorporating the speed and direction of movement of each female. Test females were presented with four calling song models which differed in pulse rate, but were still within the natural range of the species for the experimental temperature. After testing, females were dissected and the number of gregarine parasites within the digestive tract counted. There were no significant effects of either diet or parasitism on female motivation to mate although the combined effects of these variables seem to have an effect with no apparent trend. Control females did not discriminate among song types, but there was a trend of female preferences for lower pulse rates which are closest to the mean pulse rate for the species. Heavily parasitized females did not discriminate among pulse rates altho~gh there was a similar trend of high vector scores for low pulse rates. Diet, however, affected selectivity with poorly-fed females showing significantly high vector scores for pulse rates near the species mean. Such findings raise interesting questions about energy allocation and costs and risks of phonotaxis and mate choice in acoustic Orthoptera. These results are discussed in terms of sexual selection and female mate choice.

The effect of gregarine parasite infections, age, and diet on calling song structure and mating behaviour in the Texas field cricket, Gryllus integer

In the past ten years, many researchers have focussed their attention on parasites regarding the role they may play in causing variations in male secondary sexual traits and subsequent effects on female choice. Male age has also been suggested to be an important factor in female choice if old age reflects superior genes. This study investigated the effects that gregarine gut parasites, age, and diet have on the calling and mating behaviour of the male Texas field cricket, Gryllus integer. Male calling songs were recorded in the laboratory using a Digital Signal Processing Network. The song parameters measured were: pulse rate, pulse width, burst duration, pulses per burst, interburst interval, and percent missing pulses. The effects of parasite load and age on the various calling song parameters was investigated in crickets that were fed two different diets varying in nutritional quality. None of the calling song parameters were affected by either parasite load or age in either diet grou p. Courtship behaviour was ob served and recorded using an Eventlog recorder on an IBM computer in the laboratory. Females mated equally with paras(tized and unparasitized males and with old and young males The total duration and proportion of time spent performing each of 9 courtship displays were recorded for males on each diet. Only one display was affected by parasite load. Highly parasitized males fed the nutritionally inferior diet juddered for a proportionately shorter time than males with low parasite loads. Also, older males performed juddering and shaking antennae proportionally longer and juddering and raising wings for longer durations than younger males. Males that successfully mated were observed for performance of 8 post-copulatory guarding behaviour displays. None of the guarding behaviours were affected by parasite load. However, one display was affected by age, with older males performing guard turning for shorter durations than younger males. Results are discuss,ed in terms of the influence of parasites and age on female choice.

The impact of integrated programming on student attitude and achievement in grade 9 academic mathematics and science

This research studioo the effect of integrated instruction in mathematics and~ science on student achievement in and attitude towards both mathematics and science. A group of grade 9 academic students received instruction in both science and mathematics in an integrated program specifically developed for the purposes of the research. This group was compared to a control group that had received science and mathematics instruction in a traditional, nonintegrated program. The findings showed that in all measures of attitude, there was no significant difference between the students who participated in the integrated science and mathematics program and those who participated in a traditional science and mathematics program. The findings also revealed that integration did improve achievement on some of the measures used. The performance on mathematics open-ended problem-solving tasks improved after participation in the integrated program, suggesting that the integrated students were better able to apply their understanding of mathematics in a real-life context. The performance on the final science exam was also improved for the integrated group. Improvement was not noted on the other measures, which included EQAO scores and laboratory practical tasks. These results raise the issue of the suitability of the instruments used to gauge both achievement and attitude. The accuracy and suitability of traditional measures of achievement are considered. It is argued that they should not necessarily be used as the measure of the value of integrated instruction in a science and mathematics classroom.

Winâ Foy : functional object-oriented programming language

This thesis will introduce a new strongly typed programming language utilizing Self types, named Win--*Foy, along with a suitable user interface designed specifically to highlight language features. The need for such a programming language is based on deficiencies found in programming languages that support both Self types and subtyping. Subtyping is a concept that is taken for granted by most software engineers programming in object-oriented languages. Subtyping supports subsumption but it does not support the inheritance of binary methods. Binary methods contain an argument of type Self, the same type as the object itself, in a contravariant position, i.e. as a parameter. There are several arguments in favour of introducing Self types into a programming language (11. This rationale led to the development of a relation that has become known as matching [4, 5). The matching relation does not support subsumption, however, it does support the inheritance of binary methods. Two forms of matching have been proposed (lJ. Specifically, these relations are known as higher-order matching and I-bound matching. Previous research on these relations indicates that the higher-order matching relation is both reflexive and transitive whereas the f-bound matching is reflexive but not transitive (7]. The higher-order matching relation provides significant flexibility regarding inheritance of methods that utilize or return values of the same type. This flexibility, in certain situations, can restrict the programmer from defining specific classes and methods which are based on constant values [21J. For this reason, the type This is used as a second reference to the type of the object that cannot, contrary to Self, be specialized in subclasses. F-bound matching allows a programmer to define a function that will work for all types of A', a subtype of an upper bound function of type A, with the result type being dependent on A'. The use of parametric polymorphism in f-bound matching provides a connection to subtyping in object-oriented languages. This thesis will contain two main sections. Firstly, significant details concerning deficiencies of the subtype relation and the need to introduce higher-order and f-bound matching relations into programming languages will be explored. Secondly, a new programming language named Win--*Foy Functional Object-Oriented Programming Language has been created, along with a suitable user interface, in order to facilitate experimentation by programmers regarding the matching relation. The construction of the programming language and the user interface will be explained in detail.

Genetic programming for the RoboCup Rescue Simulation System

The Robocup Rescue Simulation System (RCRSS) is a dynamic system of multi-agent interaction, simulating a large-scale urban disaster scenario. Teams of rescue agents are charged with the tasks of minimizing civilian casualties and infrastructure damage while competing against limitations on time, communication, and awareness. This thesis provides the first known attempt of applying Genetic Programming (GP) to the development of behaviours necessary to perform well in the RCRSS. Specifically, this thesis studies the suitability of GP to evolve the operational behaviours required of each type of rescue agent in the RCRSS. The system developed is evaluated in terms of the consistency with which expected solutions are the target of convergence as well as by comparison to previous competition results. The results indicate that GP is capable of converging to some forms of expected behaviour, but that additional evolution in strategizing behaviours must be performed in order to become competitive. An enhancement to the standard GP algorithm is proposed which is shown to simplify the initial search space allowing evolution to occur much quicker. In addition, two forms of population are employed and compared in terms of their apparent effects on the evolution of control structures for intelligent rescue agents. The first is a single population in which each individual is comprised of three distinct trees for the respective control of three types of agents, the second is a set of three co-evolving subpopulations one for each type of agent. Multiple populations of cooperating individuals appear to achieve higher proficiencies in training, but testing on unseen instances raises the issue of overfitting.

Automatic Structure Generation using Genetic Programming and Fractal Geometry

Three dimensional model design is a well-known and studied field, with numerous real-world applications. However, the manual construction of these models can often be time-consuming to the average user, despite the advantages o ffered through computational advances. This thesis presents an approach to the design of 3D structures using evolutionary computation and L-systems, which involves the automated production of such designs using a strict set of fitness functions. These functions focus on the geometric properties of the models produced, as well as their quantifiable aesthetic value - a topic which has not been widely investigated with respect to 3D models. New extensions to existing aesthetic measures are discussed and implemented in the presented system in order to produce designs which are visually pleasing. The system itself facilitates the construction of models requiring minimal user initialization and no user-based feedback throughout the evolutionary cycle. The genetic programming evolved models are shown to satisfy multiple criteria, conveying a relationship between their assigned aesthetic value and their perceived aesthetic value. Exploration into the applicability and e ffectiveness of a multi-objective approach to the problem is also presented, with a focus on both performance and visual results. Although subjective, these results o er insight into future applications and study in the fi eld of computational aesthetics and automated structure design.

A stochastic dynamic programming approach for pricing options on stock-index futures

The aim of this thesis is to price options on equity index futures with an application to standard options on S&P 500 futures traded on the Chicago Mercantile Exchange. Our methodology is based on stochastic dynamic programming, which can accommodate European as well as American options. The model accommodates dividends from the underlying asset. It also captures the optimal exercise strategy and the fair value of the option. This approach is an alternative to available numerical pricing methods such as binomial trees, finite differences, and ad-hoc numerical approximation techniques. Our numerical and empirical investigations demonstrate convergence, robustness, and efficiency. We use this methodology to value exchange-listed options. The European option premiums thus obtained are compared to Black's closed-form formula. They are accurate to four digits. The American option premiums also have a similar level of accuracy compared to premiums obtained using finite differences and binomial trees with a large number of time steps. The proposed model accounts for deterministic, seasonally varying dividend yield. In pricing futures options, we discover that what matters is the sum of the dividend yields over the life of the futures contract and not their distribution.

Genetic Programming for Non-Photorealistic Rendering

This thesis focuses on developing an evolutionary art system using genetic programming. The main goal is to produce new forms of evolutionary art that filter existing images into new non-photorealistic (NPR) styles, by obtaining images that look like traditional media such as watercolor or pencil, as well as brand new effects. The approach permits GP to generate creative forms of NPR results. The GP language is extended with different techniques and methods inspired from NPR research such as colour mixing expressions, image processing filters and painting algorithm. Colour mixing is a major new contribution, as it enables many familiar and innovative NPR effects to arise. Another major innovation is that many GP functions process the canvas (rendered image), while is dynamically changing. Automatic fitness scoring uses aesthetic evaluation models and statistical analysis, and multi-objective fitness evaluation is used. Results showed a variety of NPR effects, as well as new, creative possibilities.

Automatic Inference of Graph Models for Complex Networks with Genetic Programming

Complex networks can arise naturally and spontaneously from all things that act as a part of a larger system. From the patterns of socialization between people to the way biological systems organize themselves, complex networks are ubiquitous, but are currently poorly understood. A number of algorithms, designed by humans, have been proposed to describe the organizational behaviour of real-world networks. Consequently, breakthroughs in genetics, medicine, epidemiology, neuroscience, telecommunications and the social sciences have recently resulted. The algorithms, called graph models, represent significant human effort. Deriving accurate graph models is non-trivial, time-intensive, challenging and may only yield useful results for very specific phenomena. An automated approach can greatly reduce the human effort required and if effective, provide a valuable tool for understanding the large decentralized systems of interrelated things around us. To the best of the author's knowledge this thesis proposes the first method for the automatic inference of graph models for complex networks with varied properties, with and without community structure. Furthermore, to the best of the author's knowledge it is the first application of genetic programming for the automatic inference of graph models. The system and methodology was tested against benchmark data, and was shown to be capable of reproducing close approximations to well-known algorithms designed by humans. Furthermore, when used to infer a model for real biological data the resulting model was more representative than models currently used in the literature.