(m，3)-非均匀分裂系的若干结果

论文摘要

设m和t为整数，且有0<t≤m，X为一个有限点集，且满足|X|=m，X的子集称作区组，B由若干个区组构成，对于每个Y X且|Y|=t，都存在一个区组B B使得|B∩Y|=t/2，则称二元组(X,B)是一个(m,t)分裂系。若一个(m,t)分裂系满足每一个区组都含有相同的元素个数m/2，则称之为均匀分裂系。通用启发式算法(metaheuristic)是一个迭代生成的过程，它通过对低层的启发式方法进行智能引导，来开拓搜索空间，并且采用一定的人工智能来构造从而有效地找到附近的最优解。常见的启发式算法有基本局部搜索算法、禁忌搜索算法(TS)、模拟退火算法（SA）。模拟退火算法(SA)被公认为是最早的通用启发式算法(metaheuristic)，当然也是第一个具有避免局部最优性能的算法。其基本思想是得到一个比当前解更差的解，从而跳出局部最优。同时进行这样一种操作的概率在搜索过程中越变越小。在本文中我们将分裂系的构造问题转化为一个组合优化问题，主要研究了t=3的非均匀分裂系，并采用模拟退火算法来进行分裂系的搜索，最终得到了较好的搜索结果。

论文目录

• 摘要
• ABSTRACT
• 目录
• 主要符号对照表
• 第一章 绪论
• 1.1 分裂系的概念
• 1.2 分裂系的性质
• 1.3 分裂系的应用
• 第二章 Metaheuristic算法简介
• 2.1 Metaheuristic算法的基本定义
• 2.2 Metaheuristic的几种常见轨迹方法
• 2.2.1 基本局部搜索
• 2.2.2 禁忌搜索算法
• 2.2.3 贪婪随机自适应搜索
• 2.3 模拟退火算法
• 2.3.1 固体退火过程
• 2.3.2 Metropolis准则
• 2.3.3 模拟退火算法主要思想
• 2.3.4 模拟退火算法基本实现
• 第三章 分裂系的构造
• 3.1 目标函数
• 3.2 初始关联矩阵的生成
• 3.3 取反方法
• 3.4 算法步骤
• 第四章 算法实验及结果分析
• 4.1 基本局部搜索与SA算法的实验比较
• 4.2 计算结果
• 第五章 结论和展望
• 附录 A 分裂系搜索结果
• 参考文献
• 致谢
• 附件