blocks|key|715984|text|我想你指的是“收敛速度”或“收敛速度”。你的问题在文献中有很多解决方案。我建议减少每次迭代的突变率，直到你陷入局部最优(收敛速度变得太低，绝对或相对)，然后重置或增加突变率以避免局部最优。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|715985|另外，你会做什么样的选择？如果父母比孩子好，你会留住他们吗？你是选择最好的个体，还是做轮盘赌选择(这会保持次优解，并有机会获得更多熵)？|715986|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|F|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|G|8|@]|9|@]|A|$]]|$1|D|3|-4|5|6|7|H|8|@]|9|@]|A|$]]]|E|$]]

I think you mean "convergence speed" or "rate of convergence". There are a lot of solutions for your problem in literature. I would suggest decreasing the mutation rate every iteration until you get "stuck" in a local optimum (rate of convergence gets too low, absolutely or relatively), then you reset or increase the mutation rate to escape the local optimum.

Also, what kind of selection do you do? Do you keep the parents if they are better than the children? Do you select the best individuals or do you do roulette-wheel selection (which keeps sub-optimal solutions with some chance for more entropy)?

blocks|key|1859953|text|这是一个相当透彻的教程，应该可以帮助你理解训练过程和所涉及的收敛。你说得对，它是一种梯度下降的形式。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1859954|http://informatics.indiana.edu/larryy/al4ai/lectures/03.IntroToGAs.pdf|offset|length|1859955|该文档已移动，现在可以在以下位置找到：|1859956|http://shinyverse.org/al4ai/lectures/03.IntroToGAs.pdf|1859957|entityMap|0|LINK|mutability|MUTABLE|url|1^0|0|0|1Y|0|0|0|0|1I|1|0^^$0|@$1|2|3|4|5|6|7|R|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|S|8|@]|9|@$D|T|E|U|1|V]]|A|$]]|$1|F|3|G|5|6|7|W|8|@]|9|@]|A|$]]|$1|H|3|I|5|6|7|X|8|@]|9|@$D|Y|E|Z|1|10]]|A|$]]|$1|J|3|-4|5|6|7|11|8|@]|9|@]|A|$]]]|K|$L|$5|M|N|O|A|$P|C]]|Q|$5|M|N|O|A|$P|I]]]]

This is a pretty thorough tutorial, should help you understand the training process and the convergence involved. You're right about it being a form of gradient descent.

<a href="http://informatics.indiana.edu/larryy/al4ai/lectures/03.IntroToGAs.pdf" rel="nofollow noreferrer">http://informatics.indiana.edu/larryy/al4ai/lectures/03.IntroToGAs.pdf</a>

That document has moved, and may now be found here:

<a href="http://shinyverse.org/al4ai/lectures/03.IntroToGAs.pdf" rel="nofollow noreferrer">http://shinyverse.org/al4ai/lectures/03.IntroToGAs.pdf</a>

blocks|key|2068437|text|遗传算法不是精确算法，它是一种启发式算法。这意味着无论你怎么努力，只有在极少数的非常罕见的情况下，你才能得到最优的解决方案。所以你是在用精度来换取一些速度。这并不意味着算法是一个失败者，只是它是为那些不需要精确解决方案而是一个很好的近似值的问题而设计的。这也意味着，除了找到最优值之外，您的必须为算法设置一个结束条件。这意味着必须有一个函数来评估一个解决方案，并告诉你它有多好。|type|unstyled|depth|inlineStyleRanges|offset|length|style|BOLD|entityRanges|data|2068438|如果你想试着提高你的精度，那么你将不得不使用特定于问题的知识来调整你的启发式方法。这意味着，利用你对问题的了解来设计更好的突变(而不是使用预定义的突变)，并改进你对种群的改进，选择算法。我再重复一遍，这不能保证你会找到最优的。|2068439|在你的特殊情况下，我相信几分钟后你就会陷入局部最大值。这意味着从这里开始你不会变得更好。这有时可以通过向种群中注入一些随机元素来解决，以便使算法摆脱最大值。这有时也可以通过故意选择糟糕的解决方案来解决。|2068440|entityMap^0|14|5|0|0|0^^$0|@$1|2|3|4|5|6|7|L|8|@$9|M|A|N|B|C]]|D|@]|E|$]]|$1|F|3|G|5|6|7|O|8|@]|D|@]|E|$]]|$1|H|3|I|5|6|7|P|8|@]|D|@]|E|$]]|$1|J|3|-4|5|6|7|Q|8|@]|D|@]|E|$]]]|K|$]]

The genetic algorithm is not a precise algorithm, it's a heuristic. That means that no matter how hard you try, only in a few very rare cases you're actually going to get to the optimal solution. So you are exchanging precision for some speed. This doesn't mean the algorithm is a loser, just that it was design for problems that don't demand the exact solution, but a good approximate. This also means that you must have an end condition for the algorithm other than finding the optimal. This means there has to exist a function that evaluates a solution and tells you how good it is.

If you want to try to increase a little bit more your precision, then you are going to have to adapt your heuristic using problem specific knowledge. This means, use what you know about the problem to design better mutations (not using the predefined ones) and also improve your refinement of the population, the selection algorithm. I repeat again, this won't guarantee that you'll find the optimal.

In your particular case I would believe that after a few minutes you're falling into a local maxima. This means that further from here you're not going to get better. This can be sometimes solved by injecting some random elements into the population in order to get the algorithm to get off the maxima. This can also be solved sometimes by deliberately choosing bad solutions.

blocks|key|1859999|text|所以本质上你有一个数字s，你想找到一个加起来为s的数字的子集，这被描述为subset+sum+problem，它是knapsack+problem的一个特例。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|1860000|我认为你关于遗传算法应用的解释是错误的。为了可视化必须考虑的可能解决方案的数量，从1000个项目的集合中选择500个项目，请阅读下面的数字"1000+/+500“的二项式系数|1860001|270288240945436569515614693625975275496152008446548287007392875106625428705522193898612483924502370165362606085021546104802209750050679917549894219699518475423665484263751733356162464079737887344364574161119497604571044985756287880514600994219426752366915856603136862602484428109296905863799821216320+(source)。|style|CODE|1860002|让我先澄清一下:遗传算法和相关方法是metaheuristics，的，这意味着它们不适合找到最优解，而是在非常短的时间内找到一个“好”的解。为了在NP困难的问题中找到最优解，你必须在最坏的情况下尝试每一种可能的组合。有一些精确优化的方法，可以智能地划分搜索空间，只评估较少的解决方案，但仍然需要数周时间才能得出最佳答案。|BOLD|1860003|如果你需要找到这个确切的最优方法，我建议你寻找确切的方法，比如branch+and+bound。例如，您可以使用著名的CPLEX优化器将您的问题描述为一个整数程序。例如，看看ILP+formulation+of+the+TSP，看看如何实现这一点，并将其转化为您的问题。|1860004|如果你不需要找到精确的最优解，你可以在你的遗传算法中监控几件事来改善它的输出：|1860005|1860006|使用足够大的种群大小和相应的选择压力。你想要避免多样性的影响，仍然要实现多样性(+convergence.|unordered-list-item|1860007|Monitor+genetic+drift+)在你的种群中。它是不是在迅速减少？如果你的种群中的所有解本质上都是相同的，那么算法已经收敛了。一旦它收敛了，你就需要重新启动它，或者引入新的遗传信息来恢复进化中的process.|1860008|Vary突变的力量。在搜索开始时翻转多个比特，在搜索结束时只翻转几个比特。|1860009|使用多个交叉点(我假设您使用单点交叉)。对于这么长的字符串，你可能想使用10个交叉点。|1860010|1860011|entityMap|0|LINK|mutability|MUTABLE|url|https://en.wikipedia.org/wiki/Subset_sum_problem|1|https://en.wikipedia.org/wiki/Knapsack_problem|2|http://www.ohrt.com/odds/binomial.php|3|http://en.wikipedia.org/wiki/Branch_and_bound|4|http://en.wikipedia.org/wiki/CPLEX|5|http://en.wikipedia.org/wiki/Travelling_salesman_problem#ILP_Formulation|6|http://en.wikipedia.org/wiki/Genetic_drift^0|10|I|0|1L|G|1|0|0|0|8C|8E|6|2|0|I|E|0|V|G|3|1N|5|4|2F|Q|5|0|0|0|0|8|D|6|0|0|0|0^^$0|@$1|2|3|4|5|6|7|1L|8|@]|9|@$A|1M|B|1N|1|1O]|$A|1P|B|1Q|1|1R]]|C|$]]|$1|D|3|E|5|6|7|1S|8|@]|9|@]|C|$]]|$1|F|3|G|5|6|7|1T|8|@$A|1U|B|1V|H|I]]|9|@$A|1W|B|1X|1|1Y]]|C|$]]|$1|J|3|K|5|6|7|1Z|8|@$A|20|B|21|H|L]]|9|@]|C|$]]|$1|M|3|N|5|6|7|22|8|@]|9|@$A|23|B|24|1|25]|$A|26|B|27|1|28]|$A|29|B|2A|1|2B]]|C|$]]|$1|O|3|P|5|6|7|2C|8|@]|9|@]|C|$]]|$1|Q|3|-4|5|6|7|2D|8|@]|9|@]|C|$]]|$1|R|3|S|5|T|7|2E|8|@]|9|@]|C|$]]|$1|U|3|V|5|T|7|2F|8|@]|9|@$A|2G|B|2H|1|2I]]|C|$]]|$1|W|3|X|5|T|7|2J|8|@]|9|@]|C|$]]|$1|Y|3|Z|5|T|7|2K|8|@]|9|@]|C|$]]|$1|10|3|-4|5|6|7|2L|8|@]|9|@]|C|$]]|$1|11|3|-4|5|6|7|2M|8|@]|9|@]|C|$]]]|12|$13|$5|14|15|16|C|$17|18]]|19|$5|14|15|16|C|$17|1A]]|1B|$5|14|15|16|C|$17|1C]]|1D|$5|14|15|16|C|$17|1E]]|1F|$5|14|15|16|C|$17|1G]]|1H|$5|14|15|16|C|$17|1I]]|1J|$5|14|15|16|C|$17|1K]]]]

So essentially you have a number s and you want to find a subset of numbers that add up to s. This is described as the <a href="https://en.wikipedia.org/wiki/Subset_sum_problem" rel="nofollow">subset sum problem</a> which is a special case of the <a href="https://en.wikipedia.org/wiki/Knapsack_problem" rel="nofollow">knapsack problem</a>.

I think your expactations regarding the application of genetic algorithms are wrong. To visualize the number of possible solutions that have to be considered to select 500 items out of a set of 1000 items, please read the following number [the binomial coefficient for "1000 over 500"]:

<code>270288240945436569515614693625975275496152008446548287007392875106625428705522193898612483924502370165362606085021546104802209750050679917549894219699518475423665484263751733356162464079737887344364574161119497604571044985756287880514600994219426752366915856603136862602484428109296905863799821216320</code> (<a href="http://www.ohrt.com/odds/binomial.php" rel="nofollow">source</a>).

Le me clarify first: Genetic algorithms and related methods are metaheuristics, which means they are not suited to find the optimal solution, but a "good" solution in a very short time. To find the optimum solution in a problem that is NP hard you would have to try every single possible combination in the worst case. There are methods for exact optimization that intelligently partition the search space and evaluate only a smaller number of solutions, still it can take weeks to come up with the optimal answer.

If you are required to find this exact optimum I would suggest you look for exact methods such as e.g. <a href="http://en.wikipedia.org/wiki/Branch_and_bound" rel="nofollow">branch and bound</a>. You could use for example the well-known <a href="http://en.wikipedia.org/wiki/CPLEX" rel="nofollow">CPLEX</a> optimizer to describe your problem as an integer program. Look for example at the <a href="http://en.wikipedia.org/wiki/Travelling_salesman_problem#ILP_Formulation" rel="nofollow">ILP formulation of the TSP</a> to see how this can be achieved and translate that to your problem.

If you are not required to find the exact optimum there are several things that you can monitor in your genetic algorithm to improve its output:

<ul>
<li>Use a large enough population size and according selection pressure. You want to avoid the effect of <a href="http://en.wikipedia.org/wiki/Genetic_drift" rel="nofollow">genetic drift</a>, still achieve convergence.</li>
<li>Monitor the variance (diversity) in your population. Is it decreasing quickly? If all solutions in your population are essentially the same then the algorithm has converged. Once it has converged you would need to restart it, or introduce new genetic information to revive the evoluationary process.</li>
<li>Vary the strength of the mutation. Flip multiple bits at the beginning of the search and reduce to flip only few bits at the end of the search.</li>
<li>Use multiple crossover points (I assume you're using single-point crossover). For such a long string maybe you want to use 10 crossover points.</li>
</ul>

To set up my question, allow me to start with an example:

Suppose a set of 1000 arrays (aka, row vectors) all the same length. Each is filled with random numbers between -1 and 1. I then pull 500 of those row vectors at random and sum them up. I now start with the sum and want to reverse engineer the selection from the original 1000. 

I decide to solve this with a genetic algorithm. I start a family of bit strings 1000 bits long and run through the mutate (aka, flip-a-random-bit) and crossover procedures. Then, after a tenth of a second, I'm 75% right. Then, after another hour, I'm 76% right. Essentially, I'm stuck waiting forever for some few dozen bits to be set correctly. It may be that my random number generator never introduces those in a way that they can be merged into the solution.

The algorithm does very well at the beginning, but then fails to improve the solution further. I tried making sure that my genetic family had one of every possible bit position. That didn't help; you can't judge how quickly items will die out of the pool.

It seems that there must be an additional component to the algorithm. There must be something driving the selection of the flip-bit (aka, mutation) locations. What is the technical term for this piece? Gradient? Where does it come from?

genetic algorithms: name the piece that drives the mutation location

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

要提出我的问题，请允许我从一个示例开始：假设有1000个长度相同的数组(也称为行向量)。每个向量都填充了-1到1之间的随机数。然后，我随机抽取500个行向量，并将它们相加。我现在从总和开始，并希望对原始1000中的选择进行反向工程。我决定用遗传算法来解决这个问题。我开始了一个1000位长的位串系列，并运行了变异(也就是...

问遗传算法:命名驱动突变位置的片段
EN

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问遗传算法:命名驱动突变位置的片段EN