-
Notifications
You must be signed in to change notification settings - Fork 0
/
ghs.py
63 lines (55 loc) · 2.2 KB
/
ghs.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
# Global Harmony Search
from dataclasses import dataclass
import numpy as np
from knapsack import Problem, Solution
@dataclass
class GHS:
problem: Problem
memory: np.ndarray
max_iterations: int
N: int
HMCR: float
PAR: float
def repair(self, cells: np.ndarray) -> Solution:
weight = self.problem.weigh(cells)
if weight > self.problem.capacity:
for i in np.random.permutation(np.arange(self.problem.size)):
if cells[i] == 1 and weight > self.problem.capacity:
cells[i] = 0
weight -= self.problem.weights[i]
else:
for i in np.random.permutation(np.arange(self.problem.size)):
if (
cells[i] == 0
and self.problem.weights[i] + weight <= self.problem.capacity
):
cells[i] = 1
weight += self.problem.weights[i]
fitness = self.problem.evaluate(cells)
return Solution(cells=cells, fitness=fitness, weight=weight)
def init_random_memory(self) -> None:
for i in range(self.N):
cells = np.random.randint(0, 2, self.problem.size)
self.memory[i] = self.repair(cells)
self.memory = np.array(sorted(self.memory, reverse=True))
def update_memory(self, solution):
if solution.fitness > self.memory[-1].fitness:
self.memory[-1] = solution
self.memory = np.array(sorted(self.memory, reverse=True))
def solve(self) -> Solution:
self.init_random_memory()
for _ in range(self.max_iterations):
cells = np.zeros(self.problem.size)
for j in range(self.problem.size):
rnd = np.random.uniform()
if rnd <= self.HMCR:
x = np.random.randint(self.N)
cells[j] = self.memory[x].cells[j]
rnd = np.random.uniform()
if rnd <= self.PAR:
cells[j] = self.memory[0].cells[j]
else:
cells[j] = np.random.randint(0, 2)
solution = self.repair(cells)
self.update_memory(solution)
return self.memory[0]