积分商城

最新搜索： C8051F310 三菱fx3u编程手册 8051 ip S3C2440 STM32Cube高效开发教程 基础篇 萝莉遥控
您现在的位置是：首页 > 教程 > 组合优化中启发式算法的研究分析
推荐星级：
  • 1
  • 2
  • 3
  • 4
  • 5

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

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

资料介绍

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

部分文件列表

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

【关注视频号领20积分】   【关注公众号立即送20积分】

部分页面预览

（完整内容请下载后查看）
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 初始种群有四个个体 01101、11000、01000、  
)
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复制了两次 , 01000和 10011各自复制了一  
次 ;  
( )  
5 复制进行交叉操作 ,假设 011│01和 100│  
11, 0110│1和 0100│0之间进行交叉形成 01111,  
10001, 01100, 01001即 15, 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为其改变量 , k为 Bolt2  
( )  
1 随机产生一组初始个体构成初始种群 ,并  
Mann常数。用固体退火模拟组合优化问题 ,将内能  
E模拟为目标函数值 f ,温度 T演化成控制参数 t ,  
即得到解组合优化问题的模拟退火算法 :由初始解 i  
和控制参数初值 t开始 ,对当前解重复“产生新解 →  
计算目标函数差 →接受或舍弃 ”的迭代 ,并逐步衰减  
t值 ,算法终止时的当前解即为所得近似最优解 ,这  
是基于蒙特卡罗迭代求解法的一种启发式随机搜索  
评价每一个个体的适配值 ;  
( )  
2 判断算法收敛准则是否满足。若满足则输  
( )  
出搜索结果 ;否则执行 3 ;  
( )  
3 根据适配值的大小以一定方式执行复制操  
作 ;  
( )  
4 按交叉概率 pc执行交叉操作 ;  
( )  
5 按变异概率 pm 执行变异操作 ;  

相关下载

全部评论(0)

暂无评论
评论赚积分>>

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

热门标签

更多>>

最新上传

  • 打赏
  • 30日榜单

热门下载

推荐下载

本站上的所有资源均为源于网上收集或者由用户自行上传，仅供学习和研究使用，无任何商业目的，版权归原作如有侵权，请 来信指出，本站将立即改正。

ICP许可证号：京ICP证070360号     21IC电子网 2000- 版权所有

京ICP备11013301号

京公网安备 11010802024343号