2009
DocumentsDate added
Inductive Linkage Identification: Scalability, Robustness, and Population Sizing
Abstract: This paper proposes a linkage identification algorithm, named inductive linkage identification (ILI), to identify linkages, which are referred to as the interdependencies among variables. The proposed algorithm utilizes the ID3 decision tree to extract sets of variables based on the mutual relevance on the fitness differences caused by perturbation. In this study, we concentrate on the properties and characteristics of ILI, including its scalability, robustness, and population requirement. According to the experimental results, compared to other linkage learning techniques, ILI exhibits equal or better flexibility, scalability, and robustness. A theoretical population sizing model is also developed in this paper to reveal the population requirement for ILI to operate. The proposed population sizing model well agrees with the experimental results and such a model may provide an insight into perturbation-based as well as entropy-based linkage learning methodologies.
Abstract: This paper proposes a linkage identification algorithm, named inductive linkage identification (ILI), to identify linkages, which are referred to as the interdependencies among variables. The proposed algorithm utilizes the ID3 decision tree to extract sets of variables based on the mutual relevance on the fitness differences caused by perturbation. In this study, we concentrate on the properties and characteristics of ILI, including its scalability, robustness, and population requirement. According to the experimental results, compared to other linkage learning techniques, ILI exhibits equal or better flexibility, scalability, and robustness. A theoretical population sizing model is also developed in this paper to reveal the population requirement for ILI to operate. The proposed population sizing model well agrees with the experimental results and such a model may provide an insight into perturbation-based as well as entropy-based linkage learning methodologies.
Free Lunch on the Discrete Lipschitz Class
Abstract: The No-Free-Lunch theorem states that all algorithms have the identical performance on average over all functions and there is no algorithm able to outperform others on all problems. However, such a result does not imply that search heuristics or optimization algorithms are futile if we are more cautious with the applicability of these methods and the search space. In this paper, within the No-Free-Lunch framework, we firstly introduce the discrete Lipschitz class by transferring the Lipschitz functions, i.e., functions with bounded slope, as a measure to fulfill the notion of continuity in discrete functions. We then investigate the properties of the discrete Lipschitz class, generalize an algorithm called subthreshold-seeker for optimization, and show that the generalized subthreshold-seeker outperforms random search on this class. Finally, we propose a tractable sampling-test scheme to empirically demonstrate the superiority of the generalized subthreshold-seeker under practical configurations. This study concludes that there exists algorithms outperforming random search on the discrete Lipschitz class in both theoretical and practical aspects and indicates that the effectiveness of search heuristics may not be universal but still general in some broad sense.
Abstract: The No-Free-Lunch theorem states that all algorithms have the identical performance on average over all functions and there is no algorithm able to outperform others on all problems. However, such a result does not imply that search heuristics or optimization algorithms are futile if we are more cautious with the applicability of these methods and the search space. In this paper, within the No-Free-Lunch framework, we firstly introduce the discrete Lipschitz class by transferring the Lipschitz functions, i.e., functions with bounded slope, as a measure to fulfill the notion of continuity in discrete functions. We then investigate the properties of the discrete Lipschitz class, generalize an algorithm called subthreshold-seeker for optimization, and show that the generalized subthreshold-seeker outperforms random search on this class. Finally, we propose a tractable sampling-test scheme to empirically demonstrate the superiority of the generalized subthreshold-seeker under practical configurations. This study concludes that there exists algorithms outperforming random search on the discrete Lipschitz class in both theoretical and practical aspects and indicates that the effectiveness of search heuristics may not be universal but still general in some broad sense.
Detecting General Problem Structures with Inductive Linkage Identification
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 make an attempt to enable a perturbation-based method, inductive linkage identification (ILI), to detect general problem structures, in which one decision variable can link to an arbitrary number of other variables. Experiments on circular problem structures composed of order-4 and order-5 trap functions are conducted. The results indicate that the proposed technique requires a population size growing logarithmically with the problem size as the original ILI does on non-overlapping building blocks as well as that the population requirement is insensitive to the problem structure consisting of similar sub-structures as long as the overall problem size is identical.
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 make an attempt to enable a perturbation-based method, inductive linkage identification (ILI), to detect general problem structures, in which one decision variable can link to an arbitrary number of other variables. Experiments on circular problem structures composed of order-4 and order-5 trap functions are conducted. The results indicate that the proposed technique requires a population size growing logarithmically with the problem size as the original ILI does on non-overlapping building blocks as well as that the population requirement is insensitive to the problem structure consisting of similar sub-structures as long as the overall problem size is identical.
Analysis of Particle Swarm Optimization Convergence Time
Abstract: In this thesis we analyze the convergence time of particle swarm optimization (PSO) on the facet of particle interaction. We propose a statistical model of PSO which captures the behavior of PSO particle interaction, and we use it to obtain results about convergence time. After the theoretical analysis we use experiments to verify our results by running real PSO on benchmark functions.
Abstract: In this thesis we analyze the convergence time of particle swarm optimization (PSO) on the facet of particle interaction. We propose a statistical model of PSO which captures the behavior of PSO particle interaction, and we use it to obtain results about convergence time. After the theoretical analysis we use experiments to verify our results by running real PSO on benchmark functions.
Inductive Linkage Identification on Building Blocks of Different Sizes and Types
Abstract: The goal of linkage identification is to obtain the dependencies among decision variables. Such information or knowledge can be applied to the designs of crossover operators and/or the encoding schemes in genetic and evolutionary methods. Thus, promising sub-solutions to the problem will be less probably disrupted and successful convergences may more likely to be achieved. In our previous studies, a linkage identification technique, called Inductive Linkage Identification (ILI), was proposed. This method was established upon the mechanism of perturbation and the idea of decision tree learning. By constructing a decision tree according to decision variables and resulting fitness difference values, the interdependent variables will be determined by the decision tree learning algorithm. In this paper, we aim to acquire more understandings on the characteristics of ILI, especially its behavior under problems composed of different-sized and different-typed building blocks. Experiments showed that ILI can efficiently handle building block of different sizes and is insensitive to building block types. Our experimental observations indicate the flexibility and the applicability of ILI on various elementary building block types that are commonly adopted in experiments.
Abstract: The goal of linkage identification is to obtain the dependencies among decision variables. Such information or knowledge can be applied to the designs of crossover operators and/or the encoding schemes in genetic and evolutionary methods. Thus, promising sub-solutions to the problem will be less probably disrupted and successful convergences may more likely to be achieved. In our previous studies, a linkage identification technique, called Inductive Linkage Identification (ILI), was proposed. This method was established upon the mechanism of perturbation and the idea of decision tree learning. By constructing a decision tree according to decision variables and resulting fitness difference values, the interdependent variables will be determined by the decision tree learning algorithm. In this paper, we aim to acquire more understandings on the characteristics of ILI, especially its behavior under problems composed of different-sized and different-typed building blocks. Experiments showed that ILI can efficiently handle building block of different sizes and is insensitive to building block types. Our experimental observations indicate the flexibility and the applicability of ILI on various elementary building block types that are commonly adopted in experiments.
On the Detection of General Problem Structures by using Inductive Linkage Identification
Abstract: Genetic algorithms and the 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. 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 make an attempt to enable a perturbation-based method, inductive linkage identification (ILI), to detect general problem structures, in which one decision variable can link to an arbitrary number of other variables. Experiments on circular problem structures composed of order-4 and order-5 trap functions are conducted. The results indicate that the proposed technique requires a population size growing logarithmically with the problem size as the original ILI does on non-overlapping building blocks as well as that the population requirement is insensitive to the problem structure consisting of similar sub-structures as long as the overall problem size is identical.
Abstract: Genetic algorithms and the 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. 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 make an attempt to enable a perturbation-based method, inductive linkage identification (ILI), to detect general problem structures, in which one decision variable can link to an arbitrary number of other variables. Experiments on circular problem structures composed of order-4 and order-5 trap functions are conducted. The results indicate that the proposed technique requires a population size growing logarithmically with the problem size as the original ILI does on non-overlapping building blocks as well as that the population requirement is insensitive to the problem structure consisting of similar sub-structures as long as the overall problem size is identical.
Free Lunches on the Discrete Lipschitz Class
Abstract: The No-Free-Lunch theorem states that there does not exist a genuine general-purpose optimizer because all algorithms have the identical performance on average over all functions. However, such a result does not imply that search heuristics or optimization algorithms are futile if we are more cautious with the applicability of these methods and the search space. In this paper, within the No-Free-Lunch framework, we firstly introduce the discrete Lipschitz class by transferring the Lipschitz functions, i.e., functions with bounded slope, as a measure to fulfill the notion of continuity in discrete functions. We then investigate the properties of the discrete Lipschitz class, generalize an algorithm called subthreshold-seeker for optimization, and show that the generalized subthreshold-seeker outperforms random search on this class. Finally, we propose a tractable sampling-test scheme to empirically demonstrate the superiority of the generalized subthreshold-seeker under practical configurations. This study concludes that there exists algorithms outperforming random search on the discrete Lipschitz class in both theoretical and practical aspects and indicates that the effectiveness of search heuristics may not be universal but still general in some broad sense.
Abstract: The No-Free-Lunch theorem states that there does not exist a genuine general-purpose optimizer because all algorithms have the identical performance on average over all functions. However, such a result does not imply that search heuristics or optimization algorithms are futile if we are more cautious with the applicability of these methods and the search space. In this paper, within the No-Free-Lunch framework, we firstly introduce the discrete Lipschitz class by transferring the Lipschitz functions, i.e., functions with bounded slope, as a measure to fulfill the notion of continuity in discrete functions. We then investigate the properties of the discrete Lipschitz class, generalize an algorithm called subthreshold-seeker for optimization, and show that the generalized subthreshold-seeker outperforms random search on this class. Finally, we propose a tractable sampling-test scheme to empirically demonstrate the superiority of the generalized subthreshold-seeker under practical configurations. This study concludes that there exists algorithms outperforming random search on the discrete Lipschitz class in both theoretical and practical aspects and indicates that the effectiveness of search heuristics may not be universal but still general in some broad sense.
Identification and Search of Protein Structural Motif
Abstract: In protein science, the common belief is that amino acid sequence determines protein structure, and then protein structure determines the biological function. As the availability of the rapidly growing number of protein crystal structures and the advent of proteomics technologies, many methods have been proposed to identify sequence-structure-function relationships.
In this study, we investigate the relationship of protein sequence-structure-function by surveying PROSITE database. PROSITE is a widely used database that maintains annotated biological motifs. We review the structurally conserved property of PROSITE patterns to validate the fundamental principle—protein structure leads to protein function.
In addition, we proposed fastCOPS that integrates a quick screening method, 3D-BLAST, an accurate structural alignment method, MAMMOTH, and the mechanism of recursive truncation with an appropriate logic flow. In general, tools and methods currently available can be adopted in the fastCOPS framework as long as they are compatible with the design. The quick component should be able to accept a protein fragment as input, and the accurate component has to be capable of aligning partial structures with possible gap insertions.
We apply fastCOPS to achieve the task of structural motif search and identification. The fastCOPS has been evaluated on various structural motifs, including the treble clef finger motif, and the leucine-rich repeat motif. In addition, we use a PROSITE pattern as query to demonstrate the capability that fastCOPS can find structurally conserved fragments but using sequence alignment tool will hardly be achieved.
Abstract: In protein science, the common belief is that amino acid sequence determines protein structure, and then protein structure determines the biological function. As the availability of the rapidly growing number of protein crystal structures and the advent of proteomics technologies, many methods have been proposed to identify sequence-structure-function relationships.
In this study, we investigate the relationship of protein sequence-structure-function by surveying PROSITE database. PROSITE is a widely used database that maintains annotated biological motifs. We review the structurally conserved property of PROSITE patterns to validate the fundamental principle—protein structure leads to protein function.
In addition, we proposed fastCOPS that integrates a quick screening method, 3D-BLAST, an accurate structural alignment method, MAMMOTH, and the mechanism of recursive truncation with an appropriate logic flow. In general, tools and methods currently available can be adopted in the fastCOPS framework as long as they are compatible with the design. The quick component should be able to accept a protein fragment as input, and the accurate component has to be capable of aligning partial structures with possible gap insertions.
We apply fastCOPS to achieve the task of structural motif search and identification. The fastCOPS has been evaluated on various structural motifs, including the treble clef finger motif, and the leucine-rich repeat motif. In addition, we use a PROSITE pattern as query to demonstrate the capability that fastCOPS can find structurally conserved fragments but using sequence alignment tool will hardly be achieved.
