以兩階段基因免疫演算法改良生存策略求解流程型排程問題

Two-phase Genetic-Immune Algorithm with Improved Survival Strategy of Lifespan for Flow-shop Scheduling Problems

吳鈴淳(Ling-Chun Wu)

指導教授 ： 張百棧

元智大學/工程學院/工業工程與管理學系/碩士(2009年)

摘要

雖然基因演算法（Genetic Algorithm, GA）為一著名的求解組合性問題的工具，但面臨過早收斂而陷入了局部最佳化的缺點。類免疫演算法（Artificial Immune System, AIS）與基因演算法一樣具有多點同步搜尋的特性，不同於基因演算法的是，其使用了記憶訓練方式與不同抗體對抗入侵的抗原變化，除了針對抗體與抗原的匹配性，也考慮抗體與抗體之間的關係，能彌補過去基因演算法的系統機制只能針對染色體單純特徵組合求解的缺陷，有鑑於此，本研究混合基因加免疫的演算法(HGIA)，輔以共演化策略改善，並將生命力賦予染色體，作為生存策略，期望在搜尋空間尋找更多樣化的解，另外，為兼顧收斂速度與探索空間，本篇加入了株落選擇機制，以人造複製的T細胞及突變的B細胞共同演化出辨識率更高之抗體，透過此機制之優良探究與探索特性，可求得近似最佳解。本研究求解單目標流程型（Flowshop）排程問題，其績效準則為以總完工時間最小化為目標，因GA之快速收歛特性，故在第一階段以GA進行演化，並於第二階段以HGIA進一步搜尋更寬廣之解空間。研究顯示，本研究所提之TPGIA，在特定問題上可提升原有SGA之求解品質。

關鍵字

基因演算法 ； 類免疫演算法 ； 排程問題 ； 共演化策略 ； 生存策略

並列摘要

In this paper, a Hybrid Genetic-Immune algorithm (HGIA) is developed to solve the flow-shop scheduling problems. The regular genetic algorithm (GA) is applied in the first-stage to rapidly evolve and when the processes are converged up to a pre-defined iteration then the Artificial Immune System (AIS) is introduced to hybridize Genetic Algorithm in the second stage is named HGIA. In the process of co-evolution, GA and AIS cooperates with each other to search optimal solution by searching different objective functions. One is named fitness in GA section and another one is antigen which will evoke the withstanding of antibodies. In the process of fighting, the antibodies evolve till they can resist the antigen. Moreover, an survival strategy is proposed to extend the lifespan of the antibodies to stay in system longer. Finally, Clonal selection is adopted into the infrastructure of AIS which contains certain types of B and T lymphocytes are selected for destruction of specific antigens invading the body. Due to the hybrid of GA and AIS contains two objectives, larger searching space and escaping from local optimal solution will be the superiority for hybridization. In the research, a set of flow-shop scheduling problems are applied for validating the efficiency. The intensive experimental results show the effectiveness of the proposed approach for Flow-shop problems in Production Scheduling.

並列關鍵字

Genetic Algorithm ； Artificial Immune System ； Scheduling Problems ； Co-evolutional process ； Survival Strategy

參考文獻

59. 柯瓊惠，「基因演算法結合人造解在生產排程之應用」，碩士論文，元智大學，2007。

60. 陳啟嘉，「基因結構探勘於承接式子群體基因演算法求解多目標組合性問題」，碩士論文，元智大學，2006。

62. 湯璟聖，「動態彈性平行機群排程的探討」，碩士論文，中原大學， 2003。

1. Aldowaisan, T. and Allahvedi, A. “New heuristics for no-wait flowshops to minimize makespan,” Computers & Operations Research, 30, pp.1219-1231, 2003.

2. Alisantoso, D., Khoo, L.P., Jiang, P.Y., “An immune algorithm approach to the scheduling of a flexible PCB flow shop,” International Journal of Advanced Manufacturing Technology, 22 (11-12), pp. 819-827, 2003.