처음 쓰는 글이네요. 약간 질문이 횡설수설해도 양해해 주시면 감사하겠습니다.
먼저 제 질문을 요약하자면 [a, b, c, d]와 같은 일정한 길이의 리스트 수십만 개를 요소로 가지는 리스트 A가 있다면 이 리스트 A 안의 리스트들을 골라내되, 골라낸 리스트들 중 리스트들의 앞 2개의 요소가 중복되는 경우가 없도록(리스트 A에 중복되는 리스트들이 있는 경우 랜덤으로 하나만 선택) 골라내는 빠른 방법이 무엇인지에 대한 것입니다.
사실 이미 일정 부분에 대해 중복없이 골라내는것을 구현은 했는데 이게 리스트 A의 길이가 짧을 때는 잘 작동하다가 길이가 수십만이 되니까 너무 오래 걸려서 어떻게 할지 잘 모르겠네요…
제가 지금 neat알고리즘(https://towardsdatascience.com/neat-an-awesome-approach-to-neuroevolution-3eca5cc7930f)을 가지고 육목(https://en.wikipedia.org/wiki/Connect6)을 플레이하는 AI를 진화시키는 프로그램을 만들고 있는데요, 부모 신경망을 교차시켜 자식 신경망을 만들도록 했는데 바둑판 크기에 맞게 신경망이 입력받는 크기와 출력받는 크기를 362(흑돌을 잡았는지 백돌을 잡았는지 입력하기 위해 길이 361의 보드 상태에 추가로 1개의 요소가 더 들어감), 361로 설정하니까 입력층 노드 2개, 출력층 노드 3개 정도에서는 아주 잘 작동하던게 속도가 너무 느려집니다.
crossover를 수행하는 함수는
def crossover(parent1, parent2):
child_connection = []
all_connection = copy.deepcopy(parent1.connection) + copy.deepcopy(parent2.connection)
#같은 노드들에 대한 연결이 존재하는지 확인하기 위한 리스트
overlap_connection = []
#자식 신경망의 은닉층 노드들의 갯수를 세기 위한 리스트
overlap_hidden_node = []
child_hidden_size = 0
#한 신경망의 연결만 자식 신경망에게로 전달되는것을 막기 위해 연결을 섞는다.
random.shuffle(all_connection)
for i in all_connection:
if i[ : 2] not in overlap_connection:
overlap_connection.append(i[ : 2])
child_connection.append(i)
#자식 신경망의 은닉 노드 갯수 조사
for node in i[ : 2]:
if parent1.input_size <= node < (parent1.input_size + parent1.hidden_size):
if node not in overlap_hidden_node:
child_hidden_size += 1
overlap_hidden_node.append(node)
#자식 신경망 객체 생성
child = ann(parent1.input_size, parent1.output_size)
child.connection = copy.deepcopy(child_connection)
child.hidden_size = child_hidden_size
child.apply_change()
return child
이렇게 생겼습니다.
신경망에서 연결은 [node1, node2, weight, True]처럼 저장되는데 이렇게 되면 node1에서 node2로 weight를 가중치로 가지는 연결이 활성화되었다는 것입니다.
이 함수에서는 두 부모 신경망의 연결을 불러와 합쳐 all_connection으로 저장한 뒤, 랜덤으로 섞고(이렇게 해야 한 부모로부터만 모든 연결이 전달되는 것을 막을 수 있기 때문에) all_connection을 순회하면서 child_connection에 이전에 추가된 연결들 중에서 현재 검사중인 연결과 node1과 node2가 같은 연결이 없다면 그대로 child_connection에 추가하고, 밑 부분에서 자식 신경망의 은닉 노드 갯수를 검사하는 부분은 아마 속도에 별 영향을 주지 않는 듯 합니다.
부모 신경망의 연결들 중에서 같은 노드끼리의 연결은 둘 중 하나만 선택하도록 하고 싶습니다.
+혹시 몰라서 전체 코드도 추가합니다
import math, random, copy
def crossover(parent1, parent2):
child_connection = []
all_connection = copy.deepcopy(parent1.connection) + copy.deepcopy(parent2.connection)
#같은 노드들에 대한 연결이 존재하는지 확인하기 위한 리스트
overlap_connection = []
#자식 신경망의 은닉층 노드들의 갯수를 세기 위한 리스트
overlap_hidden_node = []
child_hidden_size = 0
#한 신경망의 연결만 자식 신경망에게로 전달되는것을 막기 위해 연결을 섞는다.
random.shuffle(all_connection)
for i in all_connection:
if i[ : 2] not in overlap_connection:
overlap_connection.append(i[ : 2])
#child_connection.append(i)
#자식 신경망의 은닉 노드 갯수 조사
for node in i[ : 2]:
if parent1.input_size <= node < (parent1.input_size + parent1.hidden_size):
if node not in overlap_hidden_node:
child_hidden_size += 1
overlap_hidden_node.append(node)
#자식 신경망 객체 생성
child = ann(parent1.input_size, parent1.output_size)
child.connection = copy.deepcopy(child_connection)
child.hidden_size = child_hidden_size
child.apply_change()
return child
def get_random_weight():
return random.random() * 10 - 5
def sigmoid(x):
return 1 / (1 + math.exp(-x))
class ann:
def __init__(self, input_size, output_size, p = 0.6):
self.input_size = input_size
self.hidden_size = 0
self.output_size = output_size
self.node_size = self.input_size + self.hidden_size + self.output_size
self.connection = []
#연결을 랜덤으로 설정한다.
for i in range(0, input_size):
for j in range(input_size, input_size + output_size):
if random.random() <= p:
self.connection.append([i, j, get_random_weight(), True])
self.connection_structure = self.get_connection_structure()
#self.connection_structure은 self.process_order이 설정되기 전에 설정되어야 한다.
self.process_order = self.get_process_order()
#올바른 연결 추가를 위해 노드를 층별로 분리한다.
#self.connection_structure은 self.layer이 설정되기 전에 설정되어야 한다.
self.layer = self.get_layer()
#각 노드 번호의 인덱스에 그 노드가 속한 레이어 층 번호가 저장됨.
self.node_layer = [0 for i in range(0, self.node_size)]
for index, i in enumerate(self.layer):
if i != []:
for j in i:
self.node_layer[j] = index
def get_connection_structure(self):
connection_structure = [[] for i in range(0, self.node_size)]
for i in self.connection:
if i[3]:
connection_structure[i[0]].append([i[1], i[2]])
return connection_structure
def get_process_order(self):
process_order = []
node = [i for i in range(0, self.node_size)]
node_next = [i for i in range(0, self.node_size)]
node_connection = [0 for i in range(0, self.node_size)]
node_connection_check = [0 for i in range(0, self.node_size)]
for i in self.connection:
if i[3]:
node_connection[i[1]] += 1
while node_connection != node_connection_check or node != []: #출력층의 경우를 빠뜨리지 않도록 조건 or로 추가.
for i in node:
if node_connection[i] == node_connection_check[i]:
node_next.remove(i)
process_order.append(i)
for j in self.connection_structure[i]:
node_connection_check[j[0]] += 1
node = node_next
return process_order
def get_layer(self):
#레이어별로 분류
layer = []
#계산과정을 위한 리스트(레이어 값 기록)
layer_split = [1 for i in range(0, self.node_size)]
layer_split_final = []
#각 노드에 대해 그 노드에 입력을 주는 노드들의 목록
input_node_list = [[] for i in range(0, self.node_size)]
for i in self.connection:
if i[3]:
input_node_list[i[1]].append(i[0])
#각 노드에 대해 (그 노드에 입력을 주는 노드의 레이어 값의 최댓값 + 1)을 기록
#이런 방식으로 레이어 별 분류가 가능함
for i in self.process_order:
if input_node_list[i] != []: #만약 입력을 주는 노드가 없을 경우에 대비한 예외처리 추가
layer_split[i] = max([layer_split[k] for k in input_node_list[i]]) + 1
#출력층에 대해 마지막 층으로 분류되도록 조정
max_layer_value = max(layer_split)
for i in range(self.input_size, self.input_size + self.output_size):
layer_split[i] = max_layer_value
#레이어 값을 기반으로 레이어 분류
for i in range(max(layer_split)):
layer.append([])
for node, i in enumerate(layer_split):
layer[i - 1].append(node)
return layer
def propagate(self, input_data):
node = [0 for i in range(0, self.node_size)]
node[ : self.input_size] = input_data
for i in self.process_order:
if i >= self.input_size:
node[i] = sigmoid(node[i])
if self.connection_structure[i] != []:
for j in self.connection_structure[i]:
node[j[0]] += node[i] * j[1]
else:
for j in self.connection_structure[i]:
node[j[0]] += node[i] * j[1]
return node[self.input_size + self.hidden_size : self.node_size]
def mutate(self, p = 0.1):
if random.random() <= p:
self.mutate_add_node()
if random.random() <= p:
self.mutate_add_connection()
if random.random() <= p:
self.mutate_remove_connection()
if random.random() <= p:
self.mutate_change_weight()
if random.random() <= p:
self.mutate_slight_change_weight()
def mutate_add_node(self):
if self.connection != []:
is_mutatable = False
for i in self.connection:
if i[3]:
is_mutatable = True
break
#활성화된 노드가 존재한다면
if is_mutatable:
#먼저 연결을 하나 고르고
#연결이 활성화된 연결로 선택될때까지 계속 고르기를 반복한다.
con = random.choice(self.connection)
while not con[3]:
con = random.choice(self.connection)
con_index = self.connection.index(con)
self.connection[con_index][3] = False
self.hidden_size += 1
self.connection.append([con[0], self.node_size, 1, True])
self.connection.append([self.node_size, con[1], con[2], True])
self.apply_change()
def mutate_add_connection(self): #연결 추가
only_connection = []
for i in self.connection:
if i[3]:
only_connection.append(i[ : 2])
input_node = random.randint(0, self.input_size + self.hidden_size - 1)
output_node = random.randint(0, self.node_size - 1)
trail = 0
succeed = True
while self.node_layer[input_node] >= self.node_layer[output_node] or [input_node, output_node] in only_connection:
trail += 1
output_node = random.randint(0, self.node_size - 1)
if trail >= 1000:
succeed = False
break
if succeed:
self.connection.append([input_node, output_node, get_random_weight(), True])
self.apply_change()
def mutate_remove_connection(self): #연결 제거
if self.connection != []:
remove_con = random.choice(self.connection)
self.connection.remove(remove_con)
self.apply_change()
def mutate_change_weight(self): #가중치 변경
if self.connection != []:
change_con = random.choice(self.connection)
con_index = self.connection.index(change_con)
self.connection[con_index][2] = get_random_weight()
self.apply_change()
def mutate_slight_change_weight(self): #가중치 변경
if self.connection != []:
change_con = random.choice(self.connection)
con_index = self.connection.index(change_con)
self.connection[con_index][2] += (random.random() * 2 - 1)
self.apply_change()
def apply_change(self):
self.node_size = self.input_size + self.hidden_size + self.output_size
self.connection_structure = self.get_connection_structure()
#self.connection_structure은 self.process_order이 설정되기 전에 설정되어야 한다.
self.process_order = self.get_process_order()
#올바른 연결 추가를 위해 노드를 층별로 분리한다.
#self.connection_structure은 self.layer이 설정되기 전에 설정되어야 한다.
self.layer = self.get_layer()
#각 노드 번호의 인덱스에 그 노드가 속한 레이어 층 번호가 저장됨.
self.node_layer = [0 for i in range(0, self.node_size)]
for index, i in enumerate(self.layer):
if i != []:
for j in i:
self.node_layer[j] = index
a = ann(362, 361)
b = ann(362, 361)
c = crossover(a, b)