贪婪迭代算法(IG)

这篇具有很好参考价值的文章主要介绍了贪婪迭代算法(IG)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

IG算法由是Ruiz等提出的一种新型智能优化算法,该算法主要由邻域搜索、扰动算子和接受准则3个基本部分组成。IG算法提出后,以其参数少、易实现和效率高等特点引起了众多国内外学者的关注和研究,并在阻塞流水车间调度和二次多重背包问题等领域得到了理论研究和实践应用。

————————————————

算法初始化这两个解之后(通常由启发式规则实现),从当前解出发,考虑针对所解决问题设计的局部搜索方法,若局部搜索中有更好的解则贪婪地移动到那个解,局部搜索结束之后算法会采用类似模拟退火的接受准则以一定的概率接受比最好解更差的解,然后更新最好解,再对当前解采用破坏重建过程以跳出局部最优并准备下一次的迭代过程。该算法结构非常简单,参数较少,且求解效果好。

 

IG算法伪代码

贪婪迭代算法(IG)

初始化

初始解由NEH规则生成初始解,NEH算法伪代码如下: 

 贪婪迭代算法(IG)

领域搜索 

 插入领域搜索和交换领域搜索结合的随机领域搜索算法(Random Neigh-borhood Search,RNS)

  1. 每次从当前解中随机地选择一个订单,随机地选择插入邻域或者交换邻域进行搜索,
  2. 前者将其从原位置移除并插入到所有可能位置中的最优位置,后者将其与所有可能位置中最优位置的订单进行交换;
  3. 如果通过邻域搜索找到的新解优于当前解,则替换当前解并且继续搜索,否则结束搜索。

 贪婪迭代算法(IG)

 破坏-重构阶段:扰动算子-避免陷入局部最优

破坏和重建过程思想

  1. 在破坏阶段,从当前解中随机选择若干订单并移除,得到两个部分序列:
  2. 由剩余订单组成的部分解、由移除订单按照移除顺序组成的部分序列;
  3. 在重建阶段,将部分序列中的订单逐一插入到部分解中所有可能位置的最优位置,从而最终得到一个扰动解。

接受准则

接受准则的作用是更新IG算法的当前解和最好解。由于扰动算子的扰动有时可能不是足够大,导致算法在后续局部搜索过程中又陷入到相同局部最优点。

基于遗传算法中的轮盘赌选择策略

在该接受准则中,需要构建一个精英表,该精英表储存了通过局部搜索找到的新解。RWS接受准则:通过局部搜索找到新解后,如果新解优于最好解,则更新最好解,且清空精英表;如果新解不在精英表中,则将新解添加到精英表的尾部;如果精英表的长度超过ω,则从表中删除最坏解;按照RWS策略从精英表中选择一个解为当前解。令精英表的长度为τ(τ≤ω),RWS策略的实现步骤如下

贪婪迭代算法(IG)

reference :

本文参考了CSDN博主「~晚风微凉~」的原创文章,
原文链接:https://blog.csdn.net/qq_51976555/article/details/123167039

[1]张杨, 但斌, 高华丽. 基于改进迭代贪婪算法的产品服务系统订单调度优化[J/OL]. 计算机集成制造系统, 2020, 26(12): 3435-3446. 文章来源地址https://www.toymoban.com/news/detail-491377.html

到了这里,关于贪婪迭代算法(IG)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 有一种新型病毒在 3Ds Max 环境中传播,如何避免?

    3ds Max渲染慢,可以使用渲云渲染农场: 渲云渲染农场解决本地渲染慢、电脑配置不足、紧急项目渲染等问题,可批量渲染,批量出结果,速度快,效率高。 此外3dmax支持的 CG MAGIC插件专业版正式上线, CG MAGIC是一款基于3ds Max深度开发的免费智能化辅助插件,上千项实用功能

    2024年02月12日
    浏览(38)
  • 贪心算法(贪婪算法)

    贪心算法(贪婪算法) 贪心算法思想 ​ 1.贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说, 不从整体最优上加以考虑,他所做出的是在某种意义上的局部最优解 。 ​ 2.贪心选择是指所求问题的 整体最优解可以通过一系列局部

    2024年02月03日
    浏览(45)
  • 清华大学团队提出一种基于稳态视觉诱发反应的混合脑机接口

    更多脑机接口前沿技术,关注公众号:脑机接口社区 近日,清华大学团队提出一种基于脑电图(EEG)和磁脑电图(MEG)混合的脑机接口(BCI)系统的研究,旨在提高BCI性能并解决“BCI文盲”的问题。虽然EEG-based BCI已经实现了大脑和外部设备之间的通讯,但由于头骨会减弱和

    2024年02月12日
    浏览(39)
  • matlab实现贪婪算法

    下面是一个简单的 MATLAB 实现贪婪算法的示例,以解决旅行推销员问题(TSP)为例: function [min_path, min_dist] = greedy_tsp(dist_matrix)     % 输入参数:距离矩阵 dist_matrix,表示城市之间的距离     % 输出结果:最短路径 min_path 和最小距离 min_dist     num_cities = size(dist_matrix, 1);    

    2024年02月22日
    浏览(34)
  • 《花雕学AI》06:ChatGPT,一种新型的对话生成模型的机遇、挑战与评估

    37款传感器与执行器的提法,在网络上广泛流传,其实Arduino能够兼容的传感器模块肯定是不止这37种的。鉴于本人手头积累了一些传感器和执行器模块,依照实践出真知(一定要动手做)的理念,以学习和交流为目的,这里准备逐一动手尝试系列实验,不管成功(程序走通)

    2024年02月02日
    浏览(38)
  • 【LeetCode】55. 跳跃游戏 - 贪婪算法

    55. 跳跃游戏 贪婪算法思路:每一个点我能跳跃的情况,全部都跳跃一次(每一个点的最优解),如果能够跳跃出长度或者到达了最后点,那么我就是肯定可达最终点的;否则就是不可达的。(局部最优解就能够得出整体的最优解)

    2024年02月13日
    浏览(43)
  • 一种具有改进的反向导通、击穿和开关特性的新型4H-SiC沟道MOSFET

    该文提出并通过TCAD模拟研究了一种带有集成MOS通道二极管(MCD)的SiC MOSFET,其源沟槽是凹陷的。MCD具有短通道特性,通道长度可以通过改变凹陷深度来调整。由于漏极诱导的势垒降低效应,形成了一个低势垒,使电子能够顺利流过JFET区域到达N+源区域,成功消除了寄生体p

    2024年02月16日
    浏览(41)
  • 华南理工大学研究人员提出一种用于VR环境的低成本、无线脑电图测量系统

    近年来,随着技术的进步,用于测量研究和医疗环境中大脑活动的系统和设备越来越先进。一个已被广泛探索但尚未有效实现的概念是,在人们浏览虚拟现实(VR)环境时收集脑电图(EEG)测量数据。 脑电图测量是对大脑自发电子活动的记录,通常使用连接在头皮上的小型电极

    2024年03月28日
    浏览(51)
  • 云计算、大数据技术的智慧工地,实现对建筑工地实时监测、管理和控制的一种新型建筑管理方式

    智慧工地是利用物联网、云计算、大数据等技术,实现对建筑工地实时监测、管理和控制的一种新型建筑管理方式。 智慧工地架构: 1、终端层: 充分利用物联网技术、移动应用、智能硬件设备提高现场管控能力。通过RFID、传感器、摄像头、手机等终端设备,实现对项目建

    2024年02月04日
    浏览(42)
  • MCR内存(Multiplexer Combined Ranks)是一种新型内存技术,由英特尔、瑞萨电子和SK海力士联合开发

    概括 MCR内存(Multiplexer Combined Ranks)是一种新型内存技术,由英特尔、瑞萨电子和SK海力士联合开发。它在DDR5内存的基础上,将内存传输速度再次提高一倍,目前已达8000MT/s(未超频)。 MCR内存的核心技术是将多个DRAM内存模块组合在一起,并使用专门的控制器来管理它们之间

    2024年02月10日
    浏览(41)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包