当前位置:首页 >> 计算机软件及应用 >>

遗传算法


人工智能 遗传算法

目录

1
2 3

遗传算法简介

详细设计

结果

遗传算法是一种最优化算法,所谓最优化问 题,就是这样一类问题,满足它的解(称为可行 解)有很多对于每一种解有一个评价函数得到一 个评价值,也就确定了解集的一个偏序关系,在 这个偏序关系的求最小值(或最大值)或者近似 最小值(或最大值)。因为通常可行解非常之多 ,所以确定性算法很难做到这一点,而遗传算法 是模拟了生物学中物种进化的过程的一种最优化 算法,简单来说: 遗传算法=遗传操作+遗传选择

Genetic Algorithm
遗传算法

要运行遗传算法就要对其进行抽象的编码, 也就是确定染色体的形式,这里的染色体就是用 某种特定的编码方式描述一个解,通常一个具体 的解也称为个体。而多个不同的个体就组成一个 种群,一个种群内有统一的编码方式。这些概念 都完全等同于生物学中的概念,它们是平行的。 例如,N个城市的旅行商问题(TSP),假如用 1,2,...N表示这N个城市,那对于任意这样的一个 排列1p2p3...pN就表示了一个解,这个串就可以 认为是一个染色体,它表示一个个体的基因。

编码

遗传算法有一些基本的操作,如选择、交叉和变异等 首先要知道适应度函数,它通常是 问题的目的函数,描述了个体的优劣程 度同时也决定了选择操作的概率,设fi表 示第i个个体的适应度值,那选择第i个个 选择操作 体的概率就是fi/∑fj。 简单来说,这个概率的大小就决定 了该个体是被淘汰还是被保留。通常的 具体做法是用类似赌盘的方法,每个个 体占它的适应度那么宽的转盘大小,每 次掷色子,落到哪一格就选哪一格对应 的个体。

交叉操作就是让2个以上的染色体进 行交叉产生后代的过程,交叉的原则就 是要有对称性,交叉得到的后代中的基 交叉操作 因要来源于父代的所有个体中,也就是 说N个个体进行交叉是和它们的排列没关 系,这样子代才有机会得到更优秀的基 因。交叉操作是遗传算法中最重要的操 作。最简单的基本方式是交换父代中染 色体片段。

生物可以突变,正是因为有了突变 才让有限的种群中基因库可以非常丰富 ,也保证了种群的适应能力。变异操作 通常是翻转个体中某段染色体,编码后 的染色体在计算机中都是01串,也就可 以随机的翻转某个bit上的值。 交叉和变异不是一定要发生在选择 了的个体上,而是按一定控制概率发生 的,交叉概率比较高通常是0.6~0.95, 而变异概率比较低通常是0.001~0.01。

变异操作

(1)随机给定隐层和输入层间神经元的初始权 值。 (2)由给定的样本输入计算出隐层的实际输出 。 改进算法的具体步骤 (3)计算输出层与隐层间的权值。以输出层的 第r个神经元为对象,由给定的输出目标值作为 等式的多项式值建立方程。 (4)重复第三步就可以求出输出层m个神经元 的权值,以求的输出层的权矩阵加上随机固定 的隐层与输入层的权值就等于神经网络最后训 练的权矩阵。

1,产生初始种群G 2,选择G,交叉、变异->G' 3,是否满足某个终止条件 ,如果没有重复上面过程。

遗传算法一般的结构

一般的遗传算法不一定 收敛,但给一个条件,让每 遗传算法的收敛 代中最优秀的个体直接进入 到子代,就能保证一定收敛 。

首先是种群规模,也就是种群中个体的数 目,如果太小,显然不利于快速收敛,如果太 大又会花更多的时间计算,通常选择100左右 的种群规模。其次,父代可不可以有机会进入 子代?如果某次交叉产生的子代比父代还差, 遗传算法的性能 那是否还要这个新个体?当然不,父代也要有 机会进入子代。然后就是终止条件,一般运用 遗传算法时,对最优解是不了解的,那我们就 不知道算法何时停止,一般使用的终止条件是 在进化M代后,每代中的最优个体没有提高时 停止。

求根号2,也就是求方程f(x)=x*x-2=0的正整数 解,x=1时f(1)<0,x=2时f(2)>0,由介值定理, 则1到2中间存在一个根,根据代数基本定理和 根的对称性知这就是我们要找的根,由目标函 数得到适应度函数,我们选择个体都在[1,2]之 遗传算法求根号2 间,那适应度函数我可以取 j(x)=40/(2+|x*x-2|)-10,由x的取值范围知j的范 围是(0,10) x和y交叉就用取平均(x+y)/2,交叉概率取0.9, 变异概率为0。

typedef struct _indi { double code; //染色体 double degree;//适应度 }Indi; Indi group[40]; //种群规模为40 void Judge(Indi &x) { double tmp=x.code*x.code-2.0; if(tmp>=0) x.degree=40.0/(2.0+tmp)-10.0; else x.degree=40.0/(2.0-tmp)-10.0; } int happened(double p)//发生一个p=0~1间概率的事件 { return rand()<(int)(p*RAND_MAX); }

void Cross(Indi &x,Indi &y)//交叉操作,产生一个子代取代父代中最次的一个 { Indi z; z.code=(x.code+y.code)/2.0; Judge(z); if(x.degree<y.degree) { if(z.degree<=x.degree) return;//如果新个体不如双亲,淘汰之 x=z; } else { if(z.degree<=y.degree) return; y=z; } }

void main() { int i,j,best,x,y,c; double sum,strick; for(i=0;i<40;++i)//随机得到初始种群 { group[i].code=1.0+(double)rand()/RAND_MAX; Judge(group[i]); } for(i=1;i<=10;++i)//固定进化10代 { for(sum=0.0,best=0,j=0;j<40;++j) { sum+=group[j].degree;//求总的适应度sum if(group[j].degree>group[best].degree) best=j;//求当前最优个体 } printf("第%2d代中 最优个体为 %10f(%10f) 平均适应度为 %10f\n", i,group[best].code,group[best].degree,sum/40.0);

for(c=40;c;--c) { strick=(double)rand()/RAND_MAX*sum; //赌盘中的色子,选择个体x,y for(x=0;x<40&&strick>=group[x].degree;++x) strick-=group[x].degree; strick=(double)rand()/RAND_MAX*sum; for(y=0;y<40&&strick>=group[y].degree;++y) strick-=group[y].degree; if(happened(0.9)) Cross(group[x],group[y]); //交叉 } } }

第 1代中 最优个体为 1.445692(适应度 9.138515) 平均适应度为 5.201076 第 2代中 最优个体为 1.414396(适应度 9.994853) 平均适应度为 6.789277 第 3代中 最优个体为 1.414396(适应度 9.994853) 平均适应度为 7.726777 第 4代中 最优个体为 1.414396(适应度 9.994853) 平均适应度为 8.267572 第 5代中 最优个体为 1.414396(适应度 9.994853) 平均适应度为 8.803805 第 6代中 最优个体为 1.414396(适应度 9.994853) 平均适应度为 9.147720 第 7代中 最优个体为 1.414113(适应度 9.997158) 平均适应度为 9.280602 第 8代中 最优个体为 1.414205(适应度 9.999755) 平均适应度为 9.356507 第 9代中 最优个体为 1.414205(适应度 9.999755) 平均适应度为 9.465438 第10代中 最优个体为 1.414211(适应度 9.999931) 平均适应度为 9.553306

运行结果


相关文章:
遗传算法_图文.ppt
遗传算法 - 现代机械设计概论 遗传算法 2008年12月 ? 1遗传算法概述 ? 2遗传算法基本原理与方法 ? 3遗传算法的应用 1.遗传算法概述 1.1 遗传算法的概念...
遗传算法流程图.doc
遗传算法流程图 - 开始 产生初始群体 计算适应度 交叉 是否满足 优化准则 变
遗传算法的基本原理111.doc
遗传算法的基本原理111 - 第二章 2.1 2.1.1 遗传算法的基本描述 全局优化问题 遗传算法的基本原理 全局优化问题的定义:给定非空集合 S 作为搜索空间,f:S...
遗传算法详解_图文.ppt
遗传算法详解 - 5.遗传算法 遗传算法 遗传算法( 简称GA) 遗传算法(ge
遗传算法_图文.ppt
遗传算法 - 贪婪算法 min f(x)=xcos(πx) s.t. 0<
人工智能(遗传算法).doc
人工智能(遗传算法) - 人工智能 遗传算法实验报告 实验目的 1. 熟悉和掌握遗传算法的原理、实质 2. 学会使用遗传算法解决问题 3. 学会编写遗传算法程序寻找函数最...
遗传算法和遗传规划_图文.pdf
遗传算法和遗传规划 - ...... 遗传算法和遗传规划_数学_自然科学_专业资料。 您的评论 发布评论 用户评价 关于遗传算法的内容,赞 2018-06-22 12:58:10 这...
遗传算法.doc
遗传算法 - 遗传算法 一、 概念 遗传算法(Genetic Algorithm
遗传算法学习心得.doc
遗传算法学习心得 - 基本概念 遗传算法(Genetic Algorithms,
手把手教你学matlab遗传算法.pdf
遗传算法| 把手| 手把手教你学matlab遗传算法_数学_自然科学_专业资料。遗传算法 matlab程序 函数优化 基于遗传算法求解函数最优值 1 . 选择函数形式:y=10*sin(...
遗传算法_图文.ppt
遗传算法 - 遗传算法 一 基本概念? 二 基本遗传算法? 三 遗传算法应用举例? 四 遗传算法的MATLAB求解 五 遗传算法的特点与发展 一、 基本概念 遗传算法的基本...
遗传算法options.pdf
遗传算法options - 一 问题设置和结果 1 问题 Fitness fun
遗传算法的c语言程序.doc
遗传算法的c语言程序 - 一 需求分析 1.本程序演示的是用简单遗传算法随机一个
遗传算法课件PPT_图文.ppt
遗传算法课件PPT - 第三章 遗传算法 1 遗传算法 ?五.遗传算法的各种变形
遗传算法的基本原理.doc
遗传算法的基本原理 - 遗传算法的基本原理和方法 一,编码 编码:把一个问题的可行解从其解空间转换到遗传算法的搜索空间的转换方法. 解码(译码):遗传算法解空间向...
遗传算法心得.doc
IV GA 的特点遗传算法的优点: (1)群体搜索,易于并行化处理; (2)不是
遗传算法的现状及发展动向.pdf
遗传算法的现状及发展动向 - 第 + 卷第 )期 # $# 年 月 # $ 文章
基于遗传算法的特征选择_图文.ppt
基于遗传算法的特征选择 - College of Mathematics and Computer Science 基于遗传算法的特征选择 College of Mathematics a...
遗传算法的MATLAB实现实例.doc
遗传算法的MATLAB实现实例 - 遗传算法(Genetic Algorithm
基本遗传算法.doc
基本遗传算法 - 遗传算法 1、 遗传算法生物学基础和基本理论 达尔文自然选择学
更多相关标签: