Interactive Evolutionary Computation in Design Applications for Virtual Worlds by Jan Kruse


7659c1dbf2b3c67-261x361.jpg Author Jan Kruse
Isbn 9781543196726
File size 4.1MB
Year 2017
Pages 102
Language English
File format PDF
Category information technologies


 

Table of Contents 1 Introduction 1.1 Definitions 1.2 Background 1.3 Research Questions 1.4 Significance of Research 1.5 Summary of Main Contributions 1.6 Structure 2 Literature Review 2.1 Introduction 2.2 Generative Design 2.3 Artificial Intelligence 2.3.1 Definition of Artificial Intelligence 2.3.2 Artificial Intelligence Systems 2.4 Evolutionary Computation 2.4.1 Genetic Algorithm 2.4.2 Interactive Evolutionary Computation 2.5 Agents 2.5.1 Agent Architectures 2.5.2 Learning Agents 2.5.3 Multi Agent Systems 2.6 Human-based Genetic Algorithm 2.6.1 2.7 Multi-agent Genetic Algorithms Summary 3 Methodology and Research Design 3.1 Methodology 3.2 Software System 3.2.1 Pipeline 3.2.2 RIB archives 3.2.3 Applications 3.2.4 Implemented Agent Architecture 3.3 Experimental Process 3.3.1 Infographics 3.3.2 Procedural City 4 Results and Observations 4.1 Introduction 4.2 Infographics 4.3 Procedural City 4.3.1 Random Selection 4.3.2 Interactive Genetic Algorithm 4.3.3 Human-based Genetic Algorithm 5 Discussion and Conclusions 5.1 Contributions 5.2 Findings 5.3 Limitations 5.4 Future Work 5.4.1 Procedurally generated buildings 5.4.2 Evaluation Agents 5.4.3 Boosting Human-based Genetic Algorithms 5.4.4 Psychological Aspects 5.5 Conclusion 6 References List of Figures Figure 1 - Positioning Artificial Intelligence in the overall context (only relevant areas shown) Figure 2 - Field of Evolutionary Computation Figure 3 - Sphere function Figure 4 - Levi function N.13 Figure 5 - Simple reflex agent (Russell & Norvig, 2003) Figure 6 - Learning Agent (Russell & Norvig, 2003) Figure 7 - Human-based Genetic Algorithms in the field of Artificial Intelligence Figure 8 – Example of Genetic Algorithm as multi-agent system Figure 9 - Design Science Process Figure 10 - simplified pipeline overview Figure 11 - Structure of a RIB archive Figure 12 - Infographics using Genetic Algorithms Figure 13 - Manhattan grid structure example including height value examples Figure 14 - New York style streets Figure 15 - European style street layout Figure 16 - Candidate showing New York style streets, water in the background, distinct city center Figure 17 - Infographics process Figure 18 - Summary of experiments Figure 19 - Generation 1 of an IGA run Figure 20 - Generation 10 of a typical IGA run Figure 21 - Generation 20 of IGA Figure 22 - Generation 30 of exemplary IGA run Figure 23 - Generation 40 of IGA run Figure 24 - Final candidate of IGA run Figure 25 - Comparison IGA versus HBGA Figure 26 – Generation 10 of HBGA run presenting mostly water, contrary to the brief given Figure 27 - Generation 14 of the same HBGA run as above, showing mostly land-based candidates Figure 28 - Decision tree visualization with WEKA after 15 generations Preface Modern films, games and virtual reality are highly dependent on convincing computer graphics. Models of high complexity are a requirement for the successful delivery of many animated scenes and environments. While workflows such as rendering, compositing and animation have been streamlined to accommodate increasing demands, modelling of complex models is still a laborious and costly task. This research introduces the computational benefits of Interactive Genetic Algorithms to computer graphics modelling while compensating the negative effects of user fatigue, a commonly found issue with Interactive Evolutionary Computation. A multi-agent system is used to integrate Genetic Algorithms with computational agents and human designers. This workflow accelerates the layout and distribution of basic elements to form highly complex models. It captures the designer’s intent through interaction, and encourages playful discovery. A modelling pipeline integrating commercially available tools with Human-based Genetic Algorithms is implemented, and a Renderman Interface Bytestream (RIB) archive output is realized to provide easy adaptability for research and industry applications. Comparisons between Interactive Genetic Algorithms and Human-based Genetic Algorithms applied to procedural modelling of computer graphics cities indicate that an agent-based evolutionary approach outperforms a purely human-centric solution: More iterations are possible in less time, which ultimately leads to better results and a superior user experience. Based on initial testing, a range of suggestions for future investigation are given. 1 Introduction Convincing Computer Graphics models are a necessity for the creation of successful games, movies and virtual reality environments. Designing high-quality content is a laborious and costly task that requires substantial skill, time and resources (Okun & Zwerman, 2010; Shiffman, 2012). Often, many iterations are necessary to achieve the desired results. Some natural and architectural objects of higher complexity intensify this problem as they necessitate fine detail and a large number of smaller elements, which are the building blocks of the whole. This research addresses these issues by use of human-centric evolutionary computation in conjunction with autonomous agents in order to determine whether this process can be facilitated by semi-autonomous approaches. Interactive Genetic Algorithms, driven by user input, plus computational software agents that support the user in the decision making process, are the core of the solution presented in this thesis. By shifting the workload from the human user into computational areas, the laborious tasks of modelling are simplified and the process is partially automated. This study is concerned with two main ideas: First, it applies a hybrid intelligent system to interactive design and second, it seeks to explore the procedural generation of cities. Procedural city design is used as an example to demonstrate the process, identify potential benefits, and find possible issues of hybrid intelligent systems in design contexts. This research aims to identify whether the addition of two combined artificial intelligence methods, Interactive Evolutionary Computation and Autonomous Agents are beneficial to the human designer in design practice. In order to be able to find a solution to this question, the problem definition is being broken down into the following smaller pieces. First, Evolutionary Algorithms in general are discussed, and how to integrate the human user into the process to make Evolutionary Computation interactive. Further, a definition of Autonomous Agents in this specific context is provided. The agent architecture is being discussed and a software system to study the hybrid intelligent system is introduced. Finally, Generative Design in context of procedural city design as an example is being demonstrated, which serves as one of the two case study for this thesis. 1.1 Definitions CG Computer Graphics, the field of media creation by use of computer software including images, sound or animation CGI Computer Generated Images, specifically referring to images created by use of computer software DCC Digital Content Creation, field of producing digital media content such as images, sound or animation by use of computer software EC Evolutionary Computation, the field of computer science using biologically inspired search and optimization techniques IEC Interactive Evolutionary Computation, biologically inspired search and optimization techniques with a human user typically replacing a mathematical fitness function GA Genetic Algorithm, probably the most common Evolutionary Computation algorithm IGA Interactive Genetic Algorithm, Genetic Algorithm with a human user typically replacing a mathematical fitness function HBGA Human-based Genetic Algorithm, a multi-agent system replacing recombination and selection with human and/or computational agents RIB Renderman Interface Bytestream, file format used to describe scene data for Renderman compliant render engines UI User Interface, sometimes GUI (Graphical User Interface) 1.2 Background The motivation for this research originated from personal experience of the author. Having spent a significant number of years in the visual effects industry, amongst all existing workflows, modelling always stood out as a very slow, laborious task. Especially large and highly complex models, for example the beautiful, highly detailed, digital version of New York in the 1920s for Peter Jackson’s “King Kong” took months to finish and require large teams to do the mostly manual work. As a consequence, complex models are also a substantial figure in every visual effects budget (Okun & Zwerman, 2010). In order to reduce the amount of time and labour necessary, this study seeks to use computational solutions such as Evolutionary Computation and Agents for some of the tasks involved in modelling large structures. 1.3 Research Questions This study is driven by the main research question “To what extent can Interactive Evolutionary Algorithms combined with autonomous agents support designers in complex form finding tasks?” In order to address the various parts of this multifaceted problem, it is broken down into several sub-questions: What are the issues that designers face in complex form finding tasks? How does the complexity of the task influence the selection of design tools? Which is a suitable choice of algorithm, selected from variety of evolutionary algorithms, to answer the main research question? How does the addition of an autonomous agent benefit the form finding process? How can the proposed combination of Interactive Evolutionary Algorithm and agents reduce the skills requirements for the designer, yet enable the designer to produce very complex structures? 1.4 Significance of Research Design and creation of Computer Generated models is an important foundation for several different fields such as Games, Film, Visualization and Virtual Reality, to name a few. Convincing and seemingly complex models are necessary to create an immersive experience for the targeted audience across all fields (Okun & Zwerman, 2010). With computer hardware, digital cinemas and UHD television set, the mark for detailed models has been set even higher and content creators are seeking to improve the quality of their products without having to invest more money in today’s high risk environment. Artists and designers who are supplying the models have to adapt to very complex Digital Content Creation software (DCC), which often utilizes hundreds or thousands of parameters to drive the designs of the models. Naturally, modern DCC software has a very steep learning curve (Kostic, Radakovic, Cvetkovic, Trajkovic, & Jevremovic, 2012). The increasing complexity of the DCC software combined with the inversely proportional decrease in available budgets for the created content, leads to a predicament, which this research seeks to address by using computational intelligence rather than manual labour. The conflict between rising demands and shrinking budgets underlines the importance of this body of work and sets the foundation for this study. Some research into design systems that reduce manual work and utilize computing power instead has been done prior to this study (Renner & Ekárt). Those systems are mostly driven by the computer and not the designer. Resulting models are evidence of the capability of the software programmer creating the software, rather than the designer using the software. This study seeks to include the designer rather than running an exclusive automated process lacking the designer’s intent. Capturing the vision and using the designers aesthetic preference to drive the final design is an important element (Anderson, Buchsbaum, Potter, & Bonabeau, 2008) which based on the outcomes of a thorough literature review appears to have not yet been applied to complex three dimensional modelling based on computational methods. This too emphasizes the importance of this study. Finally, this research adds another important element to existing knowledge by accounting for the main implication found in interactive design systems – user fatigue (Kamalian, Yeh, Zhang, Agogino, & Takagi, 2006). Numerous iterations, slow render times that create potentially unproductive periods and the before-mentioned complexity of DCC software contribute largely to the user’s incrementing lack of concentration. Todd and Werner (Todd & Werner, 1999) formed the term “fitness bottleneck” in this context. This study addresses the issue by adding an autonomous agent to the software system, which supports the user and reduces the number of required interactive iterations. 1.5 Summary of Main Contributions This thesis presents two main contributions to existing knowledge. First, an original method to integrate asset creation using Evolutionary Computation and RenderMan compliant outputs is discussed and demonstrated. This enables future researchers as well as pipeline programmers in the creative industries to utilize advanced Artificial Intelligence algorithms in conjunction with standard commercial render engines. The second main contribution is the integration of an Interactive Genetic Algorithm with an Autonomous Agent system to support the human user in the process of creating models and lessen the effects of fatigue while increasing the number of possible iterations to refine the final product. Although the development of the workflow and the software system consumed most of the time of this research, initial testing of the academic prototype showed promising results and the foundation for further research in this field has been laid. 1.6 Structure This Thesis is structured into four main parts, namely the Literature Review, Methodology and Research Design, Results and Observations, and finally Discussion and Conclusions. The Literature Review unpacks the three main research components of this study: Generative Design, Evolutionary Computation and Agents. The section about Generative Design gives a short insight and definition of what this term in context of the vast field of Design encapsulates and how Generative Design is situated within the wider area of Computer Aided Design. The second component discusses the current knowledge about Intelligence, Machine Intelligence and more specifically Evolutionary Computation. The struggle to grasp what Intelligence in general means, as well as the ongoing discussion about machines and software and their capacity to exert seemingly intelligent behaviour is discussed. Finally, the field of Agents and Agent Systems as part of the third and probably most innovative component of this research is looked at. Methodology and Research Design discusses practice-led, design science, action and empirical research as they are part of the overall Methodology being used in this study. The experimental process as well as the software systems used to measure performance of Interactive Evolutionary Computation with Agents is being introduced. In the third main section of this thesis, results and observations are presented and discussed. The differences between Interactive Evolutionary Computation with and without Agents are highlighted in order to address the research questions. Further, the successful integration of Evolutionary Computation and standard render engines used by the visual effects industry is demonstrated. Finally, the fourth section of this study, discusses the outcomes and presents the conclusions that can be drawn from this research. This section also discusses limitations of the current work and provides an outlook into possible future research. 2 Literature Review 2.1 Introduction The problem discussed in this study is a multi-layered issue, and to answer the main research question, an investigation into two main fields is necessary: Design and Artificial Intelligence. Both are very broad fields of research and to narrow these further, and to address only the core matters of this enquiry, Generative Design (as part of Design), as well as Genetic Algorithms and Agents (both sub-fields of Artificial Intelligence) are discussed in more detail in the following literature review. These three main components address and inform the research questions, and specify the field of study in this thesis. This aids to identify the gap in existing knowledge, which this thesis attempts to fill. It is important to note, that a deeper look into Genetic Algorithms and Agents will be taken, and only briefly at Interactive Evolutionary Computation in general, in order to understand the prerequisites of Human-based Genetic Algorithms, which are the centre of the Artificial Intelligence section of this research. 2.2 Generative Design Generative Design, often also referred to as Procedural Design, is the area of form and shape finding by use of algorithmic help (Bohnacker, 2012). It is the overarching field that form finding is located in. There are some significant differences between manual design aided by computer software and automated design provided by computer software. This section of the literature review will help to understand where this research is placed. While Computer Aided Design (CAD) systems and other tools to create three dimensional objects with help of computers are technically based on algorithms and program code in general, they require the designer to manually operate the software and provide the inputs necessary to create any shape and form. Some of the processes may be partially automated, but the designer still needs to draw the objects on screen. These objects are often primitives such as circles, rectangles, cubes, spheres and other two or three dimensional shapes, which when combined, form the desired complex object (Greenberg, 2007). While this manual process lays the foundation for Generative Design, it is not part of this study, because the goal is to investigate automated or semiautomated design processes, driven by algorithms. Generative Design is the process of writing or applying often simple and small fragments of code that show objects on screen automatically, without the necessity to have the designer create underlying shapes in the first place (Greenberg, Xu, & Kumar, 2013). The creation of shapes is done by software, driven by an algorithm. The combination of many simple shapes, creates larger compound structures. These two or three dimensional structures (or objects) tend to be rather complex, given the simplicity of a few lines of code (Shiffman, 2012). For example, to create a complex procedural structure made of hundreds or thousands geometric primitives such as cubes and spheres, only 8 lines of code are required. These structures also often use recursive elements, i.e. functions or procedures that call themselves over and over again and therefore assemble a complex object from small, identical building blocks, much like some plants such as ferns or trees are complex structures that are made from very few, very simple individual elements (Reas & McWilliams, 2010). In case of the fern for example, the fractal or recursive nature is visible from a large scale to a microscopic level: The same shape is found over and over again, from plant to branch, and from branch to leaf, and so forth. This is usually referred to as self-similarity (Mandelbrot, 1983; Shiffman, 2012). In case of a procedurally modelled city, it is possible to apply some very similar techniques, while not fully self-similar, they are still based on repetition of simple building blocks, which when used in large numbers, resemble rather complex structures. An example would be windows on an office building, which are simple elements, but make up most of a large structure. Another example are streets. While most streets have similar, simple building blocks, as a whole they present a very complex and large system of gaps between buildings. Further, there is little evidence in the literature that a computer generated city has been made using Generative Design driven by the user in conjunction with algorithmic help. While there have been a few attempts to create procedural three dimensional cities as laid out by Parish and Müller (2001), these were entirely computer driven and provided no user interaction. This leads to a computer generated city as such, but does not reflect the designer’s intent at all. The city is a result of the programmer’s imagination and it can therefore be argued that it is similar to manual Computer Aided Design, with the difference that the user (or programmer) does not draw objects on screen, but writes code to create these objects. This study follows a different approach in that the user is enabled to influence the design and layout by choosing preferred layouts. Parish and Müller allow the user simply to run the software, which then produces a random result, which may or may not resemble the designer’s vision. There have also been other studies into components of generatively designed cities, for instance street structures or building structures (Lechner et al., 2004), but these researchers did not consider interactive user input at all. Therefore, this study aims to fill a significant gap in the existing literature, by using Generative Design driven by user interaction to create complex structures while seeking to reach the designer’s original vision. Using computers to explore the space of possible images, sculptures or other complex artistic forms such as musical compositions, has enabled researchers and artists to evolve pieces of art and led to the exploration of new ideas, from simple arbitrary color blobs to working functional forms such as boat designs, architectural forms or electronic circuits. Designers are being enabled to study more solutions in less time and to find forms that are outside the convention and expand their conceptual understanding. Evolutionary approaches have also led to new methods and principles, which can be exploited in future designs (Bentley, 2002). Bohnacker (2012) demonstrates a variety of typographic and abstract graphics in his book about Generative Design. Other examples include Generative Art using L-Systems (Pearson, 2011), Generative Design using very simple autonomous agents (Shiffman, 2012) and studies in Architecture (Reas & McWilliams, 2010), to name a few. Generative Design has become more common for a variety of reasons, the most significant probably being the abundance of computing power and also the arrival of suitable frameworks such as Processing (Greenberg et al., 2013) and Openframeworks (Perevalov, 2013). This study employs Generative Design for Infographics and Procedural Cities, by use of Processing (Greenberg et al., 2013) for the UI and 3Delight (“Welcome | 3delight,” 2014), a RenderMan compliant engine to create the actual CG images. 2.3 Artificial Intelligence In this section of the literature review a brief overview of the current understanding and discussion about intelligence and in particular artificial intelligence is given. Further, knowledge representation and finally problem solving is discussed. This will set the context for the Artificial Intelligence algorithms and paradigms explored in this study. While Artificial intelligence is understood to be located in the area of Intelligence in general, this research is concerned with Evolutionary Computation and Agents in particular as outlined in Figure 1. Figure 1 - Positioning Artificial Intelligence in the overall context (only relevant areas shown) 2.3.1 Definition of Artificial Intelligence In his book about Evolutionary Computation, David Fogel (2006) suggests that the term artificial intelligence itself, might be misleading. In Fogel’s view, intelligence just needs to be represented properly in form of a defined process to lose its artificial connotation. He claims that methods for generating intelligence need to be understood and applied in the same way, whether living beings, systems or machines are concerned, as these processes then become fundamentally similar and follow the same physics (Fogel, 2006). In this, he goes contrary to the majority of research in artificial intelligence, which has simply attempted to simulate intelligent behaviour as being shown by humans. Fogel proposes a definition independent of human behaviour, stating that intelligence is “the capability of a system to adapt its behaviour to meet its goals in a range of environments” (Fogel, 2006). This seems to be a very narrow definition compared to what other researchers such as Russell and Norvig (1994) break down into two main issues. Systems that imitate the thinking process of humans, and systems that attempt to model human behaviour, and respectively act like humans. The first could be represented by the research concerned with thinking or behaviour of humans. And the second, is reflected by the goal to imitate human behaviour, but idealize the behaviour first, to apply this ideal standard subsequently. The approach to imitate thinking is anchored in the interdisciplinary field of cognitive science, which combines AI computer models and experimental methods from psychology as well as neuroscience in an attempt to theorize how the human mind works, how humans think (Russell & Norvig, 1994). A popular example for the modelling of human behaviour is the Turing Test (Turing, 1950). The British mathematician Alan Turing proposed to use a simple test instead of lists of definitions that reflect intelligence. Using separate rooms, a man and a woman communicate to an interrogator only through a computer. The goal is to deceive the interrogator into believing that the man is a woman and vice versa. Then, in a second phase, the man is replaced by a computer. The goal stays the same, the computer is tasked to convince the interrogator that it is a woman, whereas the female participant tries to imitate the behaviour of a man. The computer would be able to make mistakes and provide unclear responses, just as a human might do. Turing assumed, that if the computer is able to deceive the human interrogator the same way the man did, it would have passed the intelligent behaviour test (Turing, 1950). Turing predicted in 1950, that a computer fifty years later would be able to stand the test successfully. While his prediction was not entirely accurate, contemporary research into cognitive science has achieved remarkable results. One of the most prominent examples for an approach based on cognitive science is IBM Watson, a supercomputer that imitates several different methods in the human thinking process in order to compete in Jeopardy games against human opponents (Ferrucci, Levas, Bagchi, Gondek, & Mueller, 2013). For instance, the main contribution to Watson’s successful strategies to understand the questions (or in case of Jeopardy, the answers) is the imitation of linguistic features such as narratives analysis derived from natural languages research (Lally et al., 2012). Using an expert system that derives the questions to the answers given in Jeopardy from a large database, would take too long and require too much storage by todays hardware and software standards. Instead, Watson imitates different processes of human behaviour to learn, understand and combine knowledge to be successful in the game (Prager, Brown, & Chu-Carroll, 2012). In this study, artificial intelligence is understood to be an imitation of human behaviour, as this research is concerned with systems that expose seemingly intelligent properties, and not with the cognitive process itself. Using methods that imitate human behavior leaves room to include systems that are classified as artificial intelligent approaches like optimization, search and knowledge engineering, contrary to Fogel’s rather narrow definition (Fogel, 2006). These additional systems are not necessarily adaptive, but rather statistical, and expose a behaviour similar to what is considered intelligence and therefore could be included in the broad field of intelligence and particularly artificial intelligence (Negnevitsky, 2004). This study makes use of both, adaptive as well as statistical optimization and search methods, as discussed in sections ​2.4 and ​2.5. Also noteworthy is the divide throughout the literature between hard AI and soft AI, basically referring to the difference of an AI system acting like a human, therefore mimicking human behaviour (hard AI), and using any technique that works to solve a particular problem in an seemingly intelligent way (soft AI).This topic is discussed in depth in context of autonomous agents in section ​2.5. 2.3.2 Artificial Intelligence Systems Buckland (2004) suggests that there a distinction has to be made between “Academic AI vs. Game AI” (Buckland, 2004) as Academic AI is concerned with an optimal solution to a problem, whereas Game AI is more concerned with the limitation of resources in order to keep the program using the Artificial Intelligence component interactive. While this is true in some cases, it is arguable that there are two implications with this viewpoint. First, there are many researchers in the field of Computer Science engaged in the topic of optimization of algorithms, which require the program to run as efficiently as possible, not just optimally: Algorithmic efficiency seeks to achieve results not just by optimization at any cost, but achieving optimization with the least resources possible. For example, many problems in applied computation and engineering need to be solved in a time critical manner and the systems incorporate a balanced approach between speed and optimization. An example is the Genetic Algorithm, which will be discussed in a later section (​2.4.1) of this thesis. The entire purpose of Genetic Algorithms is to solve an otherwise impossible (due to time constraints) problem in a reasonable timeframe. If that was not the intention, a brute force algorithm would certainly guarantee an optimal solution, given enough time. Second, in computer games and other applications, the issue of balance could lead to less engaging user experiences, if the resulting solution seems to be too ‘stupid’ to provide an exciting engagement. If the user loses interest or fatigues due to lack of quality, this would be similarly problematic as the lack of responsiveness. Academic research is concerned with finding different solutions in such cases, for example hybrid intelligent systems, which could offer a balance between speed and optimization (Negnevitsky, 2004). This is particularly relevant for this study, as it employs a hybrid intelligent system made of Genetic Algorithms, which are an Evolutionary Computation approach, in combination with human and computational agents. The details are shown throughout the following sections. 2.4 Evolutionary Computation Evolutionary Computation is the field of research that is concerned with computation based on the concepts of natural evolution. Figure 2 gives an overview of Evolutionary Figure 2 - Field of Evolutionary Computation Computation and its subfields. Specifically, it borrows ideas from Darwin’s theory of evolution, which states that individuals as part of a population increase their chances of survival and reproduction by way of natural selection. This selection process allows for small variations of each individuals’ properties, which are then passed on to the next generation through inheritance. Darwinism in conjunction with Mendel’s concept of genetics formed what is known in biology as modern evolutionary synthesis (Keeton, 1996). Biological evolution encapsulates the following concepts (Pimpale & Bhande, 2007): DNA (Deoxyribonucleic acid) is the molecular structure that encodes the genetic information of each cell of all living organisms. It is represented as a double helix. Chromosomes are strings of DNA. Genotype is the hereditary information encoded in the DNA. Phenotype are the observable properties as a result of the DNA. Reproduction is the creation of offspring by (usually) two parents, inheriting parts from both parents’ DNA. Crossover is the process of synthesizing an offspring DNA, creating a new chromosome. Mutation is a small accidental change in the offspring DNA, potentially resulting in slight variations to a straight, non-mutated crossover. Mutation happens with a very low probability. Survival of the fittest is the concept of only the strongest properties of a DNA being sustained over many reproduction cycles. Weaker DNA properties could result in weaker offspring, which in turn has a lower chance of survival. Over many generations, this leads to the elimination of weak DNA. This is also used synonymously with the term Evolution in the literature (Pimpale & Bhande, 2007). Modern evolutionary synthesis serves as the foundation for the many different types of evolutionary computation. While evolutionary computation borrows ideas and the notion of biological evolution from the natural process, evolutionary computation is merely an abstraction of evolutionary synthesis to emulate soft intelligent behaviour in computer software. The concepts were applied in different ways and evolved over time, so that there are now a multitude of different algorithms, which all borrow from the underlying idea of natural evolution. Examples are Genetic Algorithms (Holland, 1975), Evolution Strategies (Beyer & Schwefel, 2002) and Genetic Programming (Koza, 1992). While these all simulate natural evolution to an extent, they differ significantly in how they apply the evolutionary principles. Genetic Algorithms are heuristic search algorithms, used to find a solution in the space of all possible solutions. Evolution Strategies are designed to find solutions to technical optimization problems (Negnevitsky, 2004), and Genetic Programming generates computer programs that in turn attempt to solve the actual problem (Koza et al., 2003). Genetic Programming therefore programs computers by finding an optimal set of rules or section of code. This study uses Genetic Algorithms, which are detailed in the following section. 2.4.1 Genetic Algorithm The focus of this research is on Genetic Algorithms for two reasons. First, they are simple, yet powerful search algorithms. This study seeks to find at least one solution that fulfills the user’s intent within the virtually infinite number of possible city structures, shapes, layouts and forms. A search algorithm that is able to get to a result while other solutions such as random generation of cities might never create the vision of the designer, seems to be a reasonable choice, which is also strongly supported by existing research. Renner and Ekart (2003) conclude that “Genetic Algorithms are capable of solving surprisingly complex design problems”. Second, they have been successfully applied to much simpler, but somewhat similar design problems as presented in this thesis, for instance finding coloured blobs and stripes that reflect the intent of the designer in the solution space of all possible combinations of colour blobs and stripes (Anderson et al., 2008). This research seeks to extrapolate the positive results to the more complex design issue of Infographics and Procedural City models. Using the existing research into Genetic Algorithms for design problems, seems to be a solid starting point. Genetic Algorithms (GA), being part of the heuristic optimization or search algorithms, are very popular due to their relative simplicity, and are also well researched and understood (Fogel, 2006). They were introduced in the 1970s by John Holland and mimic natural evolution by abstracting the chromosomes into binary digits (Holland, 1975). These chromosomes are passed on from one population to a new population after genetics-inspired processes of crossover and mutation. An evaluation function called fitness function is then applied to establish each chromosome’s performance towards the final goal. If the chromosome performs poorly, it is likely to be dropped from the pool of future ‘parents’. Otherwise, if the chromosome’s fitness is high, it is more likely to be selected for reproduction. The actual reproduction process is performed by using a crossover operator, which mixes parts of two parent’s chromosomes to form the new child’s chromosome. Finally, a mutation operator is applied to some of the new found chromosome in order to ensure a certain variation of the child’s properties. This mutation operator randomly changes the value of individual digits of the chromosome binary string. Mutation operator and crossover operators effectively represent the probability of each operation (mutation and crossover) to happen. The process of simulating natural evolution is repeatedly applied for many generations and as a result, the fittest members of a population dominate, while the less fit become extinct. The underlying mechanisms of Genetic Algorithms are very simple, yet capable of showing seemingly complex behaviour and the ability to solve difficult problem sets

Author Jan Kruse Isbn 9781543196726 File size 4.1MB Year 2017 Pages 102 Language English File format PDF Category Information Technologies Book Description: FacebookTwitterGoogle+TumblrDiggMySpaceShare Modern films, games and virtual reality are highly dependent on convincing computer graphics. Models of high complexity are a requirement for the successful delivery of many animated scenes and environments. While workflows such as rendering, compositing and animation have been streamlined to accommodate increasing demands, modelling of complex models is still a laborious and costly task. This research introduces the computational benefits of Interactive Genetic Algorithms to computer graphics modelling while compensating the negative effects of user fatigue, a commonly found issue with Interactive Evolutionary Computation. A multi-agent system is used to integrate Genetic Algorithms with computational agents and human designers. This workflow accelerates the layout and distribution of basic elements to form highly complex models. It captures the designer’s intent through interaction, and encourages playful discovery. A modelling pipeline integrating commercially available tools with Human-based Genetic Algorithms is implemented, and a Renderman Interface Bytestream (RIB) archive output is realized to provide easy adaptability for research and industry applications. Comparisons between Interactive Genetic Algorithms and Human-based Genetic Algorithms applied to procedural modelling of computer graphics cities indicate that an agent-based evolutionary approach outperforms a purely human-centric solution: More iterations are possible in less time, which ultimately leads to better results and a superior user experience. Based on initial testing, a range of suggestions for future investigation are given.     Download (4.1MB) Mastering Autodesk Maya 2011 The Mathematica Graphics Guidebook Digital Character Development: Theory and Practice, Second Edition Real-time Rendering – Computer Graphics With Control Engineering Solutions Manual to Accompany Nonlinear Programming: Theory and Algorithms, 3 edition Load more posts

Leave a Reply

Your email address will not be published. Required fields are marked *