前些天發(fā)現(xiàn)一個(gè)通俗易懂,風(fēng)趣幽默的人工智能學(xué)習(xí)網(wǎng)站:
傳送門
A 簡(jiǎn)介
1 歷史
最初的元胞自動(dòng)機(jī)是由馮 · 諾依曼在 1950 年代為模擬生物 細(xì)胞的自我復(fù)制而提出的. 但是并未受到學(xué)術(shù)界重視.
1970 年, 劍橋大學(xué)的約翰 · 何頓 · 康威設(shè)計(jì)了一個(gè)電腦游戲 “生命游戲” 后, 元胞自動(dòng)機(jī)才吸引了科學(xué)家們的注意.
1983 年 S.Wolfram 發(fā)表了一系列論文. 對(duì)初等元胞機(jī) 256 種 規(guī)則所產(chǎn)生的模型進(jìn)行了深入研究, 并用熵來(lái)描述其演化行 為, 將細(xì)胞自動(dòng)機(jī)分為平穩(wěn)型, 周期型, 混沌型和復(fù)雜型.
2 應(yīng)用
- 社會(huì)學(xué): 元胞自動(dòng)機(jī)經(jīng)常用于研究個(gè)人行為的社會(huì)性, 流行 現(xiàn)象. 例如人口遷移, 公共場(chǎng)所內(nèi)人員的疏散, 流行病傳播.
- 圖形學(xué): 元胞自動(dòng)機(jī)以其特有的結(jié)構(gòu)的簡(jiǎn)單性, 內(nèi)在的并行 性以及復(fù)雜計(jì)算的能力成為密碼學(xué)中研究的熱點(diǎn)方向之一
- 物理學(xué): 在物理學(xué)中, 元胞自動(dòng)機(jī)已成功的應(yīng)用于流體, 磁 場(chǎng), 電場(chǎng), 熱傳導(dǎo)等的模擬. 例如格子氣自動(dòng)機(jī).
3 一維元胞自動(dòng)機(jī)——交通規(guī)則
定義:
-
元胞分布于一維線性網(wǎng)格上.
-
元胞僅具有車和空兩種狀態(tài).
-
元胞狀態(tài)由周圍兩鄰居決定.
規(guī)則:研究的變化對(duì)象只是中間的格子,后面的車子要比前面的車子起步延遲1格。
4 二維元胞自動(dòng)機(jī)——生命游戲
定義:
-
元胞分布于二維方型網(wǎng)格上.
-
元胞僅具有生和死兩種狀態(tài).
-
元胞狀態(tài)由周圍八鄰居決定.
規(guī)則:
骷髏:死亡;笑臉:生存
周圍有三個(gè)笑臉,則中間變?yōu)樾δ?br /> 少于兩個(gè)笑臉或者多于三個(gè),中間則變死亡。
5 什么是元胞自動(dòng)機(jī)
離散的系統(tǒng): 元胞是定義在有限的時(shí)間和空間上的, 并且元 胞的狀態(tài)是有限.
動(dòng)力學(xué)系統(tǒng): 元胞自動(dòng)機(jī)的舉止行為具有動(dòng)力學(xué)特征.
簡(jiǎn)單與復(fù)雜: 元胞自動(dòng)機(jī)用簡(jiǎn)單規(guī)則控制相互作用的元胞 模擬復(fù)雜世界.
6 構(gòu)成要素
(1)元胞 (Cell)
元胞是元胞自動(dòng)機(jī)基本單元:
- 狀態(tài): 每一個(gè)元胞都有記憶貯存狀態(tài)的功能.
- 離散: 簡(jiǎn)單情況下, 元胞只有兩種可能狀態(tài); 較復(fù)雜情況下, 元胞具有多種狀態(tài).
- 更新: 元胞的狀態(tài)都安照動(dòng)力規(guī)則不斷更新.
(2)網(wǎng)格 (Lattice)
不同維網(wǎng)格
常用二維網(wǎng)格
(3)鄰居 (Neighborhood)
(4)邊界 (Boundary)
反射型:以自己作為邊界的狀態(tài)
吸收型:不管邊界(車開(kāi)到邊界就消失)
(5)規(guī)則(狀態(tài)轉(zhuǎn)移函數(shù))
定義:根據(jù)元胞當(dāng)前狀態(tài)及其鄰居狀況確定下一時(shí)刻該元胞狀態(tài)的動(dòng)力學(xué)函數(shù), 簡(jiǎn)單講, 就是一個(gè)狀態(tài)轉(zhuǎn)移函數(shù).
分類 :
- 總和型: 某元胞下時(shí)刻的狀態(tài)取決于且僅取決于它所有鄰居 的當(dāng)前狀態(tài)以及自身的當(dāng)前狀態(tài).
- 合法型: 總和型規(guī)則屬于合法型規(guī)則. 但如果把元胞自動(dòng)機(jī) 的規(guī)則限制為總和型, 會(huì)使元胞自動(dòng)機(jī)具有局限性.
(6)森林火災(zāi)
綠色:樹(shù)木;紅色:火;黑色:空地。
三種狀態(tài)循環(huán)轉(zhuǎn)化:
樹(shù):周圍有火或者被閃電擊中就變成火。
空地:以概率p變?yōu)闃?shù)木
理性分析:紅為火;灰為空地;綠是樹(shù)
元胞三種狀態(tài)的密度和為1
火轉(zhuǎn)化為空地的密度等于空地轉(zhuǎn)換為樹(shù)的密度(新長(zhǎng)出來(lái)的樹(shù)等于燒沒(méi)的樹(shù))
fff是閃電的概率:遠(yuǎn)遠(yuǎn)小于樹(shù)生成的概率;TsmaxT_{smax}Tsmax?是一大群樹(shù)被火燒的時(shí)間尺度
程序?qū)崿F(xiàn)
周期性邊界條件
購(gòu)進(jìn)啊
其中的數(shù)字為編號(hào)
構(gòu)建鄰居矩陣
上面矩陣中的數(shù)字編號(hào),對(duì)應(yīng)原矩陣相同位置編號(hào)的上鄰居編號(hào),一 一對(duì)應(yīng)
同樣道理:
% simulate forest fire with cellular automata
% zhou lvwen: zhou.lv.wen@gmail.com
% August 15 2010
n = 300; % 定義表示森林的矩陣大小
Plight = 5e-6; Pgrowth = 1e-2; % 定義閃電和生長(zhǎng)的概率
UL = [n 1:n-1]; DR = [2:n 1]; % 定義上左,下右鄰居
veg=zeros(n,n); % 初始化表示森林的矩陣
imh = image(cat(3,veg,veg,veg)); % 可視化表示森林的矩陣
% veg = 空地為0 著火為1 樹(shù)木為2
for i=1:3000 sum = (veg(UL,:)==1) + ...(veg(:,UL)==1) + (veg(:,DR)==1) + ...(veg(DR,:)==1); % 計(jì)算出所有格子有幾個(gè)鄰居是著火的
% 根據(jù)規(guī)則更新森林矩陣:是否樹(shù)=是否樹(shù)-是否著火的樹(shù)+是否新生的樹(shù)(0-1運(yùn)算)veg = 2*(veg==2) - ...( (veg==2) & (sum>0 | (rand(n,n)<Plight)) ) + ... 2*((veg==0) & rand(n,n)<Pgrowth) ; set(imh, 'cdata', cat(3,(veg==1),(veg==2),zeros(n)) )drawnow % 可視化表示森林的矩陣
end
(7)交通概念
車距和密度
流量方程
守恒方程
時(shí)空軌跡(橫軸是空間縱軸為時(shí)間)
紅線橫線與藍(lán)色交點(diǎn)表示每個(gè)時(shí)間車的位置。
如果是豎線則表示車子在該位置對(duì)應(yīng)的時(shí)間
宏觀連續(xù)模型:
最常用的規(guī)則:
紅色條表示速度是滿的。
1 加速規(guī)則:不能超過(guò)vmax(2格/s)v_{max}(2格/s)vmax?(2格/s)
2 防止碰撞:不能超過(guò)車距
理論分析:
結(jié)果分析: 密度與流量
第一個(gè)圖:橫坐標(biāo)是歸一化后的密度,縱坐標(biāo)是車流量。第二個(gè)圖:理論值與CA的結(jié)果
結(jié)果分析: 時(shí)空軌跡
中間的深色區(qū)域是交通堵塞的區(qū)域。
ns.m
function [rho, flux, vmean] = ns(rho, p, L, tmax, animation, spacetime)
vmax = 5; %最大速度
% place a distribution with density
ncar = round(L*rho); % 車數(shù)量=L*rho
rho = ncar/L;
x = sort(randsample(1:L, ncar)); % 從1到L中隨機(jī)采ncar格樣并排序
v = vmax * ones(1,ncar); % 初始化所有車子su'du1為vmax
flux = 0; % number of cars that pass through the end
vmean = 0;
road = zeros(tmax, L);
for t = 1:tmax% 加速規(guī)則v = min(v+1, vmax);%防止碰撞gaps = gaplength(x,L); % 獲得每一輛車到前面一輛車的距離v = min(v, gaps-1);% 隨機(jī)減速vdrops = ( rand(1,ncar)<p );v = max(v-vdrops,0);% 更新位置x = x + v;passed = x>L; % 車走過(guò)整個(gè)路段x(passed) = x(passed) - L;% 回到起點(diǎn)if t>tmax/2flux = flux + sum(v/L); %平均流量vmean = vmean + mean(v);endroad(t,x) = 1;
end
flux = flux/(tmax/2);
vmean = vmean/(tmax/2);
if spacetime; figure;imagesc(road);colormap([1,1,1;0,0,0]);axis image; end% -------------------------------------------------------------------------
function gaps = gaplength(x,L)
% 計(jì)算車距
ncar = length(x);
gaps=zeros(1, ncar);
if ncar>0gaps = x([2:end 1]) -x; % d(i)=x(i+1)-x(i)gaps(gaps<=0) = gaps(gaps<=0)+L; %d(i)=d(i)+L,if d(i)<0
end
nsity = 0:0.02:1;
roadlength = 100;
vmax = 5;
tmax = 200;
pbrak = 0;
flux = [];
vmean = [];
for rho = density[R, J, V] = ns(rho, pbrak, roadlength, tmax, 0, 0);flux = [flux; J];vmean = [vmean; V];
end
% ------------------------- density vs. volecity --------------------------
figure
plot(density, vmean,'k.','markersize',15);
hold on
plot(density,min(vmax, 1./density-1),'-r','linewidth',2)
ylim([0,5.55])
legend({'Cellular automata aproach', ...'$v(\rho) = \min\{v_{\max}, 1/\rho-1\}$'}, ...'interpreter','latex')
xlabel('density in vehicles/cell')
ylabel('velocity in cell/time')
% --------------------------- density vs. flux ----------------------------
figure
plot(density, flux,'k.','markersize',15);
hold on;
plot(density,min(density*vmax, 1-density),'-r','linewidth',2)
legend({'Cellular automata aproach', ...'$J(\rho) = \min\{\rho\cdot v_{\max}, 1-\rho\}$'}, ...'interpreter','latex')
xlabel('density in vehicles/cell')
ylabel('flux in vehicles/time')
density = 0:0.02:1;
roadlength = 100;
vmax = 5;
tmax = 200;
pbrak = 0;
flux = [];
vmean = [];
for rho = density[R, J, V] = ns(rho, pbrak, roadlength, tmax, 0, 0);flux = [flux; J];vmean = [vmean; V];
end
% ------------------------- density vs. volecity --------------------------
figure
plot(density, vmean,'k.','markersize',15);
hold on
plot(density,min(vmax, 1./density-1),'-r','linewidth',2)
ylim([0,5.55])
legend({'Cellular automata aproach', ...'$v(\rho) = \min\{v_{\max}, 1/\rho-1\}$'}, ...'interpreter','latex')
xlabel('density in vehicles/cell')
ylabel('velocity in cell/time')
% --------------------------- density vs. flux ----------------------------
figure
plot(density, flux,'k.','markersize',15);
hold on;
plot(density,min(density*vmax, 1-density),'-r','linewidth',2)
legend({'Cellular automata aproach', ...'$J(\rho) = \min\{\rho\cdot v_{\max}, 1-\rho\}$'}, ...'interpreter','latex')
xlabel('density in vehicles/cell')
ylabel('flux in vehicles/time')
周呂文 中國(guó)科學(xué)院力學(xué)研究所
總結(jié)
以上是生活随笔為你收集整理的【数学建模】元胞自动机的全部?jī)?nèi)容,希望文章能夠幫你解決所遇到的問(wèn)題。
如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò),歡迎將生活随笔推薦給好友。