【正文】 yingdu[k]。 } 附錄 四：選擇、交叉和變異 過程 的代碼 include iostream include cstdio include cstdlib include include ctime using namespace std。//返回系統(tǒng)時間 int main() { freopen(,r,stdin)。 i = n。 j sum。 double tt = (double)t/。 i ++) { bn[top][i]=an[j][i]。 k 100000。//標(biāo)記已配對 int p。 } } int jishu = 0。 p ++)M[p] = 0。 if(c == d)goto loop。 } if(sum1 == 5)break。i = 100。//標(biāo)記已變異 loop: int c = rand()%sum。//變異染色體的類行指針 for(int p = 1。 bn[a][i] = bn[b][i]。//如果配對過那么在隨機(jī)一組數(shù) else { M[a] = 1。 p ++)M[p] = 0。gailv[j1]tt) { for(int i = 0。 i 100。 k = 100。 int u。//定義隨機(jī)數(shù)函數(shù) void srand( unsigned seed )。 } coutendl。 for(int k = 1。 coutshiyingdu[k] 。 sum+=t。 freopen(,w,stdout)。j=a。 } max_=work[1][0]。 for(i=1。//指示 上一步所在機(jī)器的號碼； int i。 } t=jisuan(a)。 int main() {int t。 int machine。 i SUM。 for(int j = 0。 i ++) { for(int j = 0。 int Q[10000][10000],W[10000][10000]。 39。 為了 改進(jìn)這個算法，我們可以 將 其與其他算法進(jìn)行結(jié)合，比如模擬 退火算法 、 局部優(yōu)化方法 等 ，以獲取 各 算法的優(yōu)點(diǎn)，集其大成 。 下面 是我們使用 的范例 Q= [ 1 2 3 4 5 6； 2 5 4 1 6 3； 5 4 1 2 3 6； 3 5 6 1 2 4； 1 3 5 4 6 2； 3 1 6 5 4 2 ] W= [ 8 3 6 3 1 9； 3 2 7 5 10 4； 9 4 1 9 1 2； 3 4 5 3 5 9； 2 3 5 4 6 1； 10 3 9 1 4 8 ] 輸入 這兩個矩陣以后 ， 我們 使用 這個模型， 迭代 100 次 以后 得到了 一種最優(yōu)方案S= [ 5 2 4 3 1 6 6 3 5 4 5 1 2 4 4 6 5 3 3 2 5 1 2 1 6 4 6 1 2 4 1 2 5 3 6 3]，根據(jù) 這個方案以及 Q 與 W 矩陣 ，我們算出來 T(S)??????=55。具體 方法 是，首先根據(jù)各染色體的適應(yīng)度換算出它被選中的概率，然后從 N 個 染色體 中按 這個 概率 依次 選出 N 個 （ N 為偶數(shù) ） ， 這樣適應(yīng)度高的染色體可能出現(xiàn)多次，適應(yīng)度 低 的就 很可能被 淘汰 。也就是在一個給定的合理的染色體的基礎(chǔ)上， 再將其中基因的 順序打亂，進(jìn)而產(chǎn)生新的染色體。即一個調(diào)度是由 m個工件的所有工序的排列組合，且 m 臺機(jī)器上的排列又相互制約，必須遵循：各工件的某道工序加工時，它的前道工序已經(jīng)加工完成； （ 7） TS (a)表示在調(diào)度策略 S 下，機(jī)器 Ma上全部工序的完成時間（包括機(jī)器的執(zhí)行時間和等待時間），則調(diào)度 S 的完成時間 T（ S） =max（ TS (1)， TS ( 2)， ?， TS ( m)）； （ 8）基于最短完成時間的 JSP 問題的目標(biāo)函數(shù)為 min（ T（ S）， ∨ S），即尋找一個滿足約束的調(diào)度 S，使得 T(S)最小。而遺傳算法數(shù)以一種自適應(yīng)概率搜索技術(shù)，其選擇、交叉、變異等運(yùn)算都是以一種概率的方式來進(jìn)行的，從而增加了其搜索的靈活性。傳統(tǒng)的優(yōu)化算法不僅需要利用目標(biāo)函 數(shù)值，而且往往需要目標(biāo)函數(shù)的導(dǎo)數(shù)值等其他一些輔助信息才能確定搜索方向。當(dāng)由此監(jiān)控得到算法再進(jìn)化己無法改進(jìn)解的性能時，停止計算。與二進(jìn)制編碼單點(diǎn)交叉不同在于交換的對象的差異，前者是二進(jìn)制串，后者是實空間的向量。 選擇 選擇即是在一個種群中選擇一個個體，它是隨機(jī)映射 Ts:SN→ S， 選擇操作的目的是為了避免當(dāng)前群體中有效基因的損失，使高性能的個體得以更大的概率生 存，從而提高全局收斂性和計算效率。針對優(yōu)化問題的編碼技術(shù)主要有二進(jìn)制編碼、十進(jìn)制編碼、實數(shù)編碼等。 選擇 (Selection) ：以一定的概率從種群中選擇若干個體進(jìn)行遺傳或交配。 現(xiàn)約定未完工前不允許中斷處理，作業(yè)不能拆分成更小作業(yè)。 首先 ， 我們 采用 十進(jìn)制編碼， 用 一個一維的 數(shù)組，即 一條染色體 ， 來表示 一種調(diào)度 方案， 這個 數(shù)組中的每一個數(shù)表示 一個 工件 ，該 數(shù)字 出現(xiàn) 的次數(shù)表示這是該工件的第幾道工序 。調(diào)度的任務(wù)是根據(jù)生產(chǎn)目標(biāo)和約束，為每個加工對象確定具體的加工路線、時間、機(jī)器和操作等。 最后 當(dāng) 迭代達(dá)到 規(guī)定 次數(shù) 時 ，終止 迭代，從最終種群中 挑選出 適應(yīng)度最高的染色體，即為最優(yōu) 方案 。 2. 遺傳算法 簡介 基本 內(nèi)容 遺傳算法，英文名 Geic Algorithm，是一種通過模擬達(dá)爾文進(jìn)化論的自然選擇學(xué)說和遺傳學(xué)機(jī)理的生物進(jìn)化過程的計算模型，作為一種交叉學(xué)科相互影響相互促進(jìn)的結(jié)果，遺傳算法借鑒了生物界進(jìn)化的諸多規(guī)律，并以此為基礎(chǔ)，通過模擬自然進(jìn)化過程，進(jìn)行高效率的隨機(jī)化最優(yōu)解搜索。在遺傳算法的應(yīng)用 中，表示通過交配原則產(chǎn)生一組新解的過程。實數(shù)編碼解決了二進(jìn)制和十進(jìn)制編碼對算法精度和存儲量的影響，同時便于優(yōu)化中引入問題的相關(guān)信息，譬如梯度信息。 點(diǎn)式交叉算子分為單點(diǎn)交叉和多點(diǎn)交叉。一種簡單的變異方法是替換一個或多個基因。 遺傳算法作為一種快捷、簡便、容錯性強(qiáng)的算法，在各類結(jié)構(gòu)對象的優(yōu)化過程中顯示出明顯的優(yōu)勢。傳統(tǒng)的優(yōu)化算法從解空間的一個初始 點(diǎn)開始最優(yōu)解的迭代搜索過程。 以下 是 整個 過程的流程圖 ： 生產(chǎn) 調(diào)度問題 的 數(shù)學(xué)描述 不失一般性，設(shè) n 個作業(yè) m 臺機(jī)器的車間作業(yè)調(diào)度問題滿足以下約束條件 （下文中的 “ 工件 ” 與 “ 作業(yè) ” 是同一個概念）： （ 1）每個工件包含若干道工序； （ 2）各工件必須按工藝路線以指定的次序在機(jī)器上加工； （ 3）任何一個工件的前一道工序加工完成后，方能進(jìn)行后一道工序的加工，在同一臺機(jī)器上一個加工任務(wù)完成之后，方能開始另一個加工任務(wù) 。本文采用基于工序的編碼，利用十進(jìn)制直接的表達(dá)方式。適應(yīng)度函數(shù)F（ *）的值 在這 里的意義是這種方案比 完全 一道一道工序來所需 的 時間所節(jié)省的時間，可以從目標(biāo)函數(shù) T（ *）經(jīng)轉(zhuǎn)換得到。 上一步 得到 的 N 個染色體就獲得了 繁殖 的 機(jī)會， 我們 把 N 個染色體 隨機(jī) 配成 N/2 對 ， 對每一對 進(jìn)行 交叉 ，交叉的過程如下：先 在染色體 中 隨機(jī)取一個點(diǎn) ，然后把兩條染色體該 點(diǎn) 以后 的 基因 進(jìn)行交換 。 更重要 的 是 ，采用同時處理群體中多個個體的方法，降低了陷入局部最優(yōu)解的可能性，并易于并行化。 templatetypename Fwd void printRange(Fwd first,Fwd last,char delim=39。,39。 vectorint