启发式优化算法介绍概要.ppt

* 局部 最优解 全局 最优解 运动向量 速度向量 Study Factor Here I am! The best position of team My best position x(t) pg pi v PBest gBest x(t+1) 速度与位置更新 * 5. 粒子群优化算法 （1）将群族做初始化，以随机的方式求出每一Particle 之初始位置与速度。 （2）依据fitness function计算出其fitness value以作为判断每一个Particle之好坏。 （3）找出每一个Particle 到目前为止的搜寻过程中最佳解，这个最佳解称之为Pbest。 （4）找出所有群体中的最佳解，此最佳解称之为Gbest。 （5）根据速度与位置公式更新每一Particle的速度与位置。 （6）返回步骤2继续执行，直到获得一个令人满意的结果或符合终止条件为止。 * 6. 遗传算法 进化过程 优化过程 生物进化过程是一个自然，并行，稳健的优化过程，这一优化过程的目的在于使生命体达到适应环境的最佳结构与效果，而生物种群通过 “优胜劣汰”及遗传变异来达到进化（优化）目的的。 * 6. 遗传算法 遗传算法(Genetic Algorithm)是由美国的J.Holland教授于1975年在他的专著《Adaptation in Natural and Artificial Systems》中首先提出的。 基本遗传算法的构成要素 （1）染色体的编码（产生初始群体） （2）适应度函数 （3）遗传算子（选择、交叉、变异) （4）运行参数 * 6. 遗传算法 生物的进化机制 自然选择 适应环境的个体具有更高的生存能力，同时染色体特征被保留下来。 杂交 随机组合来自父代的染色体上的遗传物质，产生不同于它们父代的染色体。 突变 随机改变父代的染色体基因结构，产生新染色体。 * 6. 遗传算法 几个术语 基因型： 1000101110110101000111 表现型：0.637197 编码 解码 个体（染色体） 基因 * 6. 遗传算法 交叉前： 00000|01110000000010000 11100|00000111111000101 交叉后： 00000|00000111111000101 11100|01110000000010000 交叉点 * 6. 遗传算法 变异前： 000001110000000010000 变异后： 000001110001000010000 变异点 * 6. 遗传算法 产生初始群体 基本位变异 新一代群体 最佳个体 计算个体适应度 是否满足停止准则 比例选择 单点交叉 SGA流程图 N Y * 7. 非支配排序遗传算法 快速非支配遗传算法（NSGA-II）具有计算复杂度低、全局有哪些信誉好的足球投注网站能力强等优点，已经成为多目标进化算法的基准算法之一，并成功应用于求解各种复杂的工程优化问题。 * 数学模型 n个决策变量，r个目标函数(相互冲突) 其中 为决策变量 寻求 ,使 满足约束的同时达到最优。 * 概念 Pareto最优解 支配关系 Pareto最优解 对于一些解，不可能进一步优化某一个或某几个目标而其他目标不至于劣化，因此也称非劣最优解。 数学描述 给定一个多目标优化问题min f(X),设X*∈Ω，若不存在X∈Ω使其满足f(X)≤f(X*)，则称X*∈Ω为Pareto最优解。 * 概念 Pareto最优解 支配关系 支配关系 设p和q是进化群体pop中任意两个不同的个体， 称p支配q ，当满足下面两个条件： ①对所有的子目标， p不比q差 即fk(p)≤ fk(q),(k=1,2,…,r) ②至少存在一个子目标，使p比q好 即存在l∈{k=1,2,…,r}，使fl(p) fl(q) 这时， p称非支配的， q称被支配的 * 概念 Pareto最优解 支配关系 . . . . . . . . . . . A B F C D E K J G I H * 7. 非支配排序遗传算法 产生初始群体P 快速非支配排序 虚拟适应度计算 锦标赛选择 交叉和变异 得到子种群Q R=P∪Q 计算各目标函数值 计算各目标函数值 快速非支配排序 选前N个个体 作为父代个体P 达到最 大代数? 结束 开始 代 数 加 1 精英策略 否 是 NSGAⅡ流程图 * 7. 非支配排序遗传算法 产生初始群体P 快速非支配排序 虚