2010
DocumentsDate added
On the Optimization of Degree Distributions in LT Codes with Covariance Matrix Adaptation Evolution Strategy
Abstract: LT codes have been a popular and practical technique in the field of channel coding since their proposal. The key component of LT codes is a degree distribution which is used to determine the relationship between source data and codewords. Luby in his proposal suggested a general method to construct feasible degree distributions. Such a general design works appropriately in typical situations but not optimally in most cases. To explore the full potential of LT codes, in this work, we make the first attempt to introduce evolutionary algorithms to optimize the degree distribution in LT codes. Degree distributions are encoded as real-valued vectors and evaluated by numerical simulation of LT codes. For applications of different natures, two objectives are implemented to search good degree distributions with different decoding behavior. Compared with the original design, the experimental results are quite promising and demonstrate that the degree distribution can be customized for different purposes. In addition to manually adjusting the degree distribution as the common practice, the work presented in this paper provides an efficient alternative approach to use and adapt LT codes for both practitioners and researchers.
Abstract: LT codes have been a popular and practical technique in the field of channel coding since their proposal. The key component of LT codes is a degree distribution which is used to determine the relationship between source data and codewords. Luby in his proposal suggested a general method to construct feasible degree distributions. Such a general design works appropriately in typical situations but not optimally in most cases. To explore the full potential of LT codes, in this work, we make the first attempt to introduce evolutionary algorithms to optimize the degree distribution in LT codes. Degree distributions are encoded as real-valued vectors and evaluated by numerical simulation of LT codes. For applications of different natures, two objectives are implemented to search good degree distributions with different decoding behavior. Compared with the original design, the experimental results are quite promising and demonstrate that the degree distribution can be customized for different purposes. In addition to manually adjusting the degree distribution as the common practice, the work presented in this paper provides an efficient alternative approach to use and adapt LT codes for both practitioners and researchers.
Optimizing Degree Distributions in LT Codes by Using The Multiobjective Evolutionary Algorithm Based on Decomposition
Abstract: LT codes are the first practical framework of digital fountain codes and have been widely used as fundamental components in many communication applications. The coding behavior of LT codes is majorly decided by a probability distribution of codeword degrees. In order to customize a degree distribution for different purposes or characteristics, a multiobjective evolution algorithm is introduced to optimize degree distributions for LT codes in this paper. Two crucial performance indicators of LT codes are considered in the present work, because minimizing the overhead of extra data packets is more important in some applications, while limiting the computational cost of the coding system in others. To flexibly handle the problem, MOEA/D is applied to optimize the two objectives simultaneously. We expect to find out the Pareto front (PF) formed by partial optimal solutions and provide the available degree distributions for different types of LT codes applications. Not only promising results are presented in this paper, but also the behavior of LT codes are thoroughly explored by optimizing the degree distribution for multiple objectives.
Abstract: LT codes are the first practical framework of digital fountain codes and have been widely used as fundamental components in many communication applications. The coding behavior of LT codes is majorly decided by a probability distribution of codeword degrees. In order to customize a degree distribution for different purposes or characteristics, a multiobjective evolution algorithm is introduced to optimize degree distributions for LT codes in this paper. Two crucial performance indicators of LT codes are considered in the present work, because minimizing the overhead of extra data packets is more important in some applications, while limiting the computational cost of the coding system in others. To flexibly handle the problem, MOEA/D is applied to optimize the two objectives simultaneously. We expect to find out the Pareto front (PF) formed by partial optimal solutions and provide the available degree distributions for different types of LT codes applications. Not only promising results are presented in this paper, but also the behavior of LT codes are thoroughly explored by optimizing the degree distribution for multiple objectives.
Estimation of Distribution Algorithms: Basic Ideas and Future Directions
Abstract: Estimation of distribution algorithms (EDAs) are a class of evolutionary algorithms which can be regarded as abstraction of genetic algorithms (GAs) because in the design of EDAs, the population, one of the GA distinctive features, is replaced by probabilistic models/distributions. Building and sampling from the models substitute for the common genetic operators, such as crossover and mutation. Due to their excellent optimization performance, EDAs have been intensively studied and extensively applied in recent years. In order to interest more people to join the research of EDAs, this paper plays as an entry level introduction to EDAs. It starts with introducing the origination and basic ideas of EDAs, followed by presenting the current EDA frameworks, which are broadly applied in many scientific and engineering disciplines. Finally, this paper also describes some ongoing topics and potential directions in the hope that readers may get further insights into EDAs.
Abstract: Estimation of distribution algorithms (EDAs) are a class of evolutionary algorithms which can be regarded as abstraction of genetic algorithms (GAs) because in the design of EDAs, the population, one of the GA distinctive features, is replaced by probabilistic models/distributions. Building and sampling from the models substitute for the common genetic operators, such as crossover and mutation. Due to their excellent optimization performance, EDAs have been intensively studied and extensively applied in recent years. In order to interest more people to join the research of EDAs, this paper plays as an entry level introduction to EDAs. It starts with introducing the origination and basic ideas of EDAs, followed by presenting the current EDA frameworks, which are broadly applied in many scientific and engineering disciplines. Finally, this paper also describes some ongoing topics and potential directions in the hope that readers may get further insights into EDAs.
Convergence Time Analysis of Particle Swarm Optimization Based on Particle Interaction
Abstract: In this paper, we analyze the convergence time of particle swarm optimization (PSO) on the facet of particle interaction. We firstly introduce a statistical interpretation of social-only PSO in order to capture the essence of particle interaction, which is one of the key mechanisms of PSO. We then use the statistical model to obtain theoretical results on the convergence time. Since the theoretical analysis is conducted on the social-only model of PSO, instead of on common models in practice, to verify the validity of our results, numerical experiments are executed on benchmark functions with a regular PSO program.
Abstract: In this paper, we analyze the convergence time of particle swarm optimization (PSO) on the facet of particle interaction. We firstly introduce a statistical interpretation of social-only PSO in order to capture the essence of particle interaction, which is one of the key mechanisms of PSO. We then use the statistical model to obtain theoretical results on the convergence time. Since the theoretical analysis is conducted on the social-only model of PSO, instead of on common models in practice, to verify the validity of our results, numerical experiments are executed on benchmark functions with a regular PSO program.
Analysis on the Collaboration between Global Search and Local Search in Memetic Computation
Abstract: The synergy between exploration and exploitation has been a prominent issue in optimization. The rise of memetic algorithms, a category of optimization techniques which feature the explicit exploration-exploitation coordination, much accentuates this issue. While memetic algorithms have achieved remarkable success in a wide range of real-world applications, the key to successful exploration-exploitation synergies still remains obscure as conclusions drawn from empirical results or theoretical derivations are usually quite algorithm specific and/or problem dependent. This paper aims to provide a theoretical model that can depict the collaboration between global search and local search in memetic compuatation on a broad class of objective functions. In the proposed model, the interaction between global search and local search creates a set of local search zones, in which the global optimal points reside, within the search space. Based on such a concept, the Quasi-Basin Class (QBC) which categorizes problems according to the distribution of their local search zones is adopted. For the behavior of local search, the subthreshold seeker, taken as a representative archetype of memetic algorithms, is analyzed on various QBCs to develop a general model for memetic algorithms. As the proposed model not only well describes the expected time for a simple memetic algorithm to find the optimal point on different QBCs but also consists with the observations made in previous studies in the literature, the proposed model may reveal important insights to the design of memetic algorithms in general.
Abstract: The synergy between exploration and exploitation has been a prominent issue in optimization. The rise of memetic algorithms, a category of optimization techniques which feature the explicit exploration-exploitation coordination, much accentuates this issue. While memetic algorithms have achieved remarkable success in a wide range of real-world applications, the key to successful exploration-exploitation synergies still remains obscure as conclusions drawn from empirical results or theoretical derivations are usually quite algorithm specific and/or problem dependent. This paper aims to provide a theoretical model that can depict the collaboration between global search and local search in memetic compuatation on a broad class of objective functions. In the proposed model, the interaction between global search and local search creates a set of local search zones, in which the global optimal points reside, within the search space. Based on such a concept, the Quasi-Basin Class (QBC) which categorizes problems according to the distribution of their local search zones is adopted. For the behavior of local search, the subthreshold seeker, taken as a representative archetype of memetic algorithms, is analyzed on various QBCs to develop a general model for memetic algorithms. As the proposed model not only well describes the expected time for a simple memetic algorithm to find the optimal point on different QBCs but also consists with the observations made in previous studies in the literature, the proposed model may reveal important insights to the design of memetic algorithms in general.
LT Codes with Connection Choice
Abstract: This paper proposes LT codes with Connection Choice (LTCC), a modified version of LT codes, to reduce the computational cost and to enhance the applicability of LT codes. The key design of LTCC is the use of tournament selection, a substitute for random selection, in the encoding phase to select source symbols to process. Theoretical analyses are conducted on the missing probability of LT codes and LTCC to reveal the reason why LTCC possesses the claimed properties. Simulation results further demonstrate that LTCC can provide the same of better performance, in terms of reception overhead, with less computational cost. In summary, LTCC can be readily utilized for applications in which the number of source symbols is from hundreds to tens of thousands. For applications of more source symbols, although LTCC might not provide significantly better performance, the computational cost will still be greatly reduced.
Abstract: This paper proposes LT codes with Connection Choice (LTCC), a modified version of LT codes, to reduce the computational cost and to enhance the applicability of LT codes. The key design of LTCC is the use of tournament selection, a substitute for random selection, in the encoding phase to select source symbols to process. Theoretical analyses are conducted on the missing probability of LT codes and LTCC to reveal the reason why LTCC possesses the claimed properties. Simulation results further demonstrate that LTCC can provide the same of better performance, in terms of reception overhead, with less computational cost. In summary, LTCC can be readily utilized for applications in which the number of source symbols is from hundreds to tens of thousands. For applications of more source symbols, although LTCC might not provide significantly better performance, the computational cost will still be greatly reduced.
Linkage Identification Based on Decision Tree Learning
Abstract: Genetic algorithms and their descendant methods have been deemed robust, effective, and practical for the past decades. In order to enhance the features and capabilities of genetic algorithms, tremendous effort has been invested within the research community of evolutionary computation. One of the major development trends to improve genetic algorithms is trying to extract and exploit the relationship among decision variables, such as estimation of distribution algorithms and perturbation-based methods. In this study, we attempt to investigate the integration of perturbation-based method, inductive linkage identification (ILI), and decision tree learning algorithms for detecting general problem structures. Experiments on circular problems structures composed of order-4 and order-5 trap functions are conducted, as well as the experiments on the cardinality of variables. Our experiments results indicates that this approach requires a population size growing logarithmically and is insensitive to the problem structure consisting of similar sub-structures as long as the overall problem size is identical and those variables are binary. Experiments also show that different adopted decision tree learning algorithms will demand different requirements when the variables are extended to higher cardinalities.
Abstract: Genetic algorithms and their descendant methods have been deemed robust, effective, and practical for the past decades. In order to enhance the features and capabilities of genetic algorithms, tremendous effort has been invested within the research community of evolutionary computation. One of the major development trends to improve genetic algorithms is trying to extract and exploit the relationship among decision variables, such as estimation of distribution algorithms and perturbation-based methods. In this study, we attempt to investigate the integration of perturbation-based method, inductive linkage identification (ILI), and decision tree learning algorithms for detecting general problem structures. Experiments on circular problems structures composed of order-4 and order-5 trap functions are conducted, as well as the experiments on the cardinality of variables. Our experiments results indicates that this approach requires a population size growing logarithmically and is insensitive to the problem structure consisting of similar sub-structures as long as the overall problem size is identical and those variables are binary. Experiments also show that different adopted decision tree learning algorithms will demand different requirements when the variables are extended to higher cardinalities.
XCS with Bit Mask in Data Mining
Abstract: In this paper, an adapted XCS is proposed to reduce the numbers of the rules. The XCS is a branch of learning classifier systems which has been proven finding accurate maximal generalizations and has good performance on difficult problems. However, it usually produces too much rules to lower readability of the classification model. That is, people may not be able to get the needed knowledge or useful information out of the model. To solve this problem, a new mutation called Bit mask is devised in order to reduce the number of classification rules and therefore to improve the readability of the generated prediction model.
We did a series of N-multiplexer experiments, including 6-bit, 11-bit, and 20-bit multiplexers to examine the performance of the proposed method. For the integer inputs, two synthetic oblique datasets, "Random-Data2" and "Random-Data9" are used to compare the performance of XCS and the proposed method. Moreover, the real world data is also used in the experience. According to the experimental results, the proposed method is verified that it has the capacity to reduce the classification rules with high prediction accuracy on the test problems.
Abstract: In this paper, an adapted XCS is proposed to reduce the numbers of the rules. The XCS is a branch of learning classifier systems which has been proven finding accurate maximal generalizations and has good performance on difficult problems. However, it usually produces too much rules to lower readability of the classification model. That is, people may not be able to get the needed knowledge or useful information out of the model. To solve this problem, a new mutation called Bit mask is devised in order to reduce the number of classification rules and therefore to improve the readability of the generated prediction model.
We did a series of N-multiplexer experiments, including 6-bit, 11-bit, and 20-bit multiplexers to examine the performance of the proposed method. For the integer inputs, two synthetic oblique datasets, "Random-Data2" and "Random-Data9" are used to compare the performance of XCS and the proposed method. Moreover, the real world data is also used in the experience. According to the experimental results, the proposed method is verified that it has the capacity to reduce the classification rules with high prediction accuracy on the test problems.
An Adaptive Data Replication Algorithm based on Star-based Data Grids
Abstract: In recent Grid research and development, data replication has been used to duplicate frequently accessed data from its current location to appropriate sites so as to improve the whole system's data access performance and reduce bandwidth consumption for data delivery. Several data replication algorithms have been proposed. Some were designed based on unlimited storage. However, not all Data Grids are with unlimited storage space. Others were implemented on limited storage environments. However, none of the algorithms developed on limited storage environments has considered file popularity, defined as how often a file is accessed by users. In fact, file popularity and data access patterns of a system vary with time since users sometimes change their interests where data access patterns, defined as the distribution of access counts on files of a system, may influence on the data access performance of the system. In other words, the file replication model of the system might not be able to adapt to the change of users’ data access behaviors. Therefore, in this study, we proposed an adaptive data replication algorithm, called Popular File Replication First algorithm (PFRF for short), which is developed on a star-based Data Grid with limited storage space. With aggregated data access information of previously job execution and user behaviors, PFRF can predict future file popularity, and replicate potential popular files/replicas to appropriate cluster/sites to adapt the change. We employ several types of file access behaviors, including Uniform, Geometric, and Zipf-like distributions, to evaluate PFRF. The simulation results show that PFRF can effectively shorten average job response time, reduce bandwidth consumption for data delivery, and increase data availability as compared with the tested algorithms.
Abstract: In recent Grid research and development, data replication has been used to duplicate frequently accessed data from its current location to appropriate sites so as to improve the whole system's data access performance and reduce bandwidth consumption for data delivery. Several data replication algorithms have been proposed. Some were designed based on unlimited storage. However, not all Data Grids are with unlimited storage space. Others were implemented on limited storage environments. However, none of the algorithms developed on limited storage environments has considered file popularity, defined as how often a file is accessed by users. In fact, file popularity and data access patterns of a system vary with time since users sometimes change their interests where data access patterns, defined as the distribution of access counts on files of a system, may influence on the data access performance of the system. In other words, the file replication model of the system might not be able to adapt to the change of users’ data access behaviors. Therefore, in this study, we proposed an adaptive data replication algorithm, called Popular File Replication First algorithm (PFRF for short), which is developed on a star-based Data Grid with limited storage space. With aggregated data access information of previously job execution and user behaviors, PFRF can predict future file popularity, and replicate potential popular files/replicas to appropriate cluster/sites to adapt the change. We employ several types of file access behaviors, including Uniform, Geometric, and Zipf-like distributions, to evaluate PFRF. The simulation results show that PFRF can effectively shorten average job response time, reduce bandwidth consumption for data delivery, and increase data availability as compared with the tested algorithms.
