遗传算法中的交叉方法

Question

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

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

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

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

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

Answer 1

使用了几种东西......尽管对并行性和几代（有时是大量人口）的需求导致使用性能良好的技术......

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

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

有关更多信息，请参阅

• http://www.codeproject.com/KB/recipes/btl_ga.aspx
• http://www.codeproject.com/KB/recipes/genics_dot_net.aspx
• http://www.codeproject.com/KB/recipes/GeneticandAntAlgorithms.aspx
• http://www.c-sharpcorner.com/UploadFile/mgold/GeneticAlgorithm12032005044205AM/GeneticAlgorithm .aspx

Answer 2

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

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

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

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

简而言之，当你说：

我发现很难想象它足以操作简单的数据类型。

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

Answer 3

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

正如你所说：

我一直想象遗传算法的各个阶段会
对涉及复杂数学的复杂对象进行
操作

，其中染色体描述了一个程序，在此如果应用交叉时，您将能够与运算符一起做更多事情。

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

Answer 4

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

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

交叉要有效发挥作用，重要的是应满足以下几个属性：

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

您希望避免交叉中所谓的不需要的突变。从这个角度来看，您还希望避免在交叉后修复大部分染色体，因为这也会引入不需要的突变。

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

Answer 5

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

作为一个例子，我用 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();            
    }