遗传算法中的交叉方法

Question

当阅读关于遗传算法中的交叉部分时，书籍和论文通常提到的方法是简单地交换两个选定候选人的数据中的位以进行繁殖。我尚未看到实际应用于实际工业应用的遗传算法的实际代码，但我发现仅对简单数据类型进行操作是不够的很难想象。

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

即使Wikipedia也仅列出了这些交叉操作的种类。

我是否缺少重要的东西，或者这些交叉方法真的是唯一使用的东西？

- TravisG

---

只是一个更新，如果你们在等待哪个答案将被接受：我会对你们所说的一切进行一些研究，并在此之后做出决定，因为现在所有的答案似乎都非常有用！谢谢。 - TravisG

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/genetics_dot_net.aspx
• http://www.codeproject.com/KB/recipes/GeneticandAntAlgorithms.aspx
• http://www.c-sharpcorner.com/UploadFile/mgold/GeneticAlgorithm12032005044205AM/GeneticAlgorithm.aspx

- Yahia

Answer 2

我一直认为遗传算法的各个阶段都需要对涉及复杂数学运算的复杂对象进行操作，而不仅仅是交换单个整数中的某些位。你可能认为需要使用复杂的数学运算，因为遗传算法必须修改一个复杂对象。但通常遗传算法并非如此工作。

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

让我们看看如何演化天线。您可以通过使用遗传算法重新排列铜分子来执行复杂模拟，但这将非常复杂且耗时长。相反，您可以识别出天线的“参数”。大多数天线由某些长度的导线组成，弯曲在某些地方以最大限度地增加其覆盖范围。因此，您可以识别出一些参数：起始电线数量、部分长度和弯曲角度。所有这些都可以轻松表示为整数，并且易于遗传算法进行操作。然后可以将结果输送到“天线模拟器”中，以查看它接收信号的效果。

总之，当您说：

我觉得仅对简单的数据类型进行操作是不够的。

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

- Ferry Boender

Answer 3

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

举个例子，我开发了一个使用C#编写的大学课表生成器，它使用整数编码来表示每天可用的时间段。这种表示方式允许非常高效的单点或多点交叉运算符，它使用LINQ的intersect函数来合并父代。

典型的多点交叉与爬山法

 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();            
    }

- Romaine Carter

Answer 4

在遗传算法中，通常会使用某种位交换技术。

正如你所说：

“我一直想象遗传算法的各个阶段将涉及到涉及复杂数学运算的复杂对象。”

我认为你正在寻找的是遗传编程，其中染色体描述了一个程序，在这种情况下，当应用交叉时，您将能够更多地使用运算符。

此外，请确保您已经理解了遗传算法中的适应度函数和遗传编程中染色体内的运算符之间的区别。

- NWS

Answer 5

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

对于所有这些简单类型，都存在交叉和变异算子。对于置换，这些算子包括OX、ERX、CX、PMX、UBX、OBX等许多算子。如果您可以组合一些简单的表示形式来表示解决方案的复杂问题，则可以重复使用这些操作，并将其分别应用于每个组件。

交叉能够有效地工作的重要因素是必须满足一些属性：

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

您希望避免在交叉过程中出现所谓的不必要的突变。在这种情况下，您还希望避免在交叉后修复大部分染色体，因为这也会引入不必要的突变。

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

- Andreas