c++ - 元启发式洗牌

Question

我目前正在研究一个 NP 完全问题，并为此实现了个人遗传算法。结果超出了我的预期。凭借精心设计的适应度函数和经过精心调整的一对种群/变异，我猜 GA 在某些情况下可能是一种出色的工具。

无论如何，我现在正在寻找能够产生最佳洗牌输出的元启发式算法(GA、模拟退火...)。

在这种情况下，我所说的混洗是指有限集的无偏(à la Fisher-Yates)随机排列。就像一个卡片组。一个巨大的(~500!排列)。

这个集合的值都是不同的。预计不会发生碰撞。

由于这种限制，我在实现 GA 解决方案时遇到了一些困难。事实上，打乱的值不能用作基因。很容易看出原因:

#include <iostream>
#include <vector>
#define SPLICING 50 // 50|50 one-point crossover
int crossover(int gene, int DNA_length, int A, int B)
{if (gene < (SPLICING*DNA_length)/100) return A; else return B;}

int main() {
    std::vector<int> A, B, C;
    A = { 3, 4, 8, 12, 2, 0, 9, 7, 10, 20 };
    B = { 8, 10, 3, 4, 20, 0, 7, 9, 2, 12 };
    int DNA_length = int(A.size());
    for (int i=0; i<DNA_length; i++) {
        C.push_back(crossover(i, DNA_length, A[i], B[i]));
                    if (i == DNA_length/2) std::cout << "| ";
                    std::cout << C[i] << " ";}
            }

输出:3 4 8 12 2 | 0 7 9 2 12

有两次碰撞 (2, 12)。

我的预期输出是这样的:3 4 8 12 2 | 0 7 9 10 20(无碰撞，完美洗牌原组)。

然后，我需要对这些值的顺序进行编码以避免这种困难。

一种天真的方法是用唯一的键来标识每个值。但是随后创建的集合是一个有序集合，因为它指的是值的排序。

看来交叉函数必须处理 parent DNA 的序数。但我不能全神贯注地解决在不发生冲突的情况下混合一个序数集(整个 DNA)的两个非线性有序序数子集( parent 的 DNA 切片)的问题!

也许我只能依靠突变来收敛。没有选择，没有 parent / child ，只有同一集合(个人的DNA)中的交换功能。简而言之:不是很有说服力。

置换唯一有限集中的序数确实很容易(例如，很简单:第一个变成第七个；第二个变成第十个，等等)。但是我不确定当第二个 of 集合 B 成为新集合的第十个时，第一个 of 集合 A 变成第七个是否有意义。

那么，我的问题是:

在您看来，可以在遗传算法的上下文中使用交叉函数来打乱集合的序数吗？如果否，您能否建议一种比蛮力、爬山技术或遗传算法更有效的元启发式方法？

谢谢。

Answer 1

您正在寻找的是基于顺序的遗传算法。您有许多基于顺序的交叉和变异运算符旨在处理此类问题。最简单的交叉算子的工作原理如下:

1. 选择交叉点
2. 将交叉点内parent1的部分复制到第一个儿子。
3. 列出交叉点之外的 parent1 元素
4. 将未使用的列表中的元素按照parent2中使用的相同顺序放置
5. 按照第 4 步中建立的顺序将这些元素复制到第一个儿子。

您可以在下图中看到我书中的示例(抱歉，描述是葡萄牙语 - 请与上面的列表相关联):

您可以在网络上搜索基于订单的运算符，或者如果您愿意，请查看我书中的数字 My Geneetic Algorithm book .您感兴趣的是第 10 章中的数字(您可以使用 Google 翻译器来理解图例)。

您不必介意本书使用序号 - 如果您没有重复，解释的所有概念都对您的问题有效。

希望对你有帮助。