畢業(yè)設(shè)計(jì)（論文）不可行染色體轉(zhuǎn)換算法VB語言設(shè)計(jì)與實(shí)現(xiàn)

1、煙臺(tái)大學(xué)畢業(yè)論文(設(shè)計(jì))分類號(hào) 編號(hào)煙 臺(tái) 大 學(xué)畢 業(yè) 論 文（設(shè) 計(jì)）不可行染色體轉(zhuǎn)換算法設(shè)計(jì)與實(shí)現(xiàn)infeasible chromosome conversion algorithm design and implementation申請(qǐng)學(xué)位： 學(xué)士學(xué)位 院 系：機(jī)電汽車工程學(xué)院 專 業(yè)：測(cè)控技術(shù)與儀器 姓 名： 學(xué) 號(hào)： 指導(dǎo)老師： 2010年6月10日煙臺(tái)大學(xué)不可行染色體轉(zhuǎn)換算法設(shè)計(jì)與實(shí)現(xiàn)姓 名： 導(dǎo) 師： 2010年6月10日煙臺(tái)大學(xué) 摘要： 本文介紹了遺傳算法、生產(chǎn)調(diào)度、不可行染色體等相關(guān)知識(shí)。在已存在的不可行染色體轉(zhuǎn)換方法中，篩選出兩種方法，利用vb6.0軟件開發(fā)平臺(tái)來實(shí)現(xiàn)不可

2、行染色體的轉(zhuǎn)換，并且對(duì)轉(zhuǎn)換結(jié)果進(jìn)行了對(duì)比。關(guān)鍵詞：遺傳算法; 不可行染色體; 轉(zhuǎn)換方法; 綜合作業(yè)調(diào)度問題abstract：this article describes the knowledge of genetic algorithm, production scheduling,infeasible chromosomes. in the methods of infeasible chromosome conversion already exists, the selected two methods, using vb6.0 software development platfor

3、m to implement the conversion of infeasible chromosome, and compared the conversion results . keyword: genetic algorithm; infeasible chromosome;conversion method ;complete job shop scheduling problem 目錄目錄4第一章 緒 論51.1遺傳算法51.2生產(chǎn)調(diào)度的概念61.3生產(chǎn)調(diào)度問題的研究意義61.4生產(chǎn)調(diào)度的性能指標(biāo)71.5生產(chǎn)調(diào)度問題的特點(diǎn)71.6 cjssp概念8第二章 不可行染色體轉(zhuǎn)換概念及

4、方法92.1不可行解與轉(zhuǎn)換的概念92.2對(duì)轉(zhuǎn)換方法的要求92.3基于路徑表的掃描換位102.4基于根右移的子樹歸位12第三章 不可性染色體轉(zhuǎn)換算法實(shí)現(xiàn)軟件設(shè)計(jì)143.1界面設(shè)計(jì)143.2程序設(shè)計(jì)153.2.1定義變量163.2.2算法共用程序設(shè)計(jì)163.2.3基于路徑表的掃描換位的程序設(shè)計(jì)203.2.4基于根右移的子樹歸位的程序設(shè)計(jì)21第四章 實(shí)驗(yàn)結(jié)果234.1實(shí)驗(yàn)結(jié)果23畢業(yè)設(shè)計(jì)總結(jié)26致 謝27參考文獻(xiàn)28附錄1 程序29附錄2 軟件界面33第一章 緒 論隨著經(jīng)濟(jì)的發(fā)展，車間生產(chǎn)調(diào)度問題是當(dāng)今科學(xué)研究的熱點(diǎn)，近十幾年來，面向用戶個(gè)性化需求的定制生產(chǎn)模式開始成為制造的主流，對(duì)市場(chǎng)需求的快速反

5、應(yīng)能力開始成為企業(yè)能否在激烈的市場(chǎng)競(jìng)爭中占得一席之地的重要，因此，柔性快速的生產(chǎn)調(diào)度就顯得格外重要。然而，現(xiàn)今國內(nèi)的大部分企業(yè)主要依靠經(jīng)驗(yàn)豐富的工人手工安排調(diào)度計(jì)劃。在調(diào)度任務(wù)規(guī)模較大且動(dòng)態(tài)多變的環(huán)境中，單純的手工調(diào)度已無法滿足市場(chǎng)的需求。因此，利用科學(xué)理論手段進(jìn)行車間作業(yè)調(diào)度是十分必要的。遺傳算法作為解決生產(chǎn)調(diào)度問題的工具，起著不可替代的作用。本文以綜合作業(yè)調(diào)度問題(complete job shop scheduling problem , cjssp) 遺傳算法中不可行染色體為對(duì)象,針對(duì)了2 種不同轉(zhuǎn)換方法,利用vb6.0軟件開發(fā)平臺(tái)進(jìn)行了轉(zhuǎn)換實(shí)現(xiàn)，并對(duì)結(jié)果進(jìn)行了分析。1.1遺傳算法遺傳

6、算法（ga：genetic algorithm）是一類借鑒生物界的進(jìn)化規(guī)律（適者生存，優(yōu)勝劣汰遺傳機(jī)制）演化而來的隨機(jī)化搜索方法。它是由美國的j.holland教授1975年首先提出，其主要特點(diǎn)是直接對(duì)結(jié)構(gòu)對(duì)象進(jìn)行操作，不存在求導(dǎo)和函數(shù)連續(xù)性的限定；具有內(nèi)在的隱并行性和更好的全局尋優(yōu)能力；采用概率化的尋優(yōu)方法，能自動(dòng)獲取和指導(dǎo)優(yōu)化的搜索空間，自適應(yīng)地調(diào)整搜索方向，不需要確定的規(guī)則。算法（algorithm）是一系列解決問題的清晰指令，也就是說，能夠?qū)σ欢ㄒ?guī)范的輸入，在有限時(shí)間內(nèi)獲得所要求的輸出。如果一個(gè)算法有缺陷，或不適合于某個(gè)問題，執(zhí)行這個(gè)算法將不會(huì)解決這個(gè)問題。不同的算法可能用不同的時(shí)間、

7、空間或效率來完成同樣的任務(wù)。一個(gè)算法的優(yōu)劣可以用空間復(fù)雜度與時(shí)間復(fù)雜度來衡量。 算法可以理解為有基本運(yùn)算及規(guī)定的運(yùn)算順序所構(gòu)成的完整的解題步驟。或者看成按照要求設(shè)計(jì)好的有限的確切的計(jì)算序列，并且這樣的步驟和序列可以解決一類問題。 一個(gè)算法應(yīng)該具有以下五個(gè)重要的特征： 算法可以使用自然語言、偽代碼、流程圖等多種不同的方法來描述。 1、有窮性一個(gè)算法必須保證執(zhí)行有限步之后結(jié)束； 2、確切性算法的每一步驟必須有確切的定義； 3、輸入一個(gè)算法有0個(gè)或多個(gè)輸入，以刻畫運(yùn)算對(duì)象的初始情況，所謂0個(gè)輸入是指算法本身定除了初始條件； 4、輸出一個(gè)算法有一個(gè)或多個(gè)輸出，以反映對(duì)輸入數(shù)據(jù)加工后的結(jié)果。沒有輸出的算

8、法是毫無意義的； 5、可行性算法原則上能夠精確地運(yùn)行，而且人們用筆和紙做有限次運(yùn)算后即可完成。 計(jì)算機(jī)科學(xué)家尼克勞斯-沃思曾著過一本著名的書數(shù)據(jù)結(jié)構(gòu)十算法= 程序，可見算法在計(jì)算機(jī)科學(xué)界與計(jì)算機(jī)應(yīng)用界的地位。遺傳算法ga的基本原理是，產(chǎn)生若干代表問題候選解的成員，并組成一個(gè)群體，按照某一評(píng)價(jià)函數(shù)或算法對(duì)群體中的每個(gè)成員進(jìn)行評(píng)估，評(píng)估結(jié)果代表解的良好性。按照適者生存、優(yōu)勝劣汰的原則，群體中的某一成員愈適合，則愈有可能產(chǎn)生后代。利用遺傳操作對(duì)群體中的成員進(jìn)行遺傳操作，產(chǎn)生新的后代，這種后代能繼承雙親的特征。對(duì)后代進(jìn)行評(píng)估，并將其放入群體，代替上一代中較弱的成員(非良好解)。此過程反復(fù)執(zhí)行，這構(gòu)成一

9、代一代的群體。隨著遺傳過程的不斷進(jìn)行，越來越良好的解就可以得到。一些學(xué)者經(jīng)過研究發(fā)現(xiàn)，遺傳算法比經(jīng)典的啟發(fā)式算法好，同時(shí)遺傳算法比傳統(tǒng)的搜索技術(shù)優(yōu)更強(qiáng)的魯棒性，因?yàn)樗粌H能解決某一特定問題，而且可以適應(yīng)不同的問題形式。遺傳算法的優(yōu)越性歸功于它與傳統(tǒng)搜索方法不同的特定結(jié)構(gòu)：(1)ga的工作問題是編碼，對(duì)搜索問題的限制極少，對(duì)函數(shù)的一些約束條件象連續(xù)性、可導(dǎo)性等不作要求，減少了要解決的問題的復(fù)雜性。(2)ga是同時(shí)搜索解空間內(nèi)的許多點(diǎn)，因而可以有效地防止搜索過程中收斂到局部最優(yōu)解，并獲得全局最優(yōu)解，與其它單點(diǎn)搜索的方法相比，在計(jì)算時(shí)間上也有較大的優(yōu)勢(shì)。(3)ga使用遺傳操作時(shí)是按概率在解空間進(jìn)行搜

10、索，因而既不同于隨機(jī)查找，也不同于枚舉查找那樣盲目的窮舉，而是一種有目標(biāo)、有方向的啟發(fā)式搜索1.2生產(chǎn)調(diào)度的概念生產(chǎn)調(diào)度就是組織執(zhí)行生產(chǎn)進(jìn)度計(jì)劃的工作。具體來說是在滿足某些約束(作業(yè)的先后關(guān)系、預(yù)定的完成時(shí)間、最早開始時(shí)間和資源能力等)的條件下對(duì)操作(作業(yè))的排序，按照排序的次序給它們分配資源和時(shí)間，并且使某個(gè)執(zhí)行目標(biāo)達(dá)到最優(yōu)(如總的執(zhí)行時(shí)間、拖期時(shí)間和生產(chǎn)費(fèi)用等)。生產(chǎn)調(diào)度問題一般可以描述為：針對(duì)某項(xiàng)可分解的工作，在一定約束條件下，如何安排其組成部分(操作)所占有的資源、加工時(shí)間、先后順序，以獲得產(chǎn)品制造時(shí)間或成本等最優(yōu)。影響調(diào)度問題的因素很多，正常情況下有：產(chǎn)品的投產(chǎn)期，交貨期(完成期)，

11、生產(chǎn)能力，加工順序，加工設(shè)備和原料的可用性，批量大小，加工路徑，成本限制等，這些都是所謂的約束條件。有些約束條件是必須要滿足的，如交貨期，生產(chǎn)能力等，而有些達(dá)到一定滿意度就行，如生產(chǎn)成本等，這些約束在進(jìn)行調(diào)度時(shí)可以作為確定性因素考慮。而對(duì)于設(shè)備故障，原料供應(yīng)變化，生產(chǎn)任務(wù)變化等非正常情況，都是事先不能預(yù)見的，在進(jìn)行調(diào)度時(shí)大都作為非確定性因素考慮。生產(chǎn)調(diào)度中涉及的工廠資源包括：原料、設(shè)備(加工、存儲(chǔ)、運(yùn)輸)、人力、資金、能源等。生產(chǎn)調(diào)度的性能指標(biāo)可以是成本最低、庫存費(fèi)最少、生產(chǎn)周期最短、生產(chǎn)切換最少、設(shè)備利用率最高、三廢(廢氣、廢水、廢渣)最少等。生產(chǎn)調(diào)度以生產(chǎn)進(jìn)度計(jì)劃為依據(jù)，生產(chǎn)進(jìn)度計(jì)劃要通過

12、生產(chǎn)調(diào)度來實(shí)現(xiàn)。生產(chǎn)調(diào)度的必要性是由工業(yè)企業(yè)生產(chǎn)活動(dòng)的性質(zhì)決定的。現(xiàn)代工業(yè)企業(yè)，生產(chǎn)環(huán)節(jié)多，協(xié)作關(guān)系復(fù)雜，生產(chǎn)連續(xù)性強(qiáng)，情況變化快，某一局部發(fā)生故障，或某一措施沒有按期實(shí)現(xiàn)，往往會(huì)波及整個(gè)生產(chǎn)系統(tǒng)的運(yùn)行。因此，加強(qiáng)生產(chǎn)調(diào)度工作，對(duì)于及時(shí)了解、掌握生產(chǎn)進(jìn)度，研究分析影響生產(chǎn)的各種因素，根據(jù)不同情況采取相應(yīng)對(duì)策，使差距縮小或恢復(fù)正常是非常重要的。1.3生產(chǎn)調(diào)度問題的研究意義企業(yè)為了適應(yīng)激烈的市場(chǎng)競(jìng)爭，相對(duì)靈活的生產(chǎn)方式逐漸成為主流，這對(duì)企業(yè)的生產(chǎn)管理的要求更加苛刻。為了獲得最大的經(jīng)濟(jì)效益，原來的生產(chǎn)計(jì)劃及僅憑經(jīng)驗(yàn)的管理方式已經(jīng)不能滿足現(xiàn)代生產(chǎn)的要求了，必須采用科學(xué)的方法對(duì)生產(chǎn)過程進(jìn)行優(yōu)化。生產(chǎn)管理

13、者所面臨的問題是：如何最優(yōu)的根據(jù)已經(jīng)具備的條件去安排生產(chǎn)以滿足市場(chǎng)上對(duì)產(chǎn)品的需求。有限資源的合理配置是人類社會(huì)所面臨的最基本經(jīng)濟(jì)學(xué)問題。學(xué)者們從不同的角度對(duì)于這方面進(jìn)行研究，產(chǎn)生了許多這類問題的不同的學(xué)科和理論，其中在生產(chǎn)領(lǐng)域產(chǎn)生了重要的生產(chǎn)調(diào)度理論。生產(chǎn)調(diào)度理論是針對(duì)制造車間生產(chǎn)計(jì)劃與控制的研究，關(guān)于它的研究涉及運(yùn)籌學(xué)、管理科學(xué)和應(yīng)用數(shù)學(xué)等，經(jīng)過近幾十年的發(fā)展，已經(jīng)形成了許多理論。在企業(yè)當(dāng)中得到了廣泛的應(yīng)用。這個(gè)理論體系應(yīng)用范圍廣泛，在一定程度上促進(jìn)了社會(huì)經(jīng)濟(jì)的發(fā)展。生產(chǎn)調(diào)度主要用于解決工件在機(jī)器上的調(diào)度和資源分配問題，可以大大提高生產(chǎn)效率和資源利用率，進(jìn)而增加企業(yè)的競(jìng)爭能力。因此生產(chǎn)調(diào)度對(duì)

14、制造企業(yè)車間作業(yè)調(diào)度問題進(jìn)行研究具有重要的現(xiàn)實(shí)意義，它是實(shí)現(xiàn)有限資源在車間作業(yè)當(dāng)中優(yōu)化配置的重要工具。但是目前在我國許多多企業(yè)生產(chǎn)管理技術(shù)及手段落后，缺乏系統(tǒng)科學(xué)的生產(chǎn)調(diào)度方法，生產(chǎn)計(jì)劃和調(diào)度安排仍然依靠經(jīng)驗(yàn)，資源利用不合理，對(duì)市場(chǎng)反映不夠靈敏，嚴(yán)重影響了企業(yè)的經(jīng)濟(jì)效益。從國外引進(jìn)了的一些較為先進(jìn)的生產(chǎn)管理技術(shù)和信息系統(tǒng)只在一定范圍內(nèi)得到了應(yīng)用，大多數(shù)制造企業(yè)的車間生產(chǎn)計(jì)劃和調(diào)度還處在依賴車間管理人員工作經(jīng)驗(yàn)的人工安排階段。1.4生產(chǎn)調(diào)度的性能指標(biāo)實(shí)際生產(chǎn)調(diào)度的性能指標(biāo)大致可以歸結(jié)為三類：(1) 最大能力指標(biāo)包括最大生產(chǎn)率、最短生產(chǎn)周期等，它們都可以歸結(jié)為在固定或者無限的產(chǎn)品需求的前提下，最大

15、化生產(chǎn)能力以提高經(jīng)濟(jì)效益。 在執(zhí)行著一條指標(biāo)時(shí)還要考慮到質(zhì)量，不能把最大生產(chǎn)(2)最低(高)成本指標(biāo)包括最大利潤、最小運(yùn)行費(fèi)用、最小投資、最大收益等，其中收益指產(chǎn)品銷售收入，運(yùn)行費(fèi)用包括庫存成本，生產(chǎn)成本和缺貨損失。(3)客戶滿意度指標(biāo)包括最短的延遲，最小的提前或者拖期懲罰等。在傳統(tǒng)的調(diào)度中，一般以平均流通時(shí)間最小、制造周期最短、滿足交貨期為調(diào)度目標(biāo)，而在實(shí)際生產(chǎn)中，由于提前完成的產(chǎn)品必須保存到交貨期，而拖期產(chǎn)品必須交付違約金，因此，在實(shí)際調(diào)度中經(jīng)?？紤]“提前”或者“拖后”的懲罰。1.5生產(chǎn)調(diào)度問題的特點(diǎn)實(shí)際的調(diào)度問題有以下特點(diǎn)：1復(fù)雜性由于裝卸作業(yè)、裝卸設(shè)備、庫場(chǎng)、搬運(yùn)系統(tǒng)之間相互影響、相互

16、作用，每個(gè)作業(yè)又要考慮它的到達(dá)時(shí)間、裝卸時(shí)間、準(zhǔn)備時(shí)間、操作順序、交貨期等，因而相當(dāng)復(fù)雜。而且調(diào)度問題是在等式或不等式約束下求性能指標(biāo)的優(yōu)化，在計(jì)算量上往往是np(nondeterministic polynomia，多項(xiàng)式非確定性問題)完全問題，即隨著問題規(guī)模的增大，對(duì)于求解最優(yōu)化的計(jì)算量呈指數(shù)增長，使得一些常規(guī)的最優(yōu)化方法往往無能為力。即使對(duì)于單臺(tái)機(jī)床加工問題，如果有n個(gè)工件而每個(gè)工件只考慮加工時(shí)間以及與操作序列有關(guān)的安裝時(shí)間，則這個(gè)問題就和n個(gè)城市的tsp(traveling salesman problem，旅行商問題)問題等價(jià)。對(duì)于一般加工系統(tǒng)，問題更加復(fù)雜。2動(dòng)態(tài)隨機(jī)性在實(shí)際的生產(chǎn)

17、調(diào)度系統(tǒng)中存在很多隨機(jī)的和不確定的因素，比如作業(yè)到達(dá)時(shí)間的不確定性、作業(yè)的加工時(shí)間也有一定的隨機(jī)性，而且生產(chǎn)系統(tǒng)中常出現(xiàn)一些突發(fā)偶然事件，如設(shè)備的損壞或修復(fù)、作業(yè)交貨期的改變等。3多目標(biāo)性實(shí)際的計(jì)劃調(diào)度往往是多目標(biāo)的，是一個(gè)多目標(biāo)決策問題，有時(shí)候這些目標(biāo)間可能發(fā)生沖突。kiran等人將調(diào)度目標(biāo)分三類：基于作業(yè)交貨期的目標(biāo)、基于作業(yè)完成時(shí)間的目標(biāo)、基于生產(chǎn)成本的目標(biāo)。這種多目標(biāo)性導(dǎo)致調(diào)度的復(fù)雜性和計(jì)算量急劇增加?；跁r(shí)間和作業(yè)交貨期的目標(biāo)，主要包括任務(wù)的生產(chǎn)周期最短，完成日期與交貨期最接近，任務(wù)在制造系統(tǒng)中的總等待時(shí)間最短等；基于成本的目標(biāo)主要考慮如何減少生產(chǎn)過程中的資金占用和怎樣合理利用資源，

18、使各個(gè)生產(chǎn)環(huán)節(jié)負(fù)荷均勻，保證生產(chǎn)的穩(wěn)定性。1.6 cjssp概念綜合作業(yè)調(diào)度問題(complete job shop scheduling problem , cjssp）是生產(chǎn)調(diào)度問題的問題之一?；究啥x為：個(gè)產(chǎn)品，每個(gè)產(chǎn)品有不相等的個(gè)裝配體，每個(gè)裝配體有不相等的個(gè)工序，在臺(tái)不同的機(jī)器上加工，已知個(gè)產(chǎn)品的結(jié)構(gòu)、各工序的制造時(shí)間和各裝配體在各機(jī)器上的制造次序約束，要求確定與產(chǎn)品結(jié)構(gòu)和工藝條件相容的各機(jī)器上所有裝配體的制造開始時(shí)間或完成時(shí)間或制造次序，使制造性能達(dá)到最優(yōu)。它作為生產(chǎn)調(diào)度問題之一，可以應(yīng)用到很多領(lǐng)域，在交通運(yùn)輸方面，可以用于車輛或者船、飛機(jī)等交通工具，貨物，司機(jī)等方面的優(yōu)化配置。

19、在人力資源管理方面分配根據(jù)人的特點(diǎn)、時(shí)間等因素分配任務(wù)。在市場(chǎng)營銷方面可用于優(yōu)化配置資金、人員、廣播電視傳媒方面的配置。本文的主要內(nèi)容就是針對(duì)cjssp問題中的一個(gè)環(huán)節(jié)進(jìn)行討論。第二章 不可行染色體轉(zhuǎn)換概念及方法遺傳算法是解決生產(chǎn)調(diào)度問題的重要方法之一，為了實(shí)現(xiàn)資源優(yōu)化配置，以基因代表工序，用染色體代表產(chǎn)品的工序組成。2.1不可行解與轉(zhuǎn)換的概念在產(chǎn)品的生產(chǎn)過程中，會(huì)遇到工序之間的加工時(shí)間前后的要求，在產(chǎn)品所需的零件沒有被加工出來之前，產(chǎn)品不允許組裝、再加工；同一零件的各個(gè)工序之間加工時(shí)間前后往往也有要求。對(duì)于加工這些都是約束。簡單舉例來講：以一條染色體代表一輛汽車的加工過程，基因代表產(chǎn)品所需的

20、零件工序，只有零件工序符合加工要求的順序，才能夠派工，否則要進(jìn)行轉(zhuǎn)換，使染色體內(nèi)基因順序符合約束條件。根據(jù)以上內(nèi)容，學(xué)者做出了以下定義：1.不可行染色體：染色體沒有基因冗余或缺損,但是違反了約束,表示的是一個(gè)不可行解,稱為不可行染色體。通常簡稱為不可行解,也即染色體解碼出來的解在給定問題的可行區(qū)域之外。就是例子中加工順序錯(cuò)誤。2.非法染色體：染色體存在基因缺損或冗余,不能表示一個(gè)解,稱為非法染色體。通常簡稱為非法解,也即某個(gè)染色體不能代表給定問題的解。在例子中表現(xiàn)為缺少零件工序。3.染色體轉(zhuǎn)換：使不可行染色體轉(zhuǎn)化為正常的可行染色體,即糾正染色體中所有違反工藝約束的情況,稱為染色體轉(zhuǎn)換。轉(zhuǎn)換只糾

21、正違反工藝約束的情況,盡量不改變?nèi)旧w中的其余信息。2.2對(duì)轉(zhuǎn)換方法的要求理想的轉(zhuǎn)換方法應(yīng)該做到,在保證糾正所有違反的約束情況下,要盡可能少地改變轉(zhuǎn)換前的染色體,使不可行染色體中包含的信息丟失最小。因此,轉(zhuǎn)換方法應(yīng)該具有下述性能: 第一，只轉(zhuǎn)換不可行染色體,對(duì)可行染色體不進(jìn)行轉(zhuǎn)換。換句話說,可行染色體轉(zhuǎn)換前后完全相同。第二，只對(duì)染色體進(jìn)行純粹的消除違反約束所必需的改變。第三，轉(zhuǎn)換前后的種群要具備同樣的多樣性,即多樣性等效轉(zhuǎn)換。本來多樣性高的種群,轉(zhuǎn)換后仍然高;原來低的轉(zhuǎn)換后仍然低,類似于修舊如舊的原則。第四，快速高效。因?yàn)檫@是對(duì)所有染色體都要應(yīng)用的過程,尤其當(dāng)問題規(guī)模比較大時(shí),時(shí)間開銷是必須要

22、考慮的一個(gè)問題。當(dāng)然,解決組合優(yōu)化問題時(shí),要根據(jù)實(shí)際需要進(jìn)行選擇或設(shè)計(jì)?？紤]到遺傳算法中時(shí)間花費(fèi)與性能的關(guān)聯(lián),要綜合考慮質(zhì)量與效率要求。至于轉(zhuǎn)換方法本身的復(fù)雜性,可計(jì)入時(shí)間開銷中。 不可性染色體轉(zhuǎn)換算法的設(shè)計(jì)已經(jīng)存在，經(jīng)過篩選，以下兩種算法是比較簡單地算法思想，在第五章中將對(duì)兩種算法進(jìn)行軟件實(shí)現(xiàn)，下面介紹一下這兩種算法的思路。2.3基于路徑表的掃描換位基于路徑表的掃描換位（cip: circulatory interchanging based on pathway）以圖2.3.1所示產(chǎn)品為例說明總的轉(zhuǎn)換思想。首先建立對(duì)每一個(gè)基因的“直系關(guān)系”表，也可稱為“父子關(guān)系”表，來說明裝配路徑，4的父

23、項(xiàng)是2，2的父項(xiàng)是1，1是4的頂級(jí)父項(xiàng)，建立的關(guān)系就為：1-2-4。在不可行染色體中，對(duì)每一基因建立完整“直系關(guān)系”表，從左至右進(jìn)行掃描，用第一個(gè)基因依次對(duì)后面的每一個(gè)基因進(jìn)行比較，如果等于后面的基因的頂級(jí)父項(xiàng)，就交換位置，并且把交換到前面的基因的頂級(jí)父項(xiàng)刪除，因?yàn)橄麓伪容^時(shí)不需要在對(duì)該父項(xiàng)進(jìn)行比較，而是對(duì)刪除后出現(xiàn)的頂級(jí)父項(xiàng)進(jìn)行比較。刪除之后，針對(duì)第二個(gè)基因進(jìn)行下一輪的比較，如此循環(huán)，如果產(chǎn)品結(jié)構(gòu)的為n層，從左至右進(jìn)行掃描n-1遍后即可把不可行染色體轉(zhuǎn)換為可性染色體。12534圖2.3.1 產(chǎn)品結(jié)構(gòu)圖流程圖如下：選擇染色體基因bu（i）尋找其后面的子項(xiàng)判斷該項(xiàng)基因是否是其子項(xiàng)yn交換位置刪除

24、頂父項(xiàng)掃描是否n-1遍yn輸出可行染色體圖2.3.2圖2.3.1為產(chǎn)品結(jié)構(gòu)圖，舉例來說：需要轉(zhuǎn)換的染色體為：1，5，3，2，4，2建立父項(xiàng)表后： 1，1-2-5，1-3，1-2，1-2-4，1-2進(jìn)行掃描第i個(gè)基因依次與后面基因比較，根據(jù)比較結(jié)果在進(jìn)行處理： 1-2-5，1，1-3，1-2，1-2-4，1-2 2-5，1，1-3，1-2，1-2-4，1-2 2-5，1-3，1，1-2，1-2-4，1-2 2-5，3，1，1-2，1-2-4，1-2 2-5，3，1-2，1，1-2-4，1-2 2-5，3，2，1，1-2-4，1-2 2-5，3，2，1-2-4，1，1-2 2-5，3，2，2-4，

25、1，1-2 2-5，3，2，2-4，1-2，1 2-5，3，2，2-4，2，1 2-5，3，2，2-4，2，1第一遍掃描完成，下面第二遍掃描： 2-5，3，2-4，2，2，1 5，3，4，2，2，1以上最后一條數(shù)據(jù)就是符合裝配約束的派工序列，即可性染色體。在掃描過程中，所比較的基因不僅要與后面進(jìn)行比較，也要與前面進(jìn)行比較，例如上面得例子中2與前面的2-5進(jìn)行比較，處理結(jié)果是刪除2-5前面的2-，而不交換位置，這樣才能得出正確的結(jié)果。2.4基于根右移的子樹歸位再次以產(chǎn)品裝配圖4.1.1為例進(jìn)行說明：父串：1，1，2，2子串：2，3，4，5對(duì)于不可性染色體： 1，5，4，2，5，3，3，1，2，4

26、同樣建立“父子關(guān)系”表，之后為： 1，1-2-5，1-2-4，1-2，1-2-5，1-3，1-3，1，1-2，1-2-4提取根為1的樹枝（即全部基因，為了實(shí)現(xiàn)第五章的循環(huán)程序，把樹也作為一樹枝處理）： 1，1-2-5，1-2-4，1-2，1-2-5，1-3，1-3，1，1-2，1-2-4將根全部右移之后： 1-2，1-2-5，1-2-4，1-2，1-2-5，1-3，1-3，1-2-4，1，1把非根基因處理，刪除右移后非根基因與根基因的關(guān)系，處理后如下： 2，2-5，2-4，2，2-5，3，3，2-4，1，1提取樹枝根為2的基因：2，2-5，2-4，2，2-5，2-4根右移后： 2-5，2-4，

27、2-5，2-4，2，2把非根基因處理，刪除右移后非根基因與根基因的關(guān)系，處理后如下： 5，4，5，4，2，2放回原來提取時(shí)的位置后： 5，4，5，4，2，3，3，2，1，1以上最后一條數(shù)據(jù)就是符合裝配約束的派工序列，即可性染色體。流程圖如下：在不可行染色體中依次提出樹枝根向右移轉(zhuǎn)換后依次放回原染色體父項(xiàng)染色體掃描完ny輸出轉(zhuǎn)換后染色體 圖2.4.1第三章 不可性染色體轉(zhuǎn)換算法實(shí)現(xiàn)軟件設(shè)計(jì)在進(jìn)行軟件設(shè)計(jì)中，使用應(yīng)用程序開發(fā)工具vb6.0設(shè)計(jì)。首先設(shè)計(jì)出操作界面，定義各個(gè)控件的屬性，然后編寫出程序。在做算法實(shí)現(xiàn)的過程中，先做出手動(dòng)輸入不可行染色體、判斷轉(zhuǎn)換后輸出結(jié)果是否正確來調(diào)試程序，等調(diào)試成功后

28、，進(jìn)行連接文本，輸入輸出都是以文本的形式進(jìn)行，這樣對(duì)于軟件操作者來說簡單易行，可以對(duì)大量的不可行染色體進(jìn)行轉(zhuǎn)換。3.1界面設(shè)計(jì) 用vb6.0 設(shè)計(jì)出操作界面如下圖所示： 圖3.1.1界面的設(shè)計(jì)：界面從上至下輸入父項(xiàng)染色體、子項(xiàng)染色體和被轉(zhuǎn)換對(duì)象不可行染色體，然后選擇算法，點(diǎn)擊轉(zhuǎn)換按鈕，轉(zhuǎn)換結(jié)束后可以點(diǎn)擊退出按鈕退出程序，也可更換輸入的染色體或者算法進(jìn)行下一次的轉(zhuǎn)換。從上至下的布局符合人的一般操作習(xí)慣。各個(gè)控件的屬性設(shè)置如下表：對(duì)象控件名屬性名屬性值功能commandbuttoncommand1caption轉(zhuǎn)換command2caption退出textboxtext1text空輸入父項(xiàng)染色體t

29、ext2text空輸入子項(xiàng)染色體text3text空輸入被轉(zhuǎn)換染色體text4text空顯示轉(zhuǎn)換后染色體text5text空顯示轉(zhuǎn)換時(shí)間labellabel1caption輸入父項(xiàng)染色體label2caption輸入子項(xiàng)染色體label3caption輸入被轉(zhuǎn)換染色體label4caption選擇算法label5caption輸出可行染色體label6caption輸出所用時(shí)間frameframe1caption輸入frame2caption輸出timertimer1enabledtrueoptionbuttonoption1captioncipoption2captionslrrls3.2程

30、序設(shè)計(jì)程序的主干如下圖所示：把需要轉(zhuǎn)換的不可性染色體復(fù)制于acip slrrls判斷選擇算法輸出結(jié)果a，結(jié)束程序 圖3.2.1 對(duì)于多條染色體的轉(zhuǎn)換，利用循環(huán)多次運(yùn)行程序，即可完成轉(zhuǎn)換。3.2.1定義變量 對(duì)程序中用到的變量進(jìn)行定義，定義如下：dim a as string 不可行染色體串定義dim b as string 父串染色體串dim c as string 字串染色體串定義字符串。dim bu(1 to 110) as string 不可性染色體基因dim fu(1 to 11) as string 父串染色體基因dim zi(1 to 11) as string 字串染色體基因di

31、m buk(1 to 100) as string定義數(shù)組。dim n as integer 不可性染色體基因數(shù)目dim m as integer 父串染色體基因數(shù)目dim z as integer 字串染色體基因數(shù)目dim i as integer 定義變量dim j as integer 定義變量dim k as integer 定義變量dim x as string 定義變量dim y as string 定義變量dim l as integer 定義變量dim e as integer 定義變量dim zh(1 to 100) as string 定義變量，用于記住提取位置dim st

32、, et, pt 定義變量，用于時(shí)間計(jì)算dim nextline as string 定義變量3.2.2算法共用程序設(shè)計(jì) 經(jīng)過程序調(diào)試成功后，連接文件，以文件的形式進(jìn)行輸入、輸出，這時(shí)可以將界面內(nèi)輸入不可性染色體、輸出轉(zhuǎn)換后染色體的控件刪除，做成如下形式： 圖3.2.2 當(dāng)單擊按鈕轉(zhuǎn)換時(shí)，時(shí)間開始計(jì)時(shí)，把父子串染色體賦值給b、c兩個(gè)字符串。具體程序，編寫如下：private sub command1_click() st = now 計(jì)時(shí)開始b = text1.textc = text2.text以輸出入的形式打開f盤中的文件/不可行染色體。open f:不可行染色體.txt for inpu

33、t as #1循環(huán)程序，每次由文件向程序內(nèi)變量a輸入一條不可性染色體，直到文件內(nèi)不可性染色體輸出結(jié)束。do until eof(1) line input #1, nextline a = nextline 在轉(zhuǎn)換過程中，父子基因關(guān)系是轉(zhuǎn)換的唯一依據(jù)。必須使父子基因之間關(guān)系用數(shù)據(jù)的形式連接在一起。利用vb內(nèi)的函數(shù)mid$（a,b,c）來提取每一個(gè)基因，a表示從字符串a(chǎn)中提?。籦表示從第b個(gè)基因提?。籧表示提取的數(shù)量為c個(gè)基因。使用for to next 語句來循環(huán)提取，直到被提取對(duì)象最后一個(gè)基因被提出。程序如下： n = len(a) 提取不可行染色體基因 for i = 1 to n bu(

34、i) = mid$(a, i, 1) next i如果a的第5個(gè)基因是3，那么bu(5)=3。 m = len(b) 提取父串基因 for j = 1 to m fu(j) = mid$(b, j, 1) next j z = len(c) 提取子串基因 for k = 1 to z zi(k) = mid$(c, k, 1) next k 在提取基因后，再對(duì)其進(jìn)行“父子關(guān)系”的確認(rèn)。這段確認(rèn)程序成為組串程序，它將完成新的字符串，裝配關(guān)系（父子關(guān)系）如下：12534 圖3.2.3 對(duì)于子串來說，如果原來是zi(7)=5，經(jīng)過組串程序后zi(7)=125，將它的父基因依次排在前面。程序如下：fo

35、r l = 1 to z 組串程序 zi(l) = fu(l) & zi(l) next l j = 1 while j = 10 for k = 1 to z l = z - k + 1 for i = 1 to l - 1 if left$(zi(l), 1) = right$(zi(i), 1) then zi(l) = zi(i) & mid$(zi(l), 2, len(zi(l) - 1) next i next k j = j + 1 wend 經(jīng)過組串后，把“父子關(guān)系”應(yīng)用到不可行染色體的基因里面去。 for i = 1 to n for k = 1 to z if bu(i)

36、 = right$(zi(k), 1) then bu(i) = zi(k) next k next i調(diào)用選擇程序，選擇程序內(nèi)調(diào)用算法程序，所以經(jīng)過調(diào)用選擇程序之后，結(jié)果已經(jīng)出來了，打開文件，進(jìn)行結(jié)果輸出。沒有的文件時(shí)，系統(tǒng)自動(dòng)建立一個(gè)名為可性染色體的txt文件，進(jìn)行結(jié)果輸出。append的輸出形式是在原來文本的末尾輸出，不會(huì)覆蓋原來的文本。chr(13)+c(10) 則表示每輸出一條染色體則回車換行。 call xuan open f:可行染色體.txt for append as #2 print #2, a + chr(13) + chr(10) 輸出可行染色體a close #2 關(guān)

37、閉文件loopclose #1 關(guān)閉原文件et = now 計(jì)時(shí)停止pt = et st 計(jì)算運(yùn)行所用時(shí)間text5 = format(pt, hh:mm:ss) 輸出時(shí)間end sub 程序結(jié)束 選擇程序的編程如下，當(dāng)有方法被選中時(shí)select case true，判斷是哪一種方法，如果case option1.value，則調(diào)用算法cip的運(yùn)算程序；case option2.value，則調(diào)用算法slrrls的運(yùn)算程序。 sub xuan()select case true case option1.value call cip 選擇第一個(gè)算法。 case option2.value ca

38、ll slrrls選擇第二個(gè)算法。 end selectend sub定義第二個(gè)按鈕的作用，當(dāng)單擊此按鈕時(shí)，將結(jié)束程序。private sub command2_click()endend sub3.2.3基于路徑表的掃描換位的程序設(shè)計(jì)基于路徑表的掃描換位( cip: circulatory interchanging based on pathway）運(yùn)算程序，把不可性染色體每一個(gè)基因與與后面的每一個(gè)基因比較，如果后面的基因是它的子項(xiàng)，二者交換位置，并且子項(xiàng)內(nèi)要?jiǎng)h除表示該基因的字符，以便于下一次掃描。這種掃描方法原本不必和前面的基因進(jìn)行比較，但是在本程序中，如下圖表示基因5的字符串125，在

39、1的前面的話，“125”中的“1”不會(huì)被刪除，當(dāng)與“125”前面的“2”進(jìn)行比較時(shí)，就會(huì)出現(xiàn)錯(cuò)誤。所以程序設(shè)計(jì)時(shí)，是對(duì)每一項(xiàng)都進(jìn)行比較的，對(duì)于一個(gè)基因，子項(xiàng)在前面，就刪除子項(xiàng)中該基因關(guān)系；子項(xiàng)在后面，交換位置后，再刪除子項(xiàng)中該基因關(guān)系，進(jìn)入下一個(gè)基因掃描。1 2534 圖3.2.4sub cip() cip運(yùn)算程序j = 0 換位及刪除程序while j = 2 and l = 2 and l i theny = bu(i) bu(i) = bu(l)bu(l) = ybu(i) = mid$(bu(i), 2, len(bu(i) - 1)exit for end if next l nex

40、t i j = j + 1wend經(jīng)過掃描，每個(gè)基因都恢復(fù)到一個(gè)字符的狀態(tài)，符合條件的基因?qū)?jīng)過交換位置，數(shù)組bu(i)按照i的遞增方向已經(jīng)成為一條可行染色體。將每一個(gè)基因進(jìn)行重新連接，賦值于a。 a = bu(1) 重整程序 for i = 2 to n bu(i) = bu(i) a = a & bu(i)next i end sub程序結(jié)束。3.2.4基于根右移的子樹歸位的程序設(shè)計(jì) 基于根右移的子樹歸位（slrrls: subtree locus reversion based on root left shift）的轉(zhuǎn)換思想是：在父項(xiàng)中依次提取代表每一個(gè)基因的字符m，經(jīng)過組串程序后的染

41、色體已經(jīng)把“父子關(guān)系”明確了，從左端查，對(duì)每一個(gè)代表不可行染色體基因的字符串進(jìn)行篩選，如果該字符串左端的字符等于字符m，說明該項(xiàng)是m的子項(xiàng)或則m本身，提取出來。將m所有子項(xiàng)及其本身依次賦值給一個(gè)數(shù)組buk()，不是m本身的字符串用函數(shù)mid$(buk(i),2,len(buk(i)-1)刪除第一個(gè)字符，len(a)是計(jì)算字符串a(chǎn)中字符個(gè)數(shù)的函數(shù)。sub slrrls() slrrls主程序st = now for j = 1 to m 對(duì)于每一父項(xiàng)基因都要進(jìn)行掃描 k = 0: l = 0 for i = 1 to n 提取該基因下所有子項(xiàng)基因 if left$(bu(i), 1) = fu(

42、j) then k = k + 1buk(k) = bu(i) l = l + 1 zh(l) = i next i 函數(shù)left$(bu(i),1)提取字符串bu(i)的左端第一個(gè)字符，zh(l)的作用是記住原來提取不可性染色體中基因時(shí)的位置。 y = 0 計(jì)算每一父項(xiàng)基因在不可性染色體里的數(shù)目y for i = 1 to n if bu(i) = fu(j) then y = y + 1 next i if y = 0 then for i = 1 to n buk(i) = mid$(buk(i), 2, len(buk(i) - 1) next i else for e = 1 to

43、k if buk(e) fu(j) then buk(e) = mid$(buk(e), 2, len(buk(e) - 1) next e掃描y次，把buk(i)中的y個(gè)父項(xiàng)基因移動(dòng)到最右端。l = 1 do while l = y 掃描y次 for e = 1 to k - 1 if buk(e) = fu(j) and buk(e + 1) fu(j) then x = buk(e)buk(e) = buk(e + 1) buk(e + 1) = x end if next e l = l + 1 loop k表示針對(duì)父項(xiàng)染色體中一個(gè)基因在不可行染色體中提取的字符串的個(gè)數(shù)。 for l

44、= 1 to k e = l 把數(shù)組zh(l)轉(zhuǎn)化為數(shù)字類型 zh(l) = val(zh(l) 把提取的基因按照新的順序，放回原來的位置。 bu(zh(l) = buk(e) next l end ifnext j 針對(duì)下一父項(xiàng)基因，在不可性染色體中尋找其子基因經(jīng)過掃描，每個(gè)基因都恢復(fù)到一個(gè)字符的狀態(tài)，符合條件的基因?qū)?jīng)過交換位置，數(shù)組bu(i)按照i的遞增方向已經(jīng)成為一條可行染色體。將每一個(gè)基因進(jìn)行重新連接，賦值于a。a = bu(1) for i = 2 to n a = a & bu(i) next iend sub第四章 實(shí)驗(yàn)結(jié)果進(jìn)行轉(zhuǎn)換實(shí)驗(yàn), 針對(duì)同一不可性染色體集合，用相同的父子

45、串染色體，一是直接對(duì)兩種算法進(jìn)行計(jì)時(shí)實(shí)驗(yàn),二是將兩種算法的輸出結(jié)果進(jìn)行比較。為了便于計(jì)時(shí),集合規(guī)模為300 條染色體, 300 條初始隨機(jī)非法染色體無一重復(fù)。4.1實(shí)驗(yàn)結(jié)果取3對(duì)父子串進(jìn)行試驗(yàn)，每對(duì)實(shí)驗(yàn)每種方法進(jìn)行兩次。通過以下的實(shí)驗(yàn)結(jié)果，進(jìn)行分析。父串為：112223335子串為：23456789a兩種方法運(yùn)行時(shí)間：cip ：13秒 slrrls：7秒cip ：14秒 slrrls：6秒父串為：123456789 子串為：23456789a 兩種方法運(yùn)行時(shí)間：cip ：12秒 slrrls：6秒 cip ：12秒 slrrls：6秒父串為：112233445 子串為：23456789a 兩種

46、方法運(yùn)行時(shí)間：cip ：14秒 slrrls：6秒cip ：14秒 slrrls：7秒以上結(jié)果表明slrrls方法明顯比cip方法快。這是因?yàn)閏ip程序在掃描過程中需要對(duì)非“直系親屬”進(jìn)行比較，例如：2和3都是1的子項(xiàng)，在cip中當(dāng)掃描至父項(xiàng)為2時(shí)，需要和3的及其子項(xiàng)們進(jìn)行比較，這樣就增加了比較工作量。而slrrls方法與cip方法相比，只是多了提取基因的過程和放回過程，提取一個(gè)父項(xiàng)基因及其子項(xiàng)基因之后，對(duì)于父項(xiàng)2，與其相比較的只有2及其子項(xiàng)，省去了和“旁系”的比較，減少了工作量，縮短了工作時(shí)間。對(duì)于同一條不可行染色體來說，兩種算法轉(zhuǎn)換的結(jié)果一樣，是因?yàn)樵赾ip中只對(duì)符合條件“直系親屬”進(jìn)行交

47、換位置，掃描方式是對(duì)不可性染色體從左向右依次提取基因，再和前后基因比較，后面有它的子項(xiàng)，就與子項(xiàng)交換位置；而slrrls是依次提取一個(gè)父項(xiàng)基因及其子項(xiàng)，掃描方式也是對(duì)不可性染色體從左向右依次提取基因，如果等于父項(xiàng)，后面基因比較，后面基因不等于父項(xiàng)時(shí)，就是該基因的子項(xiàng)，便與其交換位置；這兩種交換位置的方式是一樣的，只不過為了提高效率，slrrls是提取之后在進(jìn)行掃描，避免了對(duì)非“直系親屬”的掃描比較。舉個(gè)例子來說，1是2和3的父項(xiàng)，而且1只這兩個(gè)子項(xiàng)，對(duì)于算法cip來說，經(jīng)過n次（n是1的個(gè)數(shù)）掃描之后，1全部右移（除了1右移之外，其它染色體相對(duì)位置不變，在左面的還是在左邊），然后再對(duì)下一級(jí)進(jìn)行掃描，在掃描的過程中，對(duì)于2及其子項(xiàng)，只會(huì)在2及其子項(xiàng)的位置上進(jìn)行作用：互換位置、刪除頂級(jí)父項(xiàng)。不會(huì)去占用3及其子項(xiàng)的位置；對(duì)于3及其子項(xiàng)也是這樣。而算法slrrls是提取一個(gè)樹進(jìn)行作用，把1全部右移（這種右移也是只對(duì)1進(jìn)行，其它染色體的相對(duì)位置不變，所以右移之后排列方式是唯一的）后，提取2及其子項(xiàng)進(jìn)行2的右移，右移完畢后，再將其新的排列按照提取時(shí)的位置放回。對(duì)于3也是這樣。兩種算法的方式不一樣，但同級(jí)及其子項(xiàng)之間的位置不會(huì)發(fā)生互換，即只有“直系關(guān)系”的基因發(fā)生互換，這樣每個(gè)基因的位置最終就是固定的，所以這兩種算法結(jié)果是一樣的。兩種算法，只