解答多目標規劃的新方法-免疫系統法

A Novel Approach for Resolving Multi-Objective Optimization Problems- Immune Algorithms

馬誠韋(Cheng-Wei Ma)

指導教授 ： 鍾雲恭

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

摘要

目前有許多以生物群體行為所形成的最佳化技術，例如：螞蟻演算、基因演算、神經網路以及細胞，這類的最佳化技術越來越普遍，其解答過程藉由自然合作的行為機制。這表示可將多目標最佳化問題可以分解成數個子問題，藉由相互合作的方式來解答問題，在本文所提出的免疫人工系統是一種生物計算系統，它是一種解答多目標最佳化問題的新方法，其多目標最佳化的架構非常接近生物合作機制，它是藉由兩個搜尋過程的合作來完成多目標最佳化：第一階段區域的人工免疫搜尋機制，是要找出滿足限制條件下個別目標的最佳解；第二階段全域的人工免疫搜尋機制則是以合作的方式最小化所有目標間的衝突。在本文中，要強調的是所提出的合作型態人工免疫系統並不同於原始的免疫系統，並將提出的人工免疫演算法與文獻中的傳統的多目標最佳化技術比較其最佳化的能力。比較的結果顯示，這個提出的免疫人工系統演算法能夠明顯的減少收斂時間並增加解答的精確性。

關鍵字

生物群體行為 ； 最佳化技術 ； 免疫人工系統 ； 合作型態

並列摘要

It is well known that an optimal technique in the form of biological swarm behavior, e.g., ants, genes, neurons and cells, is an universal method in which the solution procedure is achieved by the nature cooperative behavior. This is the metaphor that an optimization problem should be suitably decomposed into several constituent sub-problems that can be solved in the way of the cooperation one another. In this thesis, an artificial immune system (AIS), one of the bio-computation methods, is presented to be a novel approach for resolving multi-objective optimization problems. The structure of a multi-objective optimization is very suitable for the biological cooperation’s nature. Two search procedures are used to cooperatively perform the multi-objective optimization. The local AIS search is to find the optimal solution of an individual (or decomposed) objective with all of constraints; the global one is to cooperatively minimize the conflict among the all objectives. Emphatically, the cooperative behavior of the proposed AIS distinguishes from that of the original one. Also, the optimizing ability of the proposed AIS algorithm is identified by comparing it with that of the classical multi-objective optimization techniques appeared in the published articles. The compared results show that the proposed AIS algorithm can significantly reduce the convergence time and potentially increase the solution accuracy.

並列關鍵字

optimal technique ； biological swarm behavior ； artificial immune system ； nature cooperative behavior

參考文獻

Bessaou, M., and P. Siarry,（2002） “A Genetic Algorithm with Real-Value Coding to Optimize multimodal Continuous Functions,” Structural and Multidisciplinary Optimization, Vol. 23, pp. 63-74.

Dasgupta, D. and N. Attoh-Okine, (1997) “Immunity-Based Systems： A Survey,” Proceeding of the IEEE Transactions on Systems, Man and Cybernetics, Vol. 1, pp. 369 -374.

Deb, K., (1999) “Solving Goal Programming Using Multi-Objective Genetic Algorithms,” Proceeding of the IEEE Transactions on Evolutionary Computation, Vol. 1, pp. 78 -84.

Dote, Y., (1998) “Soft Computing (Immune Networks) in Artificial Intelligence,” Proceeding of the IEEE Transactions on Systems, Man and Cybernetics, Vol. 2, pp.1382 -1387.

Gaspar, A. and P. Collard, （1999） “From GAs to Artificial Immune Systems: Improving Adaptation in Time Dependent Optimization,” Proceedings of the Congress on Evolutionary Computation, Vol.3 pp.1859-1866.