膜系統(tǒng)是受生物細胞和組織、器官等啟發(fā)產(chǎn)生的新的并行計算模型,它的提出引發(fā)了一大批學(xué)者的研究熱潮。其最大的特點是具有分布式和極大并行性,可以用空間的復(fù)雜度來換取時間的復(fù)雜度,從而大大縮短算法運行的時間。很多研究學(xué)者嘗試用膜系統(tǒng)來實現(xiàn)或者改進各種編程算法,運用膜系統(tǒng)特有的優(yōu)勢來降低算法的時間復(fù)雜性,以求獲得更快的運行速度。粒子群算法是智能算法的其中一種,它是受鳥群飛行時的狀態(tài)啟發(fā)產(chǎn)生的智能優(yōu)化算法,因為算法比較簡單、收斂速度比較快等特點,粒子群算法在提出之后迅速成為了炙手可熱的話題,被國內(nèi)外研究學(xué)者廣泛用于解決實際應(yīng)用問題,其應(yīng)用范圍涉及了人工智能、計算機科學(xué)、統(tǒng)計規(guī)劃等多個領(lǐng)域。但由于粒子群算法在運行過程中很容易陷入局部最優(yōu),所以現(xiàn)在很多國內(nèi)外研究者在研究粒子群算法的優(yōu)化問題。本文針對粒子群算法存在的缺點,將改進的遺傳算法嵌入其中,并與膜系統(tǒng)相結(jié)合,提出了新的運行算法。車間調(diào)度是一個解決組合優(yōu)化問題的過程,在企業(yè)面臨各種約束限制下,對車間生產(chǎn)的各道工序進行合理的規(guī)劃和分配,尋找到一個具有更少生產(chǎn)時間或者更低成本消耗的生產(chǎn)流程,從而達到提高生產(chǎn)效率的目的。車間調(diào)度是一個公認的NP-Hard難題,因為涉及到的變量和限制條件較多,使其求解變得比較復(fù)雜。本文將提出的新算法應(yīng)用于不同規(guī)模的作業(yè)車間調(diào)度問題上,結(jié)果證明該算法可以有效地解決JSSP。本文的主要創(chuàng)新點如下:(1)設(shè)計了復(fù)合型鏈式組織P系統(tǒng)(CTP)。首先提出了正反向單鏈形式的組織結(jié)構(gòu),所有細胞單向連接成一條鏈,鏈上的細胞之間可以單一正向和單一反向交流。其次將細胞型P系統(tǒng)和組織型P系統(tǒng)的性質(zhì)和功能相結(jié)合,使得組織中的每個細胞都具有活性膜的性質(zhì),即衍生性和溶解性。最后將提出的新組織結(jié)構(gòu)用于結(jié)合后的系統(tǒng)中,設(shè)計了CTP系統(tǒng),在新系統(tǒng)中,細胞的活動更加靈活,信息的交流更加方便。(2)將克隆選擇策略運用到遺傳算法的選擇操作中,結(jié)合精英選擇策略,保留匹配度最佳個體,按一定比例將匹配度低的抗體用匹配度高的克隆替換,再進行輪盤賭選擇,選出可行解集合。用此法可以選出質(zhì)量比較高的可行解,使算法的收斂速度被縮短。同時,在交叉操作中,設(shè)定一個閾值,使其與重合度相比較,根據(jù)比較結(jié)果決定是否進行交叉操作。該閾值約束提高了解的多樣性,降低了算法陷入局部最優(yōu)的概率。(3)在PSO算法中,首先基于收縮因子改進慣性權(quán)重,再與改進的遺傳算法相結(jié)合,使粒子的全局及局部搜索能力得到了平衡,提升了精確度。同時將提出的復(fù)合型鏈式組織P系統(tǒng)與改進后的PSO算法結(jié)合,利用P系統(tǒng)的極大并行性和分布式特點,大大提高了算法的運行速度。
【學(xué)位單位】：山東師范大學(xué)
【學(xué)位級別】：碩士
【學(xué)位年份】：2020
【中圖分類】：F273;F224
【部分圖文】：

山東師范大學(xué)碩士學(xué)位論文13第二章復(fù)合型鏈式組織P系統(tǒng)（CTP）本章提出了一種新型的P系統(tǒng)，該系統(tǒng)是以組織P系統(tǒng)為基礎(chǔ)系統(tǒng)，結(jié)合細胞型P系統(tǒng)活性膜性質(zhì)和鏈式P系統(tǒng)鏈式結(jié)構(gòu)，設(shè)計了一種復(fù)合型鏈式組織P系統(tǒng)(CTP)，分別從系統(tǒng)的結(jié)構(gòu)、規(guī)則和計算能力三方面進行詳細闡述。2.1CTP系統(tǒng)構(gòu)建2.1.1正反向單鏈結(jié)構(gòu)鏈式P系統(tǒng)是組織P系統(tǒng)的一種擴展模型，所有的細胞以單向或雙向連接方式形成一條鏈，本章參考鏈式P系統(tǒng)的鏈式結(jié)構(gòu)，設(shè)計了一個正反向單鏈的組織結(jié)構(gòu)，該鏈式結(jié)構(gòu)同時存在單一正向連接和單一反向連接，其結(jié)構(gòu)圖例如圖2-1：圖2-1正反向單鏈結(jié)構(gòu)上圖是一個由四個細胞構(gòu)成的正反向鏈式結(jié)構(gòu)，其中正向鏈式結(jié)構(gòu)體現(xiàn)為四個細胞之間的信息交流是由前到后的順序單向進行的，反向鏈式結(jié)構(gòu)則體現(xiàn)為最后一個細胞與前面三個細胞的信息交流從后往前的，與細胞的連接方向相反。假設(shè)細胞1是系統(tǒng)的起始細胞，細胞4為系統(tǒng)的終止細胞，則細胞1產(chǎn)生的對象只能運用交流規(guī)則通過連接渠道傳遞給細胞2，細胞2接收對象后運用規(guī)則完成對象進化，生成的新對象只能正向傳遞給細胞3。同理，細胞3想要傳遞的所有對象只能給細胞4，但細胞4內(nèi)的對象，可以通過與其他三個細胞的連接渠道傳送到任意一個細胞，當進化結(jié)束時，細胞4會將對象直接輸出到環(huán)境中。前三個細胞的信息傳遞方向與細胞的連接方向相同，將其稱為正向單鏈，由于細胞4是鏈上的最后一個細胞，所以它的信息交流方向與細胞連接的方向是相反的，稱為反向單鏈。2.1.2CTP系統(tǒng)設(shè)計上一小節(jié)介紹了設(shè)計的正反向單鏈結(jié)構(gòu)，本節(jié)將完整地、詳細地闡述復(fù)合型鏈式組織

山東師范大學(xué)碩士學(xué)位論文14P系統(tǒng)。細胞型P系統(tǒng)是以單個細胞為單位完成計算的，細胞膜具有衍生性，可以直接在膜內(nèi)生成新膜，也可以直接在膜內(nèi)溶解，而組織型P系統(tǒng)則是由多個細胞按照一定的結(jié)構(gòu)組成的，組織內(nèi)的細胞一般不具有活性膜的性質(zhì)。本文將細胞型P系統(tǒng)活性膜性質(zhì)運用在組織P系統(tǒng)中，構(gòu)成一種復(fù)合型組織P系統(tǒng)，通過運行衍生規(guī)則和溶解規(guī)則，可以實現(xiàn)系統(tǒng)中單個細胞的衍生和溶解，更大限度地發(fā)揮P系統(tǒng)的極大并行性。將正反向鏈式結(jié)構(gòu)用于復(fù)合型組織P系統(tǒng)，可以簡化系統(tǒng)的拓撲結(jié)構(gòu)，增強系統(tǒng)的簡潔性，使計算過程更加簡單明了。CTP系統(tǒng)的拓撲結(jié)構(gòu)如圖2-2：圖2-2CTP結(jié)構(gòu)圖上圖是一個含有n個膜的復(fù)合型鏈式組織P系統(tǒng)，h是整個系統(tǒng)存在的環(huán)境，膜c1為系統(tǒng)初始膜（第一個細胞），用于輸入數(shù)據(jù)和初始化參數(shù)，膜cn為系統(tǒng)的輸出膜（最后一個細胞），其余的膜均為進化膜。所有膜按照正反向鏈式結(jié)構(gòu)進行連接，每個膜可以根據(jù)運行要求執(zhí)行膜的衍生規(guī)則和溶解規(guī)則，生成新膜（用虛線圓形表示）或者將膜溶解。外層膜ci內(nèi)生成的各個新膜之間通過膜ci內(nèi)的環(huán)境進行信息交流，而外層膜ci之間則通過連接渠道直接進行信息交換。根據(jù)P系統(tǒng)的形式化定義，將一個含有m個細胞的CTP系統(tǒng)定義為：()120=,,,,,,,,,,miORsynQi+其中：（1）O是對象的非空有限集，是一個字母表；（2）12,,,m是系統(tǒng)中含有的m個細胞，1,2,,m為細胞個數(shù)的標簽；（3）,+表示了系統(tǒng)的正反向鏈式結(jié)構(gòu)，+表示了正向鏈式結(jié)構(gòu)，表示了反向鏈式結(jié)構(gòu)；

山東師范大學(xué)碩士學(xué)位論文24（6）對上一步形成的新種群，對抗體的字符串隨機選取一個位點采取取反操作，實現(xiàn)基因的突變，形成新的抗體種群。（7）滿足終止條件，輸出結(jié)果，否則，返回第三步，進行新一輪的迭代，直到迭代終止。（8）結(jié)束運算�；诳寺∵x擇的遺傳算法的流程圖如圖3-1：圖3-1CSGA算法流程圖
【參考文獻】

相關(guān)期刊論文 前5條

1 葛安華;周晏明;李權(quán)章;;改進遺傳算法求解作業(yè)車間提前/拖期調(diào)度問題[J];森林工程;2013年03期

2 王軍強;陳劍;翟穎妮;張松飛;楊建斌;孫樹棟;;擾動情形下瓶頸利用對作業(yè)車間調(diào)度的影響[J];計算機集成制造系統(tǒng);2010年12期

3 馬鑫;李琴;;克隆選擇算法的研究與實現(xiàn)[J];改革與開放;2010年12期

4 吳澄;現(xiàn)代集成制造系統(tǒng)的理論基礎(chǔ)——一類復(fù)雜性問題及其求解[J];計算機集成制造系統(tǒng)-CIMS;2001年03期

5 何霆,劉飛,馬玉林,楊海;車間生產(chǎn)調(diào)度問題研究[J];機械工程學(xué)報;2000年05期

相關(guān)博士學(xué)位論文 前3條

1 王鵬飛;群智能優(yōu)化算法及在流水車間調(diào)度問題中的應(yīng)用研究[D];吉林大學(xué);2019年

2 周瑞紅;基于群智能優(yōu)化理論的聚類改進方法及應(yīng)用研究[D];吉林大學(xué);2017年

3 薛潔;兩類生物計算問題及其在數(shù)據(jù)挖掘中的應(yīng)用研究[D];山東師范大學(xué);2015年

相關(guān)碩士學(xué)位論文 前7條

1 陳毅;L公司柔性車間調(diào)度與預(yù)防性維護集成優(yōu)化[D];貴州大學(xué);2019年

2 張超;粒子群算法與蟻群算法的改進研究[D];西安工程大學(xué);2019年

3 馬慶吉;基于改進灰狼算法的柔性作業(yè)車間調(diào)度方法研究[D];華中科技大學(xué);2019年

4 張曉寒;基于混合粒子群算法的車間調(diào)度研究及管理系統(tǒng)設(shè)計[D];武漢科技大學(xué);2019年

5 任彩樂;基于候鳥優(yōu)化算法的混合流水車間調(diào)度問題研究[D];華中科技大學(xué);2019年

6 任碩;基于膜計算的輸電線路路徑優(yōu)化問題的研究與應(yīng)用[D];山東師范大學(xué);2015年

7 孫杰;細胞型膜系統(tǒng)在聚類算法中的研究[D];山東師范大學(xué);2014年

本文編號：2865872