Как структурировать иерархию классов Генетического алгоритма?

Question

Я работаю с Генетическими Алгоритмами и хочу написать свои собственные классы GA. Поскольку у GA могут быть разные способы выбора, мутации, кроссинговера, генерации начальной популяции, расчета пригодности и завершения алгоритма, мне нужен способ подключить различные их комбинации. Мой первоначальный подход состоял в том, чтобы иметь абстрактный класс, в котором все эти методы определены как чисто виртуальные, и любой конкретный класс должен был бы их реализовать. Если я хочу опробовать два GA, которые являются одинаковыми, но с разными перекрестными методами, например, мне придется создать абстрактный класс, который наследует от GeneticAlgorithm и реализует все методы, кроме перекрестного метода, а затем два конкретных класса которые наследуют от этого класса и реализуют только перекрестный метод. Недостатком этого является то, что каждый раз, когда я хочу поменять один или два метода, чтобы попробовать что-то новое, я должен создать один или несколько новых классов.

Есть ли другой подход, который мог бы лучше применить к этой проблеме?

Answer 1

Подход, который я использовал при реализации моей структуры GA, был следующим: Создайте следующие классы: поколение Генетический алгоритм GeneticAlgorithmAdapter GeneticAlgorithmParameters Население Индивидуальный

Хотя я не реализовывал шаблон стратегии для различных операций, я уверен, что было бы тривиально создавать различные реализации операций GA в качестве параметров в экземпляре GeneticAlgorithm.

Класс GeneticAlgorithm фиксирует основной алгоритм. Он на самом деле просто определяет различные этапы (создание популяции, индивидуальная рандомизация, отбор, кроссинговер, мутация и т. Д.) И управляет популяциями индивидов в процессе работы алгоритма. Я полагаю, что здесь вы можете подключить различные операции, если хотите.

Настоящая магия заключается в адаптере. Это то, что адаптирует проблемную область (ваши конкретные подклассы людей со всеми их соответствующими данными) к генетическому алгоритму. Я часто использую дженерики, чтобы конкретные типы населения, параметры и отдельные лица передавались в реализацию. Это дает мне intellisense и строгую проверку типа для реализации адаптера. Адаптер в основном должен определить, как выполнять конкретные операции для данных лиц (и их геномов). Например, вот интерфейс для адаптера:

/// <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 для различных проблемных областей, просто написав соответствующий адаптер. С точки зрения различных реализаций выбора, кроссовера или мутации адаптер может вызывать реализацию, которая ему интересна. Обычно я закомментирую различные идеи в адаптере, пока я исследую соответствующую стратегию.

Надеюсь, это поможет. Я могу дать больше указаний, где это необходимо. Трудно сделать дизайн справедливости, как это.

Answer 2

Несколько случайных битов с моей стороны:

• проект, который вы должны проверить (как подход): часовщик
• самая сложная часть построения ГА - найти разумное генетическое представление для вашей проблемы и построить фитнес-функции с хорошим распределением пригодность для данной популяции
• при работе с (m) любыми жесткими ограничениями вы можете подумать о введении класса Translator , который обрабатывает жесткие ограничения за счет (возможной) нежелательной ДНК и небольшой производительности

Answer 3

Я думаю, что вы слишком усложняете свой подход. Предлагаем вам скачать пакет GAlib . Даже если вы извлекаете документ только в формате html или pdf. Эти библиотеки существуют уже давно, и я уверен, что вы узнаете, как структурировать вашу библиотеку, посмотрев, как это было сделано в GAlib.

Answer 4

Я бы подходил к ГА как к совместной работе множества объектов, а не как одного большого класса, инкапсулирующего весь алгоритм. В принципе, вы можете иметь абстрактный класс для каждого большого точка вариации и конкретные классы для каждого варианта реализации, который вы хотите. Затем вы объединяете конкретные классы, которые вы хотите, во множество разновидностей GA.

Кроме того, вы можете ознакомиться с шаблоном стратегии: http://en.wikipedia.org/wiki/Strategy_pattern

Answer 5

Как говорят люди, не делайте это одним гигантским классом. Это было бы ужасно. Инкапсулировать поведение в разных классах. Стратегия - это решение.
Если вам нужны примеры, скачайте исходники и примеры JGAP . Он поддерживает генетическое программирование и генетические алгоритмы. Там вы увидите красивый красивый дизайн. Мутация, кроссовер, селекция, популяция, ген - все это отдельные классы. Вы просто настраиваете объект конфигурации, где вы инициируете определенные интерфейсы с реализациями, которые вы хотите использовать, передаете правильные параметры алгоритма и запускаете его. Пакет действительно огромный, хороший Javadoc, и вы всегда можете посмотреть в источнике или проверить почтовую группу для некоторых ответов. Когда я искал пакет GA, я видел GAlib и других, но я думаю, что этот наиболее полный с действительно хорошим дизайном.

Answer 6

ваша реализация выглядит как шаблон Decorator .