2遗传算法(3) 遗传算法技术介绍 河北大学 吴彬 ( wubinbb@163.com )
2.5连续性遗传算法 实数编码 河北大学 吴彬 ( wubinbb@163.com )
二进制数编码的不足 100个变量,[-250,250],精度0.00001 100×26=2600长的二进制串表示染色体。 此时的遗传算法的搜索空间大约为22600 。 河北大学 吴彬 ( wubinbb@163.com )
实数编码的优越性 适合于在遗传算法中表示范围较大的数。 适合于精度要求较高的问题。 便于与经典优化方法混合使用。 便于处理含约束条件的问题。 河北大学 吴彬 ( wubinbb@163.com )
设计遗传算法须注意问题 适应度,复制,不依赖于问题的编码方法。 选择,变异,运行后要保证个体在约束范围内。 一些参数,本质上都可以使得它随着遗传代数的不同而变化。 河北大学 吴彬 ( wubinbb@163.com )
2.5连续性遗传算法 适应度 复制 交换 突变 线性变换 Ranking适应度分配 比例选择法(轮盘选择) 随机一致选择 竞技选择法 线性交换 中间交换 启发式交换 突变 均匀变异 非均匀变异 河北大学 吴彬 ( wubinbb@163.com )
约束条件的处理-惩罚策略 惩罚技术是遗传算法解约束优化问题中最常用的技术。 本质上它是通过惩罚不可行解将约束问题转化为无约束问题。 河北大学 吴彬 ( wubinbb@163.com )
约束条件的处理-惩罚策略 河北大学 吴彬 ( wubinbb@163.com )
约束条件的处理-惩罚策略 河北大学 吴彬 ( wubinbb@163.com )
约束条件的处理-惩罚策略 惩罚策略的主要问题是如何设计一个惩罚函数 ,从而能有效地引导遗传搜索达到解空间的最好区域。 河北大学 惩罚策略的主要问题是如何设计一个惩罚函数 ,从而能有效地引导遗传搜索达到解空间的最好区域。 河北大学 吴彬 ( wubinbb@163.com )
约束条件的处理-惩罚策略 惩罚项的评估函数 加法形式 对于极大化问题,取 河北大学 吴彬 ( wubinbb@163.com )
约束条件的处理-惩罚策略 惩罚项的评估函数 乘法形式 对于极大化问题,取 河北大学 吴彬 ( wubinbb@163.com )
约束条件的处理-惩罚策略 惩罚项的评估函数 不带参数的惩罚项 带参数的惩罚项 带参数的惩罚策略主要用于在遗传算法运行的不同阶段惩罚项对目标函数的惩罚的大小不同。一般来说,希望初期惩罚小些,后期惩罚大些。 河北大学 吴彬 ( wubinbb@163.com )
约束条件的处理-惩罚策略 不带参数的惩罚项 河北大学 吴彬 ( wubinbb@163.com )
约束条件的处理-惩罚策略 带参数的惩罚项 河北大学 吴彬 ( wubinbb@163.com )
约束条件的处理-惩罚策略 初期惩罚小 后期惩罚大 河北大学 吴彬 ( wubinbb@163.com )
谢谢 参考文献 GEATbx_Intro_Algorithmen_v33a,http://www.geatbx.com/index.html 遗传算法与工程设计,[日]玄光男,程润伟著,科学出版社 演化程序——遗传算法和数据编码的结合, [美]Z.米凯利维茨著,科学出版社 河北大学 吴彬 ( wubinbb@163.com )
线性交换 需要注意:防止染色体超出约束范围 河北大学 吴彬 ( wubinbb@163.com )
线性交换 河北大学 吴彬 ( wubinbb@163.com )
中间交换 需要注意:防止染色体超出约束范围 河北大学 吴彬 ( wubinbb@163.com )
中间交换 河北大学 吴彬 ( wubinbb@163.com )
启发式交换 r为[0,1]间随机数 不比 差,即对最大值问题 特点 使用了目标函数值以确定搜索方向。 只生成一个后代 它可能根本不产生解 不比 差,即对最大值问题 特点 使用了目标函数值以确定搜索方向。 只生成一个后代 它可能根本不产生解 河北大学 吴彬 ( wubinbb@163.com )
启发式交换 此算子有可能产生不可行解,此时产生另一个随机数r以及另一个后代。如果尝试w此后仍失败,算子终止。 河北大学 吴彬 ( wubinbb@163.com )
启发式交换 主要作用 微调 朝一个最有希望的方向搜索 河北大学 吴彬 ( wubinbb@163.com )
均匀变异 河北大学 吴彬 ( wubinbb@163.com )
均匀变异 依次指定个体编码串中的每个基因座为变异点。 对每一个变异点,以变异概率pm从对应基因取值范围内取一随机数来替代原有基因值。 河北大学 吴彬 ( wubinbb@163.com )
非均匀变异 河北大学 吴彬 ( wubinbb@163.com )
非均匀变异 表示产生[0,y]中的一个数。 随着代数t增加, 靠近0的概率增加,也就是,在初期算子可均匀搜索空间(t比较小时),在后期,局部搜索。 河北大学 吴彬 ( wubinbb@163.com )