- 元胞具有一定的計(jì)算能力混萝，可以當(dāng)作最小的非馮諾依曼架構(gòu)并行計(jì)算機(jī)。在《復(fù)雜》一書當(dāng)中介紹了采用遺傳算法篩選出能進(jìn)行二分類算法的一維元胞規(guī)則——即判斷輸入的元胞兩種狀態(tài)誰(shuí)多誰(shuí)少驱证，哪一種多就全部演變成為這一種狀態(tài)阎曹。
- 本文嘗試復(fù)現(xiàn)此操作度帮，由于元胞DNA序列種類為2的128次方種，因此我找到的規(guī)則和書中所述不同定鸟，但是效果一致 而涉。
先上貢分類器dna序列
[1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0]
分類效果：
| 小于一半 | 大于一半 |
|---|---|
 小于一半數(shù)量
|
 大于一半數(shù)量
|
 小于一半數(shù)量（47）
|
 大于一半數(shù)量（51）
|
配置
jyputer notebook
依賴包:
matrix可視化使用matplotlib 的matshow()函數(shù)
from numpy import *;#導(dǎo)入numpy的庫(kù)函數(shù)
import numpy as np; #這個(gè)方式使用numpy的函數(shù)時(shí)，需要以np.開頭仔粥。
import matplotlib.pyplot as plt
import numpy as np
import pandas as pd
%matplotlib inline
import time
import math
partone 元胞自動(dòng)機(jī)dna編碼
簡(jiǎn)單元胞自動(dòng)機(jī)編碼：
若一個(gè)元胞能觀察到自己和左右兩個(gè)元胞婴谱，則能觀測(cè)2**3種類型蟹但，每種類型對(duì)應(yīng)一種生死狀態(tài)（0死/1生）即形成了這個(gè)元胞的生存策略，例如：
? ? ?——1
? ? ?——0
? ? ?——1
? ? ?——1
? ? ?——0
? ? ?——1
? ? ?——1
? ? ?——0
即可用序列10110110作為此元胞的DNA序列
typelist=[]
for i in range(4):
typelist.extend(unique_list(permutations(innitlist(3,i), 3)))
print(typelist)
#[(0, 0, 0),
#(1, 0, 0),
#(0, 1, 0),
#(0, 0, 1),
#(1, 1, 0),
#(1, 0, 1),
#(0, 1, 1),
#(1, 1, 1)]
DNA=[1,0,1,1,0,1,1,0]
迭代環(huán)境的搭建谭羔，主要是要接入DNA來控制迭代华糖，這里我采用利用排列組合的list：
[(0, 0, 0),
(1, 0, 0),
(0, 1, 0),
(0, 0, 1),
(1, 1, 0),
(1, 0, 1),
(0, 1, 1),
(1, 1, 1)]
對(duì)應(yīng)產(chǎn)生DNA字典
#4領(lǐng)域
class nodcell:
def __init__(self, i, list_one,dickey):
self.__i = i
self.lod=list_one[i]
###############構(gòu)成首尾循環(huán)################
if i+1>=len(list_one):
righti=0
else:
righti=list_one[i+1]
if i-1<0:
lefti=list_one[len(list_one)-1]
else:
lefti=list_one[i-1]
###########################################
self.neiboer_mat=(lefti,list_one[i],righti)
#dickey即DNA策略表
self.dickey=dickey
#print(self.neiboer_mat)
# 產(chǎn)生下一代
def relod (self):
key=self.neiboer_mat
#lod： live or die
self.lod=dickey[key]
return self.lod
#迭代一代
def on_generationa(initlist,dickey):
nodlist=[]
for i in range(len(initlist)):
nod=nodcell(i, initlist,dickey)
nodlist.append(nod)
ons=[]
for i in (nodlist):
ons.append(i.relod())
return ons
#迭代n代
def all_gen(initlist,n,dickey):
finalone=[]
finalone.append(initlist)
for i in range(n):
initlist=on_generationa(initlist,dickey)
finalone.append(initlist)
return finalone
#準(zhǔn)備好8種類型的list
def prp_originlist():
originlist=[]
for i in range(4):
originlist.extend(unique_list(permutations(innitlist(3,i), 3)))
len(originlist)
return originlist
#以類型為key 存放 0/1 （DNA與類型關(guān)聯(lián)）
def prop_key(originlist,n):
dickey={}
for i in range(len(originlist)):
dickey[(originlist[i])]=DNA[i]
return dickey
DNA=[1,0,1,1,0,1,1,0]
#初始化一個(gè)200長(zhǎng)度的元胞組cc
cc=list(random.randint(0,2,200))
#生成DNA字典
dickey=prop_key(prp_originlist(),"")
#按照DNA字典迭代100次
m=np.matrix(all_gen(cc,100,dickey))
#展示
plt.matshow(m)
DNA=[1,0,1,1,0,1,1,0]
所有視覺為1的DNA數(shù)量為 2**9=512種
Part Two 升級(jí)元胞視野
元胞視野升級(jí)為左三右三，類型組合有2**7=128種
所有視覺為3的DNA數(shù)量為 -
- 2**128=340282366920938463463374607431768211456
數(shù)不清了瘟裸，因此一個(gè)一個(gè)找不可能找到客叉，這里借助遺傳算法來解決
遺傳算法步驟：
- 1 進(jìn)行編碼解碼（元胞編碼如上已變?yōu)闉槎M(jìn)制）
- 2 確定適應(yīng)度函數(shù)——（稍后探討）
- 3根據(jù)輪盤賭選擇算子，選取適應(yīng)度較大的個(gè)體话告。
- 4確定交叉概率Pc,對(duì)上一步得到的種群進(jìn)行單點(diǎn)交叉兼搏。每次交叉點(diǎn)的位置隨機(jī)。
- 5確定變異概率Pm,每次變異點(diǎn)的位置隨機(jī)沙郭。
完整程序
from numpy import *;#導(dǎo)入numpy的庫(kù)函數(shù)
import numpy as np; #這個(gè)方式使用numpy的函數(shù)時(shí)佛呻，需要以np.開頭。
import matplotlib.pyplot as plt
import numpy as np
import pandas as pd
%matplotlib inline
import time
import math
#4領(lǐng)域
class nodcell:
def __init__(self, i, list_one,thekey):
self.__i = i
self.dickey=thekey
self.lod=list_one[i]
if i+1>=len(list_one):
self.neiboer_mat=(list_one[i-3],list_one[i-2],list_one[i-1],list_one[i],list_one[0],list_one[1],list_one[2])
elif i+2>=len(list_one):
self.neiboer_mat=(list_one[i-3],list_one[i-2],list_one[i-1],list_one[i],list_one[i+1],list_one[0],list_one[1])
elif i+3>=len(list_one):
self.neiboer_mat=(list_one[i-3],list_one[i-2],list_one[i-1],list_one[i],list_one[i+1],list_one[i+2],list_one[0])
elif i-3<0:
self.neiboer_mat=(list_one[len(list_one)-1],list_one[i-2],list_one[i-1],list_one[i],list_one[i+1],list_one[i+2],list_one[i+3])
elif i+3<len(list_one):
self.neiboer_mat=(list_one[len(list_one)-2],list_one[len(list_one)-1],list_one[i-1],list_one[i],list_one[i+1],list_one[i+2],list_one[i+3])
elif i+3<len(list_one):
self.neiboer_mat=(list_one[len(list_one)-3],list_one[len(list_one)-2],list_one[len(list_one)-1],list_one[i],list_one[i+1],list_one[i+2],list_one[i+3])
else:
self.neiboer_mat=(list_one[i-3],list_one[i-2],list_one[i-1],list_one[i],list_one[i+1],list_one[i+2],list_one[i+3])
#print(self.neiboer_mat)
def relod (self):
key=self.neiboer_mat
self.lod=self.dickey[key]
return self.lod
#########################################對(duì)DNA字典的封裝###########################################################################################
from scipy.special import comb, perm
from itertools import combinations, permutations
def innitlist(a,n):
add=[]
for i in range(n):
add.append(1)
for i in range(a-n):
add.append(0)
return add
def unique_list(list1):
list2 = []
for i in list1:
if i not in list2:
list2.append(i)
return list2
def prp_originlist(n):
# 準(zhǔn)備DNA字典
originlist=[]
for i in range(n+1):
originlist.extend(unique_list(permutations(innitlist(n,i), n)))
len(originlist)
return originlist
def prop_key(originlist,DNAli):
dickey={}
for i in range(len(originlist)):
dickey[(originlist[i])]=DNAli[i]
return dickey
##################################################################################################################################
def randomkeylist(neibor=7,size=128,leng=20):
keylist=[]
originlist=prp_originlist(neibor)
for i in range(leng):
DNAli=list(random.randint(0,2,size))
key=prop_key(originlist,DNAli)
keylist.append(key)
return keylist
keylist=randomkeylist()
def on_generationa(initlist,dickey):
nodlist=[]
for i in range(len(initlist)):
nod=nodcell(i, initlist,dickey)
nodlist.append(nod)
ons=[]
for i in (nodlist):
ons.append(i.relod())
return ons
def all_gen(initlist,n,dickey):
finalone=[]
finalone.append(initlist)
for i in range(n):
initlist=on_generationa(initlist,dickey)
finalone.append(initlist)
return finalone
def plot_generate(init,generate,DNAli):
dickey=prop_key(prp_originlist(7),DNAli)
m=np.matrix(all_gen(init,generate,dickey))
plt.matshow(m)
plt.title(1)
def m_generate(init,generate,DNAli):
dickey=prop_key(prp_originlist(7),DNAli)
m=np.matrix(all_gen(init,generate,dickey))
return m
適應(yīng)度函數(shù)：元胞自動(dòng)機(jī)目標(biāo)為二分類器病线，不同于函數(shù)
- 第一次嘗試：仿照softmax函數(shù)歸一吓著，-log（x）函數(shù)及-log(1-x)作為兩種情況進(jìn)行判斷
結(jié)果：經(jīng)過上百代迭代不論初始，最終元胞全為0
這里沒有讓適應(yīng)度函數(shù)同時(shí)考慮兩種情況送挑，一種情況成立 就被判斷為高適應(yīng)度
第二次嘗試：沒有隨機(jī)初始元胞绑莺，以用同一個(gè)元胞嘗試DNA，得到的結(jié)果換一個(gè)元胞序列就變了
第三次嘗試：同時(shí)隨機(jī)正反兩例惕耕，設(shè)計(jì)正反適應(yīng)度纺裁，最后結(jié)合到一起作為最終適應(yīng)度。
如下貼出：
############################################
#遺傳算法的實(shí)現(xiàn)
import numpy as np
from scipy.optimize import fsolve, basinhopping
import timeit
#獲取初始種群：
def getIntialPopulation(length,huge):
Populationlist=[]
for i in range(huge):
init=list(random.randint(0,2,length))
Populationlist.append(init)
return Populationlist
dnak=prp_originlist(7)
#計(jì)算單個(gè)元胞的適應(yīng)度
def get_one_fit_level(DNAli,lenss,dnak,generate=200):
for i in range(1000):
init=list(random.randint(0,2,lenss))
if sum(init)>int(lenss/2):
initp=init
break
for i in range(1000):
init=list(random.randint(0,2,lenss))
if sum(init)<int(lenss/2):
initn=init
break
dickey=prop_key(dnak,DNAli)
m1=np.matrix(all_gen(initp,generate,dickey))
m2=np.matrix(all_gen(initn,generate,dickey))
lel=aa
fit=0
xp=sum(m1[-1])
xn=sum(m2[-1])
if xp<=(lel*3)/4:
fitp=0.001*(xp)/lel
else:
fitp=(xp)/lel
if xn>=lel/4:
fitn=0.001*(lel-xn)/lel
else:
fitn=(lel-xn)/lel
fit=fitn*fitp
return fit
# 計(jì)算所有元胞的適應(yīng)度
def all_fit_mean(Populationlist,initenvir,generate=200):
listfit=[]
for i in Populationlist:
listfit.append(math.exp(get_one_fit_level(i,lenss,dnak,generate)))
fitsum=sum(listfit)
li=[]
for i in listfit:
li.append(i/fitsum)
return fitsum,li
#####輪盤賭注
#####輪盤賭注
def geration_bat(fitlist,Populationlist):
licol=[]
count=0
# 累計(jì)概率的計(jì)算
for i in range(len(fitlist)):
count+=fitlist[i]
licol.append(count)
choselist=[]
#輪盤選取序號(hào)
licol=[0]+licol
for i in range(len(licol)-1):
aim=random.random(1)[0]
for i in range(len(licol)-1):
if (aim>=licol[i])&(aim<licol[i+1]):
choselist.append(i)
#print(i)
#print(len(choselist))
newgeneration =[]
for i in choselist :
newgeneration.append(Populationlist[i])
#print(len(newgeneration))
return newgeneration
#交叉
def cross_dna(lista,listb,pc):
np.random.seed(0)
p = np.array([1-pc, pc])
index = np.random.choice([0, 1], p = p.ravel())
if index==1:
pos=random.randint(0,128)
mida=lista[pos]
midb=listb[pos]
#print(listb[pos])
#print(lista[pos])
newa=[]
newb=[]
for k,l,m in zip(lista,listb,range(len(listb))):
if m==pos:
newa.append(l)
newb.append(k)
else:
newa.append(k)
newb.append(l)
return (newa,newb)
##############################變異################################
#配對(duì)
def cors_new_gen(pc,newgeneration):
lens=len(newgeneration)
for i in range(1000):
c=random.randint(0,2,lens)
if (sum(c)==int(lens/2)):
break
manl=[]
fman=[]
for i ,j in zip(newgeneration,c):
if j==0:
manl.append(i)
else:
fman.append(i)
new_cors_generation=[]
for i ,j in zip(manl,fman):
a,b=cross_dna(i,j,pc)
new_cors_generation.append(a)
new_cors_generation.append(b)
return new_cors_generation
cors_gen=cors_new_gen(1,newgeneration)
len(cors_gen)
#突變
def R_change(cors_gen,pm=0.0001):
new_list=[]
for i in cors_gen:
p = np.array([1-pm, pm])
index = np.random.choice([0, 1], p = p.ravel())
if index==1:
pos=random.randint(0,128)
newone=[]
for j in range(len(i)):
if j==pos:
if i[j]==0:
newone.append(1)
else:
newone.append(0)
else:
newone.append(i[j])
new_list.append(newone)
else:
new_list.append(i)
return new_list
開始種群繁衍500代
#初始化種群
Populationlist=getIntialPopulation(128,200)
costlist=[]
for ge in range(500):
aa=40
init=list(random.randint(0,2,aa))
#獲取初始適應(yīng)度
fitsum,fitlist=all_fit_mean(Populationlist,init,40)
#輪盤賭住選擇夫妻
newgeneration=geration_bat(fitlist,Populationlist)
#進(jìn)行交叉及編譯
cors_gen=cors_new_gen(0.7,newgeneration)
newlist=R_change(cors_gen,pm=0.05)
Populationlist=newlist
costlist.append(fitsum)
print(ge)
print(fitsum)
##防止陷入局部最優(yōu)點(diǎn)
if costlist[-1]==costlist[-2]:
break
計(jì)算機(jī)為i5四代司澎，這里用的元胞的長(zhǎng)度為40欺缘，計(jì)算速度為9秒/代，若用長(zhǎng)度為200的元胞惭缰，計(jì)算速度為50秒/代浪南，實(shí)際迭代效果適合的長(zhǎng)度就行，但是元胞的自動(dòng)繁殖時(shí)間需要足夠漱受。我取的是200次络凿。
待改進(jìn)
- 運(yùn)算速度 太慢，日后有時(shí)間會(huì)進(jìn)行向量化操作昂羡。
- 元胞的種類太豐富絮记，上面實(shí)現(xiàn)的判斷很簡(jiǎn)單，希望以后能設(shè)計(jì)出能夠選擇出邏輯運(yùn)算的適應(yīng)函數(shù)
