模拟退火算法的一种参数设定方法研究

模拟退火算法在有限计算量条件下的收敛性能对自身参数有很大的依赖性,这使得参数设定问题成了算法应用过程中的一个关键环节。考虑到模拟退火算法本身的随机性,将其参数设定问题描述为随机优化问题,提出一种系统可靠地解决该问题的混合优化算法,即基于序的巢分区算法,该算法继承了序优化算法的快速收敛性及巢分区算法的全局搜索特性,能够有效解决复杂的随机组合优化问题。以典型旅行商问题为算例的仿真结果检验了方法的高效性与可靠性。     

面向绿色航运的邮轮废弃物排放随机优化

邮轮产业的蓬勃发展带来了一系列的海洋环境问题,邮轮运营及船上乘客皆会产生不定量的废弃物,通常废弃物总量远大于其承载容量,需要在航线的多个港口处理废弃物并向港口缴纳一定费用.因此,与哪些港口签订长期合同,在哪个港口排放多少废弃物等决策将会影响邮轮公司的运营成本;这些决策需要通过一些优化模型进行科学地计算和分析.本文基于系统工程的思维对上述决策问题背景进行了分析,并运用数学规划的理论与工具,先后构建了确定性模型、适用于排污量参数服从任意概率分布的随机规划模型和适用于不确定参数区间的三阶段鲁棒优化模型.随后,本文结合上述问题与模型的特征,设计了定制化的禁忌搜索算法和粒子群算法分别求解随机模型和鲁棒模型中的大规模问题;并通过一些基于实际问题规模和数据特征的实验,验证了本文所构建的决策模型的有效性和所设计算法的求解效率.本文研究所提出的邮轮废弃物排放决策方法论对当前全球绿色航运事业的推广与发展具有一定应用价值和指导意义.     

连续体结构的模糊多目标拓扑优化设计方法研究

提出了连续体结构静力学和动力学多目标拓扑优化设计的模糊-目标规划方法。该方法利用目标规划方法将多目标优化问题转化为等效的单目标问题,并用模糊集理论中的非线性隶属函数来体现目标规划方法中目标函数期望值所具有的模糊性和不确定性。以结构静力学的刚度和动力学的特征值作为优化的两个目标函数,提出并建立了连续体结构拓扑优化设计的多目标优化模型。用移动渐进线方法(MMA)求解单目标优化问题,用序列线性规划方法(SLP)求解模糊-目标混合规划问题。通过典型的求解算例验证了所研究方法的有效性。     

一类分散多目标决策问题的模型及交互式决策方法

本文建立了一类适用范围更广泛的分散多目标决策问题的模型，基于该多目标问题的非劣解与加权增广切比雪夫范数优化问题的解之间的关系，提出了一种求解它的交互式决策方法，了求解加权增广切比雪夫范数优化问题的随机全局优化方法，示例的仿真结果表明该决策方法是实用有效的。     

Scenario-based stochastic resource allocation with uncertain probability parameters

The stochastic resource allocation (SRA) problem is an extensive class of combinatorial optimization problems widely existing in complex systems such as communication networks and unmanned systems. In SRA, the ability of a resource to complete a task is described by certain probability, and the objective is to maximize the reward by appropriately assigning available resources to different tasks. This paper is aimed at an important branch of SRA, that is, stochastic SRA (SSRA) for which the probability for resources to complete tasks is also uncertain. Firstly, a general SSRA model with multiple independent uncertain parameters (GSSRA-MIUP) is built to formulate the problem. Then, a scenario-based reformulation which can address multi-source uncertainties is proposed to facilitate the problem-solving process. Secondly, in view of the superiority of the differential evolution algorithm in real-valued optimization, a discrete version of this algorithm was originally proposed and further combined with a specialized local search to create an efficient hybrid optimizer. The hybrid algorithm is compared with the discrete differential evolution algorithm, a pure random sampling method, as well as a restart local search method. Experimental results show that the proposed hybrid optimizer has obvious advantages in solving GSSRA-MIUP problems.     

多种资源受限多项目排序问题的两层决策方法

分析了多种资源受限多项目排序问题的性质和特点 ,提出用两层决策方法建立这类问题的数学模型 .将基于直接搜索法的随机全局优化方法用于求解该问题的全局最优解 ,给出了具体的算法步骤 .计算示例表明 ,本文建立的模型和给出的算法能有效地求解多种资源受限多项目排序问题.     

动态加强CPT解job-shop调度约束满足优化问题

带有相同到达期与交货期的job-shop调度问题(JSSP)作为多种实际生产调度问题简化模型,是一类典型强NP-hard问题.对优化目标是最小化最大完工时间的JSSP问题,建立了约束满足优化问题模型(JSSC-SOP).利用弧一致约束传播算法和深度优先启发式构造活动调度,逐步加入新约束,实现活动调度集的部分列举与寻优.提出3种动态加强约束传播技术(CPT),嵌入搜索过程,提高求解效率.最后通过随机生成的实例,验证了各方法可行性与有效性.     

PRODUCTIVE GOVERNMENT EXPENDITURE IN A STOCHASTICALLY GROWING OPEN ECONOMY

This paper employs a stochastic endogenous growth model with productive government expenditure in a small open economy to analyze the optimal fiscal policy. First, a stochastic model of a small open economy is constructed. Second, the equilibrium solutions of the representative agent＇s stochastic optimization problem are derived. Third, we obtain the equilibrium solutions of the central planner＇s stochastic optimization problem and the optimal government expenditure policy. Finally, the optimal tax policy is characterized.     

基于无容量限制的p-枢纽中位问题的随机优化

在枢纽网络设计时, 未来的成本和需求等参数具有不确定性. 为了使设计的网络能在各种情景下具有最优的期望成本, 提出了无容量限制的多分配严格p-枢纽中位随机优化模型. 考虑到模型本身的结构特点和复杂程度, 采用了PH分解算法结合增广拉格朗日松弛算法, 将原问题转化为若干个独立子问题来求解. 使用了基于经典算例的随机数据集合对模型和算法进行了测试, 算例结果表明尤其在情景数量较大的情况下, 算法体现出较高的效率. 同时, 通过随机解价值分析了使用随机优化模型对于该算例的意义.     

随机需求下公交时刻表设计的鲁棒性优化

考虑在实际运营中乘客需求具有随机性,固定需求下优化的公交时刻表不适应运营的要求.随机需求下的期望值模型忽略了不利可能事件对运营的负面影响,针对此情况研究随机需求下公交时刻表设计的鲁棒性优化.模型综合考虑乘客成本与运营成本,采用鲁棒性优化权衡目标期望值与偏差期望值.结合随机模拟技术,选用遗传算法求解模型.给出了算例,验证了模型和算法的有效性.通过比较固定需求模型、随机需求期望值模型、随机需求鲁棒性模型,说明在鲁棒性优化下需要提供更多的交通供给以降低偏差期望值.最后,对鲁棒性模型中的偏差权重系数进行了灵敏度分析.     

考虑技术突破与技术升级的能力规划问题研究

技术进步与市场需求不确定性,都是制造业能力规划问题需要面对的最重要因素.以往研究仅考虑技术突破而没有考虑技术升级,较多考虑能力扩张而较少考虑能力更替,本文首次提出了一种同时考虑技术突破和升级的设备采购与替换的集成能力规划模型.在需求和技术进步双源不确定性条件下,采用Scenario方法建立了多计划期能力规划的集成决策模型,探求能力扩张、替换、维护的期望总成本最低.面对该决策问题所建立的非线性混合整数规划模型,本文为该NP complete问题设计了一种基于遗传算法框架的启发式求解算法,即通过增加变换操作的方法将该问题转换为可以随机进化求解扩张方案最优化求解替换方案的一个等价问题.在种群初始化过程中采取仅选择能力扩张决策进行染色体部分编码策略,然后用经典优化方法针对每个个体精确求解最优能力替换决策,将扩张和替换整体成本作为个体适应度参与个体评价与种群进化.实验结果表明,技术升级在不同需求变化情景下都可以有效降低能力规划的成本,且本文提出的启发式算法对于求解此类规划问题具有很好的收敛稳定性和性能稳定性.     

Cost and Service-Level-Based Model for a Seru Production System Formation Problem with Uncertain Demand

With increasing demand diversification and short product lifecycles, industries now encounter challenges of demand uncertainty. The Japanese seru production system has received increased attention owing to its high efficiency and flexibility. In this paper, the problem of seru production system formation under uncertain demand is researched. A multi-objective optimization model for a seru production system formation problem is developed to minimize the cost and maximize the service level of the system. The purpose of this paper is to formulate a robust production system that can respond efficiently to the stochastic demand. Sample average approximation (SAA) is used to approximate the expected objective of the stochastic programming. The non-dominated sorting genetic algorithm II (NSGA-II) is improved to solve the multi-objective optimization model. Numerical experiments are conducted to test the tradeoff between cost and service level, and how the performance of the seru production system varies with the number of product types, mean and deviation of product volume, and skill-level-based cost.     

不确定条件下卫星鲁棒性调度问题

在对地观测卫星调度过程中，存在着很多不确定性因素，其中云层覆盖变化是主要的不确定性来源。本文针对考虑云层覆盖不确定性的卫星调度问题，借鉴了连续函数的鲁棒性优化思想，提出了一种基于邻域的鲁棒性指标，用于衡量卫星调度方案的鲁棒性。在此基础上，建立了卫星鲁棒性调度的CSP模型，设计了基于分级优化策略的随机变邻域禁忌搜索算法。实例研究表明，本文提出的模型和求解算法能够在保证调度方案性能的基础上，获得鲁棒性强的调度方案。     

基于混合优化算法的遗传算法参数设定研究

有限计算量条件下遗传算法的理论收敛条件难以完全满足,参数选择的恰当与否直接影响到算法性能的发挥。针对这一情况,在分析现有参数设定方法的基础上,将遗传算法参数设定问题描述为随机优化问题,并提出一种解决该问题的新的混合优化算法,即基于序优化的巢分区算法。该算法将序优化思想融入巢分区算法的局部搜索过程,大大提高了局部搜索效率,而巢分区的算法框架则保证了算法的全局收敛性。以典型旅行商问题为算例的仿真结果验证了该方法的高效性与可靠性。     

一类带有随机参数的交通优化模型及遗传算法

双向编组站包含两个个独立的作业系统，确定最合理的系统分工方案是这类编组站必须解决的首要问题，车流量则是该问题重要的输入参数，在实际运输工作中，车流量随着时间的不同总要发生一定的波动变化，这必然会影响双向编组站系统分工方案，针对这一交通运输学科经常面临的情况，构造了车流波动条件下双向编组站系统作为分工的随机优化模型，建立了基于遗传算法的求解理论，该方法对交通问题具有一般性的意义。     

随机价格条件下的产业选址双层规划模型及其禁忌算法

对产业选址问题进行了描述,提出一类带有价格随机参数的产业选址双层规划模型.根据该模型的特点转化为确定性的双层规划问题, 并且设计优化该问题的禁忌算法.算法基于二进制编码, 设计三种邻域,在邻域操作中控制选址数量约束, 采用惩罚函数处理总投资额约束, 提高了禁忌算法的优化效率和优化效果.描述产业选址问题双层规划模型的构建过程, 介绍算法的原理, 给出具有代表性算例试验结果和结果分析.试验结果及其分析表明本文提出的具有随机参数的产业选址问题双层规划模型及其优化算法的有效性.     

加工时间为连续随机变量的Job Shop调度问题

针对实际调度问题中存在的不确定现象,提出了加工时间服从正态分布、最大完成时间的期望值作为目标函数的随机Job Shop问题;然后提出了解决该问题的智能优化算法:采用随机模拟的方式产生输入输出数据,利用遗传算法训练神经网络,将训练过的神经网络嵌入到另一遗传算法中,用该遗传算法来优化Job Shop调度问题;最后给出了仿真实验,通过仿真实验证明,该算法对于解决加工时间为随机变量的Job Shop调度问题是行之有效的。     

需求不确定性对最小化成本和最大化利润报童问题的影响

运用应用概率中的随机占优和可变序研究需求不确定性对两类报童问题的影响,一类是经典的最小化成本报童问题,另一类是带有二次订货策略的最大化利润报童问题. 得到对应于两类报童问题的最优成本（最优利润）关于缺货惩罚费用（二次订货费用）的单调性,并从最优化和随机比较两个方面分析两类模型的等价性. 针对最大化利润报童问题,给出在分散序意义下比较系统最优利润的充分条件,并证明当二次订货费用小于或等于零售价格时,随机大需求导致较高的最优利润,但当二次订货费用大于零售价格时此结论不一定成立. 证明对任意二次订货费用,在二阶随机占优意义下系统最优利润随需求可变性增加而减小. 进一步,证明存在一类需求分布,当需求均值相等且二次订货费用大于某一固定值时,系统最优利润随需求可变性的增加而增加. 对最小化成本报童问题给出类似的结果. 数值例子验证了得到的研究结果.     

应急物流系统中的随机定位-路径问题

为了提高突发公共事件应急物流系统的运作效率,考虑应急物资需求和救援车辆旅行时间的随机性,以及应急物资需求的紧迫性,基于机会约束规划方法建立了一个应急物流系统中带时间窗的随机定位-路径问题优化模型,设计了一种结合禁忌搜索和蒙特卡罗方法的混合遗传算法,并通过算例分析验证上述模型和算法的有效性。     

单线铁路区间能力失效条件下列车运行调整模型

列车运行调整是调度指挥工作中关键任务之一. 列车运行调整模型多是基于确定的、强度较弱的扰动提出的,然而现实中某些扰动可能包含不确定的信息, 且强度较大,使得既有模型和算法呈现出一定局限性.针对单线铁路区间能力失效条件下列车运行调整问题,考虑能力失效持续时间的不确定因素,探索优化制定列车运行调整方案的模型.提出两阶段带补偿随机期望值模型,进一步讨论了多阶段递归决策概念模型的复杂度,据此给出了不完全连续多阶段决策模型.针对两类模型提出基于分枝定界的求解算法, 设计算例进行验证,与基于优先级的运行调整方法进行比较. 结果表明,相对于基于优先级的方法,多阶段决策模型能够将总列车晚点时分的期望值降低34%,两阶段模型能够降低4%, 两种模型均能够在一定程度上提高列车正点水平.