Table of Contents1. Overview of Genetic Algorithms and Applications……………………………………………………31.1 What is Metaheuristic…………………… ……………………………………………………31.2 Understanding Genetic Algorithms and its applications………… …………………….31.2.1 Introduction to genetic algorithm:……………………. ……………………..31.2.2 Main steps of genetic algorithm:……………………………………………………. ……………………..41.2.3 Basic components of a genetic algorithm……………………………………………………. 41.2.4 General genetic algorithm structure ……………………………………….62. Applying genetic algorithm to the problem of predicting a 6-digit password…………………….92.1. Introduction of the problem……………………………………………………..92.2. Design genetic algorithm to predict password……………………………………………………112.3 Implement genetic algorithm using C#……………… ……………………………………………………112.4 Main screen:…………………………………………………… …………………….143. Conclude……………………………………………………………………………………………………………………………… 14References………………………………………………………………………………………………..1511 . Overview of Genetic Algorithms and Applications.1.1 What is Metaheuristic Metaheuristic is a general term for heuristic algorithms in solving difficult combinatorial problems. Metaheuristics include different strategies for exploring the search space using different methods and must strike a balance between the diversity and depth of the search space. A successful implementation of metaheuristics in a combinatorial problem must balance the exploitation of the experience gained during the search to identify regions with near-optimal high-quality solutions. Examples of metaheuristics include Steel Algorithm (SA – Simulated Annealing), Genetic Algorithm (GA), Ant Colony Algorithm (ACO), Tabu Search (Tabu Search) 1.2 Learn Genetic Algorithms and Application 1.2.1 Introduction to genetic algorithms: Genetic Algorithms roughly translated as Genetic Algorithms (shortly called GA) originates from the concept of evolution to survive and develop in nature. GA is a method of problem solving. imitating human behavior to survive and develop. It helps to find the optimal or best solution in terms of time and space permitting. GA considers all solutions, by first considering several solutions, then removing the inappropriate components and selecting more adaptive components to generate and transform in order to create many new solutions with increasingly high coefficient of fitness Adaptation coefficient to use as a standard for evaluating solutions.Data structure + genetic algorithm = evolutionary program. The term “evolution program” in the above formula is a term used to refer to computer programs that use search and optimization algorithms based on the principle of natural evolution1.2.2 Steps Main of genetic algorithm: Step 1: Choose a model to represent the solutions. Models can be Strings of binary numbers: 1 and 0, decimal, and can be alphanumeric or mixed alphanumeric.Step 2: Select an appropriate function to use as a criterion for evaluating solutions. .2Step 3: Continue the transformations until the best solutions are reached or until time permits.1.2.3 Basic components of genetic algorithms Hybridization (permit) cross) + Randomly select any two (or more) individuals in the population. Assume that each parent’s chromosomes have m genes.+Generate a random number between 1 and m-1 (we call it the point of hybridization).+Inject these two new individuals into the population to participate in the processes. next evolution. Mutation process (mutation)+Randomly select an individual from any parent in the population.+Generate a random number k between 1 and m, 1 ≤ k ≤ m. +Change the kth gene and return this individual to the population to evaluate the next evolutionary process Reproduction process+Calculate the fitness of each individual in the current population, make a cumulative table of fitness values (according to the number assigned to each individual). Assume that the population has n individuals. Let the fitness of the ith individual be Fi, the ith cumulative sum Fti, the total fitness of the entire population Fm.+Generate a random number F in the range from 0 to Fm.+Choose the first kth individual The first that satisfies F ≥ Ftk is introduced into the population of the new generation. Each pair of parents gives birth to two offspring by one of the following two methods+AsexualityEach infant is an exact copy from the fatherEach infant is an exact copy from the father. mother+sexual (intersection)Some bits are copied from the mother, some bits are copied from the father3Keep copying from one parent pair until the point of intersection, then copy from the other parent pair. Process selection+Sort the population in descending order of fitness.+Remove the last individuals in the sequence to keep only the best n individuals. Here, the population is assumed to have a fixed size n. Stopping condition of the algorithm: We will investigate the simplest condition to stop when the number of generations exceeds a given threshold. In some versions of the evolutionary program not all individuals evolve again. Some of them have the ability to pass from generation to generation without changing at all. In such cases, we count the number of times the number of functions. If the number of times the number of functions exceeds a predefined constant, the search is stopped. We see, the above stopping conditions assume that the user already knows the characteristic. function, and how it affects the search length. In some cases it is difficult to determine how many generations (or function evaluations) should be. The algorithm may end when the opportunity for a significant improvement has not yet begun. There are two basic types of stopping conditions. These conditions use search features to decide to stop the search process.-Based on chromosome structure: due to the convergence of the population by controlling the number of alleles that are converged, here alleles are considered as convergent. convergent if a predetermined population percentage has the same (or equivalent for non-binary representations) value in this allele. If the number of convergent alleles exceeds a certain percentage of the total number of alleles, the search is terminated.-Based on the special significance of a chromosome: measure the progress of the algorithm over a given number of generations. If this progress is less than a definite constant ε, end the search.1.2.4 General genetic algorithm structureStart4t = 0;Initialize P(t);Calculate fitness for individuals of P(t) );When (stopping condition is not satisfied) repeat t = t+1;Regenerate P'(t) from P(t);Hybrid Q(t) from P(t-1); Mutation R(t) from P(t-1);Selection of P(t) from P(t-1) U Q(t) U R(t) U P(t); End of iteration End.1.2.5 Genetic Algorithms Compared to Traditional Methods We consider the following simple problem: optimizing the function y = f(x) on the specified interval D. When using the traditional method, there are several solutions as follows: Enumeration method: Iterate over all points lying in the survey area D to find its extreme point. This method is not suitable when the input data is too large. In this case, the domain D has too large a space to be counted. Analytical method: Find the extreme point by solving the set of equations when the Gradient is equal to 0. To calculate the Gradient, we must calculate the derivative of the function. This cannot be solved in case the function is not continuous or has no derivative. In addition, for multi-extreme functions, this method may miss the extremes, the extremes found are only local. listed . However, random operations together with random search algorithms must also be weakened by inefficiencies. For Genetic Algorithms: the parameters of the search problem must be encoded as a finite sequence of characters. characters on a finite set of characters. This sequence is similar to the gene sequences of organisms. There are many ways to encode parameter sets. Simply put, we can encode as strings of bits on the character set {0,1}. Each string represents a search point in space. GA starts with a randomly generated population of sequences and then produces subsequent populations using random selection as a tool. The Genetic Algorithm thus searches over multiple parallels. but capable of climbing to many extremes at once. Through its operators, the algorithm exchanges information between extrema, thereby minimizing the possibility that the algorithm ends up at local extremes and ignores the loss of global extrema These are the characteristics of the Algorithm. genetic algorithm compared with traditional methods 1.2.6 Applications of genetic algorithms+Optimization and machine learning: In the field of optimization, there are many problems that are applied Genetic algorithms and have been as successful as optimization One-variable function optimization, multivariable function optimization, or such as the traveler problem, black box problem, business problems, system control identification, etc. The following will introduce some optimization problems: David E.Golderg has applied GA to optimize the control problem of the natural gas pipeline system. In this problem, the objective is to minimize the energy due to the compression process, which depends on the maximum and minimum pressure and pressure ratio constraints. Structural optimization: The objective of this problem is minimize the weight of the structure, depending on the maximum and minimum stress constraints of each bar. A set of standard matrix structural framework codes is used to analyze each design generated by Genetic Algorithms.6In the field of machine learning, Genetic Algorithms are used for understanding structural rules such as IF-THEN structure in artificial environment, data mining data mining.+Medical imaging with Genetic AlgorithmSimple genetic algorithm was used to perform image recording, as part of the system It is called Digital Subtraction Angiography (DSA). In a DSA, your doctor will try to look at the inside of a suspicious artery by comparing x-ray images, one taken before the dye was injected into the artery, one and one taken after the injection. Both pictures are digitized and subtracted point-by-point, with the desired end result a different image that clearly outlines the inside of the aorta. However, slight patient movement can produce two adjacent images, confusing the part of the aberration.
Viewing: What is Metaheuristic
See also: What is Follow – What does Follow mean in English
See more: Download Hill Climb Racing Android 1 Apk, Hill Climb Racing
As a result, the images must be placed side by side, in order to compute the difference in the image. Genetic algorithms are used to search for coefficients of variation to find coefficients that minimize the image difference first. and after injection, on the basis of absolute image differences. Genetic Algorithms work with encoding of parameter sets but not with values of parameters. search from a population of points, not from a single point. Genetic Algorithms use only information about the optimal criteria of the objective function and no other supporting information. use probabilistic transformation rules rather than deterministic transformation rules Genetic algorithms are usually easy to implement and apply. However, it does not always give the correct answer. Some Genetic Algorithms can provide potential solutions to a given problem for the user to choose from.72. Applying genetic algorithm to the problem of predicting a 6-digit password 2.1. Introducing the problem A very simple example of finding a password to unlock – assume that this password only accepts numbers and consists of 6 characters. With this problem there will be a total of 10^6 = 1,000,000 different ciphers. Before this problem we have to try randomly or exhaustively to find the password and can search up to 1,000,000 to find the password Of course, when faced with such problems-problems, people often find ways to improve the algorithm by how to provide some more information. For example, with the above unlocking problem, the information about which of the two generated ciphers is “better” (i.e. has a higher unlocking ability). Maybe readers will wonder “by How do I know between two passwords, which one has a higher unlocking ability?”. Usually, when unlocking, people rely on physical factors – like the noise inside a lock when a password is inserted – to predict the “good” of the code under test. Once we know the “good” of the ciphers, we will use a smarter search method – what is often called hillclimbing search. With hill-climbing search, we imagine that the problem-problem search space is a bumpy landscape, with many different high and low hills. In which, the highest hill of this land will be the best solution and the higher the position, the “closer” to the best solution (the height means the good of the solution). Hill-climbing search means that we have to generate solutions so that later the solutions get “closer” to the best solution. This operation is similar to climbing a hill (because we are getting higher and higher every day). The genetic algorithm works like hill climbing However, this type of solution still suffers from the fundamental problem that, if our land has many other small hills besides the highest hill, there is a chance that our algorithm will fail. “stuck” on a small hill. Due to the idea of ”going higher and higher”, when reaching the top of a small hill the algorithm will not be able to continue (because it can’t go up anymore, if you want to find a higher hill, you have to go down the current hill, If you go down the hill, it is not true that the idea is going higher and higher). Imagine a hill-climbing problem-solving computer as a hill climber with a “higher climb” mindset. If there is only one person climbing the hill, it is likely that he or she will be “stuck” on a low hilltop. Thus, if there are many climbers climbing the same hill at many different places, the probability of one person climbing to the highest peak will be higher. The more people, the higher the probability of reaching the highest mountain peak. But this idea is also nothing new, it is simply 30 using many computers to divide the work. Furthermore, with a search space of 10 as the unlocking problem, how many supercomputers do we need to use? More importantly, even if there are many climbers, if the number of climbers is too small compared to the number of hills, the possibility that all climbers will be “stuck” is still very high. At this point, it is possible that a thought suddenly popped up in your head. Why not give more “generations” of hill climbers? That is, if all the first climbers (say 1000 people) do not reach the top of the highest hill, then we will let another 1000 climbers continue climbing. However, there will be a problem, it is likely that in the new group of climbers, there are people who are climbing the same hills that the previous group has already climbed. How do you think? Then record the hills climbed so that the following groups inherit the results of previous group. Or in a more general way: let’s make the best (highest climbers) among the first hill climbers pass on their “experience” climbing the hill to the next 1000 people so that 1000 people This “descendant” will climb higher than them. And if the next 1000 people fail again, the best of them will pass their “experience” to the next generation of 1000 people so that these 3rd generation people can climb even higher. The process continues until a certain generation reaches the highest hilltop or the time allotted. In the event that the time is up, in all generations, the person who climbs the highest will be chosen. This is the main idea of genetic algorithm. Quite simply, instead of generating only one solution, we initially generate many (or even many) solutions at once. Then, among the generated solutions, select the best solutions to form the basis of generating the following group of solutions with the principle of “the later” the better. The process continues until an optimal solution is found. That was the original idea of genetic algorithm. Later, people improved the methodology of this idea, leading to the birth of a complete system of methods and principles used in genetic algorithms2.2. Design a genetic algorithm to predict passwordProblem: let the user enter a password of 6 characters. Write a computer program to find the password entered by the user. Algorithm: From the introduction, we know that the password guessing problem has a solution space of 10^6 cases, each solution is a 6-digit number with each digit. has values from 0->9, so design genetic algorithm as follows: 9Chromosome: is a 6-digit number with each digit having a value from 0->9 Population, survival rate through each generation: is a list of many individuals, the number of individuals of the population can be changed by trial and error until the best results are obtained, the default is 100 RGB individuals. Survival rates can be varied for best results, defaulting to 20 individuals surviving each generation. Out of 2 individuals, we take 10 individuals with the best Fitness function of the previous generation and 10 random individuals. Naturally for survival to form the next generation. Fitness function: since there is a clear answer that is a six-digit number of the user’s initial input, we design the Fitness function as follows: price The value of the Fitness function is the sum of the differences between the digits of the individual being considered and the original digits. Mutation function: we give mutations the index from 0 to 9 according to the amplitude +/- 1 on the individuals. Survive the previous population and create many mutants to put in the new population until the number is enough. Stop function: we already have the answer entered by the user, so when will the algorithm stop. in the population has the correct password instance.2.3 Implement the genetic algorithm using C#-Implement the password class:10- Install the chromosome password instance class, which includes the Fitness function-Set the class to guess the password using t genetic algorithm:11-Mutation function122.4 Main screen:133. Conclusion Along with the rapid and outstanding development of the computer industry, the user’s demand for computers is getting higher and higher: not only solve normal computing and storage tasks, users also expect waiting for computers to be more intelligent, able to solve problems like humans. Genetic algorithms are used in many fields. The application in the article is only at the level of the most rudimentary examples of genetic algorithms. The future development direction of this thesis is that it is possible to propose the design and method of applying genetic algorithms to build intelligent systems such as decision support. References<1>Slides of lectures on Algorithms and problem solving method – Assoc.Prof.Dr. Do Van Nhon<2>Machine Learning And Its Applications – Georgios Paliouras<3>Genetic Algorimths in search Optimization and Machine learning David E.Goldberg.<4> Dissertation report on Genetic Algorithms and applications – internet source14
