汽車電子中混合遺傳算法的應(yīng)用介紹

機車車輛企業(yè)是典型的訂單式生產(chǎn)企業(yè)，面對全球經(jīng)濟一體化，客戶需求個性化以及產(chǎn)品交貨高速化的經(jīng)濟時代，機車車輛行業(yè)面臨著快速響應(yīng)客戶需求、縮短產(chǎn)品交貨期、提高產(chǎn)品質(zhì)量和改進產(chǎn)品服務(wù)的壓力。為了在激烈的市場競爭中求得生存和發(fā)展，企業(yè)需要從生產(chǎn)調(diào)度環(huán)節(jié)進行優(yōu)化。生產(chǎn)調(diào)度是制造系統(tǒng)的一個研究熱點，調(diào)度的任務(wù)是根據(jù)生產(chǎn)目標(biāo)和約束，為每一個對象確定具體的加工路徑、時間、機器和操作等，優(yōu)良的調(diào)度策略對于縮短產(chǎn)品的生產(chǎn)時間，降低成本有著極大的作用。
　　訂單生產(chǎn)調(diào)度問題屬于一類NP-hard組合問題，因此尋找具有多項式復(fù)雜性的最優(yōu)算法幾乎是不可能的。傳統(tǒng)的啟發(fā)式算法、智能模擬退火算法、禁忌算法、神經(jīng)網(wǎng)絡(luò)法等算法其共性是對生產(chǎn)線優(yōu)化問題尋求滿足實際需要的近似解或滿意解，但都是局部尋優(yōu)的方法。而各種基于統(tǒng)計優(yōu)化的方法諸如模擬退火法、遺傳算法等，提供了一種解決調(diào)度優(yōu)化問題的新途徑，但也存在著一定程度的枚舉，一般來說收斂到最優(yōu)解較慢，并且對于判斷解的最優(yōu)性也很困難。將遺傳算法與優(yōu)化算法結(jié)合起來對解決訂單生產(chǎn)調(diào)度問題具有較高的性能。
　　1 混合遺傳算法
　　1.1 遺傳算法
　　遺傳算法由于其運算的簡易性和解決問題的高效性而被廣泛應(yīng)用于眾多的領(lǐng)域。理論上已經(jīng)證明，遺傳算法能從概率的意義上以隨機的方式尋求到問題的最優(yōu)解。但是另一方面，應(yīng)用實踐表明，在遺傳算法的應(yīng)用過程中也會出現(xiàn)一些不盡如人意的問題，這些問題主要表現(xiàn)為：容易產(chǎn)生早熟現(xiàn)象、局部尋優(yōu)能力較差等。并且一般來說，對很多問題，基本遺傳算法的求解效果往往不是解決這個問題的最有效的方法，它比起專門針對該問題的知識型啟發(fā)算法的求解效率要差，雖然這種知識型啟發(fā)算法并保證不了一定能夠找到問題的全局最優(yōu)解。另外，遺傳算法也無法避免多次搜索同一個可行解的情況，這也是影響遺傳算法運行效率的一個重要因素。
　　1.2 混合遺傳算法
　　梯度法、爬山法、模擬退火算法、列表尋優(yōu)法等一些優(yōu)化算法卻具有很強的局部搜索能力，而遺傳算法由于其運算的簡易性以及另一些含有問題與相關(guān)知識的啟發(fā)式算法的運行效率也比較高。因此可以預(yù)計，在遺傳算法的搜索過程中融合這些優(yōu)化方法的思想，構(gòu)成一種混合遺傳算法是提高遺傳算法運行效率和求解質(zhì)量的一個有效手段。
　　混合遺傳算法是在標(biāo)準遺傳算法中融合了局部搜索算法的思想，其特點主要體現(xiàn)在以下兩個方面：
　?。?）引入了局部搜索過程?；谌后w中各個個體所對應(yīng)的表現(xiàn)型，進行局部搜索，從而找出各個個體在目前的環(huán)境下所對應(yīng)的局部最優(yōu)解，以便達到改善群體總體性能的目的。
　?。?）增加了編碼變換操作過程。對局部搜索過程所得到的局部最優(yōu)解，再通過編碼過程將它們變化為新的個體，以便能夠以一個性能較優(yōu)的新群體為基礎(chǔ)來進行下一代的遺傳進化操作。
　　2 機車車輛業(yè)面向訂單生產(chǎn)調(diào)度模型
　　訂單生產(chǎn)調(diào)度問題中存在著多種優(yōu)化目標(biāo)或者綜合優(yōu)化目標(biāo)，調(diào)度問題的優(yōu)化目標(biāo)通常從生產(chǎn)的成本和生產(chǎn)的時間兩個方面來考慮。從生產(chǎn)成本方面來考慮，其優(yōu)化目標(biāo)有：制品最少、庫存最少、設(shè)備利用率最高等；從生產(chǎn)時間方面來考慮，其優(yōu)化目標(biāo)有：最小完成時間、最大程度滿足交貨期、最小流動時間和最小等待時間等。這兩個方向的優(yōu)化目標(biāo)之間彼此不是相互孤立的，其中的許多具體目標(biāo)之間聯(lián)系非常密切，有的相互促進，有的相互沖突，也有的毫無聯(lián)系。本算法采用以總加工時間最小為目標(biāo)，具體表示為：
　　
　　其中：Rk表示需要在設(shè)備k上加工的總工序數(shù)；Aijk表示第i個工件的第j道工序在設(shè)備k上完成加工所需要的時間。這個時間包括開始加工此道工序之前的等待時間Wijk和從開始加工到完成此道工序的所需時間Nijk；Cj表示訂單j的生產(chǎn)時間是訂單j中包括的所有部件全部完成的時間總和；Cmax為所有訂單在并行生產(chǎn)的情況下，最大完工時間，即各個訂單完成時間最晚的訂單的完成時間；目標(biāo)函數(shù)F（x）的目的是使得最長需要時間盡可能地短。這樣，經(jīng)過算法的多次迭代后就可以生成調(diào)度的近似最優(yōu)解，得到滿意的調(diào)度結(jié)果。