Как структурировать иерархию классов генетического алгоритма?
-
05-07-2019 - |
Вопрос
Я занимаюсь некоторой работой с генетическими алгоритмами и хочу написать свои собственные классы GA.Поскольку у GA могут быть разные способы проведения отбора, мутации, кроссинговера, генерации начальной популяции, вычисления пригодности и завершения алгоритма, мне нужен способ подключить различные их комбинации.Мой первоначальный подход состоял в том, чтобы создать абстрактный класс, в котором все эти методы были определены как чисто виртуальные, и любой конкретный класс должен был бы их реализовать.Например, если я хочу опробовать два одинаковых GAs, но с разными перекрестными методами, мне пришлось бы создать абстрактный класс, который наследуется от GeneticAlgorithm и реализует все методы, кроме перекрестного метода, затем два конкретных класса, которые наследуются от этого класса и реализуют только перекрестный метод.Недостатком этого является то, что каждый раз, когда я хочу поменять местами один или два метода, чтобы опробовать что-то новое, мне приходится создавать один или несколько новых классов.
Есть ли другой подход, который мог бы лучше применяться к этой проблеме?
Решение
Я бы подходил к ГА как к совместной работе множества объектов, а не как одного большого класса, инкапсулирующего весь алгоритм. В принципе, вы можете иметь абстрактный класс для каждого большого точка вариации и конкретные классы для каждого варианта реализации, который вы хотите. Затем вы объединяете конкретные классы, которые вы хотите, во многие разновидности GA.
Кроме того, вы можете ознакомиться с шаблоном стратегии: http://en.wikipedia.org/wiki/Strategy_pattern
Другие советы
Подход, который я использовал при реализации моей структуры 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 для различных проблемных областей, просто написав соответствующий адаптер. С точки зрения различных реализаций выбора, кроссовера или мутации адаптер может вызывать реализацию, которая ему интересна. Обычно я закомментирую различные идеи в адаптере, пока я исследую соответствующую стратегию.
Надеюсь, это поможет. Я могу дать больше указаний, где это необходимо. Трудно сделать дизайн справедливости, как это.
Я думаю, что вы слишком усложняете свой подход. Предлагаем вам загрузить пакет GAlib . Даже если вы извлекаете документ только в формате html или pdf. Эти библиотеки существуют уже давно, и я уверен, что вы узнаете, как структурировать вашу библиотеку, посмотрев, как это было сделано в GAlib. Р>
Несколько случайных фрагментов с моей стороны:
- проект, который вы должны проверить (в качестве подхода), - это часовщик
- самая сложная часть построения GAs - это найти разумное генетическое представление для вашей проблемы и создать фитнес-функции с хорошим распределением Фитнес для данной совокупности
- имея дело с (m) любыми жесткими ограничениями, вы могли бы подумать о введении Переводчик класс, который справляется с жесткими ограничениями ценой (возможной) нежелательной ДНК и небольшой производительности
ваша реализация выглядит как шаблон декоратора .
Как говорят люди, не делайте это одним гигантским классом. Это было бы ужасно. Инкапсулировать поведение в разных классах. Стратегия - это решение.
Если вам нужны примеры, загрузите источники и примеры JGAP . Он поддерживает генетическое программирование и генетические алгоритмы. Там вы увидите красивый красивый дизайн. Мутация, кроссовер, селекция, популяция, ген - все это отдельные классы. Вы просто настраиваете объект конфигурации, где вы инициируете определенные интерфейсы с реализациями, которые вы хотите использовать, передаете правильные параметры алгоритма и запускаете его. Пакет действительно огромный, хороший Javadoc, и вы всегда можете посмотреть в источнике или проверить почтовую группу для некоторых ответов. Когда я искал пакет GA, я видел GAlib и других, но я думаю, что этот наиболее полный с действительно хорошим дизайном. Р>