遗传算法多样度的改进.doc

《遗传算法多样度的改进.doc》由会员分享，可在线阅读，更多相关《遗传算法多样度的改进.doc（9页珍藏版）》请在三一文库上搜索。

1、精品论文大全遗传算法多样度的改进孙旭东 辽宁工程技术大学理学院应用数学系 辽宁省阜新市 (12300) E-mail：摘要：本文简要介绍了遗传算法的基础理论，并通过改进多样度定义的公式解决现有定义存在的缺陷。最后经过实例的计算悚证了改进的多样度定义在解决问题时是有效的，使多样度 度量群体的多样性更符合要求。关键字：遗传算法 ，多样度，自适应调节，哈夫曼编码。1 引言遗传算法1是模仿生物遗传与进化过程而得出的一种随机优化方法，由于它不依赖问题 的具体领域，不受搜索空间的限制性假设的约束，也不必要求诸如连续性、可微性和单峰值 等假设，甚至不要求一定具有目标函数的解析表达式，因此，遗传算法应用的领域

2、十分广泛。 本文通过介绍遗传算法并分析存在的一些的问题，并对多样度提出了三种新的定义。2 遗传算法的简介2.1 遗传算法的主要步骤步骤 1) 对研究的变量编码形成字符串,并随机建立一个初始群体。 步骤 2) 群体中诸个体适应度进行计算。步骤 3) 产生新个体过程，通过三种方式：复制：选择适应度高个体进行复制后添入到新群体中，删除适应度低的个体；交换：随机选出个体对，进行片段交叉换位，产生新个体对；突变：随机地改变没个体的某个字符，得到新个体。步骤 4) 根据各种条件判断计算过程是否可以结束,如果不满足结束条件，则回到第 2 步， 直到满足条件为止。2.2 遗传算法的编码编码是遗传算法的中首先要

3、解决的问题。个体用字符串表示成染色体，它是遗传信息遗 传的载体，串上的每个位置上的元素代表遗传因子。在遗传算法的实际应用中，根据所研究 的不同性质，可以用不同的方式表示：通常遗传因子用 0/1 码表示，也可以采用实数直接编 码和 k 个符号编码（k 为大于 2 的整数）。从大量的研究结果，一般情况下建议采用二进制 编码。下面针对二进制编码常出现的问题给出一种改进的二进制编码方法： 假设单变量 x xmin , xmax ，给定每相临的两个单变量精度 x = a 。 传统的编码方法：1） 确定字符串的长度 L，满足下式：- 9 -2 L 1 xmax xmina 2 L（1）minmax2） 在

4、 x, x 上插入 2 L 个点，它们分别如下：Lxmin , xmin + a, xmin + 2a,L, xmin + (2 1)a, xmax这 2 L 个点分别用 L 位二进制数表示，这可以实现二进制编码如下：xmin xmin + a Mxmax00L0000L01M*14*L243*L位图 1 传统的二进制编码从中我可看到 xmax 不一定可以得到 L 位二进制最大值，因此这样的编码使遗传算 法的可行区域变大；同样如果将 L 变小，使得遗传算法的可行区域变小，很有可能漏 掉最优值点。下面给出改进的编码方法：1） 确定字符串的长度 L，满足：xmax xminn2 a xmax xm

5、inn1L 1（2）其中 n1n2= 2 + 21 + 2 2 + L + 2 L 1 = 2 kk =0L= 2 + 21 + 2 2 + L + 2 L = 2 kk =0（3）（4）minmax2） 然后在 x, x 上等距地插入 2 L 个点，它们分别如下：xmin , xmin +xmax xminn1, xmin + 2xmax xminn1L,L, xmin + (21)xmax xminn1, xmax （5）这 2 L 个点分别用 L 位二进制数表示，这可以实现二进制编码如下：xmin xmin + a Mxmax00L0000L01M1112L311L位图 2 改进的二进制

6、编码改进的二进制编码方法是通过提高精度实现了二进制编码后的单变量取值范围和十进x x制取值范围的统一。注：编码的精度变为 maxminn1 a 。2.3 遗传算法的遗传算子遗传算法中最主要的三个算子是复制、交换和突变。（一）复制 复制是预测算法的基本算子，对当前的群体实施复制操作的意图是使适应度高的优良个体尽可能地在下一代新群体中得以繁殖，体现“适者生存”的自然原则，同时还要使新一代 群体中的个体数量与原有群体相同。复制是通过随机选择对象方法实现的，现在主要方法有轮盘选择法；贪婪选择法；极差选择法；小数选择法。（二）交换 交换算子每次作用在随机选择的两个个体上，通过相互交换产生两个新的子代个体

7、。群体中执行交换的个体数目与群体中个体总数之比称为交换概率，记为 Pc ，一般交换概率取0.5 至 0.8。交换还要确定字符串中交换点的位置，交换点的选择也是随机的，交换方式分为 单点方式、两点方式和多点方式等。（三）变异变异是对个体中某一位字符进行运算，一种是补算法，即把 1 变 0，或把 0 变 1，进而 产生一个新的个体。首先要确定一个突变概率，记为 Pm ，一般突变概率取 0.001 至 0.01。 执行突变的方式主要常用的方法有字符决定法和个体决定法等。2.4 遗传算法的自适应调节遗传算法的自适应调节2 是通过调节遗传算法中的控制参数来抑制早熟收敛现象和加 快收敛速度。所谓早熟，是指

8、过早的收敛到局部最优解，产生局部收敛的一个主要原因是群 体多样性过早地减少使得遗传算法的搜索空间受到限制，而多样性的减少与控制参数的选择 有着极大的关系。因此，通过自适应调节，关键是通过不断的调整参数保证群体多样性来避 免早熟收敛现象。3 关于遗传算法多样度的问题3.1 遗传算法的多样度提出的意义从 2.4 的介绍我们可以看到群体中个体多样性的减少，会使遗传算法过早的产生了局部 收敛，而遗传算法的自适应调节需要一个对群体多样性的进行度量的参数，进而来调节控制 参数。为此定义了多样度来对遗传操作过程中的每一代群体个体多样性的进行度量。因此， 一个适当的多样度来度量群体多样性对遗传算法自适应调节是

9、十分重要的。3.2 现有的遗传算法的多样度和存在缺陷321 现有的多样度定义设 X 是规模为 n 的一代群体，其个体分别记为 A1，A2，An，个体的字符长都为 L，十进制个体 x 的范围为a b.其中 Ai = ai1 , ai 2 ,LaiL , aij 0,1, i = 1,2,Ln; j = 1,2,L, L.群体 X 可用矩阵表示：a11X = a21a12a22La1L aL2 L （6） MMM an1an 2LanL 用 D j 表示矩阵 X 第 j 列元素和的函数，即nnD = 0若 a kj0或 akj = n（7）j1k =1k =1其它j=1,2,L.也就是说，若 X

10、的第 j 列元素完全相同，则 D j有人定义：= 0 ；否则 D j= 1 .L群体 X 的多样度 ： D( X ) = D jj =1（8）群体 X 的成熟度：M ( X ) = L D( X )（9）从定义我们可以知道多样度和成熟度是一对相对应的度量参数，多样度越大则成熟度越 小，多样度越小则成熟度越大。因此本文只考虑多样度的定义，成熟度的定义不予讨论。下面是已有改进的遗传算法的多样度的定义 n设 X = (a1 , a2 ,L, aL ), 其中ai = aik , i = 1,2,L, L 为群体平均值。k =1nL 定义多样度 ： D1( X ) = ( aik ak )i =1k

11、=1（10）322 现有的多样度定义存在缺陷利用 2.2 中的编码方法对单变量 x xmin , xmax 进行二进制编码，设确定的字符串的xmax xmin长度为 L，则在 x xmin , xmax 中插入相临两点的相差距离为n1，记为 d，得到个体的二进制编码： x hL hL1 L h2 h1 , 其中h k = 0或1，(k1，2，L L) 。k假设两个个体的二进制编码中 hk 不同，则它们的在十进制的差别为 2 d ，可以看到k 的不同的取值在十进制中的差别是不同的，k 值大时，十进制差别很大；而 k 值较小时，十进制差别很小。因此利用现有的多样度的定义方法只是对二进制 hk ,

12、(k = 1,2,L L) 差别 的度量，不能体现在十进制下的差别，不能很好地实现多样性度量的作用。3.3 提出改进的多样度的定义331 基于整体距离度量的多样度定义 给出个体间距离矩阵： s11S = s21s12s22Ls1n sL2 n （11） MMM sn1sn 2Lsnn 其中：sijL= S ( Ai , A j ) = (wk aik a jk ) 且 sijk =1= s ji ，sii= 0, i = 1,2,L, n .（12）wk (k = 1,2,L, L) 是根据个体 Ai 中当 k 取不同的值时 aik 对十进制影响不同适当给定 的，并规定：0 wk +1 wkL

13、 1, wi = 1, k = 1,2,L, Li =1（13）给出新的多样度n1n sD 2 ( X ) = (ij )（14）i =1j =i n 1 i332 基于十进制转换的多样度定义假设范围为a b的群体中有 n 个个体,且 m 个不同的个体,它们分别为:ai1 , ai 2 ,L aiL , aij 0,1, i = 1,2,Lm; j = 1,2,L, L.给出新的多样度m 1 mkD 3 ( X ) = n 1 s（15）其中：i j =iLS k = k =1aik a jkL 1 2 k 1 (b a) / 2ii =0（16）n 1 = ( n t ) t (b a )（

14、17）t (n 1)333 基于哈夫曼编码的多样度定义由于每个个体都是 L 位的二进制编码，所以它是等长编码，可采用哈夫曼二叉树编码3。1） 生成二叉树将群体数 n 个个体的编码作为 n 个叶子结点，生成一个二叉树，让该二叉树中每个 分支结点左、右分支分别用 0 和 1 编码，从树根结点到每个叶子结点的路径上所经分支的 0、1 编码数列应等于该叶子结点的二进制编码，则对应的编码生成二叉树。实例如下：表 1 群体数据个体二进制编码对应十进制A11000117A21000117A31110129A4000113A5000102将表 1 的群体生成二叉树见如图 3：2） 给出多样度定义图 3 生成的

15、二叉树Z4D ( X ) = wi ji（18）其中：wii =1为第 i 层结点数的权重，是根据 322 提出的二进制编码对应十进制的差别给定 wi , (i = 1,2,L, Z ) 的值，规定:Z0 wi +1 wi 1, w1 = 0, wi = 1, i = 2,3,L L. ；（19）i =1ji :为第 i 层的结点数；z : 为二叉树的深度或高度。334 性质（一）设群体规模为 n，则式（14）定义的多样度满足：0 D2 ( X ) n 1（20）证明: 当 A1 = A2 = L An 时,容易得到 D2 ( X ) = 0 ,下面证明多样度 D2 ( X ) n 1 .假

16、设 A1 ， A2 ， ， An 不 完 全 相 同 , 根 据 定 义 (11) 可 以 到 0 sij 1 , 因 此 对 于nskjn 1 ns kjk , max() 1, k = 1,2,L n ，所以可以得到D 2 ( X ) = () 最j =k n 1 ki =1j = k n 1 k大可能 值 为 n-1, 但是由于不 能同 时使得 所有 的 sijD2 ( X ) n 1 .证毕。= 1, i = 1,2,L n, j = 1,2,L n ，因此（二）设群体规模为 n，则式（15）定义的多样度满足：0 D3 ( X ) n证明: 当 A1 = A2 = L An 时,容易得

17、到 D3 ( X ) = 0 ,下面证明多样度 D3 ( X ) n .（21）假设 A1，A2，An 不完全相同,根据定义(14),可以将 A1，A2，An 不同个体间 的差别用 S k 以十进制表示，而我们知道要想群体的多样度最大，各个个体应该均匀分布，(b a)m1 m3即以方差为组成的数列，此时 sk= ,因此得到 D ( X ) = n .证毕.(n 1)i j =i（三）设群体规模为 n，则式（18）定义的多样度满足：1 D4 ( X ) n证明: 当 A1 = A2 = L An 时,容易得到 D4 ( X ) = 1 ,下面证明多样度 D4 ( X ) n .（22）假设 A1

18、，A2，An 不完全相同,根据定义 3.3.3,我们可以知道只有生产的二叉树中每 一层中的节点数目达到相应的最大值时才能使得 D4 ( X ) 取得最大值。不妨设一群体数目为n，实数范围为a,b并根据 2.2 中编码方法确定其二进制树长度为 L，利用哈夫曼二叉树编 码，则其最大多样度的群体中要使得每层都有最大节点，一定存在一个 k，满足： 2 k L2 k 1 L，（23）即得到每层结点最大数目为：20 ,21 ,2 k 1 , n, n ，（24）L1L23L k +1个nk 1Lm根 据 定 义 得 到 多 样 度 D 4 = 2 m wm=1L+ n wt , 即 群 体 范 围 为 a

19、,b 的 最 大 多 样 度t =k44max D ( X ) = D 。又因为 0 wi 1, wii =1= 1, i = 1,2,L, L ，又 2 m n, m = 1,2,L k 1k 1m显然 D 4 n wm=1L+ n wtt =kL= n wmm=1= n 1 = n .证毕.3.4 实例应用设单变元的取值范围为0 31的整数，并根据 2.2 中编码方法对它们进行二进制编码。 现给给定两个群体 X1 和 X2，分别为：15 16 17 18 19 和1 8 13 17 28，显然 X1 的 群体的多样性不好，X2 的群体的多样性很好。下面用 5 种定义分别计算，结果如下表：表

20、 2 典型群体数据及计算结果X1X2X1 的多样度计算结果X2 的多样度计算结果0111100001D ( X 1)4000D ( X 2 )40001000001000D 1 ( X 1)3600D 1 ( X 2 )24001000101101D 2 ( X 1)1350D 2 ( X 2 )34701001010001D 3 ( X 1)0645D 3 ( X 2 )41931001111100D 4 ( X 1)2225D 4 ( X 2 )3525说明：计算多样度 D 2 ( X 1) 取的权重为(0.400 0.250 0.200 0.100 0.050);计算多样度 D 4 (

21、X 1) 取的权重为(0 0.400 0.275 0.200 0.100 0.005)。从表 2 的计算结果中我们看到改进的定义比原有的定义效果好，而计算 D 2 ( X 1) 和D 4 ( X 1) 时其权重可以根据实际问题的精度适当给定进而得到更理想的结果；D 3 ( X 1) 的计算可以简化为直接在十进制下运算； D 4 ( X 1)算。的计算复杂度较小，可以简化遗传算法的运4 结语本文分析和解决了多样度存在的缺陷，并提出了 3 种新的多样度定义，为调整遗传算法 自适应算法的快速收敛和防止“早熟”问题提出了有效的解决方法，特别是利用哈夫曼二叉 树编码方法进行多样度定义，还可以大大简化算法

22、的计算的复杂度。5 致谢感谢郭嗣琮教授的指导和鼓励！参考文献1 郭嗣琮,陈刚.信息科学中的软计算方法.M.沈阳:东北大学出版社.2001.2 易伟民,申群泰.整流机组效率优化中的遗传算法的研究与应.J.贵州工业大学报.2003(3). 3 徐孝凯.数据结构.M.北京:清华大学出版社.2004.The improvement of genetic algorithmXuDong SUNDepartment of Information and Compute Science , Liaoning technical university,Fuxin,123000Abstract:This pap

23、er introduces the theory of genetic algorithms and genetic algorithms diversity of the adaptive significanceand the improvement of the formula for solving the existing definition of diversity definition of the defect.Finally Examples show that the improvement in the definition of diversity is effective in solving problems, diversity is more in line with the actual requirements.Key words: genetic algorithms, diversity, adaptive regulator, Huffman coding.