遗传算法:如何在“子集”中进行交叉?问题? [英] Genetic algorithms: How to do crossover in "subset" problems?

查看:180
本文介绍了遗传算法:如何在“子集”中进行交叉?问题?的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

我有一个要通过遗传算法解决的问题。问题是选择100个整数的某个子集(例如4)(这些整数只是表示其他内容的id)。顺序无所谓,解决问题的方法是设置整数而不是有序列表。我的健身功能很好,但是交叉功能却很麻烦。



我希望能够交配以下两个染色体:



[1 2 3 4]和
[3 4 5 6]变成有用的东西。显然,我无法使用典型的交叉功能,因为最终我的子级中可能会出现重复,这将代表无效的解决方案。在这种情况下,最好的交叉方法是什么。

解决方案

只要忽略在两者中出现的任何元素



其余元素形成两个不相交的集合,您可以将其设置为两个不相交的集合。



几乎可以应用任何随机变换(例如,随机交换一些对),而无需重复。



这可以看作是对两个集合进行排序和对齐,以便匹配的元素彼此面对并应用一种标准的交叉算法。


I have a problem which I am trying to solve with genetic algorithms. The problem is selecting some subset (say 4) of 100 integers (these integers are just ids that represent something else). Order does not matter, the solution to the problem is a SET of integers not an ordered list. I have a good fitness function but am having trouble with the crossover function.

I want to be able to mate the following two chromosomes:

[1 2 3 4] and [3 4 5 6] into something useful. Clearly I cannot use the typical crossover function because I could end up with duplicates in my children which would represent invalid solutions. What is the best crossover method in this case.

解决方案

Just ignore any element that occurs in both of the sets (i.e. in their intersection.), that is leave such elements unchanged in both sets.

The rest of the elements form two disjoint sets, to which you can apply pretty much any random transformation (e.g. swapping some pairs randomly) without getting duplicates.

This can be thought of as ordering and aligning both sets so that matching elements face each other and applying one of the standard crossover algorithms.

这篇关于遗传算法:如何在“子集”中进行交叉?问题?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!

查看全文
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆