智能控制_04遗传算法3

《智能控制_04遗传算法3》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、智能控制系统天津大学电气与自动化工程学院四天津大学自动化学院3.遗传算法的理论基础2.3隐含并行性（内在并行性）隐含并行性（ImplicitParallelism）是模式理论的另一个重要内容。这一机理说明，在遗传算法中尽管每一代只处理n个个体，但实际上却是处理了n3以上的模式。[隐含并行性定理]设(0,1)是一个很小的数，模式存活的长度,若群体规模为，则GA在一次迭代中所处理的“存活率”大于(1-)的模式数约为O(n3)。天津大学自动化学院3.遗传算法的理论基础[公式推导]以二进制编码为例。在长度为l，规模为n的群体中，

2、包含了2l~n·2l个不同的模式，随着进化过程的进行，这些模式中一些定义长度较长的模式被破坏掉，而另一些定义长度较短的模式却能够生存下来。模式存活的最大长度模式在交叉和变异时可能遭破坏。•由于变异概率很小，在此只考虑交叉的破坏，模式被天津大学自动化学院3.遗传算法的理论基础破坏的概率为：•为保证模式的存活率,令pd<（为死亡率），即：•根据模式定义长度的定义，模式的长度是：•带入上式得：天津大学自动化学院3.遗传算法的理论基础计算长度为l的位串中长度的模式数目[示例]1011100010位串的长度l＝10，Ⅰ.将它放置在个

3、体字符串的最左侧，则有：1011100010写成模式的形式，上述字符串变为：%%%%%*****%可为原位的数值（0或1）或不固定值(*)中任选一个。这时，可以组成的模式个数是：Ⅱ.将上述方框右移一位1011100010天津大学自动化学院3.遗传算法的理论基础写成模式的形式，上述字符串变为：*%%%%%****可以组成的模式个数仍是：Ⅲ.上述方框可发生在6个不同的位置，即发生次数为则该个体共包括模式数为其中重复的近一半。天津大学自动化学院3.遗传算法的理论基础群体中的模式数目若种群数量为n,则该种群中包含模式的上限为当种群数目

4、n较大时，则对一些低阶的模式肯定会有一些重复。为排除这些重复部分，取群体的规模数为我们仅计确定位数大于的模式。由于遗传操作都是利用均匀随机数，模式数目服从二项分布，即模式中阶次高于和小于数目相等。于是，计算时模式数天津大学自动化学院3.遗传算法的理论基础应取上式的1/2，则总模式数的下限值为带入则有[结论]遗传算法所处理的有效模式总数约与群体规模n的立方成正比。天津大学自动化学院4.遗传算法的实现2.4遗传算法实现中的一些问题目标函数到适配值的映射如前所述，要求所有个体的适配值必须为正数或零，不能是负数。适配值必须对应函数优化

5、的方向(1)当优化目标是求函数最大值，并且目标函数总取正值时，可以直接设定适配值函数就等于目标函数，即：f(x)＝g(x)(2)对于求目标函数最小值的优化问题，并且目标函数总取负值时，理论上只需简单地对其增加一个负号就可将其转化为求目标函数最大值的优化问题，即：f(x)＝-g(x)天津大学自动化学院4.遗传算法的实现基本遗传算法一般采用下面两种方法之一将目标函数值g(x)变换为个体的适配值f(x)：方法一：对于求目标函数最大值的优化问题，变换方法为：其中，cmin为一个适当地相对比较小的数，它可用下面方法之一来选取：•预先指定

6、的一个较小的数。•进化到当前代为止的最小目标函数值。•当前代或最近几代群体中的最小目标函数值。f(x)=g(x)-cminifg(x)-cmin>00ifg(x)-cmin≤0天津大学自动化学院4.遗传算法的实现方法二：对于求目标函数最小值的优化问题，变换方法为：其中，cmax是一个适当地相对比较大的数，它可用下面几种方法求得：•预先指定的一个较大的数。•进化到当前代为止的最大目标函数值。•当前代或最近几代群体中的最大目标函数值。f(x)=cmax-g(x)ifg(x)cmax0ifg(x)cmax天津大学自动化学院4.遗

7、传算法的实现编码原则二进制编码优点：提供的参数信息量大，优化效果好；二进制编码能够取得最大的模式数。假设二进制编码长度为l,则采用k进制编码长度为l’则有例如l=6时，若k=4，则l’=3此时，二进制编码模式数为3^6=729个四进制码模式数为5^3=125个天津大学自动化学院4.遗传算法的实现编码与解码编码假设某一参数的取值范围是[umin,umax]，我们用长度为l的二进制编码符号串来表示该参数，则它总共能够产生2l种不同的编码，参数编码时的对应关系如下：00000000…00000000＝0umin00000000…00

8、000001＝1umin+00000000…00000010＝2umin+2……11111111…11111111=2l–1umax天津大学自动化学院4.遗传算法的实现其中，为二进制编码的编码精度，其公式为：解码假设某一个体的编码是：x：blbl-1bl-2……b2b1