• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Mathematical Problems in Engineering >A Simulated Annealing Algorithm to Construct Covering Perfect Hash Families
【24h】

A Simulated Annealing Algorithm to Construct Covering Perfect Hash Families

机译：模拟退火算法构造覆盖完美哈希家庭

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Covering perfect hash families (CPHFs) are combinatorial designs that represent certain covering arrays in a compact way. In previous works, CPHFs have been constructed using backtracking, tabu search, and greedy algorithms. Backtracking is convenient for small CPHFs, greedy algorithms are appropriate for large CPHFs, and metaheuristic algorithms provide a balance between execution time and quality of solution for small and medium-size CPHFs. This work explores the construction of CPHFs by means of a simulated annealing algorithm. The neighborhood function of this algorithm is composed of three perturbation operators which together provide exploration and exploitation capabilities to the algorithm. As main computational results we have the generation of 64 CPHFs whose derived covering arrays improve the best-known ones. In addition, we use the simulated annealing algorithm to construct quasi-CPHFs from which quasi covering arrays are derived that are then completed and postoptimized; in this case the number of new covering arrays is 183. Together, the 247 new covering arrays improved the upper bound of 683 covering array numbers.
机译：覆盖完美哈希家族（CPHF）是组合设计，以紧凑的方式表示某些覆盖数组。在以前的工作中，CPHF是使用回溯，禁忌搜索和贪婪算法构建的。回溯对于小型CPHF方便，贪婪算法适用于大型CPHF，元启发式算法在中小型CPHF的执行时间与解决方案质量之间提供了平衡。这项工作通过模拟退火算法探索了CPHF的构建。该算法的邻域函数由三个扰动算子组成，它们一起为算法提供了探索和开发的能力。作为主要的计算结果，我们生成了64个CPHF，其派生的覆盖阵列改进了最著名的CPHF。另外，我们使用模拟退火算法构造准CPHF，从中推导出准覆盖阵列，然后对其进行完善和后优化。在这种情况下，新的覆盖阵列的数量为183。这247个新的覆盖阵列共同改善了683个覆盖阵列编号的上限。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号