Using genetic algorithms for the single allocation hub location problem

Hub location problem is an NP-hard problem that frequently arises in the design of transportation and distribution systems, postal delivery networks, and airline passenger flow. This work focuses on the Single Allocation Hub Location Problem (SAHLP). Genetic Algorithms (GAs) for the capacitated and uncapacitated variants of the SAHLP based on new chromosome representations and crossover operators are explored. The GAs is tested on two well-known sets of real-world problems with up to 200 nodes. The obtained results are very promising. For most of the test problems the GA obtains improved or best-known solutions and the computational time remains low. The proposed GAs can easily be extended to other variants of location problems arising in network design planning in transportation systems.

The identification and characterization of inter- and intra-species genetic diversity derived from retrotransposons in humans

Retrotransposons, which used to be considered as “junk DNA”, have begun to reveal their immense value to genome evolution and human biology due to recent studies. They consist of at least ~45% of the human genome and are more or less the same in other mammalian genomes. Retrotransposon elements (REs) are known to affect the human genome through many different mechanisms, such as generating insertion mutations, genomic instability, and alteration in gene expression. Previous studies have suggested several RE subfamilies, such as Alu, L1, SVA and LTR, are currently active in the human genome, and they are an important source of genetic diversity between human and other primates, as well as among humans. Although several groups had used Retrotransposon Insertion Polymorphisms (RIPs) as markers in studying primate evolutionary history, no study specifically focused on identifying Human-Specific Retrotransposon Element (HS-RE) and their roles in human genome evolution. In this study, by computationally comparing the human genome to 4 primate genomes, we identified a total of 18,860 HS-REs, among which are 11,664 Alus, 4,887 L1s, 1,526 SVAs and 783 LTRs (222 full length entries), representing the largest and most comprehensive list of HS-REs generated to date. Together, these HS-REs contributed a total of 14.2Mb sequence increase from the inserted REs and Target Site Duplications (TSDs), 71.6Kb increase from transductions, and 268.2 Kb sequence deletion of from insertion-mediated deletion, leading to a net increase of ~14 Mb sequences to the human genome. Furthermore, we observed for the first time that Y chromosome might be a hot target for new retrotransposon insertions in general and particularly for LTRs. The data also allowed for the first time the survey of frequency of TE insertions inside other TEs in comparison with TE insertion into none-TE regions. In summary, our data suggest that retrotransposon elements have played a significant role in the evolution of Homo sapiens.

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.

Receipt from John R. Monro, St. Catharines for payment on household items

Receipt from John R. Monro, St. Catharines for payment on household items of crockery and china, March 1, 1887.