欢迎来到论文网! 识人者智,自知者明,通过生日认识自己! 生日公历:
网站地图 | Tags标签 | RSS
论文网 论文网8200余万篇毕业论文、各种论文格式和论文范文以及9千多种期刊杂志的论文征稿及论文投稿信息,是论文写作、论文投稿和论文发表的论文参考网站,也是科研人员论文检测和发表论文的理想平台。lunwenf@yeah.net。
您当前的位置:首页 > 毕业论文 > 物流管理毕业论文

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

时间:2015-08-28  作者:李建强张洪伟

【摘要】运输问题可引申为多种组合优化问题,这类问题属于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的多目标运输问题研究多目标优化=模糊规则

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

查看相关论文专题
加入收藏  打印本文
上一篇论文:基于电子商务环境下物流配送系统的设计与实现
下一篇论文:农产品物流安全指标评价
毕业论文分类
行政管理毕业论文 工商管理毕业论文
护理毕业论文 会计毕业论文
会计专业毕业论文 英语专业毕业论文
大学毕业论文 硕士毕业论文
计算机毕业论文 市场营销毕业论文
物流管理毕业论文 法学毕业论文
相关物流管理毕业论文
最新物流管理毕业论文
读者推荐的物流管理毕业论文