文档库 最新最全的文档下载
当前位置:文档库 › 遗传算法的VC++实现

遗传算法的VC++实现

遗传算法的VC++实现
遗传算法的VC++实现

遗传算法的VC++实现

遗传算法是一种借鉴生物界自然选择和自然遗传机制的高度并行、随机、自适应搜索算法,其隐含的对全局信息的有效利用能力使遗传算法具有稳健性,能够很好地处理传统优化方法解决不了的复杂和非线性问题。遗传算法的执行过程可以简单描述为随机地在参变量空间中进行搜索,由串组成的群体在遗传算子的作用下,同时对空间中不同的区域进行采样计算,从而构成一个不断迭代进化的群体序列。遗传算法的突出表现能力是能够把注意力集中到搜索空间中期望值最高的部分,这是遗传算法中杂交算子作用的直接结果。杂交过程就是模拟生物界中的有性繁殖,它是遗传算法中最重要的部分,是遗传算法区别于其它优化算法的根本所在。遗传算法以迭代群体中的所有个体为操作对象,从本质上讲属于一种群体操作算法,其基本流程如图1 所示。一个标准的遗传算法程序包含4 个基本组成部分: (1) 参数编码; (2) 初始群体生成;(3) 适应值检测; (4) 遗传操作。其中遗传操作是遗传算法的核心,它由3 个基本操作算子组成,即选择算子、交叉算子和变异算子,不同的遗传算子对算法的运行性能有着各不相同的影响。

文章主要从遗传算法在求解连续最优化问题中的设计与实现环节上对遗传算法进行研究。根据所求解问题的性质,设计合理的遗传算法程序,使之满足求解问题的要求。

一些术语

一、染色体(Chronmosome)

染色体又可以叫做基因型个体(individuals),一定数量的个体组成了群体(population),群体中个体的数量叫做群体大小。

二、基因(Gene)

基因是串中的元素,基因用于表示个体的特征。例如有一个串S=1011,则其中的1,0,1,1这4个元素分别称为基因。它们的值称为等位基因(Alletes)。

三、基因地点(Locus)

基因地点在算法中表示一个基因在串中的位置称为基因位置(Gene Position),有时也简

称基因位。基因位置由串的左向右计算,例如在串 S =1101 中,0的基因位置是3。 四、基因特征值(Gene Feature)

在用串表示整数时,基因的特征值与二进制数的权一致;例如在串 S=1011 中,基因位置3中的1,它的基因特征值为2;基因位置1中的1,它的基因特征值为8。 五、适应度(Fitness)

各个个体对环境的适应程度叫做适应度(fitness)。为了体现染色体的适应能力,引入了对问题中的每一个染色体都能进行度量的函数,叫适应度函数. 这个函数是计算个体在群体中被使用的概率。

11122'X X X λλ=+

21221'X X X λλ=+

11122

21221''X X X X X X λλλλ=+??=+?

vc程序设计(遗传算法)

基于基本遗传算法的函数最优化

#include

#include

#include

#include

#include

#include

#include "graph.c"

#include "operator.c"

#define POP_SIZE 25 /* 种群大小*/

#define G_LENGTH 8 /* 染色体长度*/

#define C_RATE 0.2 /* 交叉概率*/

#define M_RATE 0.01 /* 变异概率*/

#define XMAX 255 /* 函数变量最大值*/

#define X1 350 /* 函数图形区窗口左上点X坐标*/

#define Y1 40 /* 函数图形区窗口左上点Y坐标*/

#define XR1 255 /* 函数图形区窗口长度*/

#define YR1 200 /* 函数图形区窗口高度*/

#define X2 360 /* 适应度图形区窗口左上点X坐标*/ #define Y2 280 /* 适应度图形区窗口左上点Y坐标*/ #define XR2 250 /* 适应度图形区窗口长度*/

#define YR2 100 /* 适应度图形区窗口宽度*/

#define STEP 2 /* 适应度图形区X方向步长*/

void initialize_gene(gene,pop_size,g_length)

/* 种群中个体遗传基因型的初始化*/

unsigned char *gene; /* 遗传基因*/

int pop_size; /* 种群大小*/

int g_length; /* 个体染色体长度*/

{

int i,j;

randomize();

for(i=0;i

for(j=0;j

*(gene+i*g_length+j)=random(2);

}

int gene_to_pheno(gene,g_length)

/* 基因型到表现型的变换--解码*/

unsigned char *gene; /* 基因型*/

int g_length; /* 染色体长度*/

{

int i,pheno;

pheno=0;

for(i=0;i

pheno=pheno*2+*(gene+i);

return(pheno);

}

void calc_fitness(gene,fitness,pop_size,g_length,func, max_fit,avg_fit) /* 计算种群中个体的适应度*/

unsigned char *gene; /* 个体的遗传基因*/

double *fitness; /* 个体的适应度*/

double *func; /* 评价函数*/

double *max_fit,*avg_fit; /* 最大适应度与平均适应度*/

int pop_size; /* 种群大小*/

int g_length; /* 个体染色体长度*/

{

unsigned char *g; /* 个体的遗传基因指针变量*/

int pheno; /* 个体的表现型*/

int i,j;

double f;

*max_fit=0.0;

*avg_fit=0.0;

f=(double)pop_size;

for(i=0;i

{

g=gene+i*g_length;

pheno=gene_to_pheno(g,g_length);

*(fitness+i)=*(func+pheno);

if(*(fitness+i)>*max_fit)

*max_fit=*(fitness+i);

*avg_fit=*avg_fit+*(fitness+i)/f;

}

}

void

sga_reproduction(gene,fitness,new_gene,new_fitness,pop_size,g_length)

/* 基于个体的适应度评价进行新一代个体的选择(轮盘赌方法),选择后分别将新的基因型和适应度代入到新个体中*/

unsigned char *gene; /* 当前代的个体遗传基因型*/

unsigned char *new_gene; /* 新一代的个体遗传基因型*/

double *fitness; /* 当前代的个体适应度*/

double *new_fitness; /* 新一代的个体适应度*/

int pop_size; /* 种群大小*/

int g_length; /* 染色体长度*/

{

double sum_of_fitness;

double border;

double r; /* 轮盘上的选择位置变量*/ int i,j;

int num;

sum_of_fitness=0.0;

for(i=0;i

sum_of_fitness=sum_of_fitness+*(fitness+i);

for(i=0;i

{

r=sum_of_fitness*(random(10001)/10000.0);

num=0;

border=*fitness;

while(border

{

num++;

border=border+*(fitness+num);

}

for(j=0;j

*(new_gene+i*g_length+j)=*(gene+num*g_length+j);

*(new_fitness+i)=*(fitness+num);

}

}

void sga_crossover(gene,pop_size,g_length,c_rate)

/* 基本遗传算法的交叉操作--单点交叉*/

unsigned char *gene; /* 遗传基因*/

int pop_size; /* 种群大小*/

int g_length; /* 个体染色体长度*/

double c_rate; /* 交叉概率*/

{

unsigned char *gene1; /* 父个体1的遗传基因指针变量*/

unsigned char *gene2; /* 父个体1的遗传基因指针变量*/

unsigned char work; /* 中间变量*/

int i,j;

int c_pos; /* 交叉位置变量*/

double r; /* 随机数变量*/

for(i=0;i

{

r=random(10001)/10000.0;

if(r<=c_rate)

{

gene1=gene+g_length*i;

gene2=gene1+g_length;

c_pos=random(g_length-2)+1;

for(j=c_pos;j

*(gene1+j)=*(gene2+j);

*(gene2+j)=work;

}

}

}

}

void sga_mutation(gene,pop_size,g_length,m_rate)

/* 基本遗传算法的变异操作--个体遗传基因按小概率翻转*/ unsigned char *gene; /* 遗传基因*/

int pop_size; /* 种群大小*/

int g_length; /* 染色体长度*/

double m_rate; /* 变异概率*/

{

int i,j;

double r;

for(i=0;i

{

for(j=0;j

r=random(10001)/10000.0;

if(r<=m_rate) /* 变异发生判断*/

{

if ( *(gene+g_length*i+j)==0)

*(gene+g_length*i+j)=1;

else

*(gene+g_length*i+j)=0;

}

}

}

void make_function(func,xmax)

/* 生成一个函数, 用于最优化计算的目标函数(最大化) */

/* f=∑ai*sin(x* bi+ci) 其中ai∈[0, 0.35]的均匀随机数

bi∈[2*pi, 5*2*pi] /xmax的均匀随机数

ci∈[0, 2*pi]的均匀随机数

x∈[0,xmax]为优化变量

i=1,2,3 */

double *func; /* 函数值*/

int xmax; /* 变量最大值

{

int x,i;

double a[3],b[3],c[3];

double pi=3.141592;

double fxmax,fx,f_value;

double f_min,f_max,f_mid,f_range;

double dbl;

randomize();

fxmax=(double)xmax;

for(i=0;i<3;i++) /* 优化函数为三个三角函数之和*/

{

a[i]=0.35*(random(10001)/10000.0);

b[i]=(4*(random(10001)/10000.0)+1)*2.0*pi/fxmax;

c[i]=2.0*pi*(random(10001)/10000.0);

}

f_min=1.0;

f_max=0.0;

for(x=0;x<=xmax;x++) /* 将优化函数正规化为[0,1]区间数*/ {

fx=(double)x;

f_value=0.0;

for(i=0;i<3;i++)

{

dbl=b[i]*fx+c[i];

f_value=f_value+a[i]*sin(dbl);

}

f_value=f_value+0.5;

if(f_value>f_max) f_max=f_value;

if(f_value

*(func+x)=(double)f_value;

}

f_range=f_max-f_min;

f_mid=(f_max+f_min)/2.0;

for(x=0;x<=xmax;x++)

{

f_value=(*(func+x)-f_mid)/f_range+0.5;

if(f_value>1.0) f_value=1.0;

else if(f_value<0.0) f_value=0.0;

*(func+x)=f_value;

}

}

void g_draw_func(func,xmax)

/* 绘制优化函数的图形*/

double *func; /* 函数值*/

int xmax; /* 变量最大值*/

{

int x,y,x_old,y_old,i;

double f;

g_rectangle(X1+1,Y1+1,X1+XR1-1,Y1+YR1-1,0,1); g_rectangle(X1+1,Y1-12,X1+XR1,Y1-1,8,1);

g_rectangle(X1,Y1,X1+XR1,Y1+YR1,6,0);

x_old=X1;

y_old=Y1+YR1-(int)(*func*YR1);

f=XR1/(double)xmax;

for(i=1;i<=xmax;i++)

{

x=X1+(int)(i*f);

y=Y1+YR1-(int)(*(func+i)*YR1);

g_line(x_old,y_old,x,y,12);

x_old=x;

y_old=y;

}

}

void g_init_grph(func,xmax)

/* 初始化画面的图形*/

double *func; /* 函数值*/

int xmax; /* 变量最大值*/

{

int x,y,x_old,y_old,i;

char c[5];

/*初始化函数图形区*/

g_rectangle(320,0,639,399,8,1);

g_rectangle(321,1,638,16,8,1);

disp_hz16("基于基本遗传算法的函数最优化",370,1,15);

disp_hz16("g(x)",X1-30,Y1-18,15);

disp_hz16("1.0",X1-30,Y1,15);

disp_hz16("0",X1-10,Y1+YR1,15);

disp_hz16("x",X1+XR1+10,Y1+YR1-20,15);

disp_hz16("XMAX",X1+XR1-10,Y1+YR1,15);

g_draw_func(func,xmax);

/* 初始化适应度图形区*/

g_rectangle(X2,Y2,X2+XR2,Y2+YR2,0,1);

g_rectangle(X2,Y2,X2+XR2,Y2+YR2,6,0);

setcolor(15);

disp_hz16("最大适应度",X2+5,Y2-18,15);

g_line(X2+90,Y2-10,X2+110,Y2-10,11);

setcolor(15);

disp_hz16("平均适应度",X2+120,Y2-18,15);

g_line(X2+205,Y2-10,X2+225,Y2-10,9);

setcolor(15);

disp_hz16("世代数",X2+168,Y2+YR2+10,15);

g_text(X2-30,Y2,15,"1.0");

/* g_text(X2-30,Y2+YR2,15,"0.0");*/

}

void g_plot_grph(num,gene,fitness,pop_size,g_length,func,

xmax,max_fit,m_f_old,avg_fit,a_f_old,gen_num)

/* 随世代进化更新图形*/

unsigned char *gene; /* 遗传基因*/

double *fitness; /* 适应度*/

double *func; /* 函数值*/

double max_fit,m_f_old; /* 当前代最大适应度,上一代最大适应度*/ double avg_fit,a_f_old; /* 当前代平均适应度,上一代平均适应度*/ int num; /* 当前世代数*/

int pop_size; /* 种群大小*/

int g_length; /* 染色体长度*/

int xmax; /* 变量最大值*/

int gen_num; /* 最大世代数*/

{

int i,j,x,y,x_old,y_old;

double f;

unsigned char *g;

char c[10];

/* 显示当前世代种群中个体的遗传基因*/

if(num==gen_num-1)

{

for(i=0;i

{

printf("Indv.%2d:",i+1);

for(j=0;j

printf("%d",*(gene+i*g_length+j));

printf("==>Fitness %.4f\n",*(fitness+i));

}

printf("Max_fit=%f \n",max_fit);

printf("Avg_fit=%f \n",avg_fit);

}

/* 显示个体在函数图形区中的位置*/

g_draw_func(func,xmax);

f=XR1/(double)xmax;

for(i=0;i

{

g=gene+i*g_length;

j=gene_to_pheno(g,g_length);

x=X1+(int)(j*f);

y=Y1+YR1-*(func+j)*YR1;

g_line(x,y-10,x,y,15);

}

/* 适应度曲线的更新*/

if(num!=1 && num<=XR2/STEP)

{

if(num%10==0) /* 每隔10代更新一次*/

{

x=X2+(num-1)*STEP;

g_line(x,Y2+1,x,Y2+YR2-1,1);

sprintf(c,"%d",num);

if(num<100 || num%20==0)

g_text(x-8,Y2+YR2,15,c);

}

x_old=X2+(num-1)*STEP;

x=x_old+STEP;

y_old=Y2+YR2-(int)(m_f_old*YR2);

y=Y2+YR2-(int)(max_fit*YR2);

g_line(x_old,y_old,x,y,11);

y_old=Y2+YR2-(int)(a_f_old*YR2);

y=Y2+YR2-(int)(avg_fit*YR2);

g_line(x_old,y_old,x,y,9);

}

}

void generation(gene,fitness,pop_size,g_length,

c_rate,m_rate,new_gene,new_fitness,func,xmax)

/* 世代进化的模拟*/

unsigned char *gene; /* 当前世代的个体遗传基因型*/ unsigned char *new_gene; /* 新一代的个体遗传基因型*/ double *fitness; /* 当前世代的个体适应度*/ double *new_fitness; /* 新一代的个体适应度*/ double *func; /* 优化函数*/

double c_rate,m_rate; /* 交叉概率和变异概率*/

int pop_size, g_length; /* 种群大小与染色体长度*/

{ int gen_max; /* 最大模拟世代数*/

int i,j,k;

double max_fit,avg_fit; /* 当前代最大适应度和平均适应度*/ double m_f_old,a_f_old; /* 新一代最大适应度和平均适应度*/ char choice[3];

setcolor(15);

disp_hz16("输入最大模拟世代数:",10,1,20);

gscanf(170,1,4,0,3,"%s",choice);

gen_max=atoi(choice);

m_f_old=0.0;

a_f_old=0.0;

for(i=0;i

{

if(i==gen_max-1)

{

printf("\n");

printf("************Gen.%d*************\n",i+1);

}

calc_fitness(gene,fitness,pop_size,g_length,func,

&max_fit,&avg_fit);

sga_reproduction(gene,fitness,new_gene,new_fitness,

pop_size,g_length);

for(j=0;j

{

*(fitness+j)=*(new_fitness+j);

for(k=0;k

*(gene+g_length*j+k)=*(new_gene+g_length*j+k);

}

sga_crossover(gene,pop_size,g_length,c_rate);

sga_mutation(gene,pop_size,g_length,m_rate);

g_plot_grph(i,gene,fitness,pop_size,g_length,func,

xmax,max_fit,m_f_old,avg_fit,a_f_old,gen_max);

m_f_old=max_fit;

a_f_old=avg_fit;

}

}

main() /* 主程序*/

{

/*当前代的个体遗传基因型与新一代的个体遗传基因型*/

unsigned char gene[POP_SIZE][G_LENGTH],

new_gene[POP_SIZE][G_LENGTH];

/*当前代的个体适应度与新一代个体的适应度*/

double fitness[POP_SIZE], new_fitness[POP_SIZE];

/* 优化函数*/

double func[XMAX+1];

/* 初始化图形设置*/

g_init();

/* 生成优化函数*/

make_function(func,XMAX);

/* 初始化显示画面*/

g_init_grph(func,XMAX);

/* 初始化种群*/

initialize_gene(gene,POP_SIZE,G_LENGTH);

/* 世代进化模拟*/

generation(gene,fitness,POP_SIZE,G_LENGTH,

C_RATE,M_RATE,new_gene,new_fitness,func,XMAX); setcolor(9);

disp_hz16("回车键结束",350,430,20); getch();

}

遗传算法的c语言程序

一需求分析 1.本程序演示的是用简单遗传算法随机一个种群,然后根据所给的交叉率,变异率,世代数计算最大适应度所在的代数 2.演示程序以用户和计算机的对话方式执行,即在计算机终端上显示“提示信息”之后,由用户在键盘上输入演示程序中规定的命令;相应的输入数据和运算结果显示在其后。3.测试数据 输入初始变量后用y=100*(x1*x1-x2)*(x1*x2-x2)+(1-x1)*(1-x1)其中-2.048<=x1,x2<=2.048作适应度函数求最大适应度即为函数的最大值 二概要设计 1.程序流程图 2.类型定义 int popsize; //种群大小 int maxgeneration; //最大世代数 double pc; //交叉率 double pm; //变异率 struct individual

{ char chrom[chromlength+1]; double value; double fitness; //适应度 }; int generation; //世代数 int best_index; int worst_index; struct individual bestindividual; //最佳个体 struct individual worstindividual; //最差个体 struct individual currentbest; struct individual population[POPSIZE]; 3.函数声明 void generateinitialpopulation(); void generatenextpopulation(); void evaluatepopulation(); long decodechromosome(char *,int,int); void calculateobjectvalue(); void calculatefitnessvalue(); void findbestandworstindividual(); void performevolution(); void selectoperator(); void crossoveroperator(); void mutationoperator(); void input(); void outputtextreport(); 4.程序的各函数的简单算法说明如下: (1).void generateinitialpopulation ()和void input ()初始化种群和遗传算法参数。 input() 函数输入种群大小,染色体长度,最大世代数,交叉率,变异率等参数。 (2)void calculateobjectvalue();计算适应度函数值。 根据给定的变量用适应度函数计算然后返回适度值。 (3)选择函数selectoperator() 在函数selectoperator()中首先用rand ()函数产生0~1间的选择算子,当适度累计值不为零时,比较各个体所占总的适应度百分比的累计和与选择算子,直到达到选择算子的值那个个体就被选出,即适应度为fi的个体以fi/∑fk的概率继续存在; 显然,个体适应度愈高,被选中的概率愈大。但是,适应度小的个体也有可能被选中,以便增加下一代群体的多样性。 (4)染色体交叉函数crossoveroperator() 这是遗传算法中的最重要的函数之一,它是对个体两个变量所合成的染色体进行交叉,而不是变量染色体的交叉,这要搞清楚。首先用rand ()函数产生随机概率,若小于交叉概率,则进行染色体交叉,同时交叉次数加1。这时又要用rand()函数随机产生一位交叉位,把染色

遗传算法的C#实现及应用

,………………………………………………“………“ 实用第一/智慧密集。.....。。。。。。。。,。.。.。。。。.。。。。。.。。。。。。。。。。。.。。。..。。。。。。。。。。。。..。。。。。,。√, ≯||j—A疆蕊嗡嗡镧鹣潲瞒虢滁酗确斓蛹鹳曩jii11||||璐彀豫澡毽畿瓷罐甍谶羲|遵麓囊鬻谶赢薏篱瀑每||?i。|?≯,鬣壤鋈国潆巢镶倦奄誊缝绥舔蔑善嚣≤譬I jl。j0j。j瓷蚤尊嶙≮啪獬i毽赫馘每蛹戳j蠢。‰酶鸯峨誓曩薯|≥il ji j j。一iI|薯0I奄§畦姻镦添。每孳舔溺警jlj;|0一『j_lt-?甍遴!l邀纛纛瓣|鬣瓣◇|lii|Il||I弩酶冁醚嗡婚穆穗姆t◇9鬟湖瀵哮咚◇i谚峰岭譬ij¨¨|:鬻攀谶一≥。|?|“ji?l疆黼誊眷懿t诵蕊囊酿褥酶姆螭t豳j酶I≮媾龋穗电鹱穰誊j|。。j|。。麓国隧嫱毒撼媳誊『:i-jl||i溪誉攀lj豢篱鬣蔷淄鬻|l|一ij鼍≥l篱鬻il豢 ≤奠do≯Z处理其余的基因l城市点卜 ?j。一鼍_i『瓢j树蛹嗽N哟hbor={G_e制ea淑Nejghbor誊l|ll}ig髓瞄蝴a}弼鼯礁u确瞅e脚S攀j。 一毫?。/|l,,熊到与翦学纂蜀溉避的一个基因,并加入新染色体曩o、。潮黼溉憾rf_{la鳓m鸯,A酬Gene椭ewGAGene j删删N磅i鳓£躜r|I;¨警自赋£lI:_l§¨'|): 、。-。:,薯£酒ftP舀黼黯一一:。i j-j?i。昭铀柏舔嚣i蜩酚鳓N∞rs悄ejghboB +寥 __l蝴Ⅺ蠢lm白赠鳓f¥缓警iO戳『;j i毒j碜净磅囊i÷i;i喹哆?簿簪两ohr9哆j舀锣me{n。wchr|。而osome}:j雾雾鬻雾耩韵秘穆然取代原染色体i. 准备好以上的方法后,还要注意四个参数的设定。交叉率一般为O.8左右,变异率一般为O.05左右,群体大小、繁殖次数要根据城市数目有所变化。调试程序时,可以修改这些参数来观察优化过程的收敛快慢、最优解的跳变等。 三、程序调试 在Vs2005中建立windows组件解决方案,添加现有项:基因类(GAGene)、染色体类(GAChfomosome)、染色体比较类(chromosomecomparer.cs)、遗传算法类(GA),调试生成(ga.衄)组件。 建立gaTsP解决方案,添加现有项tspFORM.cs窗体,添加引用ga.dll。运行程序如下图所示。工具栏第一个按钮的作用是设置一个文本文件,以记录每一代群体的染色体组成及其适应度的值。红色曲线为每一群体中最优染色体的适应度的变化,从中可以看到优化过程的收敛情况。读者可以模仿本文的第二部分,利用ga.dU解决其他问题。 旅行商问题运行图 参考文献 1.陈国良、王煦法、庄镇.遗传算法及其应用.人民邮电出版社 2.李敏强.遗传算法的基本理论与应用.科学出版社 (收稿日期:2007年1月26日)

MATLAB实验遗传算法和优化设计

实验六 遗传算法与优化设计 一、实验目的 1. 了解遗传算法的基本原理和基本操作(选择、交叉、变异); 2. 学习使用Matlab 中的遗传算法工具箱(gatool)来解决优化设计问题; 二、实验原理及遗传算法工具箱介绍 1. 一个优化设计例子 图1所示是用于传输微波信号的微带线(电极)的横截面结构示意图,上下两根黑条分别代表上电极和下电极,一般下电极接地,上电极接输入信号,电极之间是介质(如空气,陶瓷等)。微带电极的结构参数如图所示,W 、t 分别是上电极的宽度和厚度,D 是上下电极间距。当微波信号在微带线中传输时,由于趋肤效应,微带线中的电流集中在电极的表面,会产生较大的欧姆损耗。根据微带传输线理论,高频工作状态下(假定信号频率1GHz ),电极的欧姆损耗可以写成(简单起见,不考虑电极厚度造成电极宽度的增加): 图1 微带线横截面结构以及场分布示意图 {} 28.6821ln 5020.942ln 20.942S W R W D D D t D W D D W W t D W W D e D D παπππ=+++-+++?????? ? ??? ??????????? ??????? (1) 其中πρμ0=S R 为金属的表面电阻率, ρ为电阻率。可见电极的结构参数影响着电极损耗,通过合理设计这些参数可以使电极的欧姆损耗做到最小,这就是所谓的最优化问题或者称为规划设计问题。此处设计变量有3个:W 、D 、t ,它们组成决策向量[W, D ,t ] T ,待优化函数(,,)W D t α称为目标函数。 上述优化设计问题可以抽象为数学描述: ()()min .. 0,1,2,...,j f X s t g X j p ????≤=? (2)

MATLAB课程遗传算法实验报告及源代码

硕士生考查课程考试试卷 考试科目: 考生姓名:考生学号: 学院:专业: 考生成绩: 任课老师(签名) 考试日期:年月日午时至时

《MATLAB 教程》试题: A 、利用MATLA B 设计遗传算法程序,寻找下图11个端点最短路径,其中没有连接端点表示没有路径。要求设计遗传算法对该问题求解。 a e h k B 、设计遗传算法求解f (x)极小值,具体表达式如下: 321231(,,)5.12 5.12,1,2,3i i i f x x x x x i =?=???-≤≤=? ∑ 要求必须使用m 函数方式设计程序。 C 、利用MATLAB 编程实现:三名商人各带一个随从乘船渡河,一只小船只能容纳二人,由他们自己划行,随从们密约,在河的任一岸,一旦随从的人数比商人多,就杀人越货,但是如何乘船渡河的大权掌握在商人手中,商人们怎样才能安全渡河? D 、结合自己的研究方向选择合适的问题,利用MATLAB 进行实验。 以上四题任选一题进行实验,并写出实验报告。

选择题目: B 、设计遗传算法求解f (x)极小值,具体表达式如下: 321231(,,)5.12 5.12,1,2,3i i i f x x x x x i =?=???-≤≤=? ∑ 要求必须使用m 函数方式设计程序。 一、问题分析(10分) 这是一个简单的三元函数求最小值的函数优化问题,可以利用遗传算法来指导性搜索最小值。实验要求必须以matlab 为工具,利用遗传算法对问题进行求解。 在本实验中,要求我们用M 函数自行设计遗传算法,通过遗传算法基本原理,选择、交叉、变异等操作进行指导性邻域搜索,得到最优解。 二、实验原理与数学模型(20分) (1)试验原理: 用遗传算法求解函数优化问题,遗传算法是模拟生物在自然环境下的遗传和进化过程而形成的一种自适应全局优化概率搜索方法。其采纳了自然进化模型,从代表问题可能潜在解集的一个种群开始,种群由经过基因编码的一定数目的个体组成。每个个体实际上是染色体带有特征的实体;初始种群产生后,按照适者生存和优胜劣汰的原理,逐代演化产生出越来越好的解:在每一代,概据问题域中个体的适应度大小挑选个体;并借助遗传算子进行组合交叉和主客观变异,产生出代表新的解集的种群。这一过程循环执行,直到满足优化准则为止。最后,末代个体经解码,生成近似最优解。基于种群进化机制的遗传算法如同自然界进化一样,后生代种群比前生代更加适应于环境,通过逐代进化,逼近最优解。 遗传算法是一种现代智能算法,实际上它的功能十分强大,能够用于求解一些难以用常规数学手段进行求解的问题,尤其适用于求解多目标、多约束,且目标函数形式非常复杂的优化问题。但是遗传算法也有一些缺点,最为关键的一点,即没有任何理论能够证明遗传算法一定能够找到最优解,算法主要是根据概率论的思想来寻找最优解。因此,遗传算法所得到的解只是一个近似解,而不一定是最优解。 (2)数学模型 对于求解该问题遗传算法的构造过程: (1)确定决策变量和约束条件;

遗传算法求解VRP问题的技术报告

遗传算法求解VRP 问题的技术报告 摘要:本文通过遗传算法解决基本的无时限车辆调度问题。采用车辆和客户对应排列编码的遗传算法,通过种群初始化,选择,交叉,变异等操作最终得到车辆配送的最短路径。通过MA TLAB 仿真结果可知,通过遗传算法配送的路径为61.5000km,比随机配送路径67km 缩短了5.5km 。此结果表明遗传算法可以有效的求解VRP 问题。 一、 问题描述 1.问题描述 车辆调度问题(Vehicle Scheduling/Routing Problem,VSP/VRP )的一般定义为[1]:对一系列送货点和/或收货点,组织适当的行车路线,使车辆有序地通过它们,在满足一定的约束条件(如货物需求量、发送量,送发货时间、车辆容量限制、行驶里程限制、时间限制等)下,达到一定的目标(如路程最短、费用极小、时间尽量少、使用车辆数尽量少等)。问题描述如下[2]:有一个或几个配送中心),...,1(n i D i =,每个配送中心有K 种不同类型的车型,每种车型有n 辆车。有一批配送业务),...,1(n i R i =,已知每个配送业务需求量),...,1(n i q i =和位置或要求在一定的时间范围内完成,求在满足不超过配送车辆载重等的约束条件下,安排配送车辆在合适的时间、最优路线使用成本最小。 2.数学模型 设配送中心有K 台车,每台车的载重量为),...,2,1(K k Q k =,其一次配送的最大行驶距离为k D ,需要向L 个客户送货,每个客户的货物需求量为),...,2,1(L i q i =,客户i 到j 的运距为ij d ,配送中心到各个客户的距离为),...,2,1,(0L j i d j =,再设k n 为第K 台车配送的客户数(k n =0表示未使用第K 台车),用集合k R 表示第k 条路径,其中ki r 表示客户ki r 在路径 k 中的顺序为 (不包括配送中心),令 0k r 表示配送中心,若以配送总里程最短为目标函数,则可建立如下数学模型: ∑∑==?+=-K k k rk r n i r r n sign d d Z k kn k ki i k 1 1 )] ([min )1( (1) k n i ki Q qr k ≤∑=1 (2) k k rk r n i r r D n sign d d k kn k ki i k ≤?+∑=-)(0 1 )1( (3) L n k ≤≤0 (4)

遗传算法——耐心看完-你就掌握了遗传算法【精品毕业设计】(完整版)

遗传算法入门到掌握 读完这个讲义,你将基本掌握遗传算法,要有耐心看完。 想了很久,应该用一个怎么样的例子带领大家走进遗传算法的神奇世界呢?遗传算法的有趣应用很多,诸如寻路问题,8数码问题,囚犯困境,动作控制,找圆心问题(这是一个国外网友的建议:在一个不规则的多边形中,寻找一个包含在该多边形内的最大圆圈的圆心。),TSP问题(在以后的章节里面将做详细介绍。),生产调度问题,人工生命模拟等。直到最后看到一个非常有趣的比喻,觉得由此引出的袋鼠跳问题(暂且这么叫它吧),既有趣直观又直达遗传算法的本质,确实非常适合作为初学者入门的例子。这一章将告诉读者,我们怎么让袋鼠跳到珠穆朗玛峰上去(如果它没有过早被冻坏的话)。 问题的提出与解决方案 让我们先来考虑考虑下面这个问题的解决办法。 已知一元函数: 图2-1 现在要求在既定的区间内找出函数的最大值。函数图像如图2-1所示。 极大值、最大值、局部最优解、全局最优解

在解决上面提出的问题之前我们有必要先澄清几个以后将常常会碰到的概念:极大值、最大值、局部最优解、全局最优解。学过高中数学的人都知道极大值在一个小邻域里面左边的函数值递增,右边的函数值递减,在图2.1里面的表现就是一个“山峰”。当然,在图上有很多个“山峰”,所以这个函数有很多个极大值。而对于一个函数来说,最大值就是在所有极大值当中,最大的那个。所以极大值具有局部性,而最大值则具有全局性。 因为遗传算法中每一条染色体,对应着遗传算法的一个解决方案,一般我们用适应性函数(fitness function)来衡量这个解决方案的优劣。所以从一个基因组到其解的适应度形成一个映射。所以也可以把遗传算法的过程看作是一个在多元函数里面求最优解的过程。在这个多维曲面里面也有数不清的“山峰”,而这些最优解所对应的就是局部最优解。而其中也会有一个“山峰”的海拔最高的,那么这个就是全局最优解。而遗传算法的任务就是尽量爬到最高峰,而不是陷落在一些小山峰。(另外,值得注意的是遗传算法不一定要找“最高的山峰”,如果问题的适应度评价越小越好的话,那么全局最优解就是函数的最小值,对应的,遗传算法所要找的就是“最深的谷底”)如果至今你还不太理解的话,那么你先往下看。本章的示例程序将会非常形象的表现出这个情景。 “袋鼠跳”问题 既然我们把函数曲线理解成一个一个山峰和山谷组成的山脉。那么我们可以设想所得到的每一个解就是一只袋鼠,我们希望它们不断的向着更高处跳去,直到跳到最高的山峰(尽管袋鼠本身不见得愿意那么做)。所以求最大值的过程就转化成一个“袋鼠跳”的过程。下面介绍介绍“袋鼠跳”的几种方式。 爬山法、模拟退火和遗传算法 解决寻找最大值问题的几种常见的算法: 1. 爬山法(最速上升爬山法): 从搜索空间中随机产生邻近的点,从中选择对应解最优的个体,替换原来的个体,不断重复上述过程。因为只对“邻近”的点作比较,所以目光比较“短浅”,常常只能收敛到离开初始位置比较近的局部最优解上面。对于存在很多局部最优点的问题,通过一个简单的迭代找出全局最优解的机会非常渺茫。(在爬山法中,袋鼠最有希望到达最靠近它出发点的山顶,但不能保证该山顶是珠穆朗玛峰,或者是一个非常高的山峰。因为一路上它只顾上坡,没有下坡。) 2. 模拟退火: 这个方法来自金属热加工过程的启发。在金属热加工过程中,当金属的温度超过它的熔点(Melting Point)时,原子就会激烈地随机运动。与所有的其它的物理系统相类似,原子的这种运动趋向于寻找其能量的极小状态。在这个能量的变

基于遗传算法的matlab源代码

function youhuafun D=code; N=50;%Tunable maxgen=50;%Tunable crossrate=0.5;%Tunable muterate=0.08;%Tunable generation=1; num=length(D); fatherrand=randint(num,N,3); score=zeros(maxgen,N); while generation<=maxgen ind=randperm(N-2)+2;%随机配对交叉 A=fatherrand(:,ind(1:(N-2)/2)); B=fatherrand(:,ind((N-2)/2+1:end)); %多点交叉 rnd=rand(num,(N-2)/2); ind=rnd tmp=A(ind); A(ind)=B(ind); B(ind)=tmp; %%两点交叉 %for kk=1:(N-2)/2 %rndtmp=randint(1,1,num)+1; %tmp=A(1:rndtmp,kk); %A(1:rndtmp,kk)=B(1:rndtmp,kk); %B(1:rndtmp,kk)=tmp; %end fatherrand=[fatherrand(:,1:2),A,B]; %变异 rnd=rand(num,N); ind=rnd[m,n]=size(ind); tmp=randint(m,n,2)+1; tmp(:,1:2)=0; fatherrand=tmp+fatherrand; fatherrand=mod(fatherrand,3); %fatherrand(ind)=tmp; %评价、选择 scoreN=scorefun(fatherrand,D);%求得N个个体的评价函数 score(generation,:)=scoreN; [scoreSort,scoreind]=sort(scoreN); sumscore=cumsum(scoreSort); sumscore=sumscore./sumscore(end); childind(1:2)=scoreind(end-1:end); for k=3:N tmprnd=rand; tmpind=tmprnd difind=[0,diff(t mpind)]; if~any(difind) difind(1)=1; end childind(k)=scoreind(logical(difind)); end fatherrand=fatherrand(:,childind); generation=generation+1; end %score maxV=max(score,[],2); minV=11*300-maxV; plot(minV,'*');title('各代的目标函数值'); F4=D(:,4); FF4=F4-fatherrand(:,1); FF4=max(FF4,1); D(:,5)=FF4; save DData D function D=code load youhua.mat %properties F2and F3 F1=A(:,1); F2=A(:,2); F3=A(:,3); if(max(F2)>1450)||(min(F2)<=900) error('DATA property F2exceed it''s range (900,1450]') end %get group property F1of data,according to F2value F4=zeros(size(F1)); for ite=11:-1:1 index=find(F2<=900+ite*50); F4(index)=ite; end D=[F1,F2,F3,F4]; function ScoreN=scorefun(fatherrand,D) F3=D(:,3); F4=D(:,4); N=size(fatherrand,2); FF4=F4*ones(1,N); FF4rnd=FF4-fatherrand; FF4rnd=max(FF4rnd,1); ScoreN=ones(1,N)*300*11; %这里有待优化

一个简单实用的遗传算法c程序完整版

一个简单实用的遗传算 法c程序 HEN system office room 【HEN16H-HENS2AHENS8Q8-HENH1688】

一个简单实用的遗传算法c程序(转载) 2009-07-28 23:09:03 阅读418 评论0 字号:大中小 这是一个非常简单的遗传算法源代码,是由Denis Cormier (North Carolina State University)开发的,Sita (University of North Carolina at Charlotte)修正。代码保证尽可能少,实际上也不必查错。对一特定的应用修正此代码,用户只需改变常数的定义并且定义“评价函数”即可。注意代码的设计是求最大值,其中的目标函数只能取正值;且函数值和个体的适应值之间没有区别。该系统使用比率选择、精华模型、单点杂交和均匀变异。如果用Gaussian变异替换均匀变异,可能得到更好的效果。代码没有任何图形,甚至也没有屏幕输出,主要是保证在平台之间的高可移植性。读者可以从,目录 coe/evol中的文件中获得。要求输入的文件应该命名为‘’;系统产生的输出文件为‘’。输入的文件由几行组成:数目对应于变量数。且每一行提供次序——对应于变量的上下界。如第一行为第一个变量提供上下界,第二行为第二个变量提供上下界,等等。 /**************************************************************************/ /* This is a simple genetic algorithm implementation where the */ /* evaluation function takes positive values only and the */ /* fitness of an individual is the same as the value of the */ /* objective function */ /**************************************************************************/ #include <> #include <> #include <> /* Change any of these parameters to match your needs */ #define POPSIZE 50 /* population size */

6-第二篇 第2章 遗传算法的基本实现技术

2.4 遗传算子 遗传算法中包括三个遗传操作(或称遗传算子):即选择算子、交叉算子和变异算子,它们构成了遗传算法具备强大搜索能力的核心。利用遗传算子产生新一代群体实现群体进化,下面分别介绍这三种遗传算子。 2.4.1选择算子 在生物的遗传和自然进化过程中,对生存环境适应程度较高的物种将有更多机会遗传到下一代;而对生存环境适应程度较低的物种遗传到下一代的机会就相对较少。模仿这个过程,遗传算法使用选择算子(或称复制算子,Reproduction Operator)来对群体中的个体进行优胜劣汰操作:适应度较高的个体被遗传到下一代群体中的概率较大;适应度较低的个体被遗传到下一代群体中的概率较小。遗传算法中的选择操作就是用来确定如何从父代群体中按某种方法选取哪些个体遗传到下一代群体中的一种遗传运算。通过选择操作可以避免基因缺失,提高全局收敛性和计算效率。 1. 比例选择法(proportional model) 适应度比例选择方法是基本的选择方法,也叫赌轮选择(roulette wheel selection)或蒙特卡罗选择,是一种回放式随机采样方法。该方法的基本思想是:各个个体的被选中的概率与其适应度大小成正比。 设群体规模为M ,个体i 的适应度为i F ,则个体i 被选中的概率is P 为: 1 i is M i i F P F == ∑ (1,2, ,i M =) (2-14) 显然,概率is P 反映了个体i 的适应度在整个群体的个体适应度总和中所占的比例,个体适应度越大,其被选择的概率就越高,反之亦然。 2. 最佳个体保存方法(elitist model) 最佳个体保存法的思想是群体中适应度最高的个体不参与交叉运算和变异运算,而是用它来替换掉本代群体中经过交叉、变异等遗传操作后所产生的适应度最低的个体 采用这样选择方法的优点是,进化过程中某一代的最优解可不被交叉或变异操作破坏。但是,这也隐含了一种危机,即局部最优个体的遗传基因会急速增加而使进化有可能陷于局部解,也就是说,该方法的全局搜索能力差。它适合于单峰性质的优化问题的空间搜索,而不适于多峰性质的空间搜索。所以,此方法一般都与其他选择方法结合使用。 3. 期望值方法(expected value model) 在赌轮选择方法中,当个体数不太多时,产生的随机数有可能会出现不正确地反映个体适应度的选择。这时存在统计误差,也就是就,适应度高的个体有可能被淘汰,适应度低的个体也有可能被选择。为了克服这种缺点,期望值方法根据每个个体在下一代群体中的生存期望值来进行随机选择运算,是一种无回放的随机采样方法,其步骤如下: (1)计算群体中每个个体在下一代生存的期望数目i N 1 i i i M avg i i F M F N F F =?= =∑ (1,2,,i M =) (2-15)

matlab遗传算法学习和全局化算法【精品毕业设计】(完整版)

1 遗传算法步骤 1 根据具体问题选择编码方式,随机产生初始种群,个体数目一定,每个个体表现为染色 体的基因编码 2 选择合适的适应度函数,计算并评价群体中各个体的适应。 3 选择(selection)。根据各个个体的适应度,按照一定的规则或方法,从当前群体中选择出 一些优良的个体遗传到下一代群体 4 交叉(crossover)。将选择过后的群体内的各个个体随机搭配成对,对每一对个体,以一定 概率(交叉概率)交换它们中的部分基因。 5 变异(mutation)。对交叉过后的群体中的每一个个体,以某个概率(称为变异概率)改n 变某一个或某一些基因位上的基因值为其他的等位基因 6 终止条件判断。若满足终止条件,则以进化过程中得到的具有最大适应度的个体作为最 优解输出,终止运算。否则,迭代执行Step2 至Step5。 适应度是评价群体中染色体个体好坏的标准,是算法进化的驱动力,是自然选择的唯一依据,改变种群结构的操作皆通过适应度函数来控制。在遗传算法中,以个体适应度的大小 来确定该个体被遗传到下一代群体中的概率。个体的适应度越大,被遗传到下一代的概率 就越大,相反,被遗传到下一代的概率就越小。 1 [a,b,c]=gaopt(bound,fun)其中,bound=[xm,xM]为求解区间上届和下届构成的矩阵。Fun 为用户编写的函数。a为搜索的结果向量,由搜索的出的最优x向量与目标函数构成,b为最终搜索种群,c为中间搜索过程变参数,其第一列为代数,后边列分别为该代最好的的个 体与目标函数的值,可以认为寻优的中间结果。 2 ga函数。[X,F, FLAG,OUTPUT] = GA(fun, n,opts).n为自变量个数,opts为遗传算法控制选项,用gaoptimset()函数设置各种选项,InitialPopulation可以设置初始种群,用PopulationSize 可以设置种群规模,SelectionFcn可以定义选择函数, 3 gatool 函数用于打开,GATOOL is now included in OPTIMTOOL。 2.2 通过GUI 使用遗传算法 在Matlab 工作窗口键入下列命令>>gatool,或通过Start 打开其下子菜单Genetic Algorithm Tool,如图1。只要在相应的窗格选择相应的选项便可进行遗传算法的计算。其中fitnessfun 窗格为适应度函数,填写形式为@fitnessfun,Number of variable 窗格为变量个数。其它窗格参数根据情况填入。填好各窗格内容,单击Start 按钮,便可运行遗传算法 例子1 应用实例 已知某一生物的总量y(单位:万个)与时间t(月)之间的关系为y=k0(1-exp(-k1*t)), 统计十个月得到数据见表1,试求关系式中的k0,k1。先编写目标函数,并以文件名myfung.m

4-第二篇 第2章 遗传算法的基本实现技术

第 2 章 遗传算法的基本实现技术
在第一章中,以实例简述的形式提供了遗传算法的一个基本框架。基于对自然界中生物遗传和进化机 理的模仿,许多学者针对不同的问题,设计了不同的编码方法和不同的遗传算子来模仿不同环境下生物的 遗传特性。这样,由不同的编码方法和不同的遗传算子就构成了各种特点的遗传算法,下面我们根据遗传 算法的基本构成要素来阐述其基本的实现技术。
2.1 编码方法
遗传算法的特点之一是不对求解问题的决策变量直接进行操作,而是通过对个体编码,并进行交叉与 变异的进化运算过程,不断搜索出适应度较高的新个体,最终寻求出问题的最优解或近似最优解。由于遗 传算法不能直接处理问题空间或解空间的参数,必须把它们转换成表达空间或搜索空间的染色体,这一转 换操作称为编码。
2.1.1 编码原则 应用遗传算法计算时,遇到的首要问题就是编码,可以说它是整个计算的一个关键步骤。编码方法除
决定了个体的染色体排列形式,还决定了个体从搜索空间的基因型变换到解空间的表现型时的解码方法。 编码方法也影响到交叉算子、变异算子等遗传算子的运算方法。由此可见,编码方法在很大程度上决定了 如何进行群体的遗传进化运算以及遗传进化运算的效率。一个好的编码方法,有可能使遗传运算和操作过 程简单地执行;一个差的编码方法,一方面影响运算精度和储存量,另一方面可能使交叉及变异等运算难 以实现。如果编码方法和交叉处理不当,在遗传算法中因交叉而生成的个体有可能成为无用解或无效解。
另外,编码和交叉的策略是互相依存的,恰当地设计编码和交叉的策略与方法,对充分发挥遗传算法 的效能是十分重要的,在设计编码策略时,常考虑以下三个问题:
1. 完备性:对问题空间的任何一个点有搜索空间的一个点与之对应。即问题空间的所有可能解都能 表示为所设计的基因编码形式。
2. 健全性:对于表达空间中的任何一个点都有问题空间中的一个点与之对应。即任何一个基因编码 都对应于一个可能解;
3. 非冗余性:问题空间和表达空间一一对应。 上述三点表明,编码策略必须保证从问题空间到表达空间有一对一的映射关系。 应该注意的是,对于很多问题,很难设计出同时满足上述 3 个性质的编码方案,不管怎样,完备性是 必须满足的性质,在有些情况下,虽然产生无效解并不完全都是有害的,在大部分情况下是影响运算效率 的。 上述三个编码评估规范虽然带有普遍意义,但缺乏具体的指导思想,特别是满足这些规范的编码不一 定能有效地提高遗传算法的搜索效率。 De Jong 提出了较为客观明确的编码评估准则,他称之为编码原则,又称之为编码规则: 1. 有意义基因块编码规则:应使用能易于产生与所求问题相关的低阶、短定义长度模式的编码方案。 在此原则中,模式是指具有某些基因相似性的个体集合,而具有低阶、短定义长度且适应度较高的模 式称为构造优良个体的基因块。该编码原则理解为应使用易于生成适应度较高的个体编码方案。 2. 最小字符集编码原则:所设计的编码方案应采用最小字符集以使问题得到自然的表示或描述。 在此原则中说明常常使用二进制编码方法的原因,因为它满足这条编码原则的要求。根据理论分析表 明,与其他编码字符集相比,二进制编码方案能包含最大的模式数,它可使得遗传算法在确定的规模群体 中能够处理最多的模式。 上述 De Jong 编码原则,仅仅是为编码设计提出了一定的准则,它并不适合于所有的问题,在处理实 际应用问题时,必须对编码方法、交叉运算方法、变异运算方法、解码方法等统筹考虑。以便对问题求解 简便,寻求遗传运算效率最高的编码方法。

遗传算法的原理及MATLAB程序实现

1 遗传算法的原理 1.1 遗传算法的基本思想 遗传算法(genetic algorithms,GA)是一种基于自然选择和基因遗传学原理,借鉴了生物进化优胜劣汰的自然选择机理和生物界繁衍进化的基因重组、突变的遗传机制的全局自适应概率搜索算法。 遗传算法是从一组随机产生的初始解(种群)开始,这个种群由经过基因编码的一定数量的个体组成,每个个体实际上是染色体带有特征的实体。染色体作为遗传物质的主要载体,其内部表现(即基因型)是某种基因组合,它决定了个体的外部表现。因此,从一开始就需要实现从表现型到基因型的映射,即编码工作。初始种群产生后,按照优胜劣汰的原理,逐代演化产生出越来越好的近似解。在每一代,根据问题域中个体的适应度大小选择个体,并借助于自然遗传学的遗传算子进行组合交叉和变异,产生出代表新的解集的种群。这个过程将导致种群像自然进化一样,后代种群比前代更加适应环境,末代种群中的最优个体经过解码,可以作为问题近似最优解。 计算开始时,将实际问题的变量进行编码形成染色体,随机产生一定数目的个体,即种群,并计算每个个体的适应度值,然后通过终止条件判断该初始解是否是最优解,若是则停止计算输出结果,若不是则通过遗传算子操作产生新的一代种群,回到计算群体中每个个体的适应度值的部分,然后转到终止条件判断。这一过程循环执行,直到满足优化准则,最终产生问题的最优解。图1-1给出了遗传算法的基本过程。 1.2 遗传算法的特点 1.2.1 遗传算法的优点 遗传算法具有十分强的鲁棒性,比起传统优化方法,遗传算法有如下优点: 1. 遗传算法以控制变量的编码作为运算对象。传统的优化算法往往直接利用控制变量的实际值的本身来进行优化运算,但遗传算法不是直接以控制变量的值,而是以控制变量的特定形式的编码为运算对象。这种对控制变量的编码处理方式,可以模仿自然界中生物的遗传和进化等机理,也使得我们可以方便地处理各种变量和应用遗传操作算子。 2. 遗传算法具有内在的本质并行性。它的并行性表现在两个方面,一是遗传

遗传算法与优化问题

实验十遗传算法与优化问题 一、问题背景与实验目的 遗传算法(Genetic Algorithm —GA),就是模拟达尔文的遗传选择与自然淘汰的生物进化过程的计算模型,它就是由美国Michigan大学的J、Holla nd教授于1975 年首先提出的?遗传算法作为一种新的全局优化搜索算法,以其简单通用、鲁棒性强、适于并行处理及应用范围广等显著特点,奠定了它作为21世纪关键智能计算之一的地位. 本实验将首先介绍一下遗传算法的基本理论,然后用其解决几个简单的函数最值问题,使读者能够学会利用遗传算法进行初步的优化计算? 1. 遗传算法的基本原理 遗传算法的基本思想正就是基于模仿生物界遗传学的遗传过程?它把问题的参数用基因代表,把问题的解用染色体代表(在计算机里用二进制码表示),从而得到一个由具有不同染色体的个体组成的群体?这个群体在问题特定的环境里生存 竞争,适者有最好的机会生存与产生后代?后代随机化地继承了父代的最好特征,并也在生存环境的控制支配下继续这一过程.群体的染色体都将逐渐适应环境,不断进化,最后收敛到一族最适应环境的类似个体,即得到问题最优的解?值得注意的一点就是,现在的遗传算法就是受生物进化论学说的启发提出的,这种学说对我们用计算机解决复杂问题很有用,而它本身就是否完全正确并不重要(目前生物界对此学说尚有争议). (1)遗传算法中的生物遗传学概念 由于遗传算法就是由进化论与遗传学机理而产生的直接搜索优化方法;故而 在这个算法中要用到各种进化与遗传学的概念? 首先给出遗传学概念、遗传算法概念与相应的数学概念三者之间的对应关系这些概念

(2)遗传算法的步骤 遗传算法计算优化的操作过程就如同生物学上生物遗传进化的过程,主要有三个基本操作(或称为算子):选择(Selection)、交叉(Crossover)、变异(Mutation). 遗传算法基本步骤主要就是:先把问题的解表示成“染色体”,在算法中也就就是以二进制编码的串,在执行遗传算法之前,给出一群“染色体”,也就就是假设的可行解.然后,把这些假设的可行解置于问题的“环境”中,并按适者生存的原则从中选 择出较适应环境的“染色体”进行复制 ,再通过交叉、变异过程产生更适 应环境的新一代“染色体”群.经过这样的一代一代地进化,最后就会收敛到最适应环境的一个“染色体”上,它就就是问题的最优解. 下面给出遗传算法的具体步骤,流程图参见图1: 第一步:选择编码策略,把参数集合(可行解集合)转换染色体结构空间; 第二步:定义适应函数,便于计算适应值; 第三步:确定遗传策略,包括选择群体大小,选择、交叉、变异方法以及确定交叉概率、变异概率等遗传参数; 第四步:随机产生初始化群体; 第五步:计算群体中的个体或染色体解码后的适应值; 第六步:按照遗传策略,运用选择、交叉与变异算子作用于群体,形成下一代群体; 第七步:判断群体性能就是否满足某一指标、或者就是否已完成预定的迭代次数,不满足则返回第五步、或者修改遗传策略再返回第六步. 图1 一个遗传算法的具体步骤

遗传算法C语言源代码(一元函数和二元函数)

C语言遗传算法代码 以下为遗传算法的源代码,计算一元代函数的代码和二元函数的代码以+++++++++++++++++++++++++++++++++++++为分割线分割开来,请自行选择适合的代码,使用时请略看完代码的注释,在需要更改的地方更改为自己需要的代码。 +++++++++++++++++++++++++++++++一元函数代码++++++++++++++++++++++++++++ #include #include #include #include #define POPSIZE 1000 #define maximization 1 #define minimization 2 #define cmax 100 #define cmin 0 #define length1 20 #define chromlength length1 //染色体长度 //注意,你是求最大值还是求最小值 int functionmode=minimization; //变量的上下限的修改开始 float min_x1=-2;//变量的下界 float max_x1=-1;//变量的上界 //变量的上下限的修改结束 int popsize; //种群大小 int maxgeneration; //最大世代数 double pc; //交叉率 double pm; //变异率 struct individual { char chrom[chromlength+1]; double value; double fitness; //适应度 }; int generation; //世代数 int best_index; int worst_index;

遗传算法小生境技术简介

遗传算法小生境技术简介 生物学上,小生境是指特定环境下的一种组织结构。在自然界中,往往特征,形状相似的物种相聚在一起,并在同类中交配繁衍后代。在SGA 中,交配完全是随机的,在进化的后期,大量的个体集中于某一极值点上,在用遗传算法求解多峰值问题时,经常只能找到个别的几个最优值,甚至往往得到是局部最优解。利用小生境我们可以找到全部最优解。 小生境技术就是将每一代个体划分为若干类,每个类中选出若干适应度较大的个体作为一个类的优秀代表组成一个群,再在种群中,以及不同种群中之间,杂交,变异产生新一代个体群。同时采用预选择机制和排挤机制或分享机制完成任务。基于这种小生境的遗传算法(Niched Genetic Algorithms,NGA),可以更好的保持解的多样性,同时具有很高的全局寻优能力和收敛速度,特别适合于复杂多峰函数的优化问题。 模拟小生境技术主要建立在常规选择操作的改进之上。Cavichio 在1970年提出了基于预选择机制的选择策略,其基本做法是:当新产生的子代个体的适应度超过其父代个体的适应度时,所产生的子代才能代替其父代而遗传到下一代群体中去,否则父代个体仍保留在下一代群体中。由于子代个体和父代个体之间编码结构的相似性,所以替换掉的只是一些编码结构相似的个体,故它能够有效的维持群体的多样性,并造就小生境的进化环境。De Jong在1975年提出基于排挤机制的选择策略,其基本思想源于在一个有限的生存环境中,各种不同的生物为了能够延续生存,他们之间必须相互竞争各种有限的生存资源。因此,在算法中设置一个排挤因子CF(一般取CF=2或3),由群体中随机选取的1/CF 个个体组成排挤成员,然后依据新产生的的个体与排挤成员的相似性来排挤一些与预排挤成员相类似的个体,个体之间的相似性可用个体编码之间的海明距离来度量。随着排挤过程的进行,群体中的个体逐渐被分类,从而形成一个个小的生成环境,并维持群体的多样性。 Goldberg等在1987年提出了基于共享机制(Sharing)的小生境实现方法。这种实现方法的基本思想是:通过反映个体之间的相似程度的共享函数来调节群体中各个个体的适应度,从而在这以后的群体进化过程中,算法能够依据这个调整后的新适应度来进行选择运算,以维持群体的多样性,创造出小生境的进化环境。 共享函数(Sharing Function)是表示群体中两个个体之间密切关系程度的一个函数,可记为S(d )其中表示个体i和j之间的关系。例如,个体基因型之间的海明距离就可以为一种共享函数。这里,个体之间的密切程度主要体现为个体基因型的相似性或个体表现型的相似性上。当个体之间比较相似时,其共享函数值就比较大;反之,当个体之间不太相似时,其共享函数值比较小。 共享度是某个个体在群体中共享程度的一中度量,它定义为该个体与群体内其它各个个体之间的共享函数值之和,用S 表示: S = (i=1,,M) 在计算出了群体中各个个体的共享度之后,依据下式来调整各个个体的适应度:F (X)=F (X)/S (i=1,,M) 由于每个个体的遗传概率是由其适应度大小来控制的,所以这种调整适应度的方法就能够限制群体中个别个体的大量增加,从而维护了群体的多样性,并造就了一种小生境的进化环境。

相关文档