Como estruturar uma hierarquia de classe Algoritmo Genético?

Question

Eu estou fazendo algum trabalho com algoritmos genéticos e quero escrever minhas próprias classes GA. Desde a GA pode ter diferentes maneiras de fazer a seleção, mutação, cross-over, gerando uma população inicial, calcular fitness, e que encerra o algoritmo, eu preciso de uma maneira de conectar diferentes combinações destes. Minha abordagem inicial era ter uma classe abstrata que tinha todos esses métodos definidos como puro virtual, e qualquer classe concreta teria de implementá-las. Se eu quiser experimentar dois gás que são os mesmos, mas com diferentes cross-over métodos, por exemplo, eu teria que fazer uma classe abstrata que herda de GeneticAlgorithm e implementa todos os métodos, exceto os cross-over método, então duas classes concretas que herdam essa classe e só implementar o método cross-over. A desvantagem para isso é que cada vez que eu quiser trocar um ou dois métodos para experimentar algo novo que eu tenho que fazer uma ou mais novas classes.

Existe uma outra abordagem que pode aplicar melhor para este problema?

Answer 1

Gostaria de abordar o GA como uma colaboração de muitos objetos, em vez de uma grande classe encapsular o algoritmo inteiro. Basicamente, você poderia ter uma classe abstrata para cada grande ponto de variação e classes concretas para cada escolha de implementação que você deseja. Você, então, combinar as classes concretas que você quer em muitas variedades de GA.

Além disso, você pode querer se familiarizar com o padrão de estratégia: http://en.wikipedia.org/wiki/Strategy_pattern

Answer 2

A abordagem que levou ao implementar o meu quadro GA foi a seguinte: Criar as seguintes classes: Geração Algoritmo genético GeneticAlgorithmAdapter GeneticAlgorithmParameters População Individual

Embora eu não implementar o padrão de estratégia para as várias operações, tenho a certeza que seria trivial para criar várias implementações de operação GA como parâmetros na instância GeneticAlgorithm.

A classe GeneticAlgorithm capta o algoritmo básico. Realmente só define as várias etapas (criação populacional, randomização indivíduo, seleção, cross-over, mutação, etc) e gere as populações de indivíduos como o algoritmo é executado. Imagino que aqui você pode ligar em diferentes operações, se você quisesse.

As verdadeiras mentiras mágicas no adaptador. Isto é o que se adapta o domínio do problema (seus sub classes específicas dos indivíduos, com toda a sua dados relevantes) para o algoritmo genético. Eu uso de genéricos muito aqui para que os tipos específicos da população, parâmetros e indivíduos são passados ??para a implementação. Isso me dá intellisense e tipo forte verificando a implementação do adaptador. O adaptador basicamente necessita para definir a forma de executar as operações específicas para os indivíduos referidos (e seus genomas). Por exemplo, aqui é a interface para o adaptador:

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

Eu descobri que esta abordagem funciona bem para mim, porque eu posso facilmente reutilizar a implementação GA para domínios de problemas diferentes, apenas estar escrevendo o adaptador apropriado. Em termos de seleção diferente, cross-over ou mutação implementações, o adaptador pode chamar a implementação de que está interessado. O que eu normalmente fazer é comentar a diferentes ideias no adaptador enquanto eu estou investigando uma estratégia adequada.

Espero que isso ajude. Eu posso dar mais orientação sempre que necessário. É difícil fazer justiça ao projeto como este.

Answer 3

Eu acho que você tem mais de complicar as coisas na sua abordagem. Sugiro que você baixar o href="http://lancet.mit.edu/ga/" rel="nofollow noreferrer"> pacote . Mesmo que você só puxar o doc em HTML ou PDF. Estas bibliotecas foram em torno de um tempo e eu sou real certeza de que você vai aprender como estruturar sua lib de olhar como é que tem sido feito em GAlib.

Answer 4

Alguns bits aleatórios de minha parte:

• um projeto que você deve verificar se (como uma abordagem) é relojoeiro
• a parte mais difícil de construir AGs é encontrar uma representação genética sensata para o seu problema e construir uma série de funções de fitness com uma boa distribuição de aptidão para uma dada população
• quando se lida com (m) quaisquer restrições duras, você poderia pensar sobre a introdução de um Tradutor classe wich lida com as restrições duras, ao custo de (possível) DNA lixo e um pouco de desempenho

Answer 5

sua aparência de implementação como um Decorator padrão .

Answer 6

Como as pessoas dizem, não torná-lo uma classe gigante. Isso seria horrível. comportamento Encapsulate em diferentes classes. Estratégia é uma solução.
Se você precisa de exemplos fontes de download e exemplos de JGAP . Tem suporte para programação genética e Algoritmos Genéticos. Você vai ver lá design agradável agradável. Mutação, Crossover, Seleção, População, Gene - tudo isto são classes separadas. Você acabou de configuração objecto de configuração, onde você inicia interfaces definidas com implementações que deseja usar, passar parâmetros do algoritmo adequadas e você executá-lo. Realmente pacote é enorme, javadoc agradável, e você pode sempre olhar para o grupo de correio de origem ou cheque de algumas respostas. Quando eu estava olhando para o pacote GA vi GAlib e outros, mas eu acho que este é mais completa com design muito bom.