正在加载图片...
·680 智能系统学报 第12卷 2P-GA算法 为了使每个基本膜的内部区域都有对应的多 重集,利用NSGA-Ⅱ的非支配排序机制对表层膜区 P系统由字符对象多重集、反应规则和膜结构 域中的所有字符对象进行排序,排序标准参照2)完 三部分组成[)。在P系统中,字符对象与多重集分 成适应值大小,排序结束以后再将其按照等数量划 别对应所求多目标优化问题的解和解集,且每一个 分为多个子字符多重集。具体划分的形式化表述 字符对象都会通过适应度函数得到一个适应度值: 如式(7)所示: 反应规则既是算法具体的执行,也有对细胞膜的操 20=sort(0) 作,比如分裂、溶解等:膜结构的运用使算法具有了 ={01,102,…,0m} (7) 分布式和并行计算的能力[1]。在每一次的迭代,将 n sizeof(w)/m 随机产生的字符对象放入表层膜区域中,利用表层 式中:w表示字符多重集;sort(w)表示对表层膜区 膜区域中的反应规则和通信规则进行操作:最后通 域中的多重集进行非支配排序:心:表示第i个子字 过膜的溶解将多重集释放到表层膜区域中交流信 符多重集:sizeof(w)表示多重集中字符对象个数;m 息。为了降低仿真实验难度,所提算法采用的细胞 表示基本膜的个数:n表示每个基本膜取得字符对 型膜结构只有表层膜与基本膜,这种二层结构相较 象个数,具体放入规则对n进行取模。 于原结构复杂度较低。 4)对前m个基本膜用GA算法中的交叉规则进 为了使算法得出的多重集有较好的多样性,故 行多线程并行计算,以获得新的字符对象,而并行 引入NSGA-Ⅱ算法,利用其非支配排序和拥挤距离 计算可以极大地加快求解速度,具体交叉操作为 两种机制来获得。 遗传算法(genetic algorithm,GA)是模拟达尔文 S+=a·S+(1-a)·S (8) 进化论(适者生存、优胜劣汰遗传机制),借鉴生物 S,=a·S+(1-a)·S 界的进化规律演化而来的随机化搜索方法。该方 式中:S表示字符对象S第t代的值:S?表示字符 法具有并行性和更好的全局寻优能力[5-16)。 对象S2第t代的值;S+,表示字符对像S第t+1代 P-GA算法基于膜计算理论,包含了遗传机制, 的值;S?,表示字符对象S2第t+1代的值;a表示 利用NSGA-Ⅱ算法的非支配排序和拥挤距离两种机 交叉系数,经过多次实验测试,当选取a=0.5~0.7 制来设计算法,详细步骤如下。 时能获得最好的结果,故本文提出P-GA算法采用 1)根据优化问题的约束条件,在表层膜的区域 这一数值。 内随机生成N个字符对象(N≥i≥1),所有字符对 5)利用通信规则将前m个基本膜中产生的交 象均为十进制编码,具体形式为 叉结果复制一份发送到第+1个基本膜中,对第 sd=(s-miad)×rand()+smrJ(5) m+1个基本膜中的多重集进行变异操作。由于自 式中::,表示第i个字符对象的第j维:广的范围为 然进化中种群变异率往往比较低,因此在一次迭代 D≥j≥1,D表示维数;Sm表示第j维的最小值, 中,只有利用足够多的字符对象进行变异操作才能 sa表示第j维的最大值;rand()为随机数函数,产 产生更多的新个体,具体变异操作如式(9)所示: 生从0~1的随机数。 Su+i)=S)+0.1×(S(a)-S(mim)×rand() 2)根据所要优化问题的目标函数计算出每个 (9) 字符对象的适应度值,从而完成对所有字符对象的 式中:SD表示字符对象S的第t代j维的值; 评价。 S(m)表示第j维的最小值;Sm表示第j维的最 3)在初始化完成以后,利用表层膜的分裂规 大值;rand()为随机数函数,产生从0~1的随 则,在表层膜内部区域分裂出m+1个基本膜,且分 机数。 裂出的基本膜具有求解多目标优化问题的能力。 6)当每个基本膜中的规则和操作都结束以 首先,将初始化完成的m个多重集复制一份发送到 后,调用基本膜区域内的溶解规则,当m+1个基本 第m+1个基本膜的区域中:然后,将m个多重集发 膜全部溶解后,表层膜区域中就会有来自于不同 送到前m个基本膜的区域中,逐一对应。具体表层 基本膜中的字符对象;本文引入外部档案集,将从 膜分裂规则如式(6): 基本膜中溶解出的字符对象插入到外部档案集 []。→[[]1,[]2,…,[]m,[]m](6) 中,而后将表层膜区域中的字符对象与归入外部 式中:[]。表示表层膜,[]:表示第i个基本膜。 档案的字符对象进行非支配排序操作。外部档案2 P⁃GA 算法 P 系统由字符对象多重集、反应规则和膜结构 三部分组成[13] 。 在 P 系统中,字符对象与多重集分 别对应所求多目标优化问题的解和解集,且每一个 字符对象都会通过适应度函数得到一个适应度值; 反应规则既是算法具体的执行,也有对细胞膜的操 作,比如分裂、溶解等;膜结构的运用使算法具有了 分布式和并行计算的能力[14] 。 在每一次的迭代,将 随机产生的字符对象放入表层膜区域中,利用表层 膜区域中的反应规则和通信规则进行操作;最后通 过膜的溶解将多重集释放到表层膜区域中交流信 息。 为了降低仿真实验难度,所提算法采用的细胞 型膜结构只有表层膜与基本膜,这种二层结构相较 于原结构复杂度较低。 为了使算法得出的多重集有较好的多样性,故 引入 NSGA⁃Ⅱ算法,利用其非支配排序和拥挤距离 两种机制来获得。 遗传算法(genetic algorithm,GA)是模拟达尔文 进化论(适者生存、优胜劣汰遗传机制),借鉴生物 界的进化规律演化而来的随机化搜索方法。 该方 法具有并行性和更好的全局寻优能力[15-16] 。 P⁃GA 算法基于膜计算理论,包含了遗传机制, 利用 NSGA⁃Ⅱ算法的非支配排序和拥挤距离两种机 制来设计算法,详细步骤如下。 1)根据优化问题的约束条件,在表层膜的区域 内随机生成 N 个字符对象(N≥i≥1),所有字符对 象均为十进制编码,具体形式为 si,j = (smax,j - smin,j) × rand() + smax,j (5) 式中:si,j表示第 i 个字符对象的第 j 维; j 的范围为 D≥j≥1,D 表示维数; smin,j 表示第 j 维的最小值, smax,j 表示第 j 维的最大值; rand() 为随机数函数,产 生从 0~1 的随机数。 2)根据所要优化问题的目标函数计算出每个 字符对象的适应度值,从而完成对所有字符对象的 评价。 3)在初始化完成以后,利用表层膜的分裂规 则,在表层膜内部区域分裂出 m+1 个基本膜,且分 裂出的基本膜具有求解多目标优化问题的能力。 首先,将初始化完成的 m 个多重集复制一份发送到 第 m+1 个基本膜的区域中;然后,将 m 个多重集发 送到前 m 个基本膜的区域中,逐一对应。 具体表层 膜分裂规则如式(6): [ ] 0 → [ ] 1, [ ] 2,…, [ ] m, [ ] [ m+1 ] (6) 式中: [ ] 0 表示表层膜, [ ] i 表示第 i 个基本膜。 为了使每个基本膜的内部区域都有对应的多 重集,利用 NSGA⁃Ⅱ的非支配排序机制对表层膜区 域中的所有字符对象进行排序,排序标准参照 2)完 成适应值大小,排序结束以后再将其按照等数量划 分为多个子字符多重集。 具体划分的形式化表述 如式(7)所示: w · = sort(w) w · = w1 ,w2 ,…,wm { } n = sizeof(w) / m ì î í ï ï ï ï (7) 式中: w 表示字符多重集; sort(w) 表示对表层膜区 域中的多重集进行非支配排序; wi 表示第 i 个子字 符多重集;sizeof(w)表示多重集中字符对象个数; m 表示基本膜的个数; n 表示每个基本膜取得字符对 象个数,具体放入规则对 n 进行取模。 4)对前 m 个基本膜用 GA 算法中的交叉规则进 行多线程并行计算,以获得新的字符对象,而并行 计算可以极大地加快求解速度,具体交叉操作为 S 1 t+1 = α·S 1 t + (1 - α)·S 2 t S 2 t+1 = α·S 2 t + (1 - α)·S 1 t { (8) 式中: S 1 t 表示字符对象 S 1 第 t 代的值; S 2 t 表示字符 对象 S 2 第 t 代的值; S 1 t+1 表示字符对像 S 1 第 t + 1 代 的值; S 2 t+1 表示字符对象 S 2 第 t + 1 代的值; α 表示 交叉系数,经过多次实验测试,当选取 α = 0.5 ~ 0.7 时能获得最好的结果,故本文提出 P⁃GA 算法采用 这一数值。 5)利用通信规则将前 m 个基本膜中产生的交 叉结果复制一份发送到第 m+1 个基本膜中,对第 m+1 个基本膜中的多重集进行变异操作。 由于自 然进化中种群变异率往往比较低,因此在一次迭代 中,只有利用足够多的字符对象进行变异操作才能 产生更多的新个体,具体变异操作如式(9)所示: S(t+1,j) = S(t,j) + 0.1 × (S(max,j) - S(min,j) ) × rand( ) (9) 式中: S(t,j) 表示字符对象 S 的第 t 代 j 维的值; S(min,j) 表示第 j 维的最小值; S(max,j) 表示第 j 维的最 大值; rand( ) 为随机数函数,产生从 0 ~ 1 的随 机数。 6)当每个基本膜中的规则和操作都结束以 后,调用基本膜区域内的溶解规则,当 m+1 个基本 膜全部溶解后,表层膜区域中就会有来自于不同 基本膜中的字符对象;本文引入外部档案集,将从 基本膜中溶解出的字符对象插入到外部档案集 中,而后将表层膜区域中的字符对象与归入外部 档案的字符对象进行非支配排序操作。 外部档案 ·680· 智 能 系 统 学 报 第 12 卷
<<向上翻页向下翻页>>
©2008-现在 cucdc.com 高等教育资讯网 版权所有