【摘要】运输问题可引申为多种组合优化问题，这类问题属于NP-hard问题。针对fuzzy-GA算法求解多目标运输问题存在的早熟问题及解的分布性问题，本文在标准遗传算法的基础上加入免疫算法里的浓度抑制思想，实验证明，通过利用一系列的遗传操作和抗体亲和度计算、基于浓度群体更新策略生成下一代抗体群，确保了个体的多样性，加强了解群的散布性。

　　论文关键词：多目标优化，模糊规则，免疫，浓度控制

　　
　　在求解多目标优化问题时，由于目标意义不同，存在目标之间的无法比较和冲突现象，不一定在所有目标上都是最优的解。为了达到总目标的最优化，必须折中获取目标值。在多目标空间中，空间的代数结构仅满足偏序性（partial order），不再具备单目标优化的全序优良性质，从而导致求解的困难性。

　　
　　Gen，Li和Cheng讨论了用生成树表示求解运输问题的遗传算法，使用树性编码的Pruefer数，作为设计染色体的可行标准。基于Pruefer数的GA在求解多目标运输问题时，由于节省了存储单元，求解时也就节省了计算时间。

　　
　　Zou Shurong和Zhang Hongwei提出了基于Fuzzy规则的Fuzzy-GA算法，针对st-GA算法在分配运输量的过程上采用的是贪婪法，而贪婪法对优化问题较难得到满意解的问题， Fuzzy-GA算法在st-GA算法的基础上引入了表达显性知识的Fuzzy规则进行运输量的分配。从实验数据可以看出，Fuzzy-GA算法与st-GA算法相比特别是对大规模的运输优化问题有明显的优势，Fuzzy-GA算法不仅得到了更好的Pareto前沿面，而且得出了更优的Pareto解。

　　
　　免疫算法所使用的遗传结构和遗传算法类似，采用重组、变异等算子操作解决抗体优化的问题，可以看作是对遗传算法的补充。它把遗传算法中的染色体看作抗体。

　　
　　本文在Fuzzy-GA算法的基础上，首先抗体群的初始化采用新的判定规则直接生成可行的初始抗体群，加快了抗体群的迭代速度。其次在分配运输量采用模糊规则来指导运输量的分配的情况下，在保证供需平衡的基础上，进一步对运输量的分配进行局部的变异。这样使得运输量分配更趋于合理，加强了解的局部搜索能力，提高了智能进化过程的精度。以抗体的浓度作为参数来调节抗体的促进和抑制，维持抗体的多样性，使解的分布性更加均匀，从而得到更优Pareto解和更好的Pareto前沿面。

　　
　　成都信息工程学院资助项目，基金号：KYTZ200901。

　　
　　2 问题描述与符号约定

　　
　　多目标优化问题可有如下数学表述：

　　
　　模糊规则 （1）

　　
　　免疫 （2）

　　
　　基于免疫思想GA的多目标运输问题研究 （3）

　　
　　在上边式子中，x、y分别表示决策向量和目标向量。gj（x）为第j个约束条件，S为决策变量的可行解域。

　　
　　在具有m个工厂，n个仓库，q个目标函数的多目标运输问题中，m个工厂的总生产量应等于n个仓库的总需求量。用r（i,j）表示第i个工厂到第j个仓库的运输关系，任一运输关系r（i,j）上的运输量应不大于工厂i的产量，且同时不大于仓库j的需求量。具体可用下列式子描述为[2]：

　　
　　模糊规则 （4）

　　
　　模糊规则 （5）

　　
　　模糊规则 （6）

　　
　　多目标优化 （7）

　　
　　3 基于免疫思想的遗传算法

　　
　　3.1 Fuzzy-GA算法的介绍

　　
　　Fuzzy-GA是基于Pruefer编码、解码和基于模糊规则的遗传算法。Pruefer数作为一种树的节点编码方法，可用于编码运输树。运输树是一种特殊类型的树，所以Pruefer数可能对应不可行的解。Gen和Li设计了检验可行性的准则，但是此算法的效率不是很高。文中Fuzzy-GA使用易于表达显性知识的Fuzzy规则理论，但解的收敛速度不是太快，而且解的质量还可以进一步优化。

　　
　　Fuzzy规则：IF  is  and  is  THEN 浓度控制，这里是模糊集，隶属函数为三角函数，表示（1）中效用因子的高、中、低等意义。

　　
　　免疫

　　
　　多目标优化

　　
　　多目标优化

　　
　　3.2基于Lamarckian进化运输量变异过程

　　
　　运输量变异是在根据Fuzzy规则对Puefer树中运输量的的分配后对已生成的运输量矩阵按一定的方法做局部的变异，但应保证供应和需求的平衡。具体算法如下：

　　
　　输入为m行n列的运输矩阵

　　
　　第1步：

　　
　　for j=1:n列

　　
　　如果第j列不等于0的元素个数为1，则运输量变异不考虑此列元素；

　　
　　第2步：

　　
　　for i=1:m 行

　　
　　如果第i行不等于0的元素个数为1，则运输量变异不考虑此行元素；

　　
　　第3步：

　　
　　反复执行第1、2步，除去变异不考虑的行和列（即某行某列不等于0的元素的个数等于1）；一般执行m次即可完成

　　
　　第4步：

　　
　　统计运输矩阵不等于0的元素个数，如果统计后元素为0，则退出，返回原运输矩阵；

　　
　　第5步：

　　
　　for i=1:m 行

　　
　　{

　　
　　① 统计i行中不为0的个数，记为count；

　　
　　② 如果count为偶数，i行中不为0的元素进行随机加（减）微量运输量；

　　
　　③ 如果count为奇数，i行中不为0的元素进行随机加（减）微量运输量或不

　　
　　变异；

　　
　　}

　　
　　第6步：

　　
　　for i=1:m 行

　　
　　统计变异后i行运输量的行量总和，如果不等于相应的行供应量，则退出，返回原运输量分配矩阵；

　　
　　第7步：

　　
　　for j=1：n列

　　
　　统计变异后j列运输量的列量总和，如果不等于相应的列需求量，则退出，返回原运输量分配矩阵

　　
　　第8步：

　　
　　返回变异后运输分配矩阵；

　　
　　3.3浓度控制原理

　　
　　若规定抗体在集合上的距离为：

　　
　　免疫

　　
　　则抗体浓度的公式可表示为

　　
　　Density（）==免疫由此可以推知，基于免疫思想GA的多目标运输问题研究多目标优化=模糊规则

　　
　　根据上式可知，集合中与抗体基因相似的抗体越多，抗体被选中的概率就越小；反之，与抗体相似的抗体越少，抗体被选中的概率就越大，这使得差异性大的抗体获得更好的进化机会，因此，基于抗体浓度的选择在理论上保持了抗体多样性，而从使得抗体在新一代解群中都应具有较好的散布性。

　　3.4本文算法整体流程

　　
　　本算法采用文中的擂台法（arena’s principle，AP）来作为选择评价算子，对于交叉算子和变异算子都采用文献中所定义的方法。算法采用擂台法来得到Pareto解，该算法也是构造Pareto解或非支配解的快速算法，也是遗传算法的适应度评价方法。本算法也采用新的效率很高的检验Pruefer数的可行性准则，对于m个工厂n个仓库的运输问题，只要满足下列条件之一则该Prüfer数就是可行的：

　　
　　（1） Pruefer数（P）中出现的工厂节点的总个数等于n-1

　　
　　（2） Pruefer余数（CP）中出现的仓库节点总个数等于m-1

　　
　　令P（t）是当前t代时的抗体种群，C（t）是当前t代产生的抗体，PSet（t）是当前t代为止产生的Pareto解集。

　　
　　新算法流程如下：

　　
　　Begin

　　
　　;

　　
　　随机初始化可行的P（t）；

　　
　　根据构造生成树T算法、运输量的变异算法和AP算法从P（t）得PSet（t）；

　　
　　While 终止条件不满足 do

　　
　　Begin

　　
　　重组P（t）得C（t）；

　　
　　根据构造生成树T算法、运输量的变异算法和AP算法从P（t）和C（t）更新PSet（t）；

　　
　　基于浓度选择的群体更新，从P（t）和C（t）中选择出P（t+1）；

　　
　　免疫；

　　
　　end

　　
　　end

　　
　　最终得到的PSet（t）便是Pareto边界PF。

　　
　　4 算例及结论

　　
　　本文算法采用Visual Studio 2005（C#语言）实现，硬件环境为PC （Pentium IV 3.0 GHz C内存：2G）。

　　
　　4.1 算例一

　　
　　现有8家工厂、9家仓库，工厂的供应量为：a = （10, 8, 12, 16, 21, 15, 7, 9），和需求量为：b = （9, 7, 15, 10, 13, 16, 7, 10, 11）。算例拥有两个成本矩阵，如下：

　　
　　免疫

　　
　　模糊规则

　　
　　算法中的参数设置：pop_size=50，max_gen=10000，run=5。

　　
　　模糊规则

　　
　　上图是上面相同参数下三种算法的结果比较。”圆点”代表st-GA，即基于Pruefer树的遗传算法，该算法是采用贪婪法的运输分配方案。”矩形点”代表Fuzzy-GA，是在st-GA的基础上采用fuzzy规则来对运输量进行模糊分配。”菱形点”代表本文 Lam-GA算法结果，得到了更好的结果。如：（207,207）。而且明显看出取得了很好的Pareto前沿面。

　　
　　4.2 算例二

　　
　　算例二的规模较大，设有18家工厂，19家仓库，工厂供应量为a=（27, 38, 35, 24, 12, 29, 37, 42, 56, 36, 42, 40, 60, 22, 19, 38, 66, 48），仓库的需求量为b=（42, 30, 37, 19, 36, 46, 45, 37, 24, 46, 38, 23, 29, 45, 62, 18, 30, 28, 36）。该算例的成本矩阵如下：

　　
　　免疫模糊规则

　　
　　算法中的参数设置：pop_size=120,max_gen=5000,run=5次。

　　
　　多目标优化上图和前面算例一样。”圆点”代表st-GA，即基于Pruefer树的遗传算法，该算法是采用贪婪法运

　　
　　输分配方案。”矩形点”代表Fuzzy-GA，是在st-GA的基础上采用fuzzy规则来对运输量进行模糊分配。”菱形点”代表本文Lam-GA算法结果。从图可以明显看出，对于大规模算例，本文中的算法取得了很好的Pareto前沿面和Pareto解。

　　
　　本文提出的新的Lam-GA算法，采用了新的可行性判断方法，具有更快的收敛速度和更强的收敛性，在保持供应平衡的基础上对运输量进行局部变异，提高了解的精度。通过加入免疫思想中抗体浓度控制，使得Pareto解的分布性更加均匀。

　　References （参考文献）

　　[1] Zou Shurong and Zhong Hongwei, Fuzzy-GA and Multi-Objective Transportation ptimization, IEEE International Conference cis-ram .270-273，9，2008

　　[2] Michalewicz. Z, Genetic Algorithm + Data Structure = Evolution Programs,3rd. edition, Springer-Verlag, New York, 1996

　　[3] Michalewicz. Z, G. A. Vignaux and M. Hobbs, A non-standard genetic algorithm for the nonlinear transportation problems, ORSA Journal of computing, vol. 3, no.4, 307-316, 1991

　　[4] Gen,M. and Y. Li,Spanning tree-based genetic algorithm for bicriteria fixed charge transportation problem, in proceeding of the Congress on Evolutionary Computation, PP.2265-2271 Washington, DC,1999

　　[5] Gen,M. and R. Cheng, Genetic Algorithm and Engineering Optimization, J Wiley&Sons, Inc, 20004

　　[6] 多目标进化算法及其应用[M] 郑金华 科学出版社 2007

　　[7] 自然计算、机器学习与图像理解前沿[M] 焦李成 公茂果等 西安电子科技出版社 2008

　　[8]Feng Zhongtian and Zou Shurong , Improvement of the Algorithm to Determine the Feasibility of the Prüfer Number, IEEE International Conference on Natural Computation（2009）

　　[9] J. Jang, C. Sun and E. Mizutani, Neuro-Fuzzy and Soft Computation, Prentice Hall, 1997

　　[10] Das Indraned etal, A Closer look at Drawbacks of Minimizing Weighted Sums of Objectives for Pareto Set Generation in Multicriteria Optimization Problems, Structural Optimization, 14（1），63-69, 1997

　　[11] 人工免疫系统[M] 莫宏伟 左兴权 科学出版社 2009

　　[12] 免疫进化理论与应用[M] 杨孔雨 社会科学文献出版社 2008