Artificial intelligence is the study of the computer to simulate some of the human thinking process and intelligent behavior (such as learning, reasoning, thinking, planning, etc.) of the discipline, mainly including the principle of the computer to achieve intelligence, manufacturing computers similar to the human brain intelligence, so that the computer can achieve higher level of application. Ai will involve computer science, human psychology, philosophy and linguistics. It can be said that almost all the disciplines of natural science and social science, its scope has far exceeded the scope of computer science, the relationship between artificial intelligence and thinking science is the relationship between practice and theory, artificial intelligence is in the technical application level of thinking science, is one of its application branch. From the point of view of thinking, artificial intelligence is not only limited to logical thinking, to consider the image thinking, inspiration thinking can promote the development of the breakthrough of artificial intelligence, mathematical basic science often considered a variety of disciplines, mathematics is also entered the language, thinking, the artificial intelligence subject must also use mathematical tools, fuzzy mathematics is not only in the standard logic, * * range to work, Mathematics into the artificial intelligence discipline, they will promote each other and faster development.
Genetic algorithm is a search algorithm used to solve optimization in computational mathematics, and it is a kind of evolutionary algorithm. Evolutionary algorithms were originally developed based on some phenomena in evolutionary biology, including heredity, mutation, natural selection and hybridization. Genetic algorithm is usually implemented by computer simulation. For an optimization problem, a population of abstract representations of a given number of candidate solutions (called individuals) (called chromosomes) evolves toward a better solution. Traditionally, solutions are represented in binary (that is, strings of 0s and 1s), but other representations are possible. Evolution starts with a population of completely random individuals and then happens from generation to generation. In each generation, the fitness of the entire population is evaluated by randomly selecting multiple individuals (based on their fitness) from the current population to generate a new population of life through natural selection and mutation, which becomes the current population in the next iteration of the algorithm.
-
Introduction to computer problems
-
Use C++ language to prepare and debug a genetic algorithm to solve the travel agent TSP problem. The purpose is to learn how to use knowledge representation method and search strategy to solve some simple intelligence problems, familiar with the development process of simple intelligence algorithm and understand its implementation principle.
Using genetic algorithm to solve the travel salesman TSP problem: Suppose there is a travel salesman to visit N cities, he must choose the path to take, the limit of the path is that each city can only visit once, and finally to return to the original starting city. The goal of path selection is to obtain the minimum path distance among all paths.
In the genetic algorithm to solve the travel agent TSP problem, the program revolves around the three main steps of genetic algorithm: selection – copy, cross, mutation. Given 10 populations, that is, 10 chromosomes, each chromosome is composed of points that do not repeat except for the first, the same beginning and end to ensure that the route is closed, so a chromosome contains 11 points.
Genetic algorithm to solve TSP problem of travel agent
The TSP problem is to find the shortest path to traverse n cities, that is, to search a subset of natural numbers W={1,2.. N}(the W element represents the numbering of n cities) a permutation.
Genetic algorithm is a search algorithm with an iterative process of “generate + detect”. Its basic processing flow is shown in Figure 1. It can be seen from the flow chart that genetic algorithm is a population size operation, which takes all individuals in the population as the object. Selection, Crossover and Mutation are the three main operators of genetic algorithm, which constitute the so-called genetic operation and make genetic algorithm possess characteristics that are not found in other traditional methods. The genetic operator contains the following six basic factors:
(1) Parameter coding: Since genetic algorithm cannot understand spatial data directly, they must be expressed as genotype string structure data of genetic space through coding.
(2) Generation of initial population: Due to the population type operation needs of genetic algorithm, an initial population consisting of several initial solutions must be prepared for genetic operation. Each individual of the initial population is created by random method.
(3) Fitness evaluation and detection: The genetic algorithm generally does not need other external information in the process of searching evolution, and only uses fitness value to evaluate the merits and demerits of individuals or solutions, which can be used as the basis for future genetic operations.
(4) Selection: The operation of selection or replication is to select good individuals from the current population, so that they have a chance to reproduce as the father of the next generation. The more fit an individual is, the more chance it has of being selected. A probabilistic method proportional to the degree of applicability is used for selection. Specifically, it is to calculate the sum of fitness of all individuals in the group, and then calculate the proportion of fitness of each individual, and take this as the corresponding selection probability.
(5) Crossover operation: crossover operation is the most important genetic operation in genetic algorithm. A simple crossover (i.e., a one-point crossover) can be carried out in two steps: first, the individuals in the population are randomly matched; second, the crossover is randomly set among the paired individuals, and the paired individuals exchange partial information with each other.
(6) Mutation: The mutation operation is carried out by bit, that is, the content of a certain bit is mutated. Mutation is also random. Generally speaking, the variation probability P is small. Mutation manipulation is a very subtle genetic manipulation that needs to be used in conjunction with crossover manipulation in order to exploit the diversity of individuals in a population and overcome the disadvantage of being limited to local solutions.
Genetic algorithm for TSP problem of travel agent
Flow chart:
Data structure definition:
// Define the structure of chromosomes
struct Chrom
{
int cityArr[cityNum]; // The genetic code of the chromosome
char name; // The chromosome name
float adapt; // Chromosome fitness
int dis; // Chromosome path length
};
struct Chrom genes[popSize]; // Define gene library (struct array)
struct Chrom genesNew[popSize]; // Create a new population
struct Chrom temp; // Define temporary public nodes
names[cityNum] = {‘A’,’B’,’C’,’D’,’E’,’F’,’G’,’H’,’I’,’J’}; // City name
Distance [cityNum][cityNum] // City distance matrix
Function method definition:
InitGroup () // Initializes the gene pool
PopFitness () // Calculate the individual fitness of all chromosomes in the population
ChooseBest () // Returns the best chromosome
Select () // Select operation
Cross () // cross operations
Mutation () // Mutation operation
Genetic algorithm (ga) Solve the travel agent TSP problem C language code:
#include "stdio.h"
#include "stdlib.h"
#include "windows.h"
#include "time.h"
#define cityNum 10 // Number of cities (number of genes)
#define popSize 10 // Population size (size)
#defineCroRate 0.85// Cross probability
#defineMutRate 0.1// Probability of variation
#define MAX 999 // Evolution algebra
// Define the structure of chromosomes
struct Chrom
{
int cityArr[cityNum]; // The genetic code of the chromosome
char name; // The chromosome name
float adapt; // Chromosome fitness
int dis; // Chromosome path length
};
struct Chrom genes[popSize]; // Define gene library (struct array)
struct Chrom genesNew[popSize]; // Create a new population
struct Chrom temp; // Define temporary public nodes
char names[cityNum] = {'A'.'B'.'C'.'D'.'E'.'F'.'G'.'H'.'I'.'J'}; // City name
int distance[cityNum][cityNum] = {{ 0.1.2.3.4.5.6.7.8.9 }, // City distance matrix
{ 1.0.1.2.3.4.5.6.7.8 },
{ 2.1.0.1.2.3.4.5.6.7 },
{ 3.2.1.0.1.2.3.4.5.6 },
{ 4.3.2.1.0.1.2.3.4.5 },
{ 5.4.3.2.1.0.1.2.3.4 },
{ 6.5.4.3.2.1.0.1.2.3 },
{ 7.6.5.4.3.2.1.0.1.2 },
{ 8.7.6.5.4.3.2.1.0.1 },
{ 9.8.7.6.5.4.3.2.1.0 }}; // The optimal solution is 18
void initGroup()
{
// Initialize the gene pool
int i,j,k;
int t = 0;
int flag = 0;
srand(time(NULL));System time is used for initialization. When srand() is fixed, rand() gets a fixed number
for(i = 0; i < popSize; i ++)
{
// Start the assignment with a temporary node
temp.name = names[i];
temp.adapt = 0.0f;
temp.dis = 0;
// Generate 10 different numbers
for(j = 0; j < cityNum;)
{
t = rand()%cityNum; // Randomly generate numbers from 0 to 9
flag = 1;
for(k = 0; k < j; k ++)
{
if(genes[i].cityArr[k] == t)
{
flag = 0;
break; }}if(flag)
{
temp.cityArr[j] = t;
genes[i] = temp;// Store the struct array to generate an individualj++; }}}}// Calculate the individual fitness of all chromosomes in the population
void popFitness()
{
int i,n1,n2;
for(i = 0; i < popSize; i ++)
{
genes[i].dis = 0;
for(int j = 1; j < cityNum; j ++) { n1 = genes[i].cityArr[j- 1];
n2 = genes[i].cityArr[j];
genes[i].dis += distance[n1][n2];
}
genes[i].dis += distance[genes[i].cityArr[0]][genes[i].cityArr[cityNum- 1]];
genes[i].adapt = (float)1/genes[i].dis; // Sum of paths for each chromosome (individual fitness)}}// Return the best chromosome
int chooseBest()
{
int choose = 0;
float best = 0.0f;
best = genes[0].adapt;
for(int i = 0; i < popSize; i ++)
{
if(genes[i].adapt < best) { best = genes[i].adapt; choose = i; }}return choose;
}
// Select the operation
void select()
{
float biggestSum = 0.0f;
float adapt_pro[popSize];
float pick = 0.0f;
int i;
for(i = 0; i < popSize; i ++)
{
biggestSum += genes[i].adapt; / / total probability
}
for(i = 0; i < popSize; i ++)
{
adapt_pro[i] = genes[i].adapt / biggestSum; // Probability array
}
/ / roulette
for(i = 0; i < popSize; i ++) { pick = (float)rand()/RAND_MAX; // A random number between 0 and 1
for(int j = 0; j < popSize; j ++)
{
pick = pick - adapt_pro[j];
if(pick <= 0)
{
genesNew[i] = genes[j];
break; }}}for(i = 0;i < popSize; i++)
{
genes[i] = genesNew[i];
}
}
void cross() // interleaved operations
{
float pick;
int choice1,choice2;
int pos1,pos2;
int temp;
int conflict1[popSize]; // Conflicting positions
int conflict2[popSize];
int num1;
int num2;
int index1,index2;
int move = 0; // The current moving position
while(move < popSize- 1)
{
pick = (float)rand()/RAND_MAX; // Used to determine whether to interleaved operations
if(pick > croRate) // Whether two chromosomes love each other
{
move += 2;
continue; // Do not cross this time
}
// Use partial mapping hybridization
choice1 = move; // Used to select the two parents of the hybrid
choice2 = move+1; // Take care to avoid subscripting out of bounds
pos1 = rand()%popSize;
pos2 = rand()%popSize;
while(pos1 > popSize 2 - || pos1 < 1)// If the position is at the beginning or end (because all swaps are meaningless)
{
pos1 = rand()%popSize;
}
while(pos2 > popSize 2 - || pos2 < 1)
{
pos2 = rand()%popSize;
}
if(pos1 > pos2)
{
temp = pos1;
pos1 = pos2;
pos2 = temp; // Switch pos1 and POS2 positions
}
for(intj = pos1; j <= pos2; j++)// Swap the order one by one
{
temp = genes[choice1].cityArr[j];
genes[choice1].cityArr[j] = genes[choice2].cityArr[j];
genes[choice2].cityArr[j] = temp;
}
num1 = 0;
num2 = 0;
if(pos1 > 0 && pos2 < popSize - 1)/ / is divided into three segments
{
for(int j =0; j < pos1; j++) {for(int k = pos1; k <= pos2; k++)
{
if(genes[choice1].cityArr[j] == genes[choice1].cityArr[k])
{
conflict1[num1] = j;
num1 ++;
}
if(genes[choice2].cityArr[j] == genes[choice2].cityArr[k]) { conflict2[num2] = j; num2 ++; }}}for(j = pos2 + 1; j < popSize; j++) {for(int k = pos1; k <= pos2; k ++)
{
if(genes[choice1].cityArr[j] == genes[choice1].cityArr[k])
{
conflict1[num1] = j;
num1 ++;
}
if(genes[choice2].cityArr[j] == genes[choice2].cityArr[k]) { conflict2[num2] = j; num2 ++; }}}}if((num1 == num2) && num1 > 0)
{
for(int j = 0; j < num1; j ++) { index1 = conflict1[j]; index2 = conflict2[j]; temp = genes[choice1].cityArr[index1];// Swap conflicting positions
genes[choice1].cityArr[index1] = genes[choice2].cityArr[index2];
genes[choice2].cityArr[index2] = temp;
}
}
move += 2; }}// change the operation
void mutation()
{
double pick;
int pos1,pos2,temp;
for(int i = 0; i < popSize; i ++) { pick = (float)rand()/RAND_MAX; // It is used to determine whether to mutate
if(pick > mutRate)
{
continue;
}
pos1 = rand()%popSize;
pos2 = rand()%popSize;
while(pos1 > popSize - 1)
{
pos1 = rand()%popSize;
}
while(pos2 > popSize - 1)
{
pos2 = rand()%popSize;
}
int a = genes[i].dis;
temp = genes[i].cityArr[pos1];
genes[i].cityArr[pos1] = genes[i].cityArr[pos2];
genes[i].cityArr[pos2] = temp;
popFitness();// Update data
// The function of this step is to check whether the mutant is better than before the mutation, if the change in a bad direction, it is better not to change at all
// (Mandatory return, although a bit against the objective law of things, but in order to enhance the convergence of the program, this operation is necessary) (chuckles)
if(genes[i].dis > a) { temp = genes[i].cityArr[pos1]; genes[i].cityArr[pos1] = genes[i].cityArr[pos2]; genes[i].cityArr[pos2] = temp; }}}int main()
{
char c = 0;
printf("\ n \ t \ t * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * genetic algorithm for solving TSP (traveling salesman problem * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * \ n");
initGroup(); / / initialization
popFitness(); // Update data
// Output configuration information
printf("\n\t\t gene length :%d",cityNum);
printf("\t Population size :%d",popSize);
printf("\t cross probability :%.2f",croRate);
printf("\t mutation probability :%.2f",mutRate);
printf("\t Evolution algebra :%d",MAX);
printf("\t Default optimal solution: 18");
printf("\n\n\t\t**********************************************************************************************\n");
// Output distance matrix
printf("\n\n\t\t--------- City distance matrix ---------\n");
printf("\t\t");
int i,j;
for(i = 0; i < cityNum; i ++)
{
for(j = 0; j < cityNum; j ++) { printf(" %d",distance[i][j]);
}
printf("\n\t\t");
}
printf("--------------------------------\n");
// Output path information
printf("\n\t\t-------- Initial population gene bank --------\n");
printf("\t\t ");
for(i = 0; i < cityNum; i ++)
{
printf(" %c",genes[i].name);
}
printf("\n\t\t");
for(i = 0; i < cityNum; i ++) { printf("%c",genes[i].name);
for(j = 0; j < cityNum; j ++)
{
printf(" %d",genes[i].cityArr[j]);
}
printf("\n\t\t");
}
printf("--------------------------------\n");
do
{
printf("\n\t\t in search of optimal solution:");
// Continue to evolve until the defined evolution algebra is reached
for(i = 0; i < MAX; i ++)
{
select();
cross();
popFitness();// Update data
mutation();
popFitness();// Update data
int temp = (int)MAX/20;
}
printf("Complete");
printf("\n\n\t\t optimal path:");
for(i = 0; i < cityNum ; i++)
{
printf("%d-->",genes[chooseBest()].cityArr[i]);
}
printf("%d",genes[chooseBest()].cityArr[0]);
printf("\n\n\t\t Path length :%d",genes[chooseBest()].dis);
printf("Shall we try \n\n\t\t again? (Y/ Y) Yes /(N/ N) No:");
fflush(stdin);
c = getchar();
fflush(stdin);
if(c=='N'||c=='n')
{
break; }}while(1);
printf("\n\t\t");
return 0;
}
Copy the code- Summary experience
From the solution of the above situation (10 cities) by the genetic algorithm in the traveling salesman problem, it can be seen that it is feasible to solve the TSP problem by using the transmission algorithm. When using the genetic algorithm to solve the problem, increasing the number of generations can get better results, but it will take longer time, that is, a good result is always at the cost of time and force, this situation should be analyzed according to the specific problem, balance the proportion of the two in the problem solving. Parameter setting often has an important influence on the performance and results of genetic algorithm. When solving a certain problem, many parameters need to be set, so how to obtain the best parameter combination is a very important problem. In addition, optimization of selection algorithms will improve the performance of genetic algorithms, which need to be constantly involved in practice and extensive reading of good algorithms. Finally, the genetic algorithm is not necessarily the optimal solution, we can perform multiple solutions according to the need, so as to get the results in line with the requirements.