c++ - 如何构建遗传算法类层次结构？

Question

我正在做一些遗传算法方面的工作，并且想编写我自己的 GA 类。由于 GA 可以采用不同的方式进行选择、变异、交叉、生成初始种群、计算适应度和终止算法，因此我需要一种方法来插入这些方式的不同组合。我最初的方法是有一个抽象类，将所有这些方法定义为纯虚拟的，并且任何具体类都必须实现它们。例如，如果我想尝试两个相同但具有不同交叉方法的 GA，我必须创建一个继承自 GeneticAlgorithm 的抽象类并实现除交叉方法之外的所有方法，然后是两个具体类继承自该类并仅实现交叉方法。这样做的缺点是，每次我想更换一两个方法来尝试新的东西时，我都必须创建一个或多个新类。

还有其他方法可以更好地解决这个问题吗？

Answer 1

我在实现 GA 框架时采取的方法如下: 创建以下类: 一代 遗传算法 遗传算法适配器 遗传算法参数 人口 个人

虽然我没有为各种操作实现策略模式，但我确信在 GeneticAlgorithm 实例上创建各种 GA 操作实现作为参数是很简单的。

GeneticAlgorithm 类捕获基本算法。它实际上只是定义了各个步骤(群体创建、个体随机化、选择、交叉、突变等)，并在算法运行时管理个体群体。我想如果您愿意的话，您可以在这里插入不同的操作。

真正的魔力在于适配器。这就是使问题域(个体的特定子类及其所有相关数据)适应遗传算法的原因。我在这里大量使用泛型，以便将总体、参数和个体的特定类型传递到实现中。这为我提供了对适配器实现的智能感知和强类型检查。适配器基本上需要定义如何对给定个体(及其基因组)执行特定操作。例如，以下是适配器的接口(interface):

/// <summary>
/// The interface for an adapter that adapts a domain problem so that it can be optimised with a genetic algorithm.
    /// It is a strongly typed version of the adapter.
    /// </summary>
    /// <typeparam name="TGA"></typeparam>
    /// <typeparam name="TIndividual"></typeparam>
    /// <typeparam name="TPopulation"></typeparam>
    public interface IGeneticAlgorithmAdapter<TGA, TIndividual, TGeneration, TPopulation> : IGeneticAlgorithmAdapter
        where TGA : IGeneticAlgorithm
        where TIndividual : class, IIndividual, new()
        where TGeneration : class, IGeneration<TIndividual>, new()
        where TPopulation : class, IPopulation<TIndividual, TGeneration>, new()
    {
        /// <summary>
        /// This gets called before the adapter is used for an optimisation.
        /// </summary>
        /// <param name="pso"></param>
        void InitialiseAdapter(TGA ga);

        /// <summary>
        /// This initialises the individual so that it is ready to be used for the genetic algorithm.
        /// It gets randomised in the RandomiseIndividual method.
        /// </summary>
        /// <param name="ga">The genetic algorithm that is running.</param>
        /// <param name="individual">The individual to initialise.</param>
        void InitialiseIndividual(TGA ga, TIndividual individual);

        /// <summary>
        /// This initialises the generation so that it is ready to be used for the genetic algorithm.
        /// </summary>
        /// <param name="ga">The genetic algorithm that is running.</param>
        /// <param name="generation">The generation to initialise.</param>
        void InitialiseGeneration(TGA ga, TGeneration generation);

        /// <summary>
        /// This initialises the population so that it is ready to be used for the genetic algorithm.
        /// </summary>
        /// <param name="ga">The genetic algorithm that is running.</param>
        /// <param name="population">The population to initialise.</param>
        void InitialisePopulation(TGA ga, TPopulation population);

        void RandomiseIndividual(TGA ga, TIndividual individual);

        void BeforeIndividualUpdated(TGA ga, TIndividual individual);
        void AfterIndividualUpdated(TGA ga, TIndividual individual);

        void BeforeGenerationUpdated(TGA ga, TGeneration generation);
        void AfterGenerationUpdated(TGA ga, TGeneration generation);

        void BeforePopulationUpdated(TGA ga, TPopulation population);
        void AfterPopulationUpdated(TGA ga, TPopulation population);

        double CalculateFitness(TGA ga, TIndividual individual);

        void CloneIndividualValues(TIndividual from, TIndividual to);

        /// <summary>
        /// This selects an individual from the population for the given generation.
        /// </summary>
        /// <param name="ga">The genetic algorithm that is running.</param>
        /// <param name="generation">The generation to select the individual from.</param>
        /// <returns>The selected individual.</returns>
        TIndividual SelectIndividual(TGA ga, TGeneration generation);

        /// <summary>
        /// This crosses over two parents to create two children.
        /// </summary>
        /// <param name="ga">The genetic algorithm that is running.</param>
        /// <param name="parentsGeneration">The generation that the parent individuals belong to.</param>
        /// <param name="childsGeneration">The generation that the child individuals belong to.</param>
        /// <param name="parent1">The first parent to cross over.</param>
        /// <param name="parent2">The second parent to cross over.</param>
        /// <param name="child">The child that must be updated.</param>
        void CrossOver(TGA ga, TGeneration parentsGeneration, TIndividual parent1, TIndividual parent2, TGeneration childsGeneration, TIndividual child);

        /// <summary>
        /// This mutates the given individual.
        /// </summary>
        /// <param name="ga">The genetic algorithm that is running.</param>
        /// <param name="generation">The individuals generation.</param>
        /// <param name="individual">The individual to mutate.</param>
        void Mutate(TGA ga, TGeneration generation, TIndividual individual);

        /// <summary>
        /// This gets the size of the next generation to create.
        /// Typically, this is the same size as the current generation.
        /// </summary>
        /// <param name="ga">The genetic algorithm that is running.</param>
        /// <param name="currentGeneration">The current generation.</param>
        /// <returns>The size of the next generation to create.</returns>
        int GetNextGenerationSize(TGA ga, TGeneration currentGeneration);


        /// <summary>
        /// This gets whether a cross over should be performed when creating a child from this individual.
        /// </summary>
        /// <param name="ga">The genetic algorithm that is running.</param>
        /// <param name="currentGeneration">The current generation.</param>
        /// <param name="individual">The individual to determine whether it needs a cross over.</param>
        /// <returns>True to perform a cross over. False to allow the individual through to the next generation un-altered.</returns>
        bool ShouldPerformCrossOver(TGA ga, TGeneration generation, TIndividual individual);

        /// <summary>
        /// This gets whether a mutation should be performed when creating a child from this individual.
        /// </summary>
        /// <param name="ga">The genetic algorithm that is running.</param>
        /// <param name="currentGeneration">The current generation.</param>
        /// <param name="individual">The individual to determine whether it needs a mutation.</param>
        /// <returns>True to perform a mutation. False to allow the individual through to the next generation un-altered.</returns>
        bool ShouldPerformMutation(TGA ga, TGeneration generation, TIndividual individual);
    }

我发现这种方法对我来说效果很好，因为我可以轻松地针对不同的问题域重用 GA 实现，只需编写适当的适配器即可。对于不同的选择、交叉或变异实现，适配器可以调用它感兴趣的实现。我通常做的是在适配器中注释掉不同的想法，同时研究合适的策略。

希望这有帮助。必要时我可以提供更多指导。很难做到这样的设计公正。