推荐星级:
  • 1
  • 2
  • 3
  • 4
  • 5

组合优化中启发式算法的研究分析

更新时间:2019-12-15 15:23:32 大小:161K 上传用户:杨义查看TA发布的资源 标签:组合优化启发式算法 下载积分:1分 评价赚积分 (如何评价?) 打赏 收藏 评论(0) 举报

资料介绍

文档为组合优化中启发式算法的研究分析总结文档,是一份不错的参考资料,感兴趣的可以下载看看,,,,,,,,,,,,

部分文件列表

文件名 大小
组合优化中启发式算法的研究分析.pdf 161K

部分页面预览

(完整内容请下载后查看)
2005年第 1期  
淮 南 职 业 技 术 学 院 学 报  
NO. 1, 2005  
(
)
5卷 总第 14期  
JOURNAL OF HU INAN VOCATIONAL & TECHN ICAL COLLEGE  
VOL. 5, Serial No. 14  
组合优化中启发式算法的研究分析  
戴书文  
(
)
安徽理工大学数理系 , 徽 淮南 232001  
(
)
[]在组合优化的实际问题求解中 ,背包问题 , TSM 问题等 NP Non - determ inistic Polynom ial 问题  
在多项式时间内无法得到最优解 ,要解决此类问题 ,就必须借助于启发式算法 ;简单介绍了计算复杂性概念 ,列  
举了几种常用的启发式算法 ,并给出算法的自然语言描。  
[关键词 ]组合优化 ; 发式算法 ; 传算法 ; 拟退火算法  
(
)
[中图分类号 ] TP301. 6ꢀꢀ[文献标识码 ]Aꢀꢀ[文章编号 ]1671 - 4733 2005 01 - 0072 - 03  
。  
1言  
算法的复杂性仅仅依赖于所要求解问题的规  
,算法的输入 ,以及算法本身的函果一个实  
组合优化问题是指在给定优化条件下从所有的  
安排方案中找出最优的安排方案 ,其一般数学模型  
可描述为 :  
( )  
例的输入长度记为 d I ,而计算最优解的基本计算  
( )  
( )  
( )  
次数 C I d I 的一个多项式函数 g x 我  
(
(
) )  
m in f x :目标函数 ,组合优化的目。  
们称该问题通过某算法是多项式可解于很多  
(
)
rest  
x
:约束条。  
( )  
问题 ,并不存在多项式函数 g x 使问题得以解决 ,  
x
D:D 为有限点所组成的集。  
有可能需要指数时间才可解 ,此类问题在 n较大时  
所需要的时间往往让人无法接。  
背包问TSM料问题均属于组合优化  
类问题 ,理论证明 ,这些问题都是 NP类问类  
问题无法在多项式时间内求得最优解 ,因此只有依  
靠一些优化算法来寻找局部最优解或可行些  
优化算法包括禁忌搜拟退火传算法经  
网络等算法 ,涉及生物进工智理科  
经系统和统计力学等科学概念 ,并以一定的直  
观基础构造而成 ,我们统称为启发式算。  
对于给定的一个优化问题 ,若存在一个求解问  
( )  
题的最优解的算法 ,一个多项式函数 g x 和一个有  
( ) ( ) )  
(
限常数 a ,使得 C  
I
= ag d I  
,则此类问题称为  
(
)
多项式 Polynom ial 问题 ,简称 P。  
但是并不是所有的组合优化问题都能找到求解  
最优解的多项式时间算法 ,也就是不能确定一些组  
合优化问题是否属于 P问题 ,于是这些问题被成为  
NP - Hard。  
2算复杂性  
算法的复杂性的高低体现在运行该算法所需要  
的计算机资源的多少上 ,所需要的资源越多 ,该算法  
的复杂性就越高 ;反之 ,所需要的资源越少 ,该算法  
的复杂性越组合最优化问题的定义可知 ,每  
一个组合最优化问题都可以通过枚举的方法求得最  
优解 ,枚举是要时间的 ,有的时间还可以接受 ,有的  
却没有办法接以我们对枚举算法的分析要考  
虑其空间和时间的复杂度问题 ,也就是对算法进行  
正因为一些组合优化问题还没有找到求解最优  
解的多项式时间算法 ,而这些问题又有很强的实际  
应用背景 ,所以启发式算法便应运而。  
3发式算法  
启发式算法是相对于最优算法提出的 ,一个问  
题的最优算法是求得该问题每个实例的最优解 ,启  
发式算法可以这样定义 :  
[收稿日期 ]2005 - 01 - 28  
(
)
,,安徽天长市人 ,研究生 ,助教 ,研究方向 :人工智能器学习算机网络 ,电话 :  
[作者简介 ]戴书文 1979 -  
13083070750。  
5期  
戴书文 :组合优化中启发式算法的研究分析  
73  
( )  
( )  
一个直观或经验的构造算法 ,在可以接受的花  
6 返回 2 。  
(
)
费 时间 ,空间等 下给出待解决组合优化问题的每  
个实例的一个可行解 ,该可行解与最优解的偏离程  
度并不一定可以预。  
在算法中 ,适配值是对染色体进行评价的一种  
般所要优化的函数即为遗传算法中的评价  
。  
( )  
(
)
另一种定义是 :启发式算法是一种能在可接受  
的费用内寻找最好的解的技术 ,但不一定能保证所  
得解的可行性和最优性 ,甚至在多数情况下 ,无法阐  
述所得解同最优解的近似程。  
例如求函数 f x = 200 - x - 15 ^2[ 0 31 ]  
范围内最大讲问题进行编码 ,也就是怎样把  
问题求解形式化为种群进这个问题 ,我们用  
(
)
5位二进制来表示 x , 01010 就是 x个就  
(
)
由于在某些情况下 ,最优算法的计算时间使人  
无法忍受或者问题的难度使其计算时间随问题的规  
模的增加而以指数速度增加 ,此时便只能通过使用  
启发式算法来求得问题的一个可行。  
4种常见的启发式算法分析  
是遗传算法中的染色体 ,而评价函数就是 f x 本  
用遗传算法求解的过程为 :  
( )  
(
1 初始种群有四个个体 011011100001000、  
)
10011 ,分别代表 x = 13, 24, 8, 19;  
( )  
2 适配值 fi依次为 196, 119, 151, 184;  
( )  
( )  
3 选择概率 ps = fi/ sum fi 依次为 0. 30, 0.  
4. 1忌搜索算法  
18, 0. 23, 0. 28;  
( )  
禁忌搜索是一种人工智能算法 ,是局部搜索算  
法的扩展 ,所谓禁忌就是指禁止重复前面的工作。  
它的一个重要思想是标记已得到的局部最优解 ,并  
在进异步的迭代中避开这些局部最优忌搜索  
算法用一个禁忌表中的信息记录下已经到达过的局  
部最优解 ,下次不再或有选择的搜索这些点 ,从而可  
以跳出这些局部最优。  
4 按照概率执行复制操作产生新的一代 ,假  
01101复制了两次 , 0100010011各自复制了一  
;  
( )  
5 复制进行交叉操作 ,假设 01101100│  
11, 0110101000之间进行交叉形成 01111,  
10001, 01100, 0100115, 17, 12, 9;  
( )  
6 新的一代的适配值为 200, 196, 191, 164。  
禁忌搜索的典型步骤为 :  
( )  
1 选定一个初始解 xFirst,及给以禁忌表 H =  
可见新的一代的适配值比上一代。  
在遗传算法中 ,选择是保证新的一代适配值比  
上代高 ,交叉和变异是保证种群的多样性 ,防止算法  
Ф。  
( )  
2 若满足停止规则 ,停止计算 ;否则 ,xFirst  
(
过快的陷入局部最优解变异概率太大 无穷  
(
)
的邻域 N H , xFirst 中选择满足禁忌要求的候选集  
)
大 时 ,遗传算法就相当于随机搜索 ,当变异的概率  
(
)
(
)
candx xFirst ;candx xFirst 中选择一个评价  
(
)
太小 为零 时 ,就相当于贪婪算样选择合适  
的选择 ,交叉和变异的概率一般都与实际问题有关 ,  
现在仍然没有好的理论方法来选。  
值最佳的解 xNext,xFirst = xNext;更新历史记录  
( )  
H ,重复步骤 2 ;  
其中的涉及的技术问题主要有 :禁忌对象的选  
,禁忌长度的确定 ,候选集的确定 ,评价函数的确  
,被禁对象是否可以再次被禁忌。  
4. 2传算法  
4. 3拟退火算法  
模拟退火算法来源于固体退火原理 ,将固体加  
温至充分高 ,再让其徐徐冷却 ,加温时 ,固体内部粒  
子随温升变为无序状 ,内能增大 ,而徐徐冷却时粒子  
渐趋有序 ,在每个温度都达到平衡态 ,最后在常温时  
达到基态 ,内能减为最Metropolis准则 ,粒  
遗传算法是一类随机优化算法 ,他通过对染色  
体的评价和对染色体中的基因的作用 ,有效的利用  
已有的信息来指导搜索有希望改善优化质量的状  
准遗传算法的主要步骤为  
Δ
(
)
子在温度 T时趋于平衡的概率为 e - E / kT ,其  
Δ
E为温度 T时的内能 , E为其改变量 , kBolt2  
( )  
1 随机产生一组初始个体构成初始种群 ,并  
Mann固体退火模拟组合优化问题 ,将内能  
E模拟为目标函数值 f ,温度 T演化成控制参数 t ,  
即得到解组合优化问题的模拟退火算法 :由初始解 i  
和控制参数初值 t开始 ,对当前解重生新解 →  
计算目标函数差 受或舍弃 的迭代 ,并逐步衰减  
t,算法终止时的当前解即为所得近似最优解 ,这  
是基于蒙特卡罗迭代求解法的一种启发式随机搜索  
评价每一个个体的适配值 ;  
( )  
2 判断算法收敛准则是否满满足则输  
( )  
出搜索结果 ;否则执行 3 ;  
( )  
3 根据适配值的大小以一定方式执行复制操  
;  
( )  
4 按交叉概率 pc执行交叉操作 ;  
( )  
5 按变异概率 pm 执行变异操作 ;  

全部评论(0)

暂无评论

上传资源 上传优质资源有赏金

  • 打赏
  • 30日榜单

推荐下载