一般性多項式規劃問題的免疫解法

Immune Algorithm for Solving Generalized Polynomial Programming Problems

吳瑞煜(Jui-Yu Wu)

指導教授 ： 鍾雲恭

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

摘要

在科學與工程的領域中，許多問題可以被表述成一個目標函數與限制式受限於不等式(inequality)與等式(equality)限制式之受限的全域最佳化(constrained global optimization, CGO)問題。一般性多項式規劃(generalized polynomial programming, GPP)問題即是一種CGO問題。不幸地，GPP問題的目標函數與限制式皆為非凸函數(nonconvex function)。因此，許多局部最佳解可能存在於GPP問題之受限制的解空間中。傳統的非線性規劃(nonlinear programming)技術對於求解GPP問題是有困難的，因為它們使用局部最佳化。許多確定性全域最佳化(deterministic global optimization)方法已經被發展出來以克服這一個缺點。儘管，這些方法可以獲得GPP問題的全域最佳解，它們在數學上是冗長的。因此，本文提出三個有效的隨機全域最佳化(stochastic global optimization)方法：人工免疫系統(artificial immune system, AIS)、實數編碼基因演算法(real-coded genetic algorithm, RGA)與一個簡化的非常快速模擬再退火(very fast simulated reannealing, VFSR)算法。這三個技術被應用於一系列的GPP問題，並與已知的全域GPP解比較。數值計算結果指出本文所提出的AIS方法與RGA對於所有的測試問題可以收斂至全域最佳解，而且AIS方法優於RGA與VFSR算法。

關鍵字

一般性多項式規劃, 非線性規劃, 人工免疫系統, 實數編碼基因演算法, 非常快速模擬再退火

並列摘要

In science and engineering, many problems can be formulated as constrained global optimization (CGO) problems where an objective function is subject to inequality and equality constraints. The generalized polynomial programming (GPP) problem is one such CGO problem. Unfortunately, the objective function and constraints of a GPP problem are nonconvex functions. Therefore, numerous local optima may exist in the constrained solution space of a GPP problem. Traditional nonlinear programming (NLP) techniques have difficulty in solving GPP problems, since they use local optimization. Many deterministic global optimization methods have been developed to overcome this disadvantage. Although capable of obtaining global solutions to GPP problems, such approaches can be mathematically tedious. Therefore, this thesis presents three efficient stochastic global optimization techniques: artificial immune system (AIS), real-coded genetic algorithm (RGA) and a simplified very fast simulated reannealing (VFSR) algorithm. These approaches were applied to a set of GPP problems, and their best solutions were compared with the known global GPP solution to each testing GPP problem. Numerical results show that the proposed AIS approach and RGA converged to a global solution to each tested GPP problem, and that the AIS approach outperformed the RGA and VFSR algorithm.

並列關鍵字

generalized polynomial programming, nonlinear programming, artificial immune system, real-coded genetic algorithm, very fast simulated reannealing

參考文獻

Abuo-El-Ata, M.O., H. A. Fergany, and M. F. El-Wakeel, (2003) “Probabilistic multi-item inventory model with varying order cost under two restrictions: A geometric programming approach,” International Journal of Production Economics, Vol. 83, No. 3, 223-231.

Beightler, C. S., and D. T. Phillips, Applied Geometric Programming, New York: Wiley, 1976.

Coello Coello, C. A., and N. Cruz Cortes, (2002a) “A parallel implementation of an artificial immune system to handle constraints in genetic algorithms: preliminary results,” in Proceedings of the congress on Evolutionary computation, Honolulu, HI USA, 819-824.

Coello Coello, C. A., (2002b) “Theoretical and numerical constraint-handling techniques used with evolutionary algorithms: a survey of the state of the art,” Computer Methods in Applied Mechanics and Engineering, Vol. 191, No.11-12, 1245-1287.

de Castro, L., (2002a) “Immune, swarm, and evolutionary algorithms: part I: basic models,” in Proceedings of the Ninth International Conference on Neural Information Processing, Singapore, Vol. 3, 1464-1468.