GPU: the paradigm of parallel power for evolutionary computation.

Fok Ka Ling.Thesis (M.Phil.)--Chinese University of Hong Kong, 2005.Includes bibliographical references (leaves 96-101).Abstracts in English and Chinese.Abstract --- p.1Acknowledgement --- p.ivChapter 1 --- Introduction --- p.1Chapter 1.1 --- Evolutionary Computation --- p.1Chapter 1.2 --- Graphics Processing Unit --- p.2Chapter 1.3 --- Objective --- p.3Chapter 1.4 --- Contribution --- p.4Chapter 1.5 --- Thesis Organization --- p.4Chapter 2 --- Evolutionary Computation --- p.6Chapter 2.1 --- Introduction --- p.6Chapter 2.2 --- General Framework --- p.7Chapter 2.3 --- Features of Evolutionary Algorithm --- p.8Chapter 2.3.1 --- Widely Applicable --- p.8Chapter 2.3.2 --- Parallelism --- p.9Chapter 2.3.3 --- Robust to Change --- p.9Chapter 2.4 --- Parallel and Distributed Evolutionary Algorithm --- p.9Chapter 2.4.1 --- Global Parallel Evolutionary Algorithms --- p.10Chapter 2.4.2 --- Fine-Grained Evolutionary Algorithms --- p.11Chapter 2.4.3 --- Island Distributed Evolutionary Algorithms --- p.12Chapter 2.5 --- Summary --- p.14Chapter 3 --- Graphics Processing Unit --- p.15Chapter 3.1 --- Introduction --- p.15Chapter 3.2 --- History of GPU --- p.16Chapter 3.2.1 --- First-Generation GPUs --- p.16Chapter 3.2.2 --- Second-Generation GPUs --- p.17Chapter 3.2.3 --- Third-Generation GPUs --- p.17Chapter 3.2.4 --- Fourth-Generation GPUs --- p.17Chapter 3.3 --- The Graphics Pipelining --- p.18Chapter 3.3.1 --- Standard Graphics Pipeline --- p.18Chapter 3.3.2 --- Programmable Graphics Pipeline --- p.18Chapter 3.3.3 --- Fragment Processors for Scientific Computation --- p.21Chapter 3.4 --- GPU-CPU Analogy --- p.23Chapter 3.4.1 --- Memory Architecture --- p.23Chapter 3.4.2 --- Processing Model --- p.24Chapter 3.5 --- Limitation of GPU --- p.24Chapter 3.5.1 --- Limited Input and Output --- p.24Chapter 3.5.2 --- Slow Data Readback --- p.24Chapter 3.5.3 --- No Random Number Generator --- p.25Chapter 3.6 --- Summary --- p.25Chapter 4 --- Evolutionary Programming on GPU --- p.26Chapter 4.1 --- Introduction --- p.26Chapter 4.2 --- Evolutionary Programming --- p.26Chapter 4.3 --- Data Organization --- p.29Chapter 4.4 --- Fitness Evaluation --- p.31Chapter 4.4.1 --- Introduction --- p.31Chapter 4.4.2 --- Different Forms of Fitness Function --- p.32Chapter 4.4.3 --- Parallel Fitness Function Evaluation using GPU --- p.33Chapter 4.5 --- Mutation --- p.34Chapter 4.5.1 --- Introduction --- p.34Chapter 4.5.2 --- Self Adaptive Mutation Operators --- p.36Chapter 4.5.3 --- Mutation on GPU --- p.37Chapter 4.6 --- Selection for Replacement --- p.39Chapter 4.6.1 --- Introduction --- p.39Chapter 4.6.2 --- Classification of Selection Operator --- p.39Chapter 4.6.3 --- q -Tournament Selection --- p.40Chapter 4.6.4 --- Median Searching --- p.41Chapter 4.6.5 --- Minimizing Data Transfer --- p.43Chapter 4.7 --- Experimental Results --- p.44Chapter 4.7.1 --- Visualization --- p.48Chapter 4.8 --- Summary --- p.49Chapter 5 --- Genetic Algorithm on GPU --- p.56Chapter 5.1 --- Introduction --- p.56Chapter 5.2 --- Canonical Genetic Algorithm --- p.57Chapter 5.2.1 --- Parent Selection --- p.57Chapter 5.2.2 --- Crossover and Mutation --- p.62Chapter 5.2.3 --- Replacement --- p.63Chapter 5.3 --- Experiment Results --- p.64Chapter 5.4 --- Summary --- p.66Chapter 6 --- Multi-Objective Genetic Algorithm --- p.70Chapter 6.1 --- Introduction --- p.70Chapter 6.2 --- Definitions --- p.71Chapter 6.2.1 --- General MOP --- p.71Chapter 6.2.2 --- Decision Variables --- p.71Chapter 6.2.3 --- Constraints --- p.71Chapter 6.2.4 --- Feasible Region --- p.72Chapter 6.2.5 --- Optimal Solution --- p.72Chapter 6.2.6 --- Pareto Optimum --- p.73Chapter 6.2.7 --- Pareto Front --- p.73Chapter 6.3 --- Multi-Objective Genetic Algorithm --- p.75Chapter 6.3.1 --- Ranking --- p.76Chapter 6.3.2 --- Fitness Scaling --- p.77Chapter 6.3.3 --- Diversity Preservation --- p.77Chapter 6.4 --- A Niched and Elitism Multi-Objective Genetic Algorithm on GPU --- p.79Chapter 6.4.1 --- Objective Values Evaluation --- p.80Chapter 6.4.2 --- Pairwise Pareto Dominance and Pairwise Distance --- p.81Chapter 6.4.3 --- Fitness Assignment --- p.85Chapter 6.4.4 --- Embedded Archiving Replacement --- p.87Chapter 6.5 --- Experiment Result --- p.89Chapter 6.6 --- Summary --- p.90Chapter 7 --- Conclusion --- p.95Bibliography --- p.9