遗传算法c代码
A. 求二维装箱问题遗传算法代码（C或者matlab）
VS2015运行：
#include<stdio.h>
#include<string.h>
int main()
{
int n,i,j,max=0;//max为所用箱子的数目
int a[1005];//用来接收物品的
int b[1005];//即用来描述物品，又用来记录装物品的箱子（看完代码后自然会理解）
int pox[10005];//箱子的位置
memset(pox,-1,sizeof(pox));
scanf_s("%d",&n,3);
for(i=0;i<n;i++)
{
scanf_s("%d",&a[i],3);
b[i]=a[i];
}
pox[0]=0;//将箱子的位置初始化为0，是为了与数组的下标匹配，更方便标记位置
for(i=1;i<n;i++)
{
for(j=0;j<i;j++)
{
if(a[i]+b[j]<=100)
{
b[j]=b[j]+a[i];//将两个物品放在一个箱子中
b[i]=0;//用于同步物品的信息
pox[i]=j;
break;
}
else
{
pox[i]=i;
}
}
}
for(i=0;i<n;i++)
{
if(pox[i]>max)
{
max=pox[i];
}
}
for(i=0;i<n;i++)
{
printf("%d %d\n",a[i],pox[i]+1);
}
printf("%d",max+1);
return 0;
}
B. 遗传算法的c语言实现
一个非常简单的遗传算法源代码，是由Denis Cormier (North Carolina State University)开发的，Sita S.Raghavan (University of North Carolina at Charlotte)修正。代码保证尽可能少，实际上也不必查错。对一特定的应用修正此代码，用户只需改变常数的定义并且定义“评价函数”即可。注意代码的设计是求最大值，其中的目标函数只能取正值；且函数值和个体的适应值之间没有区别。该系统使用比率选择、精华模型、单点杂交和均匀变异。如果用Gaussian变异替换均匀变异，可能得到更好的效果。代码没有任何图形，甚至也没有屏幕输出，主要是保证在平台之间的高可移植性。读者可以从ftp.uncc.e,目录 coe/evol中的文件prog.c中获得。要求输入的文件应该命名为‘gadata.txt’；系统产生的输出文件为‘galog.txt’。输入的文件由几行组成：数目对应于变量数。且每一行提供次序——对应于变量的上下界。如第一行为第一个变量提供上下界，第二行为第二个变量提供上下界，等等。
/**************************************************************************/
/* This is a simple genetic algorithm implementation where the */
/* evaluation function takes positive values only and the */
/* fitness of an indivial is the same as the value of the */
/* objective function */
/**************************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
/* Change any of these parameters to match your needs */
#define POPSIZE 50 /* population size */
#define MAXGENS 1000 /* max. number of generations */
#define NVARS 3 /* no. of problem variables */
#define PXOVER 0.8 /* probability of crossover */
#define PMUTATION 0.15 /* probability of mutation */
#define TRUE 1
#define FALSE 0
int generation; /* current generation no. */
int cur_best; /* best indivial */
FILE *galog; /* an output file */
struct genotype /* genotype (GT), a member of the population */
{
double gene[NVARS]; /* a string of variables */
double fitness; /* GT's fitness */
double upper[NVARS]; /* GT's variables upper bound */
double lower[NVARS]; /* GT's variables lower bound */
double rfitness; /* relative fitness */
double cfitness; /* cumulative fitness */
};
struct genotype population[POPSIZE+1]; /* population */
struct genotype newpopulation[POPSIZE+1]; /* new population; */
/* replaces the */
/* old generation */
/* Declaration of proceres used by this genetic algorithm */
void initialize(void);
double randval(double, double);
void evaluate(void);
void keep_the_best(void);
void elitist(void);
void select(void);
void crossover(void);
void Xover(int,int);
void swap(double *, double *);
void mutate(void);
void report(void);
/***************************************************************/
/* Initialization function: Initializes the values of genes */
/* within the variables bounds. It also initializes (to zero) */
/* all fitness values for each member of the population. It */
/* reads upper and lower bounds of each variable from the */
/* input file `gadata.txt'. It randomly generates values */
/* between these bounds for each gene of each genotype in the */
/* population. The format of the input file `gadata.txt' is */
/* var1_lower_bound var1_upper bound */
/* var2_lower_bound var2_upper bound ... */
/***************************************************************/
void initialize(void)
{
FILE *infile;
int i, j;
double lbound, ubound;
if ((infile = fopen("gadata.txt","r"))==NULL)
{
fprintf(galog,"\nCannot open input file!\n");
exit(1);
}
/* initialize variables within the bounds */
for (i = 0; i < NVARS; i++)
{
fscanf(infile, "%lf",&lbound);
fscanf(infile, "%lf",&ubound);
for (j = 0; j < POPSIZE; j++)
{
population[j].fitness = 0;
population[j].rfitness = 0;
population[j].cfitness = 0;
population[j].lower[i] = lbound;
population[j].upper[i]= ubound;
population[j].gene[i] = randval(population[j].lower[i],
population[j].upper[i]);
}
}
fclose(infile);
}
/***********************************************************/
/* Random value generator: Generates a value within bounds */
/***********************************************************/
double randval(double low, double high)
{
double val;
val = ((double)(rand()%1000)/1000.0)*(high - low) + low;
return(val);
}
/*************************************************************/
/* Evaluation function: This takes a user defined function. */
/* Each time this is changed, the code has to be recompiled. */
/* The current function is: x[1]^2-x[1]*x[2]+x[3] */
/*************************************************************/
void evaluate(void)
{
int mem;
int i;
double x[NVARS+1];
for (mem = 0; mem < POPSIZE; mem++)
{
for (i = 0; i < NVARS; i++)
x[i+1] = population[mem].gene[i];
population[mem].fitness = (x[1]*x[1]) - (x[1]*x[2]) + x[3];
}
}
/***************************************************************/
/* Keep_the_best function: This function keeps track of the */
/* best member of the population. Note that the last entry in */
/* the array Population holds a of the best indivial */
/***************************************************************/
void keep_the_best()
{
int mem;
int i;
cur_best = 0; /* stores the index of the best indivial */
for (mem = 0; mem < POPSIZE; mem++)
{
if (population[mem].fitness > population[POPSIZE].fitness)
{
cur_best = mem;
population[POPSIZE].fitness = population[mem].fitness;
}
}
/* once the best member in the population is found, the genes */
for (i = 0; i < NVARS; i++)
population[POPSIZE].gene[i] = population[cur_best].gene[i];
}
/****************************************************************/
/* Elitist function: The best member of the previous generation */
/* is stored as the last in the array. If the best member of */
/* the current generation is worse then the best member of the */
/* previous generation, the latter one would replace the worst */
/* member of the current population */
/****************************************************************/
void elitist()
{
int i;
double best, worst; /* best and worst fitness values */
int best_mem, worst_mem; /* indexes of the best and worst member */
best = population[0].fitness;
worst = population[0].fitness;
for (i = 0; i < POPSIZE - 1; ++i)
{
if(population[i].fitness > population[i+1].fitness)
{
if (population[i].fitness >= best)
{
best = population[i].fitness;
best_mem = i;
}
if (population[i+1].fitness <= worst)
{
worst = population[i+1].fitness;
worst_mem = i + 1;
}
}
else
{
if (population[i].fitness <= worst)
{
worst = population[i].fitness;
worst_mem = i;
}
if (population[i+1].fitness >= best)
{
best = population[i+1].fitness;
best_mem = i + 1;
}
}
}
/* if best indivial from the new population is better than */
/* the best indivial from the previous population, then */
/* the best from the new population; else replace the */
/* worst indivial from the current population with the */
/* best one from the previous generation */
if (best >= population[POPSIZE].fitness)
{
for (i = 0; i < NVARS; i++)
population[POPSIZE].gene[i] = population[best_mem].gene[i];
population[POPSIZE].fitness = population[best_mem].fitness;
}
else
{
for (i = 0; i < NVARS; i++)
population[worst_mem].gene[i] = population[POPSIZE].gene[i];
population[worst_mem].fitness = population[POPSIZE].fitness;
}
}
/**************************************************************/
/* Selection function: Standard proportional selection for */
/* maximization problems incorporating elitist model - makes */
/* sure that the best member survives */
/**************************************************************/
void select(void)
{
int mem, i, j, k;
double sum = 0;
double p;
/* find total fitness of the population */
for (mem = 0; mem < POPSIZE; mem++)
{
sum += population[mem].fitness;
}
/* calculate relative fitness */
for (mem = 0; mem < POPSIZE; mem++)
{
population[mem].rfitness = population[mem].fitness/sum;
}
population[0].cfitness = population[0].rfitness;
/* calculate cumulative fitness */
for (mem = 1; mem < POPSIZE; mem++)
{
population[mem].cfitness = population[mem-1].cfitness +
population[mem].rfitness;
}
/* finally select survivors using cumulative fitness. */
for (i = 0; i < POPSIZE; i++)
{
p = rand()%1000/1000.0;
if (p < population[0].cfitness)
newpopulation[i] = population[0];
else
{
for (j = 0; j < POPSIZE;j++)
if (p >= population[j].cfitness &&
p<population[j+1].cfitness)
newpopulation[i] = population[j+1];
}
}
/* once a new population is created, it back */
for (i = 0; i < POPSIZE; i++)
population[i] = newpopulation[i];
}
/***************************************************************/
/* Crossover selection: selects two parents that take part in */
/* the crossover. Implements a single point crossover */
/***************************************************************/
void crossover(void)
{
int i, mem, one;
int first = 0; /* count of the number of members chosen */
double x;
for (mem = 0; mem < POPSIZE; ++mem)
{
x = rand()%1000/1000.0;
if (x < PXOVER)
{
++first;
if (first % 2 == 0)
Xover(one, mem);
else
one = mem;
}
}
}
/**************************************************************/
/* Crossover: performs crossover of the two selected parents. */
/**************************************************************/
void Xover(int one, int two)
{
int i;
int point; /* crossover point */
/* select crossover point */
if(NVARS > 1)
{
if(NVARS == 2)
point = 1;
else
point = (rand() % (NVARS - 1)) + 1;
for (i = 0; i < point; i++)
swap(&population[one].gene[i], &population[two].gene[i]);
}
}
/*************************************************************/
/* Swap: A swap procere that helps in swapping 2 variables */
/*************************************************************/
void swap(double *x, double *y)
{
double temp;
temp = *x;
*x = *y;
*y = temp;
}
/**************************************************************/
/* Mutation: Random uniform mutation. A variable selected for */
/* mutation is replaced by a random value between lower and */
/* upper bounds of this variable */
/**************************************************************/
void mutate(void)
{
int i, j;
double lbound, hbound;
double x;
for (i = 0; i < POPSIZE; i++)
for (j = 0; j < NVARS; j++)
{
x = rand()%1000/1000.0;
if (x < PMUTATION)
{
/* find the bounds on the variable to be mutated */
lbound = population[i].lower[j];
hbound = population[i].upper[j];
population[i].gene[j] = randval(lbound, hbound);
}
}
}
/***************************************************************/
/* Report function: Reports progress of the simulation. Data */
/* mped into the output file are separated by commas */
/***************************************************************/
。。。。。
代码太多 你到下面呢个网站看看吧
void main(void)
{
int i;
if ((galog = fopen("galog.txt","w"))==NULL)
{
exit(1);
}
generation = 0;
fprintf(galog, "\n generation best average standard \n");
fprintf(galog, " number value fitness deviation \n");
initialize();
evaluate();
keep_the_best();
while(generation<MAXGENS)
{
generation++;
select();
crossover();
mutate();
report();
evaluate();
elitist();
}
fprintf(galog,"\n\n Simulation completed\n");
fprintf(galog,"\n Best member: \n");
for (i = 0; i < NVARS; i++)
{
fprintf (galog,"\n var(%d) = %3.3f",i,population[POPSIZE].gene[i]);
}
fprintf(galog,"\n\n Best fitness = %3.3f",population[POPSIZE].fitness);
fclose(galog);
printf("Success\n");
}
C. 求C代码：遗传算法求函数最大值f(x)=xsin(10Pix)+1.0
%输出参数：x:求的最优解
% endpop:最终的种群
% bpop:最优种群的一个搜索轨迹
% 输出参数：
% bounds:代表变量的上下界的矩阵
% eevalFN:适应度函数
% startPop:初始群体
% termFN:终止函数的名字
% termOps: 终止函数的参数
% selectFN:选择函数的名称
% selectOpts:选择参数。
function [x,endPop,bPop,traceInfo] = ga(bounds,eevalFN,eevalOps,startPop,opts,...
termFN,termOps,selectFN,selectOps,xOverFNs,xOverOps,mutFNs,mutOps)
n=nargin;
if n<2 | n==6 | n==10 | n==12
disp('Insufficient arguements')
end
if n<3 %Default eevalation opts.
eevalOps=[];
end
if n<5
opts = [1e-6 1 0];
end
if isempty(opts)
opts = [1e-6 1 0];
end
if any(eevalFN<48) %Not using a .m file
if opts(2)==1 %Float ga
e1str=['x=c1; c1(xZomeLength)=', eevalFN ';'];
e2str=['x=c2; c2(xZomeLength)=', eevalFN ';'];
else %Binary ga
e1str=['x=b2f(endPop(j,:),bounds,bits); endPop(j,xZomeLength)=',...
eevalFN ';'];
end
else %Are using a .m file
if opts(2)==1 %Float ga
e1str=['[c1 c1(xZomeLength)]=' eevalFN '(c1,[gen eevalOps]);'];
e2str=['[c2 c2(xZomeLength)]=' eevalFN '(c2,[gen eevalOps]);'];
else %Binary ga
e1str=['x=b2f(endPop(j,:),bounds,bits);[x v]=' eevalFN ...
'(x,[gen eevalOps]); endPop(j,:)=[f2b(x,bounds,bits) v];'];
end
end
if n<6 %Default termination information
termOps=[100];
termFN='maxGenTerm';
end
if n<12 %Default muatation information
if opts(2)==1 %Float GA
mutFNs=['boundaryMutation multiNonUnifMutation nonUnifMutation unifMutation'];
mutOps=[4 0 0;6 termOps(1) 3;4 termOps(1) 3;4 0 0];
else %Binary GA
mutFNs=['binaryMutation'];
mutOps=[0.05];
end
end
if n<10 %默认的交叉信息
if opts(2)==1 %浮点编码
xOverFNs=['arithXover heuristicXover simpleXover'];
xOverOps=[2 0;2 3;2 0];
else %Binary GA
xOverFNs=['simpleXover'];
xOverOps=[0.6];
end
end
if n<9 %Default select opts only i.e. roullete wheel.
selectOps=[];
end
if n<8 %Default select info
selectFN=['normGeomSelect'];
selectOps=[0.08];
end
if n<6 %默认的算法终止准则
termOps=[100];
termFN='maxGenTerm';
end
if n<4 %初始种群为空
startPop=[];
end
if isempty(startPop) %随机生成初始种群
startPop=initializega(80,bounds,eevalFN,eevalOps,opts(1:2));
end
if opts(2)==0 %二进制编码
bits=calcbits(bounds,opts(1));
end
xOverFNs=parse(xOverFNs);
mutFNs=parse(mutFNs);
xZomeLength = size(startPop,2); %Length of the xzome=numVars+fittness
numVar = xZomeLength-1; %变量数目
popSize = size(startPop,1); %种群中个体数目
endPop = zeros(popSize,xZomeLength); %次种群矩阵
c1 = zeros(1,xZomeLength); %个体
c2 = zeros(1,xZomeLength); %个体
numXOvers = size(xOverFNs,1); %交叉操作次数
numMuts = size(mutFNs,1); %变异操作次数
epsilon = opts(1); %适应度门限值
oeval = max(startPop(:,xZomeLength)); %初始种群中的最优值
bFoundIn = 1;
done = 0;
gen = 1;
collectTrace = (nargout>3);
floatGA = opts(2)==1;
display = opts(3);
while(~done)
[beval,bindx] = max(startPop(:,xZomeLength)); %当前种群的最优值
best = startPop(bindx,:);
if collectTrace
traceInfo(gen,1)=gen; %当前代
traceInfo(gen,2)=startPop(bindx,xZomeLength); %最优适应度
traceInfo(gen,3)=mean(startPop(:,xZomeLength)); %平均适应度
traceInfo(gen,4)=std(startPop(:,xZomeLength));
end
if ( (abs(beval - oeval)>epsilon) | (gen==1))
if display
fprintf(1,'\n%d %f\n',gen,beval);
end
if floatGA
bPop(bFoundIn,:)=[gen startPop(bindx,:)];
else
bPop(bFoundIn,:)=[gen b2f(startPop(bindx,1:numVar),bounds,bits)...
startPop(bindx,xZomeLength)];
end
bFoundIn=bFoundIn+1;
oeval=beval;
else
if display
fprintf(1,'%d ',gen);
end
end
endPop = feeval(selectFN,startPop,[gen selectOps]); %选择操作
if floatGA
for i=1:numXOvers,
for j=1:xOverOps(i,1),
a = round(rand*(popSize-1)+1); %一个父代个体
b = round(rand*(popSize-1)+1); %另一个父代个体
xN=deblank(xOverFNs(i,:)); %交叉函数
[c1 c2] = feeval(xN,endPop(a,:),endPop(b,:),bounds,[gen… xOverOps(i,:)]);
if c1(1:numVar)==endPop(a,(1:numVar))
c1(xZomeLength)=endPop(a,xZomeLength);
elseif c1(1:numVar)==endPop(b,(1:numVar))
c1(xZomeLength)=endPop(b,xZomeLength);
else
eeval(e1str);
end
if c2(1:numVar)==endPop(a,(1:numVar))
c2(xZomeLength)=endPop(a,xZomeLength);
elseif c2(1:numVar)==endPop(b,(1:numVar))
c2(xZomeLength)=endPop(b,xZomeLength);
else
eeval(e2str);
end
endPop(a,:)=c1;
endPop(b,:)=c2;
end
end
for i=1:numMuts,
for j=1:mutOps(i,1),
a = round(rand*(popSize-1)+1);
c1 = feeval(deblank(mutFNs(i,:)),endPop(a,:),bounds,[gen mutOps(i,:)]);
if c1(1:numVar)==endPop(a,(1:numVar))
c1(xZomeLength)=endPop(a,xZomeLength);
else
eeval(e1str);
end
endPop(a,:)=c1;
end
end
else %遗传操作的统计模型
for i=1:numXOvers,
xN=deblank(xOverFNs(i,:));
cp=find(rand(popSize,1)<xOverOps(i,1)==1);
if rem(size(cp,1),2) cp=cp(1:(size(cp,1)-1)); end
cp=reshape(cp,size(cp,1)/2,2);
for j=1:size(cp,1)
a=cp(j,1); b=cp(j,2);
[endPop(a,:) endPop(b,:)] = feeval(xN,endPop(a,:),endPop(b,:), bounds,[gen xOverOps(i,:)]);
end
end
for i=1:numMuts
mN=deblank(mutFNs(i,:));
for j=1:popSize
endPop(j,:) = feeval(mN,endPop(j,:),bounds,[gen mutOps(i,:)]);
eeval(e1str);
end
end
end
gen=gen+1;
done=feeval(termFN,[gen termOps],bPop,endPop); %
startPop=endPop; %更新种群
[beval,bindx] = min(startPop(:,xZomeLength));
startPop(bindx,:) = best;
end
[beval,bindx] = max(startPop(:,xZomeLength));
if display
fprintf(1,'\n%d %f\n',gen,beval);
end
x=startPop(bindx,:);
if opts(2)==0 %binary
x=b2f(x,bounds,bits);
bPop(bFoundIn,:)=[gen b2f(startPop(bindx,1:numVar),bounds,bits), startPop(bindx,xZomeLength)];
else
bPop(bFoundIn,:)=[gen startPop(bindx,:)];
end
if collectTrace
traceInfo(gen,1)=gen;
traceInfo(gen,2)=startPop(bindx,xZomeLength); %Best fittness
traceInfo(gen,3)=mean(startPop(:,xZomeLength)); %Avg fittness
end
D. c语言实现*/遗传算法改进BP神经网络原理和算法实现怎么弄
遗传算法有相当大的引用。遗传算法在游戏中应用的现状在遗传编码时, 一般将瓦片的坐标作为基因进行实数编码, 染色体的第一个基因为起点坐标, 最后一个基因为终点坐标, 中间的基因为路径经过的每一个瓦片的坐标。在生成染色体时, 由起点出发, 随机选择当前结点的邻居节点中的可通过节点, 将其坐标加入染色体, 依此循环, 直到找到目标点为止, 生成了一条染色体。重复上述操作, 直到达到指定的种群规模。遗传算法的优点：1、遗传算法是以决策变量的编码作为运算对象，可以直接对集合、序列、矩阵、树、图等结构对象进行操作。这样的方式一方面有助于模拟生物的基因、染色体和遗传进化的过程，方便遗传操作算子的运用。另一方面也使得遗传算法具有广泛的应用领域，如函数优化、生产调度、自动控制、图像处理、机器学习、数据挖掘等领域。2、遗传算法直接以目标函数值作为搜索信息。它仅仅使用适应度函数值来度量个体的优良程度，不涉及目标函数值求导求微分的过程。因为在现实中很多目标函数是很难求导的，甚至是不存在导数的，所以这一点也使得遗传算法显示出高度的优越性。3、遗传算法具有群体搜索的特性。它的搜索过程是从一个具有多个个体的初始群体P(0)开始的，一方面可以有效地避免搜索一些不必搜索的点。另一方面由于传统的单点搜索方法在对多峰分布的搜索空间进行搜索时很容易陷入局部某个单峰的极值点，而遗传算法的群体搜索特性却可以避免这样的问题，因而可以体现出遗传算法的并行化和较好的全局搜索性。4、遗传算法基于概率规则，而不是确定性规则。这使得搜索更为灵活，参数对其搜索效果的影响也尽可能的小。5、遗传算法具有可扩展性，易于与其他技术混合使用。以上几点便是遗传算法作为优化算法所具备的优点。遗传算法的缺点：遗传算法在进行编码时容易出现不规范不准确的问题。
E. 如图，如何用这个PSO算法或遗传算法来求函数极值,用C语言编写代码
需要很多的子函数 %子程序：新物种交叉操作，函数名称存储为crossover.m function scro=crossover(population,seln,pc); BitLength=size(population,2); pcc=IfCroIfMut(pc);%根据交叉概率决定是否进行交叉操作，1则是，0则否 if pcc==1 chb=round(rand*(BitLength-2))+1;%在[1，BitLength-1]范围内随机产生一个交叉位 scro(1,:)=[population(seln(1),1:chb) population(seln(2),chb+1:BitLength)] scro(2,:)=[population(seln(2),1:chb) population(seln(1),chb+1:BitLength)] else scro(1,:)=population(seln(1),:); scro(2,:)=population(seln(2),:); end %子程序：计算适应度函数，函数名称存储为fitnessfun.m function [Fitvalue,cumsump]=fitnessfun(population); global BitLength global boundsbegin global boundsend popsize=size(population,1);%有popsize个个体 for i=1:popsize x=transform2to10(population(i,:));%将二进制转换为十进制 %转化为[-2，2]区间的实数 xx=boundsbegin+x*(boundsend-boundsbegin)/(power(2,BitLength)-1); Fitvalue(i)=targetfun(xx);%计算函数值，即适应度 end %给适...
望采纳！
F. 求遗传算法（GA）C语言代码
.----来个例子，大家好理解..--
基于遗传算法的人工生命模拟
#include<stdio.h>
#include<stdlib.h>
#include<graphics.h>
#include<math.h>
#include<time.h>
#include<string.h>
#include "graph.c"
/* 宏定义 */
#define TL1 20 /* 植物性食物限制时间 */
#define TL2 5 /* 动物性食物限制时间 */
#define NEWFOODS 3 /* 植物性食物每代生成数目 */
#define MUTATION 0.05 /* 变异概率 */
#define G_LENGTH 32 /* 个体染色体长度 */
#define MAX_POP 100 /* 个体总数的最大值 */
#define MAX_FOOD 100 /* 食物总数的最大值 */
#define MAX_WX 60 /* 虚拟环境的长度最大值 */
#define MAX_WY 32 /* 虚拟环境的宽度最大值 */
#define SX1 330 /* 虚拟环境图左上角点x坐标 */
#define SY1 40 /* 虚拟环境图左上角点y坐标 */
#define GX 360 /* 个体数进化图形窗口的左上角点X坐标 */
#define GY 257 /* 个体数进化图形窗口的左上角点Y坐标 */
#define GXR 250 /* 个体数进化图形窗口的长度 */
#define GYR 100 /* 个体数进化图形窗口的宽度 */
#define GSTEP 2 /* 个体数进化图形窗口的X方向步长 */
#define R_LIFE 0.05 /* 初期产生生物数的环境比率 */
#define R_FOOD 0.02 /* 初期产生食物数的环境比率 */
#define SL_MIN 10 /* 个体寿命最小值 */
/* 全局变量 */
unsigned char gene[MAX_POP][G_LENGTH]; /* 遗传基因 */
unsigned char iflg[MAX_POP]; /* 个体死活状态标志变量 */
G. C语言遗传算法在求解TSP问题 毕业论文+源代码
目
录
摘要
I
Abstract
II
引
言
1
第一章
基本遗传算法
2
1.1
遗传算法的产生及发展
3
1.2
基本原理
3
1.3
遗传算法的特点
3
1.4
基本遗传算法描述
5
1.5
遗传算法构造流程
6
第二章
遗传算法的实现技术
6
2.1
编码方法
7
2.1.1
二进制编码
7
2.1.2
格雷码编码
7
2.1.3
符点数编码
8
2.1.4
参数编码
8
2.2
适应度函数
10
2.3
选择算子
10
2.4
交叉算子
10
2.4.1
单点交叉算子
10
2.4.2
双点交叉算子
11
2.4.3
均匀交叉算子
11
2.4.4
部分映射交叉
11
2.4.5
顺序交叉
12
2.5
变异算子
12
2.6
运行参数
12
2.7
约束条件的处理方法
13
2.8
遗传算法流程图
14
第三章
遗传算法在TSP上的应用
15
3.1
TSP问题的建模与描述
15
3.2
对TSP的遗传基因编码方法
16
3.3
针对TSP的遗传操作算子
17
3.3.1
选择算子
17
3.3.1.1
轮盘赌选择
17
3.3.1.2
最优保存策略选择
17
3.3.2
交叉算子
20
3.3.2.1
单点交叉
20
3.3.2.2
部分映射交叉
21
3.3.3
变异算子
23
3.4
TSP的混和遗传算法
26
第四章
实例分析
27
4.1
测试数据
27
4.2
测试结果
27
4.3
结果分析
27
摘
要
TSP
(Traveling
Salesman
Problem)旅行商问题是一类典型的NP完全问题，遗传算法是解决NP问题的一种较理想的方法。文章首先介绍了基本遗传算法的基本原理、特点及其基本实现技术；接着针对TSP
问题，论述了遗传算法在编码表示和遗传算子（包括选择算子、交叉算子变异算子这三种算子）等方面的应用情况，分别指出几种常用的编码方法的优点和缺点，并且结合TSP的运行实例详细分析了基本遗传算法的4个运行参数群体大小、遗传算法的终止进化代数、交叉概率、变异概率，对遗传算法的求解结果和求解效率的影响，经过多次的测试设定出了它们一组比较合理的取值。最后，简单说明了混合遗传算法在求解TSP问题中的应用并对遗传算法解决TSP问题的前景提出了展望。
关键词：TSP
遗传算法
遗传算子
编码
@@@需要的话按我的名字找我吧
H. c++ 求禁忌搜索算法与遗传算法结合的代码
//个体编码方案：十进制的数列，1至26代表A至Z
//交配方法：使用整数编码的交配规则的常规交配法，
//变异方法 ：使用基于次序的变异，随机的产生两个变异位，然后交换这两个变异位上的基因
//新种群构成方法：轮盘赌法进行筛选
//算法结束条件：种群不再发生变化时停止
#include<iostream>
#include<fstream>
#include<stdlib.h>
#include<cmath>
#include<time.h>
#define random(x) (rand()%x)//随机整数
#define initial {0,2,11,1,8,16,5,19,12,4,15,17,6,18,14,9,7,3,10,13}//随机初值
using namespace std;
//参数
int city_number;
double pm = 0.92;
double initiall = 280;//种群数量
double length_table[26][26];
double pc = 0.02;
struct node
{
char name;
int num;
double x;
double y;
};
struct answer
{
int i;
int jie[26];// 十进制的数列，1至26代表A至Z
double length;
};
double f(int* x)
{
double fi = 0;
for(int i = 0; i < city_number-1; i++)
{
fi = fi + length_table[x[i]][x[i+1]];
}
fi = fi + length_table[x[city_number-1]][x[0]];
return fi;
}
double p(double fi,double fj,double t)
{
double P = exp(-(fj-fi)/t);
return P;
}
int main(int argc,char*argv[])
{
time_t tm; time(&tm);
int flag1 = tm;
int cities;
ifstream in(argv[1]);
in >> cities;
city_number = cities;
node* nodes = new node[city_number];
for(int i = 0; i < cities; i++)
{
in >> nodes[i].name >> nodes[i].x >> nodes[i].y;
nodes[i].num = i;
}
//cout << cities<<endl;
//for(int i = 0; i < cities; i++)
// cout <<nodes[i].name <<" "<< nodes[i].x <<" "<< nodes[i].y<<endl;
int i,j;
for(i = 0; i < cities; i++)
{
length_table[i][i] = (double)INT_MAX;
for(j = i+1; j < cities; j++)
{
length_table [i][j] = length_table[j][i] =sqrt(
(nodes[i].x - nodes[j].x) * (nodes[i].x - nodes[j].x) +
(nodes[i].y - nodes[j].y) * (nodes[i].y - nodes[j].y) );
//cout << length_table [i][j]<<endl;
}
}
ofstream out(argv[2]);
///////////////////////////////////////////////////////////初始设定
double t= initiall;//种群数量
int* temp = new int[cities]; answer* Ans1 = new answer;//群体
answer* Ans2 = new answer;//种群
int text[20] = initial;
int* son1 = new int[cities];
int* son2 = new int[cities];
for(int i = 0; i < cities; i++) {
temp[i] = i; Ans1->jie[i] = temp[i];
Ans2->jie[i] = text[i];
//cout << Ans2->jie[i]<<endl;
}
Ans1->length = f(Ans1->jie);
Ans2->length = f(Ans2->jie);
if(cities<15)Ans2->length =10000;
//cout << Ans2->length;
Ans1->i = random(cities);
//cout <<Ans1->i<<endl;
int pre_length = 0;
//
while(Ans1->length!=pre_length)//种群不再发生变化时停止
{
time(&tm);
double fenmu = 0;//轮盘赌法进行选择
for(int i = 0; i < cities*cities; i++)
{
fenmu = fenmu + 1/Ans1->length;
}
int j1 = 0;double s1 = 0;int r1 = rand();
while(s1*32767<=r1) { s1 = s1 + (1/Ans1->length)/fenmu; j1++; }
int j2 = 0;double s2 = 0;int r2 = rand();
while(s2*32767<=r2) { s2 = s2 + (1/Ans1->length)/fenmu; j2++; }
if(tm-flag1>270)break;
pre_length = Ans1->length;
for(int i = 0; i < 100*cities; i++)//
{
int j = random(cities);
int text = temp[Ans1->i]; temp[Ans1->i] = temp[j]; temp[j] = text;
double length = f(temp);//f(j)
if(length < Ans1->length)
{
Ans1->i = j;
for(int l = 0; l < cities; l++)
Ans1->jie[l] = temp[l];
Ans1->length = length;
}
else if(p(length,Ans1->length,t)*32767 > rand())
{
Ans1->i = j;
for(int l = 0; l < cities; l++)
Ans1->jie[l] = temp[l];
Ans1->length = length;
}
}
t = t * pm;int point = random(cities);
//使用整数编码的交配规则的常规交配法
for(int z = 0;z < point;z++) { son1[z] = Ans1->jie[z]; son2[z] = Ans1->jie[z]; }
int text1 = point;int text2 = point;int flag = 0;
for(int x = 0;x < cities;x++)
{
flag =0;
for(int c = 0;c< point;c++)
{
if(Ans1->jie[x]==son1[c])flag=1;
}
if(flag==0){ son1[text1] = Ans1->jie[x]; text1++; }
}
for(int x = 0;x < cities;x++)
{
flag =0;
for(int c = 0;c< point;c++)
{
if(Ans1->jie[x]==son2[c])flag=1;
}
if(flag==0){ son2[text2] = Ans1->jie[x]; text2++; }
}
if(Ans1->length<Ans2->length)
{
for(int m = 0; m < cities; m++)
Ans2->jie[m] = Ans1->jie[m];
Ans2->length = Ans1->length;
}
}
for(int l = 0; l < cities; l++)
{
out << char(Ans2->jie[l]+65)<<" ";
}
out <<Ans2->length<<endl;
return 0;
}
I. 如何用Ｃ语言实现遗传算法的实际应用
具体问题具体对待，关键看你用遗传算法实现什么问题，不同的问题程序不一样，但大的框架差不多都，种群初始化，参数设置，交叉算子、变异算子、选择算子，适应度函数设计。建议用数组实现，最好先大概用文字写出遗传整体结构，再实际编程
我刚做过，如果只是学习的用而不是现实工程项目，不难，