《混合差分进化与调度算法》是2012年清华大学出版社出版的图书。作者是王凌、钱斌。
书名 | 混合差分进化与调度算法 | 作者 | 王凌、钱斌 |
---|---|---|---|
ISBN | 9787302283676 | 页数 | 254 |
定价 | 34.50元 | 出版社 | 清华大学出版社 |
出版时间 | 2012-9 |
《混合差分进化与调度算法》为大家全面介绍了差分进化(DE),差分进化(DE)是当今诸多领域热点研究的智能优化算法。《混合差分进化与调度算法》主要面向自动化、管理科学与工程、计算机科学与技术、机械工程、工业工程等学科的大专院校、研究所和企业的教师、学生、研究与技术开发人员。
第1章 差分进化算法
1.1 引言
1.2 标准差分进化算法
1.2.1 变异操作
1.2.2 交叉操作
1.2.3 选择操作
1.2.4 标准DE算法流程及其特点
1.3 DE的算法研究及改进
1.3.1 改进DE操作
1.3.2 加入新操作
1.3.3 多种群
1.3.4 混合算法
1.3.5 其他
1.4 复杂环境下的DE研究
1.4.1 多目标优化
1.4.2 约束优化
1.4.3 离散优化
1.4.4 不确定动态优化
1.5 DE的应用研究
1.6 差分进化研究展望
参考文献
第2章 差分进化参数分析
2.1 引言
2.2 基于随机模型的DE参数分析
2.2.1 简化假设
2.2.2 变异操作及其参数
2.2.3 选择操作
2.2.4 交叉操作及其参数
2.2.5 其他方面
2.2.6 小结
2.3 数值仿真与分析
2.3.1 单调函数
2.3.2 凸函数
2.3.3 多极小函数
参考文献
第3章 基于和声搜索的混合DE算法
3.1 和声搜索算法
3.2 和声差分进化算法
3.3 基于典型函数的测试分析
3.3.1 数值仿真结果
3.3.2 参数性能分析
3.4 基于HSDE的电力负载分配
3.4.1 电力负载分配问题描述
3.4.2 基于SQP的HSDE算法
3.4.3 数值仿真与比较
3.5 基于协进化HSDE的可靠性优化
3.5.1 可靠性优化问题描述
3.5.2 协进化HSDE算法
3.5.3 仿真实验与比较
参考文献
第4章 基于量子计算的混合DE算法
4.1 量子差分进化算法
4.1.1 量子进化算法
4.1.2 混合算法
4.2 基于HQEDE的混沌系统参数估计
4.2.1 问题描述
4.2.2 数值仿真与算法比较
4.2.3 算法参数的影响
参考文献
第5章 基于单纯形搜索的混合DE算法
5.1 单纯形算法
5.2 NMDE混合算法
5.2.1 算法混合机制
5.2.2 混合算法
5.3 基于标准函数的性能测试
5.3.1 测试问题与算法参数
5.3.2 算法性能测试与比较
5.3.3 种群规模的影响
5.4 基于NMDE的混沌系统参数估计
5.4.1 Lorenz系统参数估计
5.4.2 Chen系统与Lü系统参数估计
5.4.3 时延系统参数估计
5.5 基于NMDE的资源受限项目调度研究
5.5.1 问题描述
5.5.2 算法设计
5.5.3 算法性能测试
参考文献
第6章 基于协进化的DE算法
6.1 约束优化问题描述
6.2 智能约束处理技术概述
6.2.1 无约束化处理
6.2.2 基于排序的方法
6.2.3 基于多目标优化的方法
6.2.4 特殊编码和操作
6.2.5 拓扑映射法
6.2.6 基于文化算法的技术
6.2.7 修补技术
6.2.8 混合策略
6.3 协进化DE算法
6.3.1 协进化机制
6.3.2 罚函数设计
6.3.3 罚因子种群的评价
6.3.4 协进化算法框架
6.4 数值仿真与算法比较
6.4.1 函数优化的测试与比较
6.4.2 伸缩杆设计问题的测试与比较
6.4.3 焊接条设计问题的测试与比较
6.4.4 压力容器设计问题的测试与比较
6.5 种群规模的影响
参考文献
第7章 基于水平比较的DE算法
7.1 约束满足度和水平比较
7.2 DELC算法
7.3 基于DELC的约束函数优化
7.3.1 算法参数设置
7.3.2 仿真结果与算法比较
7.3.3 参数影响的讨论
7.4 基于DELC的机械设计优化
7.4.1 焊接杆设计
7.4.2 弹簧设计
7.4.3 减速器设计
7.4.4 三杆珩架设计
7.4.5 压力容器设计
7.5 基于DELC的鲁棒控制器设计
7.5.1 固定结构鲁棒控制器设计问题
7.5.2 数值仿真与算法比较
7.5.3 进一步分析和讨论
参考文献
第8章 基于混合DE的置换流水线调度
8.1 引言
8.2 置换流水线调度问题描述
8.3 多目标优化问题描述
8.4 置换流水线调度算法概述
8.5 单目标置换流水线调度的混合DE算法
8.5.1 解的表达及LOV规则
8.5.2 差分进化搜索
8.5.3 基于问题的局部搜索
8.5.4 混合差分进化算法
8.5.5 HDE收敛性分析
8.6 多目标置换流水线调度的混合DE算法
8.6.1 多目标处理技术
8.6.2 多目标混合差分进化算法
8.6.3 MHDE收敛性分析
8.7 单目标问题的仿真实验与算法比较
8.7.1 实验设置
8.7.2 LOV规则讨论
8.7.3 HDE NOL和ODE、PGA、NEH的比较
8.7.4 HDE和HDE_ML、HDE_NOL的比较
8.7.5 HDE和HDE_BL的比较
8.7.6 HDE和OSA、HGA的比较
8.8 多目标问题的仿真实验与算法比较
8.8.1 实验设置
8.8.2 评价指标
8.8.3 MHDE和IMMOGLS2的比较
8.8.4 交叉概率的影响
参考文献
……
第9章 基于混合DE的有限缓冲区调度
第10章 基于混合DE的零等待流水线调度
第11章 基于混合差分进化的作业车间调度
第12章 基于混合差分进化的动态调度
参考文献
《混合差分进化与调度算法》主要阐述差分进化算法的原理、基本框架和研究进展,分析算法参数设置的影响,并重点阐述多种混合差分进化算法的设计与应用,包括基于和声搜索的混合DE算法及其在函数优化、电力负载分配和可靠性冗余优化方面的应用等。
针对梯级水电站优化调度的复杂问题,结合差分进化算法和混合蛙跳算法各自优势,提出一种新的混合差分进化算法。该算法将差分进化策略嵌入到混合蛙跳算法框架中,对整个群体循环进行分组进化与混合操作,而在每个分组内部按照差分进化策略对个体不断进行更新。数值实验表明该算法具有较强的全局搜索能力,克服了基本差分进化算法易早熟收敛的缺点。将该算法应用于梯级水电站中长期优化调度实例,并与传统动态规划法进行比较分析,进一步验证了其可行性与有效性。
以差分进化算法(DE)为基本框架,结合混沌算法(CA)和蛙跳算法(SLFA)各自局部搜索优势以及多核并行计算技术(PC),提出一种新的并行混合差分进化算法(PHDE),即将DE与CA、SLFA进行有机融合,分别对精英个体进行混沌局部搜索和对较差个体进行蛙跳局部更新,且差分进化运算、混沌局部搜索和蛙跳局部更新均采用PC,以有效缩短计算时间。PHDE具有三点优势:一是保留了DE简单易行、收敛迅速的特点;二是继承了CA、SLFA的遍历性,能够避免早熟收敛现象;三是通过合理的并行模式,有效降低了计算时间。典型测试函数表明了PHDE的可行性、高效性和鲁棒性。实例研究表明,PHDE具有较好的优化性能和计算效率,为高效求解水库群优化调度问题提供了一种可行途径。
计算机系统是由许多程序或进程需要使用的资源(例如处理机周期、存储单元和输入/输出设备)的 有限集合所组成的。调度算法的目标是把这些资源分配给要求它们的程序。 在每一判定时刻,调度算法 必须决定下一次应是若干相竞争的进程中的哪一个进程接收一给定资源。因而调度算法是指:根据系统的资源分配策略所规定的资源分配算法。对于不同的系统和系统目标,通常采用不同的调度算法,例如,在批处理系统中,为了照顾为数众多的短作业,应采用短作业优先的调度算法;又如在分时系统中,为了保证系统具有合理的响应时间,应采用轮转法进行调度。目前存在的多种调度算法中,有的算法适用于作业调度,有的算法适用于进程调度;但也有些调度算法既可用于作业调度,也可用于进程调度。2100433B
表调度算法的基本思想是通过对节点的优先级别进行排序来构造一个调度列表。
然后重复以下两个步骤直到任务图中所有节点被调度完毕:①从调度列表中顺序取出一个节点;②将节点分配到使它的启动时间最早的处理机器上。
这是传统的静态表调度算法,一些新的表调度算法是基于动态列表的调度算法,与静态方法调度列表一经构造就不会改变不同,动态列表算法在每次分配节点之后都重新计算所有未被调度节点的优先级别,并根据新的优先级别来重新安排列表中节点的顺序。
这样,动态表调度算法实际分为三步:①确定所有未被调度节点的新优先级别;②选择具有最高优先级别的节点进行调度;③将节点分配到使它的启动时间最早的处理机上。
决定节点优先级别的方法很多,有HLF(Highest LevelFirst)、LP(Longest Path)、LPT(Longest Processing Time)、CP(Critical Path)等。
2100433B
通常系统的设计目标不同,所采用的调度算法也不同。在操作系统中存在多种调度算法,其中有的调度算法适用于作业调度,有的调度算法适用于进程调度,有的调度算法两者都适用。下面介绍几种常用的调度算法:
FIFS先来先服务调度算法
特点:算法简单,但是效率低;有利于长作业,不利于短作业;有利于CPU繁忙型作业而不利于IO繁忙型作业。
SJF短作业优先调度算法
短作业(进程)优先调度算法是指对短作业祸端进程优先调度的算法。短作业优先调度算法是从后备队列中选择一个或若干个估计运算时间最短的作业,将他们呢掉入内存运行。
SJF调度算法的缺点:
1) 该算法对长作业不理。
2) 该算法完全未考虑作业的紧迫程度
3) 由于作业的长短只根据用户所提供的估计执行时间而定的,而用户又可能会有意或无意的缩短其作业的估计运行时间,致使该算法不一定能真正做到算作业优先调度。
4) 注意:SJF调度算法的平均等待时间、平均周转时间最少。
高响应比优先调度算法
高响应比优先调度算法主要用于作业调度。同时考虑从每个作业的等待时间和估计需要运行的时间。
时间片轮转调度算法
时间片轮转调度算法主要适用于分时系统。
多级反馈队列调度算法
多级反馈队列调度算法主要是时间片轮转调度算法和优先级调度算法的综合和发展。通过动态调整进程优先级和时间片大小,多级反馈队列调度算法可以兼顾多方面的系统目标。