A biased random-key genetic algorithm with forward-backward improvement for the resource constrained project scheduling problem

This paper presents a biased random-key genetic algorithm for the resource constrained project scheduling problem. The chromosome representation of the problem is based on random keys. Active schedules are constructed using a priority-rule heuristic in which the priorities of the activities are defined by the genetic algorithm. A forward-backward improvement procedure is applied to all solutions. The chromosomes supplied by the genetic algorithm are adjusted to reflect the solutions obtained by the improvement procedure. The heuristic is tested on a set of standard problems taken from the literature and compared with other approaches. The computational results validate the effectiveness of the proposed algorithm.

A random key based genetic algorithm for the resource constrained project scheduling problem

This paper presents a genetic algorithm for the Resource Constrained Project Scheduling Problem (RCPSP). The chromosome representation of the problem is based on random keys. The schedule is constructed using a heuristic priority rule in which the priorities of the activities are defined by the genetic algorithm. The heuristic generates parameterized active schedules. The approach was tested on a set of standard problems taken from the literature and compared with other approaches. The computational results validate the effectiveness of the proposed algorithm.

How to extract and expand randomness : a summary and explanation of existing results

We examine the use of randomness extraction and expansion in key agreement (KA) pro- tocols to generate uniformly random keys in the standard model. Although existing works provide the basic theorems necessary, they lack details or examples of appropriate cryptographic primitives and/or parameter sizes. This has lead to the large amount of min-entropy needed in the (non-uniform) shared secret being overlooked in proposals and efficiency comparisons of KA protocols. We therefore summa- rize existing work in the area and examine the security levels achieved with the use of various extractors and expanders for particular parameter sizes. The tables presented herein show that the shared secret needs a min-entropy of at least 292 bits (and even more with more realistic assumptions) to achieve an overall security level of 80 bits using the extractors and expanders we consider. The tables may be used to �nd the min-entropy required for various security levels and assumptions. We also �nd that when using the short exponent theorems of Gennaro et al., the short exponents may need to be much longer than they suggested.

Efficient Forest Data Structure for Evolutionary Algorithms Applied to Network Design

The design of a network is a solution to several engineering and science problems. Several network design problems are known to be NP-hard, and population-based metaheuristics like evolutionary algorithms (EAs) have been largely investigated for such problems. Such optimization methods simultaneously generate a large number of potential solutions to investigate the search space in breadth and, consequently, to avoid local optima. Obtaining a potential solution usually involves the construction and maintenance of several spanning trees, or more generally, spanning forests. To efficiently explore the search space, special data structures have been developed to provide operations that manipulate a set of spanning trees (population). For a tree with n nodes, the most efficient data structures available in the literature require time O(n) to generate a new spanning tree that modifies an existing one and to store the new solution. We propose a new data structure, called node-depth-degree representation (NDDR), and we demonstrate that using this encoding, generating a new spanning forest requires average time O(root n). Experiments with an EA based on NDDR applied to large-scale instances of the degree-constrained minimum spanning tree problem have shown that the implementation adds small constants and lower order terms to the theoretical bound.

Description of economic data collected with a random sample of commercial reef fish boats in the Florida Keys

This study summarizes the results of a survey designed to provide economic information about the financial status of commercial reef fish boats with homeports in the Florida Keys. A survey questionnaire was administered in the summer and fall of 1994 by interviewers in face-to-face meetings with owners or operators of randomly selected boats. Fishermen were asked for background information about themselves and their boats, their capital investments in boats and equipment, and about their average catches, revenues, and costs per trip for their two most important kinds of fishing trips during 1993 for species in the reef fish fishery. Respondents were characterized with regard to their dependence on the reef fish fishery as a source of household income. Boats were described in terms of their physical and financial characteristics. Different kinds of fishing trips were identified by the species that generated the greatest revenue. Trips were grouped into the following categories: yellowtail snapper (Ocyurus chrysurus); mutton snapper (Lutjanus analis), black grouper (Mycteroperca bonaci), or red grouper (Epinephelus morio); gray snapper (Lutjanus griseus); deeper water groupers and tilefishes; greater amberjack (Seriola dumerili); spiny lobster (Panulirus argus); king mackerel (Scomberomorus cavalla); and dolphin (Coryphaena hippurus). Average catches, revenues, routine trip costs, and net operating revenues per boat per trip and per boat per year were estimated for each category of fishing trips. In addition to its descriptive value, data collected during this study will aid in future examinations of the economic effects of various regulations on commercial reef fish fishermen.(PDF file contains 48 pages.)

A new scheme for establishing pairwise keys for wireless sensor networks

This paper addresses the problem of secure path key establishment in wireless sensor networks that uses the random key predistribution technique. Inspired by the recent proxy-based scheme in [1] and [2], we introduce a fiiend-based scheme for establishing pairwise keys securely. We show that the chances of finding friends in a neighbourhood are considerably more than that of finding proxies, leading to lower communication overhead. Further, we prove that the friendbased scheme performs better than the proxy-based scheme in terms of resilience against node capture.

An Efficient Scheme for Establishing Pairwise Keys for Wireless Sensor Networks

This paper addresses the problem of secure path key establishment in wireless sensor networks that uses the random key pre-distribution technique. Inspired by the recent proxy-based scheme in the work of Ling and Znati (2005) and Li et al. (2005), we introduce a friend-based scheme for establishing pairwise keys securely. We show that the chances of finding friends in a neighbourhood are considerably more than that of finding proxies, leading to lower communication overhead. Further, we prove that the friend-based scheme performs better than the proxy-based scheme both in terms of resilience against node capture as well as in energy consumption for pairwise key establishment, making our scheme more feasible.

Population structure, long-term connectivity, and effective size of mutton snapper (Lutjanus analis) in the Caribbean Sea and Florida Keys

Genetic structure and average long-term connectivity and effective size of mutton snapper (Lutjanus analis) sampled from offshore localities in the U.S. Caribbean and the Florida Keys were assessed by using nuclear-encoded microsatellites and a fragment of mitochondrial DNA. No significant differences in allele, genotype (microsatellites), or haplotype (mtDNA) distributions were detected; tests of selective neutrality (mtDNA) were nonsignificant after Bonferroni correction. Heuristic estimates of average long-term rate of migration (proportion of migrant individuals/generation) between geographically adjacent localities varied from 0.0033 to 0.0054, indicating that local subpopulations could respond independently of environmental perturbations. Estimates of average longterm effective population sizes varied from 341 to 1066 and differed significantly among several of the localities. These results indicate that over time larval drift and interregional adult movement may not be sufficient to maintain population sustainability across the region and that there may be different demographic stocks at some of the localities studied. The estimate of long-term effective population size at the locality offshore of St. Croix was below the minimum threshold size considered necessary to maintain the equilibrium between the loss of adaptive genetic variance from genetic drift and its replacement by mutation. Genetic variability in mutton snapper likely is maintained at the intraregional level by aggregate spawning and random mating of local populations. This feature is perhaps ironic in that aggregate spawning also renders mutton snapper especially vulnerable to overexploitation.

Variations in MIMO-OFDM channel capacity due to random human movement in an indoor environment

Channel measurements and simulations have been carried out to observe the effects of pedestrian movement on multiple-input multiple-output orthogonal frequency division multiplexing (MIMO-OFDM) channel capacity. An in-house built MIMO-OFDM packet transmission demonstrator equipped with four transmitters and four receivers has been utilized to perform channel measurements at 5.2 GHz. Variations in the channel capacity dynamic range have been analysed for 1 to 10 pedestrians and different antenna arrays (2 × 2, 3 × 3 and 4 × 4). Results show a predicted 5.5 bits/s/Hz and a measured 1.5 bits/s/Hz increment in the capacity dynamic range with the number of pedestrian and the number of antennas in the transmitter and receiver array.

Random Indexing K-tree

Random Indexing K-tree is the combination of two algorithms suited for large scale document clustering.