4

在阅读遗传算法的交叉部分时，书籍和论文通常指的是简单地交换两个选定候选者的数据中的比特的方法，这些候选者要复制。

我还没有看到用于实际行业应用的已实现遗传算法的实际代码，但我发现很难想象它足以对简单的数据类型进行操作。

我一直认为遗传算法的各个阶段将在涉及复杂数学运算的复杂对象上执行，而不是仅仅交换单个整数中的一些位。

甚至维基百科也只是列出了这些类型的交叉操作。

我是否遗漏了一些重要的东西，或者这些交叉方法真的是唯一使用的东西吗？

4

5 回答 5

6

使用了几件事情......尽管需要并行性和几代人（有时是大量人口）导致使用性能良好的技术......

要记住的另一点是，正确建模时“交换一些位”类似于自然发生的简单且相当准确的版本（基因重组，突变）......

对于一个非常简单且写得很好的演练，请参阅http://www.electricmonk.nl/log/2011/09/28/evolutionary-algorithm-evolving-hello-world/

有关更多信息，请参阅

于 2011-10-30T12:18:59.047 回答
3

我一直认为遗传算法的各个阶段将在涉及复杂数学运算的复杂对象上执行，而不是仅仅交换单个整数中的一些位。

您可能认为使用了复杂的数学运算，因为您认为遗传算法必须修改复杂的对象。这通常不是遗传算法的工作方式。

那么会发生什么？好吧，通常，程序员（或科学家）会识别配置中的各种参数，然后将这些参数映射到 integers/floats。这确实限制了算法可以探索的方向，但这是获得任何结果的唯一现实方法。

让我们看看进化天线。您可以使用重新排列铜分子的遗传算法执行复杂的模拟，但这将非常复杂并且需要很长时间。相反，您将识别天线“参数”。大多数天线是由一定长度的电线构成的，在某些地方弯曲，以最大限度地扩大覆盖范围。因此，您可以确定几个参数：起始线数、截面长度、弯曲角度。所有这些都可以很容易地表示为整数，因此很容易被遗传算法操纵。可以将产生的操作输入“天线模拟器”，以查看它接收信号的能力。

简而言之，当你说：

我发现很难想象对简单的数据类型进行操作就足够了。

您必须意识到简单的数据类型可以映射到更复杂的结构。遗传算法不需要了解这些复杂的结构。它所需要知道的只是它如何操纵构建复杂结构的参数。毕竟，这就是 DNA 的工作方式。

于 2012-02-23T22:44:43.183 回答
1

不同的应用需要不同的连接。目标当然是找到最有效的编码，而且通常简单的编码更适合。因此，例如，作业车间调度问题可能表示为排列列表，这些排列表示不同机器上作业的执行顺序（所谓的作业序列矩阵）。然而，它也可以表示为构建调度的优先级规则列表。旅行商问题或二次分配问题通常由单个排列表示，该排列在一种情况下表示旅行，在另一种情况下表示分配。优化仿真模型的参数或寻找复杂数学函数的根通常由实数值向量表示。

对于所有这些，仍然存在简单的类型交叉和变异算子。对于排列，例如 OX、ERX、CX、PMX、UBX、OBX 等等。如果您可以组合许多简单的表示来表示复杂问题的解决方案，您可以重用这些操作并将它们单独应用于每个组件。

交叉有效工作的重要一点是应该满足一些属性：

  • 交叉应该保留那些在两者中相似的部分
  • 对于那些不相似的部分，交叉不应引入尚未属于其中一个父元素的元素
  • 如果可能，两个解决方案的交叉应该产生一个可行的解决方案

您想避免交叉中所谓的不需要的突变。鉴于此，您还希望避免在交叉后修复大部分染色体，因为这也会引入不需要的突变。

如果您想尝试不同的运算符和问题，我们有一个不错的 GUI 驱动软件：HeuristicLab。

于 2011-10-31T17:49:45.003 回答
1

在遗传算法中，通常使用某种类型的位交换。

正如你所说：

我一直想象遗传算法的各个阶段将在涉及复杂数学运算的复杂对象上执行

我认为您正在寻找的是遗传编程，其中染色体描述了一个程序，在这种情况下，您可以在应用交叉时对运算符进行更多操作。

还要确保您了解遗传算法中的适应度函数与遗传编程中染色体内的算子之间的区别。

于 2011-10-31T09:30:30.447 回答
1

简单的位交换通常是要走的路。需要注意的关键是每个候选解决方案中使用的编码。应该对解决方案进行编码，以使新后代中引入的错误最少或没有错误。任何错误都需要算法提供修复，这将导致处理时间增加。

例如，我用 C# 开发了一个大学时间表生成器，它使用整数编码来表示每天可用的时间段。这种表示允许非常有效的单点或多点交叉运算符，它使用 LINQ 相交函数来组合父级。

典型的爬山多点交叉

 public List<TimeTable> CrossOver(List<TimeTable> parents) // Multipoint crossover
    {                                   
        var baby1 = new TimeTable {Schedule = new List<string>(), Fitness = 0};
        var baby2 = new TimeTable {Schedule = new List<string>(), Fitness = 0};

        for (var gen = 0; gen < parents[0].Schedule.Count; gen++)
        {               
            if (rnd.NextDouble() < (double) CrossOverProb)
            {                      
                baby2.Schedule.Add(parents[0].Schedule[gen]);
                baby1.Schedule.Add(parents[1].Schedule[gen]);                                                          
            }
            else
            {
                baby1.Schedule.Add(parents[0].Schedule[gen]);
                baby2.Schedule.Add(parents[1].Schedule[gen]);
            }
        }

        CalculateFitness(ref baby1);
        CalculateFitness(ref baby2);  

        // allow hill-climbing
        parents.Add(baby1);
        parents.Add(baby2);

        return parents.OrderByDescending(i => i.Fitness).Take(2).ToList();            
    }
于 2011-10-31T18:43:14.457 回答