《Java遗传算法编程》—— 1.7 搜索空间-阿里云开发者社区

开发者社区> 异步社区> 正文

《Java遗传算法编程》—— 1.7 搜索空间

简介: 在计算机科学中,如果处理优化问题时有许多候选解需要搜索,我们就称解的集合是“搜索空间”。搜索空间内每个特定的点就是给定问题的一个候选解。在这个搜索空间中有距离的概念,相比位置远离的解,位置彼此靠近的解更可能表现出相似的特征。
+关注继续查看

本节书摘来异步社区《Java遗传算法编程》一书中的第1章,第1.7节,作者: 【英】Lee Jacobson(雅各布森) , 【美】Burak Kanber(坎贝尔),更多章节内容可以访问云栖社区“异步社区”公众号查看。

1.7 搜索空间

在计算机科学中,如果处理优化问题时有许多候选解需要搜索,我们就称解的集合是“搜索空间”。搜索空间内每个特定的点就是给定问题的一个候选解。在这个搜索空间中有距离的概念,相比位置远离的解,位置彼此靠近的解更可能表现出相似的特征。为了理解这些距离在搜索空间中如何组织,请考虑下面使用二进制遗传表示的例子:

“101”与“111”只差1。这是因为只要有1个变化(0翻转到1),就能从“101”变成“111”。这意味着这些解在搜索空间中的空间距离仅为1。

另一方面,“000”与“111”是有3处不同。这就是说距离为3,在搜索空间“000”与“111”相距为3。

因为变化较少的一些解彼此较近,所以搜索空间中解的距离可以用来提供一种相似性,说明另一个解的特征相似。许多搜索算法经常将这种理解作为一种策略,以改善搜索结果。

1.7.1 适应度景观

如果搜索空间内发现的候选解标上其个体的适应度水平,我们就可以将搜索空间看成“适应度景观”。图1-1提供了一个例子,说明二维适应度景观看起来如何。

cd983b30ea20eeccfe2492280d8747fb8e277b43

适应度景观的横轴是我们要优化的值,竖轴是对应的适应度值。需要指出,这通常是对实际情况的过度简化。大多数真实世界的应用程序都有多个值需要优化,会生成多维适应度景观。

在上面的例子中,可以看到搜索空间中的每个候选解的适应度值。这很容易看到最适应解的位置,但是,要在现实中做到这一点,搜索空间中每个候选解都需要求出适应度函数的值。对于复杂的问题,搜索空间呈指数式增长,计算每个解的适应度值是不合理的。在这种情况下,搜索算法负责找到最佳解的可能位置,同时又受到限制,仅看到搜索空间的一小部分。图1-2所示是搜索算法通常会看到什么的一个例子。

请考虑一种算法,它要搜索十亿个(1 000 000 000)可能解构成的搜索空间。即使每个解只需要1秒来对适应度求值和赋值,它仍然需要超过30年,才能搜索每个可能的解!如果我们不知道搜索空间中每个解的适应度值,我们就无法确切地知道最佳解在哪里。在这种情况下,唯一合理的方法是采用一种搜索算法,它能在可用的时间内发现足够好的解。在这些条件下,一般来说,遗传算法和进化算法能够非常有效地发现可行的、接近最佳的解。

c5e843cc8dc914fab9041268bd185538c342a7f4

在搜索空间进行搜索时,遗传算法使用种群的方法。作为其搜索策略的一部分,遗传算法假设两个评分不错的解可以组合,形成一个更适应的后代。这个过程可以在适应度景观(图1-3)中看出来。

ce4769d222a2958d9c32d192fe7b14734f3e9aaf

遗传算法中的变异算子让我们搜索特定候选解的近邻。变异应用于一个基因时,其值随机地改变。这可以表示成在搜索空间(见图1-4)中跨出一步。

在这两个交叉和变异的例子中,得到的解都有可能比原来亲代的适应度更差(见图1-5)。

a9a2ea48750231718628cf1d9df803635909b6ae

在这种情况下,如果解的表现足够差,它最终会在选择过程中从基因库删除。个体候选解小的负面变化是可以接受的,只要种群平均趋势指向更适应的解。

1.7.2 局部最优

实现优化算法时,必须考虑一个障碍,即该算法能否很好地逃离搜索空间的局部最优位置。为了更好地表现什么是局部最优,请参考图1-6。

在这里,我们可以看到适应度景观中的两座小山,它们峰值略微不同。正如前面提到的,优化算法不能够看到整个适应度景观,相反,它能做得最好的是找一些解,它认为这些解很可能处于搜索空间的最佳位置。正是因为这种特点,优化算法通常能在不知不觉中专注于查找搜索空间的次优部分。

80c8d9a0523cbd259078e0ca9fe4834ab96c6945

如果实现使用一个简单的登山算法来解决任何足够复杂的问题,这个问题很快就会引起注意。一个简单登山算法没有任何内建的方法来处理局部最优,因此往往会在搜索空间的局部最优区域中终止其搜索。一个简单的随机登山算法相当于没有种群和交叉的遗传算法。该算法相当容易理解,它从搜索空间中的随机点开始,然后评估相邻的解,尝试找到更好的解。如果登山算法在相邻位置找到了更好的解,它会移动到新位置,并再次重新启动搜索过程。通过在搜索空间中找到的任何一座山向上爬,这个过程会逐渐找到更好的解,它因而得名“登山算法”。如果登山算法再也找不到更好的解,它就假设是在山顶,并停止搜索。

图1-7展示了登山算法的典型搜索过程。

6385a0ca853f0b36ad94573b4bd1ace4c7a5926e

图1-7表明,简单登山算法在搜索空间的局部最优区域开始搜索时,如何很容易返回一个局部最优解。

虽然目前还无法实现在不首先求值整个搜索空间的情况下,确保避免局部最优,但该算法有许多变种,可以帮助避免局部最优。其中一个最基本而有效的方法,称为“随机重启登山”,就是从随机起始位置多次运行登山算法,然后返回它在不同运行中找到的最佳解。这种优化方法比较容易实现,而且有效性令人惊讶。其他方法诸如模拟退火方法[参见Kirkpatrick,Gelatt,and Vecchi (1983)]和禁忌搜索[参见Glover(1989)和Glover(1990)],它们对登山算法进行了微小改变,都有助于减少局部最优。

在避免局部最优和取得接近最优的解方面,遗传算法的有效性令人惊讶。做到这一点的一种办法,是让种群能够从搜索空间的大片区域取样,定位最佳的区域,继续搜索。图1-8展示了种群在初始化时可能如何分布。

5b71ed6d9d7c74048c97545aa6c2d0b59ac5575f

经过几代后,种群就开始一致走向前几代发现的最优解。这是因为不太适合的解会在选择过程中移除,让位给交叉和变异(见图1-9)产生的新解。

变异算子也起到了逃离局部最优的作用。变异允许一个解从当前位置跳到搜索空间的另一个位置。这个过程往往会导致在搜索空间的较优区域中发现更适合的解。

49e1f7ffac2c51621617055d7d7265c81eaf4dd0

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
【双11背后的技术】基于深度强化学习与自适应在线学习的搜索和推荐算法研究
作者:灵培、霹雳、哲予 1. 搜索算法研究与实践 1.1 背景 淘宝的搜索引擎涉及对上亿商品的毫秒级处理响应,而淘宝的用户不仅数量巨大,其行为特点以及对商品的偏好也具有丰富性和多样性。因此,要让搜索引擎对不同特点的用户作出针对性的排序,并以此带动搜索引导的成交提升,是一个极具挑战性的问题。传统
10260 0
DL之RNN:人工智能为你写代码——基于TF利用RNN算法实现生成编程语言代码(C++语言)、训练&测试过程全记录
DL之RNN:人工智能为你写代码——基于TF利用RNN算法实现生成编程语言代码(C++语言)、训练&测试过程全记录
33 0
DL之RNN:人工智能为你写代码——基于TF利用RNN算法实现生成编程语言代码(C++语言)、训练&测试过程全记录(二)
DL之RNN:人工智能为你写代码——基于TF利用RNN算法实现生成编程语言代码(C++语言)、训练&测试过程全记录
29 0
冰与火之歌:「时间」与「空间」复杂度 | 算法必看系列三十六
对于一个算法,其时间复杂度和空间复杂度往往是相互影响的。当追求一个较好的时间复杂度时,可能会使空间复杂度的性能变差,即可能导致占用较多的存储空间; 反之,求一个较好的空间复杂度时,可能会使时间复杂度的性能变差,即可能导致占用较长的运行时间。另外,算法的所有性能之间都存在着或多或少的相互影响。因此,当设计一个算法(特别是大型算法)时,要综合考虑算法的各项性能,算法的使用频率,算法处理的数据量的大小,算法描述语言的特性,算法运行的机器系统环境等各方面因素,才能够设计出比较好的算法。
2254 0
[译] Bob,函数式编程是什么鬼?
本文讲的是[译] Bob,函数式编程是什么鬼?,你懂的。很多人都讨论它。你 Google 一下然后看了看前五篇文章,令人沮丧的是,你发现大部分文章只给出一个含糊不清的 Wikipedia 定义,像是:
935 0
AI+无线通信总结——初赛算法实现(Top37)
AI+无线通信总结——初赛算法实现(Top37)
82 0
人工智能: 自动寻路算法实现(一、广度优先搜索)
前言 随着人工智能技术的日益发达,我们的生活中也出现了越来越多的智能产品。我们今天要关注的是智能家居中的一员:扫地机器人。
1732 0
人工智能: 自动寻路算法实现(二、深度优先搜索)
前言 本篇文章是机器人自动寻路算法实现的第二章。我们要讨论的是一个在一个M×N的格子的房间中,有若干格子里有灰尘,有若干格子里有障碍物,而我们的扫地机器人则是要在不经过障碍物格子的前提下清理掉房间内的灰尘。
1501 0
+关注
异步社区
异步社区(www.epubit.com)是人民邮电出版社旗下IT专业图书旗舰社区,也是国内领先的IT专业图书社区,致力于优质学习内容的出版和分享,实现了纸书电子书的同步上架,于2015年8月上线运营。公众号【异步图书】,每日赠送异步新书。
12049
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载