Maximizing the Delivery of MPR Broadcasting Under Realistic Physical Layer Assumptions

It is now commonly accepted that the unit disk graph used to model the physical layer in wireless networks does not reflect real radio transmissions,and that a more realistic model should be considered for experimental simulations. Previous work on realistic scenarios has been focused on unicast,however broadcast requirements are fundamentally different and cannot be derived from the unicast case.Therefore,the broadcast protocols must be adapted in order to still be efficient under realistic assumptions.In this paper,we study the well-known multipoint relay broadcast protocol(MPR),in which each node has to choose a set of 1-hop neighbors to act as relays in order to cover the whole 2-hop neighborhood.We give experimental results showing that the original strategy used to select these multipoint relays does not suit a realistic model. On the basis of these results,we propose new selection strategies solely based on link quality.One of the key aspects of our solutions is that our strategies do not require any additional hardware and may be implemented at the application layer, which is particularly relevant to the context of ad hoc and sensor networks where energy savings are mandatory.We finally provide new experimental results that demonstrate the superiority of our strategies under realistic physical assumptions.     

Graphical model construction based on evolutionary algorithms

1 Introduction Evolutionary algorithms(EAs) [1～5] are stochastic search and optimization techniques, which were inspired by the analogy of evolution and population genetics. They have been demonstrated to be effective and robust in searching very large, varied, spaces in a wide range of applications, including classification, machine learning, ecological, so- cial systems and so on. However, most of the common evo- lutionary algorithms using simple operators are incapable of learning the reg…     

Clustering mechanism for electric tomography imaging

Electrical tomography(ET) imaging,developed in the 1980s,has attracted much industrial and research attentions owing to its low cost,quick response,lack of radiation exposure,and non-intrusiveness compared to other tomography modalities.However,to date applications thereof have been limited owing to its low imaging resolution.The issue with space resolution in existing ET imaging reconstruction methods is that they employ a mathematical approach based on an ill-posed equation with inconsistent solutions.In this paper,we propose a novel ET imaging method based on a data-driven approach.By recovering the cluster structures hidden in the ET imaging process followed by the application of a fuzzy clustering algorithm to identify the cluster structures,there is no need to study the ill-posed mathematical formulation.The proposed method has been tested by means of three experiments,including image reconstructions of a human lung image and plastic rode shape,as well as two simulations executed on the Comsol platform.The results show that the proposed method can reconstruct ET images with much higher space resolution more quickly than the existing algorithms.     

A hybrid immigrants scheme for genetic algorithms in dynamic environments

Dynamic optimization problems are a kind of optimization problems that involve changes over time.They pose a serious challenge to traditional optimization methods as well as conventional genetic algorithms since the goal is no longer to search for the optimal solution(s) of a fixed problem but to track the moving optimum over time.Dynamic optimization problems have attracted a growing interest from the genetic algorithm community in recent years.Several approaches have been developed to enhance the performance of genetic algorithms in dynamic environments.One approach is to maintain the diversity of the population via random immigrants.This paper proposes a hybrid immigrants scheme that combines the concepts of elitism,dualism and random immigrants for genetic algorithms to address dynamic optimization problems.In this hybrid scheme,the best individual,i.e.,the elite,from the previous generation and its dual individual are retrieved as the bases to create immigrants via traditional mutation scheme.These elitism-based and dualism-based immigrants together with some random immigrants are substituted into the current population,replacing the worst individuals in the population.These three kinds of immigrants aim to address environmental changes of slight,medium and significant degrees respectively and hence efficiently adapt genetic algorithms to dynamic environments that are subject to different severities of changes.Based on a series of systematically constructed dynamic test problems,experiments are carried out to investigate the performance of genetic algorithms with the hybrid immigrants scheme and traditional random immigrants scheme.Experimental results validate the efficiency of the proposed hybrid immigrants scheme for improving the performance of genetic algorithms in dynamic environments.     

Efficient aggregation algorithms on very large compressed data warehouses

Multidimensional aggregation is a dominant operation on data warehouses for on-line analytical processing(OLAP).Many efficinet algorithms to compute multidimensional aggregation on relational database based data warehouses have been developed.However,to our knowledge,there is nothing to date in the literature about aggregation algorithms on multidimensional data warehouses that store datasets in mulitidimensional arrays rather than in tables.This paper presents a set of multidimensional aggregation algorithms on very large and compressed multidimensional data warehouses.These algorithms operate directly on compressed datasets in multidimensional data warehouses without the need to first decompress them.They are applicable to a variety of data compression methods.The algorithms have different performance behavior as a function of dataset parameters,sizes of out puts and ain memory availability.The algorithms are described and analyzed with respect to the I/O and CPU costs,A decision procedure to select the most efficient algorithm ,given an aggregation request,is also proposed.The analytical and experimental results show that the algorithms are more efficient than the traditional aggregation algorithms.     

The Methodology of Testability Prediction for Sequential Circuits

Increasingly,test generation algorithms are being developed with the continuous creations of incredibly sophisticated computing systems.Of all the developments of testable as well as reliable designs for computing systems,the test generation for sequential circuits is usually viewed as one of the hard nuts to be solved for its complexity and time-consuming issue.Although dozens of algorithms have been proposed to cope with this issue,it still remains much to be desired in solving such problems as to determin 1) which of the existing test generation algorithms could be the most efficient for some particular circuits(by efficiency,we mean the Fault Coverage the algorithm offers,CPU time when executing,the number of test patterns to be applied,ectc.)since different algorithms would be preferable for different circuits;2)which parameters(such as the number of gates,flip-flops and loops,etc., in the circuit)will have the most or least influences on test generation so that the designers of circuits can have a global understanding during the stage of designing for testability.Testability forecastin methodology for the sequential circuits using regression models is presented which a user usually needs for analyzing his own circuits and selecting the most suitable test generation algorithm from all possible algorithms available.Some examples and experiment results are also provided in order to show how helpful and practical the method is.     

Performance study of selective encryption in comparison to full encryption for still visual images

Securing digital images is becoming an important concern in today＇s information security due to the extensive use of secure images that are either transmitted over a network or stored on disks. Image encryption is the most effective way to fulfil confidentiality and protect the privacy of images. Nevertheless, owing to the large size and complex structure of digital images, the computational overhead and processing time needed to carry out full image encryption prove to be limiting factors that inhibit it of being used more heavily in real time. To solve this problem, many recent studies use the selective encryption approach to encrypt significant parts of images with a hope to reduce the eneryption overhead. However, it is necessary to realistically evaluate its performance compared to full encryption. In this paper, we study the performance and efficiency of image segmentation methods used in the selective encryption approach, such as edges and face detection methods, in determining the most important parts of visual images. Experiments were performed to analyse the computational results obtained by selective image encryption compared to full image encryption using symmetric encryption algorithms. Experiment results have proven that the selective encryption approach based on edge and face detection can significantly reduce the time of encrypting still visual images as compared to full encryption. Thus, this approach can be considered a good alternative in the implementation of real-time applications that require adequate security levels.     

Analyses and Solutions of Specific Cases in Spatial Angles Calculation

1 Introduction “Spatial Angles Calculations” means that all the calculations of given and unknown parameters are related to calculating angles in 3D space. The functions and relevant parameters in 3D space are much more complicated than that in 2D space, i.e. on a plane. Professor Sun, based on his research conducting for more than a decade, presented a series of new algorithms to calculate angles in space which are valuable in both theory and applications[1]. The authors found that, in g…     

A characterization of answer sets for logic programs

Checking if a program has an answer set, and if so, compute its answer sets are just some of the important problems in answer set logic programming. Solving these problems using Gelfond and Lifschitz's original definition of answer sets is not an easy task. Alternative characterizations of answer sets for nested logic pro- grams by Erdem and Lifschitz, Lee and Lifschitz, and You et al. are based on the completion semantics and various notions of tightness. However, the notion of tightness is a local notion in the sense that for different answer sets there are, in general, different level mappings capturing their tightness. This makes it hard to be used in the design of algorithms for computing answer sets. This paper proposes a characterization of answer sets based on sets of generating rules. From this char- acterization new algorithms are derived for computing answer sets and for per- forming some other reasoning tasks. As an application of the characterization a sufficient and necessary condition for the equivalence between answer set seman- tics and completion semantics has been proven, and a basic theorem is shown on computing answer sets for nested logic programs based on an extended notion of loop formulas. These results on tightness and loop formulas are more general than that in You and Lin's work.     

Fast parallel algorithms for discrete Gabor expansion and transform based on multirate filtering

The Gabor transform has long been recognized as a very useful tool for the joint time and frequency analysis in signal processing.Its real time applications,however,were limited due to the high computational complexity of the Gabor transform algorithms.In this paper,some novel and fast parallel algorithms for the finite discrete Gabor expansion and transform are presented based on multirate filtering.An analysis filter bank is designed for the finite discrete Gabor transform(DGT)and a synthesis filter bank is designed for the finite discrete Gabor expansion(DGE).Each of the parallel channels in the two filter banks has a unified structure and can apply the FFT and the IFFT to reduce its computational load.The computational complexity of each parallel channel does not change as the oversampling rate increases.In fact,it is very low and depends only on the length of the input discrete signal and the number of the Gabor frequency sampling points.The computational complexity of the proposed parallel algorithms is analyzed and compared with that of the major existing parallel algorithms for the finite DGT and DGE.The results indicate that the proposed parallel algorithms for the finite DGT and DGE based on multirate filtering are very attractive for real time signal processing.     

Analysis of the $(1+1)$-EA for Finding Approximate Solutions to Vertex Cover Problems

Vertex cover is one of the best known NP-hard combinatorial optimization problems. Experimental work has claimed that evolutionary algorithms (EAs) perform fairly well for the problem and can compete with problem-specific ones. A theoretical analysis that explains these empirical results is presented concerning the random local search algorithm and the (1+1)-EA. Since it is not expected that an algorithm can solve the vertex cover problem in polynomial time, a worst case approximation analysis is carried out for the two considered algorithms and comparisons with the best known problem-specific ones are presented. By studying instance classes of the problem, general results are derived. Although arbitrarily bad approximation ratios of the (1+1)-EA can be proved for a bipartite instance class, the same algorithm can quickly find the minimum cover of the graph when a restart strategy is used. Instance classes where multiple runs cannot considerably improve the performance of the (1+1)-EA are considered and the characteristics of the graphs that make the optimization task hard for the algorithm are investigated and highlighted. An instance class is designed to prove that the (1+1)-EA cannot guarantee better solutions than the state-of-the-art algorithm for vertex cover if worst cases are considered. In particular, a lower bound for the worst case approximation ratio, slightly less than two, is proved. Nevertheless, there are subclasses of the vertex cover problem for which the (1+1)-EA is efficient. It is proved that if the vertex degree is at most two, then the algorithm can solve the problem in polynomial time.     

From an individual to a population: an analysis of the firsthitting time of population-based evolutionary algorithms

Almost all analyses of time complexity of evolutionary algorithms (EAs) have been conducted for (1 + 1) EAs only. Theoretical results on the average computation time of population-based EAs are few. However, the vast majority of applications of EAs use a population size that is greater than one. The use of population has been regarded as one of the key features of EAs. It is important to understand in depth what the real utility of population is in terms of the time complexity of EAs, when EAs are applied to combinatorial optimization problems. This paper compares (1 + 1) EAs and (N + N) EAs theoretically by deriving their first hitting time on the same problems. It is shown that a population can have a drastic impact on an EA's average computation time, changing an exponential time to a polynomial time (in the input size) in some cases. It is also shown that the first hitting probability can be improved by introducing a population. However, the results presented in this paper do not imply that population-based EAs will always be better than (1 + 1) EAs for all possible problems     

Improving the efficiency of multi-objective evolutionary algorithms through decomposition: An application to water distribution network design

Evolutionary algorithms (EAs) have been widely used in handling various water resource optimization problems in recent years. However, it is still challenging for EAs to identify near-optimal solutions for realistic problems within the available computational budgets. This paper introduces a novel multi-objective optimization method to improve the efficiency of a typically difficult water resource problem: water distribution network (WDN) design. In the proposed approach, a WDN is decomposed into different sub-networks using decomposition techniques. EAs optimize these sub-networks individually, generating Pareto fronts for each sub-network with great efficiency. A propagation method is proposed to evolve Pareto fronts of the sub-networks towards the Pareto front for the full network while eliminating the need to hydraulically simulate the intact network itself. Results from two complex realistic WDNs show that the proposed approach is able to find better fronts than conventional full-search algorithms (optimize the entire network without decomposition) with dramatically improved efficiency.     

Comparing evolutionary algorithms to the (1+1) -EA

In this paper, we study the conditions in which the random hill-climbing algorithm (1 + 1)-EA compares favorably to other evolutionary algorithms (EAs) in terms of fitness function distribution at a given iteration and with respect to the average optimization time. Our approach is applicable when the reproduction operator of an evolutionary algorithm is dominated by the mutation operator of the (1 + 1)-EA. In this case one can extend the lower bounds obtained for the expected optimization time of the (1 + 1)-EA to other EAs based on the dominated reproduction operator. This method is demonstrated on the sorting problem with HAM landscape and the exchange mutation operator. We consider several simple examples where the (1 + 1)-EA is the best possible search strategy in the class of the EAs.     

Parallelism and evolutionary algorithms

This paper contains a modern vision of the parallelization techniques used for evolutionary algorithms (EAs). The work is motivated by two fundamental facts: 1) the different families of EAs have naturally converged in the last decade while parallel EAs (PEAs) are still lack of unified studies; and 2) there is a large number of improvements in these algorithms and in their parallelization that raise the need for a comprehensive survey. We stress the differences between the EA model and its parallel implementation throughout the paper. We discuss the advantages and drawbacks of PEAs. Also, successful applications are mentioned and open problems are identified. We propose potential solutions to these problems and classify the different ways in which recent results in theory and practice are helping to solve them. Finally, we provide a highly structured background relating to PEAs in order to make researchers aware of the benefits of decentralizing and parallelizing an EA     

关于漂移分析的注记

进化算法成功应用于求解各种复杂优化问题,其理论研究尚处于初级阶段。时间复杂性分析可以估计算法的平均运行时间,是进化算法理论研究中的重要方向和有力工具。讨论了漂移分析和进化算法时间复杂性的关系,利用吸收马尔科夫链给出漂移定理的一个新的证明;用一步平均漂移估计算法计算时间,得到了线性函数进化算法时间复杂度的一个一般性的结果。这些结果有助于更好地理解进化算法的工作原理和性能。     

进化算法研究进展

进化算法是一类借鉴生物界自然选择和自然遗传机制的随机搜索算法，主要包括遗传算法，（ｇｅｎｅｒｉｃａｌｇｏｒｉｔｈｍｓ，简记为ＧＡｓ）、进化规划（ｅｖｏｌｕｔｉｏｎａｒｙｐｒｏｇｒａｍｍｉｎｇ，简记为ＥＰ）和进化策略（ｅｖｏｌｕｔｉｏｎａｒｙｓｔｒａｔｅｇｉｅｓ，简记为ＥＳｓ），它们可以用解决优化和机器学习等问题，进化算法的两个主要特点中群体搜索策略及群体中个体之间的信息交换，进化算法不依赖于梯度信     

Rotated neighbor learning-based auto-configured evolutionary algorithm基于旋转邻域学习的自配置进化算法

More and more evolutionary operators have been integrated and manually configured together to solve wider range of problems. Considering the very limited progress made on the automatic configuration of evolutionary algorithms (EAs), a rotated neighbor learning-based auto-configured evolutionary algorithm (RNLACEA) is presented. In this framework, multiple EAs are combined as candidates and automatically screened for different scenarios with a rotated neighbor structure. According to a ranking record and a group of constraints, the algorithms can be better scheduled to improve the searching efficiency and accelerate the searching pace. Experimental studies based on 14 classical EAs and 22 typical benchmark problems demonstrate that RNLACEA outperforms other six representative auto-adaptive EAs and has high scalability and robustness in solving different kinds of numerical optimization problems.     

On the equivalences and differences of evolutionary algorithms

Evolutionary algorithms (EAs) are fast and robust computation methods for global optimization, and have been widely used in many real-world applications. We first conceptually discuss the equivalences of various popular EAs including genetic algorithm (GA), biogeography-based optimization (BBO), differential evolution (DE), evolution strategy (ES) and particle swarm optimization (PSO). We find that the basic versions of BBO, DE, ES and PSO are equal to the GA with global uniform recombination (GA/GUR) under certain conditions. Then we discuss their differences based on biological motivations and implementation details, and point out that their distinctions enhance the diversity of EA research and applications. To further study the characteristics of various EAs, we compare the basic versions and advanced versions of GA, BBO, DE, ES and PSO to explore their optimization ability on a set of real-world continuous optimization problems. Empirical results show that among the basic versions of the algorithms, BBO performs best on the benchmarks that we studied. Among the advanced versions of the algorithms, DE and ES perform best on the benchmarks that we studied. However, our main conclusion is that the conceptual equivalence of the algorithms is supported by the fact that algorithmic modifications result in very different performance levels.     

求解背包问题的演化算法

背包问题(Knapsack Problem, KP)是一类著名的组合优化问题,也是一类NP难问题,它包括0-1背包问题、有界背包问题、多维背包问题、多背包问题、多选择背包问题、二次背包问题、动态背包问题和折扣背包问题等多种形式,在众多领域有着广泛的应用.演化算法(EAs)是一类有效的快速近似求解KP的算法.本文对近十余年来利用EAs求解KP的研究情况进行一个较为详细的总结,它一方面讨论了利用EAs求解各种KP问题时个体的编码方法与处理不可行解的有效方法,另一方面为今后进一步利用最新提出的EAs求解KP问题提供一个可借鉴的思路.