允许部分服务的随机需求车辆路径问题研究

文章对需求量满足二项分布的随机需求车辆路径问题进行了研究,在服务失败时采取允许部分服务的策略,通过仿真的方法证明了这一策略的有效性;并将嵌套分割算法与扫描算法相结合,提出了一种新的求解随机需求车辆路径问题的两阶段算法,数值试验验证了该算法的有效性.该算法拓展了车辆路径问题的算法空间.     

基于混合蚁群遗传算法的SAT问题求解

根据SAT问题的特点,通过分析传统蚁群算法和遗传算法在求解SAT问题上的不足,提出一种基于混合蚁群遗传算法的SAT问题求解方法。给出一种新的初始解的生成方式;在迭代过程中,根据较优解的累积信息提出进化算子;利用当前得到的最优解,通过改变不满足子句中文字的取值,增加变异算子。最后选取标准测试集中的20个实例对算法进行测试,实验结果表明:改进后的算法通常仅通过较少次数的迭代就能找到解,能够有效避免蚁群算法和遗传算法过早收敛的缺点,具有较强的寻优能力。     

一种修正三项Hestenes-Stiefel共轭梯度投影算法及其应用

提出一种新的修正三项Hestenes-Stiefel共轭梯度投影算法, 用于求解大规模非线性方程组问题和信号恢复问题. 该算法通过构造一个新的修正Hestenes-Stiefel搜索方向, 结合经典线搜索方法和超平面投影技术而得, 新搜索方向在不需要任何线搜索条件下自动满足充分下降性, 在常规假设条件下, 新算法具有全局收敛性质. 数值实验结果表明,  新算法高效且稳定.     

求解最小体积轴向椭球问题的线性收敛算法

通过定义求解最小体积轴向椭球问题的两个近似最优性条件, 计算满足第二个近似最优性条件的一个新的近似解, 给出一种求解最小体积轴向椭球问题的近似算法, 并证明了算法具有线性收敛性. 实验结果证实了算法的有效性.     

一类约束满足问题及其算法

针对具有解析约束形式、同一变量多赋值的约束满足问题,提出了一种新的约束满足问题定义·通过一种特殊约束满足问题的研究提出一套建立在这个定义基础之上的概念和三种算法:整数规划法、不等式组法和直接求解不定方程法,详细研究了其中的第三种算法,并给出了最坏情况下的时间复杂度,从而能够比较清晰地描述一类约束满足问题的一般分析过程,揭示了约束满足问题同经典的整数规划、数论和整数环论的联系·     

求解Fisher市场均衡问题的内点算法

Fisher 市场均衡是经济学中的经典问题，可以用线性权互补问题来表述。通过调整中心方向向可行点偏移得到新的搜索方向以保证可行性，再利用线性搜索寻找满足邻域条件的最大更新参数来设计求解Fisher市场均衡问题的算法，分析了算法的可行性，证明了算法的迭代复杂度。数值实验结果表明该算法对求解Fisher市场均衡问题是有效的。     

最大可满足性问题的算法研究综述

最大可满足性问题(maximum satisfiability,MaxSAT)是一个著名的、具有NP难度的组合优化问题.本研究总结了近年来求解最大可满足性问题的各类算法.首先,给出了最大可满足性问题的定义;然后,基于完备算法和非完备算法两个类型,对求解MaxSAT的各类算法进行了综述.其中完备算法包括分支定界算法和迭代...     

求解一个多旅行商问题的一种新近似算法

研究的多旅行商问题是：满足三角不等式的赋权完全图上的一个双目标优化问题．首先运用系统科学中的“吸引子”概念对问题求解的算法机理作了新的分析探讨,在此基础上提出了一种求解该问题的近似算法思想,并设计了算法,这是一种颇为新颖处理方法,国内外文献未见报道;文章最后还指出了几个尚须进一步思考的问题．该文旨在通过实例分析,尝试阐述一种萌芽的处理一些优化问题的新的近似算法思想,抛砖引玉,为进一步的理论研究提供基础.     

利用改进的HBDE算法求解MAX-k-SAT问题

目前,利用进化算法求解组合优化问题已成为智能计算领域中的研究热点。本文基于二进制差分演化算法和动态变邻域搜索相结合提出了一种求解最大可满足问题(MAX-k-SAT)的改进算法(记为IBDE),通过与遗传算法和Johnson算法对一系列随机大规模MAX-k-SAT实例的求解比较表明:IBDE是一种求解MAX-k-SAT问题非常有效的新方法。     

求解单调线性互补问题的势下降内点算法

研究了单调线性互补问题的一种内点法,将牛顿方向和中心路径方向相结合,通过求解一个线性方程组得到搜索方向;在每次迭代中,寻找使得新的迭代点满足可行性要求且同时使得势函数值下降的步长参数,进而建立了求解单调线性互补问题的一种势下降内点算法,并证明该算法经过多项式次迭代之后收敛到原问题的一个最优解,数值实验表明此方法是有效的。     

基于分割的超树分解方法

基于det-k-decomp算法, 通过引入同构的概念和对separator选择空间的进一步限制, 提出一类新的超树分解： 分割的超树分解, 并提出一种具有较小超树宽度的超树分解方法: 基于分割的超树分解--sht-k-decomp, 该算法能有效提高约束满足问题的求解效率. 实验结果表明, sht-k-decomp算法多数情况下效率高于det-k-decomp算法.     

基于权值加密的隐私安全分布式约束满足问题求解

隐私安全的分布式约束满足问题(distributed constraint satisfaction problem,DisCSP)求解算法可以很好地满足信息敏感的分布式组合求解问题的需要,为了获得更好的求解效率,提出了一种基于权值加密的隐私安全DisCSP的求解算法,对DisCSP问题中的约束基于不同的隐私权值进行加密求解;不需要增加额外的agent进行隐私约束的一致性检查,实现分布式的安全求解策略;对于可能出现的推理信息,用随机选择策略来避免信息泄漏.试验表明,该算法可以减少信息的传递量和计算的复杂性,因而具有更好的求解效率.     

基于约束满足的板坯设计模型与求解方法

针对客户订单的重量需求为固定值、客户订单分配过程中有最小重量限制的板坯设计问题,建立了以最小化板坯数量为目标的约束满足模型.通过三划分问题的多项式归结,证明了该问题是强NP难的;针对问题的特殊性质,给出了变量选择策略和值选择策略;提出了基于约束满足技术的求解算法,并证明了算法的收敛性;通过数据实验对算法的有效性进行了验证.     

基于蚁群算法的并行任务分配与调度

蚁群算法是近年出现的一种新启发式算法,在求解NP完全问题中具有较大优势.针对如何在满足任务约束关系的条件下用蚁群算法求解任务分配与调度问题,首先对任务的分配与调度问题建立数学模型,然后在满足子任务之间的约束关系的条件下用蚁群算法求出最优解,最后把用蚁群算法与遗传算法的最优解进行比较.通过仿真实验表明,蚁群算法比遗传算法在任务分配与调度求解中有较高的解的质量,但蚁群算法的求解速度要慢于遗传算法.     

基于聚类排序选择方法求解3-SAT问题的遗传算法

使用聚类排序选择方法的遗传算法,加入交叉算子和变异算子求解3-SAT问题。根据适应度函数及问题本身的特性,对阈值6进行调节,重新生成新的种群聚类,有效地抑制了算法延迟收敛的可能性及可满足性范式无解的可能性,使得与同类算法相比,在时间上有很大的改进。最后给出基本的求解算法并分析了该算法的复杂性。     

求解非光滑优化问题的修正HS三项共轭梯度法

为了提高大规模非光滑优化问题的求解效率,克服其他方法存储需求大、算法复杂等缺点,提出求解非光滑优化问题的一种修正HS共轭梯度算法。在经典HS三项共轭梯度法的基础上提出一种新的搜索方向,并利用Moreau-Yosida正则化技术和Armijo-type线搜索技术进行设计。新算法满足充分下降条件,搜索方向属于信赖域,在适当条件下证明了新算法全局收敛。初步的数值实验表明新算法在求解非光滑无约束优化问题方面比LMBM方法更有效。新算法不仅具有较好的收敛性质,而且数值表现良好,为更加高效地求解非光滑优化问题提供了新的方法。     

求解加权Euclidean单中心问题的SMO-型算法

通过定义求解加权Euclidean单中心(WEOC)问题的两个近似最优性条件, 基于序列最小最优化(SMO)方法, 提出一种求解WEOC问题的SMO 型算法.
该算法求解WEOC问题满足第二个近似最优性条件的(1+ε) 近似解, 并且每次迭代只需更新对偶变量的两个分量. 数值结果表明, SMO 型算法执行简单, 能有效求解高精度的大规模计算问题.     

基于并行量子遗传算法的QoS组播路由方法

通信网络时延受限且满足带宽要求的最小代价组播树问题是NP完全问题,传统方法难以求解,一般采用启发式方法求解.提出了一种基于并行量子遗传算法的服务质量(QoS)组播路由算法,算法中将各个子群体独立地并行进化,并通过相邻子群体间的信息交换实现克服早熟,避免局部收敛的目的,还提出了一种新的动态旋转角调整策略,使算法具有更好的种群多样性和全局寻优能力.仿真实验表明,新算法在求解性能上优于遗传算法(GA)和采用静态旋转角的量子遗传算法(QGA).     

基于自适应多态蚁群算法的多约束车辆路径问题

建立了在有客户优先级、路况影响、多车型、时间窗和容量等多约束条件下车辆路径问题(VRPMC)的数学模型.由于该模型是一个NP-hard问题,目前还没有多项式算法求解,又提出了采用自适应的多态蚁群算法(APACA)来对其进行求解的策略.首先,算法中侦察蚁完成满足约束条件的路径侦察并设置侦察信息素;其次,搜索蚁利用侦察蚁提供的辅助信息进一步搜索可行路径,通过多态蚂蚁间的协作和自适应调整挥发系数,能更快地搜索到问题的优化解;最后通过一个实例与节约算法、遗传算法、禁忌搜索算法和基本蚁群算法进行了对比,结果表明:对VR-PMC问题,APACA算法比前述算法在算法稳定性、运行距离、计算速度方面更具有优势.     

新的求解大规模线性最小二乘问题的随机算法

目的针对传统的求解线性最小二乘问题方法的计算、存储复杂度大,不适于大规模问题的缺点,提出新的随机算法近似求解大规模线性最小二乘问题。方法通过随机采样对超大规模线性最小二乘问题的系数矩阵进行约减,利用快速Walsh-Hadamard对问题进行变换来保留原问题的重要信息,再用QR分解算法求解约减问题,得到原问题的近似解。结果该方法有效降低了问题的求解复杂度和存储复杂度。结论数值实验表明新算法和相关算法相比求解精度可接受,但大大减少求解时间且在同等计算平台下可处理更大规模的问题。