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

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

2、行染色體的轉換，并且對轉換結果進行了對比。關鍵詞：遺傳算法; 不可行染色體; 轉換方法; 綜合作業(yè)調度問題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生產調度的概念61.3生產調度問題的研究意義61.4生產調度的性能指標71.5生產調度問題的特點71.6 cjssp概念8第二章 不可行染色體轉換概念及

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

24、頂父項掃描是否n-1遍yn輸出可行染色體圖2.3.2圖2.3.1為產品結構圖，舉例來說：需要轉換的染色體為：1，5，3，2，4，2建立父項表后： 1，1-2-5，1-3，1-2，1-2-4，1-2進行掃描第i個基因依次與后面基因比較，根據比較結果在進行處理： 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ù)據就是符合裝配約束的派工序列，即可性染色體。在掃描過程中，所比較的基因不僅要與后面進行比較，也要與前面進行比較，例如上面得例子中2與前面的2-5進行比較，處理結果是刪除2-5前面的2-，而不交換位置，這樣才能得出正確的結果。2.4基于根右移的子樹歸位再次以產品裝配圖4.1.1為例進行說明：父串：1，1，2，2子串：2，3，4，5對于不可性染色體： 1，5，4，2，5，3，3，1，2，4

26、同樣建立“父子關系”表，之后為： 1，1-2-5，1-2-4，1-2，1-2-5，1-3，1-3，1，1-2，1-2-4提取根為1的樹枝（即全部基因，為了實現(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把非根基因處理，刪除右移后非根基因與根基因的關系，處理后如下： 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把非根基因處理，刪除右移后非根基因與根基因的關系，處理后如下： 5，4，5，4，2，2放回原來提取時的位置后： 5，4，5，4，2，3，3，2，1，1以上最后一條數(shù)據就是符合裝配約束的派工序列，即可性染色體。流程圖如下：在不可行染色體中依次提出樹枝根向右移轉換后依次放回原染色體父項染色體掃描完ny輸出轉換后染色體 圖2.4.1第三章 不可性染色體轉換算法實現(xiàn)軟件設計在進行軟件設計中，使用應用程序開發(fā)工具vb6.0設計。首先設計出操作界面，定義各個控件的屬性，然后編寫出程序。在做算法實現(xiàn)的過程中，先做出手動輸入不可行染色體、判斷轉換后輸出結果是否正確來調試程序，等調試成功后

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

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

30、序設計程序的主干如下圖所示：把需要轉換的不可性染色體復制于acip slrrls判斷選擇算法輸出結果a，結束程序 圖3.2.1 對于多條染色體的轉換，利用循環(huán)多次運行程序，即可完成轉換。3.2.1定義變量 對程序中用到的變量進行定義，定義如下：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 定義變量，用于時間計算dim nextline as string 定義變量3.2.2算法共用程序設計 經過程序調試成功后，連接文件，以文件的形式進行輸入、輸出，這時可以將界面內輸入不可性染色體、輸出轉換后染色體的控件刪除，做成如下形式： 圖3.2.2 當單擊按鈕轉換時，時間開始計時，把父子串染色體賦值給b、c兩個字符串。具體程序，編寫如下：private sub command1_click() st = now 計時開始b = text1.textc = text2.text以輸出入的形式打開f盤中的文件/不可行染色體。open f:不可行染色體.txt for inpu

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

34、i) = mid$(a, i, 1) next i如果a的第5個基因是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 在提取基因后，再對其進行“父子關系”的確認。這段確認程序成為組串程序，它將完成新的字符串，裝配關系（父子關系）如下：12534 圖3.2.3 對于子串來說，如果原來是zi(7)=5，經過組串程序后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 經過組串后，把“父子關系”應用到不可行染色體的基因里面去。 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調用選擇程序，選擇程序內調用算法程序，所以經過調用選擇程序之后，結果已經出來了，打開文件，進行結果輸出。沒有的文件時，系統(tǒng)自動建立一個名為可性染色體的txt文件，進行結果輸出。append的輸出形式是在原來文本的末尾輸出，不會覆蓋原來的文本。chr(13)+c(10) 則表示每輸出一條染色體則回車換行。 call xuan open f:可行染色體.txt for append as #2 print #2, a + chr(13) + chr(10) 輸出可行染色體a close #2 關

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

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

39、1的前面的話，“125”中的“1”不會被刪除，當與“125”前面的“2”進行比較時，就會出現(xiàn)錯誤。所以程序設計時，是對每一項都進行比較的，對于一個基因，子項在前面，就刪除子項中該基因關系；子項在后面，交換位置后，再刪除子項中該基因關系，進入下一個基因掃描。1 2534 圖3.2.4sub cip() cip運算程序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經過掃描，每個基因都恢復到一個字符的狀態(tài)，符合條件的基因對經過交換位置，數(shù)組bu(i)按照i的遞增方向已經成為一條可行染色體。將每一個基因進行重新連接，賦值于a。 a = bu(1) 重整程序 for i = 2 to n bu(i) = bu(i) a = a & bu(i)next i end sub程序結束。3.2.4基于根右移的子樹歸位的程序設計 基于根右移的子樹歸位（slrrls: subtree locus reversion based on root left shift）的轉換思想是：在父項中依次提取代表每一個基因的字符m，經過組串程序后的染

41、色體已經把“父子關系”明確了，從左端查，對每一個代表不可行染色體基因的字符串進行篩選，如果該字符串左端的字符等于字符m，說明該項是m的子項或則m本身，提取出來。將m所有子項及其本身依次賦值給一個數(shù)組buk()，不是m本身的字符串用函數(shù)mid$(buk(i),2,len(buk(i)-1)刪除第一個字符，len(a)是計算字符串a中字符個數(shù)的函數(shù)。sub slrrls() slrrls主程序st = now for j = 1 to m 對于每一父項基因都要進行掃描 k = 0: l = 0 for i = 1 to n 提取該基因下所有子項基因 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)的左端第一個字符，zh(l)的作用是記住原來提取不可性染色體中基因時的位置。 y = 0 計算每一父項基因在不可性染色體里的數(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個父項基因移動到最右端。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表示針對父項染色體中一個基因在不可行染色體中提取的字符串的個數(shù)。 for l

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

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

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

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