元胞自動(dòng)機(jī)理論及其在登機(jī)問題研究中的運(yùn)用,mba畢業(yè)論文

元胞自動(dòng)機(jī)理論及其在登機(jī)問題研究中的運(yùn)用,mba畢業(yè)論文本篇論文目錄導(dǎo)航：【題目】【第一章】【第二章】元胞自動(dòng)機(jī)理論及其在登機(jī)問題研究中的運(yùn)用【3.1-3.3】【3.43.5】【第四章】【第五章】【結(jié)論/以下為參考文獻(xiàn)】第二章元胞自動(dòng)機(jī)理論及其在登機(jī)問題研究中的運(yùn)用2.1元胞自動(dòng)機(jī)基本理論。馮諾依曼〔VonNeumann〕作為20世紀(jì)最偉大的數(shù)學(xué)家之一，由于他本人在計(jì)算機(jī)和博弈論等方面的眾多成就為人們所熟知。20世紀(jì)中葉，他通過對(duì)復(fù)雜系統(tǒng)的邏輯抽象研究，提出了元胞自動(dòng)機(jī)這一系統(tǒng)。隨著計(jì)算機(jī)技術(shù)的逐步發(fā)展成熟，元胞自動(dòng)機(jī)理論也不斷豐富。1970年，數(shù)學(xué)家約翰康威〔JohnConway〕提出了生命游戲機(jī)的概念，使元胞自動(dòng)機(jī)開場能夠模擬復(fù)雜系統(tǒng)。上世紀(jì)80年代，史蒂芬沃爾弗拉姆〔StephenWolfram〕從動(dòng)力學(xué)角度對(duì)元胞自動(dòng)機(jī)進(jìn)行研究，打開了元胞自動(dòng)機(jī)應(yīng)用的另一扇大門。2.1.1元胞自動(dòng)機(jī)的概念。元胞自動(dòng)機(jī)〔CellularAutomata,簡稱CA〕是一個(gè)時(shí)間和空間都離散的動(dòng)力系統(tǒng)。分布在規(guī)則網(wǎng)格中的每一個(gè)元胞取有限的離散狀態(tài)，遵循同樣的規(guī)則同步更新。大量元胞通過簡單的互相作用而構(gòu)成動(dòng)態(tài)系統(tǒng)的演化。不同于一般的動(dòng)力學(xué)模型，元胞自動(dòng)機(jī)不是由嚴(yán)格定義的方程或函數(shù)確定，而是用一系列的規(guī)則構(gòu)成。但凡知足這些規(guī)則的模型都能夠算作是元胞自動(dòng)機(jī)模型。因而，元胞自動(dòng)機(jī)是一類模型的名稱，或者講是一個(gè)方式方法框架。其特點(diǎn)是時(shí)間、空間、狀態(tài)都離散，每個(gè)變量只取有限多個(gè)狀態(tài)，且其狀態(tài)改變的規(guī)則在時(shí)間和空間上都是局部的。2.1.2元胞自動(dòng)機(jī)的構(gòu)成。元胞自動(dòng)機(jī)最基本的元胞、元胞空間、鄰居及規(guī)則四部分〔如此圖2-1〕。簡單講，元胞自動(dòng)機(jī)能夠視為由一個(gè)元胞空間和定義于該空間的變換函數(shù)所組成。1、元胞。元胞是元胞自動(dòng)機(jī)最基礎(chǔ)的構(gòu)成部分，元胞的位置在元胞空間的格點(diǎn)上，不同的元胞具有不同的狀態(tài)和形狀。元胞的狀態(tài)能夠是二進(jìn)制{0,1}形式，可以以是{S1,S2,S3,Sj,Sk}整數(shù)形式的離散集。2、元胞空間。元胞所在的空間網(wǎng)點(diǎn)數(shù)的集合就是元胞空間。研究中經(jīng)常牽涉的元胞空間有一維空間和二維空間。一維空間只要一種劃分方式，二維元胞自動(dòng)機(jī)通常有三種方式，三角形、正方形和六邊形。3、鄰居。鄰居指的是元胞更新時(shí)能夠影響的空間范圍。不同維度的元胞空間元胞的鄰居情況有所差異不同。一維空間中，元胞鄰居的情況較為簡單，由該元胞可影響的半徑?jīng)Q定，但是對(duì)于二維元胞自動(dòng)機(jī)而言，就有較多的劃分方式，華而不實(shí)主要有VonNeumann型、Moore型和擴(kuò)展Moore型3種形式，如此圖2-3所示。邊界元胞的鄰居不同于內(nèi)部元胞，因而主要有周期型邊界、固定邊界、絕熱邊界和映射邊界幾種邊界處理方式。4、演化規(guī)則。空間中的元胞根據(jù)本身以及鄰域中元胞的狀態(tài)確定下一狀態(tài)的變換函數(shù)就是元胞的演化規(guī)則，這個(gè)規(guī)則本質(zhì)上是一種狀態(tài)轉(zhuǎn)移函數(shù)，也是利用元胞自動(dòng)機(jī)理論建模的核心?；谝欢ǖ难莼?guī)則，系統(tǒng)不斷在時(shí)間和空間上進(jìn)行迭代應(yīng)用到所有的元胞中，進(jìn)而推動(dòng)整個(gè)元胞系統(tǒng)的不斷演變，假如在迭代的經(jīng)過中沒有出現(xiàn)隨機(jī)變量，則為確定性模型，否則為非確定性模型。2.1.3元胞自動(dòng)機(jī)的原理及特征。元胞自動(dòng)機(jī)是大量簡單一樣的個(gè)體通過局部之間的互相關(guān)系組成的離散、空間能夠擴(kuò)張的系統(tǒng)，這種具有時(shí)間、空間狀態(tài)均離散的動(dòng)力學(xué)系統(tǒng)大致能夠分為四大類：平穩(wěn)型、復(fù)雜型、混沌型、周期型[38-40].元胞自動(dòng)機(jī)模型具有下面性質(zhì)[41]:1、同質(zhì)性和齊性。同質(zhì)性是指元胞空間上每個(gè)元胞的演化都遵循一樣的規(guī)則，即特定的轉(zhuǎn)移函數(shù)來決定下一時(shí)刻元胞的狀態(tài)。齊性是指形狀、大小一樣的元胞空間分布規(guī)則整潔。2、離散性。元胞自動(dòng)機(jī)模型的離散性主要具體表現(xiàn)出在元胞的空間離散性和時(shí)間離散性。3、時(shí)空局部性。周圍鄰居規(guī)則所定下的鄰域中元胞的當(dāng)下時(shí)刻t狀態(tài)是決定每個(gè)元胞的下一時(shí)刻t+1狀態(tài)的位移因素，正因如此，元胞自動(dòng)機(jī)才具有時(shí)間和空間的局部性。4、同步性。元胞的狀態(tài)變化同步進(jìn)行卻又互相獨(dú)立，互相沒有任何影響，合適并行運(yùn)算，這種算法要優(yōu)于其他模型的工作方式，能夠大大提高模擬的速度。5、維數(shù)高。維數(shù)是指元胞自動(dòng)機(jī)所組成的動(dòng)力系統(tǒng)中變量的個(gè)數(shù)。假如將區(qū)間映射生成的動(dòng)力系統(tǒng)稱為一級(jí)動(dòng)力系統(tǒng)；將平面映射生成的動(dòng)力系統(tǒng)稱為二維動(dòng)力系統(tǒng)；而對(duì)于偏微分方程描繪敘述的動(dòng)力系統(tǒng)則稱為無窮維動(dòng)力系統(tǒng)[42].從這個(gè)角度上，元胞自動(dòng)機(jī)屬于一類無窮維動(dòng)力系統(tǒng)，但在實(shí)際應(yīng)用中，即便使用計(jì)算機(jī)模擬也不可能計(jì)算無窮個(gè)變量，便有了元胞自動(dòng)機(jī)的簡化。通過上述元胞自動(dòng)機(jī)的同質(zhì)性、離散性、局部性等特點(diǎn)的簡單介紹，能夠得知不具備這些特點(diǎn)就不能稱為元胞自動(dòng)機(jī)，但在實(shí)際的應(yīng)用中，學(xué)者根據(jù)自個(gè)研究的實(shí)際需要，對(duì)模型進(jìn)行簡化和擴(kuò)展是能夠施行的。2.2元胞自動(dòng)機(jī)在旅客登機(jī)經(jīng)過中的運(yùn)用。2.2.1旅客登機(jī)經(jīng)過。登機(jī)效率的提升有賴于登機(jī)時(shí)間的縮短。假如想以更短的時(shí)間完成登機(jī)經(jīng)過，我們首先需要了解登機(jī)經(jīng)過中的影響因素，并對(duì)某些重要因素進(jìn)行分析。對(duì)于某個(gè)航班，詳細(xì)登機(jī)經(jīng)過。1、預(yù)登機(jī)區(qū)和登機(jī)口。從整個(gè)登機(jī)經(jīng)過來看，通常情況下，旅客聽到登機(jī)通知后，會(huì)向?qū)?yīng)的登機(jī)口聚集，這樣很容易造成登機(jī)口附近區(qū)域的擁擠，進(jìn)而使旅客進(jìn)入登機(jī)口的速度下降。因而，在登機(jī)口附近設(shè)置預(yù)登機(jī)區(qū)[24],對(duì)登機(jī)口附近的旅客數(shù)量進(jìn)行控制，進(jìn)而使旅客更快的進(jìn)入登機(jī)口以縮短登機(jī)時(shí)間；另外，多個(gè)登機(jī)口可以以加快登機(jī)速度[24].不僅如此，登機(jī)口的放行速度[14][24][43]與旅客進(jìn)入機(jī)艙的速度相協(xié)調(diào)，這樣能夠避免放行速度過快導(dǎo)致旅客在廊橋中的擁堵或因放行速度過慢導(dǎo)致的登機(jī)效率下降，進(jìn)而有效地減少登機(jī)時(shí)間。2、廊橋。旅客通過登機(jī)口后，進(jìn)入廊橋。由于廊橋空間較小，很難在機(jī)艙口組織旅客，因而機(jī)場會(huì)在登機(jī)口處要求旅客以某種順序排隊(duì)并通過，以保證旅客也以一樣的順序進(jìn)入機(jī)艙。通過登機(jī)口后，旅客就會(huì)進(jìn)入廊橋，由于旅客個(gè)體之間存在一定差異，因而旅客在廊橋中的步行速度也會(huì)有所不同，會(huì)使旅客的排列順序有所改變，進(jìn)而影響登機(jī)時(shí)間?，F(xiàn)有大多數(shù)的登機(jī)策略研究沒有考慮這里提到的在廊橋中旅客排列順序有所改變的情況，而更多的是是直接對(duì)旅客進(jìn)入機(jī)艙后的經(jīng)過進(jìn)行研究。3、登機(jī)艙門。旅客通過廊橋后會(huì)到達(dá)機(jī)艙門口，而登機(jī)艙門的開放數(shù)量[6]、登機(jī)艙門的使用[44]對(duì)于登機(jī)時(shí)間也有著很大的影響，尤其是空客A380等寬體客機(jī)，搭載旅客數(shù)量較多，影響會(huì)愈加明顯。4、機(jī)艙。對(duì)于旅客進(jìn)入機(jī)艙后的登機(jī)經(jīng)過則是影響登機(jī)效率的重要環(huán)節(jié)。旅客進(jìn)入機(jī)艙的速度對(duì)于登機(jī)時(shí)間的影響也很大[14][45],合理的速度能夠充分利用過道的空間，減少登機(jī)時(shí)間。旅客進(jìn)入機(jī)艙的順序是對(duì)登機(jī)時(shí)間產(chǎn)生影響最大的因素，由于旅客進(jìn)入機(jī)艙的順序不同，旅客在就坐經(jīng)過中被其他旅客阻擋的程度〔即干擾〕就有所不同，現(xiàn)有的大部分研究側(cè)重于旅客進(jìn)入機(jī)艙順序?qū)Φ菣C(jī)時(shí)間影響這一方面[6][8][12][13][14][17][18][19][20][26][23][29][46][47][48][49][50][51].在研究中，用干擾次數(shù)及時(shí)間來進(jìn)行分析。干擾主要分為兩種，一種是座位干擾，另一種是過道干擾[12].干擾最少，登機(jī)時(shí)間則最短。干擾受很多因素的影響，旅客進(jìn)入機(jī)艙的順序、旅客攜帶行李的數(shù)量[19][48][50]等影響干擾數(shù)量，旅客擺放單件行李花費(fèi)的時(shí)間、旅客在機(jī)艙中的行進(jìn)速度等行為特征[13][23][26]影響單個(gè)干擾時(shí)間。2.2.2元胞自動(dòng)機(jī)與旅客登機(jī)經(jīng)過的結(jié)合。本章的第一節(jié)和第二節(jié)分別對(duì)元胞自動(dòng)機(jī)的基本理論和旅客登機(jī)經(jīng)過進(jìn)行了介紹，本文對(duì)登機(jī)問題的研究是從第一名旅客到達(dá)登機(jī)艙門處到所有旅客就坐的整個(gè)經(jīng)過，將元胞自動(dòng)機(jī)與該登機(jī)經(jīng)過結(jié)合，通過仿真，就能夠得出使用不同機(jī)艙門、采用不同旅客放行速度以及不同登機(jī)次序的旅客登機(jī)時(shí)間。旅客是旅客登機(jī)經(jīng)過中的最基本實(shí)體，通過描繪敘述旅客在登機(jī)經(jīng)過中的行進(jìn)狀態(tài)，進(jìn)而對(duì)總登機(jī)時(shí)間進(jìn)行計(jì)算。旅客在機(jī)艙中的行進(jìn)行為是非常復(fù)雜的，本文將旅客在機(jī)艙內(nèi)的行進(jìn)行為簡單劃分為行進(jìn)、主動(dòng)停止和被動(dòng)停止三種，這樣的行進(jìn)行為能夠使用元胞自動(dòng)機(jī)的184號(hào)規(guī)則來描繪敘述。下面對(duì)元胞自動(dòng)機(jī)的184規(guī)則進(jìn)行扼要介紹。Wolfram在上世紀(jì)年代利用計(jì)算機(jī)模擬對(duì)一維元胞自動(dòng)機(jī)的種規(guī)則做了具體研究?！?〕對(duì)于初等元胞自動(dòng)機(jī)，華而不實(shí)變量有三個(gè)，每個(gè)變量取兩個(gè)狀態(tài)值，就有2*2*2=8種組合，只要給出在這八個(gè)自變量組合上的值，f就完全確定了。例如一下映射便是華而不實(shí)一個(gè)規(guī)則：以上八個(gè)組合分別對(duì)應(yīng)0或1,所以這樣的組合共有82=256種。184號(hào)規(guī)則就是這256種規(guī)則的一種，演示規(guī)則如此圖2-5所示，模型中代表有車的黑色塊1用表示，代表無車的白色塊用0表示。t時(shí)刻，假如第n輛車的前方為空，則該車前進(jìn)一格；假如第n輛車的前方被第n+1輛車所占，則該車原地不動(dòng)，即便本時(shí)間步里第n+1輛車離開前方元胞，該車也保持不動(dòng)。元胞自動(dòng)機(jī)的184規(guī)則起初用于研究交通運(yùn)輸問題，在本文中對(duì)于描繪敘述機(jī)艙中旅客行進(jìn)、主動(dòng)停止和被動(dòng)停止三種狀態(tài)是一種切實(shí)可行的方式方法，因而本文采取元胞自動(dòng)機(jī)的184號(hào)規(guī)則來編寫仿真程序