GENETIC ALGORITHM IMPLEMENTATION ON JIGSAW CROSSWORDS
CHAPTER I
INTRODUCTION
1.1 BACKGROUND PROBLEM
Many efforts are made to obtain the maximum benefit with the least possible expenditure. Along with the development of science and technology, then one way to achieve that goal is the optimization. Optimization is the search for the values of variables that are considered optimal for achieving the desired results. This optimization problem vary depending on the field. In this paper, an optimization problem to be discussed is the creation of crossword puzzles. Application of optimization is to maximize filling the empty spaces. To solve the optimization problem is, of course, needed a reliable algorithm.
Crossword puzzle is a game to sharpen the brain. Crossword puzzles can be used in education to test the ability of students, so the questions are tailored to the needs of any use. To create a crossword puzzle can be said to be easy, easy because we just combine words with each other. But it will be difficult if the number of questions used a lot, because to make a crossword puzzle of a set of questions, we have to try possible combinations of existing words to form a crossword. The more the number of questions, the more combinations that we must try. In optimization, the application of genetic algorithms are used to obtain a preparation pattern of words in the empty spaces of the most optimal. To determine whether or not optimal filling the empty space, done by looking at the number of word combinations that can be made or can also be seen from the many remaining empty space is a crossword puzzle. So, the more and better combinations of words are made to fill the empty spaces, then the optimal charging them. This solution can be overcome when creating crossword puzzles done automatically by computer.
1.2 FORMULATION OF THE PROBLEM
Issues to be discussed in this paper is how to make the combination of a set of answers to questions so as to form a crossword puzzle using a genetic algorithm.
1.3 LIMITATION OF PROBLEMS
The author limits this thesis research on:
1. Crossword puzzles are made is a crossword puzzle in the form we know today.Questions are divided into two categories: flat and declining.
2. As with TTS in general, the character used to fill the TTS box only characters A. .. Z.
3. If the reply contains characters other than letters A.. Z, then the characters are ignored. For example, if the answer of a question is a butterfly then written into kupukupu.
4. Answer landscape questions should not be arranged horizontally concatenated with answers to questions, and answers to questions should not be composed continued to decline to answer questions decreased.
1.4 RESEARCH OBJECTIVES
To create an application that can make a crossword puzzle based on the questions entered by the user by using a genetic algorithm.
1.5 BENEFITS OF RESEARCH
The benefits of this research is to facilitate in making a crossword puzzle with questions that can be determined solely by the user.
1.6 Systematics of the Writing
This final project consisting of five chapters to the subject of each chapter are:
Chapter I. INTRODUCTION
This chapter contains the background, formulation of the problem, boundary issues, the purpose of research, the benefits of research, research methods and systematic writing.
Chapter II. BASIS OF THEORY
This chapter contains the basic theory used to create applications. In this chapter explained about crossword puzzles and genetic algorithms. Described here also the terms and processes used in genetic algorithms.
Chapter III. RESEARCH METHODOLOGY
This chapter discusses the explanation of the steps in designing a crossword puzzle.
Chapter IV. ANALYSIS AND DESIGN
This chapter discusses the analysis and design of the system on a crossword puzzle.
Chapter V. RESULTS AND DISCUSSION
This chapter discusses the results obtained from testing the system crossword puzzles.
Chapter VI. CLOSING
Cover contains some conclusions obtained from the design and testing performed, also contains suggestions for development in the future.
Crossword puzzle is a game to sharpen the brain. Crossword puzzles can be used in education to test the ability of students, so the questions are tailored to the needs of any use. To create a crossword puzzle can be said to be easy, easy because we just combine words with each other. But it will be difficult if the number of questions used a lot, because to make a crossword puzzle of a set of questions, we have to try possible combinations of existing words to form a crossword. The more the number of questions, the more combinations that we must try. In optimization, the application of genetic algorithms are used to obtain a preparation pattern of words in the empty spaces of the most optimal. To determine whether or not optimal filling the empty space, done by looking at the number of word combinations that can be made or can also be seen from the many remaining empty space is a crossword puzzle. So, the more and better combinations of words are made to fill the empty spaces, then the optimal charging them. This solution can be overcome when creating crossword puzzles done automatically by computer.
1.2 FORMULATION OF THE PROBLEM
Issues to be discussed in this paper is how to make the combination of a set of answers to questions so as to form a crossword puzzle using a genetic algorithm.
1.3 LIMITATION OF PROBLEMS
The author limits this thesis research on:
1. Crossword puzzles are made is a crossword puzzle in the form we know today.Questions are divided into two categories: flat and declining.
2. As with TTS in general, the character used to fill the TTS box only characters A. .. Z.
3. If the reply contains characters other than letters A.. Z, then the characters are ignored. For example, if the answer of a question is a butterfly then written into kupukupu.
4. Answer landscape questions should not be arranged horizontally concatenated with answers to questions, and answers to questions should not be composed continued to decline to answer questions decreased.
1.4 RESEARCH OBJECTIVES
To create an application that can make a crossword puzzle based on the questions entered by the user by using a genetic algorithm.
1.5 BENEFITS OF RESEARCH
The benefits of this research is to facilitate in making a crossword puzzle with questions that can be determined solely by the user.
1.6 Systematics of the Writing
This final project consisting of five chapters to the subject of each chapter are:
Chapter I. INTRODUCTION
This chapter contains the background, formulation of the problem, boundary issues, the purpose of research, the benefits of research, research methods and systematic writing.
Chapter II. BASIS OF THEORY
This chapter contains the basic theory used to create applications. In this chapter explained about crossword puzzles and genetic algorithms. Described here also the terms and processes used in genetic algorithms.
Chapter III. RESEARCH METHODOLOGY
This chapter discusses the explanation of the steps in designing a crossword puzzle.
Chapter IV. ANALYSIS AND DESIGN
This chapter discusses the analysis and design of the system on a crossword puzzle.
Chapter V. RESULTS AND DISCUSSION
This chapter discusses the results obtained from testing the system crossword puzzles.
Chapter VI. CLOSING
Cover contains some conclusions obtained from the design and testing performed, also contains suggestions for development in the future.
CHAPTER II
BASIS OF THEORY
2.1 Cross Puzzle
Crossword puzzles or abbreviated TTS is a game that requires users to fill empty spaces with the letters that make up a word based on instructions given (wikipedia, 2007). Usual instructions are divided into categories depending on horizontal and decreased word positions to be filled.Crossword puzzles (TTS) was first published in New York's World magazine in a format similar to a crossword puzzle that is known at this time. Puzzles that are often referred to as the crossword puzzle first discovered by Wynne. TTS then became a weekly feature in the magazine. In subsequent developments TTS not only become a magazine feature. The first collection of crossword books published by Simon and Schuster in 1924. TTS becomes one of the most popular objects of that era. In Indonesia alone, the development of crosswords began in the 1970s. At that time in Jakarta published "Brain", a magazine crossword and other puzzles. This publication was also some success so many similar publications that followed.
2.2 Genetic Algorithm
Genetic algorithm is a search algorithm (searching) by way of working through the mechanism of natural selection and genetics. The goal is to determine the structures of the so-called high-quality individuals in a domain called the population to get the problem solution.
In 1975, John Holland introduced genetic algorithms for the first time. Genetic algorithms differ from conventional algorithms because it starts from an initial set of known populations. Genetic algorithms use two basic principles in biological systems, namely the selection of species present and the increased diversity (genes with genetic operations).
2.3 Genetic Algorithm Parameters
Scheme of genetic algorithm to determine how the process of genetic algorithm, so the process is also necessary to determine the genetic algorithm parameters to be used, as follows:
2.3.1 Size of population
Population size is the number of chromosomes that exist in the population.Chromosome represents the form of a crossword puzzle. Choosing the right population size will improve the performance of genetic algorithms. If the population size is too small, then the genetic algorithm has only a few alternative solutions.However, if the population size is too large, the genetic algorithm process will be slow.
2.3.2 Number of generations
The process starts from a series of genetic algorithm selection process, crossover (crossover), mutation to update generation. The process of genetic algorithm will be terminated if the number of generations has been fulfilled. The solution is taken chromosomes with fitness values (the feasibility) the best of the last generation.
2.3.3 Crossover probability (chance of crossing over)
Opportunities crossover (PC) will determine the number of crossovers (crossovers) that occurred. PC value ranges from 0 to 1. If the PC value equal to 1, then the entire chromosome will experience a crossover. If your PC is equal to 0, then the crossover will not occur, or in other words the chromosomes in offspring (child of chromosome crossovers) will be equal to the parent chromosome (chromosome parent).
2.4 Chromosome Representation and Pattern
In the concept of biological sciences recognized the existence of the term cell. Cells are the smallest parts that make up an organism. In general, an organism composed of cells making. A cell is composed of a collection of some chromosomes. A chromosome is composed of several genes. Genes are a set of DNA (Deoxyribo Nucleic Acid). Such a biological concept, adapted to the genetic algorithm. In genetic algorithm, chromosome is an alternative solution of a problem.Chromosomes can be presented in several forms according to the type of encoding used.
2.4.1 Encoding of chromosome
Coding is an essential part in resolving a problem with a genetic algorithm. The coding is pengkorversian problems in the real world into a form that can be processed using a genetic algorithm. Encoding a highly precise process determines the success or failure of a genetic algorithm to solve the problem.Proper coding will also determine the level of computational efficiency is used.
There are several types of coding that can be used in genetic algorithms, including binary encoding (binary encoding) and the coding of permutations (permutation encoding).
2.4.1.1 Encoding binary (binary encoding)
Binary encoding is an encoding that is often used and simplest. As the name implies, the gene encoding the binary value in a chromosome consists of only 0 and 1.
2.4.1.2 Encoding permutations
Permutation encoding can be used to resolve the ordering problems, such as the traveling salesman problem and scheduling problems. In the permutation coding sequence or the position of genes on chromosome represents the sequence of a process. In no value encoding permutations of the same gene in a chromosome.Examples of cases that can be solved by the permutation encoding is TSP (traveling salesman problem). Traveling salesman problem is the way how to determine the minimal route to visit some places or cities. If there are 10 cities to be visited, then it will have one chromosome 10 genes, where each gene represents a city. Position or sequence of genes in the chromosomes determine the order of the city that must be passed.
On chromosome 1 means the first city visited is a city, then city 2 and so forth until the city 10.
2.4.2 fitness value (the value of eligibility) and the objective function (objective function)
In the evolutionary process of individuals who survive (survival) of the process of natural selection will have the opportunity to reproduce again. Thus, the ability of individuals to be able to adapt and survive to survive is crucial. In the terminology of genetic algorithms the ability of an individual (chromosome) to survive can be measured by its fitness value. The better the fitness value (the feasibility) of a chromosome, the better the chances of the chromosome to survive and participate in the process of reproduction. The fitness of a chromosome can be calculated by using the objective function.
2.4.3 Selection
The selection process aims to select chromosomes that will serve as the parent (parent chromosomes) in the process of crossover (crossover). There are several methods that can be selected in the selection process, such as Roulette Wheel Selection, Rank Selection and Tournament Selection.
2.4.3.1 Roulette wheel selection
In roulette wheel selection, the chromosomes will be selected randomly determined by calculating the value of the feasibility of each chromosome. The greater the value of the feasibility of a chromosome, the greater the chances are for selected chromosomes as the parent (parent chromosomes). Encoding the roulette wheel may be analogous to such a game wheel. In the game wheel, wheel circle is divided into several regions. In roulette wheel selection, the width of a chromosomal region is determined by its fitness value, the greater its fitness value, the larger the territory, and the greater the chances are for selected chromosomes.
Roulette wheel selection process is described in the algorithm as follows:
1. [Sum] Add up all the fitness values (the feasibility) of each chromosome in the population of S.
2. [Select] Generate random numbers in the interval (0, S)-r.
3. [Loop] sequentially from the first chromosome, chromosome fitness values sum-s.if the i-th chromosome s> r then stop, then i selected as candidate chromosome parent.
In the above table it can be concluded that pupulasi size is 5. The value is the accumulated value of the fitness value of chromosome 1 to chromosome to i. To select chromosomes that will be a prospective parent then generated random numbers (0, S). Random numbers are generated as many as 5 pieces according to size of population. If ri <Si and ri> Si-1 then the chromosome is a chromosome chosen to i. In the table above, r1 = 35, since 35 <S3 (60) and 35> S2 (30) then the selected chromosome is chromosome 3.
CHAPTER III
RESEARCH METHODOLOGY
3.1 Research FrameworkThe framework of this study show the pattern of student thinking when starting and ending a research activity which is reflected in the flow diagram of the study.
3.2 Explanation of Research Framework
3.2.1 Data Collection
This stage is important because as the foundation stage of manufacturing Final, by way of conducting interviews and questionnaires to collect data that has been propagated.
3.2.2 Identification of Problem
At this stage, to identify issues to be discussed, the factors that influence as discussed in Chapter I as well as further analysis of the system to be developed.
3.2.3 Analysis of Problems
After making the identification problem, the next stage is the stage of analysis.Analysis was the analysis of the system needs to be designed, in the form of the input system.
3.2.4 Overview References
Writer looking for theories from various sources such as reference books and also through the internet relating to the writing on this thesis.
3.2.5 Designing Applications
Designing Display
- STD (State Transition Diagram): Describe the sequences to be used in running the program.
- The design interface is a design program that will build a program based on VB.net.
3.2.6 Preparation of Coding
At this stage, the program has been created translated into a form that can be read by the machine if the design implemented in detail. Coding can be done mechanically.
3.2.7 Implementation
Once the program is successfully created, the next step is a trial program. When the program is user friendly then this program can be used for teaching and learning process. If not, then go back to the design.
3.2.8 Preparation of Report
If the process of testing or implementation has been used and successfully completed the program have been completed. Once the program design process is completed, it will be a discussion of design, followed by inferences, process and report writing.
3.3 Equipment and Materials
3.3.1 Software Used
a. Operating Systems Windows 7 Ultimate
b. Asp.net
c. Microsoft Office Word 2007
d. Microsoft Office Visio 2007
3.3.2 Hardware used
a. Processor AMD Turion X2 Ultra
b. Memory (RAM) 2048 MB
c. 300 GB HDD
d. Mouse and Keyboard
The material used is data - data that are input alphabet.
3.4 Study Site
Location study of the design process until the trial carried out in house writers and Campus STT-PLN.
