混合问题

混合问题（精选十篇）

混合问题 篇1

关键词：改进粒子群算法,回溯法,旅行商问题

1 引言

TSP(Traveling salesman problem)是最经典的NP—完全问题,广泛应用于:城市管道铺设优化、物流等行业中的车辆调度优化、制造业中的切割路径优化等领域。问题描述为:有个城市,一个旅行商从某个城市出发,遍历所有城市后回到出发点,求一条经过所有城市一次且仅一次的最短遍历路径。其形式化描述为:给定加权图G=(VG,EG),其中VG表示顶点(城市)的集合表示为:VG={1,2,…,n};EG为赋权边(表示两个城市间的距离)的集合,表示为:EG={(i,j,wij),i,j∈VG,wij∈R+};Hamilton路径可以表示为:S=;其中,且对1≤i≤n,有(Vi,V(imodn)+1,wviv(imodn)+1)∈EG。记H(G)为G中所有Hamilton回路的集合,定义;目的是要寻找一条最短的Hamilton回路S*,使得:w(S*)=minS∈H(G)w(S)。

TSP是组合优化难解问题之一，目前求解组合优化问题的主要方法有模拟退火算法、遗传算法、Hopfield神经网络算法和粒子群算法[1,2,3]等。文献[2]在定义调整因子和调整序等相关概念的基础上成功地重构了离散域上的PSO算法，文献[3]在算法中引入个体间的协作机制和速度变异等改进机制。但是所有这些改进在一定程度上改善了算法的全局收敛能力，没有改变随机搜索的本质，不能保证一定收敛到全局最优解。而回溯法[4]是一种传统的全解空间搜索算法只适合于小规模问题求解。本文将改进粒子群算法快速收敛性和回溯法的全局收敛能力相结合，先利用改进粒子群算法快速获得一个局部最优解在此基础上再进行回溯搜索。这样可以减少搜索空间，提高全局搜索效率。仿真实验结果表明了两种算法结合的有效性。

2 PSO算法在离散领域的重构和改进

基本PSO算法是基于群体信息(当前全局最优个体信息)和个体自身经验(个体本身所经历的最优信息)的总结来修正个体行动策略，最终求取优化问题的解。由于TSP问题的特殊性，基本PSO算法中的速度迭代公式已不适合TSP问题。为此，文献[2]提出了调整因子和调整序等概念，详细定义请参阅文献[2]，基于这些概念基本PSO算法在离散域上重构如下：

其中，学习因子C1,C2为非负常数，rand和Rand是两个独立的介于[0,1]之间的随机数;t表示进化代数;Xit表示粒子i的当前位置;Vit表示粒子i的当前速度(调整序);Pgbest表示当前最优粒子位置;Pbesti表示粒子i曾经搜到的最优位置;公式(1)中的第1部分是粒子的惯性速度，w是惯性权重因子，它体现了粒子的记忆行为;第2部分为“认知”部分，表示了粒子的动作来源于自己经验的部分;第3部分为“社会”部分，表示粒子的动作来源于群体中其他粒子的经验部分，表现为知识的共享和合作。ω茚Vit表示以权重ω保留原有速度中的调整因子;同理，对于“认知”和社会部分表示相同的含义。(C1*rangd)和(C2*Rangd)大小分别表示粒子个体最优和全局最优对粒子的影响程度。

在公式(1)中，ω的存在非常必要，如果没有ω，即ω=1，则速度(即调整序的调整因子个数)呈增加趋势，直到粒子当前解序列与个体最优及全局最优相同时，调整因子的个数才保持不变。这样在进化中，粒子长时间处于位置交换之中，进化缓慢，这势必影响算法的性能。本文综合考虑全局搜优和收敛速度，采用下式计算惯性权重：

粒子群算法的一种改进措施是在算法中引入个体间的协作机制，详细请参见文献[3]。其基本思想是在进化的初期，粒子以较大的概率向种群中的其他粒子的个体最优学习，而在中后期，则以较大的概率向当前全局最优个体学习，这样加强了对整个空间的搜索，从而增加了发现全局最优解的机会。其选择策略如下：在第t(t<[0.8*MaxGen])代的进化过程中，随机产生一个0到1之间均匀分布的随机数r，按公式(4)计算Rt。如果r≥Rt，则从粒子群中除自身和最佳的粒子之外，随机选择一个粒子，以该粒子的最优位置，记为Pmd代替公式(1)中的Pgbest，即按公式(5)对当前粒子的速度进行更新;否则按照公式(1)进行更新。

其中t为当前进化代数，MaxGen为最大进化代数。其中Pmd是从其它粒子的Pbesti中随机选择的且不等于Pgbest。

另外，PSO算法依靠的是群体之间的合作与竞争，粒子本身没有变异机制，如果单个粒子一旦受某个局部极值的约束，此时需要借助其它粒子的成功发现。如果大部分粒子均被相同的局部极值所限制时，PSO算法容易出现暂时的停滞现象，需要经过一段很长的时间后才有可能突破局部极值的限制。这说明在短期内粒子很难跳出局部最优解的束缚。

变异是模拟生物在自然环境中由于各种因素引起的基因突变。由于TSP问题的特殊性，即改变速度即可改善种群的多样性。没有没有必要对粒子的位置向量进行变异，而是根据生物在运动中，在突然遭到外界的扰动或者发现新的目标时，速度突然改变这一现象，在基本PSO算法中引入速度变异机制。变异原则为：在算法中设置一常数Tzmax和一变量Bt，分别定义为种群最大停滞代数和种群当前不变代数;如果种群在进化一代后，没有改进则Bt=Bt+1，否则，Bt=0。如果种群在连续进化Tzmax代后都没有改进，即当Bt>Tzmax时，进行速度变异：在种群中随机选择一部分粒子，舍弃其原有的速度(调整序)，重新随机生成。这样这些粒子会快速脱离局部最优的束缚，增大发现全局最优的机会。

3 回溯算法的引入

改进措施在粒子群算法中引入，一定程度上改善了算法的全局收敛能力，但算法的随机性没有改变，算法仍然不能完全保证收敛到全局最优解。而回溯法是一种全局搜索技术，具备全局收敛能力。简介如下：

回溯法是穷举搜索技术的一种变种，它的主要思想是每次只构造解的一个分量，然后依据约束规则评估这个部分构造解。如果一个部分构造解可以进一步构造而不会违反问题的约束规则，就接受对解的下一个分量所做的第一个合法选择。如果无法对下一个分量进行合法的选择，就不必对剩下的任何分量再做任何选择了，直接进行回溯，把部分构造解的最后一个分量替换为它的下一个选择。通过对所做的选择构造一棵所谓的状态空间树，树的根代表了在查找解之前的初始状态，树的第一层节点代表了对解的第一个分量所做的选择，第二层节点代表了对解的第二个分量所做的选择，以此类推。如果一个部分构造解仍然有可能导致一个完整解，我们说这个部分解在树中的相应节点是有希望的;否则，我们说它是没希望的。叶子则要么代表了没希望的死胡同，要么代表了算法找到的完整解。回溯算法的状态空间树按照深度优先的方式来构造。如果当前节点是有希望的，通过向部分解添加下一个分量的第一个合法选择，就生成了节点的一个子女，而处理也会转向这个子女节点。如果当前节点变得没希望了，该算法回溯到该节点的父母，考虑到部分解的最后一个分量的下一个可能选择。如果这种选择不存在，它再回溯到树的上一层，以此类推。最后，该算法就可以找到问题的一个完整解，然后在此解的基础上继续查找优于该解的其他解。

例如5个节点的TSP问题，假设从1出发，最后回到1，开始没有限制，回溯法按照上述规则找到的第一个完整解为(1,2,3,4,5,1)，设其路径长度为C，然后继续回溯搜索优于该解(路径长度小于C)的新解，如果L35+L54+L41

4 改进粒子群算法和回溯法结合求解TSP问题

4.1 目标函数

设粒子i的位置如上所述，则粒子i所表示的TSP路径总长度(即位置Ti的适应值函数)为：

目标是要求出适应值最小的粒子位置。若边(ei,k,ei,k+1)∈VG，则存在正整数wei,kei,k+1∈R+,否则表示城市ei,k和城市ei,k+1没有直接通路，取wei,kei,k+1为一较大数值。

4.2 MPSO回溯法混合求解TSP问题描述

根据上述算法改进思想及速度变换重新构造TSP问题求解步骤如下：

1)设置问题域系统参数如城市的数量，初始化权值、种群规模以及边界条件等;

2)初始化种群：即随机产生粒子i(1≤i≤m)的位置向量Xii(αd)(1≤d≤N+1)和调整序STi(j,k)(1≤j,h≤N+1)。设置c1,c2,Tzmax,t=1,Bt=0;

3)根据公式(5)计算每个粒子的适应值f(Xi)，如果该位置优于Pbesti,则Pbesti被当前位置替换;否则Pbesti保持不变;

4)在当前个体的最优解Pbesti中选择一个最优值，如果它优于Pgbest，则用其更新Pgbest，且Bt=0;否则，不更新，Bt=Bt+1;

5)按公式(3)计算惯性权重w，并随机产生rand,Rand以及随机数γ，按公式(4)计算Rt;

6)如果t

7)如果BT>TZmax，则在群体中选择一部分粒子，舍弃其原有速度，重新随机生成;并且令Bt=0;t=t+1;

8)终止条件判定：如果达到最大迭代次数转Step 9;否则，转入Step 3。

9)用粒子群算法获得的局部最优解路径Pgbest和适应度初始化回溯算法的第一个完整解和条件约束(当前路径长度)，然后进行回溯搜索，回溯结束，保留的完整解即为全局最优解。

5 仿真实验分析与结论

对于14个节点的Burma14TSP问题，由于该问题解空间较小，直接回溯法和改进粒子群算法都能快速发现全局最优解，为了说明两种算法结合的有效性这里采用gr17标准旅行商问题。

实验环境：WINDOWS XP CPU T2050 2G内存，先用回溯法直接求解，经过全空间搜索可以找到全局最优解，共发现中间解105个。改进粒子群算法求解该问题时，为了提高计算速度，种群规模为30，最大进化代数为3000，最大停滞代数为8，惯性权重根据公式w=0.6-(t/MaxGen)*0.5(其中MaxGen为最大进化代数)动态变化;学习因子C1=1.4962,C2=1.4962。算法快速地收敛于次优解，其路径长度为2090。再进行回溯搜索，很快便得到全局最优解，其路径长度为2085，还有一个中间解，解路径长度为2088，但回溯并没有结束，继续遍历没有回溯到的解空间,共计回溯16分钟。

其搜索曲线如图1所示。

从搜索曲线可以看出，两种算法结合求解TSP问题，开始时由粒子群算法进行搜索，其收敛速度明显高于回溯法，而后期由回溯法保证收敛于全局最优解，避免了粒子群算法的随机性，而且整体速度快于回溯法，说明两种方法结合，即在粒子群算法搜优的基础上进行回溯，减少了一定的回溯空间，提高了回溯效率，弥补了粒子群算法的全局寻优能力的提高。但对于大规模TSP问题由于回溯法难于遍历整个空间，使得回溯效率不高，仍然不适合大规模求解，如何在保证全局搜优的基础上大幅度地减少不必要的搜索空间是进一步要研究的问题。

参考文献

[1]Kennedy J,Eberhart R.Particle swarm optimization[R].In:IEEE Int.Conf on Neural Networks,Perth,Australia.1995:1942-1948.

[2]王翠茹,张江维.基于改进粒子群优化算法求解旅行商问题[J].华北电力大学学报,2005,32(6):47-51.

[3]王翠茹,冯海迅,张江维.基于改进粒子群优化算法求解旅行商问题[J].微计算机信息,2006,22(8):273-275.

混合运算解决问题教学反思 篇2

在教学中，我充分利用多媒体课件，使教学更直观形象。从过画彩条图，帮助学生理解题意，分析题意，明确问题及解决方法。学习知识是为了运用这些知识解决生活中的问题，从而体会数学和生活的联系，以及数学在生活中的价值。在这一环节，我设计了一系列由易到难的题目。

设备混合布局问题研究 篇3

(上海海事大学 物流工程学院， 上海 201306)

0 引 言

混合布局系统从物理意义上说有其存在的理由.纯粹由一种布局类型所构成的实际生产车间并不多见，多种不同类型的布局往往同时存在，因此实际生产中的车间多数是混合布局车间.

目前，关于设备混合布局没有统一的表述，但都称混合布局是车间内设备多种布局形式的综合.设备混合布局的形式没有限定，能更真实地表达车间实际的设备布局需求状况，因此设备混合布局是未来设备布局的主要发展方向.

目前关于空间优化的研究有很多：文献[1]研究基于产品部分检验的设备单行布局建模与仿真；文献[2]和[3]基于启发式算法研究设备多行布局问题；文献[4]和[5]研究码头堆场空间资源分配优化问题等.由于设备混合布局没有固定的表现形式，存在布局形式表达、建模与求解等一系列难题，因此关于设备混合布局的研究较少：文献[6]认为设备布局只有串联、并联和串并联混合3种形式，对混合结构的布局形式和求解过程进行简化；文献[7]提出一种混合布局可视化算法，该算法主要应用于iNetboss综合网络管理系统；文献[8]仅对设备混合布局的形式进行阐述；文献[9]以卫星仪器舱布局优化设计问题为背景建立二维混合布局的组合优化模型，其研究的混合布局是矩形和圆形的混合，并非真正意义的布局形式混合.鉴于此，本文引入设备单元布局，通过对单元布局的求解间接求解设备混合布局问题.

很多学者往往在单元布局设计前假定已确定设备单元构成[10-11]，然而设备单元构成关系到单元布局优化方案的好坏.因此，本文将设备单元布局方案设计分3步完成：(1)设备单元划分；(2)设备单元内布局方案设计；(3)对构建的设备单元进行多单元系统布局求解.

1 混合布局设备单元划分

设备间关系的模糊性给设备单元划分带来困难，为克服这个难题引入模糊理论：以各设备之间在某种特性(如加工功能、设备密切程度等)上的模糊关系为依据，构造车间所有设备的模糊关系矩阵，运用模糊聚类法将关系紧密的设备聚在一起进行设备单元划分.基于模糊理论的设备单元划分步骤见图1.

图1 基于模糊理论的设备单元划分

置信水平λ变化率最大的数学模型为

(1)

式中：i为λ从大到小的聚类次数；λi为第i次聚类时的置信水平；ni为第i次的聚类数.

2 混合布局设备布局方案设计

分形理论[12]是研究复杂但具有一定意义下的自相似图形的结构几何学的理论.分形理论在布局中的应用是其在实际应用中较新的课题.基于分形理论自身的自相似原理，本文提出一种“田”分形理论模型，使分形理论用于单元布局，从系统角度考虑车间布局的优化问题.基于“田”分形理论的设备单元布局能够根据产品生产的需求变化及时调整局部布局，可重构性非常强.

设备单元“田”形布局是指单元的排列方式仿照汉字“田”的形状，由1条主线和5条副线组成，任意相邻的设备单元可以传输产品.相对于已有的“E”形布局[13]，“田”形布局能够增强单元间的产品流通，使布局更加紧凑，节省物流费用.设备单元“田”形布局见图2.

图2 设备单元“田”形布局

“田”形布局由9个设备单元构成，每条线由3个设备单元构成，其中不足的设备单元用虚拟单元代替.若有的设备单元包含的设备数>9，则对该设备单元的设备进行模糊聚类分析，进行二级设备单元“田”形排列，直至设备单元的设备数量≤9为止，因此该方法对设备数量没有限制，适用性较强.设备“田”形布局的逐级分解见图3.

图3 单元“田”形布局逐级分解

设备在“田”形网格里的布局优化进程类似于人工智能中博弈问题的求解,采用深度优先的回溯搜索策略[14]：遇到多个求解路径时，沿着其中一个路径一直走下去，当无解或无理想解时，回溯到最近的交叉点，选择另一条路径，如此往复，最后求出最优解或接近最优解.“田”形网格的构成过程见图4.

为简化设备混合布局数学建模和求解计算，假设所有设备形状均为矩形，忽略其细节形状，且设备出入口的位置已知.

以物流费用最小为优化目标，构建设备单元“田”形布局数学模型.物流费用最小化函数为

(2)

式中：Qij，fij，dij和Cij分别为设备(单元)i与设备(单元)j之间的当量物流量、物流频率、物流距离和物流成本.

图4 “田”形网格的构成过程

3 实例研究

以某企业的BJ面膜生产车间设备混合布局为例进行方法验证.车间不同设备符号对应的设备名称：{Mi(i=1，2，…，10)}={罐装，封口，检验，滚压，装盒，打码，烟包，装封箱，贴标签，托盘}.设备间当量物流量、物流频率和设备间必须保持的最小物流距离分别见表1，2和3.

3.1 设备单元划分

设置面膜生产车间设备模糊分类的特性指标为{加工功能，设备密切程度}，评价等级设置为{非常相似/密切，较相似/密切，一般相似/密切，不相似/密切}.为便于比较，将评价等级数值化，对应为{0.8，0.6，0.4，0.2}.专家和相关技术人员可以根据评价等级进行相应打分，进而可得设备模糊关系聚类矩阵

因为模糊等价关系矩阵R*要求R不仅满足自反性、对称性，还要满足传递性[15]，所以对R进行标准化处理后再进行传递闭包运算：

t(R)=R*

(3)

因此，R*=R8.

设置信水平λ分别为0.8，0.6，0.4和0.2，分别写出对应的Rλ，可得每个λ下的设备聚类情况,见表4.

表1 设备间当量物流量Qij

表2 设备间物流频率fij 次/h

表3 设备间必须保持的最小距离dij m

表4 不同置信水平λ下的设备聚类情况

根据最优聚类公式可得μmax=0.2，对应的最优聚类置信水平取值为0.8和0.6，对应的设备最优聚类数量为5和4.限于篇幅，本文仅对聚类数量为5的情况进行研究分析.

3.2 设备混合布局方案设计

设设备单元为Ui，{Ui(i=1,2,…,5)}={{M1，M2},{M3，M4，M5},{M6，M7},{M8},{M9，M10}}.首先，进行单元内的设备“田”形布局方案设计.由于单元U1的设备数量只有2台，所以无须进行“田”形排列.单元U2的设备有M3，M4，M5，其设备间物流量排序见表5.

表5 单元U2内设备间物流量排序

图5单元U2的“田”形布局方案

根据“田”形网格设备单元摆放过程，U2布局方案见图5.

U3，U4和U5包含的设备数量均不超过2，无须进行对应的单元内设备“田”形布局设计.

设备单元间的物流量排序见表6.

表6 5个设备单元间物流量排序

由表6可以看出，U4和U5之间的物流量第一，其余各单元间的物流量相等，均为第二.根据设备单元“田”形布局的构成过程可得设备单元的布局方案，见图6.

图6设备单元“田”形布局方案

单元间最小物流距离为包含设备的最小物流距离.根据车间设备物流成本公式计算对比可得，布局方案(d)的物流费用最小，因此面膜生产车间设备采用该布局.详细的设备布局见图7.

图7车间设备混合布局

4 结束语

将设备混合布局问题转化为设备多单元系统布局问题，通过对设备多单元系统布局的求解间接求解设备混合布局问题.实例研究表明，该方法不限设备混合布局的形式，不用作过多的简化，可为设备混合布局问题的研究提供一个新的方向.

参考文献：

[1] 周娜, 宓为建, 姜波. 基于产品部分检验的设备单行布局建模与仿真[J]. 上海海事大学学报, 2012, 33(3): 36-41.

[2] 郭源源, 王谦, 梁峰. 基于粒子群优化算法的车间布局设计[J]. 计算机集成制造系统, 2012, 18(11): 2476-2484.

[3] AMIR S. A genetic algorithm with the heuristic procedure to solve the multi-line layout problem[J]. Computers & Ind Eng, 2012, 62(4): 1055-1064.

[4] 顾天意, 梁承姬. 基于矩阵式遗传算法的集装箱码头堆场空间资源分配优化策略[J]. 上海海事大学学报, 2012, 33(2): 40-46.

[5] 白治江, 王晓峰. 基于负载平衡的堆存空间分配优化方案[J]. 上海海事大学学报, 2008, 29(3): 60-64.

[6] 李占国, 唐慧君, 王彤宇, 等. 基于遗传算法的可重构制造单元设备布局优化方法的研究[J]. 长春理工大学学报, 2003, 26(2): 17-19.

[7] 杨家海, 郭玺, 张辉. 基于多层次和多粒度的混合布局可视化算法及其应用[J]. 清华大学学报: 自然科学版, 2011, 51(12): 65-70.

[8] 锁小红, 刘战强. 基于物流路径的单行布局建模与仿真研究[J]. 中国机械工程, 2007, 18(21): 2576-2579.

[9] 铁军, 冯恩民. 二维混合布局问题的组合优化模型及算法[J]. 运筹与管理, 2006, 15(4): 47-50.

[10] 祝恒云, 叶文华. 模拟退火粒子群算法在动态单元布局中的应用[J]. 中国机械工程, 2009, 20(2): 181-185.

[11] KIM C O, BAEK J G, BAEK J K. A two-phase heuristic algorithm for cell formation problems considering alternative part routes and machine sequences[J]. Int J Production Res, 2004, 42(18): 3911-3927.

[12] 曼德尔布洛特(法). 分形对象[M]. 文志英, 苏红, 译. 北京: 世界图书出版公司北京公司, 1999.

[13] 张建军, 底振华, 张利. 基于分形理论的E型车间布局研究[J]. 合肥工业大学学报: 自然科学版, 2008, 31(7): 12-15.

[14] 应保胜, 张华, 杨少华. 敏捷制造车间布局优化的启发式算法[J]. 计算机集成制造系统, 2004, 10(8): 962-965.

运用混合人工鱼群算法求解装箱问题 篇4

装箱问题在现实生活中具有广泛的应用, 如多处理器的任务调度、内存分配、资源管理、运输计划等, 特别在现代的物流中, 很多问题都可以抽象化为装箱问题或装箱问题的变形, 如车辆如何装车, 才能充分利用车辆空间;资金 (资源) 如何分配才能得到最大的回报等等。因此, 找到一个高效快速的算法具有重要的现实意义。从计算复杂性理论来讲装箱问题NP完全问题, 由于目前NP完全问题不存在有效时间内求得精确解的算法, 目前的求解方法主要是一些近似算法, 如NF (Next Fit) 近似算法, FF (First Fit) 近似算法, FFD (First Fit Decreasing) 近似算法, BF (Best Fit) 近似算法, BFD (Best Fit Decreasing) 近似算法, CF近似算法等。近似算法的求解结果与物品的体积等数据又较大的关系, 甚至在某些极端的情况下, 其求解结果很不理想。本文提出了类CF算法与人工鱼群算法相结合的混合算法对装箱问题进行了求解。

2. 问题的描述

装箱问题的一般描述为:给定n个物品的序列Ln= (x1, x2, …, xn) , 物品xi (1≤i≤n) 的大小s (xi) ∈ (0, 1], 要求将这些物品装入单位容量的箱子B1, B2, …, Bm (m≤n) 中, 使得每个箱子中的物品大小之和不超过1, 并使所用的箱子数目M最小。装箱问题的数学表示如下:

其中Bi=1表示箱子i被放入物品, 反之则表示箱子i空着, αij=1表示物品j放入箱子i, 反之表示物品j未放入箱子i, s (xj) 为第j个物品的体积。

3. 人工鱼群算法

人工鱼群算法 (Artificial Fish-Swarm Algorithm, AFSA) 是李晓磊等在前人对群体智能行为研究的基础上提出的一种新型仿生优化算法。在一片水域中, 鱼往往能自行或尾随其它鱼, 找到营养物质多的地方, 因而鱼生存数目最多的地方一般就是本水域中营养物质最多的地方。人工鱼群算法根据这一特点, 通过构造人工鱼来模仿鱼群的觅食、聚群、追尾及随机行为, 从而实现寻优。以下是鱼类的几种典型行为:

1) 觅食行为:一般情况下鱼在水中随机、自由地游动, 当发现附近有食物时, 则会向着食物逐渐增多的方向游去;

2) 聚群行为:为了保证生存和躲避危害, 鱼会自然地聚集成群。鱼聚群时所遵守的规则有3条: (1) 分隔规则, 尽量避免与临近伙伴过于拥挤; (2) 对准规则, 尽量与临近伙伴的平均方向一致; (3) 内聚规则, 尽量朝临近伙伴的中心移动;

3) 追尾行为:当某条鱼发现食物时, 其他鱼会尾随其临近的伙伴快速到达食物点;

4) 随机行为:当闲暇无事时, 鱼在水中随机、自由地游动寻找食物。

4. 算法的设计

设搜索空间的维数为n, 鱼群的规模为N。每条人工鱼可表示为一个n维的向量X= (xi1, xi2, …, xm) (i=1, 2, …, N) ;适值函数Y=f (X) 表示人工鱼当前状态的食物浓度;di, j=d (Xi, Xj) (i, j=1, 2, …, N) 表示人工鱼Xi与人工鱼Xj之间的距离;δ表示拥挤度因子;TryNumber表示人工鱼每次移动的最大试探次数;Visual表示人工鱼的视野范围。

4.1 初始种群的产生

本文采用随机的方式产生鱼群的初始状态, 设要装箱的物品个数为n, 则一条人工鱼的初始状态为以下随机序列 (x1, x2, …, xn) , 其中xi∈{1, 2, …, n}, i=1, 2, …, n, 坌i≠j, xi≠xj。如有8物品要装箱, 可能的人工鱼初始状态有 (3, 5, 7, 2, 6, 8, 1, 4) 、 (3, 4, 7, 1, 8, 6, 2, 1) 等。用这种编码没有把箱子编入人工鱼的状态中, 人工鱼的状态仅和物品有关。

4.2 适值计算

适值函数的作用是将人工鱼的状态X= (x1, x2, …, xn) 转换成一种装箱方案并返回所需的箱子数量。本文采用一种类CF算法来实现这种转换, 具体描述如下:

首先把x1放入箱子B1中, 然后从最右端开始, 依次把物件xn, xn-1, …放入B1, 直到下一个物件不能再放入箱子为止, 开启新的箱子B2;设在循环时, 打开第i个箱子, 此时把物件xi放入Bi中, 再从最右端开始从右往左把物件依次放入Bi中, 假设第i-1个箱子Bi-1中最后一个放入的物件为xk, 则在第i步循环时最右端的物件为xk-1, 那当s (xi) +s (xk-1) +…+s (xl) ≤1且s (xi) +s (xk-1) +…+s (xl) +s (xl-1) >1时, 把xk-1, xk-2, …, xl放入Bi中, 开启新的箱子Bi+1。直到把物件x1, x2, …, xn放入m个箱子;最后输出m。

例如有5个物品分别重0.1、0.2、0.3、0.4、0.5, 一条人工鱼的状态为 (1、5、2、4、3) , 根据类CF算法可行装箱方案为:B1 (0.1、0.3、0.4、0.2) 、B2 (0.5) , m=2。

4.3 觅食

设人工鱼当前状态为Xi, 在其视野范围内随机选择一个状态Xj, 如果Yi

4.4 追尾

设人工鱼当前状态为Xi, 探索其邻域内状态最优的邻居XMAX, 如果Yi

4.5 聚群

设人工鱼当前状态为Xi, 探索其邻域的伙伴数目nf, 如果nf/N<δ, (0<δ<1) , 则表明伙伴中心有较多的食物并且不太拥挤, 如果此时Yi

5. 算法描述

Step1:初始化;

Step2:计算适值;

Step3:对每条工人鱼;

Step3.1:追尾;判断追尾后的状态是否好于原状态, 若是, 则转Step4, 否则转Step3.2;

Step3.2:聚群;判断聚群后的状态是否好于原状态, 若是, 则转Step4, 否则转Step3.3;

Step3.3:觅食;

Step4:更新当前最好值;

Step5:更新鱼群距离, ;

Step6:若已到最大进化代数, 退出;否则, 转Step3。

6. 实验和结果

设人工鱼X= (x1, x2, …, xn) , Y= (y1, y2, …, yn) , 则X和Y之间的距离表示如下:

k-距离邻域可以表示为:N (X, k) ={X'│d (X', X)

为了更好的测试本文算法的有效性, 笔者将本文算法与遗传算法用相同的算例及测试平台进行了一组对比实验。使用算例为x (xj) = ( (i-1) mod5+1) /10, i=1, 2, …, n。运算过程中取鱼群算法的Visual=1/n, δ=0.618, TryNumber=100, 种群规模为25, 最大迭代次数为100。遗传算法取交叉率为0.6, 变异率为0.3, 种群规模为100, 最大迭代次数为1000。运行平台为WindowsXP/VC++6.0/Intel Celeron誖2.4G/512M DDR。每个算例使用两种算法各连续计算5次, 所得结果如表1所示。

从表1的实验结果可以看出, 对大部份算例而言, AFSA在计算时间及计算精度方面均要优于GA;且当物品规模增加时, 所需计算时间并不会大幅度增长,

7. 结论

本文分析了装箱问题, 并针对装箱问题不定长解决方案的特点, 提出使用类CF与人工鱼群混合算法求解该问题。与遗传算法的对比实验表明, 本文提出的混合算法在计算速度及精度方面均要优于GA, 具有较好的应用前景。

摘要：装箱问题在实际生产中应用非常广泛, 本文在分析该问题特点的基础上, 提出了使用类CF近似算法和人工鱼群算法相结合的混合人工鱼群算法求解装箱问题, 并给出了具体的算法步骤。跟遗传算法对比, 试验结果表明, 该算法在求解装箱问题所得的结果优于遗传算法, 具有良好的应用前景。

关键词：装箱问题,CF近似算法,人工鱼群算法,混合算法

参考文献

[1]汤岩.遗传算法在装箱问题中的应用[D].大连海事大学硕士学位论文, 2005.

[2]孙春玲.装箱问题的一种新的近似算法[J].云南:云南大学学报 (自然科学版) , 2004, 26 (5) :392-396.

[3]李晓磊, 邵之江, 钱积新.一种基于动物自治体的寻优模式:鱼群算法[J].系统工程理论与实践, 2002 (11) :32-38.

[4]李晓磊, 路飞, 田国会, 等.组合优化问题的人工鱼群算法应用[J].山东:山东大学学报, 2004, 34 (5) :64-67.

混合问题 篇5

求解作业排序问题的通用混合遗传算法研究

车间作业排序理论是生产管理与组合优化领域的重要研究方向,由于其固有的计算复杂性(NP-Hard),一般无法利用经典方法求出最优解.本文针对一般作业排序问题,将遗传算法与启发式方法相结合,建立了一种混合算法框架,利用遗传算法改进启发式方法的求解性能,同时利用启发式方法引导遗传搜索过程,以提高其搜索效率.通过对完工时间与平均延误时间等不同优化目标的计算分析与比较表明,该方法对不同类型的.排序问题均具有相当满意的求解效果.

作 者：周泓 姬彬 作者单位：北京航空航天大学经济管理学院,刊 名：系统工程理论与实践 ISTIC EI PKU英文刊名：SYSTEMS ENGINEERING――THEORY & PRACTICE年，卷(期)：200121(12)分类号：O223 C931.1关键词：作业排序 遗传算法 启发式

混合型饲料添加剂有关问题浅析 篇6

关键词：混合型饲料添加剂；通用名称；生产许可

2011年修改后的国务院《饲料和饲料添加剂管理条例》颁布以来，农业部出台了一系列相关配套政策。其中，将原饲料添加剂Ⅱ类产品，归入到混合型饲料添加剂这一类中，现在大家对饲料添加剂比较好理解，而对混合型饲料添加剂的有关情况比较模糊。笔者结合目前的工作实际，就有关问题作一个简单解析。

一、混合型饲料添加剂概念

农业部第1849号公告附件2《混合型饲料添加剂生产企业许可条件》中对混合型饲料添加剂有明确的定义，是指“由一种或一种以上的添加剂与载体或稀释剂按一定比例混合，但不属于添加剂预混合饲料的饲料添加剂产品”。这里包含有三方面意思，一是无论怎么混，首先原料一定来源于已获得饲料添加剂生产许可证企业生产的饲料添加剂产品，不能是食品级（农业部第2045号公告香味物质中“食品用香料”除外）、化工级或医药级添加剂；二是一种及一种以上饲料添加剂混合，既可以是单一饲料添加剂稀释（与载体混合），例如氧化锌加载体进行稀释，也可以是两种及两种以上饲料添加剂的混合，如芽孢杆菌与低聚木糖混合；三是产品的功效侧重于功能性，不属于添加剂预混合饲料范畴，例如亚硒酸钠和维生素A混合。而添加剂预混合饲料是指由两种（类）或者两种（类）以上营养性饲料添加剂（仅指矿物质微量元素、维生素、氨基酸三类）为主，与载体或者稀释剂按照一定比例配制的饲料，包括复合预混合饲料、微量元素预混合饲料、维生素预混合饲料，产品功效侧重于营养性。

二、混合型饲料添加剂产品通用名称

由于混合型饲料添加剂这个说法是近年刚出来的新概念，大家对混合型饲料添加剂产品通用名称不好把握，尤其是在申请生产许可证、产品销售以及执法检查过程中，很多人不太清楚混合型饲料添加剂的通用名称究竟是怎样命名才算合格。首先，我们要了解目前在市场上混合型饲料添加剂生产许可证存在两种情况，一种是按《饲料和饲料添加剂生产许可管理办法》核发的混合型饲料添加剂生产许可证（2013年以后核发的简称新证），另一类就是按原《饲料添加剂和添加剂预混合饲料生产许可证管理办法》颁发的Ⅱ类饲料添加剂生产许可证仍在有效期内（简称老证）。针对新证和老证，通用产品名称就有不同的产品命名问题。就本人在实际工作中的接触和理解，混合型饲料添加剂通用产品名称应分两种情况区别对待：

第一种：关于新证产品通用名称命名

按新的许可条件下核发的混合型饲料添加剂产品通用名称分以下几种情形：（1）单一饲料添加剂品种混合或稀释，直接标示该添加剂品种名称，如枯草芽孢杆菌，应标为“混合型饲料添加剂 枯草芽孢杆菌”；（2）同类别的多种添加剂混合，应标示类别，如由枯草芽孢杆菌、乳酸杆菌和酿酒酵母等三种微生物复合而成的微生物产品应标为“混合型饲料添加剂 微生物”；（3）如果添加剂涉及的类别为二个或二个以上，但每类中只有一种产品，则每一类产品的具体产品名都要标出。如枯草芽孢杆菌和纤维素酶混合而成的产品应标为“混合型饲料添加剂 枯草芽孢杆菌+纤维素酶”；（4）如果饲料添加剂涉及多个类别，每个类别中涉及多个产品，就只标类别，每类别具体产品在组份中体现。例如几种微生物和几种酶制剂产品组成的产品，应标为“混合型饲料添加剂 微生物+酶制剂”，至于到底是哪几种微生物和哪几种酶混合，组份在三个方面有具体体现，并且这三个方面是一一对应的。一是在申报材料组份中有具体组份规定；二是在混合型饲料添加剂生产许可证产品品种栏对组份作了明确的标示；三是在产品标签的成份保证值栏中有组份具体成份。并不是企业想当然的只要有了混合型饲料添加剂许可证，就可任意进行混合。（5）如果发挥功能性作用的饲料添加剂在《饲料添加剂品种目录》分类中属于“其他”，则应直接标明其通用名称。如杜仲叶提取物产品稀释或加载体混合后，应标为“混合型饲料添加剂 杜仲叶提取物”。

（二）关于有效期内的原饲料添加剂Ⅱ类产品的通用名称问题

针对这类在有效期内原生产许可证的产品通用名称的命名，全国饲料工业标准化技术委员会以全饲标【2014】8号文作了如下规定：

对于按原《饲料添加剂和添加剂预混合饲料生产许可证管理办法》颁发的Ⅱ类饲料添加剂生产许证仍在有效期内，而这类产品与混合型饲料添加剂不完全等同，因此，在原生产许可证有效期内，上述产品其通用名称分以下两种情况进行标识：

（1）通过精制、脱水、包被等工艺处理而获得的Ⅱ类饲料添加剂产品，其通用名称表述为“饲料添加剂+《饲料添加剂品种目录》中规定的产品名称”，另起一行标注“原饲料添加剂（Ⅱ类）”字样；

（2）其余Ⅱ类饲料添加剂产品表述为“混合型饲料添加剂+《饲料添加剂品种目录》中规定的产品名称或类别”，另起一行标注“原饲料添加剂（Ⅱ类）”字样。

三、混合型饲料添加剂在申报生产许可证前要注意的几个问题

市场有一种说法，“混合型饲料添加剂是个筐，不属于添加剂、预混合饲料的都可往里面装”。其实这种观点有失偏颇。申报混合型饲料添加剂生产许可前先要把好三个关口。

第一，产品名称和组份关。企业申报混合型饲料添加剂前先要确定什么产品进行混合或稀释，或哪几种、哪几类产品混合，混合的产品主成份是否是饲料添加剂目录中已取得饲料生产许可证的产品，并且是否符合混合型饲料添加剂的基本定义。这三个条件具备后，就必须按本文中第二部分中所提到的，确定正确的产品名称和组份。例如：产品名称为混合型饲料添加剂 酶制剂，其产品组份为（淀粉酶+脂肪酶）。只有具体的产品名称确定下来，才能进行其它申报材料前的准备。

第二，标准备案关。在确定好产品名称后，如果申报的混合型饲料添加剂产品无国家标准或行业标准的话，必须制定混合型饲料添加剂企业标准。建议企业标准做好后，暂不备案，先以企业标准草案进行方法验证结论，因为在实际工作中，我们检测机构在对部分企业进行方法验证结论时，存在企业标准中提供的检验方法不完善或检验设备不全，有时按企业提供的检测方法检测时存在一些数据的修正，这些问题检测所检验人员在不影响验证方法的准确性和可操作性的前提下，针对在验证过程中发现的特殊情况提出说明或建议：诸如所用仪器、特殊器材、标准品、特殊试剂、以及其它特殊事项等提出一些修改意见，企业可以据此对标准草案进行修改，然后再去备案，这样可以节约时间，少走弯路，提高办事效率。

第三，方法验证关。农业部公告（2013）第2045号饲料添加剂品种目录中有二百多种饲料添加剂品种，从理论上讲可以任意组合成无数种混合型饲料添加剂产品，但能申请生产许可证的产品却不是任意组合就可以申报的。因为混合型饲料添加剂产品必须过产品主成分指标检测方法验证关。农业部1849号公告《混合型饲料添加剂生产企业许可条件》第二十六条中明确要求混合型饲料添加剂产品的主成分指标检测方法应当经省级饲料管理部门指定的饲料检验机构验证，但产品有国家或行业标准的除外。具体验证什么？主要是对企业申报的混合型饲料添加剂产品相应的主成份的专一性或者有效性进行验证，按企业提供的标准和检验方法，检验机构能否把主成份检验出来？能不能保证检验结果的准确？因此，就要求在申报混合型饲料添加剂生产许可证前必须事先对其产品进行验证。验证的核心是验证主成份检验方法的有效性和可操作性，并不是验证产品质量指标是否合格。通过检验机构对主成分检验方法作出验证结论后，方可进行混合型饲料添加剂生产许可证申报工作。

对重剑男女混合训练若干问题的分析 篇7

烟台击剑队自2000年建队以来, 由于受一些客观条件影响, 近十年间来一直采用“男女混合”的形式进行训练。在近十年的训练比赛中, 为各地省队输送了多名优秀运动员, 并在国内、省内的重大比赛中多次取得了优异的比赛成绩。所谓“男女混合训练”也就是将不同性别、不同剑种的运动员集中在一起进行共同训练, 通过训练最终达到共同提高竞技水平和运动成绩的目的。在训练中男女运动员合理利用这些特性可以达到互相提高共同进步的目的;但训练中同时也存在着一些消极的问题, 如不及时认清解决, 会对训练造成负面影响。本文从击剑技术训练、身体训练和实战训练等方面, 对重剑男女混合训练的优缺点进行分析探讨, 以利于击剑项目的长期发展和提高。

二、研究对象

烟台击剑队建队近十年的男女运动员。

三、研究方法

1. 观察法。

通过本人近十年来在击剑队学习训练和任教的经历, 对击剑队男女混合训练的情况进行了观察和记录。

2. 访问法。

就男女混合训练的有关问题向省队、国家队有关教练和专家进行请教访谈。

3. 文献资料法。

通过阅读男女混合训练有关文章和查阅文献资料, 了解省内、国内男女混合训练的相关情况。

四、结果与分析

烟台击剑队队自建队以来, 在省内外一系列重大比赛中, 取得了优异的比赛成绩。

从长期调查与研究的结果可以看出, 男女重剑运动员长期进行混合训练所具有的优势是男子或女子运动员单独进行训练所未有的, 但同时也存在着一些不利因素。

1. 技战术训练时的若干问题。

击剑基本技战术的学习, 要求动作规范、协调连贯。只有在掌握规范的基本技术上, 才能更快提高战术的运用能力。击剑技术的学习与训练过程, 就是运动员对技术动作做高度的熟练, 并形成高度自动化的过程。

(1) 男女重剑运动员在初学技战术时的优缺点

女运动员在学习新技术动作的初期, 她们的学习能力与男运动员并无多大差别。不足的只是在时间上和质量上。女运动员学习新动作的时间较男运动员要长些, 且开始时的质量要差些。但在开始学习过程中, 男运动员可以帮助女运动员。通过帮助训练, 能够拓宽思路、提高击剑意识;由于女运动员比较细心, 在混合训练时能够帮助男运动员更加细心地学习掌握新技术动作。其缺点在于男运动员在学习同一技术动作时, 时间加长, 在教学进度上有所脱节。

(2) 男女重剑运动员在互带个别课时的优缺点

男运动员在带女运动员个别课时, 女运动员能从男运动员那里得到更多实用的东西。这是因为男运动员传授给女运动员的都是切身体会与实战经验。男运动员带女运动员个别课, 可以弥补教练员力量的不足, 能让教练员有更多的时间和精力统筹安排训练。其缺点在于女运动员带男运动员个别课时, 在速度、力量和时机的把握上与男运动员有一定的差距。

2. 身体训练过程中的若干问题。

由于性别的差异, 女运动员的身高、体重、力量、速度、耐力等身体机能指标相对来讲都弱于男运动员。但女运动员的柔韧性和灵活性都优于男运动员。因此采用混合训练可以弥补双方的不足。通过对男女运动员的各项身体素质指标测试结果发现, 女运动员各项身体素质指标提高的同时, 男运动员也有相应的提高。其缺点在于男运动员在陪女运动员练习时, 由于性别差异各项指标提高的速度不如男运动员单独训练时快, 这要求教练员在安排身体训练时的计划要有合理性和针对性。

3. 实战训练过程中的若干问题。

在击剑教学训练中, 最接近的比赛的手段是进行各种实战练习。

(1) 不让分实战

通过不让分的实战比赛, 可以培养男运动员与弱手交锋的战术行动方法。由于女运动员的身材较矮, 男运动员也可以锻炼与矮个子运动员交锋的方法。相反, 女运动员从中可以锻炼对付高个子运动员的方法。并且提高进攻速度和交锋能力, 增强与强手交锋时的战术意识及对抗能力, 这是一种很有是实用价值的训练方法。

(2) 让分实战

让分实战就是在男女运动员同场交锋时, 规定男运动员让女运动员分数。对男运动员来讲, 这可以作为在比分落后的特殊情况下采取怎样的有效方法将比分追回的锻炼方式。这对男女运动员都是一个严峻的考验, 需要顽强的意志品质和心理适应能力, 这对提高男女运动员技战术和实战能力起到良好的锻炼作用。

(3) 擂台式实战

擂台式实战就是一名运动员在场上, 其他运动员轮流上场与其交锋的实战。这对女运动员来讲, 与男运动员轮流交锋可以更好地提高她们的专项耐力, 为正式比赛打好基础。

对男运动员来讲, 女运动员的速度、力量和节奏较慢, 在这些方面不利于男运动员的更快提高。

五、结论与建议

1. 击剑运动员进行混合训练, 对男女运动员都有益

处, 能使男女运动员同时提高并达到共同进步的目的, 特别对女运动员速度、力量、心理和技战术的提高都有非常大的帮助。她们在和男运动员的练习中可以适应更快的速度、力量和节奏, 再与女运动员交手比赛时就会在这方面占有一定的优势。烟台击剑队建队以来取得的一系列优异成绩, 就可以证明这一点。

2. 通过对以上几个方面的分析与讨论, 我们可以看

到在男女混合训练中也存在着一些不利之处, 在长期的混合训练中男运动员大量时间处在陪练的位置。虽然在心理、技战术运用等方面会有所帮助, 但长期与较弱对手练习非常不利与男运动员的全面发展和迅速提高。这还需教练员在训练比赛的过程中, 进行科学合理的安排和有针对性的调控。

3. 男女运动员在进行混合训练时应注意以下几个方面:

第一, 在运动负荷安排上, 要注意性别的差异, 男女运动员的负荷安排要有所区别。

第二, 在训练过程中要注意合理安排配对。如果配对不合理, 就会造成双方配合上的不默契, 不能得到同时提高, 只会浪费时间。

第三, 认真地对待实战比赛。对于这一点教练员应事先做好思想工作, 要求男女运动员认真对待, 防止不良态度的出现。

第四, 重视思想教育。发现情况要及时引导纠正, 避免造成不良的后果。我们要正确利用男女混合训练的优点, 将不利之处降低到最低限度, 合理地安排和调控训练过程, 就能够在省内外比赛中继续取得更好的成绩。

参考文献

[1].袁伟民.击剑[M].北京:人民体育出版社, 1996, (8) .

[2].李维仁等.奥林匹克击剑[M].北京:人民体育出版社, 2001, (6) .

[3].叶楠.女人的球, 男人的拍——乒乓女队的男陪练[J].新体育, 2001, (4) .

混合问题 篇8

有容量限制的CVRP可以描述为:一个配送中心有n辆可供运货的车辆, 每辆车有容量 (装载能力) 的限制, 其容量为常数P;有m个配送点, 每个配送点由一辆车服务, 访问且只能被访问一次;每个配送点的需求量di在 (i=1, 2, …, m) 一次服务中全部得到满足。优化的目标为:1) 在满足每个配送点的需求量的前提下使用的车数最少;2) 车辆总的行驶里程最小。

如果将配送中心设为0点, 各配送点的编号为i (i=1, 2, …, m) ;配送点各车辆编号为k (k=1, 2, …, n) ;Cij表示各个节点间的距离, 定义变量xijk, yik, 其中

$\begin{array}{l}x{}_{ijk}=\{\begin{array}{l}1,\text{车}\text{辆}k\text{经}\text{过}\text{配}\text{送}\text{点}i\text{驶}\text{向}\text{配}\text{送}\text{点}j,\\ 0,\text{否}\text{则}.\end{array}\\ y{}_{ijk}=\{\begin{array}{l}1,\text{车}\text{辆}k\text{满}\text{足}\text{客}\text{户}i\text{的}\text{需}\text{求}\text{量},\\ 0,\text{否}\text{则}.\end{array}\end{array}$

则其数学模型为[10]

$\begin{array}{l}\text{Μ}\text{i}\text{n}{\rm Z}={\displaystyle \sum _{i=0}^m{\displaystyle \sum _{j=0}^m{\displaystyle \sum _{k=1}^{n}c}}}{}_{ij}x{}_{ij};(1)\\ {\displaystyle \sum _{i=1}^{m}d}{}_{i}y{}_{ik}\le {\rm P}‚k=1,2,\cdots ,n;(2)\\ {\displaystyle \sum _{k=1}^{n}y}{}_{ik}=\{\begin{array}{l}a,i=0,\\ 1,i=1,2,\cdots ,m;\end{array}(3)\\ a\le n;(4)\\ {\displaystyle \sum _{i=0}^{m}x}{}_{ijk}=y{}_{ik};(5)\\ {\displaystyle \sum _{j=0}^{m}x}{}_{ijk}=y{}_{ik},\\ j=1,2,\cdots ,m;k=1,2‚\cdots ‚n.(6)\end{array}$

上述模型中约束条件:式 (2) 表示每个配送点的用户需求量不大于车辆的总载重量;式 (3) 表示每个配送车辆只能对每个配送点服务一次, 且配送车辆总数为a;式 (4) 表示配送的总车辆数不大于配送中心拥有的总车辆数;式 (5) 、式 (6) 表示服务完成后离开该客户。

2 求解CVRP问题的多种交叉变异策略的混合遗传算法

2.1 染色体编码方式

由于该问题所求目标为如何在使用车辆数最小的情况下使得总运输里程最小。本文针对该问题设计了自然数编码, 在[1, m]中随机产生m个不重复的自然数序列, 组成一条染色体{x1, x2, …, xm}。该染色体只表示对配送点服务的先后顺序, 如何确定车辆数, 本文设计了特殊的解码方式。具体做法是:由于车辆的载重为常数P, 当{P-x1-x2-…-xk≥0、P-x1-x2-…-xk-xk+1<0}时即第一辆车恰好满足配送点{x1, x2, …, xk}的需求量, 该车在完成对配送点xk的服务后回到配送中心, 并计算{0-x1-x2-…-xk-0}的配送走行距离值, 重复该步骤可以确定出染色体{x1, x2, …, xm}需要几辆车进行配送, 并计算出其总走行距离值。这样将问题变为一个目标值, 即确定总走行距离, 并且方便交叉变异操作, 不会产生非法解。实验证明当总走行距离较短时, 车辆数一定也较少。

2.2 选择算子

本文利用基于序评价函数进行轮盘赌选择, 其优点是可以离线计算, 从而节约算法执行时间, 并且选择压力可控。

2.3 多种交叉操作

遗传算法交叉操作是遗传算法中最重要的算子, 也是遗传算法的精髓, 它是决定算法能否产生出更优新解的关键环节, 可以说交叉算子的选择对于算法能否找到最优解起决定作用。

在现行的遗传算法中一种交叉方式贯穿算法始终, 由于在整个算法中对解空间搜索的相似性加之选择算子的作用导致大量父代在进化后期趋于一致, 这又与算法要求种群的多样性产生矛盾, 如PMX交叉在进化后期很难找到新解, 使得算法“早熟”收敛。文献[1]提出一种新交叉NPMX方式, 虽然该算子在一定程度上弱化了对种群多样性的需求, 但是这种算子在进化后期, 种群中仍有大量父代趋于一致, 两个相同的父代经这种交叉后又产生两个相同的子代, 例如:

$\begin{array}{l}\text{A}=87|4561|23\\ \text{A}1=|4561|8723\\ \stackrel{}{\to }\\ \text{B}=87|4561|23\\ \text{B}1=|4561|8723\end{array}$

这种交叉方式实际在进行单亲遗传, 但是就产生新解的效率来说不如单亲遗传的方式, 例如同样两个相同的父代:

$\begin{array}{l}\text{A}=87|4561|23\\ \text{A}1=|4561|8723\\ \stackrel{}{\to }\\ \text{B}=8|745612|3\\ \text{B}1=|745612|83\end{array}$

这样会产生两个不同的子代, 扩大了对解空间的搜索范围。但是现行单亲遗传方式也是一种交叉方式贯穿于算法始终, 同样也存在解空间搜索的相似性, 这种相似性在解空间呈“爆炸”状态时, 很难找到全局最优解, 也就是出现早熟收敛的原因之一。为了摆脱这种对于解空间搜索的相似性, 本文引入NPMX交叉和三种单亲交叉方式:PGA1, PGA2, PGA3。在不同阶段进化过程中分别使用三种单亲交叉算子。单亲交叉算子只负责寻找比父代更优的个体, 同时为了使单亲交叉参与到新解空间的探索中, 在循环一定次数后无法找到更优父代个体以一个小概率接受当前产生的个体。现将PGA1、PGA2、PGA3交叉方式说明如下:PGA1算子实际就是NPMX交叉方式进化后期种群中大量父代相同时产生更多新解的单亲交叉方式。PGA2为任意给定一个染色体A随机产生两个交叉点p1, p2 (p1<p2) , 随机产生p3作为p1-p2基因段的移动位置, 当p3∈ (p1, p2]且MAXC-p3+1<p2-p1+1 (MAXC为染色体长度) 即p3的位置应当能放下p1-p2基因段的长度, 将p1-p2基因段放置在p3位置;当p3∈[1, p1) 时移动p1-p2至p3;当p3∈ (p2, MAXC]时p2点与p3对齐, 依次递减放置。具体操作如图1所示。

PGA3采用2-opt领域搜索, 产生新解;引入三个单亲本交叉产生新解, 由于其搜索策略的不同, 避免单一交叉对解空间搜索的相似性。例如表1所示, 说明搜索策略和最优解的结构不同所进行的搜索次数有很大的差异, 利用VC++编程执行20次 (为了比较方便取相同的初始解) 。由该表可以看出初始解相同时, 由于搜索策略和最优解的不同导致搜索次数有很大的差异, 当搜索空间呈“爆炸”式增长时, 所需搜索次数将会有更大的不同, 这样也从另一个角度说明引入不同交叉方式的必要性。

2.4 变异

变异是染色体自发的产生随机变化, 在遗传算法中, 变异可以提供初始种群中不含有的基因, 或者找到选择过程中丢失的基因, 为种群提供新的内容。同时变异算子也是为了遗传算法收敛于更加精确的全局最优解。同样根据交叉分析引入与每种交叉方式对应不同变异算子, 因此, 引入三个变异算子:mutation1, mutation2, mutation3;现对三算子说明如下:mutation1算子为倒位算子。由于PGA1的特点是保留了基因位相邻关系, “倒位变异”就是破坏这种相邻关系搜索到更多的新解。mutation2算子为单点变异即对某一基因点突变, 如图2所示。

mutation3算子为低温退火算子, 在进化后期使用mutation3对个体进行退火操作, 在执行退火时初始温度tk不宜设置太高, 这是因为当温度较低时, SA进行局域搜索, 在进化后期种群中的个体在一定程度上已经逼近全局最优, 局域搜索只是对解进行微调, 考虑到算法效率内层循环数也不宜过大。SA中对新解的产生规则做了如下改进:以较大概率对个体进行“倒位”产生新解, 以较小概率进行2-opt方式产生新解。这样做也是为了避免在退火过程中搜索策略单一和搜索的相似性。降温方法采用降温方程:tk+1=∂tk, ∂=0.95选用零度作业法为终止规则, 即当t小于一个给定的正数ε=0.001时算法终止。同时模拟退火算法在终止时不能保证是本次计算所搜寻到的最优解, 因此加入一个记忆数组s-opt, 每次记录最优解。

3 算法执行步骤

图3为算法流程框架图, 其具体步骤如下:

step1 初始化, 产生初始种群;

step2 如果满足停止条件则输出结果, 计算结束;否则执行以下操作;

step3 计算个体适值, 根据适值排序种群;

step4 如果当前最优解BSF (best_so_far) 适值fit (BSF) 与种群中最佳个体pop[1]的适值fit (pop[1]) 满足fit (BSF) >fit (pop[1]) , 则fit (BSF) =fit (pop[1]) , 无改变代数计数器nl清零, 执行step5;否则直接执行step5;

step5 无改变代数加nl=nl+1;利用轮盘赌选择个体进入新种群;

step6 利用NPMX对种群进行交叉;

step7 判断nl值与进化代数gen的值;

step8 根据step7:如果满足PGA1的执行条件 (本文取nl>=5即5代无改变, gen∈[0, 33]则利用循环执行PGA1 (本文循环10次) , 直到PGA1找到比当前个体更优的解退出循环, 否则以小概率接受当前解 (本文取0.004) ;如果满足PGA2的执行条件, 则执行PGA2 (nl>=10, gen∈[330, 660]) 。否则执行PGA3 (nl>=30, gen∈[660, 1000]) 。继续执行step9;

step9 根据step8执行情况选择变异操作, 如图3所示判断执行;

step10 如果满足则停止计算, 则输出最优解结束;否则转step3。

在step8中对于PGA实际加入了智能交叉[8,9]和以小概率接受当前解的思想, 当某种交叉方式使得无改变次数大于某一值时即出现“早熟”现象, 采用不同交叉策略进行新解空间的搜索, 扩大了解空间的搜索范围。

4 试验及结果分析

本文选取了CVRP问题的4个标准测试数据:A-n32-k5、A-n33-k6、A-n36-k5、A-n39-k6对上述算法与标准遗传算法 (轮盘赌选择、PMX交叉、倒位变异) 进行对比。种群规模取50, 迭代次数1 000, 交叉率取0.95, 变异率取0.004, 退火初始温度取30, 退火速率取0.95, 其他相关参数在算法步骤中已说明, 以下结果均在VC++6.0环境下随机运行20次, 所得最好解如表2所示。

从以上结果可以看出本文在求解上述中等规模的CVRP问题均取得了较好的解, 误差在1.8%以下, 但标准的GA算法求解此类问题误差较大。

为了便于观察本文算法与标准GA算法求解CVRP过程, 本文以求解A-n33-k6的过程为例绘制了, 不同算法当前最优解fit值与进化代数N的关系曲线图 (见图4) 和不同算法随机运行20次所得的结果分布图 (见图5) 。从图4中可以看出标准GA算法在迭代550代左右就收敛了, 再继续迭代也未能找到更好的值。本文算法由于采用了多种交叉策略、变异策略, 在进化前期寻找最优解能力相对较强, 在进化后期由于采用了低温退火策略, 仍然对当前最优解有所改进, 且最终收敛到的解与目前已知最优解的误差较小。图5说明了本文算法相对于标准GA算法, 在20次随机试验中结果比较稳定。

5 结束语

本文对于CVRP问题设计了一种新的混合遗传算法, 算法中加入了多种交叉变异策略, 测试了4个中等规模的国际标准CVRP问题算例, 取得了较满意的解, 并且测试了标准GA算法对于该问题的求解, 测试结果表明本文在求解中等规模的此类问题, 均优于标准GA的算法, 对于今后此类问题的求解可以提供参考。

参考文献

[1]张丽萍, 柴跃廷.车辆路径问题的改进遗传算法[J].系统工程理论与实践, 2002, 8 (8) :79-84.

[2]肖鹏, 李茂军, 张军平, 等.车辆路径问题的单亲遗传算法[J].计算机技术与自动化, 2003, 19 (1) :26-30.

[3]姜昌华, 戴树贵, 胡幼华.求解车辆路径问题的混合遗传算法[J].计算机集成制造系统, 2007, 13 (10) :47-52.

[4]BAKER B, AYECHEW M.A genetic algorithmfor thevehicle routing problem[J].Computers&OperationsResearch, 2003, 30 (5) :787-800.

[5]胡大伟, 朱志强, 胡勇.车辆路径问题的模拟退火算法[J].中国公路学报, 2006, 19 (4) :123-126.

[6]贺国先.现代物流系统仿真[M].北京:中国铁道出版社, 2008:194-275.

[7]汪定伟.智能优化方法[M].北京:高等教育出版社, 2007.

[8]张建彬, 陈抱雪, 隋国荣, 等.智能交叉算子遗传算法的新机制[J].计算机工程与应用, 2009, 45 (32) :35-37.

[9]Hardeberg J Y.Recent Advances in Acquistion and Re-production of Multispectral I mages[C]∥14thEuropeanSignal Proces-sing Conference.Florence, 2006.

混合问题 篇9

一、委托代理问题产生的原因

由于所有者与经营者目标不一致,在企业实际经营中常发生经营者为了自身利益而损害企业所有者即股东权益的问题也即代理问题,一般对代理问题产生的原因有如下解释:

(1)风险收益的不对等。在现代公司制企业中,所有权和经营权相分离,股东作为企业的所有者,对企业享有剩余索取权,并对企业资产经营风险以出资额承担有限责任;而企业并不是由股东直接经营,而是由作为代理人的经理层负责,经理层的收益一般是双方雇佣合同规定的报酬,对企业资产经营风险并不承担责任,这是委托代理问题产生的根本原因。

(2)目标函数的差异性。企业的委托人往往追求利润最大化或者资产的保值增值,即希望以最小的代理成本获取资产增值的最大化。而代理人则追求个人尽可能多的货币与非货币收益,及自身收益的最大化。代理人还往往追求企业规模的最大化,这不仅因为经理人员的报酬在实际上与企业规模呈正相关关系,而且是因为规模的扩大本身所带来的权利和地位的提高。

(3)信息不完全和信息不对称。信息不完全不仅是指那种绝对意义上的不完全,即由于认识能力的限制,人们不可能知道在任何时候、任何地方发生任何情况,而且是指“相对”意义上的不完全,即市场经济本身不能够生产出足够的信息并有效地配置它们。信息不完全在委托代理问题中具体表现为契约的不完全性,即由于信息不完全委托人和代理人签订契约时,不可能预见将来发生的一切,从而将所有可能出现的问题都包括在契约条款之中,给经理人以可乘之机。信息不对称是指委托人和代理人对企业经营的相关信息的了解和掌握程度是不对等的。在现代企业中,由于企业由代理人直接经营,相对于委托人,代理人拥有更充分的信息,代理人就有可能利用这一优势对委托人进行隐瞒和欺诈,从而产生“道德风险”,损害委托人的利益。

(4)委托人对监督成本的控制。委托人对代理人行为进行监督,能降低代理问题产生的概率,但是这要产生监督成本。特别是在现代大型股份公司里,由于股权比较分散,股东人数较多,股东通过协商采取一致行动的成本高昂,广大中小股东对公司的影响有限,从而采取消极“搭便车”的行为,如果对单个股东来说由监督产生的成本大于他个人从监督行为中获得的利益,那么他就会对经理人采取不监督的行为,从而变相鼓励了代理问题的发生。

二、委托代理问题的博弈模型

由于所有者(股东)与经营者(董事会、经理)之间是一种委托代理关系,代理人的行为目标与委托人的行为目标常常是不一致的。所有者所要求的是股东权益的最大化,而经营者所追求的是自身利益的最大化,他很有可能利用在公司的地位和职权为自己谋取私利。如果经营者认为在追求自身利益最大化时,股东的监督使其收益与损失之差要小于他以股东权益最大化为目标而得到的收益时,就会以股东权益最大化为他的行为目标。否则,他就会违背诚信原则或敬业禁止原则以谋取私利。

本模型在参考其他模型的基础上,细化了在不同策略下博弈双方所获支付的构成因素,把股票市场作为影响模型的参数之一。在模型中,所有者有两种策略:监督和不监督;相对应的经营者也有两种策略以股东利益最大化和以自身利益最大化。设W为经营者固定工资(常数);P为股票价格(P1为经营者以股东权益最大化为目标时的股价;P2为经营者以自身利益最大化为目标时的股价;假设P1>P2);F(P)为经营者所得奖金;N为总股数;C为所有者监督经营者所需成本;U为经营者利用职权谋取的私利,或称内部人收益,这种收益实际上就是股东的损失称为代理成本;为经营者在追求自身利益最大化时受到股东的处罚;d为每股收益额(d1为经营者以股东权益最大化为目标时的每股收益;d2为经营者以自身利益最大化为目标时的每股收益;假设(d1>d2)。所有者与经营者的得益矩阵见下表,前者是经营者不同策略下的支付,后者为所有者在不同策略下的支付:

根据博弈理论,在这个博弈中不存在纯策略的纳什均衡,分析如下:

(1)当经营者选择以自身利益最大化为目标时,所有者选择监督。因为监督成本要小于代理成本即CNd2-U。

(2)当所有者监督时,经营者选择以股东利益最大化为目标。因为值较大,惩罚要大于谋私所得,所以

(3)当经营者以股东利益最大化为目标时,所有者选择不监督。因为Nd1>Nd1-C。

(4)当所有者不监督时,经营者选择以自身利益最大化为目标。因为W+F(P2)+U>W+F(P1)。

如此循环,没有一个组合构成纯策略的纳什均衡。但是,考虑所有者、经营者随机选择不同策略的概率分布,则该博弈存在一个混合策略的纳什均衡。

所以,所有者选择监督的概率一定要使经营者选择以股东权益最大化为目标和以自身利益最大化为目标的期望得益相等。

同样地,经营者选择以股东权益最大化为目标的概率一定要使所有者选择监督的期望得益与选择不监督的期望得益相等。

因此,该博弈的混合策略的纳什均衡是所有者以+*的概率选择监督,经营者以,*的概率选择以股东权益最大化为目标。

三、对混合策略纳什均衡的分析

现代公司治理的本质是要解决因所有权和经营权相分离而产生的代理问题,降低代理成本,使经营者追求股东利益最大化,最终实现股东财富增值的公司经营目标。同时由于所有者对代理人进行监督,会产生成本,该成本构成代理成本的很大一部分。所以对前面委托人和经营者通过博弈得到的混合策略纳什均衡的均衡解进行分析,就可以得出在本模型中公司治理的目标:一是减低所有者的监督成本,即均衡解-*越小越好;另一个是使经营者以股东利益最大化为目标的概率越大越好,即.*越大越好。

首先,要使所有者选择监督的概率/*变小,意味着要使经营者追求自身利益最大化的成本0上升,而收益F(P2)-F(P1)+U变小。要使U变小,公司内部必须建立一套完善和严密的监督和审计机制,使董事会、监事会、经理层三者的权利相互制衡和约束,减低代理人利用职权谋取私利的概率和数量;F(P2)-F(P1)变小,意味着企业外部必须有一个高效完善的证券市场,使企业的经营效率能直接反映到公司的股价上,同时在公司内部必须建立有效的激励机制,使经理层的报酬与公司的股价和公司经营效率直接挂钩;要使!上升,则一方面在公司内部要制定对以权谋私的经理人进行惩罚的严厉措施,另一方面则要不断发展完善经理人市场和企业控制权市场,通过外部控制加大经营者以自身利益最大化从而损害股东利益行为的成本。这一套成本收益方法的作用,在于对代理人违规行为进行事前警戒和事后处罚,但更重要的是事前警戒,要想达到这样的效果,就必须有完善的相关信息收集和传播渠道,是经理人对其行为产生的成本收益处于完全信息的状态,从而减少代理问题的发生。

其次,因为"*可变形为,所以要使%*变大,意味着C变小,&变大,也就是所有者的监督成本和经营者由股东处罚造成的成本的比比小。对于经理层的违规成本(,在分析)*是已作解释,这里不作重复。要想降低所有者对经营者的监督成本C,除了建立有效的公司治理机制,使其内部监督机制、激励机制、决策机制有效运转外,对外则要制定完善的法规法律体系,发挥产品市场、资本市场和经理人市场等公司外部治理机制的作用。

总之,公司治理结构的有效运转,需要资产诸方面权力在分离的状态中,能够保持有效的约束及监督,建立有效地内部和外部治理机制,使诸方面资产权力的掌握及运用严格受到相应资产责任的制约,从而达到诸方面利益的均衡,以保证效率的提高。具体来说就是降低所有者的监督成本,同时要提高经营者的违规成本,减少其因违规得到的收益。使所有者有动力并且有能力充分履行其对经营者的监督职能,使经营者在一套完善的权力监督和制衡机制下,能够基于成本和收益的考虑,降低经营者为追求自身利益而损害股东权益的行为发生的概率。

参考文献

[1]谢识予.经济博弈论(第二版)[M].上海:复旦大学出版社,2002.

[2]戴志敏,刘华.公司治理结构中的博弈分析[J].数量经济技术经济研究,2002,(2).

[3]朱文莉,柳艳丽.公司治理结构中内部人控制的博弈分析[J].商场现代化,2007,(3).

[4]吴延兵.公司治理结构的产生与模式——从博弈角度进行的分析[J].山西财经大学学报,2005,(6).

[5]戴芸,徐强.从博弈看国有股减持[J].商业研究,2003,(5).

混合问题 篇10

旅行商问题是一个典型的、易于描述却难于处理的组合优化问题,并且是一个NP难问题。而蚂蚁算法和遗传算法都是解决复杂问题的有效方法,都广泛应用于解决旅行商问题。

遗传算法的优点是将问题参数编码成染色体后进行优化,而不针对参数本身,从而不受函数约束条件的限制;同时具有隐含并行搜索特性,可大大减少陷入局部最小的可能。其主要缺点是对于结构复杂的组合优化问题,搜索空间大,搜索时间比较长,往往会出现早熟收敛的情况; 对初始种群很敏感,初始种群的选择常常直接影响解的质量和算法效率[1]。

蚂蚁算法不仅利用了正反馈原理,在一定程度上可以加快进化过程,而且是一种本质并行的算法,个体之间不断进行信息交流和传递,有利于发现较好解。单个个体容易收敛于局部最优,但多个个体通过合作,很快收敛于解空间的某一子集,有利于对解空间的进一步探索,从而不易陷入局部最优。但是蚁群算法也具有速度慢、易陷入局部最优等缺点。蚁群中多个个体的运动是随机的,当群体规模较大时,要找出一条较好的路径需要较长的搜索时间[2]。

遗传算法与蚂蚁算法的融合,其基本思想是汲取两种算法的优点,克服各自的缺陷,优势互补,在时间效率上优于蚂蚁算法,在求解效率上优于遗传算法,是时间效率和求解效率都比较好的一种新的启发式方法。基于上述思想,PilatML[4],丁建立[5],邵晓巍[6]等采用GA对蚁群算法中的参数进行优化。

1 蚂蚁算法的优化原理和模型描述

蚂蚁有能力在没有任何提示下找到从其巢穴到食物源的最短路径,并且能随环境的变化而变化,适应性地搜索新的路径,产生新的选择。其根本原因是蚂蚁在寻找食物源时,能在其走过的路上释放一种特殊的分泌物——信息素(随着时间的推移该物质会逐渐挥发),后来的蚂蚁选择该路径的概率与当时这条路径上该物质的强度成正比。当一定路径上通过的蚂蚁越来越多时,其留下的信息素轨迹也越来越多,后来蚂蚁选择该路径的概率也越高,从而更增加了该路径的信息素强度。而强度大的信息素会吸引更多的蚂蚁,从而形成一种正反馈机制,通过这种正反馈机制,蚂蚁最终可以发现最短路径。

下面就以TSP问题为例来说明蚂蚁算法[3]。设有n个城市组成的集合c,蚂蚁数目为m,用dij(i,j=1,2,…,n)表示城市i和城市j之间的距离,

τij(t)表示在时刻t城市i和城市j之间的路径上的信息素量,以此来模拟实际蚂蚁的分泌物。蚂蚁k(k=1,2,…,m)在运动过程中,根据各条路径上的信息量决定其转移方向,同时用禁忌表tabuk(k=1,2,…,m)来记录蚂蚁k当前所走过的城市,集合随着蚂蚁所走过的城市作动态调整。在搜索过程中,蚂蚁根据各条路径上的信息量及路径的启发信息来计算状态转移概率。p${}_{ij}^k$(t)表示在t时刻蚂蚁k由城市i转移到城市j的状态转移概率,其表达式为:

$p{}_{ij}^k(t)=\{\begin{array}{cc}\frac{\tau {}_{ij}^{\alpha }(t)\eta {}_{ij}^{\beta }(t)}{{\displaystyle \sum _{s\in allowed{}_k}\tau }{}_{is}^{\alpha }(t)\eta {}_{is}^{\beta }(t)}‚& j\in \text{a}\text{l}\text{l}\text{o}\text{w}\text{e}\text{d}{}_k\\ 0& \text{o}\text{t}\text{h}\text{e}\text{r}\text{w}\text{i}\text{s}\text{e}\end{array}$

其中:$allowed{}_k=\{1‚2‚\cdots n\}-tabu{}_k$表示蚂蚁k下一步允许选择的城市;α和β分别表示信息素和启发式因子的相对重要程度,ηij表示边(i,j)的能见度,反映由城市i到城市j的启发程度,这个量在蚂蚁的运行中不改变,通常取城市i和城市j之间距离的倒数。当所有蚂蚁完成一次周游以后,各路径上的信息素根据下式进行更新:

τij(t+n)=ρ*τij(t)+${\displaystyle \sum _{k=1}^m}$Δτ${}_{ij}^k$ (1)

(其中ρ表示信息残留系数,1-ρ表示信息挥发系数。)

蚁圈模型是被证明的全局优化较好的蚂蚁算法,关于Δτ${}_{ij}^k$的计算,其表达式为:

$\Delta \tau {}_{ij}^k=\{\begin{array}{l}Q/L{}_k\text{若}\text{蚂}\text{蚁}k\text{在}\text{本}\text{次}\text{循}\text{环}\text{中}\text{经}\text{过}\text{边}(i‚j);\\ 0,\text{否}\text{则}。\end{array}$

其中Q表示的是信息素的强度,为常数,Lk表示蚂蚁k在本次循环中所走路径的总长度。

2 基于改进交叉算子的蚁群算法

交叉运算是产生新个体的主要方法,它决定了遗传算法的全局搜索能力,传统针对TSP 问题的遗传交叉算子,如部分影射交叉、顺序交叉、循环交叉、基于位置的交叉、基于顺序的交叉等,他们都存在两个缺点,或者交叉后的子代不能很好地保留父代的优秀基因,或者子代需要做些改动才是可行的。本文在文献[7]的基础上采用精英策略进行交叉,在父代中找最好的两个染色体进行交叉,增大子代为较优解的可能性。以下给出的交叉算子[8]可以使交叉后的子代保证可行性的同时,并很好地继承了父代的优秀基因:

假设有n个城市1,2,…,n,染色体编码成为推销员所经过的城市顺序号。现在有待交叉的双亲: x1=(r11,r12,…,r1n) x2=(r21,r22,…,r2n),遗传交叉的主要目的是子代尽可能地继承父代的优秀基因。把上述染色体看成一个环,即r1n的下一个城市r1n+1=r11;根据贪婪法的思想,设计交叉步骤如下:

1) 假定当前城市r1c=r11,从x2中找到r2k=r1c,并把r1c加入子代。

2) 若r1c+1和r2k+1都不在子代中,比较d(r1c,r1c+1)和d(r2k,r2k+1),若前者大,则记当前城市r1c=r2k+1,否则记当前城市r1c=r1c+1。

3) 从x2中找到r2k=r1c,并把r1c加入子代。

4) 若① r1c+1已经在子代中,而r2k+1不在子代中,记当前城市r1c=r2k+1,并加入到子代; ② r2k+1已经在子代中,而r1c+1不在子代中,记当前城市r1c=r1c+1,并加入到子代;③ r1c+1和r2k+1 都在子代中,比较d(r1c,r1c+2)和d(r2k,r2k+2)。

5) 重复步骤2),直到完整生成子代。

变异方法:本文采用倒位变异方法;对于(1,2,3,4,5),随机产生两数2和5,则变异后就为(1,5,4,3,2),如果产生的后代比父代差,则取父代作为最优解。

3 混合蚂蚁算法流程

步骤1 参数初始化。令时间t=0,循环次数nc=0,设置最大初循环次数ncmax,信息素Q,将m只蚂蚁置于n个城市组成的集合C中,初始化信息量τij(t)为τmax

步骤2 循环次数nc=nc+1;

步骤3 蚂蚁的禁忌表索引号k=1;

步骤4 蚂蚁数目k = k+1;

步骤5 蚂蚁个体根据状态转移式计算的概率选择城市j并前进,修改禁忌表指针,将蚂蚁移动到新的城市,并把该城市移动到该蚂蚁个体的禁忌表中;

步骤6 经过n个时刻,蚂蚁k可走完所有的城市,完成一次循环,计算蚂蚁k走的总路径长度;

步骤7 若k≤m,则跳转到步骤4,否则执行步骤8;

步骤8 按照精英策略选出本次循环中的最优路径和次优路径,按照交叉算子中的方法进行交叉运算,并保留最优路径,记其为L;

步骤9 按照文中方法进行变异运算,并保留最优路径;

步骤10 按照(1)更新每条路径上的信息量;

步骤11 若满足结束条件,即如果循环次数nc>ncmax,则循环结束并输出程序计算结果,否则清空禁忌表并跳转到步骤2。

4 实验结果

本次实验采用matlab6.5对st70.tsp进行计算,蚂蚁数和城市数量大致相同,采用参数为ncmax =1 000,α=1,β=5,ρ=0.9,Q=100,交叉概率为0.8,变异概率为0.2,所得最短路线为679.747 3,而官方最优解为675。同时对eil51.tsp进行多次计算,得出最优路径为430.224 7,而官方最优解为426。从实验来看,本文的算法效果还是比较明显。

摘要：介绍了一种求解旅行商问题的混合蚂蚁算法,该算法结合了遗传算法中的改进的交叉算子和变异算子,对产生的局部最优解进行适当地交叉和变异,提高算法的搜索空间,可以提高蚁群算法的寻优能力,实验表明该算法很有效。

关键词：蚂蚁算法,遗传算法,旅行商问题,交叉算子

参考文献

[1]王凌智能优化算法及其应用.北京:清华大学出版社,2001;154—159

[2]Dorigo M,Maniezzo V,Colomy A,The ant system:optimization by a colony of cooperating Agents.IEEE Transactions on systems,Man,And Cybernetics-PartB,1996;26(1):29—41

[3]Dorigo M,Gambardella L M.Ant colony system:a cooperative leam-ing approach to the traveling salesman problem.IEEE Tronsocrions on Evolutioionog Compulolion,1997;1(1):53—66

[4]Pilat M L,White T.Using genetic algorithms to optimize ACSTSP.Brussels,Belgium:Proceedings of3rd International Work-shop on ant Algorithms/ANTS2002,LNCS,2002;282—287

[5]丁建立,陈增强,袁著祉.遗传算法与蚂蚁算法的融合.计算机研究与发展,2003;40(9):1351—1356

[6]邵晓巍,邵长胜,赵长安.利用信息量留存的蚁群遗传算法.控制与决策,2004;(10):1187—1189

[7]刘立东,蔡淮.融入遗传算法的混合蚁群算法.计算机工程与设计,2008;(5):1248—1252