source: proiecte/GAIIA/GeneticOperators.cpp @ 122

#include "GeneticOperators.h"
#include "Genetic.h"
#include <time.h>
#include <stdio.h>
#include <stdlib.h>
#include <vector>

#define DEBUG 0

using namespace std;

/**
* the default constructor
*/
HyperMutation::HyperMutation(){

}

/**
* constructor
*
* @param t the graph of tasks
* @param prob the hyper-mutation probability
*/
HyperMutation::HyperMutation(TaskGraf &tgraf, double prob){
        tasks = tgraf;
        mutation_pb = prob; 
}

/**
* Method that increases the topological level of the current task, then analyzes its predecessors
in order to find if there is another free floating node to be moved in the floating nodes list; 
finally deletes the current node.
*
* @param ch the current chromosome
* @param task_id the current task id
*/
void HyperMutation::increaseTopoLvl(Chromosome &ch, int task_id){
        int i, j, free_fnode,level,nod, succ;
        tasks.noduri[task_id].niv_topo++;

        if (DEBUG == 1) ch.print();

        //each predecessor should be checked in order to decied if it becomes a free floating node 
        for (i = 0 ; i < tasks.noduri[task_id].nr_pred ; i++){
                nod  = ((Muchie *)(tasks.noduri[task_id].predecesori[i]))->predecesor->id;              
                level = tasks.noduri[nod].niv_topo;
                free_fnode = 1; 
                //the current node is a free node if all its successors have a current topological level grater with at least 2 units   
                for (j = 0 ; j < tasks.noduri[nod].nr_succ ; j++){
                        succ  = ((Muchie *)(tasks.noduri[nod].succesori[j]))->succesor->id;             
                        if ( tasks.noduri[succ].niv_topo <= level + 1){
                                free_fnode = 0;
                                break;
                        }
                }
                if (free_fnode == 1){
                        ch.f_nodes.push_back(nod);
                }

        }

        //check if the promoted node is still a free floating node 
        nod = task_id;
        level = tasks.noduri[nod].niv_topo;
        free_fnode = 1;         
        for (j = 0 ; j < tasks.noduri[nod].nr_succ ; j++){
                succ  = ((Muchie *)(tasks.noduri[nod].succesori[j]))->succesor->id;             
                if ( tasks.noduri[succ].niv_topo <= level + 1){
                        free_fnode = 0;
                        break;
                }
        }
        if (free_fnode == 1){
                ch.f_nodes.push_back(nod);
        }

        int gasit = 0, poz;
        for (i = 0 ; i < (int)ch.size() ; i++){
                if (gasit == 0) {
                        if (ch[i].task_index == task_id){
                                gasit = 1;
                                poz =  i ;
                                continue;                       
                        }               
                }else if (ch[i].level == ch[poz].level + 1 && ch[i-1].level == ch[poz].level){
                        ch[poz].level++;
                        Gene g = ch[poz];
                        ch[poz] = ch[i-1];
                        ch[i-1] = g;
                        break;  
                }
        }

        ch.init();
                
        if (DEBUG == 1){
                ch.print();
                for (i = 0 ; i < (int)ch.f_nodes.size() ; i++)
                        printf("%d ",ch.f_nodes[i]);
                printf("\n");
        }
}

/**
* method applying the hyper-mutation on a chromosome
*
* @param ch the chromosome we want to mutate
*/
void HyperMutation::mutateIndividual(Chromosome &ch){
        int i, poz, index ; 
        Gene g; 

        double rnd = (double)(rand() % 10000) / 10000;
        if (DEBUG == 1) printf("Pb = %lf < %lf \n",rnd,mutation_pb);
        if (rnd > mutation_pb){
                return ; 
        }
                
        ch.init();

        //mapping current chromosome on the task graph 
        for (i = 0 ; i < ch.size() ; i++){
                g = ch[i];              
                tasks.noduri[g.task_index].niv_topo = g.level; 
                tasks.noduri[g.task_index].procesor_id = g.proc_index;  
        }

        //choose which free floating node to process 
        
        if (DEBUG == 1)printf("FN_size = %d \n", ch.f_nodes.size());
        
        if (ch.f_nodes.size() == 0)
                return; 
        poz = rand() % ch.f_nodes.size();
                
        index = ch.f_nodes[poz];

        if (DEBUG == 1) printf("Poz = %d \n",index);

        ch.f_nodes.erase(ch.f_nodes.begin()+poz);

        increaseTopoLvl(ch, index);
        

}

/**
* method applying the hyper-mutation on a list of chromosomes
*
* @param pop the chromosomes list we want to mutate
*/
void HyperMutation::mutate(vector<Chromosome> &pop){
        //int i;
}

/**
* Method that applies the crossover on 2 parents obtaining 2 children
*
* @param p1 the parent #1
* @param p2 the parent #2
* @param c1 the child #1
* @param c2 the child #2
*/
void Crossover::crossover(Chromosome &p1, Chromosome &p2, Chromosome& c1, Chromosome& c2)
{
        //printf("Cross\n");
        c1.operator=(p1);
        c2.operator=(p2);
        int poz = rand() % (p1.genes.size() -1) + 1;
        if (DEBUG == 1) printf("poz = %i\n", poz);
        for(unsigned int i = poz ; i < p1.genes.size() ; i ++)
                c1[i].proc_index = p2[i].proc_index;
        for(unsigned int i = poz ; i < p1.genes.size() ; i ++)
                c2[i].proc_index = p1[i].proc_index;
        c1.init();
        c2.init();

        //c1.print();
        //c2.print();
        //printf("\n\n");
}

/**
* Method that applies the crossover on a list of chromosomes
*
* @param chs the list of chromosomes
*/
void Crossover::applyCrossover(vector<Chromosome> &chs)
{
        int nr = chs.size();
        if(nr % 2 != 0)
                nr--;
        Chromosome child1, child2;
        //for each chromosomes pair
        for(int i = 0 ; i < nr ; i +=2)
        {
                crossover(chs[i], chs[i+1], child1, child2);
                chs.push_back(child1);
                chs.push_back(child2);
                if (DEBUG == 1){
                        printf("parents:\n\t");
                        chs[i].print(); 
                        printf("\t");
                        chs[i+1].print();
                        printf("children:\n\t");
                        child1.print(); 
                        printf("\t");
                        child2.print();
                }
        }
}

/**
* constructor
*
* @param p the number of processors
* @param l the maximum topological level
* @param prob the simple mutation probability
*/
SimpleMutation::SimpleMutation(int p, int l, double pr)
{
        nr_procs = p;
        max_level = l;
        mutation_pb = pr;
        
}

/**
* method applying the simple mutation on a chromosome
*
* @param ch the chromosome we want to mutate
*/
void SimpleMutation::mutateIndividual(Chromosome & ch)
{
        
        //mutation probability
        int r = rand() % 100 ;
        if(r > mutation_pb * 100)
        {
              
                return;
        }
        ch.init();

        r = rand() % ch.genes.size();
        if (DEBUG == 1) printf("SM : poz = %i\n", r);
        int old = ch[r].proc_index;
        int nou;
        for(;;)
        {
                nou = rand() % nr_procs;
                if (DEBUG == 1) printf("SM : old = %i, nou = %i\n", old, nou);
                if(nou != old)
                        break;
        }
        ch[r].proc_index = nou;
}

typedef struct
{
        int level;
        int proc;
        int nr_genes;
} Assocs;

/**
* constructor
*
* @param p the number of processors
* @param l the maximum topological level
* @param prob the swap gene mutation probability
*/
SwapMutation::SwapMutation(int p, int l, double pr)
{
        nr_procs = p;
        max_level = l;
        mutation_pb = pr;
}

/**
* method applying the swap gene mutation on a chromosome
*
* @param ch the chromosome we want to mutate
*/
void SwapMutation::mutateIndividual(Chromosome & ch)
{       
        int crt=0, lev_crt = 1;
        Assocs * asoc = (Assocs*)calloc(nr_procs*(max_level-1),sizeof(Assocs));
        int * level_cnt = (int *)calloc(max_level, sizeof(int));
        int * procs_crt = (int*)calloc(nr_procs, sizeof(int));

        int r = rand() % 100 ;
        if(r > mutation_pb* 100)
                return;

        ch.init();
        
        for(int i = 0 ; i < (signed int)ch.genes.size() ; )
        {
                if(lev_crt == ch[i].level)
                {
                        level_cnt[lev_crt]++;
                        procs_crt[ch[i].proc_index]++;
                        i++;
                }
                else
                {
                        for(int j = 0 ; j < nr_procs ; j ++)
                        {
                                if(procs_crt[j] > 0)
                                {
                                        asoc[crt].level = lev_crt;
                                        asoc[crt].proc = j;
                                        asoc[crt].nr_genes = procs_crt[j];
                                        crt++;
                                }
                        }
                        procs_crt = (int*)calloc(nr_procs, sizeof(int));                                        
                        lev_crt ++;
                }
        }
        for(int j = 0 ; j < nr_procs ; j ++)
        {
                if(procs_crt[j] > 0)
                {
                        asoc[crt].level = lev_crt;
                        asoc[crt].proc = j;
                        asoc[crt].nr_genes = procs_crt[j];
                        crt++;
                }
        }
        for(int i = 0 ; i < crt ; )
        {
                if(asoc[i].nr_genes < 2)
                {               
                        asoc[i].level = asoc[crt-1].level;
                        asoc[i].proc = asoc[crt-1].proc;
                        asoc[i].nr_genes = asoc[crt-1].nr_genes;
                        crt--;
                }                       
                else    i++;
        }
        if(crt == 0)
        {
                if (DEBUG == 1) printf("no swap mutation\n");
                return;
        }
        int random = rand() % crt, count = asoc[random].nr_genes, c1 = rand() % count, c2;
        int start_poz = 0, good = 0, rc1, rc2;
        for(;;)
        {       
                c2 = rand() % count;
                if(c2 != c1) break;
        }
        for(int i = 0 ; i < asoc[random].level ; i ++)
                start_poz += level_cnt[i];
        for(int i = start_poz ; i < (int)ch.genes.size() ; i ++)
        {
                if(good == c1 && ch[i].proc_index == asoc[random].proc) rc1 = i;
                if(good == c2 && ch[i].proc_index == asoc[random].proc) rc2 = i;
                if(ch[i].proc_index == asoc[random].proc) 
                      good++;
        }
        int aux = ch[rc1].task_index;
        ch[rc1].task_index = ch[rc2].task_index;
        ch[rc2].task_index = aux;
        if (DEBUG == 1) printf("level = %i\n", ch[rc2].level);
        
}