第3章 进化计算

《第3章 进化计算》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第2章进化计算与群智能1进化算法概述2遗传算法3粒子群算法4蚁群算法1进化算法概述为什么？进化算法框架基本步骤特点应用为什么？进化算法框架基本步骤（1）进化计算是基于自然选择和自然遗传等生物进化机制的一种搜索算法。与普通的搜索方法一样，进化计算也是一种迭代算法，不同的是进化计算在最优解的搜索过程中，一般是从原问题的一组解出发改进到另一组较好的解，再从这组改进的解出发进一步改进。而且在进化问题中，要求当原问题的优化模型建立后，还必须对原问题的解进行编码。进化计算在搜索过程中利用结构化和随机性的信息，使最满足目标的决策获得最大的生存可能，是一种概率型的算法

2、。一般来说，进化计算的求解包括以下几个步骤：给定一组初始解；评价当前这组解的性能；从当前这组解中选择一定数量的解作为迭代后的解的基础；再对其进行操作，得到迭代后的解；若这些解满足要求则停止，否则将这些迭代得到的解作为当前解重新操作。以遗传算法为例，其工作步骤可概括为：基本步骤（2）（1）对工作对象——字符串用二进制的0/1字符编码。（2）根据字符串的长度L，随即产生L个0/1字符组成初始个体。（3）计算适应度。适应度是衡量个体优劣的标志，通常是所研究问题的目标函数。（4）通过复制，将优良个体插入下一代新群体中，体现“优胜劣汰”的原则。（5）交换字符，产

3、生新个体。交换点的位置是随机决定的（6）对某个字符进行补运算，将字符1变为0，或将0变为1，这是产生新个体的另一种方法，突变字符的位置也是随机决定的。（7）遗传算法是一个反复迭代的过程，每次迭代期间，要执行适应度计算、复制、交换、突变等操作，直至满足终止条件。基本步骤（3）－伪代码将其用形式化语言表达，则为：假设α∈I记为个体，I记为个体空间。适应度函数记为Φ：I→R。在第t代，群体P(t)={a1(t),a2(t)，…，an(t)}经过复制r(reproduction)、交换c(crossover)及突变m(mutation)转换成下一代群体。这里r

4、、c、m均指宏算子，把旧群体变换为新群体。L：I→{True,Flase}记为终止准则。利用上述符号，遗传算法可描述为：t=0initializeP(0):={a1(0),a2(0)，…，an(0)};while(l(P(t))≠True)doevaluateP(t):{Φ(a1(t)),Φ(a2(t))，…，Φ(an(t))};reproduction:P′(t):=r(P(t));crossover:P″(t):=c(P′(t));mutation:P(t+1):=m(P″(t));t=t+1;end[2]特点进化计算是一种具有鲁棒性的方法，能适应

5、不同的环境不同的问题，而且在大多数情况下都能得到比较满意的有效解。对问题的整个参数空间给出一种编码方案，而不是直接对问题的具体参数进行处理不是从某个单一的初始点开始搜索，而是从一组初始点搜索。搜索中用到的是目标函数值的信息，可以不必用到目标函数的导数信息或与具体问题有关的特殊知识。因而进化算法具有广泛的应用性，高度的非线性，易修改性和可并行性。应用传统最优化进化计算、进化编程、进化学习优化神经网络图像处理、仪器参数优化、工程设计，搜索，规划，等应用举例卫星通信星座优化设计VMCK（甚小线性调频键控）调制波形优化基于匹配追踪法的导波检测信号处理信号盲源分

6、离卫星通信星座优化设计星座由一群卫星组成。理论上，卫星可以位于任何轨道上。卫星星座设计具有多种优化的目标，例如覆盖率最大化。优化的参数包括有：长半轴、轨道倾角、偏心率、星座轨道面个数、近地点幅角、各轨道面的卫星数，等。VMCK（甚小线性调频键控）调制波形优化根据VMCK波形及功率谱估计发现，其调制因子与解调性能具有一定的关联度。例如当其等于0.4时，频谱能量更集中一些，且边带抑制性更好。通过选择合适的调制因子，可以在信号解调性能和频带利用率间进行很好的平衡。基于匹配追踪法的导波检测信号处理匹配追踪法的主要思想是信号的稀疏分解。其是一个迭代过程，，每次匹

7、配时从过完备原子库D中选择一个最佳的匹配原子，然后从信号中减去该匹配原子在信号中的占有成分得到剩余量。对剩余量重复进行此过程，直到满足要求时停止。由于原子库的原子数量较大,若采用遍历搜索的方式,其运算速度不能满足应用要求信号盲源分离独立分量分析(ICA)是解决盲信号分离的主要方法之一。其基本目标是设置一分离矩阵W,使得观测信号X(t)经分离矩阵W输出列向量Y(t)=[y1(t),y2(t),⋯,yM(t),]变换后的Yi(t)尽可能的统计独立.2遗传算法主要发展历史生物学的基本概念和术语基本思想特点应用基本流程有效性适应度及调整有关的几个问题模式定理改

8、进理论研究应用举例2.1主要发展历史20世纪50年代和60年代，“人工进化系统”研究20世纪6