有些时候

暂无签名

  • 博客访问: 6076
  • 博文数量: 10
  • 用 户 组: 普通用户
  • 注册时间: 2017-05-11 14:31
  • 认证徽章:
个人简介

一句话介绍

ITPUB论坛APP

ITPUB论坛APP



APP发帖 享双倍积分

文章分类

全部博文(10)

文章存档

2017年(10)

我的朋友
微信关注

IT168企业级官微



微信号:IT168qiye



系统架构师大会



微信号:SACC2013

订阅
热词专题
友情链接

分类: 大数据

前言

本文尝试对遗传算法中不同适值函数的标定(Scaling)方法进行下总结,并针对常用的线性标定和动态线性标定进行了Python实现,以装饰器的形式添加到遗传算法框架GAFT中,这样在使用GAFT运行遗传算法迭代的时候可以更加Pythonic的给自定义的适值函数进行标定。最后针对能够防止早熟情况的大变异算法进行了相应的实现。

目前(动态)线性标定装饰器以及大变异算子均已添加到GAFT中,gaft项目链接:

适值函数的标定

选择压力

The tendency to select the best member of the current generation is known as selective pressure.

选择压力也就是种群中最好个体与最坏个体被选中概率的差值,这个差距越大,选中好个体的趋势就越大,则成为选择压力大。

适值函数的标定

一般情况下,直接拿目标函数作为适值函数十分的方便,但是很多情况下却不能这么做,例如对于求最小值问题,我们必须将目标函数取反才能作为适值函数(这是最简单的情况)。

当我们遗传算法中不同个体适值函数的值相对差别很小的时候,我们根据适应度值的大小进行个体选择的选择压力(Selective pressure)就会变小,选优的能力弱化,这个时候我们需要对原始的适值函数进行标定(Scaling)是的他们相对差别增大,进而增大选择压力,增强算法的选优能力。

例如:

 WX20170924-205842@2x

局部搜索、广域搜索与选择压力的关系

在遗传算法中,局部搜索同广域搜索其实相互矛盾的,注重局部搜索则会陷入局部最优,但是注重广域搜索会导致算法精确开发能力不强。因此需要综合两者考虑,我们可以在搜索刚刚开始的时候使用较小的选择压力来广域搜索,随着迭代的进行可以动态的增大选择压力来使算法偏向于局部搜索。

几种不同的适值函数标定方法

对目标函数的标定方法一般有:线性标定、动态线性标定、幂律标定、对数标定等

线性标定

线性标定的形式:

WX20170924-210412@2x

其中f为标定后的适值函数,ff为原始的目标函数。

求最大值

对于求目标函数的最大值的时候, 即 arg max f(x)

我们取a=1,b=?fmin+ξ, 其中ξ是一个较小的数,目的是使得种群中最差个体也有被选中的机会,不然自身减掉f?fmin=0ξ的存在可以增加种群的多样性。

最终的适值函数表达式:

WX20170924-210512@2x

求最小值

当我们需要求目标函数最小值的时候,arg min f(x),我们需要对目标函数进行取反操作, 即 厦门堆高车
a=?1,b=fmax?f(x)+ξ

最终的适值函数表达式:

WX20170924-210641@2x

GAFT中添加对于目标函数的标定

由于适值函数标定并不针对某个目标函数,我便想通过装饰器的方式来方便给任何自定义的fitness函数进行标定。对于基本的线性标定,我在GAEngine中添加了个带参数的装饰器: