广东工业大学自动化学院 张永前 蔡延光 汤雅连

1.引言

固定费用运输问题（fcTP）[1-3]属于高级运输问题，是运输问题的扩展。许多实际运输和分配问题，如具有固定物流费用的最小费用网络流（转运）问题，可以用公式表示为固定费用运输问题。除了运输问题的两个约束条件，fcTP还考虑在每个工厂与仓库之间的每一次运输会存在一定的固定成本，而每一家工厂或仓库还需要固定投资。线性运输问题则没有考虑这些固定成本和投资。fcTP属于非线性运输问题，目标函数具有不连续性，比运输问题更难处理。在实际问题中，找到fcTP的最小运输费用，对于减少运输成本，合理有 效分配资源，有着十分重要的意义。

关于fcTP的研究文献已有许多。早期工作包括：用分支定界法[4]求解pfcTP(pure fixed charge transportation problem)，采用Benders型策略和约束性Lagrangean启发式算法， 将后者与分支定界法相结合，计算结果表明两种方法都是可行的，但是不适用于大规模问题模型；文献[1]用分支法求解fcTP，产生了好的初始解，而且每次迭代能使解接近于最优解；文献[5]中提出fcTP中的目标函数是一个阶跃函数，并用启发式算法对sfcTP(step fixed charge transportation problem)求解；文献[6]中提出用生成树遗传算法求解非线性固定运输问题，并通过实验证明了该算法求解fcTP的有效性，但是仍然摆脱不了遗传算法陷入局部最优以及收敛速度慢的局限性。本文提出了用CABC(Chaos Articficial Bee Colony Algorithm)求解fcTP，并给出详细分析及实验结果对比分析。

2.问题描述及数学模型的建立

固定费用运输问题描述为：在考虑了与活动水平成比例的可变成本和固定成本这两类费用后，通过分配每家工厂的可用供应量，满足每个仓库的需求，来确定使运输成本最小的运输计划，即以运输成本为目标函数，寻找使目标函数最小化，同时满足下列条件的运输计划：

(I)工厂i到仓库j的运输量应不超过工厂i的可用量也不小于仓库j的需求量。

(II)运输量为0的情况下，不计算其引起的成本费用。

m家工厂和n个仓库的固定费用运输问题的数学模型如下：

3.算法设计

3.1 人工蜂群算法

人工蜂群（ABC）算法[7-10]是Karaboga提出的一种模仿蜜蜂觅食的仿生智能优化算法，与遗传、免疫克隆、粒子群等算法相比，ABC算法是一种较好的全局优化算法，具有设置参数少、计算简单、收敛速度快等优点。ABC算法将蜂群分为三组：采蜜蜂群、跟随蜂群和侦察蜂群。蜜蜂与一个正在采蜜的蜜源对应，记录蜜源的相关信息，通过摇摆舞与其他蜜蜂分享信息；跟随蜂在跳舞区等待分享采蜜蜂带来的蜜源信息；侦察蜂探索新的蜜源。算法的搜索活动包括3个阶段：(1)采蜜蜂对蜜源进行搜索并记忆蜜源的花蜜量；(2)观察蜂根据从采蜜蜂处获得的信息选择一个蜜源位置并对记忆的位置作一定的改变；(3)确定侦察蜂并且使其开拓新的蜜源来替代旧蜜源。在算法中，一个蜜源的位置代表优化问题中一个可能的解，蜜源的花蜜量代表解的质量(适应度)。根据蜜源的花蜜量，观察蜂选择某个蜜源的概率为(6)式，其中为蜜源个数，fit(i)为蜜源i的适应度值。

为了根据记忆位置Xi产生一个新的候选位置Vi，标准ABC算法采用式(7)更新。其中k为不同于i的蜜源， j为随机选择的下标，ijφ为[-1，1]之间的随机数。

假如蜜源Xi经过“limit”次采蜜蜂和观察蜂的循环搜索更新之后，不能够被改进，那么该位置将被放弃，该位置的采蜜蜂成为侦察蜂。“limit”是ABC算法中一个重要的控制参数，用来控制侦察蜂的选择。侦察蜂发现新位置并替换Xi的操作如式(8)所示。

3.2 动态搜索

按(7)式生成解空间[11]：则yi越大，则种群在第i维坐标上的空间分布就越大。

3.3 混沌理论

混沌[11]是自然界广泛存在的一种非线性现象，是一种貌似无规则的运动，是非线性动力系统所特有的一种运动形式，具有随机性、遍历性及规律性等特点，在一定范围内能按其自身的规律不重复地遍历所有状态。常用的混沌模型有Logistic映射模型，而Logistic映射所产生的序列不均匀，浪费了计算时 间，所以本文采用Z映射[12]，如式(10)所示。

3.4 混沌人工蜂群算法

3.4.1 基本思想

混沌人工蜂群算法的基本思想主要有：

(1)利用混沌运动的遍历性以当前搜索停滞的解为基础产生混沌序列，用产生的混沌序列中的最优位置替代其原位置，使得搜索停滞的解继续进化，提高算法的收敛速度和精度。

(2)将种群分为两部分：一部分动态调整搜索区域，加快算法的收敛速度；另一部分在原空间内搜索，保证位于空间边缘的解不被忽略。

(3)在每一次混沌搜索空间调整后，进行压缩后的迭代，使群体适应新环境。

3.4.2 算法流程

混沌人工蜂群算法的步骤为：

Step1：参数初始化设置，混沌序列初始化种群。

Step2：根据(6)式，计算每个解xi的适应度。

Step3：若符合调整搜索空间的条件，则按(9)式产生新的解空间；若不符合，则根据(7)式产生新的解vi，并计算其适应度值。

Step4：若vi与xi的适应度值相等，则用vi代替xi，否则保留xi不变。

Step5：根据轮盘赌选择策略选择与xi相关的概率值pi。

Step6：跟随蜂根据pi选择食物源，并根据(7)式进行领域搜索产生新的解，如果与xi的适应度值相等，则用代替xi，否则保留xi不变。

Step7：如果有需要放弃的解存在，则利用混沌搜索产生一个新解来代替。

Step8：判断是否达到最大迭代次数，达到则输出结果，否则执行Step3。

4.仿真实例

以文献[2]中的实例为实验对象，5x10问题模型如表1所示。本文中的实验是在Intel(R)Core™i3 CPU2.53GHz、内存为2.0G、安装系统为win7的PC机上采用Matlab7.1编程实现的。算法参数设置如下：种群规模n=200，limit=50，迭代次数Gen=2000。采蜜蜂群的规模，跟随蜂群的规模。并与文献[3]中的免疫克隆选择算法求解的结果相比较。由表2知，混沌人工蜂群算法在求解固定费用运输问题时略优于免疫克隆选择算法。

5.结束语

提出了混沌人工蜂群算法，分析了固定费用运输问题的模型。将混沌搜索策略引入到算法中，提高了算法的局部搜索能力，引导个体逐步趋于全局最优解。仿真实验表明，该算法的提出有一定的优越性。人工蜂群算法是一种新的群智能优化技术，目前关于这方面的文献相当较少，因而具有广阔的应用前景。人工蜂群算法中的参数设置如何影响算法性能也需要进一步探讨。总之，对人工蜂群算法的深入研究将会在很大程度上拓展群智能和拓宽应用领域，从而能解决更多的实际问题。

表1 5x10问题的抽样数据

表2 两种算法比较结果

[1]Veena Adlakha,Krzysztof Kowalski.On the fixedcharge transportation problem,Omega,Int.J.Mgmt.Sci.27(1999):381-388.

[2]玄光男,程润伟.遗传算法与工程优化[M].北京:清华大学出版社,2009:242-246.

[3]秦子玄,陈霞,唐小鹏,梁时木,漆杨,于中华.基于免疫克隆选择算法的固定费用运输问题优化[J].计算机应用研究,2009,26(7):2530-2534.

[4]Maud Gothe-Lundgren and Torbjorn Larsson.A set covering reformulation of the pure fixed charge transportation problem.Discrete Applied Mathematics 48(1994):245-259.

[5]Krzysztof Kowalski,Ben jamin Lev.On step fi xed-charge transportation problem.Omega 36(2008):913-917.

[6]Jung-Bok Jo,Yinzhen Li,Mitsuo Gen.Nonlinear fixed charge transportation problem by spanning tree-based genetic algorithm.Computer&Industrial Engineering 53(2007):290-298.

[7]银建霞,孟红云.具有混沌差分进化搜索的人工蜂群算法[J].计算机工程与应用,2011,47(29):27-30.

[8]拓守恒.一种求解高维约束优化问题的人工蜂群算法[J].计算机应用研究,2012,29(3):937-940.

[9]张超群,郑建国,王翔.蜂群算法研究综述[J].计算机应用研究,2011,28(9):3201-3206.

[10]W.Y.Szeto,Yongzhong Wu,Sin C.Ho.An artificial bee colony algorithm for the capacitated vehicle routing problem.European Journal of Operational Research 215(2011):126-135.

[11]暴励,曾建潮.自适应搜索空间的混沌蜂群算法[J].计算机应用研究,2010,27(4):1330-1334.

[12]王毅,赵建军,冯巍巍,付龙文,陈令新.基于自适应混沌粒子群优化的防空目标分配[J].计算机工程,2012,38(20):144-147.