遗传算法
1.遗传算法的研究对象:
研究各种非线性、多变量、多目标、复杂的自适应系统问题。
2.遗传算法的基本特征:
- 智能式搜索:依据适应度(目标函数)进行智能搜索。
- 渐进式优化:利用复制、交换、突变等操作,使下一代结果优于上一代。
- 全局最优解:利用交换和突变操作产生新个体,使得搜索得到的优化结果逼近全局最优解
- 黑箱式结构:根据问题的特性进行编码(输入)和确定适应度(输出),具有只考虑输入与输出关系的黑箱式结构,并不深究输入与输出关系的原因。
- 通用性强:不要求明确的数学表达式,只需要一些简单的原则要求,可应用于解决离散问题、函数关系不明确的复杂问题。
- 并行式运算:每次迭代计算都是对群体中的所有个体同时进行运算,是并行式运算方式,搜索速度快。
3.遗传算法运算流程图:
4.几个重要概念
- 编码:遗传算法的工作对象是字符串,对字符串的编码要求:字符串要反映所研究问题的性质;字符串的表达式要便于计算机处理。
- 适应度:在遗传算法中,衡量个体优劣的尺度是适应度。根据适应度的大小决定个体繁殖的数量、或者决定其是否消亡。适应度是驱动遗传算法的动力。
- 交换:产生新个体的一种方法,将两个个体的部分字符互相交换
- 变异:产生新个体的另一种方法,将被选择的个体的部分字符进行补运算。
- 终止条件:遗传算法是一种反复迭代的搜索方法,它通过多次进化逐渐逼近最优解。最常用的终止方法是迭代函数。当目标函数有最优目标值时,可采用控制偏差的方式实现终止。第三种终止方法是检查适应度变化。
5. 模式理论的基本概念
编码的左边数字越小,则其适应度将越大。这种字符串(编码)的形式特征就叫做编码的模式。
模式中确定的字符的个数称为模式的阶次(Order),记作O(H)。例如:0(000**)=3。
模式中最前面和最后面两个确定字符串的距离称为模式的长度(H),
(00*0*)=3,
(*0***)=0