-
Notifications
You must be signed in to change notification settings - Fork 0
/
WWO_RS.py
154 lines (145 loc) · 6.57 KB
/
WWO_RS.py
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
from testParameters import *
from BinPacking import BinPacking
from random import randint, gauss,shuffle,random
import copy
import math
import numpy as np
import time
def converterBP2WWO(solution:BinPacking):
length_dimension_list = [solution.max_weight] * len(solution.bin_list)
item_weight_list=[]
position_list = []
for bin_index in range(len(solution.bin_list)):
i=0
for item_exist in solution.bin_list[bin_index] :
if item_exist==1:
position_list.append(bin_index)
item_weight_list.append(solution.item_weight_list[i])
i+=1
return position_list, length_dimension_list,item_weight_list
class WaterWaveOptimizer:
def __init__(self, solutions: list[BinPacking],temperature = 50,alpha_temp=0.8):
self.solutions = solutions
self.alpha_temp = alpha_temp
self.temperature = temperature
class Wave:
def __init__(self, problem: BinPacking, converter=converterBP2WWO, wave_height=10, wave_length=0.5,alpha=1.01,beta=1.01):
self.problem = problem
self.position_list, self.length_dimension_list, self.item_weight_list = converter(problem)
self.height = wave_height
self.length = wave_length
self.alpha =alpha
self.beta = beta
self.sol_opt = None
def is_feasible(self):
bins = {}
for position, weight in zip(self.position_list, self.item_weight_list):
if position in bins:
bins[position] += weight
else:
bins[position] = weight
for bin_index, bin_weight in bins.items():
if bin_weight > self.problem.max_weight:
return False
return True
def fitness(self):
return self.problem.number_of_items-len(set(self.position_list))
def propagate_wave(self):
x_new = self.copy()
for d in range(len(self.position_list)):
x_new.position_list[d] = int(self.position_list[d] + randint(-1, 1) * self.length_dimension_list[d] * self.length)
if x_new.position_list[d] > x_new.length_dimension_list[d] or x_new.position_list[d] < 0:
x_new.position_list[d] = int(randint(0, x_new.length_dimension_list[d]))
if x_new.is_feasible():
return x_new
else:
return self
"""
def refract_wave(self):
x_new = self.copy()
for d in range(len(self.position_list)):
x_new.position_list[d] = gauss(0, 1)
x_new.height = self.wave_height
"""
def break_wave(self):
x_new = self.copy()
for d in range(len(self.position_list)):
x_new.position_list[d] =int(self.position_list[d] + gauss(0, 4) * self.beta * len(self.position_list))%self.problem.number_of_items
if x_new.is_feasible():
return x_new
else:
return self
def update_wave_length(self):
fmin = sum(self.item_weight_list)/self.problem.max_weight
fmax = self.problem.number_of_items
self.length = self.length * self.alpha**(-(self.fitness() + fmin) / (fmax - fmin))
def copy(self):
new_wave = copy.deepcopy(self)
return new_wave
def print_wave(self):
bins = {}
for position, weight in zip(self.position_list, self.item_weight_list):
if position in bins:
bins[position].append(weight)
else:
bins[position] = [weight]
# print("Wave Details:")
# for bin_index, item_weights in bins.items():
# print("Bin{}:".format(bin_index))
# print(", ".join(str(weight) for weight in item_weights))
# print("Position List:", self.position_list)
# print("item weights :",self.item_weight_list)
# print("Length Dimension List:", self.length_dimension_list)
# print("Height:", self.height)
# print("Length:", self.length)
# print("fitness : ",self.problem.number_of_items - self.fitness())
# print("--------------------------------------")
return self.problem.number_of_items - self.fitness(),bins
def generate_waves(self) -> list[Wave]:
waves=[]
for solution in self.solutions:
waves.append(self.Wave(problem=solution))
return waves
def optimize(self, max_iteration):
i = 0
population = self.generate_waves()
self.sol_opt = min(population, key=lambda x: x.fitness())
while i < max_iteration:
for x_index in range(len(population)):
x_new = population[x_index].propagate_wave()
if x_new.fitness() - population[x_index].fitness() > 0:
if x_new.fitness() > self.sol_opt.fitness():
#x_new.break_wave()
self.sol_opt = x_new
population[x_index] = x_new
else:
"""
instead of refracting the waves
x.height -= 1
if x.height == 0:
x_new = x.refract_wave()
"""
u = random()
if u > math.e**((x_new.fitness() - population[x_index].fitness())/self.temperature):
population[x_index] = x_new
self.temperature=self.temperature*self.alpha_temp
population[x_index].update_wave_length()
i += 1
# print("iteration : ",i)
return self.sol_opt.print_wave()
def H_WWO_RS(benchmarkFileName):
with open(benchmarkFileName, "r") as file:
array = [int(x) for x in file.read().split()]
# shuffle(array) # without order
bin_packing_instance1= BinPacking(len(array), array, bin_size)
bin_packing_instance1.first_fit()
bin_packing_instance2 = BinPacking(len(array), array, bin_size)
bin_packing_instance2.best_fit()
bin_packing_instance3 = BinPacking(len(array), array, bin_size)
bin_packing_instance3.next_fit()
start_time = time.time()
optimizer = WaterWaveOptimizer([bin_packing_instance1,bin_packing_instance2,bin_packing_instance3])
sol_optimal,solution_bins = optimizer.optimize(100)
stop_time = time.time()
elapsed_time = stop_time - start_time
return elapsed_time,sol_optimal,solution_bins