基于免疫思想GA的多目标运输问题研究
来源：UC论文网2015-10-30 14:06
摘要：
多目标优化问题可有如下数学表述,是基于Pruefer编码、解码|keyimg10|和基于模糊规则的遗传算法,本文在标准遗传算法的
关键词：多目标优化,模糊规则,免疫,浓度控制
在求解多目标优化问题时，由于目标意义不同，存在目标之间的无法比较和冲突现象，不一定在所有目标上都是最优的解。为了达到总目标的最优化，必须折中获取目标值。在多目标空间中，空间的代数结构仅满足偏序性(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)
(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()==由此可以推知，=
根据上式可知，集合中与抗体基因相似的抗体越多,抗体被选中的概率就越小；反之，与抗体相似的抗体越少，抗体被选中的概率就越大，这使得差异性大的抗体获得更好的进化机会，因此，基于抗体浓度的选择在理论上保持了抗体多样性，而从使得抗体在新一代解群中都应具有较好的散布性。
在求解多目标优化问题时，由于目标意义不同，存在目标之间的无法比较和冲突现象，不一定在所有目标上都是最优的解。为了达到总目标的最优化，必须折中获取目标值。在多目标空间中，空间的代数结构仅满足偏序性(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)
(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()==由此可以推知，=
根据上式可知，集合中与抗体基因相似的抗体越多,抗体被选中的概率就越小；反之，与抗体相似的抗体越少，抗体被选中的概率就越大，这使得差异性大的抗体获得更好的进化机会，因此，基于抗体浓度的选择在理论上保持了抗体多样性，而从使得抗体在新一代解群中都应具有较好的散布性。
