文档介绍：《人工智能及其应用大作业(一)》
题目: 基本遗传算法及其在函数优化中的作用
学号:
姓名:
基本遗传算法及其在函数优化中的应用
摘要:
从遗传算法的编码、遗传算子等方面剖析了遗传算法求解无约束函数优化问题的一般步骤,并以一个实例说明遗传算法能有效地解决函数优化问题。本文利用基本遗传算法求解函数优化问题,选用 f(x)=xsin(10πx)+,取值范围在中,利用基本遗传算法求解两个函数的最优值,遗传算法每次100代,一共执行10次,根据运算结果分析得到最优解。
关键字:遗传算法选择交叉变异函数优化

遗传算法(ic Algorithm)是一类借鉴生物界的进化规律(适者生存,优胜劣汰遗传机制)演化而来的随机化搜索方法。遗传算法是一种群体型操作,该操作以群体中的所有个体为对象。选择(Selection)、交叉(Crossover)和变异(Mutation)是遗传算法的3个主要操作算子,它们构成了所谓的遗传操作(ic operation),使遗传算法具有了其它传统方法所没有的特性。
遗传算法的特点
其主要特点是直接对结构对象进行操作,不存在求导和函数连续性的限定;具有内在的隐并行性和更好的全局寻优能力;采用概率化的寻优方法,能自动获取和指导优化的搜索空间,自适应地调整搜索方向,不需要确定的规则。

函数优化,组合优化,机器人智能控制,及组合图像处理和模式识别等。
基本遗传算法

Step1:参数设置及种群初始化;
Step2:适应度评价;
Step3:选择操作;
Step4:交叉操作;
Step5:变异操作;
Step6:终止条件判断,若未达到终止条件,则转到Step3;
Step7:输出结果。

完成了预先给定的进化代数则停止;
群体中的最优个体在连续若干代没有改进或平均适应度在连续若干代基本没有改进时停止。

开始
Gen=0
编码
随机产生M个初始个体
满足终止条件?
计算群体中各个体适应度
从左至右依次执行遗传算子
j = 0
j = 0
j = 0
根据适应度选择复制个体
选择两个交叉个体
选择个体变异点
执行变异
执行交叉
执行复制
将复制的个体添入新群体中
将交叉后的两个新个体添入新群体中
将变异后的个体添入新群体中
j = j+1
j = j+2
j = j+1
j = M?
j = pc·M?
j = pm·L·M?
Gen=Gen+1
输出结果
终止
Y
N
Y
Y
Y
N
N
N
pc
pm

本小节采用以下函数: f(x)=xsin(10πx)+,x[-1,2]

表现型:x
基因型:二进制编码(串长取决于求解精度)
按编码原理:假设要求求解精度到6位小数,区间长度为2-(-1)=3,即需将区间分为3/=3
×106等份。
所以编码的二进制串长应为22位。

产生的方式:随机
产生的结果:长度为22的二进制串
产生的数量:种群的大小(规模),如30,50,…
1111010011100001011000
1100110011101010101110
10101000111**********
10111100100**********
0001100101001100000011
00000110100**********
...

直接用目标函数作为适应度函数
①解码:将个体s转化为[-1,2]区间的实数:
s=<10001011101**********> → x=
②计算x的函数值(适应度):
f(x)=xsin(10πx)+=

选择:比例选择法;
交叉:单点交叉;
变异:小概率变异

设置的参数:
种群大小80;;;最大代数100。
运行结果如下表:

1
2
3
4
5
6
7
8
9
10
best_fit

best_f