Tài liệu A 3-Dimension room design system with interactive genetic algorithm

A 3-Dimension Room Design System With Interactive Genetic Algorithm Ha Thi Kim Dung Faculty of Information Technology University of Engineering and Technology Vietnam National University, Hanoi Supervised by Assoc. Prof. Bui The Duy A thesis submitted in fulfillment of the requirements for the degree of Master of Computer Science June 2010 Acknowledgements This dissertation could not have been completed without support and encouragement from many people. My greatest gratitude is extended to: • My advisor, Bui The Duy, the best mentor I could have. My thesis would have been much harder without the wise guidance he gave. All I learned from him will be a great experience in my future career. • My college's teachers were devoted to give vast amount of knowledge. • My colleagues were enabling me to complete course. • Our classmates, the best friends I could have. 1 Originality Statement I hereby declare that this submission is my own work and to the best of my knowledge it contains no materials previously published or written by another person, or substantial proportions of material which have been accepted for the award of any other degree or diploma at University of Engineering and Technology or any other educational institution, except where due acknowledgement is made in the thesis. Any contribution made to the research by others, with whom i have worked at UET or elsewhere, is explicitly acknowledged in the thesis. I also declare that the intellectual content of this thesis is the product of my own work, except to the extent that assistance from others in the project's design and conception or in style, presentation and linguistic expression is acknowledged. Signed................................................................................................... 2 Table of Content Acknowledgements ....................................................................................................... 1 Originality Statement ................................................................................................... 2 Table of Content............................................................................................................ 3 List of Figures................................................................................................................ 4 List of Abbreviations .................................................................................................... 5 Abstract .......................................................................................................................... 6 Introduction ................................................................................................................... 7 Chapter 1: Related work .............................................................................................. 8 1. Genetic Algorithm versus Interactive Genetic Algorithm .................................................. 8 2. IGA-based design system ................................................................................................. 12 Chapter 2: Construction of a 3D Room Design System with Interactive Genetic Algorithm ..................................................................................................................... 21 1. Overview ........................................................................................................................... 21 2. Encoding and decoding a room design ............................................................................. 24 3. About roomfitness function, selection, crossover and mutation in the IGA ..................... 34 3. Experiments and results .................................................................................................... 37 Conclusion ................................................................................................................... 39 Reference ..................................................................................................................... 43 3 List of Figures • Figure 1.1: Crossover and Mutation • Figure 1.2: IGA processing • Figure 1.1: a female's dress design • Figure 1.4: An example of encoding arm-and-sleeve styles • Figure 1.5 : Chromosome encoding • Figure 1.6: Decoding from example genotype • Figure 1.7: User interface of the system • Figure 1.8: Chromosomes and the corresponding designs. (a) and (b) are two parents and show a crossover point, and (c) is the offspring generated by applying crossover to (a) and (b). • Figure 1.9: A chromosome of a Kimono • Figure 1.10: Example of crossover • Figure 1.11: User interface for selection of the first individuals • Figure 1.12: User interface after action of the button • Figure 1.13: Example of Yukata by using improved system • Figure 2.1: System overview • Figure 2.2: An example of choosing some colors in color set to • Initial color sets representing materials products made from • Figure 2.3: A 3D preview of a home • Figure 2.4 a: Using 2 bits to encode beds • Figure 2.4 b: Using 2 bits to encode chairs and another 2 bits to encode tables • Figure 2.4 c: Using 1 bits to encode wardrobes and another 2 bits to encode dressers. • Figure 2.4 d: Using 2 bits to encode windows • Figure 2.4 e: Using 3 bits to encode doors 4 • Figure 2.5: Genes of wooden color, iron color, leather color • Figure 2.6: Another colors • Figure 2.7: A chromosome • Figure 2.8: A visualization of a home • Figure 2.9: a pair of parents generate offspring • Figure 2.10: Run 1- Most of users rated in a muddle with only one user chose a desirable design. • Figure 2.11: Run 2 - at the ninth generation, users chose the best one • With highest fitness values are 7 and 8 • Figure 2.12: Run 3 - users chose the favorite designs from the seventh or the tenth generation. • Figure 2.13 a: 4 initial designs were rated with lowest values • Figure 2.13 b: new designs generated when evolution happened • Figure 2.13 c: After several steps, the evolution stopped because of 3 designs looked alike. List of Abbreviations • GA: Genetic Algorithm • IGA: Interactive Genetic Algorithm • CAD: Computer-Aided Design. 5 Abstract The thesis "A 3-Dimension Room Design System with Interactive Genetic Algorithm" will introduce an application of Interactive Genetic Algorithms (IGAs) to the problem of 3D room design. The major goal of the proposal is to help a user obtain a desirable 3D room design in an easy and fast way. Therefore, time cost of designing is reduced. The user only has to rate each presented design then the system will calculate and generate new designs based on the user's selections. More over, generating designs based on the choices of the user is one of potential ways to meet customer's taste, which always changes. 6 Introduction In the past, the concept of self-home design was not popular. Only masons, architects and a small part of people cared about it. The period from drawing a design to choosing home furniture to complete a home was very long. Nowadays, with the development of computer-aided design systems, time effort for designing and decorating is reduced. CAD products help a user not only express 2D design drawings but also visualize them with 3D perspective views. There are a lot of 3D modeling applications e.g. Maya, 3D Studio Max, Sketchup, InteriCAD, 3D studio VIZ, 3D Home Architecture, etc. However, they are all specialized applications intended for professional designers. It is too difficult for beginners to be able to use them. Hence, time cost to complete a favorite home is often very high. Even with architects, they also take long time to design. They must create or choose a model of furniture, cover it with a color or a texture, combine to another one and then decide what kind of the scheming and perspective is acceptable. In the thesis, we propose a new approach that integrates an Interactive Genetic Algorithm (IGA) to a 3D room design to reduce time cost of designing. With this approach, the system repeatedly present several designs based on user's preference. The preference is expressed through their rates of designs. The system will calculate and generate new designs from current rated designs. It will reduce designing time because it creates automatically the scheme between models of furniture. Interactive Genetic Algorithm is similar to genetic algorithm except user fitness function. The user fitness function gets user's choices to be an input then results fitness values. The higher values are used to auto-generate new room designs until user accepts. Actually, IGA is a searching problem that helps users find out desirable designs without trying all cases in search space. Moreover, basing on user's choices is one of potential ways to meet user's taste, which always changes. The thesis is organized as follows: Chapter 1 presents related work. In this chapter, we will introduce some information about GA, IGA and some IGA-based design systems. In chapter 2, we recommend about the new approach of applying Interactive Genetic Algorithm in 3D Room Design System. We also present some information about experiments and results. 7 Chapter 1: Related work 1. Genetic Algorithm versus Interactive Genetic Algorithm Genetic Algorithm (GA) was proposed by John Holland in early 1970s. It based on Darwin's theory about evolution. It applies some of natural evolution steps like crossover, mutation, and replace. Algorithm started with a set of solutions (represented by chromosomes) called population. Solutions from one population are taken and used to form a new population (called offspring). The evolution makes the thinking that the new population will be better than the old one. Solutions, which form new solutions, are selected according to their fitness values. Which solutions have higher fitness values; they will have more chances to reproduce. These works are repeated until some conditions (for example number of populations or improvement of the best solution) are satisfied. The algorithm is applied to many problems of optimization and classification, etc. The GA algorithm is following [2]: 1 2 3 4 5 6 [Start] Generate random population of n chromosomes (suitable solutions for the problem) [Fitness] Evaluate the fitness f(x) of each chromosome x in the population. [New population] Create a new population by repeating following steps until the new population is complete a. [Selection] Select two parent chromosomes from a population according to their fitness (the better fitness, the bigger chance to be selected). b. [Crossover] With a crossover probability cross over the parents to form a new offspring (children). If no crossover was performed, offspring is an exact copy of parents. c. [Mutation] With a mutation probability, mutate new offspring at each locus (position in chromosome). d. [Accepting] Place new offspring in a new population [Replace] Use new generated population for a further run of algorithm. [Test] If the end condition is satisfied, stop, and return the best solution in current population. [Loop] Go to step 2. 8 Figure 1.1: Crossover and Mutation [1] Chromosomes chosen are usually better than other ones in hoping that better parents can generate better offspring. Nevertheless, it is possible to lost best chromosomes from last population. Therefore, elitism phenomenon is applied that best solutions will be copied from last population to new one. The common way used to encode each chromosome is a binary string encoding. Here is an example of chromosome encoding: Chromosome 1 1011010001001 Chromosome 2 1010101010101 Each bit or a bit group represents a characteristic of the solution. They call genes. To generate a new population, chromosomes need to exchange some bits with each other. This step called Crossover operator. The simplest way to do this is to choose randomly some crossover point for all parents, then swap the front part of Chromosome 1 to the front one of Chromosome 1. Here is an example of crossover: 9 Chromosome 1 1011|010001001 Chromosome 2 1010|101010101 Offspring 1 1010010001001 Offspring 2 1011101010101 Like crossover of genes in real world, offspring inherit characteristics from parents. Mutation operation reverses some bits in the binary string at very low rate. After a crossover is performed, mutation step takes place. This is to prevent falling all solutions in population into a local optimum of solved problem [2]. Mutation changes at random positions in chromosomes of the new generation. For binary encoding, we can switch a few randomly chosen bits from 1 to 0 or from 0 to 1. Mutation can then be following: Original 1 1010010001001 Original 2 1011101010101 Mutated 1 1011010001001 Mutated 2 1011101110101 Selection operator selects solutions from population based on fitness values of individuals. A fitness function prescribes the optimality of a solution so that a particular chromosome is ranked against all the other chromosomes. Optimal chromosomes, or at least chromosomes which are more optimal, are allowed to breed and mix their datasets by any of several techniques, producing a new generation that will be even better. An ideal fitness function correlates closely with the algorithm's goal, and yet may be computed quickly. Speed of execution is very important, as a typical genetic algorithm must be iterated many, many times in order to produce a usable result for a non-trivial problem. This is one of the main drawbacks of GAs in real world applications and limits their applicability in some industries. 10 Definition of the fitness function is not straightforward in many cases and often is performed iteratively if the fittest solutions produced by GA are not what is desired. In some cases, it is very hard or impossible to come up even with a guess of what fitness function definition might be. Interactive genetic algorithms address this difficulty by outsourcing evaluation to external agents (normally humans). Interactive Genetic Algorithm, one type of Interactive Evolutionary Computation (IEC) or Aesthetic Selection problems is a general term for methods of evolutionary computation that use human evaluation. Usually human evaluation is necessary when the form of fitness function is unknown (for example, visual appeal or attractiveness; as in Dawkins, 1986) or the result of optimization should fit a particular user preference (for example, taste of coffee or color set of the user interface) [13]. Interactive Genetic Algorithm is the same as GA except fitness function. In IGA user gives fitness to each individual instead of fitness function. Therefore, the system can meet user's expectation or what a customer's preference in the course of evolution. Actually, the Selection step in the algorithm applied in home decorating can be understood that "What kind of decoration is better?" and "better", "good", "bad" definitely depend on human's sense. IGA may be one of the solutions for this problem. Figure 1.2 is the visualization of IGA. 11 Figure 1.2: IGA processing Next, we will present some available design systems integrated IGA to improve the capability of user-oriented design. 1. IGA-based design system When researching about using IGA in 3D design, there have two outstanding proposals we explored. Hee-Su Kim and Sung-Bae Cho proposed one [1]. They created a 3D design IGA-based system for fashion design. In this system, they designed female's dresses. They divided a dress into seven parts: 12 Figure 1.3: a female's dress design There was a database of partial design elements. Each design was stored as 3D models. System selected the models of each part and combined them into a number of individual designs. The population was displayed and user gave fitness values to each design. Then, system reproduced the population according to the fitness value of each design, and applied crossover and mutation to make the next generation. As they mentioned, iteration of these processes could produce the population of higher fitness value, namely better designs. This system works with OpenGL and VRML. They encoded the detail model based on the knowledge of the fashion design. First, they reclassified general detail factors of a dress into some parts then encoded them with some bits for each, which chooses the color of each part. A design was made from combining them. With IGA, some combinations that preferred by user was generated, resulting in more realistic and reasonable design. 13 Figure 1.4: An example of encoding arm-and-sleeve styles 14 Figure 1.5 : Chromosome encoding Figure 1.6: Decoding from example genotype 15 Figure 1.7: User interface of the system 16 Figure 1.8: Chromosomes and the corresponding designs. (a) and (b) are two parents and show a crossover point, and (c) is the offspring generated by applying crossover to (a) and (b) The system was built very completed and potential. The design of this system is quite similar to 3D room design system we want to build. The next one is proposed by Maiko Sugahara, Mitsunori Miki, And Tomoyuki Hiroyasu to design an IGA-based system of Japanese Kimono (Yukata). [15] This system did not dividing and encoding each sample like the system mentioned earlier. They divided a Kimono into three parts: Yukata fabric, obi and pattern. Yukata fabric is a kind of material. Obi is a part of a Kimono and pattern is decorated-sample of a Kimono. Each part was encoded with bit genes representing to three colorelements of HSB. The HSB color system is based on three different ways of varying color as Hue, a particular gradation of color; Saturation, the vividness of hue; Brightness, the percentage of brightness of the color [16]. 17 Figure 1.9: A chromosome of a Kimono Figure 1.10: Example of crossover 18 Figure 1.11: User interface for selection of the first individuals Figure 1.12: User interface after action of the button 19