What Is Genetic Optimization?

Genetic Algorithm (Genetic Algorithm) is a computational model that simulates the natural evolution and biological mechanism of Darwin s biological evolution theory. It is a method of searching the optimal solution by simulating the natural evolution process. A genetic algorithm starts with a population that represents a potential set of solutions to a problem, and a population consists of a certain number of individuals that are encoded by genes. Each individual is actually a characteristic entity with a chromosome. As the main carrier of genetic material, the chromosome is a collection of multiple genes. Its internal expression (ie, genotype) is a certain combination of genes. It determines the external appearance of the shape of an individual. For example, the characteristics of black hair are controlled by Determined by a certain gene combination. Therefore, the mapping from phenotype to genotype needs to be implemented at the beginning. Because the work of imitating gene coding is complicated, we often simplify it. For example, binary coding. After the generation of the first population, according to the principles of survival of the fittest and survival of the fittest, evolution from generation to generation produces better and better approximate solutions. The first generation selects individuals based on the fitness of the individuals in the problem domain, and uses the genetic operators of natural genetics to perform crossover and mutation to produce representative new Population of solution sets. This process will cause the population in the offspring generation to be more adaptive to the environment than the previous generation. The optimal individual in the last generation population is decoded and can be used as an approximate optimal solution to the problem.

Genetic algorithms were founded in the 1960s and 1970s by Professor Holland of the University of Michigan. In the early 1960s, when designing an artificial adaptive system, Holland proposed that the basic principles of genetics should be used to simulate the natural evolution of living things. In 1975, Holland published the first monograph that systematically explained the basic theories and methods of genetic algorithms, which proposed the most important schemata theory in the research and development of genetic algorithm theory. Therefore, 1975 is generally considered to be the birth year of genetic algorithms. In the same year, de jong completed a large number of doctoral dissertation on pure numerical function optimization calculation experiments based on the idea of genetic algorithm, which laid a solid foundation for genetic algorithm and its application. In 1989, Goldberg's work comprehensively summarized and discussed genetic algorithms, and laid the foundation for modern genetic algorithms.

The genetic algorithm is a highly parallel, random, and adaptive optimization algorithm based on "survival of the fittest". The "chromosome" group represented by the problem solution is reproduced, replicated, crossed, and mutated. Group, so as to obtain the optimal or satisfactory solution to the problem. Its advantages are simple principle and operation, strong versatility, unlimited constraints, and it has implicit parallelism and ability to search for global solutions. It is widely used in combinatorial optimization problems. The earliest application of genetic algorithm to jb-shop scheduling problem is that Davis genetic algorithm solves job-shop scheduling problem with less application of neighborhood knowledge, which is more suitable for practical applications. How to use the genetic algorithm to solve job-shop scheduling problem efficiently has been regarded as a challenging problem and has become a research hotspot.

The crossover operator is the most important operator in the genetic algorithm, which determines the global convergence of the genetic algorithm. The most important criterion for crossover operator design is that children inherit the superior characteristics of their parents and the feasibility of their children. On the basis of in-depth analysis of the job-shop scheduling problem, Shao Xinyu et al. Proposed a POX method based on process coding, and compared it with other process code-based crosses, proving that the cross method solves the job-shop scheduling problem Effectiveness. At the same time, in order to solve the premature convergence of the traditional genetic algorithm in solving the jb-shop scheduling problem, Shao Xinyu et al. Also designed an improved offspring alternating pattern genetic algorithm, which significantly accelerated the convergence speed of the genetic algorithm. This principle is also applicable to Other combinatorial optimization problems. The mutation of the genetic algorithm proposed by Shao Xinyu and others is different from the mutation operation in the traditional genetic algorithm (to maintain the diversity of the population), and it is to improve the performance of the offspring through local search ^[1]

Heredity

Genetic algorithm is a general algorithm for solving search problems, which can be used for various general problems.

In the 1990s, genetic algorithms ushered in a booming period of development. Both theoretical research and applied research have become very hot topics. In particular, the application research of genetic algorithms appears to be particularly active. Not only has its application area expanded, but its ability to use genetic algorithms for optimization and rule learning has also improved significantly. At the same time, research in industrial applications is also being explored. In addition, some new theories and methods have also been developed rapidly in applied research, which undoubtedly added new vitality to genetic algorithms. The application research of genetic algorithm has expanded from the initial combination optimization solution to many newer and more engineering applications.

With the expansion of application fields, several new trends have emerged in the research of genetic algorithms: First, machine learning based on genetic algorithms. This new research topic optimizes search algorithms from genetic algorithms to historically discrete search spaces. Extend to new machine learning algorithms with unique rule generation capabilities. This new learning mechanism

Download the commonly used scikit-opt on GitHub ^[2]

Genetic algorithms are biologically based, and it's not too difficult to understand or program. The following is the general algorithm of genetic algorithm:

Because genetic algorithms are generated by evolution and genetic mechanisms

(1) Irregular coding and inaccurate representation of coding.

(2) A single genetic algorithm code cannot fully express the constraints of the optimization problem. One way to consider constraints is to use thresholds for infeasible solutions, so that the calculation time will necessarily increase.

(3) Genetic algorithms are generally less efficient than other traditional optimization methods.

(4) Genetic algorithms tend to converge prematurely.

(5) Genetic algorithm has no effective quantitative analysis methods for the accuracy, feasibility, and computational complexity of the algorithm ^[1]

Because the overall search strategy and optimized search method of the genetic algorithm do not depend on the calculation

EA_demo , published by the University of Glasgow in 1997, is still widely used today. The universities used are Liverpool University, Sussex University, Northampton University, and Ulm University , University of Geneva, Switzerland, University of Granada, Spain, University of Nova de Lisboa, Portugal, University of California, Davis (UC Davies), University of Calgary, Canada, Royal Institute of Technology, Melbourne, Australia (RMIT), National University of Singapore, National Tsinghua University in Taiwan, Shanghai Jiao Tong University, PUCRS University in Brazil, etc.

EA_demo allows users to manually run generation by generation directly on the webpage to see how the genetic / evolutionary algorithm operates step by step. It can also be run in batches in the background to observe the convergence of the algorithm and whether the chromosome jumps out of the local optimum. Users can change termination algebra, population size, mating rate, mutation rate and selection mechanism. There are also other self-study coursewares included on the AI Center website and the European Soft Computing Center website ^[1] .