算法题:比赛选择(GA)问题介绍和解决方案

2021年4月17日18:22:56 发表评论 784 次浏览

比赛选择是一种选择策略, 用于在遗传算法中从当前一代中选择最适合的候选人。这些选定的候选人然后被传递给下一代。在K向锦标赛选择中, 我们选择k个人并在其中进行比赛。在那些选择的候选者中, 只有最适合的候选者被选中, 然后传递给下一代。通过这种方式, 可以举办许多这样的比赛, 我们将最终选拔出下一代的候选人。它还具有称为选择压力的参数, 该参数是候选人参加锦标赛可能性的概率度量。如果锦标赛规模较大, 则较弱的候选人被选出的可能性较小, 因为它必须与较强的候选人竞争。选择压力参数确定了GA的收敛速度。选择压力越大, 收敛速度越大。 GA能够在很大的选择压力范围内确定最佳或接近最佳的解决方案。比赛选择也适用于负健身值。

Algorithm --
1.Select k individuals from the population and perform a tournament amongst them
2.Select the best individual from the k individuals
3. Repeat process 1 and 2 until you have the desired amount of population

让我们进行三项锦标赛选择, 我们希望的人口数量为6, 而其健身得分的初始人口为[1、2、3、4、5、6]。我们的第一场比赛将如下图所示(见图), 适应度值为6的获胜者将进入下一代。

比赛选择(GA)1

比赛选择

在第一次锦标赛之后, 我们选择了[6]作为人口。

在几次这样的比赛之后,我们可能有一个选定的人口[6,6,6,5,4,3]。它甚至可以是[6 6 5 4 3 2]。因此,下一代更有可能选出最合适的候选人。

如果以概率p选出最佳候选人

然后以p*(1-p)的概率选出下一个最佳候选人

下一个是p*(1-p)^2

等等.....

参考文献

1. http://wpmedia.wolfram.com/uploads/sites/13/2018/02/09-3-2.pdf

2. https://en.wikipedia.org/wiki/Tournament_selection


木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: