GeneticAlgorithm.cpp

Go to the documentation of this file.

/** @file GeneticAlgorithm.cpp
* @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 the libxml software.
* =================================================================
*/

#include "GeneticAlgorithm.h"

namespace DREAM
{

std::ostream& operator<< (std::ostream& out, DREAM::Solution& solution)
{
        TASK_AVLTREE::iterator task_iter;
        out << "f:" << solution.fitness_;
        for (task_iter = solution.task_avltree_.begin (); 
                task_iter != solution.task_avltree_.end (); ++task_iter)
        {
                out << " " << task_iter->second->subpriority ();
        }
        out << "\n";
        return out;
}

/////////////////////////////////////////////////////////////////////////////
//
// Solution
//
/////////////////////////////////////////////////////////////////////////////

Solution::Solution (DREAM::System* system_ptr)
: copy_ (false)
{
        system_ptr_ = system_ptr;
        system_ptr->visitor_task_avltree (&task_avltree_);
}

Solution::~Solution ()
{
        if (copy_)
                task_avltree_.destroy ();
}

bool Solution::deterministic ()
{
        std::map<uint, uint> subpriority_map;
        std::map<uint, uint>::iterator uint_iter;
        TASK_AVLTREE::iterator task_iter;

        for (task_iter = task_avltree_.begin (); 
                task_iter != task_avltree_.end (); ++task_iter)
        {
                        uint_iter = subpriority_map.find (task_iter->second->subpriority ());
                        if (uint_iter != subpriority_map.end ())
                                return false;

                        subpriority_map.insert (std::pair<uint, uint> (task_iter->second->subpriority (), 0));
        }

        return true;
}

double Solution::fitness (bool verbose, bool deterministic, double* endtoend)
{
        double score = 0.0, priority_score, subpriority_score;
        DREAM::TASK_AVLTREE error_avltree;

        system_ptr_->visitor_update_task_avltree (&task_avltree_);
        system_ptr_->reset ();
        system_ptr_->simulate (verbose, deterministic, endtoend);

        system_ptr_->visitor_error_avltree (&error_avltree);
        
        if (error_avltree.empty ())
        {
                fitness_ = 0;
                return 0.0;
        }

        DREAM::TASK_AVLTREE::const_iterator error_iter;
        DREAM::Task* task_ptr;

        for (error_iter = error_avltree.begin (); error_iter != error_avltree.end (); error_iter++)
        {
                task_ptr = error_iter->second;
                priority_score = task_ptr->priority () + 1;
                subpriority_score = task_ptr->subpriority () + 1;
                
                score += (2 * (1/priority_score)) + (1/subpriority_score);
        }

        fitness_ = score;
        return score;
}

void Solution::generate_priorities ()
#ifdef DREAM_ENHANCED_EXCEPTION_CHECKING
        throw (DREAM::Exception)
#endif
{
        if (copy_)
        {
#ifdef DREAM_ENHANCED_EXCEPTION_CHECKING
                throw DREAM::Exception ("Solution::generate_priorities () may be called only once for a Solution.");
#else
                return;
#endif
        }

        // Create a new copy of the tasks
        copy_ = true;

        TASK_AVLTREE::iterator iter;

        for (iter = task_avltree_.begin (); iter != task_avltree_.end (); iter++)
        {
                iter->second = new DREAM::Task (*iter->second);
        }

        uint i = 0;

        // Assign subpriorities.
        for (iter = task_avltree_.begin (); iter != task_avltree_.end (); iter++)
        {
                iter->second->subpriority (i++);
        }

        regenerate_priorities ();
}

void Solution::generate_subpriorities ()
#ifdef DREAM_ENHANCED_EXCEPTION_CHECKING
        throw (DREAM::Exception)
#endif
{
        if (copy_)
        {
#ifdef DREAM_ENHANCED_EXCEPTION_CHECKING
                throw DREAM::Exception ("Solution::generate_priorities () may be called only once for a Solution.");
#else
                return;
#endif
        }

        // Create a new copy of the tasks
        copy_ = true;

        TASK_AVLTREE::iterator iter;

        for (iter = task_avltree_.begin (); iter != task_avltree_.end (); iter++)
        {
                iter->second = new DREAM::Task (*iter->second);
        }

        uint i = 0;

        // Assign subpriorities.
        for (iter = task_avltree_.begin (); iter != task_avltree_.end (); iter++)
        {
                iter->second->subpriority (i++);
        }

        regenerate_subpriorities ();
}

void Solution::regenerate_priorities ()
{
        // We need to manipulate both priorities and subpriorities
        // Generate random priorities - unlike sub-priorities, priorities are not expected to be unique
        // Iterator approach is a lot faster than looking up threads for tasks

        const DREAM::SCHEDULER_MAP* scheduler_map = system_ptr_->scheduler_map ();
        DREAM::SCHEDULER_MAP::const_iterator scheduler_iter;

        const DREAM::THREAD_MAP* thread_map;
        DREAM::THREAD_MAP::const_iterator thread_iter;
        DREAM::TASK_AVLTREE task_avltree;
        DREAM::TASK_AVLTREE::iterator task_iter;
        
        for (scheduler_iter = scheduler_map->begin (); scheduler_iter != scheduler_map->end (); scheduler_iter++)
        {
                thread_map = scheduler_iter->second->thread_map ();
                
                // We extract threads to an AVLTree to allow fast lookups when assigning random priorities
                // Reimplement this, not working
                DREAM::AVLTree<uint, const DREAM::Thread*> thread_avltree;

                for (thread_iter = thread_map->begin (); thread_iter != thread_map->end (); thread_iter++)
                {
                        thread_avltree.insert (thread_iter->first, thread_iter->second);
                }

                // Let's assign the random priorities...
                // Extract tasks for the current scheduler
                scheduler_iter->second->visitor_task_avltree (&task_avltree);

                for (task_iter = task_avltree.begin (); task_iter != task_avltree.end (); task_iter++)
                {
                        // Get random priority lane index
                        uint index = (uint) random (scheduler_iter->second->threadpoolsize ());
                
                        // Assign priority to tasks
                        task_iter->second->priority (task_avltree[index]->priority ());
                }
        }

        // Generate random subpriorities
        regenerate_subpriorities ();
}

void Solution::regenerate_subpriorities ()
{
        // Generate random but deterministic schedule efficiently
        for (uint i = 0; i < task_avltree_.size () - 1; i++)
        {
                uint rand = (uint) random (task_avltree_.size () - i) + i;
                uint subpriority_temp = task_avltree_[rand]->subpriority ();
                task_avltree_[rand]->subpriority (task_avltree_[i]->subpriority ());
                task_avltree_[i]->subpriority (subpriority_temp);               
        }

        fitness (false, true);
}

void Solution::visitor (std::string& out)
{
        TASK_AVLTREE::iterator task_iter;

        for (task_iter = task_avltree_.begin (); 
                task_iter != task_avltree_.end (); task_iter++)
        {
                out << "\tTask " << task_iter->second->id () << " p: " << task_iter->second->priority () << " sp: " << task_iter->second->subpriority () << "\n";
        }
        out << "Fitness: ";
        
        char number[double_size];
        snprintf (number, double_size, "%.8f", fitness_);
        out << number << "\n";
}

/////////////////////////////////////////////////////////////////////////////
//
// GeneticOptimize
//
/////////////////////////////////////////////////////////////////////////////

GeneticOptimize::GeneticOptimize ()
{
}

void GeneticOptimize::mutate (DREAM::Solution* solution) const
{
        // Generate random mutations with 30% probability - seems pretty good
        for (uint i = 0; i < solution->task_avltree_.size (); i++)
        {
                uint rand = (uint) random (solution->task_avltree_.size () - i) + i;

                if ((uint) random (2) == 0)
                {
                        uint subpriority_temp = solution->task_avltree_[rand]->subpriority ();
                        solution->task_avltree_[rand]->subpriority (solution->task_avltree_[i]->subpriority ());
                        solution->task_avltree_[i]->subpriority (subpriority_temp);             
                }
        }

        solution->fitness (false, true);
}

void GeneticOptimize::mutate (DREAM::Solution* father, DREAM::Solution* mother, DREAM::Solution* child) const
{
        uint i;
        for (i = 0; i < father->task_avltree_.size (); i++)
        {
                child->task_avltree_[i]->subpriority (father->task_avltree_[i]->subpriority ());
        }

        for (i = 0; i < child->task_avltree_.size (); i++)
        {
                bool swap = false;

                if (father->task_avltree_[i]->subpriority () == 
                        mother->task_avltree_[i]->subpriority ())
                {
                        // 10% - the value is probably correct...
                        if ((uint) random (9) == 0)
                                swap = true;
                }
                else
                {
                        // 62.5% - the value is probably incorrect...
                        if ((uint) random (7) > 2)
                                swap = true;
                }

                if (swap)
                {
                        // We swap the value with the one present in the mother
                        uint j;
                        for (j = 0; mother->task_avltree_[j]->subpriority () != 
                                                child->task_avltree_[i]->subpriority (); j++)
                        {
                                // We shouldn't get an infinite loop here
                        }

                        // Swap
                        uint subpriority_temp = child->task_avltree_[i]->subpriority ();
                        child->task_avltree_[i]->subpriority (child->task_avltree_[j]->subpriority ());
                        child->task_avltree_[j]->subpriority (subpriority_temp);                
                }
        }

        child->fitness (false, true);
}

void GeneticOptimize::thread_level (DREAM::System* system_ptr)
{
        if (Option::optimization_space_ < 8)
                Option::optimization_space_ = 8;
        bool perfect = false;
        time_t start_time;
        time (&start_time);

        std::cout << std::endl << "Thread-level scheduling optimization." << std::endl;

        // Initialize
        system_ptr_ = system_ptr;
        
        for (uint i = 0; i < Option::optimization_space_; i++)
        {
                DREAM::Solution* solution_ptr = new DREAM::Solution (system_ptr);
                solution_ptr->generate_subpriorities ();
                solution_vector_.push_back (solution_ptr);
        }

        std::sort (solution_vector_.begin (), solution_vector_.end ());

        uint e;
        for (e = 0; e < Option::number_of_repetitions_; e++)
        {
                uint i;

                for (i = ((uint) solution_vector_.size () / 8*3); i < ((uint) solution_vector_.size () / 4 * 3); i++)
                {
                        // Mutations from parents
                        uint father = (uint) random ((uint) solution_vector_.size () / 8 * 3);
                        uint mother = (uint) random ((uint) solution_vector_.size () / 8 * 3);
                        mutate (solution_vector_[father], solution_vector_[mother], solution_vector_[i]);
                }

                for (i = 1; i < ((uint) solution_vector_.size () / 8 * 3); i++)
                {
                        // Mutations from single sources
                        mutate (solution_vector_[i]);
                }

                for (i = ((uint) solution_vector_.size () / 4 * 3); i < solution_vector_.size (); i++)
                {
                        // Regenerations
                        solution_vector_[i]->regenerate_subpriorities ();
                }

/* This would show the whole design space.

                std::cout << "Solution:\n";
                for (i = 0; i < solution_vector_.size (); i++)
                {
                        if (i == ((uint) solution_vector_.size () / 8 * 3))
                                std::cout << "\n";
                        else if (i == ((uint) solution_vector_.size () / 4 * 3))
                                std::cout << "\n";

                        std::cout << *solution_vector_[i];
                }
                std::cout << std::endl;
*/
                std::sort (solution_vector_.begin (), solution_vector_.end (), sort_solutions ());

/* This would show the best solution for every iteration.
                std::cout << *solution_vector_[0];
*/

                if (solution_vector_[0]->fitness_ == 0.0)
                {
                        perfect = true;
                        break;
                }
        }

        if (perfect)
        std::cout << "Optimal solution found in " 
                << e << " iterations with optimization space "
                << Option::optimization_space_ << ".\n";
        else
        std::cout << "Solution found in " 
                << e << " iterations with optimization space "
                << Option::optimization_space_ << ".\n";

        std::string message;
        solution_vector_[0]->visitor (message);

        // solution_vector_[0] contains the best solution, let's update the system...
        system_ptr_->visitor_update_task_avltree (&solution_vector_[0]->task_avltree_);
        system_ptr_->reset ();

        // Delete optimization space
        std::for_each (solution_vector_.begin (), solution_vector_.end (), delete_object ());

        solution_vector_.clear ();

        time_t end_time;
        time (&end_time);
        uint perf = end_time - start_time;
        std::cout << message << "\nEnd of priority assignment optimization." << std::endl
                << "Analysis time: " << perf << " seconds." << std::endl;
}

void GeneticOptimize::CPU_level (DREAM::System* system_ptr)
{
        if (Option::optimization_space_ < 8)
                Option::optimization_space_ = 8;
        bool perfect = false;
        time_t start_time;
        time (&start_time);

        std::cout << std::endl << "CPU-level scheduling optimization started." << std::endl;

        // Initialize
        system_ptr_ = system_ptr;
        
        for (uint i = 0; i < Option::optimization_space_; i++)
        {
                DREAM::Solution* solution_ptr = new DREAM::Solution (system_ptr);
                solution_ptr->generate_subpriorities ();
                solution_vector_.push_back (solution_ptr);
        }

        std::sort (solution_vector_.begin (), solution_vector_.end ());

        uint e;
        for (e = 0; e < Option::number_of_repetitions_; e++)
        {
                uint i;

                for (i = ((uint) solution_vector_.size () / 8*3); i < ((uint) solution_vector_.size () / 4 * 3); i++)
                {
                        // Mutations from parents
                        uint father = (uint) random ((uint) solution_vector_.size () / 8 * 3);
                        uint mother = (uint) random ((uint) solution_vector_.size () / 8 * 3);
                        mutate (solution_vector_[father], solution_vector_[mother], solution_vector_[i]);
                }

                for (i = 1; i < ((uint) solution_vector_.size () / 8 * 3); i++)
                {
                        // Mutations from single sources
                        mutate (solution_vector_[i]);
                }

                for (i = ((uint) solution_vector_.size () / 4 * 3); i < solution_vector_.size (); i++)
                {
                        // Regenerations
                        solution_vector_[i]->regenerate_subpriorities ();
                }

/* This would show the whole design space.

                std::cout << "Solution:\n";
                for (i = 0; i < solution_vector_.size (); i++)
                {
                        if (i == ((uint) solution_vector_.size () / 8 * 3))
                                std::cout << "\n";
                        else if (i == ((uint) solution_vector_.size () / 4 * 3))
                                std::cout << "\n";

                        std::cout << *solution_vector_[i];
                }
                std::cout << std::endl;
*/
                std::sort (solution_vector_.begin (), solution_vector_.end (), sort_solutions ());

/* This would show the best solution for every iteration.
                std::cout << *solution_vector_[0];
*/

                if (solution_vector_[0]->fitness_ == 0.0)
                {
                        perfect = true;
                        break;
                }
        }

        if (perfect)
        std::cout << "Optimal solution found in " 
                << e << " iterations with optimization space "
                << Option::optimization_space_ << ".\n";
        else
        std::cout << "Solution found in " 
                << e << " iterations with optimization space "
                << Option::optimization_space_ << ".\n";

        std::string message;
        solution_vector_[0]->visitor (message);

        // solution_vector_[0] contains the best solution, let's update the system...
        system_ptr_->visitor_update_task_avltree (&solution_vector_[0]->task_avltree_);
        system_ptr_->reset ();

        // Delete optimization space
        std::for_each (solution_vector_.begin (), solution_vector_.end (), delete_object ());

        solution_vector_.clear ();

        time_t end_time;
        time (&end_time);
        uint perf = end_time - start_time;
        std::cout << message << "\nEnd of priority assignment optimization." << std::endl
                << "Analysis time: " << perf << " seconds." << std::endl;
}

};

---