Wie ein genetischer Algorithmus Klassenhierarchie zu strukturieren?

Question

Ich mache einige Arbeit mit genetischen Algorithmen und möchte meine eigenen GA Klassen schreiben. Da ein GA verschiedene Arten tun Selektion, Mutation, cross-over haben kann, eine anfängliche Population zu erzeugen, Fitness-Berechnung, und der Algorithmus endet, ich brauche eine Art und Weise in verschiedenen Kombinationen von diesen zu verstopfen. Mein erster Ansatz war eine abstrakte Klasse zu haben, die als reine virtuelle definiert alle diese Methoden hatten, und jede konkrete Klasse würde sie umsetzen müssen. Wenn ich zwei Gase ausprobieren mag, die gleich sind, aber mit unterschiedlichem Cross-Over-Verfahren zum Beispiel, würde ich muß eine abstrakte Klasse machen, die von GeneticAlgorithm erbt und implementiert alle Methoden mit Ausnahme des Cross-Over-Verfahrens, dann zwei konkrete Klassen dass von dieser Klasse erben und nur die Cross-over-Methode implementieren. Der Nachteil ist, dass jedes Mal, wenn ich will eine Methode oder zwei auszutauschen, um etwas Neues auszuprobieren Ich habe ein oder mehr neue Klassen zu machen.

Gibt es einen anderen Ansatz, um dieses Problem besser zutreffen könnte?

Answer 1

Ich würde die GA als eine Zusammenarbeit von vielen Objekten nähert, anstatt eine große Klasse den ganzen Algorithmus eingekapselt wird. Grundsätzlich könnte man eine abstrakte Klasse für jeden großen haben Variationspunkt und konkrete Klassen für jede Implementierung Wahl, die Sie wollen. Sie dann die konkreten Klassen kombinieren Sie in vielen Sorten von GA wollen.

Auch sollten Sie sich mit der Strategie-Muster vertraut zu machen: http://en.wikipedia.org/wiki/Strategy_pattern

Answer 2

Der Ansatz, den ich nahm, als mein GA Rahmen der Umsetzung war wie folgt: Erstellen Sie die folgenden Klassen: Generation Genetischen Algorithmus GeneticAlgorithmAdapter GeneticAlgorithmParameters Population Einzelne

Auch wenn ich nicht das Strategie-Muster für die verschiedenen Operationen umgesetzt hätte, ich bin sicher, dass es trivial sein würde verschiedenes GA Betrieb Implementierungen als Parameter auf der GeneticAlgorithm Instanz zu erstellen.

Die GeneticAlgorithm Klasse fängt den Basisalgorithmus. Es definiert wirklich nur die verschiedenen Schritte (Bevölkerung Erstellung, individuelle Randomisierung, Auswahl, cross-over, Mutation, etc.) und verwaltet die Populationen von Individuen wie der Algorithmus läuft. Ich stelle mir hier, dass Sie in verschiedenen Operationen stecken könnte, wenn man wollte.

Die eigentliche Magie liegt in dem Adapter. Dies ist, was das Problem Domain (spezifische Unterklassen der Individuen, mit allen ihren relevanten Daten) passt sich dem genetischen Algorithmus. Ich benutze Generika hier viel, so dass die spezifischen Arten der Bevölkerung, Parameter und Einzelpersonen in die Umsetzung übergeben werden. Das gibt mir Intellisense und stark-Typen für die Umsetzung des Adapters zu prüfen. Der Adapter muss grundsätzlich definieren, wie die spezifischen Operationen für die angegebenen Personen durchzuführen (und ihre Genome). Zum Beispiel, hier ist die Schnittstelle für den Adapter:

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

ich gefunden habe, dass dieser Ansatz gut funktioniert für mich, weil ich einfach die GA-Implementierung für unterschiedliche Problembereiche wiederverwenden kann, nur den entsprechenden Adapter zu schreiben werden. In Bezug auf die verschiedenen Auswahl, Cross-Over oder Mutation Implementierungen kann der Adapter die Implementierung aufrufen, dass sie interessiert ist. Was ich normalerweise tun ist, verschiedene Ideen in den Adapter kommentieren, während ich eine geeignete Strategie untersuche.

Hoffe, das hilft. Ich kann mehr Orientierung bei Bedarf geben. Es ist schwer, das Design Gerechtigkeit wie dies zu tun.

Answer 3

Ich glaube, Sie sind über die Dinge in Ihrem Ansatz zu verkomplizieren. Schlagen Sie den Download der GALib Paket. Auch wenn Sie ziehen nur die doc in HTML oder PDF-Format. Diese Libs haben schon seit einer Weile, und ich bin reale sicher, dass Sie lernen, wie Sie Ihre lib strukturieren von der Suche, wie man in diesem GALib geschehen.

Answer 4

Einige Zufallsbits von meinem Teil:

• ein Projekt, das Sie (als Ansatz) sollten überprüfen, ist Uhrmacher
• der schwierigste Teil GAs des Gebäudes ist eine vernünftige genetische Darstellung für Ihr Problem zu finden und eine Fitness-Funktionen mit einer guten Verteilung von Aufbau Fitness für eine bestimmte Population
• , wenn sie mit (m) allen harten Beschränkungen handelt, können Sie einen Übersetzer über die Einführung Klasse Wich behandelt die harten Beschränkungen, auf Kosten der (möglichen) Junk-DNA und ein wenig Leistung einfiel

Answer 5

Ihre Implementierung sieht aus wie ein Dekorierermuster rel="nofollow.

Answer 6

Wie die Leute sagen, macht es nicht eine riesige Klasse. Das wäre schrecklich. Kapseln Verhalten in verschiedenen Klassen. Strategie ist eine Lösung.
Wenn Sie Beispiele benötigen downloaden Quellen und Beispiele für JGAP . Es hat Unterstützung für Genetic Programming und Genetische Algorithmen. Sie werden dort schön schönes Design sehen. Mutation, Crossover, Selection, Bevölkerung, Gene - all dies sind separate Klassen. Sie haben soeben Setup Configuration-Objekt, wo Sie definierte Schnittstellen mit Implementierungen initiieren Sie verwenden möchten, übergeben richtigen Algorithmus-Parameter und Sie es ausführen. Wirklich Paket ist riesig, javadoc schön, und man kann immer in die Quelle aussieht oder Mail-Gruppe für einige Antworten überprüfen. Als ich für GA-Paket suche, sah ich GALib und andere, aber ich denke, das mit wirklich schönen Design vollständigste ist.