Integerinterval 不等于 2 的幂的遗传算法染色体设计
Genetic Algorithm Chromosome Design for Integerinterval not equal to power of two
我有一个相当明显的问题，我有点困惑，我在互联网上找不到任何答案：
染色体内离散表型的二进制表示似乎是常态。但是所有的解释，例如 wikipedia page，只是提到，你可以用长度为 l 的染色体表示 2^l 表型。
但如果我有 300 个表型，最好的策略是什么？那么我可能生成的染色体中有很多（512-300=212）根本就是错误的。如何处理这样一个有上限的区间？
对我来说，这个问题更为重要，因为我有许多更小的尺寸，它们粘在一起。例如，如果我的 10 个维度中的每一个维度的大小都是 33，那么我的最终染色体中有 10 位，如果该维度的所有其他位都为 0，则只能为 1。
提前致谢！
Binary representation of a discrete phenotype within the chromosome appears to be the norm
我不认为那是真的。即使是……谁在乎呢。您不必使用二进制表示。
您没有指定要优化的问题。每个问题都会有不同的表示形式。有用就用。
有两种情况 - 基因型和表型。
基因型是你通过进化来操纵的东西。这些是 1 和 0，但它可以是任何你想要的。
表型是你实际评估健康的东西，你最终想要优化的东西，例如。 TSP 中的路径。
其实我撒谎了，有三件事。第三个是基因型-表型映射，它介于前两者之间。此映射的职责是为每种可能的基因型生成表型。
最后，它是关于映射的设计以及随后的基因型，以便它可以满足您的需要。你说你有 300 种可能的表型？你想使用二进制表示吗？那么，设计你的映射，它将 512 个对象映射到 300 个对象上。不过你觉得还可以。完成。
一般经验法则是作图应 "scramble" 基因型尽可能少。 IE。它应该尽可能地允许基因型的微小变化导致表型的微小变化。
小记：为什么要用GA搜索size 300的space？穷举不成吗？
最后我想告诉你，我在我的项目中做了什么，并给出了一些出版物以供验证。
首先是编码：虽然已经考虑了格雷编码和二进制编码，但 Rothlauf ("The Influence Of Binary Representations Of Integers On The Performance Of Selectorecombinative Genetic Algorithms." Rothlauf 2012) 的工作强调了二进制表示的固有优势。
另一方面，更严重的问题是找到一个合适的策略来用 m 位表示 n 个整数，这本来可以表示 2^m 个整数。即使采用尽可能少的位，也有 2^m-n 条染色体，它们不代表有效索引。为了解决这个问题，出现了两种不同的策略（参见："On methods for discrete structural optimization" Ringertz 1988，"Genetic algorithms in optimization problems with discrete and integer design variables" Lin 1992，"Methods for optimization of nonlinear problems with discrete variables: a review" Arora 1994}）：
- 惩罚方法：按照这种方法，所有无效的基因组都被分配了非常低的适应性。这导致它们极有可能消失。
- 过度分布方法：在这种方法中，无效染色体通过预定义的映射策略分配给有效表型。一个自然相关的缺点是导致有效值之间的分布不均匀，因为 $n$ 基因中的 $2^m-n$ 将具有两个表示而不是只有一个。这个问题可以通过为染色体使用更多的附加位来减少。一个人占用的位数越多，分配就越平均。易于理解：例如，在极端情况下，分布在 15 个解决方案中的 1024 个可能的染色体配置将导致比 16 个可能的配置更均匀的分布，其中只有 1 个解决方案获得第二个表示。
为了多维度的支持，所有维度的基因都进行了拼接。
我有一个相当明显的问题，我有点困惑，我在互联网上找不到任何答案：
染色体内离散表型的二进制表示似乎是常态。但是所有的解释，例如 wikipedia page，只是提到，你可以用长度为 l 的染色体表示 2^l 表型。
但如果我有 300 个表型，最好的策略是什么？那么我可能生成的染色体中有很多（512-300=212）根本就是错误的。如何处理这样一个有上限的区间？
对我来说，这个问题更为重要，因为我有许多更小的尺寸，它们粘在一起。例如，如果我的 10 个维度中的每一个维度的大小都是 33，那么我的最终染色体中有 10 位，如果该维度的所有其他位都为 0，则只能为 1。
提前致谢！
Binary representation of a discrete phenotype within the chromosome appears to be the norm
我不认为那是真的。即使是……谁在乎呢。您不必使用二进制表示。
您没有指定要优化的问题。每个问题都会有不同的表示形式。有用就用。
有两种情况 - 基因型和表型。
基因型是你通过进化来操纵的东西。这些是 1 和 0，但它可以是任何你想要的。
表型是你实际评估健康的东西，你最终想要优化的东西，例如。 TSP 中的路径。
其实我撒谎了，有三件事。第三个是基因型-表型映射，它介于前两者之间。此映射的职责是为每种可能的基因型生成表型。
最后，它是关于映射的设计以及随后的基因型，以便它可以满足您的需要。你说你有 300 种可能的表型？你想使用二进制表示吗？那么，设计你的映射，它将 512 个对象映射到 300 个对象上。不过你觉得还可以。完成。
一般经验法则是作图应 "scramble" 基因型尽可能少。 IE。它应该尽可能地允许基因型的微小变化导致表型的微小变化。
小记：为什么要用GA搜索size 300的space？穷举不成吗？
最后我想告诉你，我在我的项目中做了什么，并给出了一些出版物以供验证。
首先是编码：虽然已经考虑了格雷编码和二进制编码，但 Rothlauf ("The Influence Of Binary Representations Of Integers On The Performance Of Selectorecombinative Genetic Algorithms." Rothlauf 2012) 的工作强调了二进制表示的固有优势。
另一方面，更严重的问题是找到一个合适的策略来用 m 位表示 n 个整数，这本来可以表示 2^m 个整数。即使采用尽可能少的位，也有 2^m-n 条染色体，它们不代表有效索引。为了解决这个问题，出现了两种不同的策略（参见："On methods for discrete structural optimization" Ringertz 1988，"Genetic algorithms in optimization problems with discrete and integer design variables" Lin 1992，"Methods for optimization of nonlinear problems with discrete variables: a review" Arora 1994}）：
- 惩罚方法：按照这种方法，所有无效的基因组都被分配了非常低的适应性。这导致它们极有可能消失。
- 过度分布方法：在这种方法中，无效染色体通过预定义的映射策略分配给有效表型。一个自然相关的缺点是导致有效值之间的分布不均匀，因为 $n$ 基因中的 $2^m-n$ 将具有两个表示而不是只有一个。这个问题可以通过为染色体使用更多的附加位来减少。一个人占用的位数越多，分配就越平均。易于理解：例如，在极端情况下，分布在 15 个解决方案中的 1024 个可能的染色体配置将导致比 16 个可能的配置更均匀的分布，其中只有 1 个解决方案获得第二个表示。
为了多维度的支持，所有维度的基因都进行了拼接。