Genetic-Algorithm/ga.py at main · purnachandraborado/Genetic-Algorithm · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
import heuristicsolution
import random


class GA:

    @classmethod
    def Create_intial_population(cls, Tasklist, VirtualmachineList, highWeightageVmlist, mediumWeightageVmlist, lowWeightageVmlist):
        # calculates initial population and returns the value
        initialPopulation = []
        print("Initial Population being generated......")
        initialPopulation.append(
            heuristicsolution.Heuristc.FCFS(Tasklist, VirtualmachineList))
        initialPopulation.append(
            heuristicsolution.Heuristc.SJF(Tasklist, VirtualmachineList))
        for i in range(5):
            initialPopulation.append(heuristicsolution.Heuristc.WMR(
                Tasklist, highWeightageVmlist, mediumWeightageVmlist, lowWeightageVmlist))
        for i in range(8):
            initialPopulation.append(
                heuristicsolution.Heuristc.PurelyRandom(Tasklist, VirtualmachineList))
        return initialPopulation

    @classmethod
    def FitnessOfPopulation(cls, initialPopulation):
        # returns the Fitness value of population
        for Chromosome in initialPopulation:
            completionTime = 0
            for key, value in Chromosome.items():
                completionTime = completionTime + \
                    (key.instructionlength/value.mips)
            Chromosome["Fitness_value"] = completionTime/len(Chromosome)
        return initialPopulation

    @classmethod
    def FitnessOfChromosome(cls, Chromosome):
        # returns the fitness value of Chromosome
        completionTime = 0
        for key, value in Chromosome.items():
            if(key != "Fitness_value"):
                completionTime = completionTime + \
                    (key.instructionlength/value.mips)
        Chromosome["Fitness_value"] = completionTime/len(Chromosome)
        return Chromosome

    @classmethod
    def Parent(cls, initialPopulation):
        # # returns the parentlist which is the last two min value form population on the basis of fitness value
        parentlist = []
        # lowest = intialPopulation[0]
        # # print("intial 0 ", intialPopulation[0])
        # lowest2 = None
        # for item in intialPopulation:
        #     if item["Fitness_value"] < lowest["Fitness_value"]:
        #         lowest2 = lowest
        #         lowest = item
        #     elif lowest2 == None or lowest2["Fitness_value"] > item["Fitness_value"]:
        #         lowest2 = item
        parent1 = random.choice(initialPopulation)
        parent2 = random.choice(initialPopulation)
        parentlist.append([initialPopulation.index(parent1), parent1])
        parentlist.append([initialPopulation.index(parent2), parent2])
        return parentlist

    @classmethod
    def GeneCompletionTime(cls, instructionlength, mips):
        return instructionlength/mips

    @classmethod
    def Crossover(cls, Bestparent, Notbestparent, noOfChecks):
        # calculates crossover
        #     offspring:dict
        #         stores offspring
        #     CompletionTimeparent:dict
        #         stores the copy of the best parent
        offspring = Bestparent
        CompletionTimeparent = Bestparent
        countChecks = 0
        for key, value in Bestparent.items():
            if(countChecks == noOfChecks):
                break
            if(random.choice([1, 0]) == 1):
                countChecks += 1
                # print(f"check number = {countChecks}")
                if(key != "Fitness_value"):
                    if(key.instructionlength/value.mips > key.instructionlength/Notbestparent[key].mips):
                        tempMips1 = value.mips
                        tempvm1 = value
                        tempMips2 = Notbestparent[key].mips
                        tempvm2 = Notbestparent[key]
                        #newCompletionTime1 = key.instructionlength/tempMips2
                        CompletionTimeparent[key] = tempvm2
                        #newVm = None
                        CompletionTimeReduced = False
                        for key1, value1 in Bestparent.items():
                            if(key1 != "Fitness_value"):
                                if(Bestparent[key1] == tempvm2):
                                    #newCompletionTime2 = key1.instructionlength/tempMips1
                                    CompletionTimeparent[key1] = tempvm1
                                    CompletionTimeparent = cls.FitnessOfChromosome(
                                        CompletionTimeparent)
                                    if(CompletionTimeparent["Fitness_value"] < offspring["Fitness_value"]):
                                        CompletionTimeReduced = True
                                        break
                                    else:
                                        CompletionTimeparent[key1] = tempvm2

                        if(CompletionTimeReduced == True):
                            offspring = CompletionTimeparent
                        else:
                            CompletionTimeparent = offspring
        return offspring

    @classmethod
    def Mutation(cls, offspring, noOfSwaps):
        # Mutation :
        #     Mutation is performed in noOfSwaps times
        tempOffSpring = offspring
        for i in range(noOfSwaps):
            key1 = random.choice(list(tempOffSpring.keys()))
            key2 = random.choice(list(tempOffSpring.keys()))

            if (key1 != key2 and key1 != 'Fitness_value' and key2 != 'Fitness_value'):
                tempOffSpring[key1], tempOffSpring[key2] = tempOffSpring[key2], tempOffSpring[key1]
                tempOffSpring = cls.FitnessOfChromosome(tempOffSpring)
                if tempOffSpring['Fitness_value'] < offspring['Fitness_value']:
                    offspring = tempOffSpring
                    offspring = cls.FitnessOfChromosome(offspring)
                else:
                    tempOffSpring[key1], tempOffSpring[key2] = tempOffSpring[key2], tempOffSpring[key1]
                    tempOffSpring = cls.FitnessOfChromosome(tempOffSpring)
            else:
                noOfSwaps += 1
        return offspring

    @classmethod
    def SimulatedAnnealing(cls, mutatedOffspring, previousfitness):
        # SimulatedAnnealing:
        #     return a boolean value
        if(mutatedOffspring["Fitness_value"] < previousfitness):
            return True
        elif (random.choice([True, False]) == True):
            return True
        else:
            return False

    @classmethod
    def SurvivalSelection(cls, initialPopulation):
        # SurvivalSelection:
        #     deletes the highest Fitness Chromosome
        highest = initialPopulation[0]
        for item in initialPopulation:
            if item["Fitness_value"] > highest["Fitness_value"]:
                highest = item
        print(
            f"\nRemoved Chromosome number is {initialPopulation.index(highest)+1}\n")
        initialPopulation.remove(highest)
        return initialPopulation

    @classmethod
    def BestOffspring(cls, initialPopulation):
        # returns the Chromosome which have minimum fitness value
        lowest = initialPopulation[0]
        for item in initialPopulation:
            if item["Fitness_value"] < lowest["Fitness_value"]:
                lowest = item

        return ([initialPopulation.index(lowest), lowest])