是,如果你的基因编码设计中包含了袋鼠爱吃什么的信息,这其实不会影响到袋鼠的进化的过程,而那只 攀到珠穆朗玛峰的袋鼠吃什么也完全是随机的,但是它所在的位置却是非常确定的。)
以上是对遗传算法编码过程中经常经历的思维过程,必须把具体问题抽象成数学模型,突出主要矛盾,舍弃次要矛盾。只有这样才能简洁而有效的解决问题。希望初学者仔细琢磨。
既然确定了袋鼠的位置作为个体特征,具体来说位置就 是横坐标。那么接下来,我们就要建立表现型到基因型的映射关系。就是说如何用编码来表现出袋鼠所在的横坐标。由于横坐标是一个实数,所以说透了我们就是要 对这个实数编码。回顾我们上面所介绍的两种编码方式,读者最先想到的应该就是,对于二进制编码方式来说,编码会比较复杂,而对于浮点数编码方式来说,则会 比较简洁。恩,正如你所想的,用浮点数编码,仅仅需要一个浮点数而已。而下面则介绍如何建立二进制编码到一个实数的映射。
明显地,一定长度的二进制编码序列,只能表示一定精度的浮点数。譬如我们要求解精确到六位小数,由于区间长度为2 – (-1) = 3 ,为了保证精度要求,
6
至少把区间[-1,2]分为3 × 10等份。又因为
所以编码的二进制串至少需要22位。 把一个二进制串两个步骤。
(1)将一个二进制串
代表的二进制数转化为10进制数
:
转化位区间
里面对应的实数值通过下面
(2)对应区间内的实数:
例如一个二进制串<1000101110110101000111>表示实数值0.637197。
二进制串<0000000000000000000000>和<1111111111111111111111>则分别表示区间的两个端点值-1和2。
由于往下章节的示例程序几乎都只用到浮点数编码,所以这个“袋鼠跳”问题的解决方案也是采用浮点数编码的。往下的程序示例(包括装载基因的类,突变函数) 都是针对浮点数编码的。(对于二进制编码这里只作简单的介绍,不过这个“袋鼠跳”完全可以用二进制编码来解决的,而且更有效一些。所以读者可以自己尝试用 二进制编码来解决。) 小知识:vector(容器)的使用。
在具体写代码的过程中,读者将会频繁用到vector这种数据结构,所以大家必须先对它有所了解。
std::vector是STL(standard template library)库里面的现成的模板类。它用起来就像动态数组。利用vector(容器)我们可以方便而且高效的对容器里面的元素进行操作。示例如下:
1. //添加头文件,并使用std名空间。 2.
3. #include
5. using namespace std; 6.
7. //定义一个vector,<>内的是这个vector所装载的类型。 8.
9. vector
11. //为vector后面添加一个整型元素0。 12.
13. MyVector.push_back(0); 14.
15. //把vector的第一个元素的值赋给变量a。值得注意的是如果vector的长度只有1,
而你 16.
17. //去访问它的下一个元素的话,编译和运行都不会报错,它会返回一个随机值给你,
所以使 18.
19. //用的时候一定要注意这个潜伏的BUG。 20.
21. int a = MyVector[0]; 22.
23. //把vector里面的元素全部清空。 24.
25. MyVector.clear(); 26.
27. //返回vector里面的元素的个数。 28.
29. MyVector.size()
呵呵,如果你没用过这个模板类,请完全不必介意,因为现在为止,你已经学会了在本书里面将用到的所有功能。
另 外,我也顺便提一提,为什么我用vector而不用其它数据结构比如数组,来承载一条基因,还有后面我们将会学到的神经网络中的权值向量。诚然,用数组作 为基因或者权值向量的载体,速度会快一些。但是我用vector主要出于下面几个考虑。首先,vector的使用比较方便,方便得到其大小,也方便添加和 访问元素,还有排序。其次,使用vector也便于代码的维护与及重用(在这本书的学习过程中,学习者将会逐步建立起遗传算法和人工神经网络的引擎,通过 对代码少量的修改就能用于解决新的问题。)。另外,我还希望在研究更前缘的应用方向――通过遗传算法动态改变神经网络的拓扑结构的时候,大家仍然可以通过 少量的修改后继续利用这些代码。(因为动态地改变神经网络的拓扑结构非常需要不限定大小的容器。)
我们定义一个类作为袋鼠基因的载体。(细心的人会提 出这样的疑问:为什么我用浮点数的容器来储藏袋鼠的基因呢?袋鼠的基因不是只用一个浮点数来表示就行吗?恩,没错,事实上对于这个实例,我们只需要用上一 个浮点数就行了。我们这里用上容器是为了方便以后利用这些代码处理那些编码需要一串浮点数的问题。)
1. 2. 3. 4. 5. 6. 7.
class CGenome {
public:
//定义装载基因的容器(事实上从英文解释来看,Weights是权值的意思,这用来表示 8.
9. //基因的确有点名不符实,呵呵。这主要是因为这些代码来自于GA-ANN引擎,所
以在 10.
11. //它里面基因实质就是神经网络的权值,所以习惯性的把它引入过来就只好这样了。) 12.
13. vector
14.
15. // dFitness用于存储对该基因的适应性评估。 16.
17. double dFitness; 18.
19. //类的无参数初始化参数。 20.
21. CGenome():dFitness(0){} 22.
23. //类的带参数初始化参数。 24.
25. CGenome(vector
好了,目前为止我们把袋鼠的染色体给研究透了,让我们继续跟进袋鼠的进化旅程。
物竞天择--适应性评分与及选择函数。
1.物竞――适应度函数(fitness function)
自然界生物竞争过程往往包含两个方面:生物相互间的搏斗与及生物与客观环境的搏斗过程。但在我们这个实例里面,你可以想象到,袋鼠相互之间是非常友好的,它们并不需要互相搏斗以争取生存的权利。它们的生死存亡更多是取决于你的判断。因为你要衡量哪只袋鼠该杀,哪只袋鼠不该杀,所以你必须制定一个衡量的标准。而对于这个问题,这个衡量的标准比较容易制定:袋鼠所在的海拔高度。(因为你单纯地希望袋鼠爬得越高越好。)所以我们直接用袋鼠的海拔高度作为它们的适应性评分。即适应度函数直接返回函数值就行了。 2.天择――选择函数(selection)
自然界中,越适应的个体就越有可能繁殖后代。但是也不能说适应度越高的就肯定后代越多,只能是从概率上来说更多。(毕竟有些所处海拔高度较低的袋鼠很幸运,逃过了你的眼睛。)那么我们怎么来建立这种概率关系呢?下面我们介绍一种常用的选择方法――轮盘赌(Roulette Wheel Selection)选择法。假设种群数目,某个个体其适应度为
,则其被选中的概率为:
比如我们有5条染色体,他们所对应的适应度评分分别为:5,7,10,13,15。
所以累计总适应度为:
所以各个个体被选中的概率分别为:
呵呵,有人会问为什么我们把它叫成轮盘赌选择法啊?其实你只要看看图2-2的轮盘就会明白了。这个轮盘是按照各个个体的适应度比例进行分块的。你可以想象一下,我们转动轮盘,轮盘停下来的时候,指针会随机地指向某一个个体所代表的区域,那么非常幸运地,这个个体被选中了。(很明显,适应度评分越高的个体被选中的概率越大。)
图2-2
那么接下来我们看看如何用代码去实现轮盘赌。
1. //轮盘赌函数 2.
遗传算法入门到掌握
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)