Frank-Wolfe�㷨��⽻ͨ��������: �Ƚϲ�ͬ�������²��Ժ�����������

Frank-Wolfe(FW)算法是一类广泛应用于求解交通分配问题的算法。它具有容易编程实现,所需内存少的特点。但是该算法收敛速度较慢,不能得到路径信息。为了提高算法的效率,本文研究三种流量更新策略(all-at-once, one-origin-at-a-time, one-OD-at-a-time)以及不同的步长搜索策略下的FW算法,其中步长搜索策略包括精确线性搜索方法(包括二分法、黄金分割法、成功失败法)和不精确的线性搜索方法(包括基于Wolfe-Powell收敛准则的搜索方法和Gao等提出的非单调线性搜索方法)。最后,本文将上述策略应用于四种不同规模的交通网络中,并给出较适合求解的组合。     

第Ⅰ类双边装配线平衡问题的改进蚁群算法

为克服传统算法求解大规模双边装配线平衡问题计算时间长、性能不稳定的缺陷,针对第Ⅰ类双边装配线平衡问题,应用综合信息素搜索规则与全局信息素更新规则,提出了一种先产生任务排列序列、后按启发式分配规则产生可行解的蚁群算法,可有效脱离陷入局部最优解.用改进蚁群算法对30个不同规模的问题进行求解,并与标准蚁群算法和禁忌搜索算法进行了对比.结果表明:改进蚁群算法求出29个最优解,比普通蚁群算法、禁忌搜索算法分别能多求得6个和3个最优解;应用于汽车双边装配线算例,在保持平衡效率的条件下,改进蚁群算法计算时间为21.01 s,比普通蚁群算法减少了9.14 s,计算效率提高了30.3%.      

Local Search Algorithm with Hybrid Neighborhood and Its Application to Job Shop Scheduling Problem

A new local search method with hybrid neighborhood for Job shop scheduling problem is developed. The proposed hybrid neighborhood is not only efficient in local search, but also can help overcome entrapments while search procedure get trapped at local optima and carry the search to areas of the feasible set with better prospect. New strategies used for breaking out of entrapments are presented and they are helpful for the procedure to improve local optima. A performance comparison of the proposed method with some best-performing algorithms on all 10-job, 10-machine benchmark problems and the other two problems generated by Fisher and Thompson ( ie. , FT6 and FT20) is made. The experiment results show the better optimal performance of the proposed algorithm.     

基于改进蚁群算法的多AGV泊车路径规划

针对智能停车库中自动导引小车(Automated Guided Vehicle,AGV)存取车的路径规划问题,提出一种基于改进蚁群算法的多AGV泊车路径规划方法.单AGV路径规划方面,在基本蚁群算法基础上引入蚂蚁回退策略来增强适应性,同时改进启发式信息和信息素更新策略提高算法的收敛速度和寻优能力.多AGV路径规划方面,提出改进冲突解决策略来解决多AGV之间的冲突,其中采用临时规避-重新寻路策略来解决相向冲突.针对某典型停车场抽象模型的仿真结果表明,改进蚁群算法寻路成功率更高,并具有较强的全局搜索能力和较快的收敛速度,改进冲突解决策略能合理避免冲突,可以满足多AGV存取车路径规划的要求.     

Hybrid Optimization Algorithm Based on Wolf Pack Search and Local Search for Solving Traveling Salesman Problem

Traveling salesman problem(TSP) is one of the typical NP-hard problems, and it has been used in many engineering applications. However, the previous swarm intelligence(SI) based algorithms for TSP cannot coordinate with the exploration and exploitation abilities and are easily trapped into local optimum. In order to deal with this situation, a new hybrid optimization algorithm based on wolf pack search and local search(WPS-LS)is proposed for TSP. The new method firstly simulates the predatory process of wolf pack from the broad field to a specific place so that it allows for a search through all possible solution spaces and prevents wolf individuals from getting trapped into local optimum. Then, local search operation is used in the algorithm to improve the speed of solving and the accuracy of solution. The test of benchmarks selected from TSPLIB shows that the results obtained by this algorithm are better and closer to the theoretical optimal values with better robustness than those obtained by other methods.     

面向时变需求的高速铁路列车开行方案优化方法

为了使高铁列车开行方案与旅客时变需求相吻合,引入列车运行方案图,使列 车开行方案优化中既能利用列车运行的时间信息,又能避免结合列车运行图综合优化的 大规模计算.借助于基于时刻表的高铁客流分配方法,在区间通过能力、车站始发能力、列 车载客能力等多种约束下,以列车运行时间与旅客出行时间加权和为优化目标,构建了 时变需求下高铁列车开行方案优化的Stackelberg 博弈模型.利用降低编组、删除列车、添 加列车、拼接列车、提高编组和调整列车始发时间等邻域搜索策略,设计了求解模型的模 拟退火算法.最后,针对京沪高速铁路进行算例分析,优化产生的列车开行方案具有良好 的评价指标,特别是旅客上车时间与计划出发时间的偏差较小,具有较高的运算效率和 收敛性.     

铁路集装箱中心站多轨道吊柔性协同调度优化

针对铁路集装箱中心站轨道吊协同装卸调度(RMGCS)问题，考虑多轨道吊间的作业干涉和安全距离约束，建立目标函数为最小化集装箱完工时间的混合整数规划数学模型。结合 RMGCS问题特性，提出一种考虑多轨道吊柔性协同作业的改进麻雀搜索算法(ISSA)，首先，提出能够解决多轨道吊间作业冲突的任务分配策略和干涉判断方法；其次，设计自适应非线性动态安全值，平衡全局和局部搜索；再次，改进加入者更新移动方式，使其在全维度上靠近最优解；最后， 引入LOV(largest-order-value)规则，将个体从实数向量映射到集装箱整数序列。为了验证问题和算法的有效性，分别利用ISSA与其他算法求解不同样本规模的算例，结果表明：ISSA在不同样本 规模的RMGCS问题求解上，均具有更好的寻优效果。此外，所提出的柔性协同调度模式相比现有的固定范围顺序装卸调度模式，使样本量为45的装卸作业总完工时间缩短了15.5%。     

有限理性下个体出发时间选择行为研究

个体受限于认知能力和逻辑推理能力的限制,在出行决策过程中很难做到完 全理性.本文以出发时间选择为例,在有限理性行为假设基础上,引入空间知识获取、学习 及认知更新和方案搜索等关键行为要素,构建有限理性下的出行决策过程理论框架.融合 RP和SP 调查方法,设计出发时间选择行为意向调查方案.研究个体知识的表达方式,应 用贝叶斯学习理论完成认知更新.定义搜索成本和收益函数,利用调查数据分别提取基于 PART 和RIPPER 算法的出发时间启发式搜索规则和决策规则.结果表明,有限理性下个 体出发时间选择行为存在感知阈值,而并非寻求全局最优解.     

一种求解Job-Shop调度问题的快速禁忌搜索算法

介绍了一种解决Job-Shop调度最短完工时间的有效的快速禁忌搜索算法,该算法首先利用插入算法构造尽可能好的初始解,然后使用禁忌搜索算法改进当前解,用基准实例进行仿真,实验结果表明该算法是可行的和有效的.     

集装箱船舶装箱排序问题的两阶段算法

集装箱船舶装箱排序问题综合集装箱装船顺序与船舶贝内排箱,是一类典型的组合优化问题.考虑堆场发箱顺序和船舶配载之间的关联,构建集装箱船舶装箱排序问题的数学模型.针对构建的优化模型,鉴于已有方法难以直接对其进行求解,基于两阶段分层求解思想设计SWO-HES两阶段算法.算法第1阶段利用吱呀轮算法(SWO)大邻域导向式搜索的特点优化集装箱装船顺序问题;第2阶段将SWO的结果作为输入,基于启发式规则和演化策略算法(ES)构造混合演化策略算法(HES)优化船舶贝内排箱问题.最后,通过不同规模算例的研究,将SWO-HES与常见智能算法、基于实际装船规则的启发式算法进行对比分析,验证模型与算法的有效性.     

Sensitivity Analysis of Simulated Annealing for Continuous Network Design Problems

In this paper, parameters choices of simulated annealing for continuous network design problems are discussed. A bi-level programming model for continuous network design problem is introduced. Objective function of the upper level is defined as the sum of the total travel time on the network and the total investment costs of link capacity expansions. The lower level problem is the user equilibrium assignment model, which is solved by the Gradient projection algorithm. Sensitivity analysis method is the first time used to analyze and compare the influence of the different selection of parameters to the implementation of simulated annealing algorithm. Suggestions of parameter selection are also given. Analysis demonstrates that the efficiency and precision of these methods can be improved clearly with the proposed suggestions.     

�������������������ģ���˻��㷨�����ȷ���

研究了求解城市交通连续网络设计问题的模拟退火算法参数选择原则。采用双层规划模型来描述固定需求下的城市交通连续网络设计问题,其中上层问题的目标函数为整个网络的总阻抗和总投资额之和,下层问题则是用户平衡配流模型。利用模拟退火算法求解上层模型,下层模型则采用基于路径的GP算法进行求解。本文首次采用了灵敏度分析方法分析参数选择对模拟退火算法求解连续网络设计问题影响,比较了各个参数对算法结果及时间的影响,确定了参数的选择原则。根据上述分析方法得到的参数选择原则来设定参数的取值,能够提高算法的执行效率和收敛精度。     

IIR数字滤波器设计的搜寻者优化算法

为进一步提高无限冲击响应(IIR)数字滤波器的性能,提出了一种基于搜寻者优化算法(SOA)的IIR数字滤波器设计方法.SOA基于模拟人的随机搜索行为,由利用位置变化评价得到的经验梯度确定搜索方向,由采用简单模糊规则的不确定性推理确定搜索步长,通过搜寻者在搜索空间的位置更新,实现对优化问题的求解.2个典型设计实例的仿真结果表明,与差分进化算法(DE)和3种改进的粒子群算法(PSO)相比,SOA具有较好的全局寻优能力和较快的收敛速度,能有效地应用于IIR数字滤波器的没计.     

多人共站第一类混流装配线平衡问题的优化

针对使用传统模型和算法求解第一类多人共站混流装配线的平衡问题，兼顾工作站数、工人数和工作站负荷均衡，引入了新变量和不对称约束来构建新的数学模型. 提出了一种改进的鸡群算法，使用基于优先权值的编码方式在解码过程中优先选择能最早开始作业的工人来减少序列相关空闲时间，设定工位分配接受准则来分配工人数量以减少工位平均空闲时间；根据适应值大小将种群分为3个不同的群体来实现系统的有效搜索，其中，公鸡群个体基于其适应值差异在不同大小的邻域范围内搜索，母鸡群个体基于适应值相关的参数分别向所归属的公鸡或者其他公鸡/母鸡方向搜索，小鸡群个体则向其归属的母鸡方向搜索；最后将新模型和改进的鸡群算法用于求解标杆算例. 研究结果表明:在算例验证中，对比传统的模型，新模型多找出8个算例的最优解，且寻优速度更快；在算法平均收敛运算时间相似的情况下，本文所提算法求得的平均工人数、工位数以及平滑指标系数等评价指标分别提高了10.74%、16.05%和44.89%，验证了所提模型和算法的有效性和优越性.      

舰船电力系统潮流计算方法

根据舰船电力系统的特点,在比较陆用电力系统各种潮流计算方法的基础上,提出了适合于舰船电力系统的潮流计算方法.该方法从回推/前推算法出发,利用解环点处电流补偿技术处理弱环网运行状态,采用PV节点电流补偿技术解决系统多源问题,最终得到舰船电力系统潮流统一计算流程.文中给出了计算实例.     

考虑时空热度的共乘匹配问题建模及求解

在共乘匹配问题中，考虑时空热度对共乘车主收益的影响，构建了以共乘收益和共享路线百分比为优化目标的数学模型，提出了一种启发式多进程进化算法用于求解. 算法根据历史数据采用三次样条插值法和复合辛普森求积法得到预计订单的时空热度，从而预估车主共乘收益. 在进化算法中，根据差异度自适应选择不同的交叉策略，以达到搜索深度和广度的自动平衡. 实验结果表明，该算法与最优化算法(匈牙利算法)比较，在以相同效用矩阵作为输入条件时，本文方法可在较短时间内得到高质量的解，且在处理大规模实例上效果明显，能够高效求解共乘匹配问题.     

3D human motion tracking by using interactive multiple models

Of different model-based methods in vision based human tracking, many state of the art works focus on the stochastic optimization method to search in a very high dimensional space and try to find the optimal solution according to a proper likelihood function. Seldom works perform a framework of interactive multiple models (IMM) to track a human for challenging problems, such as uncertainty of motion styles, imprecise detection of feature points and ambiguity of joint location. This paper presents a two-layer filter framework based on IMM to track human motion. First, a method of model based points location is proposed to detect key feature points automatically and the filter in the first layer is performed to estimate the undetected points. Second, multiple models of motion are learned by the prior motion data with ridge regression and the IMM algorithm is used to estimate the quaternion vectors of joints rotation. Finally, experiments using real images sequences, simulation videos and 3D voxel data demonstrate that this human tracking framework is efficient.     

考虑时空热度的共乘匹配问题建模及求解

在共乘匹配问题中,考虑时空热度对共乘车主收益的影响,构建了以共乘收益和共享路线百分比为优化目标的数学模型,提出了一种启发式多进程进化算法用于求解. 算法根据历史数据采用三次样条插值法和复合辛普森求积法得到预计订单的时空热度,从而预估车主共乘收益. 在进化算法中,根据差异度自适应选择不同的交叉策略,以达到搜索深度和广度的自动平衡. 实验结果表明,该算法与最优化算法(匈牙利算法)比较,在以相同效用矩阵作为输入条件时,本文方法可在较短时间内得到高质量的解,且在处理大规模实例上效果明显,能够高效求解共乘匹配问题.     

基于等高线特征的三维地形造型技术研究与应用

讨论了基于矢量化的等高线生成数字高程模型（Digital Elevation Map）的方法,并在此基础上进行了三维建模,实现了等高线的三维可视化,本文以线性内插为基础,采取了简化的基于等高线特性的内插方法,并提出了一种等高线的快速搜索方法,该算法通过软件实现,已应用在铁路电力架空线路辅助设计系统中．     

基于OpenMP的并行遗传算法求解SAT问题

为了提高SAT （boolean satisfiability） 问题求解效率,在OpenMP （open multi-processing） 编程框架下,将遗传算法与局部搜索算法结合,改进了混合遗传算法中的选择算法,将原有选择操作的时间复杂度降低到O(N)级别. 算法采用OpenMP中的编译制导语句#pragma omp parallel粗粒度并行化驱动混合遗传算法,采用#pragma omp single语句块实现了子种群间个体的同步迁移操作. 与同类算法HCGA （hybrid cloud genetic algorithm）比较分析表明:改进算法HGA （hybrid genetic algorithm）以及并行后的混合遗传算法CGPHGA （coarse-grained parallel hybrid genetic algorithm）在求解成功率和求解效率上都有显著提高,部分问题求解成功率提高达5倍.