一种求解协作配送成本分摊问题核仁解的近似迭代算法

协作配送问题是典型的组合优化合作博弈问题,也可称为协作车辆路径问题,其核心问题之一是确定公平合理的成本分摊方案.其中核仁解由于具有唯一性和公平性等特点,是成本分摊领域中公认的科学分摊方案.本文提出了一种近似求解协作配送问题核仁解的方法.首先分析证明了当顾客位置分布均匀,从理论上协作配送成本分摊问题会是凸博弈问题,然后,基于凸博弈的核仁解会等同于预内核解的理论,提出了一个能够求解凸博弈问题核仁解的迭代逼近算法(approximate iterative algorithm,AIA),分析了AIA算法的复杂度为O(n~42~n),为此又提出了AIA的有效提速策略,可将AIA的复杂度降低至多项式.最后,通过求解协作配送算例和实例,验证了本文AIA算法能够准确求解得到协作配送成本分摊问题的核仁解,提出的求解策略能有效的减少求解耗时,并且得到的最终结果与实际核仁解的平均偏差不到0.02%,更重要的是AIA能够用于求解所有凸博弈问题的核仁解.     

0/1背包问题快速降价法及其应用

用数学方法分析了0/1背包问题的特性,提出了一个快速降价算法,该算法能成批确定一定在最优解中的物品和成批排除一定不在最优解中的物品。该算法既可单独使用,又可与启发式算法结合达到更好的结果。文中给出了应用实例及其分析。     

基于蚁群优化算法的0-1背包问题求解

蚁群优化算法在求解旅行商问题、指派问题、Job-shop调度问题和网络路由问题等获得了极大的成功．将蚁群优化算法应用于0—1背包问题，首先将0—1背包问题表示成相应的构造图，并针对该图设计了两个状态转移公式，蚂蚁根据这两个状态转移公式在带权图中移动直到死亡．此时，蚂蚁所走过的路径即构成背包问题的一个可行解．仿真实验对该算法的参数进行了讨论，再与遗传算法进行比较，结果显示该算法具有较高的性能．     

双尺度变异离散粒子群算法求解背包问题

针对传统离散粒子群算法求解背包问题早熟收敛、精度低等缺点提出一种解决背包问题的双尺度变异离散粒子群算法.利用对当前最优解进行双尺度速度变异,可以实现提高算法局部最优解搜索能力的同时,保持算法的全局搜索能力和逃出局部极值的能力.在算法初期利用粗尺度速度变异可使粒子快速定位到最优解区域,算法后期则通过逐渐减小的细尺度变异可提高算法最优解的精度.粒子位置初始化过程中,把采用贫心策略所得的结果作为一个粒子的初始位置.将改进算法与其他算法比较证明该算法不仅能够有效解决其他算法搜索能力差的问题,同时还提高了最优解的精度和收敛速度.     

伪凸二次规划的最优解集

寻找数学规划问题的多个最优解乃至最优解集是一项有理论价值和实践意义的工作,因为决策者可以从多个最优解中挑选其满意的最佳方案。然而,目前有关寻求非线性规划问题多个最优解的研究还比较少见且存在局限性。研究了伪凸目标函数的二次规划问题,首先提出和证明了最优解集的特征,然后借助于求解带有人工变量的辅助线性规划全部最优解的方法,提出了伪凸二次规划有唯一最优解的条件,并在不满足该条件的情况下,通过寻找辅助线性规划的最优解集以获得伪凸二次规划的最优解集。最后给出了两个算例以说明方法的有效性。     

带振荡策略的启发式算法求解一类新型分配问题

提出了一种新型的分配问题,该问题来源于钢铁企业中的板坯优化管理.与一般分配问题相比,该问题在将物品分配给背包时,除了需满足背包的容量限制外,还需满足流向限制.此问题可归结为 一般分配问题,因此为NP难问题.针对该问题,提出了带有振荡策略和长期表的启发式算法求解.振荡策略使局部搜索算法在可行区域和不可行区域间振荡,以获得更好的近优解;其次,在算法中引入了禁忌搜索的长期表,根据频率鼓励物品的多样性移动,提高算法的分散搜索能力.为验证算法有效性, 对随机产生的23种规模的数据进行了实验.实验结果表明：对于小规模数据,算法结果与最优解的最大偏差为0.55{\%};在大规模情况下,算法能在快速的时间内获得问题的近优解.     

一种新的优化方法:β算法

提出了一种新的求解全局最优问题的算法。该算法适合求解非线性、非凸、包含多个局部最优解的最优化问题,且对所求解的问题没有很强的前提条件,适用范围宽广,该算法利用了目标函数超曲面在可行域中的起伏,对可行域进行分割压缩,并最终收敛于某个全局最优解。最后通过实例与模拟退火算法进行了比较,检验了其优异的鲁棒性和收敛速度。     

复杂物体连续碰撞检测动态投影分离剔除算法

针对复杂物体间碰撞检测,为提高碰撞检测效率,减少计算量,解决普通算法不直接适用于非凸体等问题,提出了一种连续碰撞检测算法。首先,该算法在初检测阶段利用基于波前法的三角网格生成,对非凸体等复杂物体表面进行网格划分,获取高质量三角形,得到三角形点、线、面参数信息;然后,用动态投影分离剔除法对三角形单元对进行高层剔除,从而剔除掉不可能发生碰撞的三角形;最后,针对可能碰撞的三角形特征对进行精确相交测试,返回发生第一次碰撞时间,完成碰撞检测。经过复杂度分析和实验论证,该算法响应速度快,在结构复杂物体的连续碰撞检测中效率较高,对于非凸体也可适用。     

求解0-1背包问题的二进制狼群算法

狼群算法(wolf pack algorithm, WPA)源于狼群在捕食及其猎物分配中所体现的群体智能,已被成功应用于复杂函数求解。在此基础上,通过定义运动算子,对人工狼位置、步长和智能行为重新进行二进制编码设计,提出了一种解决离散空间组合优化问题的二进制狼群算法（binary wolf pack algorithm, BWPA）。该算法保留了狼群算法基于职责分工的协作式搜索特性,选取离散空间的经典问题--0-1背包问题进行仿真实验,具体通过10组经典的背包问题算例和BWPA算法与经典的二进制粒子群算法、贪婪遗传算法、量子遗传算法在求解3组高维背包问题时的对比计算,例证了算法具有相对更好的稳定性和全局寻优能力。     

具有多值映射的两级优化问题的广义算法研究

两级优化问题是一种非凸非光滑问题，绝大多数问题的求解都是建立在下层有唯一解的基础之上的。而本文针对多值映射，即下层非唯一解的情形，利用隐函数理论，将两级优化问题转化为带有隐函数的非光滑问题，提出求解这类问题的广义算法框架，并证明其收敛性，最后通过实例验证该方法的实用性．     

两阶段资金投入条件下多项目组合中基于项目启动水平的资金分配问题研究

对两阶段资金投入条件下多项目组合中基于项目启动水平的资金分配问题进行了研究.由于已启动项目的资金不能按预算全额投入,因此文中引入了项目启动水平的概念,低于最低启动水平则项目不能启动.假设每个项目的净收益值与资金投入值可表示为与启动水平有关的线性函数,据此对两阶段投资过程分别建立了数学模型,分析认为它们分别属于0/1背包问题和连续背包问题,且都为NP难题.在建立了相关定理及定义的基础上,基于连续松弛条件下的价值密度贪婪准则,分别应用分枝定界算法、动态规划算法得到了该问题的资金分配最优策略.     

利用改进的二进制狼群算法求解多维背包问题

(1. Materiel Engineering College, Armed Police Force Engineering University, Xi’an 710086, China; 2. Materiel Management and Safety Engineering College, Air Force Engineering University,  Xi’an 710051, China;3. Air Traffic Control and Navigation College, Air Force  Engineering University, Xi’an 710051, China)     

求解大规模多背包问题的高级人工鱼群算法

针对复杂的大规模多背包问题,提出了一种基于高级人工鱼群算法的求解方法。为了解决人工鱼群算法收敛速度慢、求解精度低的问题,所提算法通过改进其初始化方法,优化人工鱼个体的行为选择方式和追尾行为来加快问题求解的收敛速度;同时引入了动态视野及步长和人工鱼调整策略来提高算法搜索的精度。仿真实验表明:与现有的算法相比,所提算法不仅能快速收敛,而且可以达到更高的精度,尤其是对于规模越大的多背包问题算法性能提升越明显。     

Quantum-inspired ant algorithm for knapsack problems

The knapsack problem is a well-known combinatorial optimization problem which has been proved to be NP-hard. This paper proposes a new algorithm called quantum-inspired ant algorithm (QAA) to solve the knapsack problem. QAA takes the advantage of the principles in quantum computing, such as qubit, quantum gate, and quantum superposition of states, to get more probabilistic-based status with small colonies. By updating the pheromone in the ant algorithm and rotating the quantum gate, the algorithm can finally reach the optimal solution. The detailed steps to use QAA are presented, and by solving series of test cases of classical knapsack problems, the effectiveness and generality of the new algorithm are validated.     

Inertial projection algorithms for convex feasibility problem

The purpose of this paper is to apply inertial technique to string averaging projection method and block-iterative projection method in order to get two accelerated projection algorithms for solving convex feasibility problem.Compared with the existing accelerated methods for solving the problem,the inertial technique employs a parameter sequence and two previous iterations to get the next iteration and hence improves the flexibility of the algorithm.Theoretical asymptotic convergence results are presented under some suitable conditions.Numerical simulations illustrate that the new methods have better convergence than the general projection methods.The presented algorithms are inspired by the inertial proximal point algorithm for finding zeros of a maximal monotone operator.     

基于时间反演的上行NOMA系统能效优化算法

为了解决上行非正交多址接入(non-orthogonal multiple access,NOMA)系统在多径环境下传输效率较低问题,提出了一种基于时间反演(time reversal,TR)的上行NOMA网络资源分配算法.首先,利用TR技术独特的空时聚焦特性,增大信号的接收强度.其次,考虑用户最小传输速率约束和用户最...     

基于TDOA/AOA混合的高精度室内可见光定位算法

为了提高室内三维空间的定位精度,提出了一种基于联合到达时间差与到达角度(time difference of arrival/angle of arrival,TDOA/AOA)信息的混合定位算法。由于构建的目标函数具有非凸性,采用传统定位算法在目标函数求解过程中会出现局部最优解的问题。因此,针对该问题,将目标函数转成二次约束二次规划问题,通过引入半定松弛(semi-definite relaxation,SDR)方法将目标函数转换为二阶锥规划(second order cone programming, SOCP)问题,寻找全局最优解。其次,针对SOCP无法对凸包外的目标进行有效定位的问题,在该算法的基础上引入了惩罚项,使松弛后的约束条件进一步逼近原始约束条件,解决了定位过程中的凸包问题。数值仿真结果表明:在10 m×10 m×3 m的三维定位空间内,选取40×40个测试点,平均定位误差为1.39 cm,可实现室内三维空间高精度定位。与传统的混合定位算法相比,均能够获得较高的定位精度。     

Synchronous Parallel Block Coordinate Descent Method for Nonsmooth Convex Function Minimization

This paper proposes a synchronous parallel block coordinate descent algorithm for minimizing a composite function, which consists of a smooth convex function plus a non-smooth but separable convex function. Due to the generalization of the proposed method, some existing synchronous parallel algorithms can be considered as special cases. To tackle high dimensional problems, the authors further develop a randomized variant, which randomly update some blocks of coordinates at each round of computation. Both proposed parallel algorithms are proven to have sub-linear convergence rate under rather mild assumptions. The numerical experiments on solving the large scale regularized logistic regression with 1 norm penalty show that the implementation is quite efficient. The authors conclude with explanation on the observed experimental results and discussion on the potential improvements.     

基于活跃集迭代法的支持向量机快速增量学习算法

介绍了一种新的支持向量机（SVM），其优化问题的对偶问题为具有简单界约束的凸二次规划问题：探讨了将活跃集迭代法运用于这种SVM的学习算法以及初始活跃集的选取问题；针对增量学习和大规模学习问题，提出了基于活跃集迭代法的SVM快速增量学习算法；实验验证了算法的有效性。