IntelligentAlgorithmScheduler/ChaosReproducePSO.py at master · Sherryran08/IntelligentAlgorithmScheduler · 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
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
# -*- coding: utf-8 -*-
# @Author : ZhaoKe
# @Time : 2021-04-22 11:35
import numpy as np
from utils.functions import logistic_function
from utils.Entities import Cloudlet, VM, calculate_fitness
from utils.AlgorithmEntities import DParticle
from matplotlib import pyplot as plt


class ChaosReproductionPSO:
    def __init__(self, cloudlets, vms, population_number=1000, times=500, w=0.95, c1=2, c2=2):
        self.cloudlets = cloudlets
        self.vms = vms
        self.population_number = population_number  # 种群数量
        self.times = times  # 遗传代数
        self.w = w
        self.c1 = c1
        self.c2 = c2
        self.vmax = 5

        self.cloudlet_num = len(cloudlets)  # 任务数量也就是粒子长度
        self.machine_number = len(vms)  # 机器数量

        self.particles = list()  # Set[Gene]类型
        self.gbest = None
        self.sigma = 2
        self.chaosNum = 20

    def init_population(self):
        for _ in range(self.population_number):
            size = self.cloudlet_num
            p = DParticle(size)
            p.solution = np.random.randint(0, self.machine_number, size=self.cloudlet_num)
            p.velocity = -5 + 10 * np.random.rand(self.cloudlet_num)
            p.fitness = calculate_fitness(p.solution, self.cloudlets, self.vms)
            self.particles.append(p)

    def find_best(self):
        best_score = 0
        best_particle = None
        for p in self.particles:
            score = calculate_fitness(p.solution, self.cloudlets, self.vms)
            if score > best_score:
                best_score = score
                best_particle = p
        return best_particle

    def update_velocity(self, p: DParticle, lb: DParticle, gb: DParticle):
        E1 = np.array([np.random.random() for _ in range(self.cloudlet_num)])  # [0.1, 0.2, 0.002, 0.4, ...]
        E2 = np.array([np.random.random() for _ in range(self.cloudlet_num)])
        v1 = np.array(gb.solution) - np.array(p.solution)
        v2 = np.array(lb.solution) - np.array(p.solution)
        velocity = self.c1 * E1 * v1 + self.c2 * E2 * v2
        velocity = np.clip(velocity, -self.vmax, self.vmax)
        p.velocity = p.velocity * self.w + velocity

    # 复指一段序列
    def update_position_copy1(self, p: DParticle, b: DParticle, flag: int):
        # 复制0.8即可
        if flag == 1:
            le = int(self.cloudlet_num * 0.7)
            start = np.random.randint(0, self.cloudlet_num)
            for i in range(start, start + le):
                p.solution[i % self.cloudlet_num] = b.solution[i % self.cloudlet_num]
        if flag == 2:
            le = int(self.cloudlet_num * 0.4)
            start = np.random.randint(0, self.cloudlet_num)
            for i in range(start, start + le):
                p.solution[i % self.cloudlet_num] = b.solution[i % self.cloudlet_num]

    # 更新坐标
    def update_position(self, p: DParticle):
        p.solution = np.abs(p.solution + p.velocity)
        for t in range(len(self.cloudlets)):
            if p.solution[t] > self.machine_number:
                p.solution[t] = np.ceil(p.solution[t]) % self.machine_number
        p.solution = list(map(int, p.solution))

    # 获得一组混沌序列
    def getSeries(self, v0):
        tempSet = [[0] * self.cloudlet_num] * 30
        tempSet[0] = [x / self.machine_number for x in v0]
        for i in range(1, 30):
            tempSet[i] = [x for x in logistic_function(tempSet[i - 1], 3.5)]
        for i in range(30):
            tempSet[i] = [int(self.machine_number * x) for x in tempSet[i]]
        # print(tempSet)
        tempFit = []
        for i in range(30):
            tempFit.append(calculate_fitness(tempSet[i], self.cloudlets, self.vms))
        best_score = 0
        best_solution = None
        for i in range(self.chaosNum):
            if tempFit[i] > best_score:
                best_score = tempFit[i]
                best_solution = tempSet[i]
        res = DParticle(self.cloudlet_num)
        res.velocity = self.gbest.velocity
        res.solution = best_solution
        res.fitness = best_score
        return res

    # 离散粒子群算法
    def exec(self):
        # 初始化基因，基因包含染色体和染色体的适应度
        self.init_population()
        self.gbest = self.find_best()
        lb = self.particles.pop()
        best_score = calculate_fitness(lb.solution, self.cloudlets, self.vms)
        global_best_score = calculate_fitness(self.gbest.solution, self.cloudlets, self.vms)
        results = []
        # 迭代过程 仅包含速度和位置的更新
        for t in range(self.times):
            # 升序排序
            self.particles.sort(key=lambda x: x.fitness)
            ind = 0
            for p in self.particles:
                if p is self.gbest:
                    continue
                if p is lb:
                    continue
                self.update_velocity(p, lb, self.gbest)
                self.update_position(p)
                if ind > self.population_number / 3 or ind < 2 / 3 * self.population_number:
                    self.update_position_copy1(p, lb, 2)
                else:
                    self.update_position_copy1(p, self.gbest, 1)
                ind += 1
                score = calculate_fitness(p.solution, self.cloudlets, self.vms)
                if score > best_score:
                    best_score = score
                    lb = p
                if score > global_best_score:
                    global_best_score = score
                    self.gbest = p
            tempGbest = self.getSeries(self.gbest.solution)
            if tempGbest.fitness > global_best_score:
                global_best_score = tempGbest.fitness
                self.gbest = tempGbest
            results.append(global_best_score)
            if t % 20 == 0:
                print("CRPSO iter: ", t, " / ", self.times, ", 适应度: ", global_best_score)
        # print(gb.solution)
        return results

    # 输出结果
    def schedule(self):
        # bpso = BPSO(self.cloudlets, self.vms, times=300)
        result = self.exec()
        # print("exec结果result：")
        # print(result)  # 打印出来是个引用，因为result是GeneEvaluation
        i = 0
        for _ in self.gbest.solution:
            print("任务:", i, " 放置到机器", self.vms[self.gbest.solution[i]].id + 1, "上执行")
            i += 1
        plt.plot(range(self.times), result)
        # plt.savefig('imgr2/BPOScheduler-0.95_2_2--vmax5-popu100-iter200-w095-cg2-cl2.png', dpi=300,
        #             format='png')  # bbox_inches="tight"解决X轴时间两个字不被保存的问题
        plt.show()


# if __name__ == '__main__':
#     # 测试数据
#     nodes = [
#         VM(0, 0.762, 2, 920, 2223, 400, 2000),
#         VM(1, 0.762, 2, 1200, 2223, 1000, 2000),
#         VM(2, 0.762, 2, 850, 2223, 800, 2000),
#         VM(3, 0.762, 2, 1200, 2223, 900, 2000),  # 4
#     ]
#     lets = [
#         Cloudlet(0.078400, 60.689797, 228.9767549846),
#         Cloudlet(0.065683, 185.848012, 187.97925024),
#         Cloudlet(0.050440, 96.030497, 206.7730432),
#         Cloudlet(0.104019, 131.428883, 218.785084),  # 4
#         Cloudlet(0.022355, 192.582491, 231.971066946),
#         Cloudlet(0.232862, 226.085299, 233.033953),
#         Cloudlet(0.194654, 77.503350, 190.415564374),
#         Cloudlet(0.148194, 241.349622, 264.54314854),  # 8
#         Cloudlet(0.146926, 199.978750, 248.2824453),
#         Cloudlet(0.081256, 149.824589, 243.1697191),
#         Cloudlet(0.237547, 141.050771, 277.0119905),
#         Cloudlet(0.138457, 139.508608, 271.25358),
#         Cloudlet(0.088451, 133.618232, 245.98392322),
#         Cloudlet(0.266167, 156.087665, 214.03950067748),
#         Cloudlet(0.130581, 158.033508, 251.2432088),
#         Cloudlet(0.099247, 211.409329, 197.8128878),  # 16
#         Cloudlet(0.124647, 259.696868, 245.596727694),
#         Cloudlet(0.076976, 186.666789, 277.3108057617),  # 18
#     ]
#     bpso = ChaosReproductionPSO(lets, nodes, times=150)
#     bpso.schedule()