答：每個解對應的是一組權重，即子問題，紅點附近的四個點，也就是它的鄰居怎麼確定呢？由權重來確定，算法初始化階段就確定了每個權重對應的鄰居，也就是每個子問題的鄰居子問題。權重的鄰居通過歐式距離來判斷。取最近的幾個。
https://blog.csdn.net/Twobox/p/16408751.html
https://www.zhihu.com/question/263555181?sort=created其中兩個回答都挺好的
1. 輸入N m
# N表示取點密度 m表示問題維度
1.1 輸入 T
# 表示取最近的T個作為鄰居
2. 生成均勻分布權重向量
2.1 計算每個權重向量之間的歐拉距離
3. 權重向量個數即為：初始種群個數
4. 初始化種群，每個個體一一對應權重
4.1 更具權重之間距離，取前T個作為鄰居person
5. EP = 空
# 維護成最優前沿
6. 計算最初的全局最優Z
# 把每個帶入f1 f2中，取最小值 z1 z2
7. 開始循環N代
7.1對於每個個體，在領域中選取2個個體進行交叉變異，獲得2個新個體
7.1.1更新全局解z
7.2在領域中隨機選擇2個個體，用新個與舊個體進行對比
# 新個體帶入子目標問題，直接對比值即可
7.3如果更優，則替換舊個體dna
7.4更新EP
# 如果有別接收的新解，將新解與EP每一個進行比較，刪除被新解支配的，如果新解沒有被舊解支配，那麼加入EP
代碼實現設計
# 分析
需要維護的數據結構：
某個體最近的T位鄰居： 可以考慮采用對象列表即可
均勻分布的權重向量：一個二維ndarray數組即可
權重向量與個體對應關系：個體對象，直接保存權重向量數組
權重向量之間的距離矩陣：開局初始化，不變的
EP list,裡面的個體是對象的引用
z list
目標函數集合，F list domain list
# 接口設計
class Person
attribute:
dns：一維ndarray
weight\_vector: 一維ndarray
neighbor: list
o\_func:Objective\_Function 目標函數
function:
mutation
cross\_get\_two\_new\_dna：返回2段新dna
compare#與子代比較
accept\_new\_dna
choice\_two\_person:p1,p2
class Moead\_Util
attribute:
N
M
T:
o\_func：Objective\_Function
pm:變異概率
EP:[dna1,dna2,..]
weight\_vectors:二維數組
Euler\_distance:二維數組
pip\_size
Z:[] # 這裡面元素為一維ndarray數組，即dna，即解
function:
init\_mean\_vector:二維數組
init\_Euler\_distance:二維數組
init\_population:[]
init\_Z:一維屬豬
update\_ep
update\_Z
class Objective\_Function:
attribute:
F:[]
domain:[[0，1],[],[]]
function:
get\_one\_function:Objective\_Function
1 import numpy as np
2
3
4 class Person:
5 def \_\_init\_\_(self, dna):
6 self.dna = dna
7 self.weight\_vector = None
8 self.neighbor = None
9 self.o\_func = None # 目標函數
10
11 self.dns\_len = len(dna)
12
13 def set\_info(self, weight\_vector, neighbor, o\_func):
14 self.weight\_vector = weight\_vector
15 self.neighbor = neighbor
16 self.o\_func = o\_func# 目標函數
17
18 def mutation\_dna(self, one\_dna):
19 i = np.random.randint(0, self.dns\_len)
20 low = self.o\_func.domain[i][0]
21 high = self.o\_func.domain[i][1]
22 new\_v = np.random.rand() * (high - low) + low
23 one\_dna[i] = new\_v
24 return one\_dna
25
26 def mutation(self):
27 i = np.random.randint(0, self.dns\_len)
28 low = self.o\_func.domain[i][0]
29 high = self.o\_func.domain[i][1]
30 new\_v = np.random.rand() * (high - low) + low
31 self.dna[i] = new\_v
32
33 @staticmethod
34 def cross\_get\_two\_new\_dna(p1, p2):
35 # 單點交叉
36 cut\_i = np.random.randint(1, p1.dns\_len - 1)
37 dna1 = p1.dna.copy()
38 dna2 = p2.dna.copy()
39 temp = dna1[cut\_i:].copy()
40 dna1[cut\_i:] = dna2[cut\_i:]
41 dna2[cut\_i:] = temp
42 return dna1, dna2
43
44 def compare(self, son\_dna):
45 F = self.o\_func.f\_funcs
46 f\_x\_son\_dna = []
47 f\_x\_self = []
48 for f in F:
49 f\_x\_son\_dna.append(f(son\_dna))
50 f\_x\_self.append(f(self.dna))
51 fit\_son\_dna = np.array(f\_x\_son\_dna) * self.weight\_vector
52 fit\_self = np.array(f\_x\_self) * self.weight\_vector
53 return fit\_son\_dna.sum() - fit\_self.sum()
54
55 def accept\_new\_dna(self, new\_dna):
56 self.dna = new\_dna
57
58 def choice\_two\_person(self):
59 neighbor = self.neighbor
60 neighbor\_len = len(neighbor)
61 idx = np.random.randint(0, neighbor\_len, size=2)
62 p1 = self.neighbor[idx[0]]
63 p2 = self.neighbor[idx[1]]
64 return p1, p2
1 from collections import defaultdict
2
3 import numpy as np
4
5
6 def zdt4\_f1(x\_list):
7 return x\_list[0]
8
9
10 def zdt4\_gx(x\_list):
11 sum = 1 + 10 * (10 - 1)
12 for i in range(1, 10):
13 sum += x\_list[i] ** 2 - 10 * np.cos(4 * np.pi * x\_list[i])
14 return sum
15
16
17 def zdt4\_f2(x\_list):
18 gx\_ans = zdt4\_gx(x\_list)
19 if x\_list[0] < 0:
20 print("????: x\_list[0] < 0:", x\_list[0])
21 if gx\_ans < 0:
22 print("gx\_ans < 0", gx\_ans)
23 if (x\_list[0] / gx\_ans) <= 0:
24 print("x\_list[0] / gx\_ans<0：", x\_list[0] / gx\_ans)
25
26 ans = 1 - np.sqrt(x\_list[0] / gx\_ans)
27 return ans
28
29 def zdt3\_f1(x):
30 return x[0]
31
32
33 def zdt3\_gx(x):
34 if x[:].sum() < 0:
35 print(x[1:].sum(), x[1:])
36 ans = 1 + 9 / 29 * x[1:].sum()
37 return ans
38
39
40 def zdt3\_f2(x):
41 g = zdt3\_gx(x)
42 ans = 1 - np.sqrt(x[0] / g) - (x[0] / g) * np.sin(10 * np.pi * x[0])
43 return ans
44
45
46 class Objective\_Function:
47 function\_dic = defaultdict(lambda: None)
48
49 def \_\_init\_\_(self, f\_funcs, domain):
50 self.f\_funcs = f\_funcs
51 self.domain = domain
52
53 @staticmethod
54 def get\_one\_function(name):
55 if Objective\_Function.function\_dic[name] is not None:
56 return Objective\_Function.function\_dic[name]
57
58 if name == "zdt4":
59 f\_funcs = [zdt4\_f1, zdt4\_f2]
60 domain = [[0, 1]]
61 for i in range(9):
62 domain.append([-5, 5])
63 Objective\_Function.function\_dic[name] = Objective\_Function(f\_funcs, domain)
64 return Objective\_Function.function\_dic[name]
65
66 if name == "zdt3":
67 f\_funcs = [zdt3\_f1, zdt3\_f2]
68 domain = [[0, 1] for i in range(30)]
69 Objective\_Function.function\_dic[name] = Objective\_Function(f\_funcs, domain)
70 return Objective\_Function.function\_dic[name]
1 import numpy as np
2
3 from GA.MOEAD.Person import Person
4
5
6 def distribution\_number(sum, m):
7 # 取m個數，數的和為N
8 if m == 1:
9 return [[sum]]
10 vectors = []
11 for i in range(1, sum - (m - 1) + 1):
12 right\_vec = distribution\_number(sum - i, m - 1)
13 a = [i]
14 for item in right\_vec:
15 vectors.append(a + item)
16 return vectors
17
18
19 class Moead\_Util:
20 def \_\_init\_\_(self, N, m, T, o\_func, pm):
21 self.N = N
22 self.m = m
23 self.T = T # 鄰居大小限制
24 self.o\_func = o\_func
25 self.pm = pm # 變異概率
26
27 self.Z = np.zeros(shape=m)
28
29 self.EP = [] # 前沿
30 self.EP\_fx = [] # ep對應的目標值
31 self.weight\_vectors = None # 均勻權重向量
32 self.Euler\_distance = None # 歐拉距離矩陣
33 self.pip\_size = -1
34
35 self.pop = None
36 # self.pop\_dna = None
37
38 def init\_mean\_vector(self):
39 vectors = distribution\_number(self.N + self.m, self.m)
40 vectors = (np.array(vectors) - 1) / self.N
41 self.weight\_vectors = vectors
42 self.pip\_size = len(vectors)
43 return vectors
44
45 def init\_Euler\_distance(self):
46 vectors = self.weight\_vectors
47 v\_len = len(vectors)
48
49 Euler\_distance = np.zeros((v\_len, v\_len))
50 for i in range(v\_len):
51 for j in range(v\_len):
52 distance = ((vectors[i] - vectors[j]) ** 2).sum()
53 Euler\_distance[i][j] = distance
54
55 self.Euler\_distance = Euler\_distance
56 return Euler\_distance
57
58 def init\_population(self):
59 pop\_size = self.pip\_size
60 dna\_len = len(self.o\_func.domain)
61 pop = []
62 pop\_dna = np.random.random(size=(pop\_size, dna\_len))
63 # 初始個體的 dna
64 for i in range(pop\_size):
65 pop.append(Person(pop\_dna[i]))
66
67 # 初始個體的 weight\_vector, neighbor, o\_func
68 for i in range(pop\_size):
69 # weight\_vector, neighbor, o\_func
70 person = pop[i]
71 distance = self.Euler\_distance[i]
72 sort\_arg = np.argsort(distance)
73 weight\_vector = self.weight\_vectors[i]
74 # neighbor = pop[sort\_arg][:self.T]
75 neighbor = []
76 for i in range(self.T):
77 neighbor.append(pop[sort\_arg[i]])
78
79 o\_func = self.o\_func
80 person.set\_info(weight\_vector, neighbor, o\_func)
81 self.pop = pop
82 # self.pop\_dna = pop\_dna
83
84 return pop
85
86 def init\_Z(self):
87 Z = np.full(shape=self.m, fill\_value=float("inf"))
88 for person in self.pop:
89 for i in range(len(self.o\_func.f\_funcs)):
90 f = self.o\_func.f\_funcs[i]
91 # f\_x\_i：某個體，在第i目標上的值
92 f\_x\_i = f(person.dna)
93 if f\_x\_i < Z[i]:
94 Z[i] = f\_x\_i
95
96 self.Z = Z
97
98 def get\_fx(self, dna):
99 fx = []
100 for f in self.o\_func.f\_funcs:
101 fx.append(f(dna))
102 return fx
103
104 def update\_ep(self, new\_dna):
105 # 將新解與EP每一個進行比較，刪除被新解支配的
106 # 如果新解沒有被舊解支配，則保留
107 new\_dna\_fx = self.get\_fx(new\_dna)
108 accept\_new = True # 是否將新解加入EP
109 # print(f"准備開始循環: EP長度{len(self.EP)}")
110 for i in range(len(self.EP) - 1, -1, -1): # 從後往前遍歷
111 old\_ep\_item = self.EP[i]
112 old\_fx = self.EP\_fx[i]
113 # old\_fx = self.get\_fx(old\_ep\_item)
114 a\_b = True # 老支配行
115 b\_a = True # 新支配老
116 for j in range(len(self.o\_func.f\_funcs)):
117 if old\_fx[j] < new\_dna\_fx[j]:
118 b\_a = False
119 if old\_fx[j] > new\_dna\_fx[j]:
120 a\_b = False
121 # T T : fx相等 直接不改變EP
122 # T F ：老支配新 留老，一定不要新，結束循環.
123 # F T ：新支配老 留新，一定不要這個老，繼續循環
124 # F F : 非支配關系 不操作，循環下一個
125 # TF為什麼結束循環，FT為什麼繼續循環，你們可以琢磨下
126 if a\_b:
127 accept\_new = False
128 break
129 if not a\_b and b\_a:
130 if len(self.EP) <= i:
131 print(len(self.EP), i)
132 del self.EP[i]
133 del self.EP\_fx[i]
134 continue
135
136 if accept\_new:
137 self.EP.append(new\_dna)
138 self.EP\_fx.append(new\_dna\_fx)
139 return self.EP, self.EP\_fx
140
141 def update\_Z(self, new\_dna):
142 new\_dna\_fx = self.get\_fx(new\_dna)
143 Z = self.Z
144 for i in range(len(self.o\_func.f\_funcs)):
145 if new\_dna\_fx[i] < Z[i]:
146 Z[i] = new\_dna\_fx[i]
147 return Z
import random
import numpy as np
from GA.MOEAD.Moead\_Util import Moead\_Util
from GA.MOEAD.Objective\_Function import Objective\_Function
from GA.MOEAD.Person import Person
import matplotlib.pyplot as plt
def draw(x, y):
plt.scatter(x, y, s=10, c="grey") # s 點的大小 c 點的顏色 alpha 透明度
plt.show()
iterations = 1000 # 迭代次數
N = 400
m = 2
T = 5
o\_func = Objective\_Function.get\_one\_function("zdt4")
pm = 0.7
moead = Moead\_Util(N, m, T, o\_func, pm)
moead.init\_mean\_vector()
moead.init\_Euler\_distance()
pop = moead.init\_population()
moead.init\_Z()
for i in range(iterations):
print(i, len(moead.EP))
for person in pop:
p1, p2 = person.choice\_two\_person()
d1, d2 = Person.cross\_get\_two\_new\_dna(p1, p2)
if np.random.rand() < pm:
p1.mutation\_dna(d1)
if np.random.rand() < pm:
p1.mutation\_dna(d2)
moead.update\_Z(d1)
moead.update\_Z(d2)
t1, t2 = person.choice\_two\_person()
if t1.compare(d1) < 0:
t1.accept\_new\_dna(d1)
moead.update\_ep(d1)
if t2.compare(d1) < 0:
t2.accept\_new\_dna(d2)
moead.update\_ep(d1)
# 輸出結果畫圖
EP\_fx = np.array(moead.EP\_fx)
x = EP\_fx[:, 0]
y = EP\_fx[:, 1]
draw(x, y)
