一种最速下降的贪婪迭代算法

压缩传感应用于图像压缩重构的算法通常有凸优化算法和贪婪迭代算法两大类.一般而言,凸优化算法重构概率高、速度较慢,贪婪迭代算法具有较快的重构速度,但损失了重构质量.结合凸优化算法中的最速下降法及贪婪迭代算法中的正交匹配算法(OMP),提出了一种新的算法,并应用于一维信号和二维图像信号的压缩重构实验,且深入对比分析了不同降采样矩阵对新算法的影响.结果发现,对同一降采样矩阵,即使图像的纹理不同,新算法在重构质量及重构时间上都优于原始的OMP算法.

改进迭代贪婪算法求解可重入流水车间调度问题

可重入混合流水车间是在混合流水车间的基础上增加了可重入特性,具有更高的调度复杂性。为了求解可重入混合流水车间调度问题,首先建立了调度优化模型,优化目标为最小化最大完工时间,然后提出一种带精英调整的学习型迭代贪婪算法(LIG-EA)。LIG-EA算法采用基于工件的编码方式,对重组后的染色体进行解码。种群分为精英个体和普通个体两部分,对精英个体进行精英破坏重建和基于关键工件的染色体调整,对普通个体进行学习机制的构建和普通个体的破坏重建。为提高初始种群质量,采用NEH启发式算法进行种群初始化,并针对可重入混合流水车间的重入特性,在重建操作中增加了插入有效性判断,提高了算法的运行速度。通过大量实验表明LIG-EA算法能够有效求解可重入混合流水车间调度问题。

求解能耗成本平衡的分布式阻塞流水线调度群体迭代贪婪算法

在经典分布式流水车间调度问题基础上,本文构建了具有序列相关准备时间的分布式阻塞流水线调度问题(DBFSP SDST)的混合线性整数规划模型(MILP),以均衡各工厂能耗成本为优化目标,提出了基于群体优化的迭代贪婪算法(PEIG).该算法针对零缓冲区和多工厂生产模式,设计了问题特性的启发式方法;针对迭代贪婪算法(IGA)的优势和不足,提出了基于群体的局部搜索策略、多邻域搜索结构和增强的跨工厂破坏重构方法,以进一步平衡所提算法的全局探索和局部搜索能力.通过270个测试算例的数值仿真,以及与最新4种代表算法的统计比较,本文验证了所提PEIG算法的优越性,能为中大规模的DBFSP SDST提供更优的调度方案.

求解流水车间订单接受与调度问题的多线程并行迭代贪婪算法

针对流水车间实际生产过程中交货期短和生产能力不足的困难,研究了流水车间订单接受与调度问题,并以企业生产总净利润最大化为目标建立了数学优化模型。鉴于传统迭代贪婪算法求解流水车间调度问题的优势与不足之处,提出了一种多线程并行迭代贪婪算法(MPIG)。在算法的初始化阶段以及破坏重构阶段分别设计基于NEH(Nawaz-Enscore-Ham)的初始解产生方法以及融合不同破坏优先级的破坏方式。为提高算法搜索效率,提出了一种多线程并行搜索策略。首先利用二分查找算法快速找到订单在待插入序列中的拒绝点,随后通过多个线程同时搜索订单在序列中的局部最优位置,并最终找到订单最佳插入位置。实验结果表明,与解决类似生产调度问题的相关智能优化算法相比,所提出的MPIG具有更好的求解质量以及求解稳定性。同时,与实际生产过程中常用的启发式调度方法相比,所提出的算法在目标值上表现出不低于11%的改进率,可以有效增加企业生产总净利润,减小拖期成本。

基于种群的多层次迭代贪婪算法优化阻塞流水车间调度问题

针对以最小化最大完工时间为目标的阻塞流水车间调度问题,提出一种有效的基于种群的多层次迭代贪婪算法进行求解。算法基于排列形式进行编码,提出NEH_PF(Nawaz-Enscore-Ham&profile fitting)算法构造初始种群,以提高初始解的质量;设计了多层次迭代贪婪算法,并基于插入、交换策略对个体进行变异,基于Path-Relinking算法对个体进行交叉,以提高个体局部搜索能力,并提出部分交叉策略来更新种群。通过标准实例测试,验证了所提算法的有效性。

求解具有混合约束流水车间调度问题的迭代贪婪算法

基于传统的流水车间调度问题,提出一种有限等待约束、阻塞约束以及无等待约束共存的混合约束流水车间调度问题。以问题的最小化最大完工时间为目标,提出一种利用迭代贪婪算法进行求解的方法。该方法利用改进的NEH算法计算初始解,通过迭代贪婪算法进行优化,并设计多点交叉策略和插入邻域搜索策略提高解的质量。通过经典实例测试,验证了所提算法的有效性。

基于贪婪-快速阈值迭代的SAR地面动目标稀疏表征算法

合成孔径雷达地面动目标成像(Synthetic Aperture Radar Ground Moving Target Imaging,SAR-GMTIm)技术通过在静止场景的SAR图像中检测运动目标响应,实现针对运动目标的重聚焦成像。通常情况下,地面运动目标回波响应相对于静止场景的回波(即杂波)具有较强的稀疏性,增强SAR-GMTIm成像结果的稀疏特征有利于目标分类和识别。现有的一阶算法如阈值迭代算法(Iterative Shrinkage-thresholding Algorithm,ISTA)及其改进方法,快速阈值迭代算法(Fast Iterative Shrinkage-thresholding Algorithm,FISTA)都可用于SAR-GMTIm稀疏特征增强,但都存在运算效率偏低,收敛速度较慢的问题。针对以上问题,本文提出了一种贪婪-快速阈值迭代算法(Greedy Fast Iterative Shrinkage-thresholding Algorithm,Greedy FISTA)用于SAR-GMTIm稀疏特征恢复。该算法基于重启动框架对FISTA进行改进,缩短了算法重启间隔和振荡周期,拥有比FISTA更快的收敛速度。本文利用Greedy FISTA针对SAR-GMTIm的仿真复数据以及美国空军实验室的Gotcha实测雷达数据进行成像实验,并对比Greedy FISTA和FISTA、ISTA在SAR动目标成像中达到同等精度所需的迭代次数,再结合相变热力图分析法对比三种算法的恢复性能。实验结果表明Greedy FISTA应用于SAR-GMTIm系统具有良好的成像效果,且在收敛速度和稀疏信号恢复方面相较传统阈值迭代算法及快速阈值迭代算法有明显优势。

基于改进迭代贪婪算法的产品服务系统订单调度优化

针对拥有多条生产线和多支安装团队的服务型制造企业,研究了产品服务系统订单的调度问题。以最小化所有订单的交付时间总和为目标,考虑了各订单的最早允许服务时间约束,构建了产品服务系统订单调度问题的混合整数线性规划模型,并设计了改进的迭代贪婪算法进行求解。在该算法中,首先根据问题的特点设计了基于订单排序的整数编码与解码方法,其次基于最早允许服务时间排序提出一种改编NEH初始化方法,然后结合插入邻域和交换邻域提出一种随机邻域搜索算法,并通过嵌入针对部分解的邻域搜索优化提出了一种破坏、优化与重建过程作为扰动算子,最后基于轮盘赌的选择策略设计了一种新的接受准则。在仿真实验中,检验了所提局部搜索算法、扰动算子和接受准则的有效性,并将改进迭代贪婪算法与经典迭代贪婪算法进行了对比分析,同时探讨了关键参数对算法性能的影响。结果表明,所提出的改进策略非常有效,显著提升了改进后迭代贪婪算法的求解效率,且该算法对于生产线数量、安装团队数量和最早允许服务时间等因素均表现出了较好的鲁棒性。

基于混合迭代贪婪算法的分布式车间调度研究

分布式协同生产已逐渐成为经济全球化和生产国际化背景下的主要生产方式。以总装配时间为优化目标,提出一种混合迭代贪婪(HIG)算法,求解分布式装配阻塞流水车间调度问题(DABFSP)。在HIG算法的初始化阶段,采用问题驱动的构造启发式方法生成初始解。在HIG算法的破坏-重构阶段,采用基于邻域信息的扰动策略更新可行调度序列。在HIG算法的局部搜索阶段,使用基于邻域结构的插入操作进一步更新可行解。以一定概率接收较差调度序列进入下一代,从而避免算法早熟收敛。在试验阶段,选取了以不同工件数、机器数、工厂数和产品数为组合的共计900个问题实例,测试、比较了HIG算法和其他8种先进对比算法的性能。通过统计学分析得出结论:在求解DABFSP时,所提出的HIG算法具有显著的优势。

基于种群迭代贪婪算法无等待流水车间调度

针对无等待流水车间调度问题,提出一种基于种群迭代的改进贪婪算法解决以最小化最大完工时间为目标的此类问题。首先,采用改进NEH(Nawaz–Enscore–Ham)算法提升初始种群的质量,提高种群的多样性,并得出初始解,确定最优个体;其次,采用种群迭代贪婪算法对确定的种群序列进行破坏与重新构建,将新序列插入指定位置,并对获得的候选方案进行本地搜索,获得新的解决方案,同时取代劣势解决方案;最后,通过仿真实例将种群迭代贪婪算法与其他智能优化算法在平均相对偏差率、最佳相对偏差率、算法收敛性上进行对比,结果表明种群迭代贪婪算法求解所提问题的高效性和稳定性。

零空闲置换流水车间总延误最小迭代贪婪算法

研究以总延误时间为目标且具有释放时间约束的零空闲置换流水车间调度问题。基于贪婪选择和作业对交换,设计基本迭代贪婪算法IGA;结合先到先服务FCFS排产规则对初始解的构建进行改进,并提出作业对多次循环交换对邻域搜索进行优化,递进设计了3种迭代贪婪算法FIGA、MIGA、FMIGA。通过不同规模的数据实验和与对比算法的比较分析,验证了FMIGA算法的有效性。结果显示该算法不仅能提高解的质量,而且具有良好的稳定性,为求解具有释放时间的零空闲置换流水车间总延误问题提出了一种新方法。

基于改进迭代贪婪算法的预制构件调度研究

迭代贪婪算法是一种具有较强局部搜索能力的元启发式算法,但由于传统迭代贪婪算法搜索范围过大,搜索效率有限,为了进一步提升传统迭代贪婪算法的搜索能力,考虑到阈值接受算法具有能缩小搜索范围的特点,提出了一种改进的迭代贪婪算法解决流水车间预制生产的订单接受与调度问题;该改进算法是在破坏原调度序列后加入一种基于构造启发式规则的重建策略,并结合阈值接受算法的自适应接受准则用以跳出局部最优;经大量仿真实验结果显示,与传统迭代贪婪算法、禁忌搜索算法以及遗传算法对比,改进的迭代贪婪算法具有更好的求解质量和鲁棒性。

基于贪婪算法的高分辨信号源DOA估计

确定辐射源的来波方向(DOA)是阵列信号处理的重要研究内容,已经广泛应用于雷达、声纳和无线通信等领域。本文研究了远场窄带信号源的DOA高分辨估计问题。利用信号来波方向在空域具有稀疏性的特点,建立了远场窄带信号源的稀疏表示模型。根据协方差矩阵的特征值分解和贪婪匹配追踪算法原理提出了一种基于特征值分解的多重正交匹配追踪算法(EIG-MOMP)。首先,利用特征值分解对阵列接收数据进行降维处理。这一降维操作使得问题转化为了一个具有多重观测向量(MMV)的欠定方程求解问题。接着利用MOMP算法对降维后的数据进行处理,最终得到信号的DOA估计值。该算法实现了在低信噪比下远场窄带信号源的高分辨DOA估计,并具有较低的运算复杂度。将本文提出的算法与传统的Capon算法、多重信号分类算法(MUSIC)以及正交匹配追踪算法(OMP)进行了对比。结果证明,该算法在低信噪比下能取得较好的DOA估计效果,可以针对任意的相干信号源,并且具有高分辨率的优点。

变量块内部迭代算法求解零空闲流水车间问题

零空闲流水车间问题(NIFSP)是流水车间问题中带有约束条件的典型NP-hard问题,在大多数现实场景下,零空闲约束是对机器的基本要求。而目前关于NIFSP问题提出的算法对于较大规模算例、综合性能及参数调整的灵活性较差。为此,以最小化最大完工时间为目标,提出了一种可变内部迭代算法VIIA。在VIIA的初始化阶段,使用改进的FRB5产生初始解,提高了FRB5的效率,在保证算法性能的同时极大地缩短了CPU消耗时间。在破坏重建阶段,通过增加对移除工件块数量的内部迭代,从而灵活调整参数值。VIIA增大了邻域搜索,以适应不同规模的算例。为了验证VIIA算法的性能,将该算法与在流水车间调度问题中表现优秀的几种算法进行了比较。实验结果证明了VIIA在NIFSP问题求解上性能的优越性,并且在最优解的搜索上,性能明显优于对比算法。

一种新的混合粒子群算法求解置换流水车间调度问题

针对粒子群算法易早熟的缺点,提出了一种结合迭代贪婪(IG)算法的混合粒子群算法。算法通过连续几代粒子个体极值和全局极值的变化判断粒子的状态,在发现粒子出现停滞或者粒子群出现早熟后,及时利用IG算法的毁坏操作和构造操作对停滞粒子和全局最优粒子进行变异,变异后利用模拟退火思想概率接收新值。全局最优粒子的改变会引导粒子跳出局部极值的约束,增加粒子的多样性,从而克服粒子群的早熟现象。同时,为了使算法能更快找到或逼近最优解,采用了循环迭代策略,在阶段优化结果的基础上,周而复始循环迭代进行求解。将提出的混合粒子群算法应用于置换流水车间调度问题,并在问题求解时与几个具有代表性的算法进行了比较。结果表明,提出的算法能够克服粒子群早熟,在求解质量方面优于其他算法。

有效的混合粒子群算法求解阻塞流水车间调度问题

针对以最小化完工时间为目标的阻塞流水车间调度问题,提出了一种混合粒子群算法进行求解。该算法将粒子群算法与迭代贪婪算法进行了结合。利用改进的迭代贪婪算法产生问题初始优化解,利用粒子群算法进行全局优化。针对粒子群算法易早熟收敛的特点,提出一种判断粒子停滞和粒子群早熟的方法,并在发现种群早熟后利用迭代贪婪算法的构造操作和毁坏操作对相关粒子进行变异,同时按照一定比例对最差的部分粒子进行重新初始化,以增加种群多样性。通过标准实例测试,验证了所提算法的有效性。

混合迭代贪婪算法求解准时生产分布式流水线调度问题

针对以最小化总延迟时间为优化目标的分布式置换流水线问题(distributed permutation flowshop scheduling problem,DPFSP),建立问题排序模型,并提出混合迭代贪婪算法(hybrid iterated greedy,HIG)进行求解.基于问题特点提出最小工期差值(smallest due date difference value,SDV)规则及3种工厂分配规则,同时结合问题性质提出两种工件插入各工厂内部时问题目标值的下界估计方法.首先,通过实验确定使用分配规则1将工件向各工厂进行分配,同时结合下界估计方法的NEH作为改进启发式算法以生成较高质量初始解;其次,为了增加解的多样性,提出一种关键工厂的移除策略和适用于问题的模拟退火机制;然后,设计基于4种有效邻域操作的两阶段变邻域下降搜索策略,用于在HIG每代中对问题解空间的不同区域进行较深入和细致的搜索;最后,通过仿真实验和算法比较验证了采用HIG求解所提出问题的有效性.

两阶段流水车间成组调度问题的迭代贪婪算法

针对两阶段流水车间成组调度问题,在同时考虑序列不相关准备时间和阶段间双向运输时间约束的情况下,以最小化最大完工时间为目标建立了混合整数线性规划模型,结合问题特征提出一种协同进化迭代贪婪算法.算法将工件组间排序和各工件组内工件间排序两个子问题进行统一编码,设计了不同的启发式规则产生问题的初始解,并提出一种协同导向迭代贪婪规则对两个子问题进行联合优化,进而给出了问题的三个下界以评估算法的性能.通过不同规模的数据实验和与对比算法的比较分析,验证了所提算法的高效性和稳健性.

求解阻塞混合流水车间调度的双层变异迭代贪婪算法

混合流水车间调度是制造业领域的前沿方向,而研究带有阻塞约束的问题更具有现实意义.针对阻塞混合流水车间调度问题(BHFSP),以最小化最大完工时间为优化目标建立BHFSP的数学模型并详细阐述其计算过程,在零缓冲区特性的基础上设计一种双层变异策略的迭代贪婪(IGDLM)算法求解BHFSP.分析传统迭代贪婪(IG)算法中的优势和不足,针对阻塞特性提出双层变异策略来提高解的多样性,进一步平衡所提算法的全局探索和局部搜索能力.通过100个测试算例的数值仿真以及与5种代表算法的统计比较,验证所提出的双层变异策略与IG融合的算法能够得到更好的目标值,并为中大规模的BHFSP提供更优的调度方案.

求解零空闲流水车间调度问题的离散正弦优化算法

针对以最小化最大完工时间(makespan)为目标的零空闲流水车间调度问题(NIFSP),提出一种离散正弦优化算法(DSOA)进行求解.受正弦波形的启发,原始的正弦优化算法(SOA)是一种利用正弦函数对个体位置进行更新的全局优化算法.首先,重新定义了适应组合优化问题的位置更新策略,采用一种去除工件数大小可变的迭代贪婪算法来对个体位置进行更新,以提高算法的探索能力.其次,采用了交叉操作和保留精英解的选择策略,避免算法陷入局部最优.最后,为了提高局部搜索的开发能力和算法精度,引入了一种基于插入的局部搜索方法,以便于在当前最优解的周围寻找更好的解.此外,基于Taillard基准,给出了算法性能比较的仿真结果,实验结果验证了所提出的DSOA算法求解NIFSP的有效性.