




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、一个问题:道路铺设电网架设网络构设537( ,154,)线形时间Prim 算法Kruskal算法指数时间搜索算法 牛牛文库文档分享方案基本费用难度系数生态破坏e1,e2504030e2,e3503050e3,e1405040综合评价260310300(20,30,10)(30,10,20)(20,20,30)e1e2e3CITY1CITY2CITY3架设铁路的基本费用架设铁路的难度系数铁路造成的生态破坏修建一条铁路需要考虑的因素124一个简单的例子 牛牛文库文档分享一个问题:道路铺设电网架设网络构设537( ,154,)线形时间Prim 算法Kruskal算法指数时间搜索算法 牛牛文库文档分享
2、一个问题:数据规模1789101112131415估计用时1s内2s40s20m6h8d270d30y1200y天文数字537( ,154,)搜索算法的时间复杂度我们真的要等1200年?如果有一种方法能在短短的时间内得到一组与最优解十分逼近的近似解呢? 牛牛文库文档分享遗传算法历史背景遗传算法(Genetic Algorithm)是一种模拟自然选择和遗传的随机搜索算法。它由John Holland提出,最初用于研究自然系统的适应过程和设计具有自适应性能的软件。近年来,遗传算法作为问题求解和最优化的有效工具,已被非常成功地应用与解决许多最优化问题并越来越流行。42578714769940初始化群
3、体估价工作流程问题的一个可行解编码理论编码理论 牛牛文库文档分享57409987761442遗传算法工作流程估价保持遗传交配遗传变异遗传概率控制 牛牛文库文档分享遗传算法多目标最小生成树编码理论Prfer编码机制 每一棵树与一个长度为n-2的数字串对应 对于任意一个长度为n-2的数字串也与唯一的一棵生成树相对应编码过程 编码串初始为空串 令j为树中编号最小的叶节点; 如果j与i相邻,则把i加入当前编码串的最右端 把j以及连接i和j的边从树中删除,这时候树只有n-1个顶点 重复以上步骤直到树中只剩下一条边这时候得到的编码串即为相应树的Prfer编码解码过程设P为编码串,S为图的顶点编号不出现在P
4、中的顶点的集合;设i为S中编号最小的顶点,j为P中最左端的顶点,则将连接i和j的边加入到树中,然后分别把i和j从P和S中删除,如果P中不在出现顶点j则把j加入到S中重复以上步骤,直到P为空;当P为空串时,S中刚好剩下两个顶点,将连接这两个顶点的边加入到树中,最后构成的树即为与最初P对应的生成树。 优势可以很容易地随机生成一棵生成树很适合执行各类遗传操作 牛牛文库文档分享遗传算法多目标最小生成树编码理论估价函数估价函数设置 fi(x)表示待估价的染色体在目标i的费用情况,mini表示截止到上一代为止,产生的所有染色体在目标i的费用的最小值。优势更好的突出了每个染色体在各个目标上的优势避免了由于每
5、个目标的取值范围不同或者费用的整体趋势不同而造成的某些个体在某些目标的优势无法被体现 牛牛文库文档分享遗传算法多目标最小生成树编码理论估价函数遗传算子PARENT 12565交配遗传错位交叉算子从当前群体中抽出两条染色体,在两条染色体上随机抽取一个等位的长度不超过的片段进行交换,并择择优选取。PARENT 28577 22 8优势由于编码理论的性质,这种操作很大程度地保留了亲本优良特性,并且能一定程度上引入另一个样本一些特性。变异遗传从当前群体中抽出一条染色体(Parent),在染色体上随机抽取一个位置,用一个随机的值替换。单点变异算子优势由于编码理论的性质,这种操作也可以在较大程度上保留亲本
6、的优良性质。概率控制保持遗传(54)交配遗传(45)变异遗传( 1) 牛牛文库文档分享遗传算法多目标最小生成树编码理论估价函数遗传算子 牛牛文库文档分享遗传算法多目标最小生成树算例分析 牛牛文库文档分享遗传算法多目标最小生成树算例分析 牛牛文库文档分享遗传算法多目标最小生成树算例分析 牛牛文库文档分享小结编码理论估价函数遗传算子通过测试结果我们可以看到遗传算法在解决组合优化类问题有着和其他算法无法比拟的强大优势,它的特点就是可以在较短的时间内,得到令人满意的解,而且算法相对简洁。对于现实生活中的大量常规算法无法解决的问题,遗传算法都有着良好的应用前景。谢谢! 遗传算法不仅一种算法,更是一种思想。在各种常用算法中
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 基础知识2025年高中化学模拟试题及答案
- 2025年联盟山东省菏泽一中学业水平考试语文试题模拟卷(九)含解析
- 把握脉络的保安证试题及答案
- 福建省福州市长乐高中、城关中学2024-2025学年高三第一次质量调研(一模)数学试题含解析
- 高效备考2025保安证试题及答案
- 针对性保安证考试试题及答案解析
- 2025年保安证考试现场技能试题及答案
- 烟台城市科技职业学院《品牌策划与管理》2023-2024学年第二学期期末试卷
- 2025年保安证考纲解读试题及答案
- 吉林省“五地六校”2025届高三第二次适应性训练物理试题含解析
- 2024年职业技能“大数据考试”专业技术人员继续教育考试题库与答案
- 国家高新技术企业评定打分表
- 人工智能实验学校实施方案
- SYT 6680-2021 石油天然气钻采设备 钻机和修井机出厂验收规范-PDF解密
- 华为供应链管理岗位笔试题目含笔试技巧
- 任务4 聚酯缩聚生产操作-生产操作规程
- 铁路少年-练习及答案
- 2024高考物理复习备考策略
- 锦江国际酒店的员工手册
- 邻里市集活动策划方案
- 公司清洁生产的审核报告书
评论
0/150
提交评论