楊彩虹 林守金 楊明

摘要：為提高孔群模具的加工效率，提出了一種最近鄰、遺傳算法和禁忌搜索相融合的改進(jìn)遺傳算法。采用最近鄰算法選取一系列好的初始種群，同時(shí)將禁忌搜索中“禁忌”的思想引入到遺傳算法中，并在進(jìn)化過(guò)程中隨機(jī)引入部分新個(gè)體，進(jìn)行迭代搜索。根據(jù)孔群加工特點(diǎn)建立了類似旅行商問(wèn)題的數(shù)學(xué)模型，并用改進(jìn)算法求解最短加工路徑，在分布復(fù)雜的孔類模具上進(jìn)行數(shù)值實(shí)驗(yàn)。輪胎實(shí)例應(yīng)用結(jié)果表明，改進(jìn)算法優(yōu)化后路徑長(zhǎng)度比CAM系統(tǒng)算法優(yōu)化后路徑長(zhǎng)度縮短5.31%，比X向路徑法縮短77.88%，比Y向路徑法縮短77.63%，比最近鄰算法縮短4.52%;當(dāng)實(shí)驗(yàn)參數(shù)相同時(shí)，改進(jìn)算法路徑長(zhǎng)度比遺傳算法縮短14.65%，且運(yùn)行時(shí)間平均縮短了63.60%。改進(jìn)算法的路徑長(zhǎng)度明顯縮短，有效提高了孔群的數(shù)控加工效率。其通用性較好，在提升數(shù)控系統(tǒng)孔群加工效率方面具有參考價(jià)值。

關(guān)鍵詞：應(yīng)用數(shù)學(xué);孔群加工;最近鄰;禁忌搜索;遺傳算法

中圖分類號(hào)：TP399文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1008-1534（2019）02-0091-07

在數(shù)控加工中，孔群加工占比較大，通過(guò)優(yōu)化算法實(shí)現(xiàn)對(duì)孔類模具數(shù)控加工路徑的優(yōu)化顯得尤為重要[1-2]。目前，數(shù)控加工程序的編寫多采用人機(jī)交互方式實(shí)現(xiàn)，后置處理可選擇的路徑一般有2～3種可選。利用后置軟件處理加工路徑時(shí)，有時(shí)會(huì)導(dǎo)致刀具在幾個(gè)區(qū)域間來(lái)回跳轉(zhuǎn)，同時(shí)又要抬高刀具，極其浪費(fèi)時(shí)間且不能保證路徑的優(yōu)越性。因此，孔群的加工路徑規(guī)劃往往依靠人工經(jīng)驗(yàn)制定，極大地浪費(fèi)了人力物力資源。隨著機(jī)械制造業(yè)的快速發(fā)展，傳統(tǒng)人工制定加工路徑的方法難以滿足實(shí)際生產(chǎn)需要，盡量縮短刀具空行程，減少走刀的時(shí)間，提高加工生產(chǎn)效率已成必然趨勢(shì)[3]。因此，數(shù)控編程實(shí)現(xiàn)孔群加工路徑的優(yōu)化是目前亟待解決的關(guān)鍵問(wèn)題。

孔類模具數(shù)控加工路徑的優(yōu)化過(guò)程可以看作是旅行商問(wèn)題[4-5]，旅行商問(wèn)題是一個(gè)經(jīng)典的NP難度的組合優(yōu)化問(wèn)題，對(duì)于大規(guī)模的TSP問(wèn)題，得到最優(yōu)解非常困難，因此人們提出了許多常見的近似解法，如最近鄰算法、插入算法、r-opt算法、Clark&Wright算法、雙生成樹啟發(fā)式算法、Christofides算法[6]，但由于這些算法的缺陷可能不適用于某些特定問(wèn)題，獲取的近似解可能會(huì)偏離于最優(yōu)解。隨著科學(xué)技術(shù)的不斷發(fā)展，許多實(shí)際問(wèn)題不可能在有效的時(shí)間內(nèi)找到相對(duì)較優(yōu)的解，促使啟發(fā)式算法的出現(xiàn)，如遺傳算法[7]、粒子群優(yōu)化算法、蟻群優(yōu)化算法[8]、模擬退火算法、人工神經(jīng)網(wǎng)絡(luò)、進(jìn)化策略、進(jìn)化編程、禁忌搜索和免疫計(jì)算[9]等。

遺傳算法是建立在自然選擇和自然遺傳機(jī)理基礎(chǔ)上的迭代自適應(yīng)概率性搜索算法，模擬自然界優(yōu)勝劣汰的進(jìn)化現(xiàn)象，將搜索空間映射為遺傳空間，把所有可能的解經(jīng)過(guò)編碼使之成為一個(gè)向量（染色體），向量里的每一個(gè)元素稱為基因，然后通過(guò)不斷的計(jì)算各染色體的適應(yīng)度函數(shù)值，選擇最好的染色體，獲得最優(yōu)解[7]。遺傳算法涉及到的概念有編碼、解碼、適應(yīng)度函數(shù)和遺傳操作等概念。采用遺傳算法進(jìn)行路徑規(guī)劃在目前已成為研究熱點(diǎn)，遺傳算法的優(yōu)點(diǎn)在于能很好地處理約束、魯棒性強(qiáng)，具有潛在的并行性，全局搜索能力強(qiáng);缺點(diǎn)是收斂較慢，甚至迭代難以收斂，局部搜索能力弱，運(yùn)行時(shí)間長(zhǎng)，且當(dāng)問(wèn)題規(guī)模較大時(shí)，迭代過(guò)程中會(huì)占用很大的內(nèi)存空間，再加上遺傳算子中的交叉算子使得染色體之間具有很大的相似性，可能導(dǎo)致搜索停滯不前，使種群多樣性減少，同時(shí)，由于變異的力度不夠，遺傳算法的爬山能力很弱，導(dǎo)致種群多樣性得不到補(bǔ)充，使算法出現(xiàn)早熟特征[6-7]。

筆者針對(duì)傳統(tǒng)遺傳算法出現(xiàn)的收斂慢及早熟現(xiàn)象，提出了一種改進(jìn)的遺傳算法，該算法采用最近鄰算法選取一系列好的初始種群，加快了種群的搜索速度，同時(shí)將禁忌搜索中“禁忌”的思想引入到遺傳算法中，并在進(jìn)化過(guò)程中隨機(jī)引入新個(gè)體，保證了種群多樣性，增強(qiáng)了算法的爬山能力，避免了算法出現(xiàn)早熟現(xiàn)象。

1孔群加工路徑模型

針對(duì)多孔型模具的加工，同一平面上存在大量的待加工孔，孔群中也可能會(huì)存在不同類型孔。對(duì)于同一平面內(nèi)的K種不同類型的孔，數(shù)控加工過(guò)程中必須要進(jìn)行換刀操作。但由于換刀必須要回到刀具參考點(diǎn)，可以將每一類孔的加工看作是單一的旅行商問(wèn)題[10]，對(duì)同類孔樣的加工，由于對(duì)各個(gè)孔的尺寸參數(shù)設(shè)定、加工方法都是相同的，因此路徑優(yōu)化可以看成簡(jiǎn)單的點(diǎn)位優(yōu)化，故只考慮一類孔的路徑優(yōu)化問(wèn)題。設(shè)孔群加工模型集合為G=（V，E），其中V={0，1，2，…，n}，0為數(shù)控機(jī)床刀具參考點(diǎn)，1～n代表待加工孔的集合;E為邊的集合，邊（i，j）的權(quán)值為dij，i，j∈V，在該問(wèn)題中dij取歐氏距離;孔群數(shù)控加工路徑優(yōu)化的目標(biāo)為尋找G的優(yōu)化巡回路線，該巡回路線是經(jīng)過(guò)圖V集中每個(gè)頂點(diǎn)恰好一次的路徑，即尋找經(jīng)過(guò)V集的每個(gè)頂點(diǎn)的最短線路。則加工路徑的數(shù)學(xué)模型為

2改進(jìn)遺傳算法在孔群加工路徑中的應(yīng)用

針對(duì)孔群加工路徑問(wèn)題，筆者提出了一種改進(jìn)遺傳算法，該算法是一種基于最近鄰、禁忌搜索和遺傳算法的新型遺傳算法。算法的編碼方式，適應(yīng)度函數(shù)的選取，種群選擇策略，交叉變異的方式都影響整個(gè)算法的運(yùn)行效率。

2.1編碼方式

針對(duì)n個(gè)孔的加工路徑問(wèn)題，求解的一個(gè)重要環(huán)節(jié)是對(duì)其進(jìn)行編碼。在該問(wèn)題中采用路徑表示法的編碼方法。二進(jìn)制編碼不適合孔群加工問(wèn)題，這是由染色體長(zhǎng)度n和每一個(gè)后代解驗(yàn)證的復(fù)雜性所決定。種群中每個(gè)染色體長(zhǎng)度為n，染色體中的每個(gè)基因由1～n的數(shù)字組成，0為數(shù)控機(jī)床刀具參考點(diǎn)，1～n代表待加工孔的集合，染色體為1～n的全排列。染色體的每個(gè)基因排序即表示對(duì)每個(gè)孔進(jìn)行排序。

2.2適應(yīng)度函數(shù)的選擇

對(duì)于一條路徑的優(yōu)劣，判斷的標(biāo)準(zhǔn)是看其適應(yīng)度函數(shù)的值，針對(duì)該問(wèn)題，用其路徑長(zhǎng)度的倒數(shù)作為其適應(yīng)度函數(shù)的值，即

當(dāng)Fitness（x）值越大時(shí)，F(xiàn)（x）值就越小，表明加工路徑總長(zhǎng)度越短，對(duì)應(yīng)加工路徑越好。一般迭代次數(shù)作為終止條件，因此，在最后一代中最好的染色體可能是局部最優(yōu)解或是全局最優(yōu)解。

2.3種群選擇策略

種群選擇策略采用精英保留策略，此方法是比較種群中所有個(gè)體的適應(yīng)度值，從中擇優(yōu)選擇一部分個(gè)體作為父體，并利用選擇的個(gè)體進(jìn)行交叉和變異操作。

1）交叉交叉是父代將自身優(yōu)秀基因遺傳給子代的一種繁殖操作，對(duì)于每一個(gè)交叉操作，利用選擇策略選出的個(gè)體參與交叉操作，產(chǎn)生適應(yīng)度值高的新個(gè)體的可能性更高。常用交叉算子有順序交叉（orderedcrossover，OX），部分映射交叉（parliallymappedcrossover，PMX），循環(huán)交叉（cyclecrossover，CX）[11];改進(jìn)算法選擇順序交叉算子，在父代F1中隨機(jī)選擇2個(gè)交叉點(diǎn)，將父代F1交叉點(diǎn)之間的基因片段作為子代K相同位置的基因片段，把F2中非F1交叉點(diǎn)之間的基因按順序分別放在子代K的基因片段兩邊的位置，生成新的子代個(gè)體。以染色體長(zhǎng)度n=10為例，選擇父代F1和F2，若隨機(jī)選擇交叉點(diǎn)位置為4，7，則具體交叉操作如下。

父代F1：[WB]238（9675）1014，

父代F2：[DW]65374210198，

子代K：[DW]342（9675）1018，（6）

2）變異變異是在保留父代優(yōu)秀基因并保持種群多樣性的一種進(jìn)化手段。常用變異算子有：移位變異（displacementmutation，DM），交換變異（exchangemutation，EM），逆轉(zhuǎn)變異（inversionmutation，IVM）[11];改進(jìn)算法采用交換變異算子進(jìn)行變異操作，隨機(jī)作用在一個(gè)父代染色體上，在父代F中隨機(jī)選擇4個(gè)變異點(diǎn)，按升序排列n1<n2<n3<n4，將父代F中[n1，n2]之間基因片段與其[n3，n4]之間基因片段互換生成新的子代K。以染色體長(zhǎng)度n=10為例，選擇父代F，若隨機(jī)選擇變異點(diǎn)位置為2，3，7，9，則具體變異操作如下：

父代F：[WB]6（51）742（1038）9，

子代K：[DW]6（1038）742（51）9。（7）

2.4改進(jìn)遺傳算法流程

考慮到最近鄰算法和遺傳算法各自具有優(yōu)缺點(diǎn)，最近鄰算法生成的路徑的基因總體是比較優(yōu)良的，而遺傳算法本身具有很高的并行性等。鑒于此，筆者設(shè)計(jì)了結(jié)合最近鄰和禁忌搜索思想的遺傳算法來(lái)求解加工路徑優(yōu)化問(wèn)題。改進(jìn)遺傳算法的流程如下，算法流程如圖1所示。

Step1.設(shè)定種群大小Numpop、設(shè)定交叉概率crate、變異概率mrate、選擇率srate和隨機(jī)概率rrate，并且設(shè)定算法的終止條件r=Iteration，置進(jìn)化代數(shù)r=0，禁忌表tabu=[];

Step2.將每一個(gè)孔作為出發(fā)點(diǎn)，由最近鄰算法生成的路徑所構(gòu)成的集合記為P，并計(jì)算個(gè)體的適應(yīng)度，從P中隨機(jī)選擇Numpop個(gè)個(gè)體初始化第一代種群S（r）;

Step3.更新禁忌表tabu，禁忌表中存放已經(jīng)搜索過(guò)的路徑;

Step4.擇優(yōu)選擇，比較種群S（r）中所有個(gè)體的適應(yīng)度值，從中擇優(yōu)選擇一部分個(gè)體作為父體F;

Step5.執(zhí)行交叉操作產(chǎn)生新的路徑[AKS-]（r），且新的路徑不與禁忌表中路徑重復(fù);

Step6.執(zhí)行變異操作產(chǎn)生新的路徑[AKS=]（r），且新的路徑不與禁忌表中路徑重復(fù);

Step7.更新父代和子代的并集Srecent（r）;

Step8.隨機(jī)生成新的路徑S*（r），且新的路徑不與禁忌表中路徑重復(fù)（引入新個(gè)體，增加種群多樣性）;

Step9.r←r+1，在Srecent（r）∪S*（r）擇優(yōu)選擇Numpop個(gè)個(gè)體作為新的種群S（r）;

Step10.若滿足終止條件，則停止并輸出最短路徑F（xbest）;否則轉(zhuǎn)Step3。

3輪胎實(shí)例應(yīng)用

3.1遺傳算法與改進(jìn)算法對(duì)比實(shí)驗(yàn)

為測(cè)試改進(jìn)遺傳算法在路徑優(yōu)化中的性能，以大型輪胎模具孔群加工為例，提取輪胎模具Step文件幾何信息得到模具俯視面孔位分布[12-15]，如圖2所示。

針對(duì)圖2中平面孔進(jìn)行路徑的加工優(yōu)化，通過(guò)對(duì)輪胎模具Step文件分析可知，該平面孔為同一類型孔，且孔群規(guī)模為

408個(gè)，采用提出的改進(jìn)算法和遺傳算法分別對(duì)該孔群加工路徑進(jìn)行優(yōu)化，在實(shí)驗(yàn)中，2種算法參數(shù)設(shè)置相同，且參數(shù)設(shè)置如下：種群大小Numpop=180，設(shè)定交叉概率crate=0.9、變異概率mrate=0.02、選擇率srate=0.3和隨機(jī)概率crate=0.9，并且設(shè)定算法的終止條件Iteration=500。通過(guò)實(shí)驗(yàn)，數(shù)據(jù)如表1所示。

由表1可知，經(jīng)過(guò)10次路徑優(yōu)化實(shí)驗(yàn)，遺傳算法的平均路徑長(zhǎng)度為Sgamean=23356.3994mm，最優(yōu)路徑長(zhǎng)度為Sgamin=22400.5508mm，平均運(yùn)行時(shí)間Tgamean=10547.4750s，改進(jìn)算法的平均路徑長(zhǎng)度為Simgamean=19934.0159mm，最優(yōu)路徑長(zhǎng)度為Simgamin=19930.7042mm，平均運(yùn)行時(shí)間Timgamean=3839.2024s。與遺傳算法相比，改進(jìn)算法的平均路徑長(zhǎng)度縮短了14.65%，最優(yōu)路徑長(zhǎng)度縮短了11.03%，平均運(yùn)行時(shí)間縮短了63.60%。為了更好地對(duì)比算法性能，利用Matlab軟件繪制出2種算法適應(yīng)度進(jìn)化曲線圖，如圖3所示。

從圖3中可以看出，在迭代次數(shù)相同時(shí)，改進(jìn)算法的適應(yīng)度值更大，故而路徑更優(yōu)，且與傳統(tǒng)遺傳算法相比，能更快收斂到全局最優(yōu)。圖4為遺傳算法在上述參數(shù)下的最優(yōu)加工軌跡圖，圖5為改進(jìn)算法最優(yōu)加工軌跡圖。

3.2其他優(yōu)化算法對(duì)比實(shí)驗(yàn)

為驗(yàn)證改進(jìn)算法的先進(jìn)性，分別采用自主研發(fā)的CAM系統(tǒng)算法、X向路徑法、Y向路徑法對(duì)該模具孔群進(jìn)行路徑優(yōu)化。其中X向路徑法是按照孔群X坐標(biāo)值升序排列進(jìn)行加工的過(guò)程，Y向路徑法是按照孔群Y坐標(biāo)值升序排列進(jìn)行加工的過(guò)程。圖6a）為CAM系統(tǒng)算法生成的軌跡圖，圖6b）為X向路徑法生成的軌跡圖，圖6c）為Y向路徑法生成的軌跡圖。

3.3實(shí)驗(yàn)結(jié)果及數(shù)據(jù)分析

由表2中不同優(yōu)化方法孔群加工最優(yōu)路徑長(zhǎng)度對(duì)比可知，改進(jìn)算法優(yōu)化后路徑長(zhǎng)度比CAM系統(tǒng)算法優(yōu)化后路徑長(zhǎng)度縮短5.31%，比X向路徑法縮短77.88%，比Y向路徑法縮短77.63%，比最近鄰算法縮短4.52%，進(jìn)化代數(shù)500次且參數(shù)相同時(shí)，比遺傳算法路徑長(zhǎng)度縮短14.65%。由此可見，改進(jìn)算法優(yōu)化后路徑長(zhǎng)度最短，能夠有效縮短孔群加工路徑長(zhǎng)度，減少加工時(shí)間，從而提高了加工效率。

4其他模具實(shí)例應(yīng)用

為驗(yàn)證改進(jìn)算法的通用性，對(duì)非均勻，變化比較復(fù)雜的某孔類模具實(shí)例進(jìn)行路徑優(yōu)化實(shí)驗(yàn)，該模具實(shí)例由197個(gè)非均勻分布的孔構(gòu)成，分別用最近鄰算法，自主研發(fā)的CAM系統(tǒng)算法，X向路徑法，Y向路徑法，遺傳算法以及改進(jìn)遺傳算法對(duì)該模具孔群進(jìn)行路徑優(yōu)化，不同算法最優(yōu)加工軌跡見圖7。表3為不同優(yōu)化方法的最優(yōu)路徑長(zhǎng)度結(jié)果及比較。

從表3可知，提出的改進(jìn)遺傳算法相較其他算法加工路徑長(zhǎng)度明顯縮短，可以有效提高加工效率。

5結(jié)語(yǔ)

提出的改進(jìn)遺傳算法，結(jié)合了最近鄰和禁忌搜索的思想。采用最近鄰算法選取一系列好的初始種群，加快了種群的搜索速度，同時(shí)將禁忌搜索中“禁忌”的思想引入到遺傳算法中，使得種群在進(jìn)化過(guò)程中保證了多樣性，增強(qiáng)了算法的爬山能力，避免了算法出現(xiàn)早熟。輪胎實(shí)例以及其他模具實(shí)例表明，采用改進(jìn)遺傳算法進(jìn)行孔群加工路徑優(yōu)化能以較快的速度找到更優(yōu)的解，極大地提高了生產(chǎn)效率和節(jié)省資源消耗，在實(shí)際生產(chǎn)輪胎模具中已得到證實(shí)。同時(shí)，在其他類型實(shí)例的加工路徑的優(yōu)化問(wèn)題中可利用本算法進(jìn)行路徑優(yōu)化，也能取得較好的結(jié)果。但當(dāng)孔群規(guī)模特別大時(shí)，算法運(yùn)行效率有待提升，下一步的研究重心將放在提高超大規(guī)?？兹郝窂絻?yōu)化的運(yùn)行效率方面。

參考文獻(xiàn)/References：

[1]LUONGLHS，SPEDDINGT.Anintegratedsystemforprocessplanningandcostestimationinholemaking[J].TheInternationalJournalofAdvancedManufacturingTechnology，1995，10（6）：411-415.

[2]龔玉玲，武美萍，徐曉棟，等.基于改進(jìn)遺傳算法的孔群數(shù)控加工路徑優(yōu)化[J].組合機(jī)床與自動(dòng)化加工技術(shù)，2017（11）：52-56.

GONGYuling，WUMeiping，XUXiaodong，etal.Researchonpathoptimizationofholegroupmachiningbasedonimprovedgeneticalgorithm[J].ModularMachineTool&AutomaticManufacturingTechnique，2017（11）：52-56.

[3]段振云，孔令斌，趙文輝，等.覆蓋件模具數(shù)控加工方法的研究[J].組合機(jī)床與自動(dòng)化加工技術(shù)，2015（4）：123-125.

DUANZhenyun，KONGLingbin，ZHAOWenhui，etal.ResearchonthemethodsofcoveringpartsmouldNCmachining[J].ModularMachineTool&AutomaticManufacturingTechnique，2015（4）：123-125.

[4]周正武，丁同梅.基于TSP和GA孔群加工路徑優(yōu)化問(wèn)題的研究[J].組合機(jī)床與自動(dòng)化加工技術(shù)，2007（7）：30-32.

ZHOUZhengwu，DINGTongmei.ResearchonholesmachiningpathplanningoptimizationwithTSPandGA[J].ModularMachineTool&AutomaticManufacturingTechnique，2007（7）：30-32.

[5]ZHANGWeibo，ZHUGuangyu.Drillingpathoptimizationbyoptimalforagingalgorithm[J].IEEETransactionsonIndustrialInformatics，2017（99）：1-1.10.1109/TII.2017.2772314.

[6]文永軍.旅行商問(wèn)題的兩種智能算法[D].西安：西安電子科技大學(xué)，2010.

WENYongjun.TwokindsofIntelligentAlgorithmsforTravelingSalesmanProblem[D].Xi′an：XidianUniversity，2010.

[7]汪定偉.智能優(yōu)化方法[M].北京：高等教育出版社，2007.

[8]潘曉萌，李冰.蟻群算法優(yōu)化和路徑規(guī)劃問(wèn)題的應(yīng)用研究[J].科技通報(bào)，2016，32（6）：99-103.

PANXiaomeng，LIBing.Applicationofantcolonyoptimizationandpathplanning[J].BulletinofScienceandTechnology，2016，32（6）：99-103.

[9]王磊，肖人彬.基于免疫記憶的人工免疫算法模型及其應(yīng)用[J].模式識(shí)別與人工智能，2002，15（4）：385-391.

WANGLei，XIAORenbin.Analgorithmicmodelofartificialimmunesystembasedonimmunologicalmemoryanditsimplementation[J].PatternRecognitionandArtificialIntelligence，2002，15（4）：385-391.

[10]肖軍民.一種改進(jìn)遺傳算法在孔群加工路徑中的優(yōu)化[J].組合機(jī)床與自動(dòng)化加工技術(shù)，2015（2）：151-153.

XIAOJunmin.OptimizationofNCmachiningpathforholesbasedonimprovedgeneticalgorithm[J].ModularMachineTool&AutomaticManufacturingTechnique，2015（2）：151-153.

[11]王春香，郭曉妮.基于遺傳蟻群混合算法的孔群加工路徑優(yōu)化[J].機(jī)床與液壓，2011，39（21）：43-45.

WANGChunxiang，GUOXiaoni.Holesmachiningpathoptimizationbasedonahybridalgorithmintegratedgeneticalgorithmwithantcolonyoptimization[J].MachineTool&Hydraulics，2011，39（21）：43-45.

[12]趙繼俊.優(yōu)化技術(shù)與MATLAB優(yōu)化工具箱[M].北京：機(jī)械工業(yè)出版社，2011.

[13]SUHSH，CHOJH，HONGHD.OnthearchitectureofintelligentSTEP-compliantCNC[J].InternationalJournalofComputerIntegratedManufacturing，2002，15（2）：168-177.

[14]盛濱.基于STEP-NC的信息提取系統(tǒng)的研究與實(shí)現(xiàn)[D].廈門：廈門大學(xué)，2008.

SHENGBin.ResearchandImplementationofInformationExtractionSystembasedonSTEP-NC[D].Xiamen：XiamenUniversity，2008.

[15]ISO10303-21.Industrialautomationsystems-Productdatarepresentationandexchange-Part21：Implementationmethod：Cleartextencodingoftheexchangestructure[S].1997.