遺傳算法求解幾何問題

點擊上方“小白學(xué)視覺”，選擇加"星標"或“置頂”

重磅干貨，第一時間送達

作者 | Victor Sim?

編譯 | VK?

來源 | Towards Data Science

我最近看了一個關(guān)于“令人難以置信的直覺人工智能發(fā)明”的ted演講：https://www.ted.com/talks/maurice_conti_the_incredible_inventions_of_intuitive_ai

這個ted演講的特色是使用直觀的人工智能生成汽車模型。這部分內(nèi)容很簡短，沒有詳細說明什么類型的人工智能以及它是如何實現(xiàn)的，所以我決定嘗試用遺傳算法復(fù)制這個項目的一個小規(guī)模版本。

我為什么選擇遺傳算法？與神經(jīng)網(wǎng)絡(luò)不同的是，遺傳算法可以很容易地生成內(nèi)容，而無需對圖像進行卷積，然后將其轉(zhuǎn)換回原始尺寸。但是，要找到正確格式的汽車模型數(shù)據(jù)是極其困難的，

概述了項目類型后，我應(yīng)該如何簡化問題?

概念

我將用簡單的想法來代替制造低空氣阻力的汽車，即創(chuàng)建一個由n個點組成的最大區(qū)域的形狀，以點連接的方式。

形狀的面積將使用鞋帶（Shoelace ）公式計算。從名稱中可以推導(dǎo)出它是如何工作的:點坐標的交叉乘法創(chuàng)建了鞋帶類型模式。

然后我將使用一種遺傳算法(改編自這段代碼：https://troysquillaci.me/simple-genetic-algorithm.html)來生成一組數(shù)字，然后將這些數(shù)字轉(zhuǎn)換為坐標，從而繪制出一個形狀。

代碼

步驟1 |依賴項

import?random
import?numpy?as?np
from?IPython.display?import?clear_outputdef?sigmoid(x):
????return?1/(1+np.exp(-x))
????
def?PolyArea(x,y):
????return?0.5*np.abs(np.dot(x,np.roll(y,1))-np.dot(y,np.roll(x,1)))

導(dǎo)入程序運行所需的基本依賴項。random用于隨機生成智能體，numpy用于初始化和操作矩陣，IPython display用于清除屏幕上的混亂。

為了簡單起見，我將在這個項目中使用的唯一激活函數(shù)是sigmoid函數(shù)。

polyarea函數(shù)是以numpy為數(shù)學(xué)基礎(chǔ)的鞋帶算法的實現(xiàn)。

步驟2 |實現(xiàn)類

class?genetic_algorithm:
????????
????def?execute(pop_size,generations,threshold,network):
????????class?Agent:
????????????def?__init__(self,network):
????????????????class?neural_network:
????????????????????def?__init__(self,network):
????????????????????????self.weights?=?[]
????????????????????????self.activations?=?[]
????????????????????????for?layer?in?network:
????????????????????????????if?layer[0]?!=?None:
????????????????????????????????input_size?=?layer[0]
????????????????????????????else:
????????????????????????????????input_size?=?network[network.index(layer)-1][1]
????????????????????????????output_size?=?layer[1]
????????????????????????????activation?=?layer[2]
????????????????????????????
????????????????????????????self.weights.append(np.random.randn(input_size,output_size))
????????????????????????????self.activations.append(activation)
????????????????????def?propagate(self,data):
????????????????????????input_data?=?data
????????????????????????for?i?in?range(len(self.weights)):
????????????????????????????z?=?np.dot(input_data,self.weights[i])
????????????????????????????a?=?self.activations[i](z)
????????????????????????????input_data?=?a
????????????????????????yhat?=?a
????????????????????????return?yhat
????????????????self.neural_network?=?neural_network(network)
????????????????self.fitness?=?0
????????????????self.gene_drive?=?[]
????????????def?__str__(self):
????????????????????return?'Loss:?'?+?str(self.fitness[0])

這是程序的開始，創(chuàng)建了遺傳算法類和執(zhí)行函數(shù)。

在agent的init中，初始化一個神經(jīng)網(wǎng)絡(luò)類，并根據(jù)給定的矩陣結(jié)構(gòu)隨機生成其權(quán)重。

步驟3 |創(chuàng)建種群

def?generate_agents(population,?network):
????????????return?[Agent(network)?for?_?in?range(population)]

該函數(shù)以種群大小和網(wǎng)絡(luò)結(jié)構(gòu)為參數(shù)，生成智能體的種群，神經(jīng)網(wǎng)絡(luò)隨機生成權(quán)值。

步驟4 |計算適合度

def?fitness(agents):
????????????for?agent?in?agents:
????????????????total_area?=?0
????????????????
????????????????points?=?agent.neural_network.propagate(np.random.randn(1,semi_epochs))
????????????????
????????????????for?shape?in?points:
????????????????????x?=?list(shape[:num_points])
????????????????????y?=?list(shape[num_points:])
????????????????????
????????????????????y.insert(0,0)
????????????????????x.insert(0,0)
?????y.insert(-1,0)
????????????????????x.insert(-1,0)
?????total_area?+=?PolyArea(x,y)?
????????????????????
????????????????agent.fitness?=?total_area/semi_epochs
????????????????
????????????return?agents

我們將潛在點作為神經(jīng)網(wǎng)絡(luò)的輸入。正因為如此，網(wǎng)絡(luò)將進行多次嘗試來生成形狀，并記錄這些形狀的平均面積。

理論上，該算法將生成一個智能體，該智能體可以一致地生成具有n個點的高區(qū)域形狀。觀察這些形狀可以幫助我們了解如何創(chuàng)建大面積的區(qū)域。

步驟5 |選擇

def?selection(agents):
????????????agents?=?sorted(agents,?key=lambda?agent:?agent.fitness,?reverse=True)
????????????print('\n'.join(map(str,?agents)))
????????????agents?=?agents[:int(0.2?*?len(agents))]
????????????return?agents

程序的這一部分是選擇算法，它根據(jù)智能體的適合度按逆序?qū)λ鼈冞M行排序。然后它會保留前五名。

步驟6 |交叉：

def?crossover(agents,network,pop_size):
????????????offspring?=?[]
????????????for?_?in?range((pop_size?-?len(agents))?//?2):
????????????????parent1?=?random.choice(agents)
????????????????parent2?=?random.choice(agents)
????????????????child1?=?Agent(network)
????????????????child2?=?Agent(network)
????????????????
????????????????shapes?=?[a.shape?for?a?in?parent1.neural_network.weights]
????????????????
????????????????genes1?=?np.concatenate([a.flatten()?for?a?in?parent1.neural_network.weights])
????????????????genes2?=?np.concatenate([a.flatten()?for?a?in?parent2.neural_network.weights])
????????????????
????????????????split?=?random.randint(0,len(genes1)-1)child1_genes?=?np.array(genes1[0:split].tolist()?+?genes2[split:].tolist())
????????????????child2_genes?=?np.array(genes1[0:split].tolist()?+?genes2[split:].tolist())
????????????????
????????????????for?gene?in?parent1.gene_drive:
????????????????????child1_genes[gene]?=?genes1[gene]
????????????????????child2_genes[gene]?=?genes1[gene]
????????????????????
????????????????for?gene?in?parent2.gene_drive:
????????????????????child1_genes[gene]?=?genes2[gene]
????????????????????child2_genes[gene]?=?genes2[gene]
????????????????
????????????????child1.neural_network.weights?=?unflatten(child1_genes,shapes)
????????????????child2.neural_network.weights?=?unflatten(child2_genes,shapes)
????????????????
????????????????offspring.append(child1)
????????????????offspring.append(child2)
????????????agents.extend(offspring)
????????????return?agents

從種群的20%中隨機選出兩個父母。然后繁殖。如何做到這一點：

1. 他們的權(quán)重平坦化(flatten)

2. 找到一個隨機的交點。這一點是單親的遺傳信息結(jié)束的地方，也是單親遺傳信息開始的地方。

3. 將創(chuàng)建兩個子代，然后將其添加到智能體列表中。這些子對象彼此不同，因為它們有不同的交點。

這有希望讓好父母的優(yōu)良品質(zhì)遺傳給后代。

步驟7 |突變

def?mutation(agents):
????????????for?agent?in?agents:
????????????????if?random.uniform(0.0,?1.0)?<=?0.1:
????????????????????weights?=?agent.neural_network.weights
????????????????????shapes?=?[a.shape?for?a?in?weights]flattened?=?np.concatenate([a.flatten()?for?a?in?weights])
????????????????????randint?=?random.randint(0,len(flattened)-1)
????????????????????flattened[randint]?=?np.random.randn()newarray?=?[]
????????????????????indeweights?=?0
????????????????????for?shape?in?shapes:
????????????????????????size?=?np.product(shape)
????????????????????????newarray.append(flattened[indeweights?:?indeweights?+?size].reshape(shape
????????????????????????indeweights?+=?size
????????????????????agent.neural_network.weights?=?newarray
????????????return?agents

有10%的幾率發(fā)生突變。在這種情況下，變異指的是某個權(quán)重值被一個隨機浮點值替換。通過將權(quán)重展平，找到要更改的隨機權(quán)重。

步驟9 |執(zhí)行

for?i?in?range(generations):
????????????print('Generation',str(i),':')
????????????agents?=?generate_agents(pop_size,network)
????????????agents?=?fitness(agents)
????????????agents?=?selection(agents)
????????????agents?=?crossover(agents,network,pop_size)
????????????agents?=?mutation(agents)
????????????agents?=?fitness(agents)
????????????
????????????if?any(agent.fitness?>?threshold?for?agent?in?agents):
????????????????print('Threshold?met?at?generation?'+str(i)+'?!')
????????????????
????????????if?i?%?100:
????????????????clear_output()
????????????????
????????return?agents[0]

將最后一段代碼粘貼到函數(shù)中，函數(shù)應(yīng)該在調(diào)用時運行。

num_points?=?3
semi_epochs?=?100

network?=?[[semi_epochs,100,sigmoid],[None,num_points*2,sigmoid]]
ga?=?genetic_algorithm
agent?=?ga.execute(100,100,10,network)
weights?=?agent.neural_network.weights

我們可以改變程序可以用來創(chuàng)建形狀的點的數(shù)量，以及程序可以生成點的次數(shù)，以得到平均值。改變這些值，你可能會發(fā)現(xiàn)一些有趣的東西!

原文鏈接：https://towardsdatascience.com/using-genetic-algorithms-to-solve-geometrical-problems-3789cb70bf25

交流群

歡迎加入公眾號讀者群一起和同行交流，目前有SLAM、三維視覺、傳感器、自動駕駛、計算攝影、檢測、分割、識別、醫(yī)學(xué)影像、GAN、算法競賽等微信群（以后會逐漸細分），請掃描下面微信號加群，備注：”昵稱+學(xué)校/公司+研究方向“，例如：”張三?+?上海交大?+?視覺SLAM“。請按照格式備注，否則不予通過。添加成功后會根據(jù)研究方向邀請進入相關(guān)微信群。請勿在群內(nèi)發(fā)送廣告，否則會請出群，謝謝理解~