贪心策略范文

2024-05-24

贪心策略范文（精选7篇）

贪心策略第1篇

在现实生活中, 贪心策略的运用无处不在, 尤其在有关于金钱的问题中, 例如, 投资股票、期货、黄金、房地产, 等等。投身其中的人都会期望以最快的速度获得自己想要的财富, 而他们中很多的人采用的正是各种各样的贪心策略, 这些策略具有灵活多变、容易理解、容易使用等优点, 因此被大多数人使用。但也正是由于贪心算法本身不能完美解决高维度的问题, 所以导致多数人最终并没有得到真正期望的结果。

本论文首先介绍了一种简化的投资模型和三种贪心策略, 然后对这三种策略的运算结果进行比较分析, 并结合实际生活中的股票投资问题, 探讨了人们运用的贪心策略, 并简要分析这些策略的特点。

二、简化的投资模型

问题描述:假设有一笔资金可以选择n个项目中的若干个进行投资, 而且每一个项目的投资周期都是一个单位时间, 这n个项目的收益和截止期分别为p1, p2, …, pn和d1, d2, …, dn, 即第i个项目必须在其截止期di之前的任意一个单位时间进行投资, 才能获得对应的收益pi, 求解一个最佳的投资顺序, 使得总收益最大。

例如, 表1数据中有6个单月份即可完成的项目, 第一个项目只要在4月份结束之前的某一个月份进行投资, 即可获得其对应20%的收益, 其他依此类推。

n=6 (投资周期为:1个月)

从上面描述中可以看出, 这个简化的投资模型将投资问题简化成只有截止期di和收益pi两个维度的问题, 根据提出贪心策略的基本方法, 可以针对这两个量化的维度, 机械式的提出4种贪心策略: (1) pi大的优先, (2) di小的优先, (3) di大的优先, (4) pi小的优先。其中di小的优先, 就是对时间紧急的项目优先去完成, pi大的优先, 就是收益大的项目优先去完成。根据问题求解目标, 对所提四种贪心策略进行初步筛选, 可以排除掉 (3) 和 (4) , 因为这些策略与追求目标背道而驰。

上面这些贪心策略都只侧重于考虑问题中的一个维度, 而忽视了其他维度, 因此最终得到的结果与最优解都存在差距。这个简化投资模型能够得到最优解的贪心策略是: (5) pi大的优先考虑, 尽量不提前。也就是项目按pi从大到小依次安排, 每一个项目安排在它的截止期di对应的月份中, 如果di对应月份被其他项目占用, 则从di开始往前找一个最近且空闲的月份去安排此项目 (即让此项目提前的时间尽可能短) , 如果不存在这样的月份, 则放弃该项目。

三、贪心策略的比较

依据上面贪心策略 (1) 、 (2) 和 (5) , 分别计算简化模型中的样例数据, 可以得出如下结果:

(1) 策略安排结果 (投资周期为:1个月) (见表2)

累加收益:20%+15%+8%+7%=50%

复利收益: (1+20%) × (1+15%) × (1+8%) × (1+7%) -1=59.5%

放弃项目的收益:13%+10%=23%

(2) 策略安排结果 (投资周期为:1个月) (见表3)

累加收益:10%+15%+8%+20%=53%

复利收益: (1+10%) × (1+15%) × (1+8%) × (1+20%) -1=63.9%

放弃项目的收益:13%+7%=20%

(5) 策略安排结果 (投资周期为:1个月) (见表4)

累加收益:20%+15%+13%+8%=56%

复利收益: (1+20%) × (1+15%) × (1+13%) × (1+8%) -1=68.4%

放弃项目的收益:10%+7%=17%

三种策略的比较分析: (1) 策略看重的是项目收益, 将最大的安排在最前面完成, 而结果却是最不理想的; (2) 策略看重的是项目紧急性, 将截止期最小的安排在最前面完成, 对这组样例数据而言, 其结果优于 (1) 策略; (5) 策略兼顾项目收益和紧急性, 在收益大优先安排的前提下, 尽量不让其提前完成, 即让它刚好按时完成或者提前程度最小的情况下完成。

从计算结果可以明显看出, 策略不同, 最终安排项目的顺序和收益会有很大区别, 而且每一种策略都是容易被发现和使用的, 不过在使用之前应该分析出不同策略的优缺点, 然后考虑使用。

四、股票投资模型

投资人在投资股票时追求的收益主要来自两个方面, 一是公司股权分红;二是价格波动产生的价差。在目前全世界疯狂的股市投资与投机中, 包括保险、社保基金在内的绝大多数人都在追求通过价格波动获取收益。例如, 做波段是近两年保险、社保基金等机构青睐的一种操作方式, 他们采用的其实就是一种贪心策略的操作手法。

股票投资是一种十分复杂的经济行为, 人们认识事物都倾向于删繁就简, 抓主要因素, 弃次要因素, 如果对上面简化模型进行适当扩充, 可以得出如下类比的股票投资模型 (见表5) 。

(投资周期:日、周、月、季、年)

这个模型中, 将股票的净资产、市盈率、成长性、抗风险能力等基本面因素, 以及经济发展势头、大盘趋势等大环境因素, 简化成判断其收益能否成功的概率因素。不同的人侧重考虑的因素不一样, 判断成功概率值就不一样。对收益和截止期的判断, 也完全取决于投资者的经验和股市博弈的动态演变过程。

不同的群体, 选择的投资周期也不一样, 有的是以日、周为周期的短线持股者, 有的是以月、季为周期的中长线持股者, 有的是以年为周期的长线持股者, 即使是一个固定的投资者, 他的投资周期可能也不断地在短、中、长之间发生着变化。

正是由于每一个投资者对股票投资的认识都不一样, 因此他们会得出一个不同于他人的投资模型, 但是他们的目标都是一样的, 都是在尽自己所能去获取自认为可以轻易获取的最大投资收益。也正是受这个贪心策略的驱使, 投身其中的很多人都在努力付出时间与精力, 忙于构建和完善自己的投资模型, 这就是贪心策略的魅力所在, 它让参与的多数人都认为很简单, 在经过了相当长时间的磨炼之后才发现一个事与愿违的事实。

五、贪心策略的运用分析

对于股票类问题的分析, 往往容易偏向于考虑其中一个方面的因素, 而忽视了另外的因素, 或者在很多因素中难以提出一种有效策略兼顾所有因素, 从而导致难以直接运用贪心策略解决这类问题。贪心策略的致命缺陷就是以偏概全, 用少数的几个因素去推断多个因素决定的结果。

以上贪心策略只能在大势向好时有效发挥作用, 而在趋势不明朗或向坏时容易诱导人犯错。股票投资市场不仅是一个价格波动的市场, 更是一个庞大的博弈市场, 价格的波动只是各方博弈力量叠加的结果。不同投资者都在采用不同的贪心策略与其他投资者进行博弈, 他们都试图通过各种手段去赚取差价, 包括有实力的资金通过影响股价赚取差价。

例如, 2011年10月18日上市的中国水电, 在众多中小投资者拒绝申购和拒绝接盘的口号声中, 被少数大资金短线炒作, 由于缺乏大势和群众基础, 炒作难以为继, 出现暴涨暴跌。在上市第一天以高于6元/股的价格买入的投资者, 显然在贪心策略的使用上受到了很大的引诱, 因为超过50亿的成交金额是在5元/股价格以下完成的, 他们获利已经超过20%, 而且A股炒新资金基本都是短线价格投机为主, 因此, 不管是长线还是短线投资者, 在第一天股价上涨到6元以上还买入都是一种高风险低收益的选择, 是对上面贪心策略模型中成功概率没有认识的表现。

A股市场近几年暴涨暴跌, 其实就是广大参与者各种贪心策略合力产生的结果。包括基金在内的众多投资人追涨杀跌, 造就了一个个的传奇故事, 而更有太多的人在错误的时机使用了不符合形势的贪心策略, 最终亏损累累。

六、结束语

虽然贪心策略具有直观、容易理解、容易发现、容易使用和策略多样的特点, 但是贪心策略并没有让多数人获得成功, 因为贪心策略在运用之时, 存在太多陷阱, 或者说对于收益、爆发期和成功概率难以把握, 导致多数人会不断地否定自己构建的投资模型, 然后不断地犯错误, 最终输给市场。

参考文献

贪心策略第2篇

目前复杂网络社团识别算法方面的研究较多,主要分为两类: 一类是分离法,即找出社团之间的边,将其从社团中移除; 另一类是聚合法,将联系紧密的点聚合为一个社团,通过优化某个社团划分质量指标实现聚合。第一类算法的典型代表是GN分裂算法[6],该算法是复杂网络社团识别研究领域的一种标准算法[7],但时间复杂度较高。第二类算法的典型代表是Louvain算法[8]、模拟退火网络社团识别算法[9]和极值优化模块度识别法[10]等。

Louvain算法是基于贪心策略实现的,划分速度相当快,但不保证划分结果的准确度。模拟退火算法能获得全局最优的模块度值,达到较准确的社团划分,但划分速度相当慢。基于Louvain算法和模拟退火算法这种优缺点互补关系,本文对贪心策略结合模拟退火识别网络社团进行研究,提出一种新的社团识别算法SAGA( Simulated Annealing And Greedy) 。该算法用贪心策略消除模拟退火算法中结点移动运动的盲目无规则性,使结点的每次均向模块度增大的方向移动,缩短模拟退火算法获取最优值的时间。

1 相关概念

1. 1 模块度

模块度Q是最常用的衡量社团划分质量的标准,模块度Q越大,表明社团划分算法的划分效果越好,划分结果越符合网络的客观实际社团结构。模块度Q的计算公式如下

其中,NM是社团数; L是网络中的边数; ls是社团s内的结点之间的边数,ds是社团s内结点的度数之和。

1. 2 模拟退火

模拟退火算法应用复杂网络社团识别时,将温度T当作控制参数,模块度函数Q取反当作内能E。识别过程[11]: 首先,在初始温度下,将每个网络结点初始化为一个独立的社团,计算出这一初始网络社团划分状态下的内能。然后,逐渐降低温度,每一温度T下,执行N2次结点从一个社团随机地移动到其他社团的运动和N次两个社团合并运动或一个社团分裂为二个社团的运动,从而获得新划分状态,计算新状态的内能,用Metropolis准则决定是否接受生成的新状态,直至E趋于全局最小值。内能E最小时对应的社团划分结果即为网络的最优社团划分。Metropolis接受准则的数学公式如下[12]

其中,Ei是当前状态的内能; Ej是生成的新状态的内能; k为Boltzmann常数。

模拟退火识别网络社团统计上能保证找到全局最优值,缺点是搜索过程耗时过长。

1. 3 贪心策略

贪心策略是指在对问题求解时总是做出在当前看来是最佳的选择,即不从整体最优上加以考虑,只做出某种意义上的局部最优选择。文献[8]提出的Louvain社团识别法就基于贪心策略优化模块度来获取网络社团结构的。Louvain算法划分速度相当快,但不保证划分全局最优性。

2 SAGA算法

2. 1 算法思想

导致模拟退火识别网络社团收敛速度相当慢的原因: 降温过程的每一温度下会执行N2次某一单个结点从一个社团随机地移动到其他社团的运动,N为网络中的结点数。这每一温度下的N2次结点的运动是随机的,无方向性的,无引导的,必定包含很多未能使网络社团划分状态对应的目标函数值更优的结点运动。

针对这一问题,本文用贪心策略指导这每一温度下的N2次的结点运动,除去这一运动过程的盲目性,即除去了很多于收敛到最优模块度值无用的结点移动,使每个结点的每次移动都向模块度值增加的方向移动,使搜索过程更快地收敛到最优模块度值。具体策略是: 对某个结点i的移动运动,首先计算其从所属的社团移入邻居节点j所属的社团的模块度增量,计算公式如下

其中,ΔQout为结点i从其所属的社团移出时产生的模块度增量,ΔQin为结点i移入其的邻居节点时所属的社团时产生的模块度增量。ΔQout和 ΔQin的表达式相似,将一个孤立结点放入一个社团C时所产生的模块度增量计算公式如下

其中,∑in表示社团C内边的权值之和; ∑tot表示连接到社团C内的结点的边的权值之和; Ki表示连接到结点i的边的权值之和; Ki,in表示连接结点i和社团C内的结点的边之和; m为网络内所有边的权值之和。之后,将结点i放入使模块度增量最大且模块度值为正数的社团中,若不存在这样的模块度值,则结点i继续保留在其原来所在社团中。对每一温度下要移动的N2个结点执行此操作,N为网络中的结点数。

2. 2 算法执行流程

为便于更好地理解基于模拟退火和贪心策略的SAGA算法,在此给出SAGA网络社团识别算法的整体流程图。SAGA识别网络社团流程如图1 所示。

3 实验和分析

该实验数据来自文献[13]中提到的标准数据集海豚社群Dolphin网络,文献[14]中提到的空手道俱乐部Karate网络,以及从Newman个人网站[15]下载的标准数据集美国政治书Polbooks网络。这3 个数据集的相关详细信息如表1 所示。

其中,|V|表示网络中边数;|ε|表示网络中节点数;值为|ε|/|V|,CNact为实际的社团数;“-”表示没有确定的社团聚类结果。

3. 1 实验环境

硬件配置: Intel Core i5 - 3470 CPU @ 3. 20 GHz,2. 00 GB内存。

软件环境: Windows 7 旗舰版操作系统,Matlab2012b的编译环境。

3. 2 实验结果和性能评价

3. 2. 1 SAGA算法识别速度评价

本文提出的SAGA社团识别算法是在模拟退火( Simulated Annealing,SA) 社团识别算法上改进的,目的是在不改变SA较高识别准确度的条件下,大幅度缩短SA快速的识别时间。因此,实验设定SAGA和SA两个算法搜索到相同的最优模块度Q值的情况下,比较两个算法所花费的时间,计算SAGA与SA所花费的时间的百分比tSAGA/ tSA。将SAGA和SA应用在3 个网络数据集Karate、Dolphin和Polbooks上进行社团划分,实验结果如表2。

注: - 表示计算时间超过了24 h。

表2 所示,在获取到相同的模块度Q的条件下,Karate数据集上SAGA所需时间是SA所需时间的11. 4% ,Dolphin数据集上SAGA所需时间是SA所需时间的36. 9% ,表明由模拟退火和贪心策略结合的SAGA算法可大幅缩短SA获取最优值的时间,具有快速的识别速度。另外,在网络的结点规模超过100 个结点时,SAGA算法和SA算法在本文的实验条件和实现方式下,其所需时间均超过24 h,表明SAGA算法和SA算法均只适合于规模较小的网络社团划分。

3. 2. 2 SAGA算法识别精度评价

社团识别算法的识别精度主要依据算法运行后所获得的模块度Q值来确定,Q值越大表明算法的识别精度越高,Q值由式( 1) 计算而得。SAGA算法是在贪心策略社团识别上做的改进研究,目的是获得比贪心策略社团识别法( Greedy算法) 和Louvain社团识别法更优的结果。因此,将SAGA算法、Greedy算法、Louvain算法应用在Karate、Dolphin、Polbooks这3 个标准网络数据集上进行社团划分实验,3 个算法所获模块度Q如表3 所示。

表3 所示,在Karate、Dolphin、Polbooks数据集上,SAGA所获的模块度Q均大于Greedy算法、Louvain算法所获的模块度。表明SAGA算法确实拥有比较高的识别精度,能够达到比较准确的社团划分。同时,也表明由模拟退火和贪心策略结合的SAGA算法能有效地避免贪心策略易陷入局部最优的问题。

4 结束语

本文对模拟退火和贪心策略进行结合研究,提出一新的社团识别算法SAGA。实验结果表明SAGA具有强大的搜索能力和较模拟退火快速的执行速度,在精度要求较高且时间要求较快的场合具有一定的应用价值。另外,SAGA算法识别速度与精度受执行贪心策略的结点运动数影响。如何找到一个普适准则来计算此结点数,使SAGA在任何网络下都具有最优识别性能,这有待于进一步研究。

摘要：为了提高复杂网络社团识别的精度和速度,文中结合模拟退火和贪心策略识别社团结构的优势,提出一种新的社团识别算法。该算法利用贪心策略引导模拟退火搜索最优解过程中单个结点的无规则盲目移动,消除了大量无效移动,在搜索到全局最优解的情况下,将搜索时间大幅缩减。实验表明,SAGA具有强大的搜索能力和较快的模拟退火执行速度,可获得较高的模块度,达到较为准确的社团分割,且具有一定的应用价值。

贪心算法解决活动安排问题研究第3篇

假设要在足够多的会场里安排一批活动, 并希望使用尽可能少的会场。这里就需要选用合适的算法来解决类似的问题。虽然计算机的计算能力每年都在飞快增加, 但是, 需要处理的信息量更是呈指数级的增长。互联网的信息流量在飞快进步, 数据量更是达到了前所未有的程度。无论是三维图形, 海量数据处理等都需要极大的计算量。在网络时代, 越来越多的挑战需要靠卓越的算法来解决。

1 贪心算法以及贪心算法的基本要素

贪心算法是指从问题的初始状态出发, 通过若干次的贪心选择而得出最优值 (或较优解) 的一种解题方法。并不是从整体上加以考虑, 它所做出的选择只是在某种意义上的局部最优解。贪心算法可以简单描述为:对一组数据进行排序, 找出最小值, 进行处理, 再找出最小值, 再处理。也就是说贪心算法是一种在每一步选择中都采取在当前状态下最好或最优的选择, 从而希望得到结果是最好或最优的算法。

贪心算法解题步骤:①从问题的某个初始解出发;②采用循环语句, 就根据局部最优策略, 得到一个部分解, 缩小问题的范围或规模;③将所有部分解综合起来, 得到问题的最终解。另外它也是一种某种度量意义下的最优解的分级处理方法。

对于一个具体的问题, 怎么知道是否可用贪心算法来解决问题, 以及能否得到问题的一个最优解呢?从许多可以用贪心算法求解的问题中可以看到它们一般具有两个重要的性质:①贪心选择性质;②最优子结构性质。

另外, 同一个问题可用不用算法解决, 而一个算法的质量优劣将影响到算法乃至程序的效率。一个算法的评价主要从时间复杂度和空间复杂度来考虑。

2 用贪心算法描述问题

贪心算法高效地解决了一系列活动争用某一个公共资源的问题, 本文主要研究的是n个活动全部安排所需要的最少资源数。面对资源的日益紧缺, 如何有效合理地利用资源一直是专家学者研究的热点问题。

用贪心算法解决本题的思想是:资源足够多, 但要使用最少的资源安排全部活动, 同时保证每个资源中安排的活动集在时间上不能发生冲突。如果第一个资源中尽可能安排最多的活动, 则这个资源得到了充分的利用, 而且剩下的活动越少, 第二个资源也尽可能安排最多的活动, 依次类推。

以下我们证明该问题具有贪心算法的两个性质:

(1) 活动安排问题具有贪心选择性质

证明:首先将活动安排问题数学化, 设有n个活动的集合 E= { 1 , 2 , …, n }, 每个活动 i 都有一个要求使用该资源的起始时问si 和一个结束时问fi 。即k是所需最少资源的个数。设活动已排序, ( A1 , A2 , … , Ak ) 是所需要的k个已安排了活动的资源。

①当k = 1时, 也就是所有的活动在一个资源里相容, A1 是满足贪心选择性质的最优解;②当k >= 2时, 取B1=A1, BK=Ak (即Bk是安排了m个活动的一个资源, (n-m) 个活动都安排在B1 到Bk-1个资源里) 。就是 (n-m) 个活动安排需要 (k -1) 个资源。则 (B1, B2 , …, Bk-1 ) 是 (n - m) 个活动可行解。

另一方面, 由{ ( A1 , A2, …, Ak) -Ak}= (B1, B2, …, Bk-1) 知, (B1, B2, …, Bk-1) 也是满足贪心选择性质的最优解, 所以, 活动安排问题具有贪心选择性质。

(2) 活动安排问题具有最优子结构性质

证明: ( A1, A2, …, Ak ) 是n个活动的集合E= {1, 2 , …, n }所需资源的最优解。设A1中安排了m个相容的活动, 那么也就是说 (n-m) 个活动完全安排需要k-1个资源。假设 (n - m) 个活动安排只需要k-2个资源或则更少的资源。也就是说n个活动安排只需要k-1个资源就可以安排完, 则前后出现矛盾。一个问题的最优解包含其子问题的最优解时, 称此问题具有最优子结构性质。

3 程序清单及复杂性分析

算法的复杂性是算法运行所需要的计算机资源的量, 需要时间资源的量称为时间复杂性, 需要空间资源的量称为空间复杂性, 由于计算机的快速发展, 计算机的空间资源很少作为考虑的对象, 目前最为关注的就是时间复杂性。

利用数组解决活动安排问题。程序的思想:设有n个活动等待安排, 这些活动的起始时间和结束时间分别存放在数组 start[]和 finish[]中, 定义了一个整型变量flag用于标记活动是否被分配了资源。要对活动的开始时间与已分配的资源里最后被添加进去的活动的结束时间进行比较, 如果大于, 则把该活动添加进此资源, 否则继续与其他资源的最后被添加的活动的结束时间进行比较, 如果所有的已分配资源均安排不了, 则分配一个新资源来安排此活动。程序清单如下:

public class needSource{

①static int start[] ={1, 3, 0, 5, 3, 5, 6, 8, 8, 2, 12};//活动开始时间数组;②static int finish[]={4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14};//活动结束时间数组 public static void main (String[] args) { int i, j, flag=0; int num[]=new int[11];int m[]=new int[100]; //有足够多的资源 int source=1; //初始化, n个活动至少需要一个资源 int n=start.length; //活动的个数 (一共有多少个活动) num[0]=1; //num[i]=j;编号为i的活动安排在第j个资源里 m[1]=0; //资源1中最后被添加进来的活动编号是0;③for (i=1;i=finish[m[j]]) { //最后被添加进来的活动结束时间相比;⑥num[i]=j;//把i活动安排在j资源里;⑦m[j]=i; //记录最后被添加到j中的i活动;⑧flag=1; //标记活动已被分配到了资源 };⑨h=j; //j的值是变化的。赋值h以记录值;⑩if (flag==1) {//活动被安排了, 则跳出循环; (11) break; }}; (12) if (flag==1) {}else{ num[i]=h+1;//所有的资源都不能安排, 则添加新资源 m[h+1]=i; //记录最后添加到j+1中的活动isource++; } flag=0; }System.out.println (source) ;} }

结果及分析:程序实现了在控制台打印出所需要资源的个数。运行程序结果显示5, 与手工测算结果相同。

复杂性分析:语句①、②是给数组赋值语句, 是0①操作;语句③的循环控制变量i要从1增加到n, 故它的频度是n。语句④的循环控制变量j是从1增加到source, 但是source无论什么情况下都小于n, 则语句④最多循环了 (1+2+3+…+n) = (n2) /2, 而语句④的循环体中语句⑤因为每次都需要判断, 所以频度也是0 (n2) ;语句⑥、⑦、⑧执行的次数是一样的。并且和语句 (12) else循环体中的执行次数加起来正好是0 (n2) ;语句⑨、⑩执行次数是0 (n2) ;语句 (11) 最多执行n次;语句 (12) 的频度n;该算法中所有语句的频度之和 (即算法的时间耗费) 为: T (n) =0 (1) + 20 (1) +0 (n) +0 (n2) +0 (n2) +30 (n2) +20 (n2) +20 (n) ;所以时间复杂度是0 (n2) ;

4 结束语

本文对初步资源规划问题的思考, 可以对多个资源组合规划问题的基础研究提供有效的参考作用。目前多个资源组合规划问题在现实研究中仍有许多不尽人意的地方, 如何设计实用的算法解决多个资源组合规划问题, 是值得我们不断研究探讨的课题。

参考文献

[1]肖衡.浅析贪心算法[J].办公自动化杂志, 2009 (10) .

[2]常又渠, 肖贵元.贪心算法的探讨与研究[J].重庆电力高等专科学校学报, 2008 (2) .

贪心策略第4篇

背包问题KP(Knapsack Problem)是计算机科学中的一个典型问题[1],又称为子集和问题,在金融和工业领域的投资决策、预算控制、资源分配和货物装载等方面有着重要的应用,对于该问题的快速求解不仅具有理论意义,而且有极大的应用价值。目前,求解KP问题的算法通常有分枝定界法、贪心算法、二表算法和动态二表算法等经典算法[2],以及模拟退火算法(SA)、遗传算法(GA)、蚁群算法(ACO)和免疫算法等随机搜索算法[3,4]。经典算法的时间复杂性是指数阶的,对于大规模KP问题的求解效率极低,不能保证求得最优解。遗传算法和蚁群算法等随机方法是近年来提出的具有本质并行性和全局搜索特点的演化算法,在求解大规模KP问题方面,具有速度快、求得结果更优的优点。虽然演化算法的计算结果一般优于经典算法,但并不一定能得到问题的最优解。因此,如何改进现有的演化算法以追求更优求解质量是求解KP问题的一个重要研究方向。

本文首先介绍了背包问题的数学模型[1,7]和一种具有双重结构编码的二进制粒子群优化算法(DS_BPSO)[5];然后基于贪心算法思想,定义了一种解决非正常编码个体问题的贪心变换方法,给出了实现算法;将贪心变换方法与DS_BPSO相结合,提出了一种基于粒子群优化算法求解KP问题的新算法:基于贪心变换的DS_BPSO(简称GDS_BPSO)。对文献[3,6]中著名的背包实例,利用GDS_BPSO得出了一个更好解3119/1000,此解是目前已知的最好结果。此外,对不同规模的随机KP问题实例,将GDS_BPSO与混合遗传算法(HGA)[3]进行比较,结果表明:GDS_BPSO算法远远胜过HGA算法。

1 背景知识介绍

1.1 广义背包问题

广义背包问题GKP[1,7]是计算科学中一个典型的NP-hard问题,它的一般提法是:已知n个物品的容积和价值分别为wi和ci(1≤i≤n),背包的容量限制为v,如何选择物品装入背包,使得在背包容量限制之内所装入的物品的总价值最大?GKP的数学形式描述为:

设C=(c1,c2,…,cd)T,W=(w1,w2,…,wd)T,其中ci,wi∈Z,1≤i≤d,又设M∈Z,Z为正整数集。求d维向量X=(x1,x2,…,xd)T∈{0,1}d,使得:

$\begin{array}{l} \max f (x_{1}, x_{2}, \dots, x_{d}) = C X = \sum_{i = 1}^{d} c_{i} x_{i} \\ s . t . W X = \sum_{i = 1}^{d} w_{i} x_{i} \leq Μ (1) \end{array}$

其中,C=(c1,c2,…,cd)T为各物品的价值构成的向量,W=(w1,w2,…,wd)T为各物品的容积构成的向量,M为背包的最大容量。当xi=1时,表示第i个物品装入背包;WX为装入背包中物品的总容积,而CX为此时物品的总价值。显然,求解GKP只要求出满足(1)式的d维向量X=(x1,x2,…,xd)T。由于(1)式中带有约束条件,因此在利用演化方法求解GKP的过程中必须处理非正常编码的个体。常用的方法有罚函数法、特殊编码法和基于启发策略的修正法[4]。本文将采用最后一种方法,在下节中给出一种基于贪心策略的贪心变换修正方法。

1.2 具有双重结构编码的二进制粒子群优化算法

二进制粒子群优化算法BPSO(Binary Particle Swarm Optimization)[8]是粒子群优化算法(PSO)的二进制编码形式,由Kennedy和Eberhart于1997年首先给出,之后文献[9]讨论了利用BPSO算法求解Lot Sizing Problem。文献[5]分析了BPSO算法的缺陷,提出了一种比BPSO算法性能更优的具有双重结构编码的二进制粒子群优化算法(DS_BPSO)。下面简要介绍DS_BPSO算法的一般原理[5]。

在DS_BPSO算法中,定义第i个粒子为有序五元组 $(X_{i}, \bar{X}_{i}, V_{i}, Ρ_{i}, \bar{Ρ}_{i})$ ,其中 $\bar{X}_{i}, V_{i}, \bar{Ρ}_{i} \in$ 辅助搜索空间 $\bar{S} \subset R^{d}$ ;Xi,Pi∈{0,1}d,即 $X_{i} = (x_{i 1}, x_{i 2}, \dots, x_{i d})^{Τ} \in {0, 1}^{d}, \bar{X}_{i} = (\bar{x}_{i 1}, \bar{x}_{i 2}, \dots, \bar{x}_{i d})^{Τ} \in \bar{S} ‚ Ρ_{i} = (p_{i 1}, p_{i 2}, \dots, p_{i d})^{Τ} \in {0, 1}^{d} ‚ \bar{Ρ}_{i} = (\bar{p}_{i 1}, \bar{p}_{i 2}, \dots, \bar{p}_{i d})^{Τ} \in \bar{S}$ ;Xi为基本位置, $\bar{X}_{i}$ 为辅助位置;Pi和 $\bar{Ρ}_{i}$ 分别为个体最好位置和辅助最好位置; $V_{i} = (v_{i 1}, v_{i 2}, \dots, v_{i d})^{Τ} \in \bar{S}$ 为粒子速度。又令Pg=(pg1,pg2 ,…,pgd)T和 $\bar{Ρ}_{g} = (\bar{p}_{g 1}, \bar{p}_{g 2}, \dots, \bar{p}_{g d})^{Τ}$ 分别表示粒子在 $\bar{S}$ 和{0,1}d中全局最好位置。于是位置与速度更新公式为:

$v_{i j} (t + 1) = w v_{i j} (t) + c_{1} r_{1} (t) (\bar{p}_{i j} (t) - \bar{x}_{i j} (t)) + c_{2} r_{2} (t) (\bar{p}_{i j} (t) - \bar{x}_{i j} (t))$

$\bar{x}_{i j} (t + 1) = \bar{x}_{i j} (t) + v_{i j} (t + 1) (2)$

$x_{i j} (t + 1) = {\begin{cases} 0 若 s i g n (\bar{x}_{i j} (t + 1)) \leq 0.5 时 \\ 1 若 s i g n (\bar{x}_{i j} (t + 1)) > 0.5 时 \end{cases} (3)$

其中1≤i≤s,1≤j≤d;sign(x)是模糊函数,且sign(x)=1/(1+e-x);r1(t),r2(t)是(0,1)上的随机数。此外,如果f(Xi(t+1))≥f(Pi(t)),则 $Ρ_{i} (t + 1) = Ρ_{i} (t) ‚ \bar{Ρ}_{i} (t + 1) = \bar{Ρ}_{i} (t)$ ;如果f(Xi(t+1))<f(Pi(t))),则 $Ρ_{i} (t + 1) = X_{i} (t + 1) ‚ \bar{Ρ}_{i} (t + 1) = \bar{X}_{i} (t + 1)$ 。同时,Pg(t+1)∈{P1(t+1),P2 (t+1),…,Ps(t+1)}且 $f (Ρ_{g} (t + 1)) = \min {f (Ρ_{1} (t + 1)), f (Ρ_{2} (t + 1)), \dots, f (Ρ_{s} (t + 1))} ‚ \bar{Ρ}_{g} (t + 1) = \bar{Ρ}_{k} (t + 1)$ ,其中k满足Pg(t+1)=Pk(t+1)且1≤k≤s。

在(2)式中,c1和c2是加速常数,满足0≤c1≤c2且c1+c2=4;辅助搜索空间 $\bar{S} = [- 5 ‚ 5]^{d} ‚ d$ 为个体的维数;w为惯性因子,且w∈[0.4,1],一般可令w=1-t/MAXT,t为算法当前迭代次数,MAXT为算法的总迭代次数。

2 贪心二进制粒子群优化算法

在利用DS_BPSO算法求解GKP问题时,需要解决两个问题:一是由于算法每次迭代所产生的粒子位置向量Xi=(xi1,xi2,…,xid)T不一定满足(1)式的约束条件,即第i个粒子是非正常编码的个体,不能利用DS_BPSO算法直接求解,必须对向量Xi=(xi1,xi2,…,xid)T进行适当的修正,使其成为正常编码个体。注意到,当第i个粒子为非正常编码个体时,必然是 $\sum_{j = 1}^{n} w_{j} x_{i j} > Μ$ ,即Xi中xij=1的项太多,应采用适当的方法将Xi中某些项修正为零;另一个问题是个体编码的优化问题,即对于满足(1)式约束条件的向量Xi=(xi1,xi2,…,xid)T而言,尽管使不等式 $\sum_{j = 1}^{n} w_{j} x_{i j} \leq Μ$ 成立,但不一定使 $\sum_{j = 1}^{n} w_{j} x_{i j}$ 的值为极大。这样,第i个粒子的位置编码Xi=(xi1,xi2,…,xid)T尽管是合理的,但利用价值可能很小,即粒子位置编码的利用率太低。为了解决上述两个问题,下面定义一种贪心变换(Greedy Transform),并给出实现这种变换的有效算法。

定义1 设G:{0,1}d→{0,1}d,如果对于任意X=(x1,x2,…,xd)T∈{0,1}d,均有Y=G(X)=(y1,y2,…,yd)T∈{0,1}d满足 $\sum_{j = 1}^{d} w_{j} y_{j} \leq Μ$ ,并且使 $\sum_{j = 1}^{d} w_{j} y_{j}$ 的值极大,即不存在Z=G(X)=(z1,z2,…,zd)T∈{0,1}d,使得不等式 $\sum_{j = 1}^{d} w_{j} y_{j} < \sum_{j = 1}^{d} w_{j} z_{j} \leq Μ$ 成立,则称G为定义在{0,1}d上的一种贪心变换。

在贪心变换G的作用下,不满足(1)式约束条件的非正常编码个体X1被修正为正常编码个体Y1,并且使得个体Y1的编码是满足(1)式约束条件的最好或近似最好个体;而对于正常编码个体X2,在G的作用下被进一步优化为个体Y2,使得Y2满足不等式 $\sum_{j = 1}^{d} w_{j} x_{2 j} < \sum_{j = 1}^{d} w_{j} y_{2 j}$ ≤M,这样,个体X2进一步优化为个体Y2,有利于算法效率的提高。将实现定义1中贪心变换的具体算法称为贪心变换算法GTA(Greedy Transform Algorithm),下面即给出一种高效的贪心变换算法。

设X=(x1,x2,…,xd)T为非正常编码个体,Y=(y1,y2,…,yd)T为对X修正后的个体。又设M为背包的最大容量。C=(c1,c2,…,cd)T和W=(w1,w2,…,wd)T分别为各物品的价值和容积构成的向量,ind[ ]为一临时数组,则GTA的算法描述为:

算法1 贪心变换方法GTA(X,C,W,M)

步骤1 排序:根据ci/wi由大到小的顺序将i存入ind[ ];

步骤2 修正:

(1) 置t←2,yind[1]←xind[1],Temp←wind[1];

(2) 当t≤d时,重复执行(3)～(5);

(3) 计算Temp←Temp+wind[t]*xind[t]的值;

(4) 如果Temp>M且xind[t]=1,则yind[t]←0;

否则yind[t]←xind[t];

(5) 令t←t+1,转(2)继续。

步骤3 输出Y=(y1,y2,…,yd)T,结束。

注意,在数组ind[ ]中,ind[1]为C和W中价值容量比(ci/wi)最大的物品位序,依次类推,ind[d]为C和W中价值容量比最小的物品位序。此外,当物品的个数d较大时,在步骤1的排序中应选用快速排序算法[9],以加快排序速度。

将上述贪心变换GTA(X,C,W,M)融入DS_BPSO算法,用于处理非正常编码个体,可得到一种求解广义背包问题的新算法,由于贪心变换在其中起到关键作用,因此将新算法称为基于贪心DS_BPSO(简称GDS_BPSO),其伪代码描述如下:

算法2 GDS_BPSO算法

步骤1 初始化种群 ${(X_{i}, \bar{X}_{i}, V_{i}, Ρ_{i}, \bar{Ρ}_{i}) | 1 \leq i \leq s}$ ;

步骤2 Xi←GTA(Xi,C,W,M);Pi←Xi ;

步骤3 种群进化:对于i=1,2,…,s重复执行(1)～(6);

(1) 如果f(Xi)<f(Pi)则Pi←Xi; $\bar{Ρ}_{i} \leftarrow \bar{X}_{i}$ ;

(2) Pg←min{Pi|1≤i≤s}; $\bar{Ρ}_{g} \leftarrow \bar{Ρ}_{k} \land k s a t i s f i e d Ρ_{g} = Ρ_{k}$ ;

(3) 对于j=1,2,…,d重复执行(4)、(5);

(4) 计算 $v_{i j} \leftarrow ω v_{i j} + c_{1} r_{1} (\bar{p}_{i j} - \bar{x}_{i j}) + c_{2} r_{2} (\bar{p}_{g j} - \bar{x}_{i j})$ ;

(5) 计算 $\bar{x}_{i j} \leftarrow \bar{x}_{i j} + v_{i j}$ ;

(6) 计算Xi←GTA(Xi,C,W,M);

步骤4 当不满足终止条件时,转步骤3继续;

步骤5 输出(Pg,f(Pg)),结束。

3 GKP问题实例与计算结果

为了说明GDS_BPSO在求解GKP问题时表现出的优越性能,首先利用GDS_BPSO计算文献[3,6]中著名的GKP问题实例,并与文献[3,6]中结果相比较。由于混合遗传算法(HGA)[3]是求解背包问题的最有效算法之一,因此为进一步检验GDS_BPSO在求解GKP问题时的性能,分别利用GDS_BPSO和HGA对于不同规模的GKP问题实例进行求解,并且从算法所能够求得的最好解(由“总价值/总容量”表示)、求得此最好解所需的最小迭代次数以及成功率等三个方面进行比较。

限于篇幅,以下仅以文献[3,6]中的著名GKP问题实例,以及规模d=100和d=150的两个随机GKP问题实例来说明问题。在计算时,GDS_BPSO和HGA的相关参数设置分别为:算法迭代次数均设为200,种群规模设为100。在HGA中,采用单点交叉和单点变异,交叉概率和变异概率分别为0.5和0.1。在GDS_BPSO中,辅助空间取为[-5.0,5.0]d,c1=c2=2.0。为了计算成功率和最小迭代次数,各实例均重复计算20次;此外,给出最好解对应的个体编码(即粒子位置编码),以便于验证。

GKP问题实例1[3,6] 物品的价值集C={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},物品的容积集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,25,30,45,30,60,50,20,65,20,25,30,10,20,25,15,10,10,10,4,4,2,1},背包最大容量1000,规模为d=50。

由表1可知,利用GDS_BPSO算法求解实例1所得结果远远优于文献[3,6]中的结果。此外,利用GDS_BPSO算法还可以得出许多优于3103/1000的次优解,其中的一部分在表2中列出。

GKP问题实例2 物品的价值集C={998,997,991,986,978,977,939,936,924,920,911,901,901,885,880,866,866,863,856,842,809,794,792,789,778,767,764,764,763,759,756,747,739,708,707,706,694,693,684,680,676,652,644,640,628,612,607,597,593,570,560,556,556,556,542,538,530,530,520,498,487,466,464,461,459,456,452,443,412,399,391,383,381,378,377,359,353,351,327,317,311,295,289,287,283,269,249,248,235,193,189,189,134,108,93,74,51,48,23,8},物品的容积集W={353,180,377,230,87,174,157,390,186,213,56,86,77,215,252,90,360,187,294,379,372,384,93,328,283,99,114,374,383,183,248,164,323,263,266,318,296,196,10,324,128,376,19,280,229,225,217,134,233,35,361,302,166,374,392,319,241,15,384,82,158,322,139,239,110,44,115,23,267,82,30,198,173,70,329,125,220,107,148,159,351,56,17,99,308,396,327,235,213,223,372,376,191,299,304,277,292,391,120,37},背包最大容量9803,规模为d=100。

GKP问题实例3 物品的价值集C={997,981,953,943,943,942,939,934,928,918,917,915,914,911,908,900,891,889,870,869,846,841,838,830,826,820,820,812,807,804,799,796,789,783,777,776,773,753,753,753,753,750,740,735,734,726,715,713,697,696,691,688,646,641,636,631,620,616,615,610,605,595,590,589,588,585,582,578,577,568,563,561,558,553,552,548,546,536,523,518,512,510,508,507,504,491,486,475,457,450,448,441,434,425,409,407,400,398,390,383,369,365,358,353,350,344,343,331,326,299,299,288,277,275,266,258,254,237,233,233,231,223,209,201,199,197,194,191,179,176,171,163,147,141,132,127,85,85,73,64,36,35,29,28,27,27,22,15,6,1},物品的容积集W={102,78,388,352,161,323,333,196,113,296,236,203,208,264,74,265,181,161,63,258,136,136,154,363,67,119,234,235,97,302,75,311,96,9,321,301,197,387,374,224,251,93,234,245,145,26,24,95,306,254,339,321,283,102,352,282,32,191,252,236,336,132,52,250,20,32,370,262,264,315,314,117,241,21,217,49,99,6,288,336,146,185,225,343,253,397,159,134,395,228,131,7,109,102,60,290,199,335,209,36,382,38,38,42,29,211,38,61,153,137,51,105,295,4,192,201,24,33,168,229,283,218,295,288,50,65,344,139,374,385,181,144,380,92,249,173,245,37,227,385,395,393,149,353,257,376,148,289,202,80},背包最大容量14976,规模为d=150。

根据上述计算结果可以看出:对于不同规模(也包括规模d=200,300,500,800和1000等)的GKP问题实例,无论是在求得最优解(总价值/总容量)的质量方面,还是在求得最优解成功率和最小迭代次数方面,GDS_BPSO算法均远远胜过HGA算法。也就是说,对于GKP问题求解,GDS_BPSO算法是一种比HGA算法更有效的演化算法。

4 结束语

利用演化算法计算NP问题的最大优点在于求解过程不完全依赖于NP问题的固有性质,但是也应该看到,如果能将NP问题所具有的某种特性融入求解之中,必将极大地改善演化算法的求解性能和求解效率。本文将DS_BPSO算法与贪心变换方法相结合,提出了一种求解GKP问题的新算法GDS_BPSO,该算法既充分发挥了DS_BPSO的快速收敛特性,又充分利用了贪心变换对GKP问题所具有的优势。实践证明,GDS_BPSO算法是目前求解背包问题的最有效演化算法之一。

参考文献

[1]Martello S,Manderick B.Knapsack Problem.John Wiley,Chichester UK,1990.

[2]李肯立,李庆化,戴光明,等.背包问题的一种自适应算法.计算机研究与发展,2004,7(41):1292-1297.

[3]周明,孙树栋.遗传算法原理及其应用.北京:国防工业出版社,2001.

[4]黄席樾,张著洪,等.现代智能算法理论及应用.北京:科学出版社,2005.

[5]贺毅朝,王彦祺,刘建芹.一种适于求解离散问题的二进制粒子群优化算法.计算机应用与软件,2007(1).

[6]张铃,张钹.佳点集遗传算法.计算机学报,2001,9(24):917-922.

[7]陈国良,王熙法,庄镇泉,等.遗传算法及其应用.北京:人民邮电出版社,2003.

[8]Kennedy J,Eberhart R C.A discrete binary version of the particle swarm optimization.Proceedings of the1997Conference on Systems,Man,and Cybernetics,Piscataway,UJ,IEEE Service center,1997:4104-4109.

一种求解TSP的贪心遗传算法第5篇

TSP(Traveling Salesman Problem)即旅行商问题,一般描述为:设有n个城市组成的交通图,一个商人要从住地城市出发,到其它城市各一次去推销货物,最后回到住地城市。假定任意两个城市i、j之间的距离dij(dij=dji)是已知的,问应该怎样选择一条最短的路线?TSP是经典的NP完全问题[1]。

目前,求解该问题的方法有穷举法、回溯法、分支限界法、贪心法、智能计算[2~9]方法等。其中,穷举法、回溯法和分支限界法均是基于搜索的确定性算法,复杂度随着问题规模的增加指数级增加;贪心法和智能计算方法是近似算法,不一定能够得到TSP的最短路径。这些方法中,遗传算法得到的结果是比较令人满意的,只是收敛速度较慢,当问题的规模比较大时,会出现局部最优解,即近似最优解。为了提高遗传算法的收敛速度和求解质量,将贪心策略融入到遗传算法种群初始化和遗传算子中,着重考虑初始种群的质量和遗传操作的有效性,提出了一种基于贪心策略求解TSP的遗传算法。

1 求解TSP的贪心策略

TSP的实质是在给定的无向带权图中寻找长度最短的哈密尔顿回路问题。该问题的贪心策略主要有两种:1)始终选择距离商人所在城市最短且未走过的城市作为下一个要推销货物的城市,依此类推得到一条哈密尔顿回路;2)选用Prim算法或Kruskal算法采用的贪心策略生成最小生成树,然后前序遍历该最小生成树得到一条哈密尔顿回路。采用贪心策略得到的哈密尔顿回路一般优于随机产生的哈密尔顿回路。

2 贪心遗传算法

2.1 编码格式

任何一条哈密尔顿回路均是由无向带权图的所有顶点编号组成的一个排列,设n个顶点编号为(1,2,3,…,n),则由n个编号组成的全排列是所有可能的回路,最短哈密尔顿回路肯定包含其中。因此,编码采用自然数编码,每个自然数是一个城市编号,代表染色体的一个基因。每个染色体由n个基因组成,代表一条哈密尔顿回路,如染色体(1,3,4,2,7,5,6,9,10,8)表示由城市1出发,依次经过城市3→4→2→7→5→6→9→10→8,最后回到城市1的一条旅行路线。

2.2 适应度度量

问题的目标是找出路径长度最短的路径,因此路径长度能够衡量路径的优劣。路径长度长,则路径劣,反之,路径长度短,则路径优。因此,选用路径长度的倒数作为适应度函数,路径长度越长,适应度值越小,路径越劣,否则,路径越优。适应度函数设计如下:

fitness(28)1/d,其中,d为一条哈密尔顿回路的路径长度,i,jd为旅行商行进路径上从第i个城市到第j个城市之间的路径长度,fitness为染色体的适应度。

2.3 选择操作

采用精英策略,即在父代个体中选择一个适应度最大的个体代替子代个体中适应度最小的个体。这样,可以保证进化过程中最优个体随进化代数的增加而不断优化。

2.4 交叉操作

采用两点交叉操作,假设两个父代个体为X和Y,随机产生1~n之间的两个随机数pos1和pos2,不妨设pos1

显然,交叉后的新个体为:

2.5 变异操作

文献[10,11]统计了大量的TSP问题的最优解,发现TSP的最优解中每个城市都从距离自己最近的k个城市中选择一个作为下一个要推销货物的城市。如果k=1,则对应第2节中的贪心策略(1)。据文献[10,11]的统计,100城市以内,通常取k=9;100个城市到300个城市之间,取k=15;300个城市到1000个城市之间,取k=20。为此,建立一个二维数组G[1:n][1:k],其中G[i][j]中存储距离城市i最近的第j个城市编号。变异操作依据二维数组G进行变异。假设要变异的父代个体为Z,首先产生一个1~n之间的随机数x1,然后,产生一个1~k之间的随机数x2,查找G[Z[x1]][x2]中的城市编号在父代个体Z中的位置x3,将Z[x3]与Z[x1+1]交换位置。

变异操作依赖于二维数组G,快速形成二维数组G中的数据对提高遗传算法的求解速度大有帮助。这里采用分治法得到G中的数据。假设无向带权图的邻接矩阵为C[1:n][1:n],具体操作如下:

算法1分治法获得距城市i最近的k个城市。

步骤1:置i=1,kk=k;

步骤2:初始化b[1:n]={1,2,3,…,n};

步骤3:置L=1;R=n;

步骤4:产生一个L~R之间的随机数x;

步骤5:b[L]与b[x]交换;

步骤6:以b[L]指向的元素C[i][b[l]]为基准将数组b中的元素分成两部分,前半部分指向的元素比基准元素小,后半部分指向的元素比基准元素大,设基准元素所在的位置为j。

步骤7:如果j==k,则将b[1:k]中的数据存入G[i][1:k]中;如果j

步骤8:i++,如果i<=n,转步骤2;

2.6 种群初始化

设种群的规模为M,根据贪心策略(1)产生一个质量较高的正常染色体,然后进行(M-1)次变异操作。这样得到的种群质量很高且其中的个体均为正常染色体。

2.7 自适应交叉、变异概率

遗传算法中的交叉概率pc和变异概率pm的选择直接影响到算法的收敛性,贪心遗传算法中采用自适应交叉概率和变异概率,它们的计算公式如下:

其中fmax表示群体中的最大适应值;favg表示群体平均适应值;f表示要交叉的两个个体中较大的适应度值;f’表示要变异个体的适应值;k1,k2,k3,k4为常数,算法中取k1=0.5、k2=0.9、k3=0.02、k4=0.05。

当种群中各个体的适应度趋于一致或趋于局部最优时,使交叉概率和变异概率增加,相反,当群体适应度比较分散时,使交叉概率和变异概率减少。同时,对于适应度值高于群体平均适应值的个体,对应于较低的交叉概率和变异概率,使个体得以保护进入下一代;而低于平均适应值的个体,相对应于较高的交叉概率和变异概率,使该个体被淘汰。

3 仿真实验

为了验证算法的有效性,选用规模分别为10、50、100的三个实例进行实验,并且与基本遗传算法的求解情况进行对比。三个实例的具体数据如下:

实例1:规模n=10,10个城市的坐标分别为61 19,97 93,95 100,60 96,15 72,27 102,3395,10 34,29 41,48 77。

实例2:规模n=50,50个城市的坐标分别为34 91,10 71,72 12,58 105,94 26,47 17,10394,54 69,31 68,53 78,87 29,67 51,18 42,88 24,97 49,84 30,37 64,98 51,108 52,12 31,14 56,66 19,43 18,71 43,96 14,9552,66 98,62 64,76 43,70 29,41 48,77 86,108 24,30 63,17 79,26 32,52 17,73 70,57103,40 27,53 86,24 36,27 44,30 81,10274,64 76,74 85,10 22,10 61,86 89。

实例3:规模n=100,100个城市的坐标分别为71 101,71 40,108 79,101 10,89 27,27 24,105 51,46 77,38 63,19 83,91 13,79 26,9377,95 12,40 67,91 77,20 76,97 81,87 55,74 48,81 57,25 102,21 67,15 63,81 90,50 40,85 30,100 87,108 96,14 99,41 54,98 20,28 29,69 37,19 29,89 26,10 106,6368,40 103,16 59,64 82,70 104,64 43,5639,81 38,69 51,31 98,76 43,95 80,39 71,70 18,92 72,16 88,89 107,97 48,79 93,50 105,76 43,19 67,27 44,63 45,68 103,53 103,76 61,50 104,47 84,22 107,61 105,27 102,102 47,40 23,20 99,38 19,96 54,50 92,79 30,103 102,72 24,37 17,104 15,23 21,23 103,74 13,105 72,91 56,19 58,7834,21 64,45 37,43 50,72 37,87 27,50 52,10 10,68 86,64 45,40 41,105 47,33 32,37106。

利用贪心遗传算法和基本遗传算法对上述三个实例分别进行了50次独立实验,种群规模M=80,最大迭代次数500代,实验结果统计如表1所示。

由表1可以看出:1)贪心遗传算法的平均迭代次数和最好解出现次数均优于基本遗传算法;2)在求解结果方面,针对实例1,两种算法得到的结果一致,均为最优解,而实例2和实例3,两种算法得到的解均为近似最优解,贪心遗传算法的最好解明显优于基本遗传算法的最好解。由此,贪心遗传算法的求解速度和求解质量均优于基本遗传算法。

4 结束语

贪心遗传算法是将基本遗传算法和贪心策略融合的产物。贪心策略的融入,改进了遗传算法的性能,提高了求解的质量和速度。在今后的研究工作中,将继续关注经典启发式策略与近似算法的融合,以提高近似算法的有效性。

摘要：文章分析了求解TSP的多种方法,研究了TSP的贪心策略,将贪心策略融入到遗传算法的种群初始化和遗传操作中。同时,采用分治策略获取距离当前城市最近的k个城市,提出了一种贪心遗传算法。实验结果表明:贪心遗传算法在求解速度和求解质量上都有明显改进。

关键词：旅行商问题,遗传算法,贪心策略,分治法

参考文献

[1]M Garey,D Johnson.Computers and Intractability[M].WH Freeman,San Francisco,1979.

[2]王宇平,李英华.求解TSP的量子遗传算法[J].计算机学报.2007,30(5):748-755.

[3]黄勇军,武友新,刘华斌.应用改进的遗传算法求解TSP问题[J].计算机工程与设计.2007,28(24):5909-5911.

[4]王哲,何锫.压缩搜索空间的遗传算法在TSP中的应用[J].计算机工程与设计.2009,30(16):3830-3832.

[5]王永贵,曲海成,赵婉彤.一种改进的遗传算法在TSP问题中的应用[J].辽宁工程技术大学学报(自然科学版).2011,(30)2:263-267.

[6]张建萍,刘希玉.一种基于基因库求解TSP的单亲遗传算法[J].计算机仿真.2010,27(8):198-200.

[7]张启义,邱国庆,寇学智,陈亮.两阶段遗传算法在求解TSP问题中的应用[J].解放军理工大学学报(自然科学版).2011,12(1):79-82.

[8]汪金刚,罗辞勇.求解TSP问题的自适应邻域遗传算法[J].计算机工程与应用.2010,46(27):20-24.

[9]陶利民,郭俊恩.改进遗传算法在求解TSP问题上的应用研究[J].计算机工程与应用,2009,45(33):45-47.

[10]萧蕴诗,李炳宇,吴启迪.求解TSP问题的模式学习并行蚁群算法[J].控制与决策,2004,19(8):885-888.

一种油井运输车调度的贪心算法第6篇

关键词：油井,运输车,贪心算法,调度

在石油开采过程中，当油井采油量到达其储油限度时需要派运输车前往油井将已采好的石油运回油场控制中心。一辆运输车的运输量一般大于一个油井的储量，如果只运输已满油井的油会造成运输资源的浪费，因此需要派遣尚未装满油的运输车前往其他油井采油。在这个过程中，如何选择油井前往是有区别的。如果选择的油井不当，可能会造成运输车需要前往的油井数较多。这样会增长运输车的行驶路程，浪费运输资源。因此选择合适的调度策略进行油井运输车调度是非常必要的。在目前实际工程中往往是根据经验人工调度车辆，非常不科学，因此需要一个有效的调度算法来调度运输车运输的路线。此问题实际上是一个NP完全问题，理论界尚未提出最优解的成熟的解决方法，但在具体工程应用中，可以尝试得到次优解的解决方案，往往在很大程度上能够满足工程的需要，因此提出一种贪心算法解决油井运输车调度问题。

1 一种油井运输车调度策略优劣的评价标准

对于油井运输车调度这个实际问题，明确调度策略优劣的评价标准是非常必要的，因为调度策略的评价标准实际上就是设计调度算法的目标。明确了这个目标，才能按照这个目标来设计调度算法。

一般来说，油井运输车调度有两个目标，一是尽可能多的运输石油，二是尽可能减少运输车行驶的总路程。然而这两个目标本身就具有矛盾性，如果希望尽可能多的运输石油则往往需要前往多个油井采油，便会增加行驶的总路程，从而增加运输成本。由于这两个目标在实际情况中都是影响运输的重要因素，因此需要综合考虑这两个目标，才可以全面、合理地解决油井运输车调度问题。在此，我们提出一个综合的调度目标，即使得单位采油量所消耗的成本最小，可以得到如下公式：

其中A为每次发出一辆运输车所需的固定成本，S为行驶的总路程，K为单位路程所需花费的成本，C为采油总量，wei为评价值。评价值可以作为评价调度策略优劣的标准，评价值越小说明单位采油量所消耗的成本越低，运输效率越高，因而调度策略越好，反之则越差。

2“最小耗运比优先”贪心调度算法

2.1 算法思想介绍

根据上面提出的油井运输车调度策略优劣的评价标准，我们提出了一种使单位运油量运输成本最少的贪心调度算法，在此称之为“最小耗运比优先”贪心调度算法。算法思路是，当检测到油场的某个油井的储油量满时，便派一辆运输车到达此油井将其所有储油运光。此时运输车还有运输量剩余，需要前往其他油井运输石油。现在需要按照一个准则来选择下一个油井前往并运输该油井的石油，以后不断按照这个准则选择油井前往，直到运输车装满为止。这个准则我们是这样确定的，选择一个油井，该油井满足：前往该油井可以采取的石油量除以为了到达该油井采油在总路程上多行的路程的商值是所有油井中最大的一个。前往该油井采油。其中前往该油井可以采取的石油量为该油井的石油储量与运输车剩余运输量两者中的较小者。而为了到达该油井采油在总路程上多行的路程是现在所在油井到该油井的路程加上该油井到出发点的路程减去现在所在油井到出发点的路程。商值为单位多行的路程获得的采油量，这个值完全可以反映单位运输资源的运油效率，显然应该选取值最大的一个前往。以后以此类推，直到运输车满为止。

2.2 算法具体步骤

每当某一油井油满时便派遣一辆运输车至此油井将其储油全部运光，然后按照下面的方法为这辆运输车寻找以后各油井进行采油：

(1）计算每次行程造成在总路程上多行的路程

用目前处在的油井到下一个油井的距离加上下一个油井到出发点的距离减去目前所处的油井到出发点的距离，得到此次行程造成在总路程上多行的路程，如图1。

S1为目前所处油井到下一个油井的最短距离，S2为下一个油井到油场控制中心的距离，S3为目前所处油井到油场控制中心的距离。S即为此次行程造成在总路程上多行的路程。

(2）计算每次前往下一个油井的最多运油量

如果下一个油井储油量大于目前运输车的剩余运量，则前往下一个油井采油后可以将运输车装满，则那时比现在多运输的运输量为目前运输车的剩余运量。如果下一个油井储油量小于目前运输车的剩余运量，则前往下一个油井可以将该油井的所有储量运光，则比现在多运输的运输量为下一个油井的储量。

X为将前往的油井的目前储油量，L为运油车此时剩余载量，M即为前往下一个油井最多运油量。

(3）将路程和运油量化为统一量纲

将路程和运油量分别除以各自平均值，化为统一量纲，为下一步加权做准备。

其中S为任意两点间最短路径的平均值，n为点的总个数。为油井的平均容量，m为一个油井的总容量。S'为统一量纲后的路程量，M'为统一量纲后的运油量。

(4）计算确定前往哪个油井的评价值W

其中H1,H2分别为每次采油量和每次多行路程的系数，由管理人员依据对采油量和所行路程两个因素的重视程度人为灵活设定。将S和M加权之后相除，即为行驶单位多行的路程换来采油量的多少，将这个值作为评价值W。

对除了当前所在油井以外的所有油井按此公式求出一个评价值W，选择评价值最大的一个作为下一个前往的油井，在下一个油井采过油后，若运油车载量已满，则选择返回。否则选择评价值最大的一个油井前往，继续循环，直至某一次载量满时选择返回。

2.3 算法原理解释

此算法是贪心算法的变形与应用。采用每到一个油井就判断一次的方式，每次找出条件最优的一个油井作为下一个目的地前往，直至达到可返回条件，开车返回。

在寻找条件最优的油井的过程中，实际上是一种加权模型。分别对每次采油量和每次相比于直接返回多行的路程两个因素进行加权。权重的设定可根据具体情况下对各因素的偏重灵活设定，也可在具体情况下经过试验确定。在加权之前首先要将不同量纲的两个因素化为相同量纲，即将每次采油量除以其平均值(在此平均值用储油罐体积的一半代替)，将每次多行的路程除以任意两点间路程的平均值，因为只有对相同量纲的量进行加权才有意义。将加过权的两个量相除是用来计算行驶单位多行的路程换来采油量的多少，将这个值作为评价值。对所有的点进行这样的计算，对这个值进行比较，选取其中值最大的一个，即为最合算的下一目的地。

2.4 算法分析与改进

由于在实际情况下可能出现这样的情况，即某一次采油结束后，运油车未满载，但剩余载量很小，而按照上述方法计算出的评价值最大的一个油井也距离较远。因此前往任何一个油井均不合算，应该立即放回。然而根据前述算法，还应该前往一处油井执行一次运输，造成运输资源的浪费。因此算法应该改进，下面给出两种改进方案：

方法一改进算法实际上是改进算法中的可返回条件。为此，仍然应用加权模型，即在每一个油井采过油后，按照同样的方法计算各油井的评价值，选出最大的一个评价值，若此最大评价值<1，则认为此时全部油井均不值得前去采油，即所行路程所消耗的运输资源已大于此次采油的价值，因此放弃采油，选择返回。否则选择评价值最大的一个油井前往，继续循环，直至某一次满足可返回标准，选择返回。

方法二和方法一一样，方法二也是改进算法中的可返回条件，但改进方法不同。运用第2部分中提出的评价标准，在每此到达一个油井采完油后，用“最小耗运比优先”调度算法得到下一个应该前往的油井，假设前往下一个油井，用上述评价标准对整个过程求出一个评价值，如果求出的评价值比不前往下一个油井的评价值大，则说明不合算，因此立即返回，如果小则前往下一个油井。

3 结束语

本文提出一种解决油井运输车的储量大于一个油井的储油量的情况下进行运输车的调度算法。使用贪心法的思想，很好地解决了充分合理地利用运输车资源进行运输的问题。且此算法的时间复杂度低，完全可以用程序实现后运用在实际系统中，有很好的实用性，因此很有价值。

参考文献

[1]王海龙.城市公交系统调度的优化模型[J].南昌航空大学学报(自然科学版),2009,23(4):17-19.

[2]苏永云,晏克非,韩皓.公交运营特性模型研究[J].重庆交通学院学报,2001,20(1):42-46.

[3]游维.基于贪婪策略的0/1背包问题算法研究[J].计算机与现代化,2007(4):12-16.

贪心策略第7篇

1 多目标二维切割问题数学模型

1.1 问题描述及建模

在这里, 我们只考虑剩余的材料是矩形的情况, 如果是多边形, 可将其化为矩形再考虑进一步的切割。接下来, 把这些剩余材料看作是原材料, 针对一定数量和大小的零件需求, 建立数学模型。由于所剩余的材料大小不等, 这类切割问题被定义为多目标的切割问题。

解决复杂的排样问题的二维优化下料模型一般都是构造成线性规划的数学模型, 以原材料消耗的总面积最小为目标, 但是对于我们所要讨论的情况, 仅仅考虑消耗的总面积最小是不够的, 还要考虑所用原料的种类最少。

设原材料板材, 其长、宽、数量分别记为 (Li, Wi, di) , 其中i=1, 2, L, n, 待下料的零件的长、宽、数量记为 (l, w, b) , 求如何下料使所用原材料的总消耗最小且所用原材料的种类最少。可用如下数学模型来描述:

上述模型是一个大型整数线性规划模型, 随着原板材种类的增加, 下料方式总数也将急剧增加, 导致用单纯形法或分支定界法很难求解。

1.2 模型说明

下面对模型中所涉及的变量及模型的合理性进一步说明。目标函数是使锯切损失且所使用原材料的种类最少, 因为不同规格的原材料的使用可以减少据切损失但同时又会增加材料成本和库存成本;

(1) 式为对所需零件数量的约束;

(2) 式为对原材料数量的约束。

2 贪心算法

贪心算法总是做出当前看来是最好的选择。也就是说, 不从整体最优上加以考虑, 它所做出的仅是在某种度量标准上的局部最优解。但是它对范围相当广泛的许多问题能产生整体的最优解。对于一个给定的问题, 往往可能有好几种度量标准, 这些度量标准初看似乎都是可取的。但实际上, 用其中的大多数度量标准作为贪心方法处理的度量标准, 得到的最优解并不是问题的最优解, 而是次优解。在使用贪心算法设计求解的过程中, 选择能产生问题最优解的最优度量标准是一个核心问题。一般情况下, 选出最优度量标准并不是一件容易的事, 不过, 一旦选出某个问题的最优度量标准, 那么用贪心算法求解这个问题就特别有效。

贪心算法的基本思路是从问题的某个初始解出发, 逐步逼近给定的目标, 以尽可能快的求得最好的解。当到达算法中的某一步不能再继续前进的时候, 算法停止。实现该算法的过程如下:

(1) 从问题的某一初始解出发;

(2) 同时能朝给定的总目标前进一步求解;

(3) 求出可行解的一个解元素;

(4) 由所有解元素组合成问题的一个可行解。

贪心算法, 该算法针对本文所讨论的切割问题的主要思想是每次只考虑在一块原材上的排样, 完毕后, 调整下料零件总量;重复此过程, 直至所有的待切割零件被排完。这种方法对切割方式不作整体优化, 避免了大规模线性规划的求解, 算法较简单。算法的核心在于用启发式算法来求解在一张原材上的最优切割方式。由于该算法没有对所有切割方式作整体优化, 效果不是很理想。但是对于本文所讨论的内容, 由于待下料的零件形状、大小是单一的, 切割方式的选择也就很有限, 只能考虑到零件长与宽的不同摆放方向, 因此, 采用贪心算法求解能达到很好的效果。

3 贪心算法求解多目标二维切割问题

由于下料方式的解集数目较多, 遍历到所有的方式是不现实的, 因此, 优化下料问题就是找到一组近似于最佳的下料组合方式。

以使用一种原材料所剩余的余料以及原材料使用的种类数最少为贪心选择决策, 即如上节所描述的数学模型中, 以

为贪心选择决策。

通过一系列局部最优的选择, 即贪心选择来求得整体最优解。

4 算法求解实例

一个物料发放系统, 有以下几种尺寸存货:

现在有用户需要16*21尺寸的料20块, 怎样找出浪费最小的尺寸?

通过计算, 结果如图1所示。

通过C语言实现, 选择80*90㎝2尺寸的原料一张, 就可以切割出所需要的20块16*21㎝2的材料, 且平均剩余最少。

5 结论

本文重点讨论了大规模多目标二维下料问题的快速解法, 即采用贪心算法的近似求解该算法简明, 易于编程。实践证明, 采用该算法能得到很好的解。