混合EDA求解绿色机器人U型装配线平衡问题

针对带序相关约束的绿色机器人第2类U型装配线问题(GRSDUALBP-2),建立了以同时最小化节拍时间和能耗为优化目标的数学模型,并提出一种混合分布估计算法(HEDA)进行求解。首先,在算法编码解码阶段考虑工序与机器人分配的协同优化,设计一种操作分配规则以提高解码效率;然后,在算法优化阶段采用基于概率模型的分布估计算法(EDA),以有效积累和学习优质解信息,并设计3种邻域策略以进一步提高算法局部搜索性能;最后,通过仿真实验与算法对比,验证了HEDA是求解GRSDUALBP-2的有效算法。     

求解混合流水车间调度问题的分布估计算法

针对混合流水车间调度问题(Hybrid flow-shop scheduling problem, HFSP)的特点, 设计了基于排列的编码和解码方法, 建立了描述问题解空间的概率模型, 进而提出了一种有效的分布估计算法(Estimation of distribution algorithm, EDA). 该算法基于概率模型通过采样产生新个体, 并基于优势种群更新概率模型的参数. 同时, 通过实验设计方法对算法参数设置进行了分析并确定了有效的参数组合. 最后, 通过基于实例的数值仿真以及与已有算法的比较验证了所提算法的有效性和鲁棒性.     

分布式有限缓冲区流水车间混合EDA调度北大核心CSCD

在实际工业生产背景下,针对具有NP难特性的分布式有限缓冲区流水车间调度问题,提出了一种混合分布估计算法,用于最小化最大完成时间。首先,由于已有算法无法保证局部搜索后概率模型对优质个体分布统计的准确性,提出了反最小完成工厂映射规则;然后,引入基于Swap邻域和基于Insert邻域的局部搜索,进一步加强算法的局部搜索能力,从而对HEDA全局搜索得到的优质解区域进行细致搜索;最后,通过仿真实验和算法的比较验证HEDA的有效性。     

超启发式分布估计算法求解带软时间窗的同时取送货车辆路径问题

本文针对带软时间窗的同时取送货车辆路径问题(VRPSPDSTW),以最小化车辆行驶总里程和最大化服务准时率为优化目标,提出一种超启发式分布估计算法(HHEDA)进行求解.全局搜索阶段,首先,提出3种启发式规则生成初始个体,以确保初始种群的质量和分散性;其次,根据问题特点,构造3个概率矩阵分别学习和积累优质解的排序信息、客户间的距离信息和捆绑信息,并通过采样概率矩阵生成新个体,以增强算法全局搜索发现解空间中优质区域的能力.局部搜索阶段,将11种邻域操作组成备选集合,进而设计学习型超启发式局部搜索(LHHLS),用于动态选择备选集合中的部分邻域操作构成多种新的有效启发式算法,以执行对解空间中优质区域的深入搜索.最后,仿真实验和算法比较验证了HHEDA的有效性.     

混合分布估计算法求解考虑同步性和准时性的三阶段装配集成调度问题

本文研究以加工–运输–装配同步性和交货准时性的加权和为优化目标的三阶段装配集成调度问题(3sAISP_SP),并基于问题特点设计混合分布估计算法(HEDA)进行求解.首先,分别建立3sAISP SP的数学规划模型和排列模型.其次,在对问题模型特点分析的基础上,设计合理的编码和解码规则,同时利用HEDA中基于概率模型的全局搜索以发现问题解空间存在优质解的区域.然后,为进一步提高算法性能,设计3种局部搜索策略对优质解区域进行细致搜索.进而,在小规模问题下,将HEDA得到的较优解与优化求解器GUROBI得到的最优解进行比较,验证HEDA的求解结果接近最优解;在较大规模问题下,将HEDA与其他有效智能优化算法进行比较,验证HEDA的求解性能.最后,通过对优化目标中不同权重设置的实验分析,给出加工–运输–装配同步性和交货准时性权重设置的合理范围,并得到考虑装配同步性有利于降低中间库存的结论.     

改进蚁群算法求解绿色周期性车辆路径问题北大核心CSCD

针对带时间窗的绿色周期性车辆路径问题(GPVRPTW),同时以最小化运输时间和总能耗为优化目标,提出一种改进蚁群算法(IACO)进行求解。首先,IACO采用三维概率矩阵记录不同配送日期的车辆路径子问题的优质解信息,并设计基于信息熵的信息素更新机制进行合理地学习和积累,从而增强算法全局搜索的引导性;其次,引入基于5种邻域操作的变邻域搜索以提高算法的局部搜索能力;最后,在不同规模问题上进行仿真实验与算法对比,结果验证了IACO的有效性。     

超启发式交叉熵算法求解分布式装配柔性作业车间调度问题

本文针对一类新型两阶段分布式装配柔性作业车间调度问题(DAFJSP),建立问题模型,以最小化最大完工时间为优化目标并提出一种超启发式交叉熵算法(HHCEA)进行求解.首先,设计基于工序序列、工厂分配和产品序列的三维向量编码规则和结合贪婪策略的解码规则,同时提出4种启发式方法以提高初始解的质量.然后,设计高低分层结构的HHCEA,高层为提高对搜索方向的引导性,采用交叉熵算法(CEA)学习和积累优质排列的信息,其中各排列由结合问题特点设计的11种启发式操作(即11种有效的邻域操作)构成;低层为增加在解空间中的搜索深度,将高层确定的每个排列中的启发式操作依次重复执行指定次数并在执行过程中加入基于模拟退火的扰动机制,以此作为一种新的启发式方法执行搜索.最后,通过仿真实验与算法对比验证HHCEA可有效求解DAFJSP.     

经验分布函数概率模型的分布估计算法

连续域分布估计算法普遍采用高斯概率模型,假设变量服从高斯分布。该假设并不具有普遍意义。提出一个任意分布的连续多变量耦合分布估计算法,利用经验分布函数从样本估计分布,采样产生新的个体。描述经验分布函数和逆变换法采样,讨论用样本构造经验分布函数并采样的基本思想,给出一次采样算法及完整的分布估计算法,通过典型函数的仿真实验,说明方法的正确性和有效性。     

求解置换流水线调度问题的混合离散果蝇算法

针对置换流水线调度问题,提出了一种新颖的混合离散果蝇算法.算法每一代进化包括4个搜索阶段:嗅觉搜索、视觉搜索、协作进化和退火过程.在嗅觉搜索阶段,采用插入方式生成邻域解;在视觉搜索阶段,选择最优邻域解更新个体;在协作进化阶段,基于果蝇个体间的差分信息产生引导个体;在退火操作阶段,以一定概率接受最优引导个体从而更新种群.同时,通过试验设计方法对算法参数设置进行了分析,并确定了合适的参数组合.最后,通过基于标准测试集的仿真结果和算法比较验证了所提算法的有效性和鲁棒性.     

混合离散教与学算法求解复杂并行机调度问题

针对制造行业中广泛存在的一类复杂并行机调度问题, 即带到达时间、多工序、加工约束和序相关设置时间的并行机调度问题(Parallel machine scheduling problem with arrival time, multiple operations, process restraints and sequence-dependent setup times, PMSP_AMPS), 建立问题的排序模型并提出一种混合离散教与学优化算法进行求解, 优化目标为最小化最大完工时间.首先, 根据标准教与学算法(Teaching-learning-based optimization, TLBO)中两阶段个体更新公式的特点, 在保留每一阶段个体更新公式框架不变的前提下, 对公式中具体改变实数个体或向量的每个核心操作均用所设计的排列操作进行替换, 使其可直接在离散问题解空间中执行基于标准教与学算法机理的全局搜索, 从而明显提高了原算法的全局搜索效率.其次, 采用交换操作和插入操作构造了一种简洁有效地变邻域局部搜索, 对全局搜索发现的优质解区域进行细致搜索, 从而进一步增强了算法的性能.通过对不同测试问题的仿真实验和算法比较, 验证了所提算法可有效求解PMSP_AMPS.     

置换流水车间调度问题的两阶段分布估计算法

针对置换流水车间调度问题,以最小化总流水时间为目标,提出了一种新颖的两阶段分布估计算法。第一阶段先利用NEH（Nawaz-Enscore-Ham,NEH）启发式构造一个较优的初始个体,然后随机生成初始种群,为保留种群的多样性,提出一种择优机制来选择个体并建立概率模型,同时在当代种群中利用精英机制保留当代种群中的最优解,最后利用概率模型采样并生成下一代种群。第二阶段采用插入、互换操作算子对第一阶段得到的最优解进行邻域搜索,来提高分布估计算法的全局搜索能力,阻止其陷入局部最优解。通过对算例进行实验、对比和分析,证明该算法的可行性和有效性。     

求解柔性流水车间调度问题的高效分布估算算法

针对最小化最大完工时间的柔性流水车间调度,利用事件建模思想,线性化0-1混合整数规划模型,使得小规模调度问题通过Cplex可以准确求解,同时设计了高效分布估算算法来求解大规模调度问题.该算法采用的是一种新颖的随机规则解码方式,工件排序按选定的规则安排而机器按概率随机分配.针对分布估算算法中的概率模型不能随种群中个体各位置上工件的更新而自动调整的缺点,提出了自适应调整概率模型,该概率模型能提高分布估算算法的收敛质量和速度.同时为提高算法局部搜索能力和防止算法陷入局部最优,设计了局部搜索和重启机制.最后,采用实验设计方法校验了高效分布估算算法参数的最佳组合.算例和实例测试结果都表明本文提出的高效分布估算算法在求解质量和稳定性上均优于遗传算法、引力搜索算法和经典分布估算算法.     

A hybrid variable neighborhood search for solving the hybrid flow shop scheduling problem

This paper proposes a hybrid variable neighborhood search (HVNS) algorithm that combines the chemical-reaction optimization (CRO) and the estimation of distribution (EDA), for solving the hybrid flow shop (HFS) scheduling problems. The objective is to minimize the maximum completion time. In the proposed algorithm, a well-designed decoding mechanism is presented to schedule jobs with more flexibility. Meanwhile, considering the problem structure, eight neighborhood structures are developed. A kinetic energy sensitive neighborhood change approach is proposed to extract global information and avoid being stuck at the local optima. In addition, contrary to the fixed neighborhood set in traditional VNS, a dynamic neighborhood set update mechanism is utilized to exploit the potential search space. Finally, for the population of local optima solutions, an effective EDA-based global search approach is investigated to direct the search process to promising regions. The proposed algorithm is tested on sets of well-known benchmark instances. Through the analysis of experimental results, the high performance of the proposed HVNS algorithm is shown in comparison with four efficient algorithms from the literature.     

一种求解多维背包问题的混合分布估计算法

针对多维背包问题（MKP）,提出一种基于分布估计算法的混合求解算法,该算法基于优势种群构建概率模型,并基于概率模型采样产生新个体;同时,提出一种基于MKP问题信息的修复机制,有效修复采样后种群中的不可行解．另外,设计了一种自适应的局部搜索操作,以增强算法的局部搜索能力,基于标准测试集的仿真结果和算法比较验证了所提出的混合算法的有效性和鲁棒性．     

A hybrid estimation of distribution algorithm for solving the resource-constrained project scheduling problem

In this paper, a hybrid estimation of distribution algorithm (HEDA) is proposed to solve the resource-constrained project scheduling problem (RCPSP). In the HEDA, the individuals are encoded based on the extended active list (EAL) and decoded by serial schedule generation scheme (SGS), and a novel probability model updating mechanism is proposed for well sampling the promising searching region. To further improve the searching quality, a Forward-Backward iteration (FBI) and a permutation based local search method (PBLS) are incorporated into the EDA based search to enhance the exploitation ability. Simulation results based on benchmarks and comparisons with some existing algorithms demonstrate the effectiveness of the proposed HEDA.     

Solving system-level synthesis problem by a multi-objective estimation of distribution algorithm

In this paper, the system-level synthesis problem (SLSP) is modeled as a multi-objective mode-identity resource-constrained project scheduling problem with makespan and resource investment criteria (MOMIRCPSP-MS-RI). Then, a hybrid Pareto-archived estimation of distribution algorithm (HPAEDA) is presented to solve the MOMIRCPSP-MS-RI. To be specific, the individual of the population is encoded as the activity-mode-priority-resource list (AMPRL), and a hybrid probability model is used to predict the most promising search area, and a Pareto archive is used to preserve the non-dominated solutions that have been explored, and another archive is used to preserve the solutions for updating the probability model. Moreover, specific sampling mechanism and updating mechanism for the probability model are both provided to track the most promising search area via the EDA-based evolutionary search. Finally, the modeling methodology and the HPAEDA are tested by an example of a video codec based on the H.261 image compression standard. Simulation results and comparisons demonstrate the effectiveness of the modeling methodology and the proposed algorithm.     

基于分布估计算法的连续函数全局优化问题研究

分布估计算法从宏观的角度建立一个概率模型,用来描述解空间的分布,从而通过进化计算获得优势个体。目前,离散型分布估计算法研究已经比较成熟,而连续型分布估计算法研究进展缓慢。采用均匀分布缩小采样领域的思想,设计新的分布估计算法求解连续型优化问题。实验数据表明,该分布估计算法对于求解连续型问题是有效的。     

A bi-population based estimation of distribution algorithm for the flexible job-shop scheduling problem

In this paper, an effective bi-population based estimation of distribution algorithm (BEDA) is proposed to solve the flexible job-shop scheduling problem (FJSP) with the criterion to minimize the maximum completion time (makespan). The BEDA stresses the balance between global exploration and local exploitation. In the framework of estimation of distribution algorithm, two sub-populations are used to adjust the machine assignment and operation sequence respectively with a splitting criterion and a combination criterion. At the initialization stage, multiple strategies are utilized in a combination way to generate the initial solutions. At the global exploration phase, a probability model is built with the superior population to generate the new individuals and a mechanism is proposed to update the probability model. At the local exploitation phase, different operators are well designed for the two sub-populations to generate neighbor individuals and a local search strategy based on critical path is proposed to enhance the exploitation ability. In addition, the influence of parameters is investigated based on Taguchi method of design of experiment, and a suitable parameter setting is determined. Finally, numerical simulation based on some widely used benchmark instances is carried out. The comparisons between BEDA and some existing algorithms as well as the single-population based EDA demonstrate the effectiveness of the proposed BEDA in solving the FJSP.