record
abstract
I
abstract
two
guide
word
1
chapter one
Basic genetic algorithm
2
1. 1
Generation and development of genetic algorithm
three
1.2
fundamental principle
three
1.3
Characteristics of genetic algorithm
three
1.4
Basic genetic algorithm description
five
1.5
Genetic algorithm construction process
six
chapter two
Realization technology of genetic algorithm
six
2. 1
encoding method
seven
2. 1. 1
binary coding
seven
2. 1.2
Gray code coding
seven
2. 1.3
Symbolic point coding
eight
2. 1.4
Parameter coding
eight
2.2
Fitness function
10
2.3
Selection operator
10
2.4
Crossover operator
10
2.4. 1
Single-point crossover operator
10
2.4.2
Two-point crossover operator
1 1
2.4.3
Uniform crossover operator
1 1
2.4.4
Partial mapping intersection
1 1
2.4.5
Sequential crossover
12
2.5
Mutation operator
12
2.6
operational parameter
12
2.7
Processing method of constraint conditions
13
2.8
Genetic algorithm flow chart
14
chapter three
Application of Genetic Algorithm in tsp
15
3. 1
Modeling and description of tsp problem
15
3.2
Genetic coding method of tsp
16
3.3
Genetic operator of tsp
17
3.3. 1
Selection operator
17
3.3. 1. 1
roulette wheel selection
17
3.3. 1.2
Optimal preservation strategy selection
17
3.3.2
Crossover operator
20
3.3.2. 1
Single point intersection
20
3.3.2.2
Partial mapping intersection
2 1
3.3.3
Mutation operator
23
3.4
Hybrid genetic algorithm for solving traveling salesman problem
26
chapter four
case analysis
27
4. 1
test data
27
4.2
test result
27
4.3
result analysis
27
choose
ask
The amount of a teaspoon.
(Travel
salesman
The traveling salesman problem is a typical np-complete problem, and genetic algorithm is an ideal method to solve it. Firstly, this paper introduces the basic principle, characteristics and basic implementation technology of the basic genetic algorithm. Then for tsp
This paper discusses the application of genetic algorithm in coding representation and genetic operators (including selection operator and crossover operator mutation operator), points out the advantages and disadvantages of several common coding methods respectively, and analyzes in detail the influence of four operating parameters of basic genetic algorithm, terminated evolutionary algebra of genetic algorithm, crossover probability and mutation probability on the solution result and solution efficiency by combining with the running example of tsp, and sets a set of reasonable values for them after many experiments. Finally, the application of hybrid genetic algorithm in solving tsp problem is briefly explained, and the prospect of genetic algorithm in solving tsp problem is prospected.
Keywords: tsp
genetic algorithm
Genetic operator
encode
@ @ @ Call my name if you need it.