在遗传算法中编码为位串有什么帮助?

问题描述 投票:2回答:1

假设我们必须解决一个全局优化问题,其中必须找到5个变量的值,所有这些变量都是整数。假设我们得到了两条亲本染色体,

父母1:6,10,3,5,12

父母2:12、10、3、8、11

如果我们在前两个元素之后进行交叉,则会得到以下结果

儿童1:6,10,3,8,11

儿童2:12,10,3,5,12

在这里我们可以清楚地看到孩子与父母有关。

但是当我们将其编码为位串时,则每个染色体都将被编码为单个位串,我们可以随机选择任何交叉点。我看不出这比完全随机选择任何试用解决方案有什么好处。

我对突变也有类似的问题。我们随机翻转一下。如果翻转的位的值很小,那么变化将很小。但是,如果它的地价很大,那么变化将很大。与完全随机地改变染色体相比,有什么好处?

encoding genetic-algorithm bitstring
1个回答
0
投票

二进制编码仍然很常见,主要是因为有关GA的第一个著作使用了该编码。

此外,它通常是节省空间的:用整数序列表示的[6, 10, 3, 5, 12]可能需要5 * 32位;对于一个位字符串表示形式,5 * 4位就足够了(假设数字在[0;15]范围内)。

在此方面,knapsack problem是位字符串表示的最佳情况(每个位都说明相应的对象是否在背包中)。

我们可以随机选择任何交叉点。我看不出这比完全随机选择任何试用解决方案有什么好处

通常选择交叉点在数字的中间引入该数字的本质上任意的突变,具有破坏性(负)效果。

[人工智能-一种现代方法(Russel,Norvig)的本地搜索算法和优化问题-遗传算法部分中有关于此效果的很好的例子。

也看一下similar question on Software Engineering
© www.soinside.com 2019 - 2024. All rights reserved.