论文研究-求解图同构的判定算法.pdf

所需积分/C币:17 2019-09-11 23:40:01 518KB .PDF
53
收藏 收藏
举报

应用回溯法求解规模较大的N皇后问题时,时间开销巨大。从提出布尔遗传算子角度,增强遗传算法局部搜索性能,与具有良好全局搜索性能的矩阵遗传算子组合应用,对N皇后问题求解。采用自然数和二进制互换的编码方式,应用N皇后的约束条件构造适应度函数,保证了算法的全局收敛性。通过与回溯法和相关遗传算法比较,实验证实了该方法应用于求解N皇后问题,具有良好的搜索效率和求解质量。
帅训波,马书南:应用布尔遗传算子求解N皇后问题 2011,47(16)5 适应度函数构造满足皇后间不在同一斜线上的约束条件。仟的编码长度缩短为NgA,而布尔遗传算子中的异或运算由 意给定所提的自然数编码的染色体两个基因a和a,表示在与其相邻基因求和取模等运算来替代,也可以根据基因特征 第i行的a列、第j行的a列分别放置皇后。适应度函数设构造该编码下的“异或”操作,保证操作运算后对被操作的基 计如下 因达到变异效果。 0.i-j1≠2{a1-a 4实验结果与分析 令 41遗传参数控制 对于终止代数的选取控制进行了实验。算法应用Java语 min 1= (2) i-0j-i+I 言编程实现,采用CPU为双Itel内核2.0GHz,内存1GB的 因此,所有满足f=0取得最小值的合法自然数染色体为PC机上进行实验操作,操作系统是 Windows Xp,选取8、10 N皇后问题的解。式(2)所构造的适应度函数比文献[的适1520、30个皇后构成5组测试用例种群规模M-40,对每组 应度函数简沽、高效,避免了皇后间冲突的重复计算 实验分别遗传100代、200代、500代、800代、1000代、1500代 33优化组合遗传算法及收敛性 的搜索到的最优解个数进行统计。为了兼顾算法效率,其中, 基丁布尔与矩阵两种新型遗传算子优化组合的N皇后问皇后数为8和10的两组实验采用二进制编码,后三组采用八 题求解算法(BMGA)描述如下: 进制编码,布尔运算采用相邻基因求和取模,求取随机抽取各 步骤1满足N皇后问题行列约束条件,生成自然数编码自 自20次的结果平均值结果如表2所示。 的初始种群,并初始化最优解集S=φ。 表2对N皇后问题搜索不同代数的结果统计 步骤2对种群中每个自然数编码染色体转换为二进制编 N1004200代50080010001415001 码串。 5.751320244531.00 6.20 38.70 步骤3排序选取等于染色体二进制编码长度的数个染色 105.207.309.2513.7518.40 152.50 4.007. 16.00 1850 体,应用矩阵遗传算子,进行全局搜索 0.050.651253.45 步骤4对矩阵遺传算子搜索得到的n个新染色体,启用 30 0 0 0.45 1.75 4.50 布尔遗传算子,进行局部搜索,并计算新种群各个染色体的适 应度,对于任意满足f(P)=0的解,且pgS,则S=SU{P}。 表2统计结果表明,在给定种群规模的情况下,算法收敛 步骤5判断是否满足算法结束条件,如果满足,则输出最 所需遗传代数随皇后个数增多而呈非线性增长,兼顾搜索效 终解S,否则转向步骤3 率,当皇后数目较大时,采用κ进制编码是有效的,算法具有 步骤6输出最终求解结果。 良好的扩展性。 对本文求解算法的全局收敛性进行证明分析 4.2对比实验及结果分析 引理1如果变异概率pn∈(0,1),交叉概率P∈(0,1), 本文算法与回溯法和文献[10的遺传算法比较。在4.1节 同时采用排序选择和局部搜索策略,遗传算法最终收敛到全的实验环境下,将其对各个皇后问题搜索到的第一个有效解 局最优解 所需时间进行对比,随机抽取各自20次实验结果,求取平均 定理2设皇后问题规模N,当种群规模大丁2N「bM时 值,如表3所示。 BMGA算法以概率1收敛至全局最优解。 表3搜索时间对比 证眀由文献[9]的矩阵遗传算子性能分析,矩阵遺传算子 皇后数 8 10 等效于n个染色体的“矩阵”方式杂交;根据2.2节的布尔遗传 回溯法s0.0940.529514062 算子分析,BMG∧算法过程中的布尔遗传算子,等效于对矩 文献[0算法/s0.1070492207341637.510 本文算法/s0.7461.1753.03144746.366 阵遗传算子搜索过程中的2n个染色体进行“布尔遗传”方式 变异。设皇后问题规模为N,那么染色体的二进制编码长度为 对于回溯法求解皇后数大于20和文献[1]算法求解皇后 NbN,如果种群规模大于2NlbM时,使得“矩阵遗传”式数30的问题,时间开销太大,因此,本文对其没有给出具体时 杂交概率P∈(0,),且“布尔遗传”式变异概率Pn∈(,1),又间数字统计。对于皇后数不大于10的情况,由于本文算法中 因为算法采用选择排序策略,故由引理1可知,BMGA算法以组合遗传算子运算消耗,搜索至第·个有效解的效率略低于 概率1收敛到全局最优解。 回溯法和文献[的算法,但当皇后数较大时,本文算法搜索 选用遗传操作一定的代数作为算法终止策略,在4.1节对到解的效率远远高于其他两种算法,这是因为布尔遗传算子 遗传代数与皇后个数间的关系进行实验,为算法在应用过程的局部搜索能较快地“发现”有效解。 中,根据N取值而选取合适的终止代数提供参考。 34算法扩展 5结论 当皇后数N较大时,如果仍然采用将自然数编码转换为 在遗传算子局部搜索策略研究基础之上,提出布尔新型 二进制编码,再应用布尔遗传运算,这样难免会造成二进制染遗传算子,将其与具有良好全局搜索性能的矩阵遗传算子组 色体编码较长,二进制表示解的空间搜索开销稍大,由此,对合应用,用于对N皇后问题求解。设计了自然数与二进制相 算法应用进行了扩展,使其具有更广的适用对象。将自然数互转换的编码方式,构造了以N皇后的约束条件为基础的适 编码可以转换为四进制、八进制等其他K进制形式编码,相应 (卜转68页)

...展开详情
试读 3P 论文研究-求解图同构的判定算法.pdf
立即下载
限时抽奖 低至0.43元/次
身份认证后 购VIP低至7折
一个资源只可评论一次,评论内容不能少于5个字
您会向同学/朋友/同事推荐我们的CSDN下载吗?
谢谢参与!您的真实评价是我们改进的动力~
  • 至尊王者

关注 私信
上传资源赚钱or赚积分
最新推荐
论文研究-求解图同构的判定算法.pdf 17积分/C币 立即下载
1/3
论文研究-求解图同构的判定算法.pdf第1页

试读结束, 可继续阅读

17积分/C币 立即下载