A Study on the Behavior of Genetic Algorithms on NK-Landscapes : Effects of Selection, Drift, Mutation, and Recombination(Neuro, Fuzzy, GA)(<Special Section>Nonlinear Theory and its Applications)
スポンサーリンク
概要
- 論文の詳細を見る
NK-Landscapes are stochastically generated fitness functions on bit strings, parameterized with N bits and K epistatic interactions between bits. The term epistasis describes nonlinearities in fitness functions due to changes in the values of interacting bits. Empirical studies have shown that the overall performance of random bit climbers on NK-Landscapes is superior to the performance of some simple and enhanced genetic algorithms (GAs). Analytical studies have also lead to suggest that NK-Landscapes may not be appropriate for testing the performance of GAs. In this work we study the effect of selection, drift, mutation, and recombination on NK-Landscapes for N 96. We take a model of generational parallel varying mutation GA (GA-SRM) and switch on and off its major components to emphasize each of the four processes mentioned above. We observe that using an appropriate selection pressure and postponing drift make GAs quite robust on NK-Landscapes; different to previous studies, even simple GAs with these two features perform better than a random bit climber (RBC+) for a broad range of classes of problems (K ≥ 4). We also observe that the interaction of parallel varying mutation with crossover improves further the reliability of the GA, especially for 12 < K < K 32. Contrary to intuition, we find that for small K a mutation only evolutionary algorithm (EA) is very effective and crossover may be omitted; but the relative importance of crossover interacting with varying mutation increases with K performing better than mutation alone (K > 12). This work indicates that NK-Landscapes are useful for testing each one of the major processes involved in a GA and for assessing the overall behavior of a GA on complex non-linear problems. This study also gives valuable guidance to practitioners applying GAs to real world problems of how to configure the GA to achieve better results as the non-linearity and complexity of the problem increases.
- 社団法人電子情報通信学会の論文
- 2003-09-01
著者
-
Aguirre Hernan
Faculty Of Engineering Shinshu University
-
Tanaka Kiyoshi
Faculty Of Engineering Seikei University
関連論文
- PB80 A FIRST TOTAL SYNTHESIS OF REDOX COENZYME FACTOR 420
- Empirical Model with Cooperative-Competitive Genetic Operators to Improve GAs : Performance Investigation with 0/1 Multiple Knapsack Problems
- Performance Study of Improved Distributed Genetic Algorithm in 0/1 Multiple Knapsack Problem
- Differential Responses in Activity of Antioxidant Enzymes to Different Environmental Stresses in Arabidopsis thaliana
- Performance Analysis of Path Relinking on Many-objective NK-Landscapes
- δ-Similar Elimination to Enhance Search Performance of Multiobjective Evolutionary Algorithms
- A Study on Parallel Varying Mutation in Deterministic and Self-Adaptive GAs with 0/1 Multiple Knapsack Problems (特集:進化的計算)
- Purification of an Aminopeptidase Preferentially Releasing N-terminal Alanine from Cucumber Leaves and Its Identification as a Plant Aminopeptidase N(Biochemistry & Molecular Biology)
- A study on diversity activation and collective detection in artificial immune systems (特集 ソフトコンピューティングの新展開)
- Controlling Dominance Area of Solutions in Multiobjective Evolutionary Algorithms and Performance Analysis on Multiobjective 0/1 Knapsack Problems
- Enhancing Multiobjective Evolutionary Algorithms by Local Dominance and Local Recombination : Performance Verification in Multiobjective 0/1 Knapsack Problems
- Directed ortho Lithiation in the Reactions of 3,5-Dimethyl-and 5-Trifluoromethyl-1-phenylpyrazoles with Butyllithium
- Multiple Messages Embedding Using DCT-based Mod4 Steganographic Method
- A Study on a Data Encryption Scheme Based on a Shape-Variable Truncated Baker Transformation(Papers Selected from 2003 International Technical Conference on Circuits/Systems, Computers and Communications(ITC-CSCC 2003))
- Improvements of StegErmelc steganographic method using hybrid recursive matrix encoding (「安全・安心・快適」な社会の実現を目指す画像電子関連技術論文特集)
- Complete video quality preserving data hiding in MPEG domain with Reverse Zerorun Length data representation scheme (「超」を追求する画像電子関連技術論文特集号)
- A Data Hiding Method Using Mquant in MPEG Domain
- StegErmelc : A Novel DCT-Based Steganographic Method Using Three Strategies
- A Novel Chaotic Multiple-Bits Modulation Scheme Using Mapping Parameters as Data Carrier
- Performance Analysis of Path Relinking on Many-objective NK-Landscapes
- Physiological and enzymological properties of phosphoenolpyruvate carboxylase in soybean (Glycine max L.cv Enrei) seeds
- Enhancing Multiobjective Evolutionary Algorithms by Local Dominance and Local Recombination: Performance Verification in Multiobjective 0/1 Knapsack Problems
- PM3 Analysis of Nitrone Cycloadditions to Methyl 4,4,4-Trifluoro-2-butenoate
- An Improved Simulation Method of Color Perception by Elderly People Based on Measured Luminescence Spectrum and Color Constancy Relaxation
- Multi-Level Image Halftoning Technique with Genetic Algorithms(Special Section on Digital Signal Processing)
- A Study on the Behavior of Genetic Algorithms on NK-Landscapes : Effects of Selection, Drift, Mutation, and Recombination(Neuro, Fuzzy, GA)(Nonlinear Theory and its Applications)
- Inter-Block Evaluation Method to Further Reduce Evaluation Numbers in GA-Based Image Halftoning Technique(Digital Signal Processing)
- Wheat-Aegilops chromosome addition lines showing high iron and zinc contents in grains
- Computational Cost Reduction of Improved Super-Resolution Method Using Overlapped Block Matching
- Controlling Dominance Area of Solutions in Multiobjective Evolutionary Algorithms and Performance Analysis on Multiobjective 0/1 Knapsack Problems
- Local Dominance MOEA Including Control of Dominance Area of Solutions on 0/1 Multiobjective Knapsack Problems