基于全局边缘排序的超启发算法在绿色物流选址-路径优化问题中的应用

为了解决目前物流选址-路径优化问题(LRP),提出一种以低碳排放量、配送中心选址规划和车辆路径规划为目标的双目标LRP模型。针对传统启发式算法在解决大规模LRP时的通用性差、效率低的缺点,设计出一种以选择函数法作为选择策略、以基于全局边缘排序的评价指标作为接受策略的超启发算法。通过求解基准测试实例,该算法在解决所提LRP模型时,能准确、高效、智能地设计出调度方案。与传统启发式算法以及性能良好的超启发算法在解的整体质量、单个解收敛效率等方面进行对比,验证了所提方法的可行性和有效性。

基于强化学习的超启发算法求解有容量车辆路径问题

为了更高效地求解物流优化领域中的有容量车辆路径问题,减少陷入局部最优的情况,提出一种基于强化学习的超启发算法。设计了算法的高层启发式策略,包括选择策略和解的接受准则:基于学习机制,使用强化学习中的深度Q神经网络算法构造该算法的选择策略,对底层算子的性能进行奖惩评价;利用奖惩值以及模拟退火作为算法的接受准则,对优质解建立序列池,从而引导算法更有效地搜索解空间,并采用聚类思想提升初始解的质量。对有容量车辆问题的标准算例进行计算,并与其他算法对比,统计分析了最优值、误差率和平均值,实验结果表明了所提算法在该问题求解上的有效性和稳定性,总体求解效果优于对比算法。

超启发算法研究进展综述

超启发算法是一类新兴的优化方法,通过机器学习、算法选择、算法生成等技术求解组合优化等问题,具备跨问题领域求解的能力。针对超启发算法研究进展进行综述和讨论。首先,梳理超启发算法的定义、结构、特点和分类;其次,归纳选择式超启发算法和生成式超启发算法的研究进展及相关技术,包括选择低层启发式算法采用的学习方法,迭代计算中的移动接受策略,低层启发式算法的生成方法;最后,讨论现有超启发算法研究中存在的不足及未来的研究方向。

基于蚁群选择超启发算法的低碳选址—路径问题

针对有容量约束的低碳选址—路径问题,提出一种基于蚁群选择机制的超启发算法用于模型求解,即将蚁群选择机制作为超启发算法的选择策略。首先对蚁群选择策略进行参数寻优,将高层策略进行对比实验分析得出最优的接受准则,即只接受好解(OI),并与得到的蚁群选择策略参数进行优化组合。此外,与其他算法的对比实验验证了所提算法的有效性。最后分别对以最少碳排放量和最小成本为目标的模型进行求解分析对比,结果表明考虑碳排放的选址—路径模型可以有效减少碳排放量。

基于改进超启发算法的通信卫星任务松弛调度方法

在卫星通信保障压力不断增加的背景下,需要不断提高通信卫星任务调度的效率。任务调度的矛盾主要集中在通信任务的申请时间和资源带宽的冲突上,文中通过松弛任务申请条件的方式,建立通信卫星任务调度的松弛模型,通过小幅度的时间和带宽调整来减少任务之间的冲突,增加任务获取卫星资源的可能性,提高任务的可执行率。在此基础上,提出一种基于人工蜂群的超启发算法对模型进行求解,该算法采用人工蜂群算法作为高层选择策略,并根据卫星资源调度问题的特点选择7种低层启发算子进行序列优化,同时采用模拟退火方式作为接受准则避免陷入局部最优。最后通过仿真实验及算法对比验证了提出的松弛模型和改进算法的有效性。

基于阈值超启发算法的建设资源平衡优化

提出了阈值超启发算法,以解决资源限制的项目调度或资源分配中资源均衡问题。首先,在元启发式过程域中通过设计阈值来设置启发式算法的优先级,通过优先级来判别选择进入的元启发式算法。其次,用软件运行解决方案域,计算资源分配值。最后,通过举例验证,证明所提出的方法提高了项目的自动均衡功能,有效地增强了资源分配能力。

混合超启发式算法求解复杂两级车辆路径问题

针对模糊需求下的绿色两级车辆路径问题,以最小化车辆运营成本和油耗成本之和为优化目标,提出一种混合超启发式算法进行求解.首先,考虑两级问题解空间庞大且相互耦合,设计一种聚类分解策略将该问题分解为多个子问题,以合理缩小问题搜索空间;然后,提出增强超启发式分布估计算法(enhanced hyperheuristic estimation of distribution algorithm,EHHEDA)对各个子问题进行求解,进而获得原问题的解.EHHEDA基于超启发式算法框架,在高层策略域设计一种基于三维概率模型的分布估计算法,动态确定由底层操作域中各搜索算子所组成的排列(即高层个体),可有效控制和引导整个算法的搜索行为;同时,在底层操作域设计10种有效邻域搜索算子,并加入重升温操作的模拟退火机制作为问题解(即底层个体)的接受准则,有利于在问题解空间中执行深入搜索.仿真实验结果表明,所提出的算法在大多数测试集上优于近年来用于求解类似问题的算法,验证了所提出算法的有效性.

基于K-means聚类的超启发式跨单元调度方法

结合我国制造业实际生产状况,针对柔性作业车间跨单元调度问题,提出一种基于K-means聚类的超启发式算法。应用K-means聚类算法将相近属性的实体划入相应“工件簇”决策块中,采用蚁群算法为每个决策块选择启发式规则;对每个决策块内的实体运用相应的启发式规则产生调度解。仿真结果表明:该算法以决策块的形式适度增大了计算粒度,有效降低了算法时间复杂度,以聚类的方式将具有相近属性的被加工实体进行聚集,有利于为不同属性的实体选择合适的规则。该算法提高了计算效率,具有较好的优化性能,是解决柔性跨单元调度的一种有效算法。

超启发式人工蜂群算法求解多场景鲁棒分布式置换流水车间调度问题

本文考虑现实中广泛存在的加工时间不确定的分布式置换流水车间调度问题(DPFSP),研究如何建立问题模型和设计求解算法,方可确保算法最终获得的解在多个典型DPFSP场景下,均具有能满足客户期望的较小优化目标值(即makespan值).在问题建模方面,首先,采用场景法构建多个不同典型场景以组成场景集(每个场景对应1个具有不同加工时间的DPFSP),并设定合适的makespan值作为场景阈值,用于在评价问题解时从场景集中动态筛选出“坏”场景子集;其次,在常规优化目标makespan的基础上,结合“坏”场景子集概念提出可实现鲁棒调度的新型优化目标,用于引导算法每代加强对当前“坏”场景子集中每个DPFSP场景对应解空间的搜索;然后,结合所提的新型优化目标,建立基于多场景的鲁棒DPFSP(MSRDPFSP).在算法设计方面,提出一种超启发式人工蜂群算法(HHABC)对MSRDPFSP进行求解.HHABC分为高、低两层结构,其中低层设计6种启发式操作(HO),高层采用人工蜂群算法控制和选择低层HOs来不断生成新的混合启发式算法,从而实现在不同场景对应解空间中的较深入搜索.在不同规模测试问题上的仿真实验与算法对比,验证了HHABC的有效性.

超启发式三维EDA求解绿色双边装配线平衡问题

针对绿色机器人的第Ⅰ类双边装配线平衡问题(green robotic two-sided assembly line balancing problem of type-Ⅰ, GRTALBP-Ⅰ),建立问题模型并提出一种超启发式三维分布估计算法(hyperheuristic three dimensional estimation of distribution algorithm, HH3DEDA)进行求解。在HH3DEDA中,结合问题特征,设计基于工序选择因子的组合编码,进而设计高低分层结构的HH3DEDA。在高层,采用三维概率矩阵学习优质高层个体中块结构及其分布信息,后通过采样该矩阵以生成新的高层个体,其中高层个体由结合问题特点设计的12种启发式操作的排列构成;在低层,将高层每个个体所确定启发式操作排列作为一种新的启发式算法对GRTALBP-Ⅰ解空间执行较深入搜索。同时,引入机器人开关机节能策略,进一步提升所获取非支配解的质量。通过仿真对比实验,验证了所提算法的有效性。

基于超启发式算法的配电网线路过载保护控制协调优化方法

在配电网线路过载时,对功率和负荷分配不均匀,导致线路的故障率有所增加,对此,研究基于超启发式算法的配电网线路过载保护控制协调优化方法。基于超启发式算法组建过载保护控制模型,以最小目标向量分类配配电网线路运行,设置其目标函数,以不同的线路运行资源为执行状态,定义运行保护周期,确定线路过继保护时间,设置两组线路流相,建立两相同步旋转坐标系,对配电网线路的过载量进行调节,对线路功率进行分量调节,实现配电网线路过载保护控制的协调优化。

云环境下超启发式能耗感知调度算法

能耗感知调度的研究对云计算数据中心的可持续发展有着重要意义。能耗感知调度是一个NP难的多目标优化问题,目前云环境下的任务调度算法较少考虑能耗问题,且不能实现对能耗的灵活管理,随机搜索算法是一种解决该问题的有效途径,但其计算开销大,收敛速度慢。将异构云环境下的能耗感知调度问题定义为一个带约束的问题,即在一定的完成时间下优化系统能耗,以实现对能耗的灵活管理。此外,提出了基于在线学习的超启发式算法(OLHH),该算法结合电压调节技术,在设计了简单高效的启发式策略集的基础上,引进超启发式算法,并采用在线学习的方式跟踪启发式策略的表现,实现对启发式策略的合理管理,从而达到提高算法的收敛性能的目的。模拟实验表明,该算法能够实现系统能耗的灵活管理,且比传统的随机搜索算法有着更好的收敛性能。

超启发式文化基因算法优化生产与预维修集成调度问题

鉴于传统车间调度通常认为机器始终处于可用状态而有悖于实际生产环境的不确定性,考虑机器使用过程中需要周期性的进行预防性维修的情况,以最大完工时间和预防性维修总成本为目标,建立了机器预防性维修和柔性作业车间调度的集成优化模型。针对该模型设计了年龄模型下的3种不同的集成策略,并开发了一种超启发式文化基因算法,算法采用两层结构,顶层采用文化基因算法的搜索机制,底层是全局搜索算子库和局部搜索算子库,采用基于概率的改进的自适应算子选择机制。实验表明,该算法可以有效求解生产调度与预维修集成优化问题。通过对比可知,同步集成策略表现最优。将役龄模型应用于同步集成策略中,进一步优化了同步集成调度策略,在保证机器可靠性的前提下降低了最大完成时间和预防性维修总成本。

基于超启发式的多星协同任务规划算法研究

针对多星协同任务调度问题,分析了问题实际约束和问题调度目标,提出了多星协同任务规划调度模型。提出了一种新的基于超启发式算法应用框架对多种算法的管理和调度,研究超启发式多星对地观测任务规划求解方法。最后实验数据证明了算法的有效性和适用性。

时间依赖型同时取送货VRP及超启发式算法

为有效地协调正逆向物流,更好地体现城市物流配送速度时变的特点,降低物流配送成本,以时间依赖型同时取送货车辆路径问题为对象,建立其数学规划模型;设计了基于禁忌搜索的超启发式算法对其进行求解。在算法高层,设计了基于禁忌搜索评分制的选择策略及模拟退火的接收准则,实时监控底层启发式算子的性能并选择最优算子。通过基准实例测试及实验对比分析,表明了该算法能快速地找到满意解,所设计高层策略能保证算法跳出局部最优并快速收敛,从而证明了所提算法求解该问题的有效性。

超启发式遗传算法柔性作业车间绿色调度问题研究

针对启发式算法通用性较差的问题,建立了多目标柔性作业车间绿色调度模型,设计了一种超启发式遗传算法对问题进行求解。首先,建立了以最大完工时间和最小能耗为目标的柔性作业车间绿色调度模型,并设计了超启发式遗传算法对模型进行优化求解;然后,对于高层启发式策略采用遗传算法,随机生成初始种群,对种群进行了选择、交叉和变异操作,并且在常规算子基础上,结合柔性作业车间调度特点设计了9种适应该问题的算子,同时对于低层问题域种群采用了贪婪初始化方法生成;最后,通过基准算例验证了算法的运行效率,通过实例验证了算法的性能。研究结果表明:与参考算法相比,采用贪婪初始化生成初始种群的算法其收敛速度较快,运行效率较高,且不容易陷入局部最优;通过超启发式遗传算法获得的解中最大完工时间的最小值为64,最小能耗为647,解的质量不差于其它算法,算法的通用性较强。

进化式超启发算法求解多车型低碳选址-路径问题

为了降低物流配送成本和减少CO2排放量,提出一种综合考虑多车型和同时取送货的低碳选址-路径问题,并构建三维指数混合整数规划模型.针对所提问题,设计一种进化式超启发式求解算法,即在超启发式算法框架下,采用进化式策略作为高层学习策略,以实时准确地监控底层算子的性能信息并选择合适的底层算子,包括量子选择、蚂蚁策略、蛙跳机制以及自然竞争等.同时,挖掘算子性能信息以构建自适应接收机制,引导全局搜索,加快算法收敛速度.通过对不同规模实例的仿真实验与对比分析,验证了4种进化式超启发式算法在求解物流配送多车型同时取送货低碳选址-路径问题模型上的有效性与鲁棒性.

课程表问题的一种模拟退火超启发式算法

课程表问题是经典的组合优化问题,属于NP-hard问题。长期以来人们一直都在寻求快速高效的近似算法,以便在合理的计算时间内准确解决大规模课程安排问题,并提出许多有效且实用的启发式和元启发式算法。在此基础上提出了一种基于多个图染色启发式规则的模拟退火超启发式算法。在超启发式算法的框架中,用模拟退火算法作为高层搜索算法,多个图染色启发式规则为底层的构造算法。与现有的方法相比,该算法具有很好的通用性,可以很容易推广到考试时间表、会议安排、旅行商问题、背包问题等应用领域。实验表明,该算法是可行有效的,且无一例时间、空间冲突。

基于超启发式算法的选址-路径问题研究

为了降低物流配送过程中车辆的碳排放,采用具有良好通用性的超启发式算法对低碳选址路径问题进行求解。将蛙跳算法作为超启发式算法的高层选择策略,并在蛙跳算法中提出了基于最长公共子序列的相似度计算方式代替原有的相似度计算,而采用动态规划的方法对个体间的最长公共子序列进行计算。实验结果表明:提出的相似度计算方式能更直观地反映个体之间的相似性,具有良好的通用性,并且在低碳选址-路径问题上获得更优秀的解。

基于机器学习算法的卷烟营销智能客户拜访策略研究

为提高卷烟行业客户经理的工作效率和服务质量,提出一种基于机器学习算法的卷烟营销智能客户拜访策略。在构建卷烟客户价值分类模型的基础上,利用K均值聚类机器学习算法对零售客户进行分类,合理设置LKH超启发算法和Dijkstra最短路径算法的参数,对客户经理拜访路径进行最优规划和智能导航。仿真结果表明,基于机器学习算法的卷烟营销智能客户拜访策略显著提高了客户经理人均拜访户数、商户满意度,大大缩减了户均在途时间和商户拜访服务覆盖周期。文中提出的策略有助于推动卷烟营销工作质量变革、效率变革和动力变革。