面向多目标优化的一种混合进化算法

针对多目标优化问题,设计一种基于量子计算和非支配排序遗传算法相结合的智能算法进行求解,综合量子算法和非支配排序遗传算法的优点,在局部搜索和全局搜索之间进行权衡。混合算法采用量子比特对问题的解进行编码,基于量子旋转门算子、分散交叉算子以及高斯变异算子对种群进行更新。进行局部深入搜索时,用一个解在目标空间中跟理想点的距离来评价该解的优劣;进行全局搜索时,基于非支配排序遗传算法中的有效前沿的划分和解之间的拥挤距离来评价某个解。最后,在经典的测试函数ZDT5上对所提混合算法进行了测试。通过对比分析若干项针对有效解集的评价指标,该混合算法在跟最优有效前沿的逼近程度以及有效解集分布的均匀程度上均优于目前得到广泛应用的非支配排序遗传算法。     

求解零等待流水车间调度问题的改进蝙蝠算法

针对零等待流水车间调度问题特性,设计了一种蝙蝠算法进行求解.算法模拟蝙蝠捕食搜索行为进行寻优,利用基于最小位置值规则的随机键编码方式来表示问题解,采用基于NEH方法的局部搜索策略和随机交换、插入、逆序操作的变邻域搜索策略来提高局部优化性能,进一步根据Metropolis概率准则接受劣解来避免早熟.通过典型算例对所提算法进行仿真测试并与粒子群算法和RAJ启发式算法进行对比,结果表明所设计算法求解零等待流水车间调度问题的有效性和优越性,是求解流水车间生产调度问题的一种有效工具.     

基于种群自适应调整的多目标差分进化算法

为提高已有多目标进化算法在求解复杂多目标优化问题上的收敛性和解集分布性,提出一种基于种群自适应调整的多目标差分进化算法。该算法设计一个种群扩增策略,它在决策空间生成一些新个体帮助搜索更优的非支配解;设计了一个种群收缩策略,它依据对非支配解集的贡献程度淘汰较差的个体以减少计算负荷,并预留一些空间给新的带有种群多样性的扰动个体;引入精英学习策略,防止算法陷入局部收敛。通过典型的多目标优化函数对算法进行测试验证,结果表明所提算法相对于其他算法具有明显的优势,其性能优越,能够在保证良好收敛性的同时,使获得的Pareto最优解集具有更均匀的分布性和更广的覆盖范围,尤其适合于高维复杂多目标优化问题的求解。     

带有资源转移时间的RCPSP资源流模型及算法

本文在传统资源受限项目调度问题(resource-constrained project scheduling problem, RCPSP)中引入资源转移时间,为有效获得问题的最优解,采用资源流编码方式表示可行解,建立了带有资源转移时间的RCPSP资源流优化模型,目标为最小化项目工期。根据问题特征设计了改进的资源流重构邻域算子,分别设计了改进的禁忌搜索算法和贪心随机自适应禁忌搜索算法求解模型。数据实验结果表明,相较于现有文献中的方法,所提两种算法均可针对更多的项目实例求得最优解,并且得到最优解的时间更短,求解效率更高。此外,分析了算法在求解具有不同特征的项目实例时的性能,所得结果为项目经理结合项目特征评价算法适用性提供了指导。     

凸二次半定规划一个新的原始对偶路径跟踪算法

本文提出求解凸二次半定规划的一个新的原始对偶路径跟踪算法.在每次迭代中,通过求解一个线性方程组产生搜索方向.在一定条件下证明算法产生的迭代点列落在中心路径的邻域内,且算法至多经■次迭代可得到一个ε-最优解.     

一种改进的多模式项目反应性调度问题

既有的项目反应性调度问题只关注了基准调度方案的稳定性,而忽略了项目调度目标的最优实现。本文提出了一种两阶段多模式资源受限项目反应性调度问题。第一阶段,在新的项目执行环境下,对项目进行完全重调度,得到新的最优调度目标值。第二阶段,以新的最优调度目标值为约束,以最大化调度稳定性为目标,求得新的最优调度方案。针对问题特点,基于IBM ILOG优化编程语言OPL和CPLEX V12.8.0,设计出该问题的求解程序。最后,基于标准算例,对本文提出的反应性调度方法、既有的反应性调度方法、完全重调度方法进行了充分的比较测试,结果表明本文提出的反应性调度方法在缩短项目工期、保护基准方案的稳定性方面具有明显优势。     

新非单调线搜索规则的Lampariello修正对角稀疏拟牛顿算法

本文设计了求解无约束最优化问题的新的非单调线搜索规则的Lampariello修正对角稀疏拟牛顿算法.新的步长规则类似于Grippo非单调线搜索规则并包含Grippo非单调线搜索规则作为特例.新的步长规则在每一次线搜索时得到一个相对于Grippo非单调线搜索规则的较大步长,同时保证算法的全局收敛性.数值例子表明算法是有效的,适合求解大规模问题.     

项目多技能人力资源指派与调度混合算法

研究多技能人力资源在项目活动上的指派与调度问题.首先,从问题特点出发,把原始问题分解为指派问题子模型和调度问题子模型.然后,对项目活动间的重叠关系进行识别,将其转化为对指派问题的有效约束,构建数学规划与约束规划相结合的混合算法对问题求解,并采用CPLEX编程实现.研究表明,算法可有效缩减指派问题的可行域,快速地找到问题的近优解,从而提高多技能人力资源的使用效率,是求解项目多技能人力资源指派与调度问题的一个有效方法.     

考虑动态加权A星算法的预翻箱作业优化

为改善堆场作业效率，提出考虑堆场翻箱位规则的集装箱预翻箱作业优化模型并使用动态加权A星算法进行求解，进而确定满足作业规则限制的最优移动序列。基于集装箱装船过程的预翻箱作业，将预翻箱作业过程的贝位布局抽象为A星算法的状态节点，以错误堆叠箱和翻箱迭代深度计算总成本函数，引入动态加权因子控制翻箱迭代方向，提出新颖的搜索分支规则选择有效分支进行搜索。通过上海港码头和相关文献的算例进行实验，结果表明，设计的动态加权启发式函数能够有效改善寻优过程中跳出局部最优解的能力，验证了考虑堆场运作规则-翻箱位规则的算法有效性和稳定性。研究成果能够普遍适用于作业工艺和贝位布局不同的集装箱码头预翻箱作业，能够为堆场运作优化提供决策参考。     

随机活动工期下求解资源约束项目最大期望净现值的动态调度算法

本文研究了随机活动工期下如何调度资源约束项目使得项目的期望净现值最大。首先对问题进行了界定,建立了相应的优化模型,其次针对问题的特点设计了一种动态规划算法。在算法设计的过程中,本文通过对项目网络图结构及不同状态最优值之间关系的分析,优化了动态规划算法状态的生成过程及状态最优值的求解过程,从而加快了算法的求解。使用随机生成的540个不同规模、不同结构的仿真案例对算法的有效性进行了验证,并分析了项目网络特征对算法效率的影响。实验发现:项目的次序强度对算法所需时间有着较大的影响,随着项目次序强度的减小,生成的状态数量会增加,从而计算时间也会增加。本文的研究可以为不确定环境下的项目调度提供决策支持。     

双机成比例无等待流水线重调度干扰管理研究

针对由异速机构成的双机成比例无等待流水线的加工特点,研究了机器扰动工况下的生产重调度问题,提出了兼顾初始调度目标(最小化制造期)和扰动修复目标(最小化工件滞后时间和)的干扰管理方法。在最短加工时间优先(SPT)排序规则的最优解特性分析基础上,证明了右移初始加工时间表是事后干扰管理的最优调度方案,建立了基于SPT规则的事前干扰管理模型,设计了基于理想点趋近的多目标处理策略,提出了离散量子微粒群优化与局部搜索机制相结合的启发式模型求解算法。算例实验结果表明,本文提出的干扰管理模型和算法是有效的。     

人力资源多维分配问题的混合算法

针对已有多维分配问题求解算法复杂、耗时长及精度低等问题,本文将二部图中寻求最优匹配的方法进行推广,运用试分配、饱和路调整和增广路调整对多维分配问题的最优解进行搜索,提出了求解人力资源多维分配问题的最小零面优先分配混合算法和随机试分配混合算法,对算法的有效性进行了理论证明,并分析了算法的时间和空间复杂度;同时通过这两种混合算法对初始零元素数不同的代价矩阵求解时间的计算,以及与Lagrangian松弛算法和剪枝法的耗时、精度的对比,分别得到了两种混合算法的适用性和高效性,最后通过算例验证了算法的有效性。     

二次整数背包问题的新算法

给出了一种求解一般二次整数背包问题(quadratic integer knapsack problem,QIKP)的新算法.该方法把占优的概念与分支定界思想结合,旨在寻求全局最优解.对QIKP给出了占优的定义,通过变量系数之间的关系,很容易找到占优组和极小占优组,从而删除可行域中那些非最优点.新的占优定义对凹的二次函数尤其有效.在理论证明的基础上,设计相应的算法,并进行了数值计算.结果显示,在随机产生的例子中,该算法是有效的,并且与传统的分支定界算法相比,得到了更好的最优解,最优值有了较大的提升.     

一种求解延迟工件数最小的混合流水车间调度问题的模拟退火算法

针对延迟工件数最小的混合流水车间调度问题,给出了一种改进的模拟退火求解算法. 该算法首先给出一个启发式算法来获得初始解,然后用模拟退火算法对初始解改进. 通过交换工件在第一阶段的排序来获得一个新的解,采用最先空闲设备分配规则和先到先被加工规则,对工件在剩余各级的工序进行调度. 实验仿真表明算法是可行有效的.     

建筑废料现场分拣协调调度优化研究

工程项目施工现场废料分拣的效率对施工进度具有重要的影响。通过分析现场废料分拣实施过程,建立了带有限中间缓冲的混合流水车间调度模型。提出了收集阶段作业排序的动态自适应算法和后续设备分配问题的考虑缓冲区的设备分配规则,在此基础上设计了废料分拣模型的启发式算法,平衡各分区工作量,进一步搜索最优解,并推导了问题的一个低界。实验结果表明,所提出算法能很好地对施工现场废料分拣问题进行求解,具有良好的收敛性和较高的时间效率。     

求广义线性比试和问题全局解的新方法

为确定广义线性比式和规划问题(GFP)的全局最优解,提出一个新的分支定界方法.在算法中,分支过程采用单纯形对分规则,且界的估计通过一些线性规划问题的求解完成.给出算法的收敛性证明.数值试验结果显示算法是有效可行的.     

置换流水车间调度问题的中心引力优化算法求解

目前求解置换流水车间调度问题的智能优化算法都是随机型优化方法,存在的一个问题是解的稳定性较差。针对该问题,本文给出一种确定型智能优化算法——中心引力优化算法的求解方法。为处理基本中心引力优化算法对初始解选择要求高的问题,利用低偏差序列生成初始解,提高初始解质量;利用加速度和位置迭代方程更新解的状态;利用两位置交换排序法进行局部搜索,提高算法的优化性能。采用置换流水车间调度问题标准测试算例进行数值实验,并和基本中心引力优化算法、NEH启发式算法、微粒群优化算法和萤火虫算法进行比较。结果表明该算法不仅具有更好的解的稳定性,而且具有更高的计算精度,为置换流水车间调度问题的求解提供了一种可行有效的方法。     

基于资源随机中断的反应性多模式项目调度优化

资源中断是项目实施过程中一种常见现象,它会导致项目进度计划的变更并引起额外的成本。本文研究资源随机中断下的项目调度问题,目标是对基准进度计划进行合理的调整,以最小化由此所造成的额外成本。作者首先对研究问题进行界定,随后构建问题的优化模型。针对模型的NP-hard属性,设计禁忌搜索启发式算法。最后以基准列表算法和随机生成算法为参照,在随机生成的标准算例集合上对算法进行测试,得到如下结论:在可接受的计算时间范围内,禁忌搜索获得的满意解质量明显高于其他两种启发式算法;算法的平均计算时间随着项目活动数的增加而增加,随着网络复杂度、资源强度或资源中断次数的增加而减小;满意解的平均目标函数值,随着项目活动数或网络复杂度的增加而增加,随着资源中断次数的增加而减小,与资源强度无明显关系。     

带有新的迭代格式的内点算法

研究了求解线性规划问题的二阶Mehrotra型预估-矫正内点算法,使用Newton方法求解预估方向和矫正方向,并利用两个方向的一种新的组合方式得到搜索方向.在每次迭代中,要求新的迭代点在中心路径的一个宽邻域内,从而计算出步长参数.通过分析,证明了该算法经过有限次迭代后收敛到问题的一个最优解,并具目前内点算法最好的多项式复杂度O(槡nL).数值实验表明该算法在实践中是有效的.     

动态连续蚁群系统及其在天基预警中的应用

存在监控冲突的天基中段预警传感器调度优化是一个动态、高维、复杂多约束的非线性优化问题,其解空间的高维度与状态复杂性直接制约了智能优化算法的运用.本文以任务分解与任务复合优先权计算为基础,通过二级分离机制将解空间维度与状态复杂性降低至适于连续蚁群(continuous ant-colony optimization,CACO)处理的全局优化形态,构建出相应的优化子路径集.在此基础上,针对监控冲突导致的状态变化特性,从局部搜索递进与募集的角度提出适于传感器调度优化的MG-DCACO(double direction continuous ant-colony optimization based mass recruitment and group recruitment)算法,成功将智能优化算法应用于基于低轨星座的天基中段预警中.最后对算法的收敛性进行论证,并通过与已有规则调度算法的对比得出MG-DCACO算法可获得优于规则调度算法的全局最优解.