GeneticAlgorithm.h

Go to the documentation of this file.

/** @file GeneticAlgorithm.h
* @author Gabor Madl
* @date Created 08/2005
* @brief Genetic algorithm library.
*
*
* =================================================================
* DREAM License v2.0
* 
* DREAM - Distributed Real-time Embedded Analysis Method
* http://dre.sourceforge.net.
* Copyright (c) 2005-2007 Gabor Madl, All Rights Reserved.
* 
* This file is part of DREAM.
* 
* DREAM is free software; you can redistribute it and/or modify it
* under the terms of the GNU General Public License version 2 as
* published by the Free Software Foundation. No future versions of
* the GPL license may be automatically applied to DREAM. It is in
* the sole discretion of the copyright holder to determine whether
* DREAM may be released under a different license or terms. There
* are no restrictions on the use of DREAM for any purpose.
* 
* DREAM is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
* 
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
* MA 02110-1301, USA.
* 
* By submitting comments, suggestions, code, code snippets,
* techniques (including that of usage), and algorithms, submitters
* acknowledge that they have the right to do so, that any such
* submissions are given freely and unreservedly, and that they
* waive any claims to copyright or ownership. In addition,
* submitters acknowledge that any such submission might become
* part of the copyright maintained on the overall body of code,
* which comprises DREAM. By making a submission, submitter agrees
* to these terms. Furthermore, submitters acknowledge that the
* incorporation or modification of such submissions is entirely
* at the discretion of the moderators of the DREAM project.
* 
* DREAM links to the Libxml2 third party library. Please see 
* COPYING-libxml for the copyright information of Libxml2.
* =================================================================
*/

#ifndef DREAM_GENETICALGORITHM
#define DREAM_GENETICALGORITHM

#include "../core/System.h"

namespace DREAM
{

class Solution;
struct sort_solutions;
struct optimize_cpus;

/** Operator overloading for appending DREAM::Solution to std:string. */
std::string& operator<< (std::string& out, DREAM::Solution& solution);

/** A deterministic schedule for DREAM::System. */
class Solution
{

friend class GeneticOptimize;
friend class ModelCheck;
friend std::ostream& operator<< (std::ostream& out, DREAM::Solution& solution);
friend struct sort_solutions;

public:

        /** Creates a solution corresponding to the System.
        * @param system_ptr is the pointer to the System to be used to generate the Solution.
        */
        Solution (DREAM::System* system_ptr);

        /** Destructor. */
        virtual ~Solution ();

        /** Returns true if the schedule corresponding to the Schedule is deterministic. 
        * The function is conservative - it might return false for some deterministic systems but not the other way.
        * @return mostly true if the Solution is deterministic.
        */
        bool deterministic ();

        /** Calculates how good the current solution is.
        * @param verbose specifies whether simulation messages will be supressed or not.
        * @param deterministic specifies whether randomness is allowed.
        * @param endtoend updates the pointer's target with the end-to-end execution time of the model (unless the pointer is NULL).
        * @return the fitness.
        */
        virtual double fitness (bool verbose, bool deterministic, double* endtoend = NULL);

        /** Generates random solution for the System. */
        virtual void generate_priorities ()
#ifdef DREAM_ENHANCED_EXCEPTION_CHECKING
                throw (DREAM::Exception)
#endif
        ;

        /** Generates random solution for the System. */
        virtual void generate_subpriorities ()
#ifdef DREAM_ENHANCED_EXCEPTION_CHECKING
                throw (DREAM::Exception)
#endif
        ;

        /** Regenerates random solution. */
        virtual void regenerate_priorities ();

        /** Regenerates random solution. */
        virtual void regenerate_subpriorities ();

        /** Produces nice output from the Solution.
        * @param out is the message to be output.
        */
        void visitor (std::string& out);

protected:

        /** Flag which stores when the new task AVL tree copy is created. */
        bool copy_;

        /** Stores the fitness of the Solution. */
        double fitness_;

        /** Map storing all the Tasks in the System. */
        DREAM::TASK_AVLTREE task_avltree_;

        /** Pointer to the system */
        DREAM::System* system_ptr_;
};

/** Optimizes the scheduling of DREAM::System. */
class GeneticOptimize
{
public:
        /** Creates a genetic algorithm. */
        GeneticOptimize ();
        
        /** Destructor. */
        virtual ~GeneticOptimize () {};

        /** Single source mutation. 
        * @param solution is the solution to be mutated.
        */
        virtual void mutate (DREAM::Solution* solution) const;

        /** Mutation from two parents. 
        * @param father is one of the solution sources.
        * @param mother is the other solution source.
        * @param child is a pointer to the solution to be modified (it can be father or mother as well...).
        */
        virtual void mutate (DREAM::Solution* father, DREAM::Solution* mother, DREAM::Solution* child) const;

        /** Thread-level optimization of fixed-priority scheduling using genetic algorithms. 
        * We partition the solution space into 8 zones. One zone is reserved for the best solutions.
        * Three zones are reserved for mutations from parents. Two zones are reserved for single mutations.
        * Two zones are reserved for random generation only.
        * @param system_ptr is a pointer to the System.
        */
        virtual void thread_level (DREAM::System* system_ptr);

        /** CPU-level optimization of fixed-priority scheduling using genetic algorithms.
        * Optimizes both priorities and subpriorities.
        * We partition the solution space into 8 zones. One zone is reserved for the best solutions.
        * Three zones are reserved for mutations from parents. Two zones are reserved for single mutations.
        * Two zones are reserved for random generation only.
        * @param system_ptr is a pointer to the System.
        */
        virtual void CPU_level (DREAM::System* system_ptr);

protected:

        /** AVLTree that stores the potential solutions with their fitness as key. */
        std::vector<DREAM::Solution*> solution_vector_;

        /** Pointer to the system */
        DREAM::System* system_ptr_;
};

/** Used by genetic algorithms to sort solutions based on the fitness function. */
struct sort_solutions
{
        bool operator () (DREAM::Solution* solution1, DREAM::Solution* solution2)
        {
                return (solution1->fitness_ < solution2->fitness_);
        }
};

};

#endif

---