摘要：目的 在传统冷链物流的车辆路径问题模型基础上,考虑服务节点和车辆运输过程中产生的碳排放,并加入客户满意度,在有限资源情况下最小化路径成本和最大化客户满意度。方法 构建多目标低碳冷链物流车辆路径问题模型,将爬山算法局部搜索思想应用到麻雀搜索算法中,形成改进麻雀搜索算法,并用其对上海市某区域内的冷链物流配送路径优化问题算例进行求解。结果 通过与改进前及其他2种智能优化算法运行结果进行对比发现,改进后的麻雀搜索算法具有更快的寻优速度和更好的寻优能力,且改进后的算法对模型的碳排放效用性更高。结论 基于国家的低碳政策,设计出符合当下实情的低碳冷链物流运输模型,通过改进优化算法设计运输方案,验证了爬山算法局部搜索思想对麻雀搜索算法进行改进的有效性及所构建低碳冷链物流车辆路径模型的合理性。

摘要：考虑不确定性的模糊多式联运路径优化研究,可以在满足运输方案经济环保双重要求的同时,增强运输方案的鲁棒性,提高企业的抗风险能力.本文建立了模糊需求和模糊运输时间下低碳低成本多式联运路径优化模型,针对连续型元启发式算法无法直接求解离散型组合优化模型的问题,设计了基于优先级的通用编码方式.在此基础上,为进一步提高算法的求解质量,提出了带启发式因子的特殊解码方式,并且提出了一种带邻域搜索策略的自适应差分进化算法.结果表明,改进算法获得的最终方案在蒙特卡罗采样的大多数场景下满足约束,方案稳定性强,目标值最低.

摘要：经典k-均值问题是一类应用广泛的聚类问题,它是指给定R^(d)中观测点集合D和整数k,目的是在空间中寻找k个点作为中心集合S,使得集合D中的每个观测点到S中离它最近的中心的距离平方求和最小。这是个NP-难问题。经典k-均值问题有很多推广,本文研究的带惩罚的相同容量k-均值问题就是其中之一。与经典k-均值问题相比,惩罚性质是指每个观测点都给定惩罚费用,当某个观测点到最近中心的距离大于惩罚费用时,其对目标函数的贡献就用该观测点的惩罚费用来代替最近的距离的平方,相同容量约束要求每个中心至多连接U个观测点。针对这种问题,我们设计了局部搜索算法,该算法在至多选取(3+α)k个中心的情况下,可以达到β-近似,其中,参数α>34,β>α+34/α-34。

摘要：带平衡约束的矩形布局问题属于组合优化问题,当问题规模增大时求解困难。为提高求解效率,设计了一个蜂群算法,通过分析解的分布,提供了基于贪心策略的群体初始化方案,选择了有效的变异算子,将蜂群算法的搜索空间聚焦于最优解可能的区域。另外设计了一个二次局部搜索算法,对解的质量进行进一步提升。在10个公开的案例上与目前性能最好的算法进行了对照,提出的蜂群算法在其中9个较大规模的案例上超过了现有算法。理论分析和实验结果表明,相对于现有算法,所提蜂群算法能明显提高求解效率。

摘要：在求解边坡临界滑动面问题的优化算法中,大多都存在结构复杂、参数取值困难或寻优效果差的缺点。为此,将基于高斯分布模型的分布估计算法与基于简化Bishop法的滑面安全系数计算模型相结合,建立具有简单生物协同和竞争思想的临界滑动面搜索新方法;然后,针对3自由度问题,设计了一种局部搜索方法,以弥补分布估计算法局部搜索性能差的劣势。将标准方法和改进方法分别应用于边坡断面复杂度依次递增的3道算例中,完成对标准方法正交试验结果的极差分析和多因素方差分析,并实现标准算法与改进算法计算结果的对比分析。结果表明:(1)标准分布估计算法可以计算出边坡的临界滑动面;(2)当算例简单时,各控制因素都不会对计算结果产生显著性差异;当算例复杂时,只有种群规模呈现出显著性;(3)改进算法比标准算法的计算结果更佳、搜索速度更快,且有效降低了种群规模大小对计算结果的影响。探索分布估计算法在边坡临界滑动面搜索问题中的应用,为解决该类问题开辟出了一条新的研究途径。初步校验表明,该模型鲁棒性更好,具有广阔的应用前景。

摘要：随着软硬件设计规模日益增加,功能越来越复杂,功能验证与调试在整个设计周期中占有的比重越来越大,迫切需要高效的方法诊断与定位设计中的错误,而求解不可满足子式可以显著提高自动化工具定位错误的效率.近年来,求解不可满足子式的算法多是基于DPLL(Davis-Putnam-Logemann-Loveland)回溯搜索过程的完全算法,很少有研究涉及到不完全方法.文中针对求解不可满足子式的不完全方法,提出了悖论证明与悖论解析树的概念,并提出一种启发式局部搜索算法,从布尔公式的悖论证明中求解不可满足子式.算法首先采用融合了布尔推理技术、动态剪枝方法及蕴含消除方法的局部搜索过程,逐步构建悖论证明所对应的悖论解析树;然后调用递归函数搜索悖论解析树,最终得到不可满足子式.基于实际测试集与随机测试集进行了实验对比,结果表明文中提出的算法优于同类算法,而且动态剪枝与蕴含消除技术能够有效地减少存储空间及运行时间.

摘要：针对中药饮片制造场景下调度求解过程中加工时间不确定以及存在工序间时滞的问题,以最小化最大完工时间为目标,建立考虑时滞的模糊柔性作业车间调度模型,并设计一种改进的遗传算法(IGA)进行求解。使用一种四层编码方法描述带时滞约束的染色体,构建具有模糊加工时间和模糊时滞的作业析取图获取关键路径,使用基于变邻域下降法(VND)的禁忌搜索(TS)增强算法局部搜索能力,再使用一种精英拓展选择策略提高算法迭代效率。以某企业的生产调度数据为例进行仿真实验,结果表明,改进算法在求解中药饮片生产调度问题中具备较好的性能。

摘要：合取范式最大可满足问题是理论计算机科学的核心问题.局部搜索被许多求解实践证明是解答合取范式最大可满足问题十分有效的方法,但未见关于局部搜索算法解答该问题性能分析的结果.文中讨论最大3可满足问题(Max-(3)-Sat)的局部搜索算法并分析算法性能.证明Max-(3)-Sat问题的一位跳变局部搜索算法的近似性能比为4/3;证明一位跳变局部搜索后跟有条件全体跳变算法,解答Max-(3)-Sat问题的近似性能比为5/4.设计一位跳变加全体跳变的新局部搜索算法,证明新算法解答Max-(3)-Sat问题的近似性能比为8/7.将8/7-近似局部搜索算法推广为解答Max-(k)-Sat问题的局部搜索算法,证明算法的近似性能比为(2k+2)/(2k+1),k4.设计解答Max-(k)-Sat问题的两位跳变局部搜索算法,证明两位跳变局部搜索算法的近似性能比为1+1/(2k+1+k(k-1)/(n-k)),k4.局部搜索算法经多次运行可进一步提高求解性能.文中结果显示,局部搜索算法在合取范式最大可满足问题求解实践中表现出高性能,有其必然性.

摘要：作为与归结推理方法互补的推理方法,扩展规则推理方法得到了国内外广泛认可.目前扩展规则推理方法的研究主要集中于完备推理方法,由于极大项变换方式过于机械,导致该方法处理公式的规模比较局限.该文在深入分析扩展规则推理和局部搜索关联性的基础上,利用子句集中的"极大项"概念设计了一种反向求解策略,进而设计并实现一种新的基于局部搜索的扩展规则推理框架.在此基础上,为了使得极大项搜索过程更加适配该框架,提出了一种基于精确格局检测实现和双向半扩展规则策略的两阶段局部搜索算法.实验结果表明,该文提出的基于精确格局检测的新型扩展规则推理算法ERACC突破了传统扩展规则推理对公式规模的局限,求解效率有了极大提高,使得扩展规则推理方法不再受公式规模制约,可以用于知识编译和可能性推理等多方面的应用.

摘要：ERACC(Extension Rule Based on Accurate Configuration Checking)算法由杨洋等人基于扩展规则和格局检测提出,具有较高的推理效率.为进一步提高ERACC算法在大规模SAT(Satisfiability)问题求解上的性能,本文在搜索由极大项组成的空间时,首先利用IMOM(Improved Maximum Occurrences on Clauses of Maximum Size)思想生成初始极大项,接着设计了适用于扩展规则推理的CCA_ER(Configuration Checking with Aspiration for Extension Rule-Based Reasoning)启发式策略,为极大项中格局信息未发生变化的变量对应文字提供一定的翻转机会.同时,为进一步提高扩展规则推理算法在k-SAT问题求解上的性能,设计了适用于扩展规则推理的PAWS_ER(Pure Additive Weighting Scheme for Extension Rule-Based Reasoning)策略,并且给出变量的Subscore_ER(Subscore for Extension Rule-Based Reasoning),CScore_ER(Comprehensive Score for Extension Rule-Based Reasoning)和HScore_ER(Hybrid Score for Extension Rule-Based Reasoning)属性.在此基础上,提出了ERACC_IAPS(ERACC with IMOM,CCA_ER,PAWS_ER and Subscore_ER)和CERACC_IAPS(ERACC with IMOM,CCA_ER,PAWS_ER,CScore_ER and HScore_ER)算法.实验结果表明:ERACC_IAPS和CERACC_IAPS算法的效率明显优于ERACC算法,最高可将其求解效率提高1000多倍.