贪心算法汽车加油问题（精选5篇）
篇1：贪心算法汽车加油问题
证明人民币找零问题贪心算法的正确性
问题提出：
根据人们生活常识，我们到商店里买东西需要找零钱时，收银员总是先给我们最大面值的，要是不够再找面值小一点的，直到找完为止。这就是一个典型的贪心选择问题。问题描述：
当前有面值分别为100 元、50 元、20 元、10 元、5元、1元, 5角, 2角、1角的人民币。证明人民币在找零时（1-99元）符合贪心算法，即证明此问题满足贪心算法的两个基本要素：即最优子结构性质和贪心选择性质。
问题证明：
当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。在人民币找零问题中，其最优子结构性质表现为：
设c[i]是各面额人民币使用的数量，S[i]是商品价格为n时的最优解，数量为K。现在设某面值的人民币数量减一：S[j]=S[j]-1，则新的S[i]为n-c[j]的最优解，纸币数K-1.否则，设T[i]是n-c[j]的最优解，纸币数为m，即m 设纸币面额100,50,20,10,5,2,1元的数量依次为A,B,C,D,E,F,G，则根据贪心算法思想得到的解应依次保证max（A），max（B），max（C），max（D），max（E），max（F），max（G）。假设存在更优的算法，使得所用的纸币数更少，即数量至少小于或等于A+B+C+D+E+F+G-1。那么在纸币总数减少的情况下保证总额不变只能增大相对大面额纸币的数量并减少小面额纸币数量。而由贪心算法知max（A）已经是最大的了，以此类推，max（B），max（C），max（D），max（E），max（F）均应为最大数量了，所以贪心算法得到的解是最优解，即满足贪心选择性质。 综上所述，人民币找零问题满足贪心算法。 开课实验室：数学实验室 指导老师：韩逢庆 时间：2011.12 学院：理学院 专业：信息与计算科学 班级：2009级2班 姓名：古 月 学号：09180230 一、实验目的 1．加深学生对贪心算法设计方法的基本思想、基本步骤、基本方法的理解与掌握； 2．提高学生利用课堂所学知识解决实际问题的能力； 3．提高学生综合应用所学知识解决实际问题的能力。 二、实验内容 题目见P143:4-16,4-23.三、实验要求 （1）用分治法求解最少加油次数和最少硬币个数问题； （2）再选择自己熟悉的其它方法求解本问题； （3）上机实现所设计的所有算法； 四、实验过程设计（算法设计过程）（1）最少加油次数 实验题目 一辆汽车加满油以后可以行使n公里，旅途中有若干个加油站，设计一个有效算法，指出应在哪些加油站停靠加油，使沿路加油次数最少。并证明算法能产生一个最优解。过程设计 贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。比如说最少加油次数的问题。在这个算法中，我采用的贪心算法的策略。首先人机互动的设定加满油以后最长能够行使的距离，然后输入了各个站点之间的距离，在程序的设计中，首先检查了程序的可行性。要是遇到当某两个站点之间的距离大于汽车一次加油以后所能够行使的最大距离时，我们认为此问题是不可行的。这个在实际情况中也是很容易理解的。然后在满足可行性条件下，依次采用贪心算法对问题得以实现。采用s这个来保存现在车里面留下的油，当此时留下的有能够行驶完这一站点到下一站点之间的距离是，在这一站点的时候就不加油。但是若不能行使完这一段路程的时候，就加满油。核心算法如下： for(i=0,s=0;i { s=s+a[i]; if(s>n) { sum++; s=a[i]; } }（2）最少硬币个数问题 实验题目 考虑下面的用最少硬币个数找出n分钱的问题： 当使用2角5分，1角，5分和1分四种硬币面值时，设计一个找n分钱的贪心算法，并证明算法能产生最优解。过程设计 贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。比如说找最少硬币个数的问题。在算法的实现过程中，当剩余的钱数大于2角5分时，我们在记录找2角5分硬币的个数的变量里面加一，同时把剩余所找的钱的总数目也减2角5分。不断重复这个过程，直到剩余所需找的钱的数目小于2角5分时，在记录找1角硬币的个数的变量里面加一，同时把剩余所找的钱的总数目也减1角，不断重复这个过程，直到剩余所需找的钱的数目小于1角。5分和1分的硬币实现过程同上述过程一样，一直执行到所剩的钱的数目为0，此时停止计算，得到最优解。 五、实验结果分析（1）最少加油次数 当加油后行驶的最大距离小于相邻站点的最小值时，此时，可行，求解结果如下： 当加油后行驶的最大距离大于相邻站点的最小值时，此时，没用可行性，为边沿情况，求解结果如下： （分析时空复杂性，设计测试用例及测试结果）时间复杂性：该算法的时间复杂度为O(n)空间复杂性分析：该算法的空间复杂度为O(1)（2）最少硬币问题 当输入的找零钱数为正常的时候的运行情况如下： 当输入的找零钱数为不正常的时候（为负）的运行情况如下： （分析时空复杂性，设计测试用例及测试结果）时间复杂性：该算法的时间复杂性为O(n)空间复杂性分析：该算法的空间复杂性为O(1) 六、实验体会 贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题，相容活动安排问题等。这样和采用动态规划的算法相比，算法的思想更加的简单，实现起来更加的容易。 但是也要明确贪心算法和动态规划的主要区别。及0-1背包问题可以用动态规划算法求解，但是贪心选择算法却不能用动态规划算法求解。因为贪心算法无法最终将背包装满，部分闲置的背包空间使得每公斤背包空间的价值降低了。 七、附录：（源代码）（1）最少加油次数 具体算法的实现如下： #include cin>>a[i];} for(i=0;i<=n;i++){ cout<<“第”< { sum=-1; break; } if(sum!=-1){ } for(i=0,s=0;i s=s+a[i]; if(s>n) { sum++; s=a[i]; } } } if(sum==-1)cout<<“没有可行性”< #include cout<<“ 您输入的数据有错!”< a++; m=m-2.5;} while(m>=1){ b++; m=m-1;} while(m>=0.5){ c++; m=m-0.5;} while(m>=0.1){ d++; 关键词：背包问题,遗传算法,贪心算法,贪心遗传算法 近年来,背包问题［1］吸引了许多理论科学家和实际工作者对其进行深入的研究。在结构方面,背包问题形式看似简单,但其却有组合爆炸的性质。如今,在实际工作中,越来越多的领域运用到了背包问题。 求解背包问题的方法可分为启发式算法,如贪心算法、模拟退火算法、蚁群算法; 最优化算法,如动态规划算法、回溯法、分支定界法等［2］。这些算法均能找到相应的最优解,但也均有各自的局限性及缺陷。 本文介绍了贪心算法和遗传算法求解0 - 1 背包问题,并在其基础上提出基于贪心算法的遗传算法来解决背包问题。 最后,运用计算机仿真技术来验证混合遗传算法的设计。这样,即克服了传统算法的缺陷,又加快了算法的收敛性,可得到更好的最优解。 1 背包问题 背包问题的一般提法为［3］: 已知n个物品的重量w和价值p分别为wi> 0 和pi> 0,背包的容量c。背包的容量ci> 0,其中,i = 1,2,3,4,…,则如何选择物品,使得在有限的容量内装入物品的价值最大。 问题的一般可表示为0 -1 整数规划问题 目标函数 其中,xi为0 - 1 决策变量; xi= 1 表示将物品装入背包; xi= 0 表示不将物品装入背包中。 2 问题求解方法 2. 1 贪心算法 贪心算法属于启发算法,即通过问题的初始状态, 经若干次的贪心选择而得出最优的一种解题方法［4 －5］。贪心算法每一步只需考虑一个数据,因此所得出的解只是某种意义上的局部最优解。 2. 2 遗传算法 遗传算法是模拟达尔文的生物自然选择学说和自然界的生物进化过程的一种自适应全局概率搜索算法［6］。其将问题的每一个可能解看作是群体中的一个个体,并将每个染色体编码成串的形式,通过选择个体,并预定目标对个体进行评价,给出一个适应值［2］。 通过选择,杂交和变异,从而获得全局最优解［7］。 虽然遗传算法在许多领域中都有成功的应用,但其自身也存在不足,如局部搜索能力差、存在未成熟收敛和随机游走等现象,导致算法的收敛性能差,所需较长时间才能找到最优解等问题［8］。 2. 3 贪心遗传算法 针对贪心算法和遗传算法的缺陷,设计了贪心遗传算法。该算法是基于贪心算法的遗传算法。其基本思路是先用贪心算法生成问题的一个初始的贪心解, 然后通过遗传算法对剩余的算子进行变异,使得算子的适应度增加,在对背包中的物品进行比较交换,求得最优解。在算法中,克服了贪心算法和遗传算法会陷入局部最优的状态,使收敛度和运行速度得到提高。 算法如下: ( 1) 适应度函数和算子选择。一般而言,对背包中的普通个体,采用求得适应度函数。对算子的适应度就行评估后, 由公式计算出选择概率。本文对算子的选择采用精英赌轮方法［9］对算子进行选择,其包括两方面: 精英主义和赌轮选择。 ( 2) 运用贪心算法对背包内的物品进行操作。对算子进行选择后,首先运用贪心算法对物品进行了初次操作,得到一个初始的最优解,步骤如下: Step1 将未装入背包中的物品,按照物品的价值密度(pi/vi),进行降序排列,形成新的队列aj。 Step2 将物品按照价值密度从高到低依次放入背包中,若物品未超出背包的总容积则计算背包中物品的总价值,直到物品循环完毕,转入Step3。 Step3 将超过背包体积的物品取出,放入体积较小的下一个物品,并转入Step2。 ( 3) 算子的杂交变异。运用贪心算法虽能较快的得到满意解,但不能保证解最优。因此,需对算子的适应度进行重新计算,并进行重新杂交变异,使算子的适应度得到提到。因此在对背包问题运用贪心算法进行操作后,背包外会剩余一定的算子,对其进行杂交变异构成新的算子,算子经过变异,适应度会比以前增加, 具体步骤如下: Step1 将物品价值按照适应度由小到大降序排列,得到一个新的种群{k1,k2,…,kn}表示越往后价值p则越大。 Step2 在新得到的种群{k1,k2,…,kn}中,依次取出两个算子ki和ki+1,i=1,2,3,…。 Step3 将ki和ki+1作为双亲进行杂交,形成一个新的染色体yi。 Step4 在yi中以p(xi)的概率选择出适应度差的个体,采取均匀变异[10]使染色体变异。 Step5 将新产生的个体适应值与原个体的适应值相比较,若有提高则此次个体变异成功,原个体被变异,否则重新随机选择变异位,如试4次,若始终不能高于原个体的适应值,则保留原个体,然后返回Step2直至循环结束[2]。 Step6 对适应度重新计算,方法(1)。 ( 4) 对初始解进行改进。此时,剩余的物品由于重新杂交变异后,它们的适应度会得到提升。因此,当其与一开始由贪心算法中放入背包的物品进行比较后,会发现新个体的适应度可能会大于背包中个体的适应度。此时,可将之换出,步骤如下: Step1 将新得到的染色体种群和背包中的物品依次进行比较,首先在背包中找出适应度最差的个体aj,将其与中染色体的适应度进行比较,若此时背包外的物品适应度较好,则将新得到的染色体换入背包中。 Step2 若此时适应度不变,则转入下一组比较。 Step3 将所有染色体循环完毕,此时得到最优解。 文中不仅运用了贪心算法,并将贪心算法和遗传算法相结合,构成了一种新的算法,并设计出一种新的算子后产生新一代的种群,将新种群中得到的算子和原有种群进行比较,换出适应度差的个体,使得背包问题得到最优解。 3 操作分析 由于贪心算法不能保证全局最优的结果。所以在贪心算法的基础上对其进行修正得到了这种改进的算法。由以上算法操作过程可看出,这种修正使得不可行解变为可行解,且使得适应度得到提高。这样既可让最优值得到提高,也可让全局的适应度值提升,使整个种群更加优秀。 4 数值结果与结论 实验采用的数据,是经典的背包问题数据［11］,即pi表示物品的价值; vi表示物品的体积; max表示背包的体积。 pi80,82,85,70,72,70,66,50,55,25,50,55,40, 48,50,32,22,60,30,32,40,38,35,32,25,28,30,22, 50,30,45,30,60,50,20,65,20,25,30,10,20,25,15, 10,10,10,4,4,2,1 vi220,208,198,192,180,180,165,162,160,158, 155,130,125,122,120,118,115,110,105,101,100,100,98,96,95,90,88,82,80,77,75,73,72,70,69,66, 65,63,60,58,56,50,30,20,15,10,8,5,3,1 max 1000 将数据通过遗传算法和贪心遗传算法进行比较, 得到表1 的结果。 由实验结果可看出,贪心遗传算法对选择方式进行了处理后,使得整体的适应度值有了较大的提高,得到最优值的准确性也比其他的算法要高。而当被选择的物品规模较大时,其优越性会更加明显。 5 结束语 针对背包问题的特性,设计了一种贪心遗传算法结合,并使用其对大规模的背包问题求解。通过计算机仿真可看出,该算法对于背包问题能获得高质量的解。 随着我国经济的发展，人们物质水平不断提高，汽车作为一种普通商品走入千家万户，作为给汽车补充燃料的加油站数量也随之大量增加。加油站经营过程中大量储存和销售汽油和柴油，这两种物质具有易燃、易爆、易挥发易扩散流淌和静电荷积聚等危险、危害的特性，这就决定了加油站具有较大的火灾爆炸危险和中毒危害。特别对火灾爆炸事故，一旦发生，不仅造成加油站内人员伤亡和设备设施的毁坏，而且会严重威胁加油站周围的居民和环境，带来较大的人员伤亡、财产损失和社会影响，必须引起全社会的足够重视。关于汽车加油站的消防要求，《汽车加油加气站设计与施工规范》。 1、对汽车加油站消防安全的定位 根据国务院344号令《危险化学品安全管理规定》的精神，政府安监局贮罐危险化学品行业，时汽车加油站的行业主管领导部门。公安消防部门在确定消防安全重点单位的时候，因为加油站具有较大的火灾爆炸性，往往都把加油站确定为县（市、区）级公安机关消防大队列管的重点单位，作为消防安全重点单位，公安消防部门对汽车加油站实时正常的监督抽查，是其法定职责，但其不能设计行业管理的汽车加油站的专项治理、专项检查，或要求统一配置专用标示、设施。对在监督抽查中发现的汽车加油站重大火灾隐患，应及时通知主管部门处理，并予以必要的协助。 2、汽车加油站常见的消防隐患 2.1平面布局存在的问题 在对城乡汽车加油站进行消防安全检查时，经常会晕倒一下一些问题。 1）汽车加油站的位置，应距其它建筑有足够的消防间距；尤其是距明火点应保证25m的距离，这一点大部分城市加油站都做不到，应采取措施：用高2.2m的非燃烧实体墙惊醒防火分隔。现在的问题是，有的隔墙是非实体墙；或者实体墙高度不够；或材料是燃烧体，面向进出口道路的一侧，宜建造非实体墙。 2）单一进出口，汽车加油站的进口和出口应分别设置，有的加油站设在院子里，只有一个进出口，不行。要么整改，要么关门。 3）汽车加油站的平面布局存在的问题，一般是分区不明确。生产区域（包括：加油机、管线、加油车位、道路、油罐区、卸油平台、油槽车库、仓库、营业室等）和生活管理区域（办公室、宿舍、食堂、锅炉房、厕所、门卫等）没有分隔开，或间距不够。一定要根据现有条件，采取措施整改，这种问题比较普遍。 4）防火间距：汽车加油站与国家一、二级架空通讯线路的距离，与架空电力线路的距离，要符合规范要求。要注意的是：间距1.5倍杆高是地面投影的距离，测量时应以罐壁为起点，而不是以围墙为起点。 5）加油站超储，目前市场油价波动很大，一些人里有加油站的储量进行囤积，凡加油站超储的，都应视作违规。例如：三级加油站储量（汽油，以下同）超过60m3（约44t），单罐超过30m3（月22t）；二级加油站超过120m3（约88t），单罐超过50m3（约37t）；一级加油 站超过180m3（约132t）.6）有的农村加油站，纯粹是家庭加油站，窗外是加油机，厂里就是居室，明火取暖，做饭，炒菜抽烟，看电视。有的还兼营小卖店业务。这类加油站一般油品储量很少，有的采用架空罐，靠重力自流加油。这样的加油站在农村并不是个别现象，不安全因素太多，应与取缔。 2.2管理制度问题 1）汽车加油站应当建立并适时明确的管理制度。例如：禁止摩托车进站加油不熄火，禁止用塑料桶直接接油等这些现象非常普遍，确实非常危险的火灾隐患，一定要坚决禁止。有些燃烧不充分从排气管冒火星、冒黑烟的汽车、农用车、拖拉机进加油站要给他配带防火帽，加完油出站卸下。禁止有问题的车辆随意出入加油站。 2）禁止吸烟，汽车加油站映射有明显的禁烟禁或标志。无论任何人，进入加油站区域都不吸烟。检查加油站时，经常发现站内地面有烟头这是严重的违章行为。即令解释是加油车从驾驶室清理下来的，也要处罚。 3）汽车加油站应设置规范的警示标志，和“禁止烟火”、“减速慢行”、“摩托车加油请熄火”、“进口”、“出口”等警示、提示标语、说明。许多加油站的警示标志不规范，或无警示、提示、说明等。2.3关于消防器材问题 现在城乡汽车加油站都配备了灭火器，但存在的不少问题。例如：有的汽车加油站配备的灭火器时二氧化碳灭火器，显然灭火级别不 够；有的灭火器数量不足。配置的泡沫灭火器和车式泡沫镍火气冬季使用肯定有问题；灭火器的保温防冻问题和防晒遮阳问题；消防沙、石棉被时加油站最好的最有效的扑救初期火灾的灭火工具，不少加油站没有配置（沙堆也涉及防冻问题）。设置消防栓的加油站，有一些存在消防水源压力不足的问题。2.4加油机的防爆剂避雷问题 1）加油机的防爆问题需要引起应有的注意，现状的加油机出厂前内部都是封闭的，具有防爆功能，在进行修理后，一般都不能恢复封闭，防爆功能缺失了。更有的人在加油机里面做手脚，用遥控手段是数字空跑赚昧心钱。这就更危险了。 2）因为考虑防火防爆问题，所以不允许汽车加油站内出现明火火花。要求加油站建筑的门窗不应出现铁碰铁现象，使用的滤油网、各种锁都应是铜制的，使用的工具，如：扳子、钳子、管钳子等应当是铜的有色金属工具。许多加油站根本不知道这些要求，所以存在的这类问题较多。 3）加油站的静电接地存在问题较多，例如：埋在地下的油罐未作静电接地；管线的法兰、阀门未作静电跨接，卸油平台无静电接地设施(或损坏)。加油枪的静电接地线断开是普遍现象。油槽车卸油时应注意天气，不能在天低云暗、电闪雷鸣时卸油。以防不测。 4）避雷问题。如果加油站周围的建筑或其它构筑物、树木较高，可不做避雷设计。但是加油站的建筑位置高时应考虑避雷措施。罐上的安全阀如果突出地面2.5m以上，就应考虑安装避雷设施。有避雷 设施的汽车加油站，应每年按时有法定单位测试接地电阻值，（同时测试静电接地电阻值）并有年检合格证。法定避雷测试单位各地不同，有的地区是电业局，有的是气象局，有的是技术监督局，但是有同等法律效力。 5）劳动保护：加油站的工作人员应当穿着防静电的工作服和防静电鞋等。防静电工作服、手套的质地材料应是天然纤维的，例如：纯棉、纯麻、纯毛等，不允许含有化学纤维。防静电鞋与电工鞋相反，不能与地面绝缘。还应注意的是不光外衣防静电，内衣、衬衣、毛衣、毛裤、袜子等也应防静电。现在各加油站配置的工作服等大部分不合格或不规范。 6）加油站给危险品车辆加油时，如：化学试剂车辆、液氨车、液氮车、液氯车、液氢车、烟花爆竹车辆、液化气槽车、油罐车、高压气瓶车、液化气罐车等特种车辆。应当先检查其静电接地等设施是否完好有效，应选择无其它车辆时，或保持了安全距离，再加油。尘世闹市区的加油站应明确标示，不给各种危险品车辆加油。以防止意外事故发生。2.5取暖和供电问题 1）汽车加油站的供电负荷等级为三级。站内电气安装是按照防爆规范要求设计施工的。其线路应穿管；要求三通、接头等处要封堵封闭；罩棚下的照明灯具，应选用防护型防爆灯。许多汽车加油站在防爆区域内，使用的是普通的电器，例如：插座、电子表、电话等，与偶的甚至还临时接线，安装电热器，使用电褥子。 2）加油站冬季采暖问题，在作业区和营业室严禁采用明火取暖，包括：电暖器、燃油燃气的采暖器和蒸汽取暖的暖气。小锅炉和土锅炉和营业室保持规定的防火间距。存在上述问题的都应进行整改。 近年来城市出现了与加气站设在一起的汽车加油加气站，要满足加气站的规范的安全要求。这里就不提了。 3、针对汽车加油站存在消防安全隐患问题所采取的措施 以上所说的各种问题，在加油站里是普遍存在的火灾隐患公安消防部门在实施消防监督抽查时，要留心注意，及时发现这些隐患并及时解决问题，不能视而不见。对在汽车加油站发现的各种火灾隐患，在工作中应从以下几点入手： 1）严把审核验收关，加油站应按GB50156-2002进行设计、施工，并经公安消防部门审核、验收合格后投入使用。 2）加强日常的防火检查和督促火灾隐患整改工作。 ①督促加油站做好防火检查。消防安全负责人应至少每月组织一次放火检查；消防安全管理人应至少每周组织一次放火检查；每组每天巡查不少于两次；班组交班前，班组消防安全管理人员应共同进行一次巡查。检查结束，应做好检查记录，检察人员应在检查记录表上签名，存入单位消防档案。 ②督促加油站及时整改火灾隐患。加油站对存在的火灾隐患要采取措施及时真该，并在真该完毕后，负责整改的部门或人员应逐级上报至消防安全责任人；对公安消防部门责令限期改正的火灾隐患，应在规定的限期内改正，写出火灾隐患整改复函，向当地公安消防部门 申报检查、验收。对不能立即改正的火灾隐患，应制定整改方案，明确整改措施，应将危险部位停业整改，并落实整改期间的安全防范措施。 3）组织宣传教育、培训及灭火和应急疏散演练。加油站的消防安全责任人、消防安全管理人员应参加公安消防部门组织的消防安全培训；加油员、油罐车驾驶员等特殊工种人员应经过培训后持证上岗；加油站对新员工组织一次上刚强消防安全教育、培训；加油站施工期间，施工单位应对施工人员进行一次消防安全教育、培训。在加油站内部每半年搞一次组织灭火和应急疏散演练。演练时应在加油站入口处设置带有“正在进行消防演练”字样的标志牌，在演练结束后，总结问题，做好记录，修订预案内容。 0-1背包问题是计算机科学中一个经典的NP完备问题,传统的解决方法一种是试图通过数学方法给出它的解析解,另一种是用穷举法。但这些方法都有它的局限性,解析解对于目标函数是连续可微的情况,通过求解使目标函数梯度为零的一组非线性方程,可以解决该问题,但对于任意目标函数却无能为力。穷举法,在问题规模较小的情况下,可以有效地得到最优解,但对于较大规模的问题,求解复杂度将以指数形式增加,运算时间可能无法满足实际应用的要求。还有贪心方法、动态规划法、回溯法、分支界限法等方法,但它们都在问题规模比较大时求解复杂度将以指数形式增加。近年来兴起的一种借鉴生物界自然选择和自然遗传机制的随机化搜索算法——遗传算法己被广泛地应用组合优化领域,其全局最优性、可并行性、高效性在函数优化、模式识别、图像处理等领域得到了广泛的应用。遗传算法克服了传统优化方法的缺点,借助了大自然的演化过程,是多线索而非单线索的全局优化方法,采用的是种群和随机搜索机制[3]。 本文应用遗传算法来解决0-1背包问题,并用贪心策略对该算法做了相应的改进。 1 0-1背包问题模型 0-1背包问题:给定n种物品和一个背包,物品i的重量是wi,其价值是vi,背包的容量为C。问:应该如何选择装入背包的物品,使得装入背包中物品的总价值最大?[1] 设xi表示第i个物品是否装入,则该问题的数学模型为: st: 2 遗传算法 遗传算法是模拟达尔文的遗传选择和自然淘汰的生物进化论过程的计算模型,它是由美国的J.Holland教授1975年首先提出。它的思想源于生物遗传学和适者生存的自然规律,是具有“生存+检测”的迭代过程的随机搜索算法。遗传算法以一种群体中的所有个体为对象,并利用随机化技术指导对一个被编码的参数空间进行高效搜索。其中,选择、交叉和变异是遗传算法的主要遗传操作,参数编码、初始群体的设定、适应度函数的设计、遗传操作设计、控制参数设定五个要素组成了遗传算法的核心内容。 作为一种新的全局优化搜索算法,遗传算法以其简单通用性、鲁棒性强,适用于并行处理以及高效性、实用性等显著特点,在各个领域得到了广泛应用,取得了良好效果,并逐渐成为重要的智能算法之一。 3 遗传算法解决0-1背包问题 3.1 编码 在0-1背包问题中只存在背包装入和不装入两种情况,所以算法采用二进制编码,0表示不装入,1表示装入,编码长度为所需要装入的物品数量。 3.2 适应度函数 3.3 初始种群的产生 算法采用如下代码产生初始群体: 其中f为适应度函数,t为约束函数,g存储的是个体装载信息。 这样产生的初始群体和随机产生的相比有两个好处:(1) 不会产生不可行解,因为只有满足约束条件的个体才会被选择;(2) 使个体具有较好的适应性。 3.4 遗传操作 (1) 选择 算法采用轮盘赌选择法和最佳个体保存法相结合的方法。轮盘赌选择法是最常用的方法,在该方法中,各个个体的选择概率和其适应度值成正比,也就是说个体适应度越大,其被选择的概率就越大,反之亦然。该方法一般情况下可以选择出适应度值大的个体,但也存在统计误差,即最优个体未被选择。最佳个体保存方法就是将适应度最高的个体不进行选择、交叉、变异而直接复制到下一代。因此算法采用二者相结合的方法,首先,选择最优个体直接复制到下一代,然后在剩下的个体中应用轮盘赌法进行选择,这样既可以克服轮盘赌法的统计误差,又可以避免优秀个体在交叉、变异过程中遭到破坏。 其中选择概率如下: (2) 交叉 是把两个父个体的部分结构根据交叉概率加以替换而生成新个体,也称基因重组。其主要目的是为了能够在下一代产生新的个体,而这些新个体中可能存在比原个体更优的个体。通过交叉操作,遗传算法的全局搜索能力有了质的提高。交叉是遗传算法获取新优良个体的重要手段。 目前交叉操作主要采用单点交叉和两点交叉,也可以是多点交叉。本文采用单点交叉,其具体操作是:以交叉概率Pc选择要交叉的父代对数,然后随机产生交叉点,将两个父代个体位于交叉点后的基因互相交换,从而产生子代个体。 交叉概率控制着交叉操作被使用的频度,较大的交叉概率可增强遗传算法开辟新的搜索区域的能力,但同时较高的交叉频率使优秀个体遭到破坏的可能性增大,若交叉概率太低,遗传算法搜索可能陷入迟钝状态,无法得到最优解。一般取Pc从0.25到1.00之间。 (3) 变异操作 是以概率Pm对群体中的个体基因串的基因位上的基因值进行改变。进行变异操作的目的为:一是使得遗传算法具有局部的随机搜索能力,因此此时变异概率应取较小值;二是使遗传算法可维持群体多样性,以防止出现未成熟收敛现象,此时变异概率应取较大的值。 一般解决0-1背包问题的遗传算法其变异操作就是把基因值取反,即把0变为1或把1变为0。 本文中对一般的变异操作做了一些改进:以变异概率Pm选择变异的基因位置,如果该位置为0,进行变异,将该位置变为1;如果该位置为1,则重新选择基因位置,直到基因位为1。因为在算法中,引入贪心思想对不可行解进行处理,所以在变异时不存在不可行解,也就没必要将1变为0。 3.5 不符合条件解的处理 算法设计中有两种不符合条件的解:一是不可行解,即背包容量超重的解;二是可行解,但背包装包容量严重不足。 人们一般是通过惩罚函数对不符合条件的解进行惩罚,以使个体朝最优的承重方向进化,从而达到加快遗传算法收敛速度的作用。本文根据贪心思想,设计了处理两类不符合条件解的贪心方法: 可行解的处理 设x=(x1,x2,…,xn)是一个背包利用不足的可行解,将背包中还没有背的项目按价值—重量比降序排列,然后按照排好的依次加入背包中,直到背包不能装为止。 不可行解的处理 不可行解是在交叉和变异过程中产生的。对于这类不可行解,可做如下处理:将背包中已装入的物品按价值—重量比升序排列,然后依此顺序减掉物品,直到背包不超重为止。 在本算法中,每当进行交叉和变异操作后就进行不符合条件解的处理,这样可以保证父代产生的子代都是比较优秀的,也可以加快算法向最优解的方向前进。 判断第二类不符合条件解的方法:采用随机数N的方法来判断,一般是先生成随机数N,如果当前背包容量小于N×C,那么就认为背包装载不足。随机数不能太小,小了就起不到处理背包装载不足的目的,太大了也不行,容易使算法陷入局部搜索中,也容易减少个体的多样性,不利于遗传算法收敛速度。算法经过多次尝试,一般情况下N取0.6～0.8之间比较合适。 3.6 算法终止条件 虽然遗传算法具有概率1收敛的极限性质,然而实际算法通常难以实现理论上的收敛条件。因此,一般的目标应该是具有一定优化质量的快速搜索。由于实际应用遗传算法时不允许让其无限制地进行搜索,同时问题的最优解也通常未知,因此必须设计一些近似收敛准则来终止算法进程。常用方法包括:给定一个最大进化步数;给定个体评价总数;给定最佳搜索解的最大滞留步数等。 4 算法仿真试验及结果分析 实例1 w={ 80,82,85,70,72,70,66,50,55,25 ,50,55,40,48,50,32,22,60,30,32 , 40,38,35,32,25,28,30,22,50,30 ,45,30,60,50,20 ,65,20,25,30,10 ,20,25,15,10,10 ,10,4, 4, 2, 1} v={220,208,198,192,180,180,165,162,160,158,155,130,125,122,120 ,118,115,110,105,101,100,100,98, 96, 95,90, 88, 82, 80,77, 75, 73, 72, 70, 69,66, 65, 63, 60,58,56, 50, 30, 20, 15,10, 8,5,3,1} c=1000 设初始种群数量为M=40,交叉概率Pc=0.7,变异概率Pm=0.1,最大进化代数为500。 对于该实例分别用普通遗传算法和本文的算法重复运行30次。比较算法所能达到的最优结果(价值最大)、以及达到最优结果所需的代数。如表1 所示。 实例2 w={135,133 ,130 ,11 ,128 ,123 ,20 ,75 ,9 ,66 ,105,43,18,5,37,90,22,85,9,80,70,31,25,37,41,97,85,57,53,17,20,17,60,35,57,35,61,40,8,50,32,40,72,35,100,2,7,19,28,10,22,27,30,11,5,7,41,22,9,14,19,21,23,88,91,47,68,108,10,12,43,11,20,37,17,4 ,3,21,10,67} v={135,133 ,130 ,11 ,128 ,123 ,20 ,75 ,9 ,66 ,105,43,18,5,37,90,22,85,9,80,70,31,25,37,41,97,85,57,53,17,20,17,60,35,57,35,61,40,8,50,32,40,72,35,100,2,7,19,28,10,22,27,30,11,5,7,41,22,9,14,19,21,23,88,91,47,68,108,10,12,43,11,20,37,17,4 ,3,21,10,67}[8] 设初始种群数量为M=40,交叉概率Pc=0.7,变异概率Pm=0.1,最大进化代数为500,随机数N=0.8,c=1505。 对于该实例分别用普通改进遗传算法和本文的贪心算法重复运行30次。比较算法所能达到的最优结果(价值最大)、平均最优解以及达到最优结果所需的平均代数。如表2所示。 从试验结果上来看,基于贪心策略的遗传算法无论是在最优解(价值最大)的质量还是解的速度方面都有了很大的提高,尤其是解的质量方面比改进的遗传算法有较大的提高。 5 结 论 本文改进了原算法随机产生初始种群的方法,这样可以使初始种群具有良好的适应性、局部的最优性。在进行选择操作时采用轮盘赌法和最优个体保存方法相结合,这样即可以克服轮盘赌法的统计误差,又可以保证最优个体遗传到下一代。在交叉和变异过程中采用贪心思想处理两种不可行解,加速了算法朝最优解方向进化的速度,从而提高了算法的效率和速度。从试验数据可以看出,该算法能有效地解决0-1背包问题。 参考文献 [1]王晓东.算法设计与分析[M].北京:清华大学出版社.2005:250-252. [2]霍红卫,许进,保铮.基于遗传算法的0/1背包问题求解[J].西安电子科技大学学报,1998,26(4):493-497. [3]陈国良,王煦法,庄镇泉,等.遗传算法及其应用[M].北京:人民邮电大学,1996:12-14. [4]郭晓晖.遗传算法在求解背包问题中的应用[J].大连铁道学院学报,2001,22(3):32-35. [5]Sartal Sahni.Approximate algorithms for the0/1knapsack problem[J].Journal of ACM,1995,22(1):182-184. [6]Cormen TH,Leiserson CE,Rivest RL,et al.Introduction to algorithms[M].Cambridge:The MIT Press,2001:263-265. [7]陈文兰,刘建华.一个求解0-1背包问题的遗传算法[J].福建电脑,2006(05):109-110. 【贪心算法汽车加油问题】相关文章： 贪心算法典型例题06-03 贪心的名人故事05-22 当贪心遇到爱心04-23 有关贪心励志故事05-06 以贪心为话题的作文04-08 形容贪心的贬义词05-19 以贪心为话题的初一作文04-29 贪心的狐狸童话故事作文05-15 我家的贪心宝贝小仓鼠作文300字04-23 幼儿园中班教案《贪心的小狗》含反思05-20篇2：贪心算法汽车加油问题
篇3：贪心算法汽车加油问题
篇4：汽车加油站消防安全问题研究
篇5：贪心算法汽车加油问题