指派問題的啟發(fā)式算法研究畢業(yè)論文(存儲(chǔ)版)

　　

【正文】 波機(jī)制。圖式中第1位數(shù)字和最后位數(shù)字間的距離稱為圖式的長度，并用δ(H)表示。串長度及編碼形式對算法收斂影響極大。變異概率Pm太小時(shí)難以產(chǎn)生新的基因結(jié)構(gòu)，太大使遺傳算法成了單純的隨機(jī)搜索。通過對“染色體”的優(yōu)化就實(shí)現(xiàn)了對網(wǎng)絡(luò)的優(yōu)化。遺傳算法雖然可以在多種領(lǐng)域都有實(shí)際應(yīng)用，并且也展示了它潛力和寬廣前景；但是，遺傳算法還有大量的問題需要研究，目前也還有各種不足。傳統(tǒng)遺傳算法在采用非序號編碼（包括二進(jìn)制編碼、實(shí)數(shù)編碼等）且所求解問題屬無約束優(yōu) 化問題時(shí)是有效的。、單親遺傳算法的特點(diǎn)與傳統(tǒng)遺傳算法一樣，單親遺傳算法群體規(guī)模N的選擇對計(jì)算效率有著很大的影響。單親遺傳算法的全部遺傳操作都在一個(gè)個(gè)體上進(jìn)行，遺傳迭代的進(jìn)行與群體的多樣性無關(guān)，不要求初始群體中的個(gè)體具有的多樣性，也不會(huì)發(fā)生“早熟收斂”現(xiàn)象。C、適應(yīng)度定標(biāo)法：為使遺傳算法有效地工作，必須保持種群內(nèi)染色體的多樣性和位串之間的競爭機(jī)制。它要求每個(gè)子群體的進(jìn)化獨(dú)立進(jìn)行，群體之間互不干擾。序號編碼單親遺傳算法常用的遺傳算子可分為兩大類：基因重組算子和基因突變算子。實(shí)數(shù)編碼單親遺傳算法主要用于有約束的復(fù)雜工程優(yōu)化問題。有的論文在假定上一代群體中的所有個(gè)體被選擇到下一代的概率都大于0時(shí)，對單親遺傳算法的全局收斂性進(jìn)行了分析研究，指出單親遺傳算法的基因換位算子、基因移位算子、基因倒位算子和基因突變算子對串空間的搜索都具有遍歷性，單親遺傳算法在引入了最優(yōu)保持操作后是全局收斂的。通過改進(jìn)個(gè)體編碼方式， 壓縮了個(gè)體空間；通過對初始群體進(jìn)行預(yù)處理，提高了初始群體中個(gè)體的平均適應(yīng)度；通過 改進(jìn)個(gè)體適應(yīng)度函數(shù)的計(jì)算方法，減少了個(gè)體適應(yīng)度的計(jì)算時(shí)間；通過對群體中個(gè)體的相似 性檢查而淘汰部分相同的個(gè)體，能保持群體中個(gè)體的多樣性。肖鵬等將單親遺傳算法應(yīng)用于物流配送和車輛路徑問題中，也取得了良好的效果。針對目前應(yīng)用廣泛的常規(guī)遺傳算法在求解該問題時(shí)存在的難以保證方案連通性 和輻射性的缺陷，提出了基于單親遺傳算法的配電網(wǎng)絡(luò)優(yōu)化規(guī)劃算法。、單親遺傳算法的展望單親遺傳算法自誕生以來，其理論研究和應(yīng)用研究取得了一定的進(jìn)展。 單親遺傳算法與其它優(yōu)化方法的綜合二、 混合單親遺傳算法 、算法模型簡介指派問題的標(biāo)準(zhǔn)形式（以人和事為例）：有n個(gè)人和n件事，已知第i個(gè)人做第j件事的費(fèi)用為cij(i,j=1,2……n)，要確定人和事之間一一對應(yīng)的指派方案，使完成這n件事的總費(fèi)用最少。證明：設(shè)與這樣的一個(gè)排列對應(yīng)，其中可看作是排列中數(shù)所在位置左邊比小的數(shù)的個(gè)數(shù)。編碼方法：對任一指派方案，按定理2證明中的方法，它與中某元素一一對應(yīng)。隨機(jī)選取四個(gè)換位點(diǎn)，進(jìn)行鏈?zhǔn)浇粨Q，令得新個(gè)體。 對人，重新安排其工作為，滿足條件Ⅰ）：，若不存在滿足該條件的工作，轉(zhuǎn)6C。、新的遺傳算法算法1.取種群規(guī)模 ，換位概率為，隨機(jī)在集合中產(chǎn)生初始種群，解碼后記為；（基因換位）：以概率在中選擇參加基因換位的個(gè)體，用基因換位算子產(chǎn)生后代。對上述三個(gè)算例，記錄了其10次運(yùn)行的結(jié)果，結(jié)果見表2。 Partheno Genetic Algorithm。 lk (km) is the length of line k 。 YM (￥/year) is the fee for existing line power loss。 ΔU k (kV)is the Voltage drop in line k 。 g ( Dk ) (?/km) is the resistance per unit length, when the section of line k is2 Dk (mm )。 r0 is the discount rate of power system。d. Acceptable level of reliability.Where F is the objective function。數(shù)值實(shí)驗(yàn)表明該算法對求解AP問題有較好的效果。表1 城市規(guī)模TSP最短路長AP總費(fèi)用迭代次數(shù)種群規(guī)模Fri269378331510Dantzig42699510510Eil101629571512Tsp225391634231512Lin31842029272951010表2 最好解12345678910迭代次數(shù)均值6202020202020202020202010020100305305305308307306305305305305309100306200475477477479477477475479477477479100由表1可以看出，就可以求出明顯優(yōu)于TSP問題的最優(yōu)解的解，顯示了該算法的有效性。重新選擇；取，顯然，均滿足條件，比較的大小，得時(shí)，此差值最大，令，令，重復(fù)該過程。ⅰ、選擇的新工作不允許和中的記錄重復(fù)，同時(shí)第人不允許和中的記錄重復(fù)；ⅱ、令，必須滿足中元素的個(gè)數(shù).具體步驟如下：設(shè)為一指派方案（表示第人做第件事，）；2 、初始化：(表示到目前為止比原指派方案減少的費(fèi)用)。適應(yīng)度函數(shù)：對每一個(gè)個(gè)體，用解碼方法求出其對應(yīng)的指派方案，則為該指派方案消耗的總費(fèi)用。故規(guī)模為的AP問題任一可行的指派方案均可用中的元素表示。證明：因可取兩個(gè)值0和1，可取3個(gè)值0,1,2，一般地， 可取個(gè)值的取值相互獨(dú)立，故可能取值的個(gè)數(shù)為。 單親遺傳算法運(yùn)行機(jī)理的進(jìn)一步研究。該方法通過隱含傳統(tǒng)遺傳算法交叉算子 功能的基因換位等遺傳算子來實(shí)現(xiàn)進(jìn)化操作，簡化了遺傳操作過程，同時(shí)避免了“早熟收斂” 問題。與常規(guī)遺 傳算法比較，實(shí)數(shù)編碼單親遺傳算法通過采用一個(gè)基因?qū)?yīng)一個(gè)參數(shù)的實(shí)數(shù)編碼方式，壓縮了染色體串長，且無需解碼；通過采用單親繁殖方式，提高了遺傳算子的搜索效率，并能較方便地在遺傳操作過程中處理約束條件；通過在遺傳操作過程中實(shí)現(xiàn)基因協(xié)同變異，進(jìn)一步提高了遺傳算子的搜索效率。研究了單親遺傳算法在模式聚類問題中的應(yīng)用，用單親遺傳算法求解模式聚類問題可 以使聚類結(jié)果完全不依賴于初始聚類中心。這種算法克 服了模糊 C均值算法的局部最優(yōu)問題以及采用普通遺傳算法聚類時(shí)搜索速度和聚類精度的矛盾。對單親遺傳算法的圖式定理進(jìn)行了分析研究，單親遺傳算法的遺傳算子處理圖式的能力與傳統(tǒng)遺傳算法的基本相當(dāng)，單親遺傳算法具有與傳統(tǒng)遺傳算法類似的隱含并行性。多點(diǎn)遺傳算子對圖式的破壞作用太大，搜索效率不高，使用不多。實(shí)數(shù)編碼單親遺傳算法的研究工作起步較晚，針對火電廠機(jī)組優(yōu)化組合問題提出了一種實(shí)數(shù)編碼方式，每條染色體中的每個(gè)基因代表一臺(tái)機(jī)組某一個(gè)時(shí)段內(nèi)的出力，使染色體串長大大縮短，提高了搜索效率。Whiley 則考慮針對個(gè)體之間的海明距離 (Hamming Distance)來配置變異概率。針對上述原因，防止早熟一般有以下方法：A、 選擇合適的群體規(guī)模：在計(jì)算量允許的情況下，盡量選擇較大的群體規(guī)模，以保證群體的多樣性。眾所周知，傳統(tǒng)遺傳算法的交叉算子在群體中的個(gè)體都相同時(shí)是無效的，這就要求初始群體中的個(gè)體具有廣泛的多樣性，并且這種多樣性必須維持到遺傳迭代的完成。因?yàn)楫?dāng)交叉算子作用于代表可行解的兩個(gè)個(gè)體時(shí)，產(chǎn)生的兩個(gè)新個(gè)體很可能不再代表可行解。遺傳算法所涉及的六大要素：參數(shù)編碼、初始群體的產(chǎn)生、適應(yīng) 度函數(shù)的設(shè)計(jì)、遺傳操作的設(shè)計(jì)、控制參數(shù)的設(shè)定以及算法終止條件。神經(jīng)網(wǎng)絡(luò)由于有分布存儲(chǔ)等特點(diǎn)，一般難以從其拓?fù)浣Y(jié)構(gòu)直接理解其功能。2．遺傳算法在網(wǎng)絡(luò)設(shè)計(jì)中的應(yīng)用用遺傳算法設(shè)計(jì)一個(gè)優(yōu)秀的神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)，首先是要解決網(wǎng)絡(luò)結(jié)構(gòu)的編碼問題；然后才能以選擇、交叉、變異操作得出最優(yōu)結(jié)構(gòu)。交叉概率Pc太小時(shí)難以向前搜索，太大則容易破壞高適應(yīng)值的結(jié)構(gòu)。六、遺傳算法的應(yīng)用關(guān)鍵遺傳算法在應(yīng)用中最關(guān)鍵的問題有如下3個(gè)1．串的編碼方式這本質(zhì)是問題編碼。例如：H=1xx 0 x x是一個(gè)圖式。由于遺傳算法使用適應(yīng)值這一信息進(jìn)行搜索，并不需要問題導(dǎo)數(shù)等與問題直接相關(guān)的信息。常用的尺度變換方法如下：：F＇＝aF＋b：F＇＝Fｋc.、指數(shù)尺度變換：F＇＝eｘp（－beitaF）約束條件處理（1）、搜索空間限定法：對遺傳算法的搜索空間的大小加以限制，使得搜索空間中表示一個(gè)個(gè)體的點(diǎn)與解空間中的表示一個(gè)可行解的點(diǎn)有一一對應(yīng)關(guān)系。(3)、計(jì)算量小。適應(yīng)度函數(shù)適應(yīng)度函數(shù)也稱評價(jià)函數(shù)，是根據(jù)目標(biāo)函數(shù)確定的用于區(qū)分群體中個(gè)體好壞的標(biāo)準(zhǔn)。對其的第1，4位置的基因進(jìn)行變異，則有S39。這個(gè)過程反映了隨機(jī)信息交換；目的在于產(chǎn)生新的基因組合，也即產(chǎn)生新的個(gè)體。給出目標(biāo)函數(shù)f，則f(bi)稱為個(gè)體bi的適應(yīng)度。四、遺傳算法的步驟和意義1．初始化選擇一個(gè)群體，即選擇一個(gè)串或個(gè)體的集合bi，i=1，2，...n。遺傳算法的原理可以簡要給出如下：choose an intial populationdetermine the fitness of each individualperform selectionrepeatperform crossoverperform mutationdetermine the fitness of each individualperform selectionuntil some stopping criterion applies這里所指的某種結(jié)束準(zhǔn)則一般是指個(gè)體的適應(yīng)度達(dá)到給定的閥值；或者個(gè)體的適應(yīng)度的變化率為零。2．交叉(Crossover)這是在選中用于繁殖下一代的個(gè)體中，對兩個(gè)不同的個(gè)體的相同位置的基因進(jìn)行交換，從而產(chǎn)生新的個(gè)體。B、用N的整數(shù)部分確定各個(gè)對應(yīng)個(gè)體在下一代群體中的生存數(shù)目。（2）、隨機(jī)競爭選擇（Stochastic Tournament）：每次按輪盤賭選擇一對個(gè)體，然后讓這兩個(gè)個(gè)體進(jìn)行競爭，適應(yīng)度高的被選中，如此反復(fù)，直到選滿為止。在每個(gè)串中，每個(gè)二進(jìn)制位就是個(gè)體染色體的基因。非線性它對應(yīng)遺傳學(xué)中的異位顯性(Epistasis)適應(yīng)度(Fitness)表示某一個(gè)體對于環(huán)境的適應(yīng)程度。5 、基因位置(Gene Position)一個(gè)基因在串中的位置稱為基因位置，有時(shí)也簡稱基因位。基因突變和基因雜交可產(chǎn)生更適應(yīng)于環(huán)境的后代。遺傳算法介紹一、遺傳算法的基本概念遺傳算法的基本思想是基于Darwin進(jìn)化論和Mendel的遺傳學(xué)說的。1987年，Goldberg發(fā)表Genetic Algorithms in Search，Optimization and Machine Learning,詳細(xì)介紹了GA在工程上的應(yīng)用。當(dāng)時(shí)，其主要目的是說明自然和人工系統(tǒng)的自適應(yīng)過程。而且由于數(shù)學(xué)模型本身就是實(shí)際問題的簡化，或多或少地會(huì)忽略一些因素， 再加上數(shù)據(jù)采集的不準(zhǔn)確性，參數(shù)估計(jì)的不準(zhǔn)確性可能使最優(yōu)算法所得的解比啟 發(fā)式算法產(chǎn)生的解產(chǎn)生更大的誤差。經(jīng)典算法包括線性規(guī)劃和非線性規(guī)劃的傳統(tǒng)算法、動(dòng)態(tài)規(guī)劃的傳統(tǒng)算法、 整數(shù)規(guī)劃的傳統(tǒng)算法和分枝定界等算法。求解AP精確解的方法，如分枝切割法（Branchandcut method，），其計(jì)算量十分巨大，對較大規(guī)模的問題難以應(yīng)用。關(guān)鍵詞：遺傳算法。首先，設(shè)計(jì)了一個(gè)新的編碼方法,并且對這種編碼方法，給出了簡便的解碼方法。局部搜索AbstractA novel hybrid parthenogenetic approach for assignment problems (AP for short) is proposed in this paper. First, a new encoding scheme and a new decoding scheme are designed. Second, an efficient geneexchange operator is given. In order to enhance its ability of exploration, a local search scheme is integrated into the operator. Based on these, a novel and effective parthenogenetic algorithm for AP is presented. Finally, the simulation is made and the results show the effectiveness of the proposed algorithm. Key words: genetic algorithm；assignment problems；binatorial optimization；local search目錄一、引言 指派問題、啟發(fā)式算法 遺傳算法 單親遺傳算法的特點(diǎn) 1單親遺傳算法理論研究現(xiàn)狀 1單親遺傳算法的應(yīng)用研究現(xiàn)狀 1單親遺傳算法的展望 17二、 混合單親遺傳算法 1算法模型簡介 17 、新的遺傳算法 1新的編碼方法 1基因換位算子、局部搜索 1新的遺傳算法 2計(jì)算機(jī)仿真 2 結(jié)束語 22主要參考文獻(xiàn) 24外文論文 25中文譯文 34致 謝 43一、引言、指派問題、啟發(fā)式算法在日常生活中經(jīng)常會(huì)遇到這樣的問題：某單位需要完成N項(xiàng)任務(wù)，恰好M個(gè)人可以承擔(dān)這些任務(wù)。本文提出了用混合單親遺傳算法求解AP的一種新算法，設(shè)計(jì)了