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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

本文編號(hào)：2865872