Shulou(Shulou.com)06/01 Report--

This article mainly introduces the example analysis of big data genetic algorithm to solve the job shop scheduling problem, the article is very detailed, has a certain reference value, interested friends must read it!

Whether genetic algorithm or any other intelligent optimization algorithm is nothing more than a framework, the purpose is to search for the "optimal solution" of a problem, why to add double quotation marks here, because this kind of intelligent optimization algorithm has a defect, that is, it is easy to fall into "local optimization" in the process of search.

To give you a vivid example, let us have an intuitive feeling about the genetic algorithm. For example, there are six cocks and five hens in the 1000-meter race, the first 100m, and two cocks and two hens are in the top four respectively. At this time, the remaining four cocks and three hens must find a way to catch up with the first four chickens, so they come up with two methods of "crossover" and "mutation". A rooster and a hen "crossed" gave birth to a rooster and a hen. After the breeding, the father and mother were unfortunately killed. A total of three pairs of chickens were able to reproduce through "crossover". What about the remaining rooster? this rooster has a genetic mutation, that is, "mutation" into a new rooster. (please note that the top four chickens have not changed. After the last 7 chickens have "crossover" and "mutation", the total number of chickens is still 11) In the second 100 meters, there are still two Roosters and two hens in the top four, but the top four here may not be the top four chickens in the first 100 meters, and the remaining seven chickens are still "crossover" and "mutation". The aim is to make yourself run faster. Up to the 10th 100 meters, the final sprint stage, after all, there can only be one champion in the race (not considering tied for the first place), so the chicken that won the championship runs the fastest. This chicken may be one of the 11 chickens in the beginning, or it may be bred through "crossover" and "mutation" among some chickens. In short, this chicken is the strongest. In fact, this is the so-called "victory and slight elimination". Chickens that run slowly will be eliminated, but they will reproduce before they are eliminated.

two。 Operation flow of genetic algorithm

Next, the framework of genetic algorithm is given.

1. Initialization: randomly generate all individuals of the first generation population according to the characteristics of each population.

2. Calculate individual fitness: calculate the fitness of each individual.

3. Selection process: according to certain selection criteria, some excellent individuals are selected to participate in crossover and mutation operations.

4. crossover process: pairwise pairing in the population, exchanging some chromosome genes and completing the crossover operation.

5. Mutation process: randomly change some genes in the individual to realize the mutation operation.

6. termination judgment: if the new generation population meets the termination condition, stop the iteration of the algorithm and record that the optimal solution at this time is the optimal solution of the problem; otherwise, add 1 to the number of iterations and return to step 2.

3. Description of job shop scheduling problem

Job shop scheduling refers to allocating the sequence of processing workshops according to the reasonable needs of product manufacturing, so as to achieve the purpose of making rational use of product manufacturing resources and improving the economic benefits of enterprises. The job shop scheduling problem can be described mathematically as there are n parts to be processed on m machines. Given the processing time of each workpiece, the optimization goal is how to determine the processing sequence of the workpiece and the distribution of the workpiece on the machine in each stage, so as to minimize the maximum completion time.

4. Genetic algorithm for solving Job Shop scheduling problem

1. Individual coding

When the total number of workpieces to be processed is k and the total processing process of the workpiece ni is mj, the individual is represented as the length of

The first half of the chromosome represents the processing process of all the workpieces on the machine, and the second half represents the processing machine serial number of each process of the workpiece. Such as an individual

The individual expresses the processing sequence of the workpiece with four processing procedures of two times on three machines. The first 8 bits represent the processing order of the workpiece, which is workpiece 2-> workpiece 4-> workpiece 3-> workpiece 1-> workpiece 1-> workpiece 2-> workpiece 3-> workpiece 4. 9 to 16 bits represent the processing machine, in the following order: machine 2-> machine 1-> machine 3-> machine 2-> machine 2-> machine 1-> machine 3.

two。 Fitness value

The fitness value of the chromosome is the completion time of all the workpieces, and the formula for calculating the fitness value is

Where time refers to the time it takes to complete all tasks. The shorter the completion time of all the workpieces, the better the chromosome.

3. Select operation

Roulette is used to select the chromosomes with good fitness, and the individual selection probability is

Where it indicates the probability that chromosome I is selected in each selection.

4. Cross operation

In the crossover operation, two chromosomes are randomly selected from the population, and the antecedents of each chromosome are taken out for crossover. The method of operation is as follows: the crossing position is 5, and only the front position of the individual is crossed.

After crossing, the process of some workpieces is redundant (workpiece 2 of child 1, workpiece 3 of child 2), and the process of some workpiece is missing (workpiece 3 of child 1, workpiece 2 of child 2). Therefore, the redundant operation of the workpiece process is changed into the missing operation of the workpiece process, and the second half of the processing machine is adjusted according to the operation machine of the individual before crossing.

5. Mutation operation

The mutation operator first selects the mutant individual from the population, then selects the mutation position pos1 and pos2, and finally exchanges the processing procedure and the corresponding processing machine serial number of the pos1 and pos2 position in the individual, as shown below, the mutation position is 2 and 4.

The above is all the contents of the article "example Analysis of big data's genetic algorithm for solving Job Shop scheduling problem". Thank you for your reading. Hope to share the content to help you, more related knowledge, welcome to follow the industry information channel!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.