狠狠撸

勤益科技大學工業工程與管理學系曾懷恩進化式演算法在製造與管理議題的應用

碩士與學士的區隔思考清楚自己的定位與這兩年想要充實的能力正確的態度：心智模式與追求卓越系統觀與思辨的能力語言能力具備實證與執行的能力專長 (30 歲前的謀生能力 ) 程式語言、資料結構繪圖能力、 AutoCAD 與 SolidWORKs ??? 要不要繼續念博士班的企圖

帶領研究生的心得思考清楚自己的定位到最適合的研究室。老師的個性與風格也是考慮的重點。付出與所得成正比、對於自己選定的路不要後悔。注意兩年的進度與時程。碩士論文絕對是研究的重心所在。論文通常是具備實務或學術上的價值，只要能滿足一方面的要求就可以。以碩士論文的方向作為修課的依據。

寫程式 ?? 對於管理學院的學生 ( 資管系除外 ) 至今仍是很困難的工程。寫程式是磨鍊心志的好方法。邏輯能力的整理與訓鍊。沒有捷徑但可快步到位。爬樓梯式的階段式進程。沒有耕耘就不會有收獲。只要努力就一定會進步。自我能力的培養與肯定。

程式語言程式語言（ programming language ），又稱程式設計語言（ program design language ），是一組用來定義電腦程式的語法規則。它是一種被標準化的交流技巧，用來向電腦發出指令。一種電腦語言讓程式設計師能夠準確地定義電腦所需要使用的資料，並精確地定義在不同情況下所應當採取的行動。程式＝資料結構＋演算法

程式階梯基本關 – 變數、邏輯、迴圈、函數指標關 (Pointer) 資料結構 (Data structure) 物件導向 (Object-Oriented) STL (S tandard Template Library) 演算法 (Algorithms) 統一建模語言 UML (Unified Modeling Language)

何謂結構 (Data structures)? 結構是定義你所需要之特殊種類物件的資料型態。 Structure 將彼此相關的變數聚合 (Aggregate) 成單一的單元 ( 模組 ) ，基本上是利用不同的資料型態與使用者定義的資料型態等的混合體，用來達到資料的抽象化 (data abstraction) 。其好處是資料概念的具體化及資料表達的簡化。如 Link list 及 Binary-tree 都是典型的範例。 C 的延伸性資料型態的宣告，其語法如下： struct 延伸性資料型態的名稱 { 資料型態 ? 變數名稱 ,..., 變數名稱 ; . . . };

演算法的定義演算法 (algorithm) 在韋氏辭典定義為：“在有限步驟內解決數學問題的程序”。在計算機科學的領域中，我們所解決的問題不再只限於數學問題，因此演算法泛指適合被實作為計算機程式的解題方法。例如算出兩個自然數的最大公因數的演算法，稱為歐幾里得演算法。或是排列資料順序的演算法，統稱為排序演算法。

演算法的特性 l. 準確描述的輸入 (Input) ；演算法通常是接受一些輸入，加以處理或運算，而?產生一些輸出值。這些輸入必須有清楚的型別和個數描述。例如前面提到的?歐幾里得演算法，需要兩個自然數作為輸入。 2. 每一指令必須具有明確性 (Definiteness) 及有效性 (Effectiveness) ；清楚而不造成? 混淆，並且能讓人們用紙筆來執行。 3. 正確性 (Correctness or Definiteness) ；演算法既是以解題為目的，所以我們必須?? 能夠證明一演算法可以正確地解決問題。 4. 有限性 (Finiteness) ；演算法必須在有限步驟內結束。通常我們不需要知道執行步驟的確實數目，而是它的上限。也就是說，我們比較想知道執行此演算法的步驟 ( 或時間 ) 不會超過某個上限。這對我們了解並評估演算法相當重要。 5. 結果的描述和輸出 (Output) ；例如歐幾里得演算法的輸出，是兩個自然數的最大公因數，也是自然數。

演算法共通特性存在許多可能解答值得花很多時間找出較佳的演算法直觀方式演算解決小問題很方便，但是面對大問題一籌莫展存在許多實際應用尋找最短路徑，以降低貨運或者航空公司燃料耗損成本

演算法的表示演算法與使用哪一種程式語言撰寫沒有絕對關係建立思考過程以不同的處理邏輯與順序達成某種特定的目的文字、流程圖、虛擬碼

演算法的最佳化找到演算法的瓶頸所在或是耗費計算資源最多的地方，這時候我們需要進行最佳化的動作，讓演算法臻至完美要挑選合適的演算法可以幫助一個大型計算程式節省數分鐘，甚至數天的計算時間。一个好的演算法通常是要靠知识、经验的累积才能够设计出最适合问题的演算法。

演算法的設計考量如何設計演算法？如何表示演算法？如何證明問題解決的正確性？如何評估效能？如何進行最佳化？

名詞 Evolution Algorithms=Genetic algorithms + Data Structures

基因演算法 (Genetic algorithms) 簡介 GA 是一種模擬「物競天擇」、「適者生存」的搜尋法則；每個物種在某個生存環境中彼此互相競爭、淘汰，只有適應性強的物種得以存活及繁衍；並透過複製、交配、突變等演化方式產生下一代的物種，如此反覆進行，最後留下適應性最強的物種。而 GA 的遊戲規則就是「適者生存」。 GA 主要是以操作染色體 (Chromosome) 來進行演化過程，在反覆演化的過程中，可看成是在問題的可行區域中做系統化的多維空間搜尋；而其特點為多點搜尋、只需適應值資訊、轉移規則是隨機性而非決定性的。另外 GA 的搜尋方式是屬於平行式而非循序式的，這點和 Greedy 、 Tabu 、模擬退火法等的搜尋方式有很大的不同。

General structure of genetic algorithms

母體（族群、人口） Population 母體的產生隨機產生染色體或是利用啟發法產生染色體直到達到所設定的母體數。另外當一個初始母體經過一系列的遺傳操作後（複製、交配、突變），子代隨即產生，此時就必須考慮要用何種方式去取代母體。完全取代並無保留優秀下一代的意義、運用菁英保留技巧是常用的技巧。 copy Crossover & Mutation Best Other 20% 80%

Genetic operator: Crossover and mutation 交配操作是遺傳演算法重要的操作；它將兩個母代的部份資訊交換，而產生兩個子代；交配運算就猶如在解空間中作大幅度的跳躍搜尋，母代是否要進行交配運算取決於交配率。突變操作在 GAs 被視為次要操作；此種操作與一般演算法的鄰近區域搜尋的觀念相類似，而某染色體是否突變則取決於突變率。在遺傳演算法中，藉由突變操作可增加母體的異樣程度。

適應度函數 (Fitness function) 雖然目標函數值可用來評估染色體的優劣，但由於問題的不同；例如：極大化和極小化問題並非都可直接利用目標函數值來評估，適應度函數的設計是 GAs 的重點。 Fitness function 的設計必須滿足「適者生存」的觀念，亦即染色體越佳，其適應值就越高，且在演化過程中就越容易存活。例如對極小化問題，可令適應度函數 fintess(X)=1/X ，其中 X 為目標函數值。如此目標函數值越高者，則適應度越差且越不易存活。

選擇機制人工遺傳系統模仿自然界「適者生存」的工具，主要功能是用來確定某個染色體被複製的個數；適應度函數和選擇機制兩者配合使用，即可實現 GAs 中的複製操作過程。如同自然界的演化規則一樣；遺傳演算法讓較優解在複製過程中複製較多的個數，如此在後續的操作過程中，就有較高的機會可以存活。 Holland 在 GAs 中應用輪盤法 (Roulette wheel) 來實現此一概念。

輪盤法 (Roulette wheel) 其中 f i 為染色體 i 的適應性值；如此適應度越高則所佔的面積就越大。假設對此輪盤射一飛鏢，當然面積越大的就越容易射中，如此被複製的機率就越高，重複此步驟，直到複製完相等於母體數的染色體。

研究重點 2 客製化為基的規劃模式 (Customization manufacturing) 1 以 connector 為基的組裝規劃模式 5 基因演算法 (Genetic algorithms ) 6 群蟻演算法 (Ant colony algorithms) 7 模擬退火法 (Simulated annealing algorithms) 3 模組化議題的探討 (Product modularity) 4 綠色環保議題的探討 (Design for environment)

以 connector 為基的組裝規劃模式 1 Journal of Intelligent Manufacturing , 10, 423-435 (1999)

研究動機過去組裝模式的描述大多採用產品零件 , 易產生之問題只可解較少的零件數目之組裝規劃問題。包含的資訊太少。 Tseng and Li(1999) 提出 Connector-based 的組裝規劃模式可以有效地解決這些問題，並降低產品的複雜度。

Connector 觀念及其相關工程資訊 Connector 是以零件間的「結合型態」作為產品的描述依據，本身扮演著設計階段觀念層次的建構單元，故可包含著更多工程資訊。運用啟發式求解組裝順序。

Connector 為基與 GAs 結合 2 International Journal of Production Research , 42(11), 2243-2261 (2004)

Focus How to turn the connector concept into genetic coding? What are the operation mechanisms of a GA? How to apply (1) and (2) in practical cases?

Basic idea for connector A connector example : bolt-nut-washer (b) Information on bolt-nut-washer connector

Classification of fastener types 3 Races and ball-bearing balls MND Not disassembled 1 snap ring, bearing, spring MD Disassembled Movable fastener 4 pressing fits, riveted joints, welding FND Not disassembled 2 Screw, bolted joint, key, spline, wedge FD Disassembled Fixed fastener level Example Code Type

Example: stapler (a) Part drawing (a) Part information Pivot rod 18 Guide rod 9 Rivet4 17 Bottom track 8 Rivet3 16 Staple spring 7 Fastener piece 15 狠狠撸 foot 6 Rivet bottom 14 Pivot spring 5 spring 13 Steel top 4 base 12 Rivet1 3 Impact plate 11 Bracket spring 2 Rivet2 10 Steel cover 1 Part name Part No. Part name Part No.

connector-based precedence graph.

Note: (1) FD: Fixed fastener disassembled (2) FND: Fixed fastener Not disassembled (3) MD:Movable fastener disassembled (4) MND: Movable fastener Not disassembled (5) T 1 : hand (6) T 2 : screwdriver (7) T 3 : a hand vice Connector information of stapler 1,4,8,12,18 T 3 z FND Interference fit C 8 1,2,3 T 3 y FND Interference fit C 7 6,5,4 T 1 -y MD Snap fit C 6 8,9 T 1 x FND Insert C 5 6,7 T 1 -x MD Spring C 4 6,9 T 1 -x FND Insert C 3 7,9 T 1 -x MD Spring C 2 12,15,16,17 T 3 y FND Interference fit C 1 10,11,12,13,14 T 3 -y FND Interference fit C 0 Component owned by connector Tool Direction Combination type Connector name No.

Connector object (Mapping from 2(b))

Concept for fitness function The lower the frequency of alternation of the precedence sequence for a product, the higher the probability it will fit and survive.

Weight design wc + wd + wt = 1. If the result of ranking order is w1 ≥ w2 ≥ w3 ≥…≥ wn ≥ 0 , the summation of the number of weights is referred to as sum-of-ranks. the relative weight of the most important attribute will be n/(sum-of-ranks)

Calculate the fitness value Connector information Generate initial populations Reproduction: Roulette Wheel method PMX crossover Insert mutation method Optimal solutions obtained (1) (2) (3) (4) (5) (6) (7) No Satisfy the stopping criteria ? Generate new population number of populations, mutation rate, crossover rate, stopping criteria. (1) Yes The flow chart that combines the connector concept and the GAs

Case study – a computer Part drawing

Computer: connector-based precedence graph

Interface of the computer program with the GAs

Result If the weight value of each engineering feature is assigned to equal (i.e., wc = wd = wt = 1/3). the connector-based assembly sequence of the computer hard disk will be as follows: {12, 7, 0, 10, 8, 5, 6, 2, 4, 1, 3, 22, 18, 17, 11, 14, 9, 15, 16, 13, 21, 19, 20} The average computation time over 10 trials at hard disk was 0.9108 second.

Convergence plot of stapler Convergence plot of computer hard disk

Conclusions As a comparison, the traditional heuristic algorithm developed from liaison graph, connector-based approach was another novel research direction for the assembly planning. To make this research efficient and flexible, the following features are introduced: Object-oriented programming and standard template library (STL) syntax was used to combine the connector concept and GAs; Parameter values found by experiment were significant for the quality of GA’s solution.

Guided-GAs 引導式基因演算法 3 International Journal of Production Research, 44(3), 601-625 (2006)

引导式基因演算法流程图

引导式基因演算法首先對染色體進行編碼，其中基因碼編號代表 Connector 編號，基因碼位置代表 Connector 組裝順序，如下圖所示：

引导式基因演算法本研究透過二元樹的觀念，與 Connector 優先關係矩陣結合，建構以 Connector 為基之二元樹，而建構以 Connector 為基之二元樹必須滿足下面兩個準則。 (1) 二元樹左邊子節點之 Connector 的組裝優先順序，必須優先於根節點之 Connector 。 (2) 右邊子節點之 Connector 的組裝優先順序為最小。

引导式基因演算法當 Connector 為基之二元樹建構完整後，本研究採用中序拜訪排序出 Connector 組裝順序。因為中序的拜訪程序為先拜訪左子樹，然後拜訪樹根，最後再拜訪右子樹，故中序拜訪所排列出組裝順序必定符合 Connector 優先關係。

引导式基因演算法本研究適應性函數是以 Connector 之工程資訊相似度為基，計算整個 Connector 組裝順序之工程資訊相似度總和，如公式 (3) 所示：

引导式基因演算法本研究為了防止染色體中好的基因碼被破壞，故將以基因碼適應值作為產生基因碼保留區間的依據，其演算方法如下： Step1 ：令 i=1 。 i=1.2.3….m m 為染色體之長度。 Step2 ：令區間起始位置 Block-start =i ，而區間大小 Block-size=0 。 Step3 ：隨機產生一浮點數 p ，其中 p 介於 1 到 0 之間。

引导式基因演算法 Step4 ：依據公式 (4) 計算染色體位置 i 之 Connector 與 i+1 位置之 Connector 工程相似度，佔染色體位置 i 之 Connector 與其它 Connector 中相似度最大之比例。

引导式基因演算法 Step5 ：判斷 p 與 Ri 大小。 (a). 若 Ri 大於等於 p ，則 i 與 Block-size 加一，並且重複 Step3 至 Step5 步驟。 (b). 若 Ri 小於 p ，且 Block-size 小於三分之一的染色體長度，則對 i 加一並且重複 Step2 至 Step5 步驟。否則進行 Step6 步驟。 Step6 ：終止搜尋並且以 Block-start 為保留區間之起始位置，而 Block-size 為保留區間之大小。

引导式基因演算法本研究之引導式交配法在演化過程中考慮了問題之限制條件，故引導式交配法所產生之子代必定是可行解，其演化步驟如下：

引导式基因演算法本研究發展一種引導式突變法，以防止染色體經過突變機制後變成不可行解，而其演化步驟如下所示：

范例测试本研究分別探討釘書機、電風扇與印表機三個測試範例，對於引导式基因演算法之求解品質的影響。首先以釘書機為範例在交配率為 70% 、突變率為 30% 、母體大小為 21 的測試環境下，比較引导式基因演算法與 Tseng ,Li and Chang(2004) 所提出之傳統基因演算法之求解效率是否有差異

電風扇交配率為 70% 、突變率為 30% 、母體大小為 51 、最大世代數為 1500 代的測試環境 0 137 17.3333 16.6666 Guided-GAs 6 879 17 6.5999 Traditional-GAs Times of infeasible solution Average generations of convergence Max fitness value Average fitness value Method

Convergence plot of electrical fan.

Part drawing of the laser printer 0 76.6666 75.5333 Guided-GAs 10 0 0 Traditional-GAs Times of infeasible solution Max fitness value Average fitness value Method

结论與建議結合二元樹觀念所產生之初始母體可以大幅提昇基因演算法之求解品質。引导式基因演算法其求解品不但比傳統基因演算法還要好，而且其以較少世代數將解收斂於較好的解，故引导式基因演算法可以用較短時間搜尋到較好的解。

Memetic Algorithms 改良式基因演算法 4 Expert Systems with Applications 33(2), 451-467 (2007)

改良式基因演算法否是是否

適應值計算本研究適應性函數是以 Connector 之工程資訊相似度為基，計算整個 Connector 組裝順序之工程資訊相似度總和，如公式 (3) 所示：

交配 (2/2) Partial Mapped Crossover(PMX)

突變突變機制主要是在產生變化較大之染色體，以防止基因演算法過早收斂於區域最佳解。 Inversion Mutation( 單點突變 )

范例测试 (1/11) 本研究分別探討釘書機、電風扇與印表機三個測試範例，對於雙基因演算法之求解品質的影響。首先以釘書機為範例在交配率為 70% 、突變率為 30% 、母體大小為 21 的測試環境下，比較改良式基因演算法與 Tseng(2006) 所提出之 Guided-GAs 之求解品質是否有差異。

范例测试 (2/11) 5.67 5.627 MAs 5.67 5.495 Guided-GAs 最大適應值平均適應值方法

范例测试 (3/11) 電風扇是一個限制條件較複雜之測試範例，本研究在交配率為 70% 、突變率為 30% 、母體大小為 51 、最大世代數為 1500 代的測試環境下，比較改良式基因演算法與引导式基因演算法之求解品質是否有差異。 18.333 18.285 3.951 MAs 16.667 16.133 2.808 Guided-GAs 最大適應值平均適應值平均時間方法

范例测试 (5/11) 印表機範例是本研究所列舉之三個範例中，限制式最複雜的一個範例，本研究將以此範例來比較改良式基因演算法與引导式基因演算法之求解品質是否有差異。 80 79.096 25.97 改良式基因演算法 76.67 75.595 18.5427 引导式基因演算法最大適應值平均適應值平均時間方法

范例测试 (8/11) 81 79.596 90.89 MAs 77.66 76.862 118.691 Guided-GAs 最大適應值平均適應值平均時間方法

结论 MAs 除了可以解決限制式過多之問題亦可求得比 Guided-GAs 品質較佳之解與求解的效率。本研究測試最高案例為 200 個 Connector ，測試結果皆能搜尋出可行解，此外，並給予定義以至少要有兩層”隱藏層“為基準且當組裝規劃問題經過複雜度公式計算大約為 70 以上時，即可稱之為 " 限制式較多之組裝規劃問題”。

Artificial Immune Systems for Exploring Assembly Sequence Planning 5 Engineering Applications of Artificial Intelligence 22(8), 1218-1232 (SCI) (2009)

Motivation Memetic Algorithms(MAs) 的觀念將原有的演算法進一步提昇了求解品質，但是在一些測試的問題中，卻發現其求解時間會比 Guided-GAs 來得長。擬以 Artificial Immune System(AIS) 來求解組裝順序 , 因 AIS 模擬免疫反應中的抗體面對一個或多個未知的抗原來進行演算，並利用免疫系統中株落選擇 (Clonal selection) 的觀念，在每一代抗體的演化過程中，將較佳的抗體篩選出來，再無性 ( 繁殖 ) 複製選擇產生不同抗體以對抗外來入侵抗原的機制；這種方法將可改善 GAs 易收斂於局部解的缺點。

免疫 (Immunity) 系統所謂的免疫 (Immunity) 系統指的是當生物當受到外來微生物或病菌感染時免疫細胞受到激發以外部的侵入的過程，誘發免疫系統生產生反應的病菌或物質稱之為抗原 (Antigen, Ag) 免疫系統經由抗原刺激後，能與抗原結合的免疫細胞稱之為抗體 (Antibody, Ab) 。

B Cell and T cell B Cell 是 B 淋巴細胞 (Lymphocyte) ，是由骨髓 (Bone Marrow) 所產生的細胞，主要是受到抗體刺激後產生反應，並分泌抗體跟抗原結合。 T Cell 也就是 T 淋巴細胞，是在胸腺 (Thymus) 中成熟，主要功能辨識外部的侵入者並加以消滅；即 B 細胞要有效產生抗體對抗外來的抗原，必須依靠 T 細胞的幫助， B 細胞及 T 細胞表面會有許多受體 (Receptor) ，當抗原經由免疫階段後會產生不同的決定部位 (Epitope) ，當兩者接觸後會發生生物化學作用，其結合程度稱之為親和力 (Affinity) 。當 Receptor 跟 Epitope 結合越緊密，也就是表示親和度越高；這就是免疫系統中的專一性特點。

親和力成熟 (Affinity Maturation) 在免疫辨識之中可以得知， B 細胞經由跟抗原親和力判定，通過門檻值後就被刺激活化，這樣親和度選擇現象稱為親和力成熟 (Affinity Maturation) ，免疫系統會依此產生專一結合的細胞選殖 (Cloning) 若將抗原可定義為 Connector 為基的組裝規劃的目標式，抗體可定義為對應目標式所產生的答案，親和力是衡量 AIS 抗體間或是抗體跟抗原之間結合程度，而在 ASP 中是維持組裝順序的多樣性。

發展 ASP 專屬的 AIS 演算法的幾項觀念本研究應用 AIS 的專一性來產生初始解，而其初始解需要符合先行圖所描述的限制條件以產生可行解，再應用株落選擇中選殖 (cloning) 概念，將比較好的抗體選入記憶細胞區中，並分裂成符合題意記憶細胞區中所需個數。本研究應用 GAs 中的 crossover 及 mutation 產生多個可行解，以達到抗體多樣化的目的。在記憶性方面，每一次搜尋的可行皆予記錄，因應每次記憶好的抗體再跟抗原快速反應。最後最佳化的抗體再從記憶細胞區中輸出。

分支度 (Outdegree) 及內分支度 (Indegree) Outdegree: 以節點 Ci 為例 , Outdegree 就是接在 Ci 之後的節點數。如果先行順序中 Ci ? Cj ， Cj 為 Ci 的 Outdegree ，其 Outdegree 為 1 。 Indegree: 以節點 Ci 為例 , Indegree 就是接在 Ci 之前的節點數。如果先行順序中 Cj ? Ci ， Cj 為 Ci 的 Indegree ，其 Indegree 為 1 。

Stapler: connector-based precedence graph

為组装规划而设计类免疫演算法流程图

Stapler: 單點突變操作程序

最佳抗體次佳抗體 1 次佳抗體 2 相同個數 k = 6 66.7 % 相同個數 k = 5 55.6 % 100% 親和力挑選示意圖

Comparison between three algorithms for fan. 18.667 18.365 3.045 AIAs 18.333 18.285 3.951 Memetic Algorithms 16.667 16.133 2.808 Guided-GAs Max objective value Average objective value Average time Method

Convergence plot of electric fan

Comparison between three algorithms for laser printer 82.33 81.432 19.067 AIAs 80 79.096 25.965 Memetic Algorithms 76.67 75.595 18.543 Guided-GAs Max objective value Average objective value Average time Method

Conclusion 在 ASP 問題中，良好的初始解品質的效益將大於傳統的 immune algorithms 的做法；其次，本研究所 proposed 的 AIS 與傳統 GAs 的不同處在於應用人工免疫的多樣性特性，將可免於陷入 local optimal 的困境中。與過去代表性的範例來作比較，以電風扇為例，發現 AIS 在平均求解時間優於 Guided-GAs 約 20%, 最大目標值優於 Guided-GAs 約 12% ，比起 MAs 改善約 2% ，而以印表機為例，可得知 AIS 在平均求解時間優於 MAs 約 26.6 % 、最大目標值優於 Guided-GAs 約 7.4% 及 MAs 約 2.9% ，進而證明 AIS 可以有效針對限制式過多，易落入局部最佳解及求解時間過長問題做有效的解決。因此，綜觀而言， AIS 可以用來解決 Tseng (2006) 應用 Guided-GAs 求解組裝規畫問題易陷入局部最佳解的問題，而在 MAs 方面 (Tseng et al. ,2007) ，求解品值差異不大，但是在求解時間卻可以有效的縮短

绿色导向产物模组化之研究 Modular design to support green-life cycle engineering 7 Expert Systems with Application, 34, 2524-2537 (2008)

Green life-cycle engineering Fierce market competition is shortening the product life cycle. Passive resource recycling approach can no longer cope with the ever-increasing burden current products have on the environment. It is important to maximize the usage percentage of resources and minimize the damage to the environment in the early product design stage. Product life cycle refers to the total amount of time from material, manufacturing, assembly, consumer use, and final disposal or recycle of a product.

Motivation(Taking green life cycle into consideration) The author attempted to apply the green modular concept to product design. Advantages for this study: Reexamination of product functions ensures that the goal of environmental protection can be achieved. Products or product components can be recycled, reused and disposed of more easily. The life-cycle cost estimation enables designers to bring product cost into control.

Module definition Modules can be defined as the integral physical structures corresponding to specific product functions. (Otto and Woods, 2001) A proper modular design is able to cope the green objective and assemble components effectively into new products.

This study comprises three parts: Liaison graph is used to describe the product models, and liaison intensity of components is introduce. To assign the components whose liaison intensities are stronger in the same module, a clustering method is needed. The grouping genetic algorithm (GGA) is employed to solve the clustering problem. The evaluation of the clustering result: green pollution analysis and cost viewpoint are proposed in this study.

Liaison graph of a pen (a) (b) A higher LI indicates a more difficult type of combination and a smaller LI means a simpler type of combination. Liaison intensity(LI)

Estimate of liaison intensity among components A higher LI indicates a more difficult type of combination and a smaller LI means a simpler type of combination. In this study, a number from 0 to 100 is employed to describe the liaison intensity between components. The liaison intensity is decided by four engineering attributes of components such as the contact type, combination type, tool type, and accessed direction.

Table 1 Intensity of contact type Strong combination high Score Many faces will be contacted. 30 Multi-face contact Many points will be contacted. 24 Multi-point contact The contact part is a face. 18 Single face contact The contact part is a line . 12 Line contact The contact part is a point. 6 Point contact Description Liaison intensity Attribute Contact type

Computing intensity LIi = CTi + CBi + TLi + ADi (1) where LIi represents the total liaison intensity of the ith component; CTi represents the contact type intensity of the ith component; CBi represents the combination type intensity of the ith component; TLi represents the tool type intensity of the ith component; ADi represents the accessed direction intensity of the ith component.

Encoding for grouping genetic algorithms (GGA). Each gene stands for a module. For a chromosome composed of five modules “ABCDE”, the number of modules can be expressed as A={1}, B={3, 6}, C={4}, D={2}, E={5}.

Fitness Design A stronger Li intra indicates that it is easy to assemble components in a module

Crossover for GGA Reinsert part 6

Green analysis Poll = Weight × Indicator Where Poll indicates the pollution value of a component; Weight denotes the weight of the component (Kg); and Indicator represents the unit pollution index of a component. The pollution value offered by Eco-indicator99 ( http: // www.pre.nl / ).

Cost analysis Total Cost = material cost + process cost +assembly cost Material cost = unit cost of material (NT$/Kg) × material weight (Kg) Process cost = unit cost of process (NT$/sec) × time for process (sec) Assembly cost = the unit assembly cost (NT$/sec) × assembly time (sec).

Case study- table lamp. 22 components and 22 liaisons

Table 5 Estimate liaison intensity for table lamp Create the Liaison Intensity for every components. 40 1 Angle Hand Turn on PC 13-14 40 1 Angle Hand Turn on PC 12-14 60 1 Angle Small tool type Put on PC 11-14 36 1 Angle Hand Insert PC 10-14 45 4 Angles Hand Insert MPC 9-10 30 5 Angles Hand Insert LC 8-10 26 5 Angles Hand Put on LC 7-10 54 1 Angle Small tool type Turn on PC 6-20 54 1 Angle Small tool type Turn on PC 6-19 54 1 Angle Small tool type Turn on PC 5-18 54 1 Angle Small tool type Turn on PC 5-17 54 1 Angle Small tool type Turn on PC 5-16 54 1 Angle Small tool type Turn on PC 5-15 32 5 Angles Hand Put on SFC 5-10 60 1 Angle Hand Insert MFC 3-6 54 1 Angle Small tool type Turn on PC 2-22 54 1 Angle Small tool type Turn on PC 2-21 30 5 Angles Hand Insert LC 2-8 26 5 Angles Hand Put on LC 2-7 32 5 Angles Hand Put on SFC 1-6 48 1 Angle Hand Insert SFC 1-4 32 5 Angles Hand Put on SFC 1-2 Liaison intensity Accessed direction Tool type Combination type Contact type Liaison

Interface for liaison intensity estimation. Boland C++6.0

The results obtained from the GGA. Five modules can be get.

Eco-indicator99 Situation 1 Component 8 Situation 2 Whole module 3,6,19,20 0.16 0.3 240 Cast iron 0.00125 Screw8 22 0.16 0.3 240 Cast iron 0.00125 Screw7 21 0.16 0.3 240 Cast iron 0.00125 Screw6 20 0.16 0.3 240 Cast iron 0.00125 Screw5 19 0.16 0.3 240 Cast iron 0.00125 Screw4 18 0.16 0.3 240 Cast iron 0.00125 Screw3 17 0.16 0.3 240 Cast iron 0.00125 Screw2 16 0.16 0.3 240 Cast iron 0.00125 Screw1 15 9 16.5 330 Plastic 0.05 A_plug 14 1.8 3.3 330 Plastic 0.01 Fuse2 13 1.8 3.3 330 Plastic 0.01 Fuse1 12 14.07 25.8 86 Steel 0.30 Transformer 11 7.2 13.2 330 Plastic 0.04 Base 10 1.8 3.3 330 Plastic 0.01 Power 9 *26.17 48 240 Cast iron 0.20 Soft_pipe 8 1.8 3.3 330 Plastic 0.01 Plastic 7 9 16.5 330 Plastic 0.05 Contact 6 4.69 8.6 86 Steel 0.1 Steel2 5 0.47 0.86 86 Steel 0.01 Steel1 4 1.11 2.04 51 Glass 0.04 Bulb 3 5.4 9.9 330 Plastic 0.03 Cover2 2 14.39 26.4 330 Plastic 0.08 Cover1 1 % Poll Indicator Material Weight Name Component

Design modification and the modular component analysis Situation 1: When the bearable green polluted value is not accepted by the designer. Designers choose new materials or designs of lower pollution values. Component 8’s polluted value is the highest (Table 6). Obviously, Component 8 (Soft_pipe) should be improved. Situation 2: With the result of clustering, designer can replace the whole module according to the bearable green polluted value. Major components for the light bulb module are Component 3 and Component 6.

Table 7 Material cost and process cost change of Component 8. Change the material to reduce the green polluted value. Choose the alternative material whose pollution and cost are lower. The material and process costs will be changed when the material is changed. 5.1 1.0 5.1 4.76 1.0 4.76 C pc T pcu C pcu C pc T pcu C pcu Cost Weight Unit Cost Weight Unit Process cost 0.6 0.2 3.0 0.56 0.2 2.8 C m W m C mu C m W m C mu Cost Weight Unit Cost Weight Unit Material cost After modification Before modification

Fig. 7. (a) Illustration for light bulb module, (b) a revised modular graph for the table lamp. (a) (b) Situation 2 A new design replace the original component 3, 6 ,19 and 20.

Conclusion Result a score system using the liaison graph was adopted to evaluate the liaison intensity between components. a GGA was adopted for the clustering of modules. The crossover methodology proposed by Falkenauer was adjusted for the constraints in modular classification problem. Green pollution and cost analysis was conducted to evaluate the clustering result.

Future work The green polluted standard should be established as references for designers. Proper decision-making strategies can be added to help evaluate the liaison intensity between components, making the algorithm more objective and flexible.

应用多目标混合基因演算法整合組裝規劃與線平衡之研究 8 International Journal of Production Research, 21(1), 5951-5977 (2008)

研究動機與背景 (1/6) 組裝規劃 ( ASP ) 規劃者依據產品設計的描述，以個人特定的組裝經驗法則為基礎，規劃出完整的組裝順序。有效的串聯設計與生產間資訊減少實際組裝時的時間降低整體的製造成本組裝線平衡 ( ALB ) 指派製程與裝配作業給各工作站最大化製造的產出與需求成本間的比例提高製造生產效率

研究動機與背景 (2/6) ASP ALB ASP ALB 顧客導向 CE Consider Simultaneously Local optimal

研究動機與背景 (3/6) ASP 規劃 ALB 規劃組裝在先關係圖彈性組裝系統 WS01 WS02 WS03 WS04 A B C D Flow 1 2 3 4 5 7 6 8 3 5 6 3 5 6

研究動機與背景 (4/6) 總生產成本組裝成本 10%~30% ASP & ALB 相關文獻 Schmidt et al. (1995) Hong et al. (1997) Lee et al. (2001) Chen et al. (2002) 生產效率產品成本產品品質

研究動機與背景 (5/6) 多目標混合基因演算法 (Multi-objective hybrid genetic algorithms, MOHGA) 進化式多目標最佳化 ( Evolutionary multi-objective optimization, EMO ) 基因多目標規劃 Efficiency Performance 彈性組裝系統集群基因演算法 (Grouping genetic algorithms, GGA) 序列式基因演算法 ( G enetic algorithms, GAs) 多目標規劃

研究目的降低規劃的錯誤率及日後的生產成本整合的系統將有助於設計者的思維進行上下游資訊的串聯快速回應顧客多樣少量的需求變異

研究方法關聯圖為基的產品模型 ASP 與 ALB 規劃分析 MOHGA 架構決策分析兼顧 ASP 與 ALB 的組裝線設計

ASP 規劃分析 Liaison graph Assembly precedence graph EX:1 -> 2 -> 4 -> 3 -> 6 -> 5 -> 7 -> 8 1 2 3 4 5 7 6 8 p1 p2 p3 p4 p5 p6

ALB 規劃分析 EPALB 模式導入各工作站的流程時間盡可能的均等 SALBP SPALB-1 SPALB-2 1 2 3 4 5 7 6 8 Cycle time 1 2 3 4 5 6 7 8

ASP 與 ALB 小結 {{1, 2}, {3, 4, 5, 6},{7, 8}} 方向性 : ± X 、 ± Y 、 ± Z 工具種類 : T 1 、 T 2 、 T 3 、 T 4 1 2 3 4 5 7 6 8 Liaison 編號組裝時間組裝工具組裝方向 1 11 T 1 -y 2 17 T 1 x 3 9 T 3 x 4 5 T 1 -x 5 8 T 3 -y 6 12 T 3 z 7 10 T 2 z 8 3 T 4 x 4 -> 3 -> 6 -> 5 3 -> 4 -> 6 -> 5 3 -> 5 -> 4 -> 6 4 -> 3 -> 5 -> 6 3 -> 4 -> 5 -> 6 Liaisons 組裝順序

目标函数的设定組裝線的不均衡狀態 (Imbalance) 組裝方向變換耗時函數值 (Direction change) 組裝工具變換耗時函數值 (Tooling change) DC n 值 ={0, 1, 2} TC n 值 ={0, 1}

多目標最佳化目標間相互有所衝突目標之間單位的差異幾乎沒有一個解可以同時滿足所有的目標多目標整體目標函數衡量固定權重加總法主觀的權重決定柏拉圖最佳解法隨機的方式產生權重

柏拉圖最佳解 (Pareto optimal solutions) 不可凌越解 (Non-dominated solutions) 非劣解 (Non-inferior solutions) x : 可行解 y : 柏拉圖解

變動權重法 (1/2) 假設考慮下列具有 n 個目標的多目標最小化問題：染色體 x 的目標函數可以定義為 n 個目標之權重和，如所示：其中， w 1 , w 2 ,…, w n 為 n 個目標之非負權重且滿足下列的關係，如所示：

變動權重法 (2/2) 權重值 w i 的決定方式如所示： r 1 , r 2 ,…, r n 為非負的隨機實數或非負的隨機整數權重值的變化可以改變搜尋的方向以找到不同的柏拉圖最佳解

多目標混合基因演算法編碼產生初始解局部搜尋計算目標函數選擇交配突變局部搜尋精华保留策略更新柏拉圖最佳解是否終止結束開始

決策分析本研究提出下列步驟來輔助決策者挑選步驟 1 : 計算各目標的最大值與最小值步驟 2 : 計算估算值步驟 3 : 以各目標的估算值作為參考點，計算柏拉圖最佳解到參考點的相對距離步驟 4 : 挑選相對距離最小的柏拉圖最佳解

范例测试與分析測試問題 Name ：測試問題名稱 n ：作業數目，即本研究的 liaison 數目 m ：工作站數目 t min ：作業的最小組裝時間 t max ：作業的最大組裝時間 t sum ：作業的總組裝時間 OS ：即 Order Strength TV ：組裝時間變化性比例

柏拉图最佳解绩效衡量本研究利用 Kaige et al. ( 2003 ) 使用的柏拉圖最佳解多樣性評估方式擴張 ( Spread ) 程度 : D 間隔 ( Spacing ) 程度 : S

測試結果 (1/4) 柏拉圖最佳解集合 ( Kilbridge )

測試結果 (2/4) 各工作站流程時間 ( Kilbridge )

測試結果 (3/4) 各工作站工具變換函數值 ( Kilbridge )

測試結果 (4/4) 各工作站方向變換函數值 ( Kilbridge )

结果分析 (1/4) 柏拉圖最佳解散佈圖 ( Kilbridge ) 柏拉圖最佳解超平面 ( Kilbridge ) 柏拉圖最佳解超平面 ( Warnecke ) 柏拉圖最佳解超平面 ( Wee-Mag )

结果分析 (2/4) 不均衡狀態函數值收斂圖 ( Kilbridge ) 工具變換耗時函數值收斂圖 ( Kilbridge ) 方向變換耗時函數值收斂圖 ( Kilbridge ) 柏拉圖最佳解個數趨勢圖 ( Kilbridge )

结果分析 (3/4) 目標一與目標二的散佈圖 ( Kilbridge ) 目標一與目標三的散佈圖 ( Kilbridge ) 目標二與目標三的散佈圖 ( Kilbridge ) 正規化公式

结果分析 (4/4) 目標函數之盒型圖 ( Kilbridge )

柏拉圖最佳解決策分析 (1/2)

柏拉圖最佳解決策分析 (2/2) 設計變更找出差異性較大的工作站局部零件的組裝分析

MOHGA 績效驗證與 Rekiek 進行比較 Min1 為 Rekiek 最小工作量的平均值； Max1 為 Rekiek 最大工作量的平均值； Min 2 為本研究最小工作量的平均值； Max2 為本研究最大工作量的平均值；

结论本研究提出一個新的方式求解組裝順序與組裝線平衡同時考量的彈性組裝系統目的是降低產品設計的前置時間以及改善製造的品質與成本藉由測試範例的結果證實 MOHGA 可以有效找到柏拉圖最佳解集合的區域且可以達到組裝線平衡的績效提供決策者一個選擇柏拉圖最佳解的方式提供設計變更的資訊

編碼表示法序列式染色體群組導向染色體

解碼程序 Back 1 2 3 4 5 7 6 8

初始族群的產生 (1/2) 步驟 1: 紀錄每一 Liaisons label 值步驟 2: 選擇邊界石 EX:1 -> 2 -> 4 -> 3 -> 6 -> 5 -> 7 -> 8 EX: L = 8 / 3 = 2.67 邊界石 = {1 3.67 6.34 9.01} Seed = {1 4 7 10} 1 2 3 4 5 7 6 8 8 8 3 4 7 7 4 3 5 6 2 2 6 5 1 1 label Liaison label Liaison

初始族群的產生 (2/2) 步驟 3: Liaisons 分群步驟 4 與步驟 5: 配置 Liaisons 分群結果 : {1, 2, 4}, {3, 6, 5}, {7, 8} 配置結果 : {1 -> 2}, {4 -> 3 ->6 }, {5 -> 7 ->8 } Back WS1 WS2 WS3 1 2 3 4 5 6 7 8

選擇運算子應用輪盤法 (Roulettle wheel) 步驟 1: 隨機指定權重步驟 2: 選取成對父代染色體步驟 3: 重複步驟 1 與步驟 2 ，直到滿足族群大小 Back

交配運算子設計 (1/3) 上半部基因的交配方式 ( PMX )

交配運算子設計 (2/3) 下半部基因的交配方式 ( Falkenauer 提出 )

交配運算子設計 (3/3) 修正之步驟步驟 4-1: 調整各基因內的 Liaisons 順序依據上半部基因的交配結果步驟 4-2: 調整基因間的順序無法調整之基因則進行刪除基因作業步驟 4-3: 基因數目的檢核當不滿足硬限制，執行新增或刪除基因作業步驟 4-4: 遺失的物件配置依據對整體目標值所產生的影響力，進行機率性方式指派基因內的狀態變動，需再度調整 Liaisons 順序 Back

突變運算子設計本研究對每一基因均給予突變機率來決定是否需要進行突變上半部基因以隨機互換的方式產生子代下半部基因以機率性方式重新配置 Back

精华保留策略保留各單一目標評估值最佳的個體第二母體中隨機挑選一定數量的個體 Back

基因局部搜尋演算法 (1/2) 本文應用 Ishibuchi et al. (2003) 所提出的多目標基因局部搜尋演算法 (MOGLS) 進行局部搜尋改善演化機制後解的品質改善收斂到柏拉圖最佳解的運算效率只選取優良的個體與適當的權重方向進行改善

基因局部搜尋演算法 (2/2) MOGLS 流程步驟 1 ：隨機產生新的權重組合步驟 2 ：使用競爭式法則挑選染色體步驟 3 ：進行局部搜尋步驟 3-1 ：利用局部搜尋機率 P LS 決定是否執行以下步驟步驟 3-2 ：利用鄰近解搜尋，產生相對於現在染色體解 x 的新解 y 。步驟 3-3 ：計算 x 與 y 的適應性函數，如果 y 優於 x ，則 y 取代 x 步驟 3-4 ：重複步驟 3-2 與步驟 3-3 ，如果已經進行 k 次鄰近搜尋，則結束局部搜尋的步驟。 Back

Mass customization 9 Expert Systems with Applications 29, 913-925 (2005)

摘要產品變異和客製化是目前以市場為導向的製造環境下的趨勢。怎樣產生一張精確的 BOM 以符合顧客的需要並且適合生產，在競爭市場中是相當重要的。本研究的目的是在假設生產一種準確的新產品的情況下，有效地降低設計的時間和成本。研究利用 CBR 演算法來建構新的 BOM 。與目前問題類似的案例可以在計算過程中節省許多時間，並且為設計者提供正確的方向。當解決一個新的問題， CBR 技術能迅速幫助產生適合目前狀況的 BOM 。

介紹 (1/2) Fohn et al. (1995) 曾經使用電腦作為案例，研究中證明大約 30-85% 的產品資訊是錯誤的，這種錯誤將造成企業在工程設計上的負擔。因此，怎樣對產品結構的複雜性和準確度進行控制已經變成企業現今企業必須面對的重要挑戰之一。在處理產品結構上，如果企業完全依頼專業人員的知識或經驗，那麼會因為不完全的溝通或者認知上的衝突，容易失去對產品結構的控制。這將增加設計交替的困難和成本的壓力。

介紹 (2/2) CBR( 案例式推理 ) 能透過以前相似的案例來解決問題 (Kolodner ， 1993) 。其產品結構具有以下優勢：過去成功的案例可以再使用以解決一個新的問題。經由過去成功的案例，相同的錯誤可以被避免，以及改進解決問題的品質。容易收集過去失敗或成功的案例，降低獲取知識的瓶頸。當有經驗的技術人員離開公司時， CBR 能預防企業 know how 的損失。

CBR 概論 (1/2) CBR (case-based reasoning ) 主要是以累積運用先前的案例，作為解決日後問題的參考。方法為先收集與問題有關的案例，並集合成一案例庫，爾後欲解決特定問題時，從案例庫中挑選與問題類似的案例做為參考，並經過適當的修正後，成為目前問題的解決方案。簡單地說， CBR 就是：人類推理的過程推理過程的表達在應用程式發展上，解決問題的一種方法論

CBR 概論 (2/2) 有學者提出 CBR 是由四個 RE 組成 Retrieve( 取得問題的類似案例 ) Reuse( 使用案例的解決方法來嘗試解決問題 ) Revise( 對系統建議方式進行驗證 ) Retain( 將獲得驗證之案例與解決方法保留以做為日後的參考 )

CBR 應用領域過去， CBR 已經被成功地解決很多問題。管理方面：規劃和流程設計、顧客關係管理、缺點分析、知識管理的設計和執行。商業方面：財務 ( 預測利率、公司債券率 ) 、電信 ( 通話記錄分類 ) 、行銷 ( 線上銷售支援 ) 、策略規劃與設計。 CBR 適用於處理雜訊資料、不完整資料，可處理大量資料及不同類型資料，預測正確性高，解釋能力很好及易於整合與操作等優點。 (Bose et al. , 2001)

特徵樹規則為了確保特徵樹的合理性，應該服從下列的規則：規則 1 ︰相連接的節點不能構成迴路。規則 2 ︰特徵應該用來描述父層節點。規則 3 ︰當節點代表零件，子層表示子零件或者父層節點的特徵。規則 4 ︰當節點代表特徵，即表示在子層沒有節點；為描述父層節點的特性。規則 5 ︰產品結構的標準應該由負責產品結構計畫的人員所建立，。

範例 (1/3) PILOT pen 特徵樹

Blue pen vs. green pen BOM Blue Green

相似度的計算 (1/2) Step.1 檢查 case 中的每個屬性是否相等。代表輸入 Case ( I ) 的第 j 屬性的值表示資料庫 (R) 裡第 i 個 case 中第 j 個屬性的值假設 1 ： 0 ： Step.2 計算每個節點的相似度。

相似度的計算 (2/2) Step.3 計算所有節點的相似度。給予一個權重，所有節點相似度加總後即成總相似度。

範例 (2/3) ： j={1, 2, …, 14}={pen, PILOT, body, ink cartridge, 0.3 , green , tail, green , tip, silver, cap, green , 0.3 , sharp tip } ： j={1, 2, …, 14}={pen, PILOT, body, ink cartridge, 0.4 , blue , tail, blue , tip, silver, cap, blue , 0.4 , rounded tip } 權重

範例 (3/3) :j={1, 2, …, 14}={1, 1, 1, 1/3, 0, 0, 1/2, 0, 1, 1, 1/4, 0, 0, 0} 相似度計算如下：

產品結構之 CBR 演算法流程

個案探討個案為台中的 CNC 機械製造廠。公司為了便於產品規格管理，打算建置產品結構系統。專案涵括負責訂單流程的業務部門與負責設計的 R&D 部門。根據上圖的 CBR 演算法建置電腦系統。討論 CNC 車床的 37 項特徵，如下圖。業務人員轉換顧客需求成為新的工作單。訂單將被轉換成一棵產品特徵樹。

2 Enclosure guarding 2 Turret size 3 Eliminates truncating device 9 Turret type 1 Oil bump Turret 1 Cooling system 5 Main spindle horsepower 1 Lubrication pump 7 Main spindle thimble Standard accessories 10 Main spindle Rotational speed 4 Z-axis servo motor 10 Main spindle tip 3 Z-axis transmission type 10 Spindle bore 2 Z-axis feeding rate Headstock 6 Z-axis speedy feeding 15 Bed length 1 X-axis servo motor 1 Rail type 2 X-axis 3 Carriage width 1 X-axis feeding rate 4 CNC controller 2 X-axis speedy feeding 15 Center distance Feeding 2 Carriage width 1 Tailstock quill 2 Cross slide length 2 Tailstock quill movement 6 Center height 1 Tailstock body movement 6 Rail radius 1 Tailstock thimble 6 Bed radius 1 Tailstock quill diameter 9 Model two Tailstock 3 Model one Option Feature Option Feature

分析 & 評估產品特徵樹

個案成果 CBR 演算法可以在產品特徵樹已依據特定的規範建立的情況下應用。以前的經驗可以被完整地記錄並且傳送，使得處理產品規格過程中的錯誤率降低。研究結果證明新工作單和過去最相似的工作單之間存在著一些差別。因此，設計者可以聚焦在工作單中不同的部份，因此節省時間和精力。因設計變化來自於過去最相似的案例， CBR 系統能有效地降低設計變異的頻率。當設計上的某些變化是必要的，它能使設計變異的成本降低。

结论與建議本研究中，應用 CBR 技術於 BOM 的規劃。類似目前問題的過去案例被提取，根據目前的限制條件做調整。結果證明此法能降低產生 BOM 所需要的時間。使用本方法，設計者能彼此分享他們的知識和經驗。更重要的是，它能避免經驗的損失，和設計上相同的錯誤再發生。未來研究上，可強調資料庫中集群分析的應用以提升提取速度，且降低資料庫的負擔。在案例的比較上，模糊比較的觀點可以用來加強推論演算法。

總結要將一件事作得稍為像樣，一定要忍受一些孤獨、忍受一些冷漠、甚致一些嘲諷。實力是建立在一步一腳印努力之上，心性的陶養同等重要，必須建立對於作研究的興趣。研究工作就是冒險之旅，很難預期最後的結果是什麼，要經得起失敗，不要太計較得失。郭台銘名言：成功是最差的老師，它只會帶給你膽怯和懦弱。 Do not work hard, work smart. 對於研究的堅持與訓練會讓學生帶入工作職場，通常研究作得好的人工作表現也會理想。思考清楚兩年研究生涯的定位。

狠狠撸

長庚 0511.2011(曾懷恩教授演講)

Recommended

More Related Content

Similar to 長庚 0511.2011(曾懷恩教授演講) (20)

長庚 0511.2011(曾懷恩教授演講)