多背包问题的改进遗传算法
最近我一直在改进多背包问题的传统遗传算法。所以我的改进遗传算法比传统遗传算法效果更好。我测试过。 （我使用了 OR-Library 公开提供的 (http://people .brunel.ac.uk/~mastjjb/jeb/orlib/mknapinfo.html）用于测试 GA。）有谁知道其他改进的 GA。我想与其他改进的遗传算法进行比较。其实我在网上搜索过。但找不到好的算法来比较。
Recently i've been improving traditional genetic algorithm for multiknapsack problem. So My Improved Genetic Algorithm is working better then Traditional Genetic Algorithm. I tested. (i used publically available from OR-Library (http://people.brunel.ac.uk/~mastjjb/jeb/orlib/mknapinfo.html) were used to test the GAs.) Does anybody know other improved GA. I wanted to compare with other improved genetic algorithm. Actually i searched in internet. But couldn't find good algorithm to compare.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
应该有很多不错的 GA 方法可供您比较。然而，您应该首先尝试清楚地确定您已经测试过哪种“传统”GA 方法。
我可以推荐的一种好方法是 NSGA-II 算法，它是为多目标优化而开发的。
请查看以下内容以了解其他想法：
There should be any number of decent GA methods against which you can compare. However, you should try to first clearly establish exactly which "traditional" GA method you have already tested.
One good method which I can recommend is the NSGA-II algorithm, which was developed for multi-objective optimization.
Take a look at the following for other ideas:
您只能将您的解决方案与具有完全相同的编码和适应度函数的问题进行比较（这意味着它们是等效的问题）。如果问题不同，那么随着问题的变化，任何比较都会很快变得无关紧要，因为适应度函数几乎总是针对您想要解决的任何问题。事实上，如果您使用遗传算法工具包，则适应度函数是您唯一需要编写的内容，因为其他所有内容通常都是开箱即用的。
另一方面，如果适应度函数相同，那么比较给定不同参数的结果是有意义的，例如不同的突变率、不同的交叉实现，甚至完全不同的进化范式，例如共同进化、基因表达、比较标准 GA 等。
You can compare your solution only to problems with the exact same encoding and fitness function (meaning they are equivalent problems). If the problem is different any comparison becomes quickly irrelevant as the problem changes, since the fitness function is almost always ad-hoc for whatever you're trying to solve. In fact the fitness function is the only thing you need to code if you use a Genetic Algorithms toolkit, as everything else usually comes out of the box.
On the other end, if the fitness function is the same, then it makes sense to compare results given different parameters, such as different mutation rate, different implementations of crossover, or even completely different evolutionary paradigms, such as coevolution, gene expression, compared to standard GAs, and so on.
您是否正在尝试通过使用遗传算法来提高多背包求解器的最新技术？或者您是否试图通过使用 multiknapsack 作为测试平台来推进遗传算法技术？ （你能澄清一下吗？）
根据你的目标是什么，你的问题的答案是完全不同的。由于其他人已经解决了后一个问题，我将假设前一个问题。
与基本遗传算法相比，几乎没有什么重大的飞跃。通过使用遗传算法解决多重背包问题的最佳改进是改进突变和交叉算子的编码，这可以使结果性能产生数量级的差异，并消除对基本遗传算法的任何调整。您可以做很多事情来使突变和交叉算子适合多背包。
我首先会调查有关 multiknapsack 的文献，看看人们在 multiknapsack 上使用的不同类型的搜索空间和解决方案技术。在他们的最优或次优方法（独立于遗传算法）中，他们使用什么类型的搜索运算符？它们将什么编码为变量以及将什么编码为值？使用什么启发式评估函数？他们检查哪些限制？然后，您将根据您的变异和交叉算子调整它们的编码，并查看它们在遗传算法中的表现如何。
多背包问题的有效搜索空间编码或准确的启发式评估函数很可能转化为高效的变异和交叉算子。由于多重背包是一个经过深入研究的问题，拥有大量研究文献，因此它对您来说应该是一座金矿。
Are you trying to improve the state-of-the-art in multiknapsack solvers by the use of genetic algorithms? Or are you trying to advance the genetic algorithm technique by using multiknapsack as a test platform? (Can you clarify?)
Depending on which one is your goal, the answer to your question is entirely different. Since others have addressed the latter question, I'll assume the former.
There has been little major leaps and bounds over the basic genetic algorithm. The best improvement in solving the multiknapsack via the use of genetic algorithms would be to improve your encoding of the mutation and crossover operators which can make orders of magnitude of difference in the resulting performance and blow out of the water any tweaks to the fundamental genetic algorithm. There is a lot you can do to make your mutation and crossover operators tailored to multiknapsack.
I would first survey the literature on multiknapsack to see what are the different kinds of search spaces and solution techniques people have used on multiknapsack. In their optimal or suboptimal methods (independent of genetic algorithms), what kinds of search operators do they use? What do they encode as variables and what do they encode as values? What heuristic evaluation functions are used? What constraints do they check for? Then you would adapt their encodings to your mutation and crossover operators, and see how well they perform in your genetic algorithms.
It is highly likely that an efficient search space encoding or an accurate heuristic evaluation function of the multiknapsack problem can translate into highly effective mutation and crossover operators. Since multiknapsack is a very well studied problem with a large corpus of research literature, it should be a gold mine for you.