Содержание
- Introduction
- 1. topicality Topics.
- 2. Goal and tasks of the research
- 3. Review of Research and Development
- 4.Representation of real solutions in binary form
- Conclusion
- References
Introduction
At the present time is rapidly developing a new direction in theory and practice of artificial intelligence - evolutionary computation (EC). Features of the ideas of evolution and self-organization lies in the fact that they are confirmed not only for biological systems, developing many billions of years. These ideas have now been successfully used for the development of many technical and, in particular, software systems. Genetic algorithms (GAs) were developed by American researcher Holland. Goldberg (student of Holland) has successfully developed and expanded the field of Civil Aviation of its application. Also in the 60s in Germany I. Rechenberg laid the foundations of "evolutionary strategies" (ES). In science and evolutionary computation techniques are used as adaptive algorithms for solving practical problems and as a computational model of the evolution of natural systems. EV have been successfully used in solving complex problems in technical development and business. With the EV industry has developed many design decisions that will save millions of dollars. EV is widely used to predict the development of financial markets, investments, etc. EV Methods commonly used for evaluation and selection of (sub) optimal continuous parameter models of large dimension, for a variety of NP-complete combinatorial problems in systems extracting knowledge from large databases (Data mining) and many other fields of science and technology. Once the computer systems are fast enough and affordable EV become a major tool for searching suboptimal solutions of the problems that were previously considered intractable.
1. topicality Topics
Master's thesis is devoted to actual scientific problem of development of WEB-interface for the implementation of the genetic algorithm. GA uses principles and terminology borrowed from the biological science - genetics. In GA, each individual represents a potential solution to some problem. In the classical GA individual encodes a string of binary digits - chromosome, each bit is called the genome. Many individuals - a population of potential solutions. Search for (sub) optimal solution is performed in the course of the evolution of the population - a sequential conversion of a finite set of solutions to another by means of genetic operators reproduction, crossover and mutation. EV uses the following mechanisms of natural evolution: 1) The first principle is based on the concept of survival of the fittest and natural selection according to Darwin, which was formulated by him in 1859 in his book "The Origin of Species by Means of Natural Selection." According to Darwin, individuals are better able to solve problems in their environment survive and reproduce more (reproduces). In genetic algorithms, each individual represents a solution to some problem. By analogy with this principle, individuals with the best values ??of the target (fitness) functions have a greater chance to survive and reproduce. The formalization of this principle, as we shall see, gives the operator of reproduction. 2) The second principle is due to the fact that the child chromosome is composed of parts of chromosomes derived from parents. This principle was discovered in 1865 by Mendel. Its formalization provides a basis for the operator of mating (crossover). 3) The third principle is based on the concept of mutation, discovered in 1900 de time. Originally, the term used to describe material (abrupt) changes in the properties of their descendants, and the acquisition of properties that are absent from their parents. By analogy with the principle of genetic algorithms use a similar mechanism for abrupt changes in the properties of descendants, and thus, increase the diversity (variation) of individuals in the population (the set of solutions).
2. Goal and tasks of the research
In my master's paper describes the implementation of the classical genetic algorithm using the programming language PHP. The main purpose of the study is to develop a WEB-interface to work with a genetic algorithm. The main objectives of the study: A. Give the main stages of development of WEB-interface Two. Describe the operation of genetic algorithm, lead to the block diagram. Three. Create a program in PHP 4. Develop an application that shows the algorithm.
3. Review of Research and Development
Genetic algorithms (GAs) were developed by American researcher Holland. Goldberg (student of Holland) has successfully developed and expanded the field of Civil Aviation of its application. Also in the 60s in Germany I. Rechenberg laid the foundations of "evolutionary strategies" (ES). The basis of this work was based on three principle mechanisms of natural evolution: 1) the principle of natural selection according to Darwin, which was formulated by him in 1859 in his book "The Origin of Species by Means of Natural Selection." 2) The principle of which is due to the fact that the child chromosome is composed of parts of chromosomes derived from parents. This principle was discovered in 1865 by Mendel. Its formalization provides a basis for the operator of mating (crossover). 3) The third principle is based on the concept of mutation, discovered in 1900 de time.
4. Predstavlenie real solutions in binary form
In the previous example we have considered only integer solutions. We generalize to the case of GA real numbers in the following example in which the function f (x) = (1,85-x) * cos (3,5 x - 0,5), presented at the ris.1.5 need to find the real, which maximizes f, ie is such that for all x.
Пример функции с популяцией особей в начале эволюции
We need to build a GA to solve this problem. To represent a real solution (chromosome), we use a binary vector, which is used in a classical simple GA. Its length depends on the required accuracy of the solution, which in this case, we set three decimal places. Since the segment has a length of 20 solutions to achieve the specified accuracy of the interval [-10, 10] should be divided into equal parts, the number of which shall be not less than 20 * 1000. As the binary representation of numbers using a binary code segment. This code allows you to define the corresponding real number, if known to the boundary of the solution. It follows that the binary vector to encode a real solution should be 15 bits, as 16384 = <20000 This allows you to split the interval [-10, 10] to 32,768 units and provide the necessary accuracy. The mapping of the binary representation of () () is a real number in the interval [-10, 10] is performed in two steps. 1) Transfer of a binary number to decimal: 2) The calculation of the corresponding real number x: Where the - 10 the left boundary of the solution. Naturally chromosome (000000000000000), and (111111111111111) represent the boundaries of the segment 10 and 10, respectively. Obviously, given the binary representation of real numbers, you can use the classical simple GA. On-ris.1.5 ris.1.8 represented the location of individuals - potential solutions at various stages of the GA in the search for solutions. Figure 1.5 shows the initial population of potential solutions, which uniformly covers the area to find a solution. Next, clearly shows how gradually with increasing numbers of individuals of generation "condense" in the vicinity of the extrema and eventually found a better solution.
Рисунок 2 – Начальная «конденсация» особей популяции в окрестностях экстремумов
Конденсация» особей в окрестностях эксремумов
Рисунок 4 – Положение особей популяции в конце эволюции
Рисунок 5 – Положение особей популяции в конце эволюции
Conclusion
The objective of this course project was to realize WEB-interface that implements a genetic algorithm. This WEB-interface has been successfully created, tested its functionality and efficiency.