·168 智能系统学报 第3卷 假设2：晶体形成过程中，晶界微偏聚动力和晶 1.2冰晶效应 间脆性断裂等现象不会对晶格点阵的整体布局产生 1.2.1冰晶形成 蝴蝶效应，忽略该算法在最坏情况下获得可行解的 冰晶是自然界很平常的物理现象.液体凝固包 难度 括晶核的形成和长大，晶核的形成是液体中的一些 假设3：固相的冰晶内不存在扩散现象，忽略凝 原子的动能减少到足以使这些原子固定于晶格点阵 固界面曲率等因素对凝固前沿的影响，以此来简化 上时发生的晶体成核现象，如水结冰 冰晶生长所谓的能量函数， 原子的大小、形态及相邻原子间键合的性质，会 TSP问题与冰晶现象的相似性分析，如表1， 导致一种最低能量的单晶组态，决定了原子在晶体 值得一提的是其中冰晶生长的过程就是TSP路径 中规则的周期性排列，温度和压力的不同，会有不同 形成的过程 的晶体结构1湖面结冰则是以湖畔为依托冰晶不 断的向湖中心生长，直到湖面冰封的过程 表1特征相似性分析 1.2.2树枝晶体 Table I Similarity analysis of the characteristics 湖岸的表面一般都有凹凸部分，水会均匀地浸 序号 冰晶算法 TSP(计算几何) 透湖岸，并吸附着空气和湿气，导致晶胚的活性较 CFI 湖面 地图（凸壳域） CF2 湖畔 国界（凸壳边界） 大，与水全接触的湖畔的晶核，可以优先生长。 CF3 晶胞 城市（点集） CF4 冰晶生长 路径形成 CF5 临界冰渣 诱导走向歧途的城市 CF6 微风吹拂湖面 局部约束扰动 1.1形成湖畔 1.1.1凸壳定义 平面(E)中点集S的凸壳是包含S的最小 图2树枝晶的生长 凸集，凸壳是S计算几何中最普遍、最基本的一种 Fig,2 Growth of the dendrite 结构，它不仅有许多自身的特征，还是构造其他几何 形体的有效工具.本文采用Gramham扫描算法，如 凝固初期，晶粒在生长过程中与相邻晶粒接触 果点集有n个点，时空开销主要涉及角度排序，需要 形成凝固壳，先沿着湖岸横向生长，形成树枝晶的树 O(Hog列时间) 干和分支，竞争过程中优先生长的分支在横向又生 1.1.2围建湖岸 出子分支形成树枝晶，如图2所示，其阴影部分表示 令V=(,2,,ym)代表由v个晶核组成 己结冰区域， 的一个矢量，存储凸壳的顶点并以此为基础形成湖 计算机模拟晶体生长，本文采用距离函数代替 岸，为湖水中晶胞提供一个结冰的容器 能量函数，控制晶体生长的过程，令Ew(p)为第1 凸壳的抽象形态如图1，其中每一个圆点表示 特征点对应凝固前沿的每条边是否结冰的判定依 一个城市，黑色的圆点表示湖畔的晶核，白色的圆点 据，点x、y代表该边的2个端点.E(p)=Da+ 表示湖面游离的晶胞，外围样条虚线表示的人工围 Do Dsy-A(dn da),pr min{Ex (p)(i=1. 建的湖岸，直线段虚线表示点集的凸壳边界 2,k,…2.其中：D表示点x和点y的距离： d和dm分别表示i点与其最近点、次近点的距离：A =0,1),取0为绝对代价，取1为相对代价；pk表 示获得能量最小值的ⅰ点，该点可以凝固结冰；k是 一个待定值，指需要计算的每个城市最邻近城市的 0 数目，均匀分布的TSP问题取30~60就可以，不均 匀的分布适当取大一点，要保证在k邻图中不会出 现孤立的岛.E,(p)控制树枝晶的生长并进行过程 图1湖畔模型结构 扫描，所得记录即所求TSP可行解，晶胞全部结冰 Fig 1 Structure of the lakefront model 后，图2所示湖中心未结冰区域的边界就是所求 TSP问题的可行解路径 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net假设 2 :晶体形成过程中 ,晶界微偏聚动力和晶 间脆性断裂等现象不会对晶格点阵的整体布局产生 蝴蝶效应 ,忽略该算法在最坏情况下获得可行解的 难度. 假设 3 :固相的冰晶内不存在扩散现象 ,忽略凝 固界面曲率等因素对凝固前沿的影响 ,以此来简化 冰晶生长所谓的能量函数. TS P 问题与冰晶现象的相似性分析 ,如表 1 , 值得一提的是其中冰晶生长的过程就是 TS P 路径 形成的过程. 表 1 特征相似性分析 Table 1 Similarity analysis of the characteristics 序号 冰晶算法 TSP(计算几何) CF1 湖面 地图(凸壳域) CF2 湖畔 国界(凸壳边界) CF3 晶胞 城市(点集) CF4 冰晶生长 路径形成 CF5 临界冰渣 诱导走向歧途的城市 CF6 微风吹拂湖面 局部约束扰动 111 形成湖畔 11111 凸壳定义 平面( E 2 ) 中点集 S 的凸壳[4 ] 是包含 S 的最小 凸集 ,凸壳是 S 计算几何中最普遍、最基本的一种 结构 ,它不仅有许多自身的特征 ,还是构造其他几何 形体的有效工具. 本文采用 Gramham 扫描算法 ,如 果点集有 n 个点 ,时空开销主要涉及角度排序 ,需要 O( nlog n) 时间[5 ] . 11112 围建湖岸 令 V = ( v1 , v2 , v3 , …, vm ) 代表由 v 个晶核组成 的一个矢量 ,存储凸壳的顶点并以此为基础形成湖 岸 ,为湖水中晶胞提供一个结冰的容器. 凸壳的抽象形态如图 1 ,其中每一个圆点表示 一个城市 ,黑色的圆点表示湖畔的晶核 ,白色的圆点 表示湖面游离的晶胞 ,外围样条虚线表示的人工围 建的湖岸 ,直线段虚线表示点集的凸壳边界. 图 1 湖畔模型结构 Fig11 Structure of the lakefront model 112 冰晶效应 11211 冰晶形成 冰晶是自然界很平常的物理现象. 液体凝固包 括晶核的形成和长大 ,晶核的形成是液体中的一些 原子的动能减少到足以使这些原子固定于晶格点阵 上时发生的晶体成核现象 ,如水结冰. 原子的大小、形态及相邻原子间键合的性质 ,会 导致一种最低能量的单晶组态 ,决定了原子在晶体 中规则的周期性排列 ,温度和压力的不同 ,会有不同 的晶体结构[6 ] . 湖面结冰则是以湖畔为依托冰晶不 断的向湖中心生长 ,直到湖面冰封的过程. 11212 树枝晶体 湖岸的表面一般都有凹凸部分 ,水会均匀地浸 透湖岸 ,并吸附着空气和湿气 ,导致晶胚的活性较 大 ,与水全接触的湖畔的晶核 ,可以优先生长. 图 2 树枝晶的生长 Fig12 Growth of the dendrite 凝固初期 ,晶粒在生长过程中与相邻晶粒接触 形成凝固壳 ,先沿着湖岸横向生长 ,形成树枝晶的树 干和分支 ,竞争过程中优先生长的分支在横向又生 出子分支形成树枝晶 ,如图 2 所示 ,其阴影部分表示 已结冰区域. 计算机模拟晶体生长 ,本文采用距离函数代替 能量函数 ,控制晶体生长的过程 ,令 Exy ( pi) 为第 i 特征点对应凝固前沿的每条边是否结冰的判定依 据 ,点 x、y 代表该边的 2 个端点. Exy ( pi) = Dix + Diy - Dxy - λ( df i + dsi ) , pk = min{ Exy ( pi) } ( i = 1 , 2 , …, k , …,2 k) . 其中 : Dxy 表示点 x 和点 y 的距离; df i和 dsi分别表示 i 点与其最近点、次近点的距离;λ = { 0 , 1} ,取 0 为绝对代价 ,取 1 为相对代价; pk 表 示获得能量最小值的 i 点 ,该点可以凝固结冰; k 是 一个待定值 ,指需要计算的每个城市最邻近城市的 数目 ,均匀分布的 TSP 问题取 30～60 就可以 ,不均 匀的分布适当取大一点 ,要保证在 k 邻图中不会出 现孤立的岛. Exy ( pi) 控制树枝晶的生长并进行过程 扫描 ,所得记录即所求 TSP 可行解 ,晶胞全部结冰 后 ,图 2 所示湖中心未结冰区域的边界就是所求 TSP 问题的可行解路径. ·168 · 智 能 系 统 学 报 第 3 卷