vc程序设计（遗传算法）

/**************************************************************/

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

/* 同济大学计算机系 王小平 2000年5月 */

/**************************************************************/

#include<stdio.h>

#include<stdlib.h>

#include<graphics.h>

#include<math.h>

#include<time.h>

#include<string.h>

#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=0i<pop_sizei++)

for(j=0j<g_lengthj++)

*(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=0i<g_lengthi++)

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=0i<pop_sizei++)

{

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=0i<pop_sizei++) /* 轮盘赌的选择循环 */

sum_of_fitness=sum_of_fitness+*(fitness+i)

for(i=0i<pop_sizei++)

{

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

num=0

border=*fitness

while(border<r)

{

num++

border=border+*(fitness+num)

}

for(j=0j<g_lengthj++)

*(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=0i<pop_size-1i=i+2)

{

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_posj<g_lengthj++) /* 两个父个体之间部分遗传基因的交换 */

{ work=*(gene1+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=0i<pop_sizei++)

{

for(j=0j<g_lengthj++)

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 /* 变量最大值 <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=0i<3i++) /* 优化函数为三个三角函数之和 */

{

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=0x<=xmaxx++) /* 将优化函数正规化为[0,1]区间数 */

{

fx=(double)x

f_value=0.0

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

{

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<f_min) f_min=f_value

*(func+x)=(double)f_value

}

f_range=f_max-f_min

f_mid=(f_max+f_min)/2.0

for(x=0x<=xmaxx++)

{

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=1i<=xmaxi++)

{

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=0i<pop_sizei++)

{

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

for(j=0j<g_lengthj++)

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=0i<pop_sizei++)

{

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=0i<gen_maxi++)

{

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=0j<pop_sizej++)

{

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

for(k=0k<g_lengthk++)

*(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()

}

当前科学技术正进入多学科互相交叉、互相渗透、互相影响的时代，生命科学与工程科学的交叉、渗透和相互促进是其中一个典型例子，也是近代科学技术发展的一个显著特点。遗传算法的蓬勃发展正体现了科学发展的这一特点和趋势。

制造机器智能一直是人类的梦想，人们为此付出了巨大的努力。人工智能技术的出现，就是人们得到的成果。但是，近年来，随着人工智能应用领域的不断拓广，传统的基于符号处理机制的人工智能方法在知识表示、处理模式信息及解决组合爆炸等方面所碰到的问题已变得越来越突出，这些困难甚至使某些学者对强人工智能提出了强烈批判，对人工智能的可能性提出了质疑。

众所周知，在人工智能领域中，有不少问题需要在复杂而庞大的搜索空间中寻找最优解或准优解。像货朗担问题和规划问题等组合优化问题就是典型的例子。在求解此类问题时，若不能利用问题的固有知识来缩小搜索空间则会产生搜索的组合爆炸。因此，研究能在搜索过程中自动获得和积累有关搜索空间的知识，并能自适应地控制搜索过程，从而得到最优解或准有解的通用搜索算法一直是令人瞩目的课题。遗传算法就是在这种背景下产生并经实践证明特别有效的算法。

遗传算法(Genetic Algorithm, GA)是近年来迅速发展起来的一种全新的随机搜索与优化算法,其基本思想是基于Darw in的进化论和Mendel的遗传学说。该算法由密执安大学教授Holland及其学生于1975年创建。此后，遗传算法的研究引起了国内外学者的关注。自1985年以来.国际上已召开了多次遗传算法的学术会议和研讨会.国际遗传算法学会组织召开的ICGA( International Conference on Genetic Algorithms)会议和FOGA( Workshop on Foundation of Genetic Algorithms)会议。为研究和应用遗传算法提供了国际交流的机会。

作为一种通用的问题求解方法，遗传算法采用简单的编码技术来表示各种复杂的结构并通过对一组编码表示进行简单的遗传 *** 作和优胜劣汰的自然选择来指导学习和确定搜索的方向。

近年来，遗传算法已被成功地应用于下业、经济答理、交通运输、工业设计等不同领域.解决了许多问题。例如，可靠性优化、流水车间调度、作业车间调度、机器调度、设备布局设计、图像处理以及数据挖掘等。本文将从遗传算法的理论和技术两方而概述目前的研究现状。描述遗传算法的主要特点、基木原理以及各种改进算法，介绍遗传算法的程序设计。

遗传程序设计是借鉴生物界的自然选择和遗传机制，在遗传算法的基础上发展起来的搜索算法，它己成为进化计算的一个新分支。在标准的遗传算法中，由定长字符串(问题的可行解)组成的群体借助于复制、交叉、变异等遗传 *** 作不断进化找到问题的最优解或次优解。遗传程序设计运用遗传算法的思想，常采用树的结构来表示计算机程序，从而解决问题。对于许多问题，包括人工智能和机器学习上的问题都可看作是需要发现一个计算机程序，即对特定输入产生特定输出的程序，形式化为程序归纳，那么遗传程序设计提供了实现程序归纳的方法。

把遗传算法和计算机程序结合起来的思想出现在遗传算法中，Holland把产生式语言和遗传算法结合起来实现分类系统，还有一些遗传算法应用领域的研究者将类似于遗传算法的遗传 *** 作施加于树结构的程序上。

近年来，遗传程序设计运用遗传算法的思想自动生成计算机程序解决了许多问题，如预测、分类、符号回归和图像处理等，作为一种新技术它己经与遗传算法并驾齐驱。 1996年，举行了第1次遗传程序设计国际会议，该领域己引起越来越多的相关学者们的兴趣。

1967年，Holland的学生J.D.Bagley在博士论文中首次提出“遗传算法（Genetic Algorithms）”一词。此后，Holland指导学生完成了多篇有关遗传算法研究的论文。1971年，R.B.Hollstien在他的博士论文中首次把遗传算法用于函数优化。1975年是遗传算法研究历史上十分重要的一年。这一年Holland出版了他的著名专著《自然系统和人工系统的自适应》（Adaptation in Natural and Artificial Systems），这是第一本系统论述遗传算法的专著，因此有人把1975年作为遗传算法的诞生年。Holland在该书中系统地阐述了遗传算法的基本理论和方法，并提出了对遗传算法的理论研究和发展极其重要的模式理论（schema theory）。该理论首次确认了结构重组遗传 *** 作对于获得隐并行性的重要性。同年，K.A.De Jong完成了他的博士论文《一类遗传自适应系统的行为分析》（An Analysis of the Behavior of a Class of Genetic Adaptive System）。该论文所做的研究工作，可看作是遗传算法发展进程中的一个里程碑，这是因为，他把Holland的模式理论与他的计算实验结合起来。尽管De Jong和Hollstien 一样主要侧重于函数优化的应用研究，但他将选择、交叉和变异 *** 作进一步完善和系统化，同时又提出了诸如代沟（generation gap）等新的遗传 *** 作技术。可以认为，De Jong的研究工作为遗传算法及其应用打下了坚实的基础，他所得出的许多结论，迄今仍具有普遍的指导意义。

进入八十年代，遗传算法迎来了兴盛发展时期，无论是理论研究还是应用研究都成了十分热门的课题。1985年，在美国召开了第一届遗传算法国际会议（International Conference on Genetic Algorithms ，ICGA），并且成立国际遗传算法学会（International Society of Genetic Algorithms ，ISGA），以后每两年举行一次。

1989年，Holland的学生D.E.Goldberg出版了专著《搜索、优化和机器学习中的遗传算法》（Genetic Algorithms in Search , Optimization, and Machine Learning）。该书总结了遗传算法研究的主要成果，对遗传算法及其应用作了全面而系统的论述。同年，美国斯坦福大学的Koza基于自然选择原则创造性地提出了用层次化的计算机程序来表达问题的遗传程序设计( genetic programming, GP)方法，成功地解决了许多问题。

在欧洲，从1990年开始每隔一年举办一次Parallel Problem Solving from Nature 学术会议，其中遗传算法是会议主要内容之一。此外，以遗传算法的理论基础为中心的学术会议还有Foundations of Genetic Algorithms，该会也是从1990年开始隔年召开一次。这些国际会议论文，集中反映了遗传算法近些年来的最新发展和动向。

1991年，L.Davis编辑出版了《遗传算法手册》（Handbook of Genetic Algorithms），其中包括了遗传算法在工程技术和社会生活中的大量应用实例。

1992年，Koza发表了他的专著《遗传程序设计:基于自然选择法则的计算机程序设计》”。1994年，他又出版了《遗传程序设计，第二册:可重用程序的自动发现》深化了遗传程序设计的研究，使程序设计自动化展现了新局面。有关遗传算法的学术论文也不断在《Artificial Intelligence》、《Machine Learning》、《Information science》、《Parallel Computing》、《Genetic Programming and Evoluable Machines》\《IEEE Transactions on Neural Networks》,《IEEE Transactions on Signal Processing》等杂志上发表。1993年，MIT出版社创刊了新杂志《Evolutionary Computation》。1997年，IEEE又创刊了《Transactions on Evolutionary Computation》。《Advanced Computational Intelligence》杂志即将发刊，由模糊集合创始人L.A.Zadeh教授为名誉主编。目前，关于遗传算法研究的热潮仍在持续，越来越多的从事不同领域的研究人员已经或正在置身于有关遗传算法的研究或应用之中。

工智能（Artificial Intelligence）是研究、开发用于模拟、延伸和扩展人智能的理论、方法、技术及应用系统的一门新技术科学。人工智能领域的研究包括机器人、语言识别、图像识别、自然语言处理和专家系统等。

人工智能（Artificial Intelligence），英文缩写为AI。它是研究、开发用于模拟、延伸和扩展人的智能的理论、方法、技术及应用系统的一门新技术科学。

人工智能是计算机科学的一个分支，它企图了解智能的实质，可以产出一种新的可以和人类智能相似的方式做出反应的智能机器，该领域的研究主要有机器人、语言识别、图像识别、自然语言处理和专家系统等。

自从人工智能诞生以来，理论和技术越来越成熟，应用领域在不断的扩大，可以设想，未来人工智能带来的科技产品，将会是人类智慧的“容器”。人工智能可以把人的意识、思维的信息过程的模拟。虽然人工智能不是人的智能，但可以像人那样思考、最终可能超过人的智能。

优点：

1、在生产方面，效率更高且成本低廉的机器及人工智能实体代替了人的各种能力，人类的劳动力将大大被解放。

2、人类环境问题将会得到一定的改善，较少的资源可以满足更大的需求。

3、人工智能可以提高人类认识世界、适应世界的能力。

缺点：

1、人工智能代替了人类做各种各样的事情，人类失业率会明显的增高，人类就会处于无依靠可生存的状态。

---