搜公众号
推荐 原创 视频 Java开发 开发工具 Python开发 Kotlin开发 Ruby开发 .NET开发 服务器运维 开放平台 架构师 大数据 云计算 人工智能 开发语言 其它开发 iOS开发 前端开发 JavaScript开发 Android开发 PHP开发 数据库
Lambda在线 > 旺财与guitar > bitset使用小记

bitset使用小记

旺财与guitar 2019-02-15
举报

       早就想写点编程相关的东西,但又一直没想到写什么,刚好最近在看《C++ primer》,发现里面有很多东西都是我曾经没有用到过的。我是从2010年开始学C++的,全凭爱好,野路子出身。当时看的是哪本C++教材,现在已经不记得,总之看完以后就开始编程,用到的知识点基本上也都是那个教材里面的。直到现在,C++17都出来了,我发现我平时写的代码基本还是那些基础知识的堆叠,很多好的特性都没有用上。有的时候,会不经意地发现一些有用的东西,用一下,然后再对比自己之前写的代码,瞬间感觉以前的代码low爆了。所以,最近想重新把C++基础再巩固巩固,在原来的基础上升华一下。有句话说得好,“你知道的越多,你会发现你不知道的也就更多”。《C++Primer》给我的感受,和网传的一样,并不适合初学者,因为它太全面了,以至于你要花费相当长的时间来完全掌握它。

      2015年暑假,我刚考完研,在家研究一个益智小游戏的破解算法(关于这个小游戏其实有个很长的故事,以后有机会讲讲),当时找了很多算法感觉都不太合适,最后发现用遗传算法来做可能可以实现,然后就抱着试一试的态度做了一下,最终也证明了遗传算法确实是行之有效的方法。当时考虑到要把这个算法做的通用一点,方便以后用,于是把它封装成了一个类,然后把遗传算法的各种变种都加进去了,只需要设一下参数就能够随意改变算法所采用的策略(比如染色体的交叉重组规则、基因突变规则、精英的挑选方式等等),最后写了大概有1000行左右。

       当时为了表示一个染色体,我用到了MFC封装的CArray类;代码中有这样一行内容:

typedef CArray<int> Chromosome;

也就是用一个CArray<int>类型来表示一个染色体,其中每一个int类型元素用来表示一个基因。这样的后果是什么呢?如果染色体的长度是10,int类型是32位,那么占用的空间至少是320bit,显得很浪费;另外还有一个问题,就是在做交叉重组操作时,要进行的赋值运算次数比较多。然鹅,当时的我并不考虑这些效率上的问题,我的目的很纯粹,就是实现遗传算法,不惜一切代价。其实现在想一下,当时如果用链表的话,这样做交叉重组就简单很多了。不过已经无所谓了,因为这次要说的这个bitset比链表更快,更强那就是。

       我曾考虑过这样一个问题,就是能不能用一个int类型的整数来表示一个染色体呢?这样的话,这个整数转化成一个2进制数之后就是一串“0101”的二进制位,这正好是一个天然的染色体编码。如果用int类型表示染色体,那么交叉重组操作就可以用移位操作"<<"和">>"来实现,基因突变操作直接对某一位取反就行了。这样的话无论是对效率的提升还是对代码量的简化都是一个大的进步。但是这里有一个问题,就是int能表示的2进制位数是有限的,如果int是32位,那就不能表示长度为33的染色体,要表示更多的二进制位,就要增加int变量的个数,那样问题又复杂化了。所以这个想法也就一直停留在简单的一个想法上,但却让我耿耿于怀。

       最近我在《C++ Primer》里面看到bitset这个类,这个类可以用来定义一个任意长度的bit数组,你可以直接对它的任意一个二进制位操作,甚至可以像int变量那样对它使用移位操作,我看到这个类型的时候很兴奋,因为用它来解决我一直在思考的这个问题简直可以说是完美。然后,我迫不及待地用bitset把遗传算法重写了一遍,当然不包括各种变种,最终,算上main函数,整个代码量没超过200行。相比以前写的算法,执行速度变快是毋庸置疑的,另外代码的通用性更强了,因为bitset是C++标准库里面的东西,而CArray是MFC封装的东西。

       这里主要介绍一下交叉重组操作和变异操作的实现代码。

1.首先看一下交叉重组:

bitset<20> A,B;

bitset<20>temp=A>>pos<<pos|B<<(SIZE-pos)>>(SIZE-pos);

B=B>>pos<<pos|A<<(SIZE-pos)>>(SIZE-pos);

A=temp;

这段代码的作用是对长度为20的A、B两个染色体,在pos指定的位置完成交叉操作。乍一看这段代码,可能会头晕,没关系,先慢慢分析一下。

先看“A>>pos<<pos”,其中A是一个有20个二进制位的bitset,你可以把它想象成一个20位的int。pos代表交叉的位置(position),从低位到高位的顺序,最低位的pos=0。先A>>pos,然后再A<<pos,就会把A中位于pos右边的所有二进制位变成0;同理,“B<<(SIZE-pos)>>(SIZE-pos)”就会使B中在pos的左边(包含pos)所有二进制位都变成0,然后再用“|”操作符将他们连接起来,这样就得到了A和B交叉重组后的其中一个后代。将这个结果保存到一个临时变量temp中。

同样的道理,“B=B>>pos<<pos|A<<(SIZE-pos)>>(SIZE-pos);”这一行代码就会将A中位于pos左边(包含pos)的二进制位,与B中在pos右边的二进制位连接起来,得到另一个交叉重组的后代,然后用结果去覆盖B,最后,用临时变量temp去覆盖A,A和B就完成了在pos位置交叉重组的操作。

2.再看一下基因突变操作的代码,真的非常简单:

bitset<20> A;

A.flip(pos);

只需要用flip函数对pos位置的二进制位取反即可。

       这两点是用bitset实现遗传算法的精髓,剩下的就是完成变比技术、后代的选择操作、以及整个迭代流程等,因为与bitset本身的应用无关,所以就不写了。有兴趣的朋友可以到我的Github下载源码:

https://github.com/h258384667/Algorithms/blob/master/GA.cpp

       最后说一下bitset的缺点,虽然用bitset实现了遗传算法,但是bitset这个类必须在定义变量的时候就指定二进制位的位数,并且不能够用变量去指定,也就是说在代码编译之前就必须向编译器指定二进制位的位数,在程序运行中用变量去指定染色体长度是不允许的,所以存在一定的局限性。举个例子,上面代码定义染色体的时候是

bitset<20> A;

如果我们改写为:

int length=20;

bitset<length> A;

那么在编译的时候就会报错。关于这个问题,可以用boost库中的dynamic_bitset来解决,这是一个可变长度的bitset,是对bitset的扩展。


版权声明:本站内容全部来自于腾讯微信公众号,属第三方自助推荐收录。《bitset使用小记》的版权归原作者「旺财与guitar」所有,文章言论观点不代表Lambda在线的观点, Lambda在线不承担任何法律责任。如需删除可联系QQ:516101458

文章来源: 阅读原文

相关阅读

关注旺财与guitar微信公众号

旺财与guitar微信公众号:h258384667

旺财与guitar

手机扫描上方二维码即可关注旺财与guitar微信公众号

旺财与guitar最新文章

精品公众号随机推荐

举报