No description available.

In many everyday tasks it is necessary to compare the performance of the individuals in a population described by two or more criteria, for example comparing products in order to decide which is the best to purchase in terms of price and quality. Other examples are the comparison of universities, countries, the infrastructure in a telecommunications network, and the candidate solutions to a multi- or many-objective problem. In all of these cases, visualising the individuals better allows a decision maker to interpret their relative performance. This thesis explores methods for understanding and visualising multi- and many-criterion populations. Since people cannot generally comprehend more than three spatial dimensions the visualisation of many-criterion populations is a non-trivial task. We address this by generating visualisations based on the dominance relation which defines a structure in the population and we introduce two novel visualisation methods. The first method explicitly illustrates the dominance relationships between individuals as a graph in which individuals are sorted into Pareto shells, and is enhanced using many-criterion ranking methods to produce a finer ordering of individuals. We extend the power index, a method for ranking according to a single criterion, into the many-criterion domain by defining individual quality in terms of tournaments. The second visualisation method uses a new dominance-based distance in conjunction with multi-dimensional scaling, and we show that dominance can be used to identify an intuitive low-dimensional mapping of individuals, placing similar individuals close together. We demonstrate that this method can visualise a population comprising a large number of criteria. Heatmaps are another common method for presenting high-dimensional data, however they suffer from a drawback of being difficult to interpret if dissimilar individuals are placed close to each other. We apply spectral seriation to produce an ordering of individuals and criteria by which the heatmap is arranged, placing similar individuals and criteria close together. A basic version, computing similarity with the Euclidean distance, is demonstrated, before rank-based alternatives are investigated. The procedure is extended to seriate both the parameter and objective spaces of a multi-objective population in two stages. Since this process describes a trade-off, favouring the ordering of individuals in one space or the other, we demonstrate methods that enhance the visualisation by using an evolutionary optimiser to tune the orderings. One way of revealing the structure of a population is by highlighting which individuals are extreme. To this end, we provide three definitions of the “edge” of a multi-criterion mutually non-dominating population. All three of the definitions are in terms of dominance, and we show that one of them can be extended to cope with many-criterion populations. Because they can be difficult to visualise, it is often difficult for a decision maker to comprehend a population consisting of a large number of criteria. We therefore consider criterion selection methods to reduce the dimensionality with a view to preserving the structure of the population as quantified by its rank order. We investigate the efficacy of greedy, hill-climber and evolutionary algorithms and cast the dimension reduction as a multi-objective problem.

This thesis studies rhythm from an evolutionary computation perspective. Rhythm is the most fundamental dimension of music and can be used as a ground to describe the evolution of music. More specifically, the main goal of the thesis is to investigate how complex rhythmic structures evolve, subject to the cultural transmission between individuals in a society. The study is developed by means of computer modelling and simulations informed by evolutionary computation and artificial life (A-Life). In this process, self-organisation plays a fundamental role. The evolutionary process is steered by the evaluation of rhythmic complexity and by the exposure to rhythmic material. In this thesis, composers and musicologists will find the description of a system named A-Rhythm, which explores the emerged behaviours in a community of artificial autonomous agents that interact in a virtual environment. The interaction between the agents takes the form of imitation games. A set of necessary criteria was established for the construction of a compositional system in which cultural transmission is observed. These criteria allowed the comparison with related work in the field of evolutionary computation and music. In the development of the system, rhythmic representation is discussed. The proposed representation enabled the development of complexity and similarity based measures, and the recombination of rhythms in a creative manner. A-Rhythm produced results in the form of simulation data which were evaluated in terms of the coherence of repertoires of the agents. The data shows how rhythmic sequences are changed and sustained in the population, displaying synchronic and diachronic diversity. Finally, this tool was used as a generative mechanism for composition and several examples are presented.

by Ngan Po Shun. / Thesis (M.Phil.)--Chinese University of Hong Kong, 1998. / Includes bibliographical references (leaves 109-115). / Abstract also in Chinese. / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Data Mining --- p.1 / Chapter 1.2 --- Motivation --- p.4 / Chapter 1.3 --- Contributions of the research --- p.5 / Chapter 1.4 --- Organization of the thesis --- p.6 / Chapter 2 --- Related Work in Data Mining --- p.9 / Chapter 2.1 --- Decision Tree Approach --- p.9 / Chapter 2.1.1 --- ID3 --- p.10 / Chapter 2.1.2 --- C4.5 --- p.11 / Chapter 2.2 --- Classification Rule Learning --- p.13 / Chapter 2.2.1 --- AQ algorithm --- p.13 / Chapter 2.2.2 --- CN2 --- p.14 / Chapter 2.2.3 --- C4.5RULES --- p.16 / Chapter 2.3 --- Association Rule Mining --- p.16 / Chapter 2.3.1 --- Apriori --- p.17 / Chapter 2.3.2 --- Quantitative Association Rule Mining --- p.18 / Chapter 2.4 --- Statistical Approach --- p.19 / Chapter 2.4.1 --- Chi Square Test and Bayesian Classifier --- p.19 / Chapter 2.4.2 --- FORTY-NINER --- p.21 / Chapter 2.4.3 --- EXPLORA --- p.22 / Chapter 2.5 --- Bayesian Network Learning --- p.23 / Chapter 2.5.1 --- Learning Bayesian Networks using the Minimum Descrip- tion Length (MDL) Principle --- p.24 / Chapter 2.5.2 --- Discretizating Continuous Attributes while Learning Bayesian Networks --- p.26 / Chapter 3 --- Overview of Evolutionary Computation --- p.29 / Chapter 3.1 --- Evolutionary Computation --- p.29 / Chapter 3.1.1 --- Genetic Algorithm --- p.30 / Chapter 3.1.2 --- Genetic Programming --- p.32 / Chapter 3.1.3 --- Evolutionary Programming --- p.34 / Chapter 3.1.4 --- Evolution Strategy --- p.37 / Chapter 3.1.5 --- Selection Methods --- p.38 / Chapter 3.2 --- Generic Genetic Programming --- p.39 / Chapter 3.3 --- Data mining using Evolutionary Computation --- p.43 / Chapter 4 --- Applying Generic Genetic Programming for Rule Learning --- p.45 / Chapter 4.1 --- Grammar --- p.46 / Chapter 4.2 --- Population Creation --- p.49 / Chapter 4.3 --- Genetic Operators --- p.50 / Chapter 4.4 --- Evaluation of Rules --- p.52 / Chapter 5 --- Learning Multiple Rules from Data --- p.56 / Chapter 5.1 --- Previous approaches --- p.57 / Chapter 5.1.1 --- Preselection --- p.57 / Chapter 5.1.2 --- Crowding --- p.57 / Chapter 5.1.3 --- Deterministic Crowding --- p.58 / Chapter 5.1.4 --- Fitness sharing --- p.58 / Chapter 5.2 --- Token Competition --- p.59 / Chapter 5.3 --- The Complete Rule Learning Approach --- p.61 / Chapter 5.4 --- Experiments with Machine Learning Databases --- p.64 / Chapter 5.4.1 --- Experimental results on the Iris Plant Database --- p.65 / Chapter 5.4.2 --- Experimental results on the Monk Database --- p.67 / Chapter 6 --- Bayesian Network Learning --- p.72 / Chapter 6.1 --- The MDLEP Learning Approach --- p.73 / Chapter 6.2 --- Learning of Discretization Policy by Genetic Algorithm --- p.74 / Chapter 6.2.1 --- Individual Representation --- p.76 / Chapter 6.2.2 --- Genetic Operators --- p.78 / Chapter 6.3 --- Experimental Results --- p.79 / Chapter 6.3.1 --- Experiment 1 --- p.80 / Chapter 6.3.2 --- Experiment 2 --- p.82 / Chapter 6.3.3 --- Experiment 3 --- p.83 / Chapter 6.3.4 --- Comparison between the GA approach and the greedy ap- proach --- p.91 / Chapter 7 --- Medical Data Mining System --- p.93 / Chapter 7.1 --- A Case Study on the Fracture Database --- p.95 / Chapter 7.1.1 --- Results of Causality and Structure Analysis --- p.95 / Chapter 7.1.2 --- Results of Rule Learning --- p.97 / Chapter 7.2 --- A Case Study on the Scoliosis Database --- p.100 / Chapter 7.2.1 --- Results of Causality and Structure Analysis --- p.100 / Chapter 7.2.2 --- Results of Rule Learning --- p.102 / Chapter 8 --- Conclusion and Future Work --- p.106 / Bibliography --- p.109 / Chapter A --- The Rule Sets Discovered --- p.116 / Chapter A.1 --- The Best Rule Set Learned from the Iris Database --- p.116 / Chapter A.2 --- The Best Rule Set Learned from the Monk Database --- p.116 / Chapter A.2.1 --- Monkl --- p.116 / Chapter A.2.2 --- Monk2 --- p.117 / Chapter A.2.3 --- Monk3 --- p.119 / Chapter A.3 --- The Best Rule Set Learned from the Fracture Database --- p.120 / Chapter A.3.1 --- Type I Rules: About Diagnosis --- p.120 / Chapter A.3.2 --- Type II Rules : About Operation/Surgeon --- p.120 / Chapter A.3.3 --- Type III Rules : About Stay --- p.122 / Chapter A.4 --- The Best Rule Set Learned from the Scoliosis Database --- p.123 / Chapter A.4.1 --- Rules for Classification --- p.123 / Chapter A.4.2 --- Rules for Treatment --- p.126 / Chapter B --- The Grammar used for the fracture and Scoliosis databases --- p.128 / Chapter B.1 --- The grammar for the fracture database --- p.128 / Chapter B.2 --- The grammar for the Scoliosis database --- p.128

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

Data mining algorithms discover knowledge from data. The knowledge are commonly expressed as dependency relationships in various forms, like rules, decision trees and Bayesian Networks (BNs). Moreover, many real-world problems are multi-class problems, in which more than one of the variables in the data set are considered as classes. However, most of the rule learners available were proposed for single-class problems only and would produce cyclic rules if they are applied to multi-class ones. In addition, most of them produce rules with conflicts, i.e. more than one of the rules classify the same data items and different rules have different predictions. Similarly, existing decision trees learners cannot handle multi-class problems, and thus cannot detect and avoid cycles. In contrast, BNs represent acyclic dependency relationships among variables, but they can handle discrete values only. They cannot manage continuous, interval and ordinal values and cannot represent higher-order relationships. Consequently, BNs have higher network complexity and lower understandability when they are used for such problems. / This thesis has studied in depth discovering dependency relationships in various forms by Evolutionary Computation (EC). Through analysis of the reasons leading to the disadvantages of rules, decision trees and BNs, and their learners, we have proposed a sequence of EAs, a novel functional dependency network (FDN) and two techniques for dependency relationship learning and for multi-class problems. They are the multi-population Genetic Programming (GP) using backward chaining procedure and the GP employing co-operating scoring stage for acyclic rules learning. The dependency network with functions can manage all kinds of values and represent any kind of relationships among variables, the flexible and robust MDLGP to learn the novel dependency network and BN. Based on the FDN we have further developed the techniques to learn rules without conflict and acyclic decision trees for multi-class problems respectively. The new self-organizing map (SOM) with expanding force for clustering and data visualization for data preprocessing have also been given in the appendix. / Shum Wing Ho. / "May 2007." / Adviser: Kwong-Sak Leung. / Source: Dissertation Abstracts International, Volume: 69-01, Section: B, page: 0436. / Thesis (Ph.D.)--Chinese University of Hong Kong, 2007. / Includes bibliographical references (p. 221-240). / Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Electronic reproduction. [Ann Arbor, MI] : ProQuest Information and Learning, [200-] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Abstracts in English and Chinese. / School code: 1307.

Traditional techniques for the design of robots require human engineers to plan every aspect of the system, from body to controller. In contrast, the field of evolu- tionary robotics uses evolutionary algorithms to create optimized morphologies and neural controllers with minimal human intervention. In order to expand the capability of an evolved agent, it must be exposed to a variety of conditions and environments. This thesis investigates the design and benefits of virtual robots which can reflect the structure and modularity in the world around them. I show that when a robot’s morphology and controller enable it to perceive each environment as a collection of independent components, rather than a monolithic entity, evolution only needs to optimize on a subset of environments in order to maintain performance in the overall larger environmental space. I explore previously unused methods in evolutionary robotics to aid in the evolution of modularity, including using morphological and neurological cost. I utilize a tree morphology which makes my results generalizable to other mor- phologies while also allowing in depth theoretical analysis about the properties rel- evant to modularity in embodied agents. In order to better frame the question of modularity in an embodied context, I provide novel definitions of morphological and neurological modularity as well as create the sub-goal interference metric which mea- sures how much independence a robot exhibits with regards to environmental stimu- lus. My work extends beyond evolutionary robotics and can be applied to the opti- mization of embodied systems in general as well as provides insight into the evolution of form in biological organisms.

The efficiency of the mechanical design process can be improved by the use of evolutionary algorithms. Evolutionary algorithms provide a convenient and robust method to search for appropriate design solutions. Difficult non-linear problems are often encountered during the mechanical engineering design process. Solutions to these problems often involve computationally-intensive simulations. Evolutionary algorithms tuned to work with a small number of solution iterations can be used to automate the search for optimal solutions to these problems. An evolutionary algorithm was designed to give reliable results after a few thousand iterations; additionally the scalability and the ease of application to varied problems were considered. Convergence velocity of the algorithm was improved considerably by altering the mutation-based parameters in the algorithm. Much of this performance gain can be attributed to making the magnitude of the mutation and the minimum mutation rates self-adaptive. Three motorsport based design problems were simulated and the evolutionary algorithm was applied to search for appropriate solutions. The first two, a racing-line generator and a suspension kinematics simulation, were investigated to highlight properties of the evolutionary algorithm: reliability; solution representation; determining variable/performance relationships; and multiple objectives were discussed. The last of these problems was the lap-time simulation of a Formula SAE vehicle. This problem was solved with 32 variables, including a number of major conceptual differences. The solution to this optimisation was found to be significantly better than the 2004 UWA Motorsport vehicle, which finished 2nd in the 2005 US competition. A simulated comparison showed the optimised vehicle would score 62 more points (out of 675) in the dynamic events of the Formula SAE competition. Notably the optimised vehicle had a different conceptual design to the actual UWA vehicle. These results can be used to improve the design of future Formula SAE vehicles. The evolutionary algorithm developed here can be used as an automated search procedure for problems where performance solutions are computationally intensive.

DAEX is a metaheuristic designed to improve the plan quality and the scalability of an encapsulated planning system. DAEX is based on a state decomposition strategy, driven by an evolutionary algorithm, which benefits from the use of a classical planning heuristic to maintain an ordering of atoms within the individuals. The proof of concept is achieved by embedding the domain-independent satisficing YAHSP planner and using the critical path h1 heuristic. Experiments with the resulting algorithm are performed on a selection of IPC benchmarks from classical, cost-based and temporal domains. Under the experimental conditions of the IPC, and in particular with a universal parameter setting common to all domains, DAEYAHSP is compared to the best planner for each type of domain. Results show that DAEYAHSP performs very well both on coverage and quality metrics. It is particularly noticeable that DAEX improves a lot on plan quality when compared to YAHSP, which is known to provide largely suboptimal solutions, making it competitive with state-of-the-art planners. This article gives a full account of the algorithm, reports on the experiments and provides some insights on the algorithm behavior.

Thesis (Ph. D.)--University of Texas at Austin, 2003. / Vita. Includes bibliographical references. Available also from UMI Company.