Locality-preserving hash functions for general purpose parallel computation

Consider the problem of efficiently simulating the shared-memory parallel random access machine (PRAM) model on massively parallel architectures with physically distributed memory. To prevent network congestion and memory bank contention, it may be advantageous to hash the shared memory address space. The decision on whether or not to use hashing depends on (1) the communication latency in the network and (2) the locality of memory accesses in the algorithm.We relate this decision directly to algorithmic issues by studying the complexity of hashing in the Block PRAM model of Aggarwal, Chandra, and Snir, a shared-memory model of parallel computation which accounts for communication locality. For this model, we exhibit a universal family of hash functions having optimal locality. The complexity of applying these hash functions to the shared address space of the Block PRAM (i.e., by permuting data elements) is asymptotically equivalent to the complexity of performing a square matrix transpose, and this result is best possible for all pairwise independent universal hash families. These complexity bounds provide theoretical evidence that hashing and randomized routing need not destroy communication locality, addressing an open question of Valiant.This work was started when the author was a student at Oxford University, supported by a National Science Foundation Graduate Fellowship and a Rhodes Scholarship. Any opinions, findings, conclusions, or recommendations expressed in this publication are those of the author and do not necessarily reflect the views of the National Science Foundation or the Rhodes Trust.     

基于进化计算的兴趣建模

为实现对个体的兴趣建模,提出基于进化计算的建模(Evolutionary Computation Based Modeling,ECBM)方法。该方法采用定性和定量相结合的方式对个体的兴趣系统进行建模,首先通过定性分析构建个体的兴趣模型框架,然后通过进化计算(Evolutionary Computation)方法对模型参数自动进化。实验结果表明,ECBM能够通过数据驱动模式优化模型参数,并利用更新信息进化模型,使其不断逼近真实系统。     

Binary particle swarm optimization with multiple evolutionary strategies

This paper introduces a novel variation of binary particle swarm optimization(BPSO) algorithm and a further extension to improve its performance.Firstly,mimicking the behaviors of some creatures group,multiple evolutionary strategies BPSO(MBPSO) is introduced which takes different evolutionary strategies for various particles according to their performances.Then,on the basis of MBPSO,a new strategy is discussed to improve the performance of the MBPSO(M2BPSO) which adopts the concept of the mutation operator aiming to overcome the premature convergence and slow convergent speed during the later stages of the optimization.The proposed two algorithms are tested on seven benchmark functions and their results are compared with those obtained by other methods.Experimental results show that our methods outperform the other algorithms.     

A note on circle packing

The problem of packing circles into a domain of prescribed topology is considered. The circles need not have equal radii. The Collins-Stephenson algorithm computes such a circle packing. This algorithm is parallelized in two different ways and its performance is reported for a triangular, planar domain test case. The implementation uses the highly parallel graphics processing unit (GPU) on commodity hardware. The speedups so achieved are discussed based on a number of experiments.     

基于强化学习的无线传感器网络入侵检测攻防博弈研究

无线传感器网络易遭到各种内部攻击,入侵检测系统需要消耗大量能量进行攻击检测以保障网络安全。针对无线传感器网络入侵检测问题,建立恶意节点（malicious node,MN）与簇头节点（cluster head node,CHN）的攻防博弈模型,并提出一种基于强化学习的簇头入侵检测算法——带有近似策略预测的策略加权学习算法（weighted policy learner with approximate policy prediction,WPL-APP）。实验表明,簇头节点采用该算法对恶意节点进行动态检测防御,使得博弈双方快速达到演化均衡,避免了网络出现大量检测能量消耗和网络安全性能的波动。     

An evolutionary lion optimization algorithm‐based image compression technique for biomedical applications

Recently, medical image compression becomes essential to effectively handle large amounts of medical data for storage and communication purposes. Vector quantization (VQ) is a popular image compression technique, and the commonly used VQ model is Linde–Buzo–Gray (LBG) that constructs a local optimal codebook to compress images. The codebook construction was considered as an optimization problem, and a bioinspired algorithm was employed to solve it. This article proposed a VQ codebook construction approach called the L2‐LBG method utilizing the Lion optimization algorithm (LOA) and Lempel Ziv Markov chain Algorithm (LZMA). Once LOA constructed the codebook, LZMA was applied to compress the index table and further increase the compression performance of the LOA. A set of experimentation has been carried out using the benchmark medical images, and a comparative analysis was conducted with Cuckoo Search‐based LBG (CS‐LBG), Firefly‐based LBG (FF‐LBG) and JPEG2000. The compression efficiency of the presented model was validated in terms of compression ratio (CR), compression factor (CF), bit rate, and peak signal to noise ratio (PSNR). The proposed L2‐LBG method obtained a higher CR of 0.3425375 and PSNR value of 52.62459 compared to CS‐LBG, FA‐LBG, and JPEG2000 methods. The experimental values revealed that the L2‐LBG process yielded effective compression performance with a better‐quality reconstructed image.     

Secure authentication scheme for passive C1G2 RFID tags

Privacy and security concerns inhibit the fast adaption of RFID technology for many applications. A number of authentication protocols that address these concerns have been proposed but real-world solutions that are secure, maintain low communication cost and can be integrated into the ubiquitous EPCglobal Class 1 Generation 2 tag protocol (C1G2) are still needed and being investigated. We present a novel authentication protocol, which offers a high level of security through the combination of a random key scheme with a strong cryptography. The protocol is applicable to resource, power and computationally constraint platforms such as RFID tags. Our investigation shows that it can provide mutual authentication, untraceability, forward and backward security as well as resistance to replay, denial-ofth-service and man-in-the-middle attacks, while retaining a competitive communication cost. The protocol has been integrated into the EPCglobal C1G2 tag protocol, which assures low implementation cost. We also present a successful implementation of our protocol on real-world components such as the INTEL WISP UHF RFID tag and a C1G2 compliant reader.     

Handling multiple objectives with biogeography-based optimization

Biogeography-based optimization (BBO) is a new evolutionary optimization method inspired by biogeography. In this paper, BBO is extended to a multi-objective optimization, and a biogeography-based multi-objective optimization (BBMO) is introduced, which uses the cluster attribute of islands to naturally decompose the problem. The proposed algorithm makes use of nondominated sorting approach to improve the convergence ability effciently. It also combines the crowding distance to guarantee the diversity of Pareto optimal solutions. We compare the BBMO with two representative state-of-the-art evolutionary multi-objective optimization methods, non-dominated sorting genetic algorithm-II (NSGA-II) and archive-based micro genetic algorithm (AMGA) in terms of three metrics. Simulation results indicate that in most cases, the proposed BBMO is able to find much better spread of solutions and converge faster to true Pareto optimal fronts than NSGA-II and AMGA do.     

Interactive Genetic Algorithm with Mixed Initiative Interaction for multi-criteria ground water monitoring design

Design of optimal plans for environmental planning and management applications should ideally consider the multiple quantitative and qualitative criteria relevant to the problem. For example, in ground water monitoring design problems, qualitative criteria such as acceptable spatial extent and shape of the contaminant plume predicted from the monitored locations can be equally important as the typical quantitative criteria such as economic costs and contaminant prediction accuracy. Incorporation of qualitative criteria in the problem-solving process is typically done in one of two ways: (a) quantifying approximate representations of the qualitative criteria, which are then used as additional criteria during the optimization process, or (b) post-optimization analysis of designs by experts to evaluate the overall performance of the optimized designs with respect to the qualitative criteria. These approaches, however, may not adequately represent all of the relevant qualitative information that affect a human expert involved in design (e.g. engineers, stakeholders, regulators, etc.), and do not necessarily incorporate the effect of the expert's own learning process on the suitability of the final design. The Interactive Genetic Algorithm with Mixed Initiative Interaction (IGAMII) is a novel approach that addresses these limitations by using a collaborative human-computer search strategy to assist users in designing optimized solutions to their applications, while also learning about their problem. The algorithm adaptively learns from the expert's feedback, and explores multiple designs that meet her/his criteria using both the human expert and a simulated model of the expert's responses in a collaborative fashion. The algorithm provides an introspection-based learning framework for the human expert and uses the human's subjective confidence measures to adjust the optimization search process to the transient learning process of the user. This paper presents the design and testing of this computational framework, and the benefits of using this approach for solving groundwater monitoring design problems.