最近我一直在改进多背包问题的传统遗传算法。所以我改进的遗传算法比传统的遗传算法效果更好。我测试过。（我使用从 OR-Library（http://people.brunel.ac.uk/~mastjjb/jeb/orlib/mknapinfo.html）公开获得的用于测试 GA。）有人知道其他改进的 GA。我想与其他改进的遗传算法进行比较。其实我在互联网上搜索。但是找不到比较好的算法。
问问题
563 次
3 回答
1
应该有任意数量的体面 GA 方法可供您比较。但是，您应该首先尝试清楚地确定您已经测试过哪种“传统” GA 方法。
我可以推荐的一种好方法是NSGA-II 算法，它是为多目标优化而开发的。
看看下面的其他想法：
- 遗传算法 - 维基百科
- 卡洛斯 A. Coello Coello (1999)。“基于进化的多目标优化技术的综合调查”，知识和信息系统，卷。1，第 269-308 页。
- Carlos A. Coello Coello 等人 (2005)。“进化多目标优化的当前和未来研究趋势”，进化算法的信息处理，Springer。
于 2010-06-23T02:23:12.910 回答
1
您只能将您的解决方案与具有完全相同编码和适应度函数的问题进行比较（这意味着它们是等效的问题）。如果问题不同，随着问题的变化，任何比较都会很快变得无关紧要，因为适应度函数几乎总是针对您要解决的任何问题。事实上，如果您使用遗传算法工具包，您只需编写适应度函数即可，因为其他所有内容通常都是开箱即用的。
另一方面，如果适应度函数相同，那么在给定不同参数的情况下比较结果是有意义的，例如不同的突变率，不同的交叉实现，甚至完全不同的进化范式，例如协同进化，基因表达，比较到标准 GA，等等。
于 2010-06-10T16:09:36.787 回答
0
您是否正在尝试通过使用遗传算法来提高多背包求解器的最新技术？或者您是否试图通过使用 multiknapsack 作为测试平台来推进遗传算法技术？（你能澄清一下吗？）
根据您的目标是哪一个，您的问题的答案是完全不同的。由于其他人已经解决了后一个问题，我将假设前者。
基本的遗传算法几乎没有什么重大的飞跃。通过使用遗传算法解决多背包问题的最佳改进是改进对变异和交叉算子的编码，这可以使结果性能产生数量级的差异，并对基本遗传算法进行任何调整. 您可以做很多事情来使您的变异和交叉运算符适合多背包。
我将首先调查关于多背包的文献，看看人们在多背包上使用了哪些不同类型的搜索空间和解决方案技术。在他们的最优或次优方法（独立于遗传算法）中，他们使用什么样的搜索算子？它们将什么编码为变量以及它们将什么编码为值？使用了哪些启发式评估函数？他们检查什么约束？然后，您将根据您的变异和交叉运算符调整它们的编码，并查看它们在您的遗传算法中的表现如何。
多背包问题的有效搜索空间编码或准确的启发式评估函数很可能转化为高效的变异和交叉算子。由于 multiknapsack 是一个拥有大量研究文献的很好研究的问题，它应该是你的金矿。
于 2010-06-23T07:22:37.603 回答