遗传算法五大基本要素——参数编码群体设定

丰富的线上&线下活动,深入探索云世界

做任务,得社区积分和周边

最真实的开发者用云体验

让每位学生受益于普惠算力

让创作激发创新

资深技术专家手把手带教

遇见技术追梦人

技术交流,直击现场

海量开发者使用工具、手册,免费下载

极速、全面、稳定、安全的开源镜像

开发手册、白皮书、案例集等实战精华

为开发者定制的Chrome浏览器插件

遗传算法主要借用生物进化中的“适者生存”的规律。

遗传算法包括两个数据转换操作,一个是从表现型到基因型的转换,将搜索空间中的参数或解转化成遗传空间中的染色体或者个体,这个过程叫做编码(coding)。另一个就是从基因型到变现型的转换,即将个体转换成搜索空间中的参数,这个过程叫做解码(decode)。

遗传算法中包含了五个基本要素:参数编码,初始群体的设定,适应度函数的设计;遗传操作设计和控制参数设定。

由于遗传算法不能直接处理问题空间的参数,因此,必须通过编码将要求解的问题表示成遗传空间的染色体或者个体。它们由基因按一定的结构组成。由于遗传算法的健壮性,对编码的要求并不苛刻。对一个具体的应用问题如何编码是应用遗传算法的首要问题,也是遗传算法应用的难点。事实上,还不存在一种通用的编码方法,特殊的问题往往采用特殊的方法。

将问题空间的参数编码为一维排列的染色体的方法,称为一维染色体编码方法。一维染色体编码中最常用的符号集是二值符号集$\{0,1\}$,即采用二进制编码(BinaryEncoding)。

(1)二进制编码二进制编码是用若干二进制数表示一个个体,将原问题的解空间映射到位串空间$B=\{0,1\}$上,然后在位串空间上进来遗传操作。<>/font

优点:二进制编码类似于生物染色体的组成,从而使算法易于用生物遗传理论来解释,并使得遗传操作若交叉、变异等很容易实现。另外,采用二进制编码时,算法处理的模式数最多。

缺点:①相邻整数的二进制编码可能具有较大的Hamming举例。例如,15和16的二进制表示为01111和10000,因此,算法要从15改进到16则必须改变所有的位。这种缺陷造成了Hamming悬崖(HammingCliffs),将降低遗传算子的搜索效率。②二进制编码时,一般要先给出求解的精度。但求解的精度确定后,就很难在算法执行的过程中进行调整,这就是算法缺乏微调(fine-tuning)的功能。若在算法一开始就选择较高的精度,那么串长就很大,这样也会降低算法的效率。③在求解高维优化问题的时候,二进制编码串将非常长,从而使得算法的搜索效率很低。

(2)Gray编码$Gray$编码是将二进制编码通过一个变换进行转换得到的编码。设二进制串$<β_1β_2...β_n>$对应$Gray$串$<γ_1γ_2...γ_n>$,则从二进制编码到$Gray$编码的变换为:

$$γ_k=\begin{cases}β_1,\quadk=1\\β_{k-1}\bigoplusβ_k,\quadk>1\end{cases}\tag{1}$$

上式子(1)中,$\bigoplus$表示摸2的加法,也就是异或运算,不同为1,相同为0。

举个例子说明一下:假设有一个二进制编码串$(10110)_2$,那么我们将它转化为Gray编码后为$(11101)_{Gray}$。

从一个Gray串到二进制串的变换为:

$$β_k=\displaystyle\sum^{k}_{i=1}{γ_i(mod2)}=\begin{cases}γ_1,\quadk=1\\β_{k-1}\bigoplusγ_k,\quadk>1\end{cases}\tag{2}$$

举个例子说明一下:假设有一个Gray编码串$(01001)_{Gray}$,将其转化为二进制编码串后为$(01110)_2$。

Gray编码的优点是克服了二进制编码的Hamming悬崖的缺点。

为克服二进制编码的缺点,对问题的变量是实向量的情形,可以直接采用实数编码。

实数编码是用若干实数表示一个个体,然后在实数空间上进行遗传操作。

对于多参数优化问题的遗传算法,常采用多参数级联编码。其基本思想是把每个参数先进行二进制编码得到子串,再把这些子串连成一个完整的染色体。多参数级联编码中的每个子串对应各自的编码参数,所以,可以有不同的串长度和参数的取值范围。

由于遗传算法是对群体进行操作的,所以,必须为遗传操作准备一个由若干初始解组成的初始群体。群体设定主要包括两个方面:初始种群的产生和种群规模的确定。

遗传算法中初始群体中的个体可以是随机产生的,但最好采用如下策略设定:

①根据问题固有知识,设法把握最优解所占空间在整个问题空间中的分布范围,然后,在此分布范围内设定初始群体。

②先随机产生一定数目的个体,然后从中挑选最好的个体加人初始群体中。这种过程不断迭代,直到初始群体中个体数目达到了预先确定的规模。

群体中个体的数量称为种群规模。种群规模影响遗传优化的结果和效率。当种群规模太小时,遗传算法的优化性能一般不会太好,容易陷入局部最优解。而当种群规模太大时,则计算复杂。

种群规模的确定受遗传操作中选择操作的影响很大。模式定理表明:若种群规模为$M$,则遗传操作可从这$M$个个体中生成和检测$M^3$个模式,并在此基础上能够不断形成和优化积木块,直到找到最优解。

显然,==种群规模越大==,遗传操作所处理的模式就越多,产生有意义的积木块并逐步进化为最优解的机会就越高。==种群规模太小==,会使遗传算法的搜索空间范围有限,因而搜索有可能停止在未成熟阶段,出现未成熟收敛现象,使算法陷入局部最优解。因此,必须保持种群的多样性,即种群规模不能太小。

THE END
1.最常用的五大算法总结!附算法题思路,看完茅塞顿开!转自:最常用的五大算法 https://blog.csdn.net/watson2016/article/details/77857824 一、贪心算法 贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的仅是在某种意义上的https://mp.weixin.qq.com/s?__biz=MjM5ODc2Mzk2MA==&mid=2451788978&idx=3&sn=1ec2d358dc201c95f7c85e8438c613b8&chksm=b11238658665b173f858315941fe08939c0e5ecaa29bf86d6f8bb0d5f1dd2e10c5c064646c38&scene=27
2.五大常用算法五大常用算法之一:分治算法 基本概念: 把一个复杂的问题分成两个或更多的相同的或相似的子问题。再把子问题分成更小的子问题。直到最后子问题可以简单的解决。 分成的子问题与原问题形式相同,并且互相独立,递归的解决这些子问题。然后将子问题的解合并得到原问题的较小模式。这就为使用递归技术提供了方便。分治与递归https://www.jianshu.com/p/bc02cd2fe06f
3.五大常用算法之一:分治算法五大常用算法之一:分治算法 分治算法: 一、基本概念 分治法是计算机科学中非常重要的算法。字面上的解释是“分而治之”,即将一个复杂的问题分为两个或两个以上相同或相似的子问题,然后将子问题分为更小的子问题。。。直到最后一个子问题可以简单地直接解决,原始问题的解决方案就是子问题的解决方案的结合。这一https://www.tulingxueyuan.cn/tlzx/jsp/3793.html
4.自动驾驶路径规划五大常用算法汽车技术自动驾驶路径规划五大常用算法 无人驾驶系统的核心可分为四个部分:感知、定位、规划和控制。规划承接环境感知,并下启车辆控制,是实现无人驾驶的关键技术之一。规划是指无人车为了到达某一目的地而做出决策和计划的过程,其规划出来的轨迹是带速度信息的路径,对于无人驾驶车辆而言,这个https://www.auto-testing.net/news/show-116633.html
5.笔记:五大常用算法51CTO博客笔记:五大常用算法 贪婪算法,动态规划算法,分治算法,回溯算法,分支限界算法 贪心算法 单源最短路 Dijkstra算法 最小生成树 Kruskal算法 Prim算法 动态规划算法 任意两点间的最短路 Floyd算法 01背包——m[ i ][ j ] 表示 在面对第 i 件物品,且背包容量为 j 时所能获得的最大价值,不断的更新它,因为得出的https://blog.51cto.com/u_11347864/6686752
6.衡量算法好坏的五大标准是什么?Worktile社区衡量算法好坏的五大标准: 1、时间复杂度; 2、空间复杂度; 3、正确性; 4、可读性; 5、健壮性。时间复杂度是指,执行算法所需要的计算工作量,这是一个代表算法输入值的字符串的长度的函数。 1、时间复杂度 在计算机科学中,时间复杂性,又称时间复杂度,算法的时间复杂度是一个函数,它定性描述该算法的运行时间。https://worktile.com/kb/p/34908
7.五大常用算法之四:回溯法五大常用算法之四:回溯法 标签: 算法 收藏 1、概念 回溯算法实际上一个类似枚举的搜索尝试过程,主要是在搜索尝试过程中寻找问题的解,当发现已不满足求解条件时,就“回溯”返回,尝试别的路径。回溯法是一种选优搜索法,按选优条件向前搜索,以达到目标。但当探索到某一步时,发现原先选择并不优或达不到目标,就https://www.imooc.com/article/27990
8.程序设计五大算法在程序设计中,有许多经典的算法被广泛应用于各种领域。下面将介绍程序设计中的五大算法,包括贪心算法、分治算法、动态规划算法、回溯算法和图算法。 1.贪心算法 贪心算法是一种简单而高效的算法,它通过每一步都选择当前最优解来达到全局最优解。贪心算法通常适用于那些具有最优子结构的问题,即问题的最优解可以通过https://wenku.baidu.com/view/18ed554dedfdc8d376eeaeaad1f34693dbef1011.html
9.五大常用算法之贪心算法,算法数据结构五大常用算法贪心算法基础知识点 贪心算法是一种常用的算法设计技术,通过一系列的选择来得到问题的解,所做的每个选择都是当前状态下局部最好的选择,即贪心选择。下面是贪心算法的基本概念、算法框架和应用场景。 贪心算法的基本概念 贪心算法是通过一系列的选择来得到问题的解,每个选择都是当前状态下局部最好的选择。贪心算法的基https://download.csdn.net/download/qq_40464803/85089599
10.五大常用算法:分治动态规划贪心回溯和分支界定五大常用算法:分治、动态规划、贪心、回溯和分支界定这五种算法引出了很多问题。慢慢的更新链接! 动态规划的五个典型算法:动态规划 1.最大连续子序列之和 2.数塔问题(二叉树从上往下遍历最大和问题) 3.01背包问题 4.最长递增子序列(LIS) 5.最长公共子序列(LCS) //最长公共子序列(LCS)两个字符串的最长连续公https://www.cnblogs.com/ranjiewen/p/6083952.html
11.金融科技发展带来五大新挑战!易纲:积极应对算法歧视等新型垄断问题金融科技发展带来五大新挑战!易纲:积极应对算法歧视等新型垄断问题 摘要 炒股第一步,先开个股票账户 中国人民银行行长易纲日前在国际清算银行(BIS)监管大型科技公司国际会议上表示,在技术进步的推动下,中国金融科技蓬勃发展。 与此同时,“金融科技的不断发展也给中国监管当局带来了新挑战。”易纲表示,一是无牌或超https://finance.eastmoney.com/a/202110092132432726.html
12.《集异璧之大成》阅读笔记及杂谈(附录一):人机博弈蒙特卡洛算法也常用于机器学习,特别是强化学习的算法中。一般情况下,针对得到的样本数据集创建相对模糊的模型,通过蒙特卡洛方法对于模型中的参数进行选取,使之于原始数据的误差尽可能的小。从而达到创建模型拟合样本的目的。 超复杂的搜索树 1·五大常用搜索算法https://www.gameres.com/846786.html
13.学好算法,你就可以轻轻松松解数独啦腾讯云开发者社区本文我们就来介绍五大经典算法的下一个 — 回溯算法。 2. 回溯算法 数学课堂上,老师说:“同学们,6 可以拆分成几加几呀?”,台下的同学们鸦雀无声,顿时有些冷场,老师一下子有点生气“掰着指头算不会吗?” 这个“掰着指头算”就是一个数字一个数字的尝试,通过穷举获得问题的结果集,对于复杂的有限空间的问题https://cloud.tencent.com/developer/article/2031645