📄 ga.txt
字号:
遗传算法(Genetic Algorithm,GA)是一种抽象于生物进化过程的基于自然选择和生物遗传机制的优化技术.
遗传算法的基本原理
在遗传算法的执行过程中,每一代有许多不同的种群个体(染色体 )同时存在。这些染色体中哪个保留(生存)、哪个淘汰(死亡),是根据 它们对环境的适应能力来决定的,适应性强的有更多的机会保留下来 。适应性强弱是通过计算适应性函数f(x)的值来判别的,这个值称为适应值。适应值函数f(x)的构成与目标函数有密切关系,往往是目标函数的变种。主要的遗传算子有如下几种:
1.选择(Selection)算子又称复制(reproduction)、繁殖算子。选择是从种群中选择生命力强的染色体,产生新种群的过程。选择的依据是每个染色体的适应值大小,适应值越大,被选中的概率就越大,其子孙在下一代产生的个数就越多。选择的方法根据不同的问题,采用不同的方案。最常见的方法有比率法、排列法和比率排列法。
2.交叉(Crossover)算子又称重组(recombination)、配对(breeding)算子。当许多染色体相同或后代的染色体与上一代没有多大差别时,可通过染色体重组来产生新一代染色体。染色体重组分两个步骤进行:首先,在新复制的群体中随机选取两个染色体,每个染色体由多个位(基因)组成;然后,沿着这两个染色体的基因随机取一个位置,二者互换从该位置起的末尾部分基因。例如,有两个用二进制编码的个体A和B,长度L=5,A=a1a2a3a4a5,B=b1b2b3b4b5。随机选择一个整数k∈[1,L-1],设k=4,经交叉后变为:
A=a1a2a3|a4a5 A'=a1a2a3b4b5
B=b1b2b3|b4b5 B'=b1b2b3a4a5
遗传算法的有效性主要来自选择和交叉操作,尤其是交叉,在遗传算法中起着核心作用。
3.变异(Mutation)算子
选择和交叉算子基本上完成了遗传算法的大部分搜索功能,而变异则增加了遗传算法找到接近最优解的能力。变异就是以很小的概率,随机改变字符串某个位置上的值。在二进制编码中,就是将0变成1,将1变成0。变异发生的概率极低(一般取值在0.001～0.02之间)。它本身是一种随机搜索,但与选择、交叉算子结合在一起,就能避免由复制和交叉算子引起的某些信息的永久性丢失,从而保证了遗传算法的有效性。
传算法是多学科结合与渗透的产物,已经发展成一种自组织、自适应的综合技术,广泛应用在计算机科学、工程技术和社会科学等领域。其研究工作主要集中在以下几个方面
1.基础理论
包括进一步发展遗传算法的数学基础,从理论和试验研究它们的计算复杂性。在遗传算法中,群体规模和遗传算子的控制参数的选取非常困难,但它们又是必不可少的试验参数。在这方面,已有一些具有指导性的试验结果。遗传算法还有一个过早收敛的问题,怎样阻止过早收敛也是人们正在研究的问题之一。
2.分布并行遗传算法
遗传算法在操作上具有高度的并行性,许多研究人员都在探索在并行机和分布式系统上高效执行遗传算法的策略。对分布并行遗传算法的研究表明,只要通过保持多个群体和恰当控制群体间的相互作用来模拟并行执行过程,即使不使用并行计算机,也能提高算法的执行效率。
3.分类系统
分类系统属于基于遗传算法的机器学习中的一类,包括一个简单的基于串规则的并行生成子系统、规则评价子系统和遗传算法子系统。分类系统被人们越来越多地应用在科学、工程和经济领域中,是目前遗传算法研究中一个十分活跃的领域。
4.遗传神经网络
包括连接权、网络结构和学习规则的进化。遗传算法与神经网络相结合,正成功地用于从时间序列分析来进行财政预算。在这些系统中,训练信号是模糊的,数据是有噪声的,一般很难正确给出每个执行的定量评价。如果采用遗传算法来学习,就能克服这些困难,显著提高系统性能。Muhlenbein分析了多层感知机网络的局限性,并猜想下一代神经网络将是遗传神经网络。
5.进化算法
模拟自然进化过程可以产生鲁棒的计算机算法——进化算法。遗传算法是其三种典型的算法之一,其余两种算法是进化规划(Evolutionary Programming,EP)和进化策略(Evolutio nary Strategies,ES)。这三种算法是彼此独立地发展起来的。进化规划最早由美国的L.J.Fogel、A.J.Owens和M.J.Walsh提出;进化策略则由德国的I.Rechenberg和H.P.Schwefel建立。具体应用也很广，我就拿它解决了好几个难题。
下面我给出我们校数学建模时的程序你分析一下就明白了。
#define Ins 35 /*指令数*/
#define Com 45/*部件数*/
#define Row 100
#define JCn 0*Row/*交叉的概率*/
#define FZn .15*Row
#define PY Row-JCn-FZn
#define times 1000 /*迭代次数*/
#define hyR .4*Ins/*交叉概率*/
#define Optnum 5 /*最优解的个数*/
#include "stdlib.h"
#include "time.h"
#include "stdio.h"
#include "conio.h"
unsigned char *A[Row+1]; /*遗传矩阵*/
unsigned char *Aimg[Row+1]; /*A的备份*/
unsigned long Aused[Row+1];
unsigned long Acomnum[Row+1];
unsigned long Ainsnum[Row+1];
unsigned long Opt[Optnum+1][Ins+1]; /*最优的解*/
unsigned long Optins[Optnum+1]; /*最优解的指令个数*/
double ada[Ins+1]; /*行适应度*/
char ins[Ins+1][Com+1]={{0},{0,4,8,20,31,44},{0,8,19,22,29,37}，{0,2,16,34,33,32},{0,7,11,35,30},{0,5,13,18,21},{0,1,7,9,23,25},
{0,3,5,6,14,24},{0,7,20,21,32,35},{0,9,15,20,45},{0,6,10,39,42,43},{0,1,11,21,34,38},{0,2,4,18,22,37},{0,6,17,25,36},{0,22,33,34,38},{0,2,10,20,37},{0,9,24,29,39},{0,15,18,29,31},{0,4,42,44,45},{0,13,23,26,39},{0,7,12,40,41},{0,12,16,19,28,35},{0,6,23,27,45},{0,33,37,40,41},{0,3,17,19,36},{0,16,33,44,45},{0,13,19,24,25},{0,2,3,5,8},{0,4,7,9,12,43},{0,16,17,20,32},{0,28,33,34,36},{0,10,23,25,27},{0,1,5,44,45},{0,11,15,18,43},{0,7,14,22,36},{0,3,15,25,39}};/*促使*/
char inslen[Ins+1]={0,15,80,30,12,7,19,32,12,45,36,57,78,65,53,34,48,46,32,26,22,26,19,17,22,10,30,82,73,66,55,24,46,37,77,9};/*指令长度*/
unsigned long step=0;
void iniA(void); /*初始化A*/
void adaRate(void); /*适应度*/
void judge(void); /*判断*/
void elim(void); /*选取:最优的五个解*/
void JC(void); /*交叉*/
void FZ1(void); /*复制*/
void PY1(void); /*变异*/
void back(void);
void showA(void); /*给出A*/
void showOpt(void); /*给出最优解*/
double rnd(void); /*给出0~1间的随机数*/
void main(void)
{randomize();
iniA();
while(1)
{adaRate();
judge();
elim();
if(step++>=times)
break;
JC();
FZ1();
PY1();
back();
}
showOpt();
}
void iniA(void)
{unsigned long i,j,knum=0;
for(i=1;i<=Row;i++)
A[i]=(unsigned char *)malloc(sizeof(char)*(Ins+1));
Aimg[i]=(unsigned char *)malloc(sizeof(char)*(Ins+1));
}
for(i=1;i<=Row;i++)
{for(j=1;j<=Ins;j++)
{if(rnd()>0.5) A[i][j]=1;
else a[i][j]=0;
}
}
for(i=1;i<=Optnum;i++)
{for(j=1;j<=Ins;j++)
{Opt[i][j]=1;
Optins[i]+=inslen[j];
}
}
}
void adaRate(void)
{unsigned long i,j,k;
double insnum,comnum;
int iscom[Com+1]; /** 部件是否出现 **/
for(i=1;i<=Row;i++)
{ada[i]=insnum=comnum=0;
for(j=1;j<=Com;j++)
iscom[j]=0;
for(j=1;j<=Ins;j++)
if(A[i][j])
{insnum+=inslen[j];
for(k=1;k<=Com;k++)
iscom[ins[j][k]]=1;
}
for(j=1;j<=Com;j++)
if(iscom[j]) comnum+=1;
if(insnum)
ada[i]=comnum/insnum; /**适应度函数**/
else
ada[i]=0;
Acomnum[i]=comnum;
Ainsnum[i]=insnum;
}}
void judge(void)
{}
void elim(void)
{unsigned long i,j,k;
for(i=1;i<=Row;i++) /*检查是否有更优解*/
if(Acomnum[i]==Com)
{for(j=1;j<=Optnum;j++)
if(Ainsnum[i]<Optins[j])
{Optins[j]=Ainsnum[i];
for(k=1;k<=Ins;k++)
Opt[j][k]=A[i][k];
break;
}}}
void JC(void)
unsigned long a,i,j,F,M; /* fsum 是行适应度的和 */
unsigned char used;
double fsum=0,f,m;
for(i=1;i<=Row;i++) /*初始化*/
{Aused[i]=0;
for(j=1;j<=Ins;j++)
Aimg[i][j]=0;
}
i=0;
while(i<JCn) /*这个while选取交叉的行*/
{a=random(Row)+1; /*因为random值域是从0到Row-1*/
used=0;
for(j=1;j<=i;j++)
if(Aused[j]==a)
used=1;
if(!used)
{Aused[++i]=a;
fsum+=ada[a];
}
}
for(i=1;i<=JCn;i++) /*这个for计算P(i)的值*/
ada[Aused[i]]/=fsum;
for(i=2;i<=JCn;i++) /*把P(i)值化为范围*/
ada[Aused[i]]+=ada[Aused[i-1]];
ada[(int)JCn]=1.0;
for(i=1;i<=JCn/2;i++)
{f=rnd();
for(j=1;j<=JCn;j++)
{if(ada[Aused[j]]>=f)
{M=F=j;
break;
}
}
while(M!=F)
{m=rnd();
for(j=1;j<=JCn;j++)
{if(ada[Aused[j]]>=m)
{M=j;
break;
}
}
}
for(j=1;j<=Ins;j++)
{Aimg[i*2-1][j]=A[M][j];
Aimg[i*2][j]=A[F][j];
}
}
for(i=1;i<=JCn/2;i++)
{for(j=1;j<=hyR;j++)
Aimg[i*2-1][j]=Aimg[i*2][(int)(Ins-hyR+j)];
for(j=1;j<=Ins-hyR;j++)
Aimg[i*2][j]=Aimg[i*2-1][(int)(hyR+j)];
}
for(i=1;i<=JCn;i++)
for(j=1;j<=Ins;j++)
A[Aused[i]][j]=Aimg[i][j];
}
void FZ1(void)
{unsigned long i=0,j,k,l,a;
unsigned char used;
while(i<FZn)
{a=random(Row)+1;
used=0;
for(j=1;j<=JCn+i;j++)
if(Aused[j]==a)
used=1;
if(!used) Aused[(int)((++i)+JCn)]=1;
}
}
void PY1(
Top
4 楼sdp（雨尘）回复于 2002-05-30 11:09:25 得分 0 遗传算法（Genetic Algorithm）
——遗传算法（Genetic Algorithm，缩写为GA）是一种有效的解决最优化问题的方法。它最先是由John Holland于1975年提出的。从那以后，它逐渐发展成为一种通过模拟自然进化过程解决最优化问题的计算模型。
--—利用遗传算法解最优化问题，首先应对可行域中的点进行编码（一般采用二进制编码），然后在可行域中随机挑选一些编码组成作为进化起点的第一代编码组，并计算每个解的目标函数值，也就是编码的适应度。接着就像自然界中一样，利用选择机制从编码组中随机挑选编码作为繁殖过程前的编码样本。选择机制应保证适应度较高的解能够保留较多的样本；而适应度较低的解则保留较少的样本，甚至被淘汰。在接下去的繁殖过程中，遗传算法提供了交叉和变异两种算子对挑选后的样本进行交换。交叉算子交换随机挑选的两个编码的某些位，变异算子则直接对一个编码中的随机挑选的某一位进行反转。这样通过选择和繁殖就产生了下一代编码组。重复上述选择和繁殖过程，直到结束条件得到满足为止。进化过程最后一代中的最优解就是用遗传算法解最优化问题所得到的最终结果。
——从以上介绍可以看出，GA算法具有下述特点：
GA是对问题参数的编码组进行进货，而不是直接对参数本身。
GA的搜索是从问题解的编码组开始搜索，而不是从单个解开始。
GA使用目标函数值（适应度）这一信息进行搜索，而不需导数等其他信息。
GA算法使用的选择、交叉、变异这三个算子都是随机操作，而不是确定规则。
——实践表明，遗传算法解最优化问题的计算效率比较高、适用范围相当广。为了解释这一现象，Holland给出了图式定理。所谓图式，就是某些码位取相同值的编码的集合。图式定理说明在进化过程的各代中，属于适应度高、阶数低且长度短的图式的编码数量将随代数以指数形式增长。另外，Holland还发现遗传算法具有隐含的并行计算特性。最近的研究则表明，上述遗传算法经适当改进后对任意优化问题以概率1收敛于全局最优解。
——将遗传算法用于解决各种实际问题后，人们发现遣传算法也会由于各种原因过早向目标函数的局部最优解收敛，从而很难找到全局最优解。其中有些是由于目标函数的特性造成的，例如函数具有欺骗性，不满足构造模块假说等等；另外一些则是由于算法设计不当。为此，不断有人对遗传算法提出各种各样的改进方案。例如：针对原先的定长二进制编码方案；提出了动态编码、实数编码等改进方案；针对按比例的选择机制，提出了竞争选择、按续挑选等改进方案；针对原先的一点交叉算子，提出了两点交叉、多点交叉、均匀交叉等算子；针对原先遗传算法各控制参数在进化过程中不变的情况，提出了退化遗传算法、自适应遗传算法等。另外，针对不同问题还出现了分布式遗传算法、并行遗传算法等等。
——近年来，随着对于遗传算法研究的不断深入完善，有越来越多的人认识了解了遗传算法，并把它应用到越来越广泛的领域，例如机器学习、模式识别、图像处理、神经网络、工业优化控制和社会科学等方面。特别是在解决旅行商问题、煤气管道的最优控制、通信网络链接长度的优化问题、铁路运输计划优化、喷气式收音机涡轮机的设计、VLSI版面设计、键盘排列优化等问题上遗传算法都取得了很大的成功。
——目前国际国内有关GA的研究热潮方兴未艾。除从1985年起每两年举办一届GA国际会议外，还有MIT从1993年开始出版的《Evolutionary Computatio》和《Adaptive Behavior》两种杂志、IEEE从今年起出版的专门关于进化计算的汇刊。另外，各种AI类的杂志不断出版有关进化计算的专辑。其它有关GA理论和工程应用的文章也在各种不同类型杂志上不断涌现。国内有关GA的研究也正在不断深入地展开。
Top
5 楼gmwang（随便看看）回复于 2002-09-23 11:17:54 得分 0 基本遗传算法源程序：
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define POPSIZE 50
#define MAXGENS 1000
#define NVARS 2
#define PXOVER 0.8
#define PMUTATION 0.25
#define TRUE 1
#define FALSE 0
int generation;
int cur_best;
float s;
FILE *galog;
struct genotype
{double gene[NVARS];
double fitness;
double upper[NVARS];
double lower[NVARS];
double rfitness;
double cfitness;
};
struct genotype population[POPSIZE+1];
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -