3维场景映射真实世界的场景，但3维设计人员普遍不具备严格的建筑学背景及空间组织能力，设计的游戏场景作品往往画面美观，但场景设计违背基本的场景空间组织原则，其原因在于3维场景设计师普遍缺乏建筑场景组织的知识背景及经验，而建筑规划及相关领域从业者较少涉及具体的3维建模工作。提出一种多重方法协同操作的交互式遗传算法，以用户偏好驱动场景扩展，实现3维场景扩展的灵活性和用户友好性。理论上来说，该方法可以应用于建筑设计、游戏设计及3维仿真等学科交叉领域，使不同专业背景的创作人员进行知识融合。

Wertheimer于1923年提出著名的Law of Good Gestalt理论，即对某不规则结构进行最大程度地简化、规则化及序列化以便于抽离出其规则化元素。该理论中所提及的完形原则及对称最大化理论逐渐被计算机视觉研究者所重视，对于3维场景立面及平面分析的研究逐渐形成体系。建筑场景立面的分析可以追溯到对称化图形分析领域，Aliaga^[1]认为可通过图形对称性分析从而得出不规则结构中所存在的某种规律，即可用艺术创作领域的“风格化”来解释。对称性量化分析理论已经有很多研究者进行探索，如Hao等人^[2]就如何对近似对称图形的特征进行量化分析提出自己的观点，并研究不规则对象中隐含的对称性特征。3维模型对称性特征的提取也日益成为研究热点，Blokelon等人^[3]通过参数化编辑的方式进行3维对称性分析；Hochstein^[4]提出自顶至底层次化分解的方法提取3维对称性特征。很多新的方法也应用于复杂3维对象的特征提取，如Ankerst等人^[5]将3维模型采样为点云进行特征提取；Kazhdan等人^[6]采用3维模型反射和旋转对称的球函数集合来描述3维特征，并提出基于3维实体3个主方向上的轮廓特征分别提取轮廓特征。Hochstein^[7]认为在场景分层处理过程中，建筑常呈群落状态，需要将子结构中的最基础元素进行特征提取，逐步分解至再无法进行对称性分析最小单元。在借鉴上述研究者方法的基础上，本文采用包围盒法，将现有场景进行分层及割裂处理，同时使用改进的蚁群算法实现场景的优化布局，作为多方法协同操作的前期处理方法。

场景的扩充和优化使用改进的遗传算法来实现。传统遗传算法适用于显式函数表示的优化问题，但是很多美学和艺术设计领域的性能优化指标往往属于隐式性能指标的优化，难以用明确的函数来表示。1986年Dawkins^[8]提出交互式遗传算法 (IGA) 思想；1991年Sims^[9]在计算机图像中使用交互式计算方法并取得一定成果；Takagi等人^[10]研究交互式遗传算法理论并将其应用于语音识别、艺术设计及虚拟现实等领域。交互式遗传算法IGA在传统遗传算法基础上引入人的主观评价并将其作为进化个体适应值的优化方法，该算法建立在将变量空间映射在心理空间的方法之上，可以通过设计师评估从而得到最优解。但普遍效率低下，从而引起用户的严重疲劳感，易受环境影响，具有不稳定性。提出一种多重方法协同操作的交互式遗传算法 (CIGA)，以解决传统IGA方法的缺陷。

有很多研究者采用神经网络的方法来对3维组群对象进行特征聚类，例如Moon等人使用前馈神经网络 (feed-forward neural network) 来进行训练从而学习3维零件实体特征以组成零件组；Smith等人采用ART (adaptive resonance theory) 网络来研究零件族群的成组规律；Onwubolu等人提出使用BPN网络来进行实体模型特征识别；Sunil等人使用ANN网络来对CAD模型进行特征识别。本文则提出采用自适应共振网络的方法来实现3维场景建筑特征的聚类。

3维模型的预处理是首要进行的工作，PCA方法忽视3维面片的面积差异性，会导致细节层次的网格产生不同的主轴，于是采用连续PCA方法^[7](CPCA) 参数化三角形网格，$c$是三角网格质心，$o$为网格任一点，($m, n$) 为质心坐标，${w_i}$为网格面片面积，${A_i}$、${B_i}$、${C_i}$为三角网格3个顶点，$S$是模型表面积，$C$是协方差矩阵，CPCA算法的公式为

$ \begin{array}{*{20}{c}} {\boldsymbol{o} = {{\left[{{o_x}, {o_y}, {o_z}} \right]}^{\rm{T}}} = }\\ {m \cdot {A_i} + n \cdot {B_i} + \left( {1 -m -n} \right) \cdot {C_i}} \end{array} $

(1)

$ m=\text{ }\frac{1}{S}\iint{\boldsymbol{o}~\text{d}S}=\frac{1}{S}\sum\limits_{i=1}^{N}{{{S}_{i}}}\cdot \frac{({{A}_{i}}+{{B}_{i}}+{{C}_{i}})\text{ }}{3} $

(2)

$ \begin{matrix} f\left( \boldsymbol{o} \right)=\left( \boldsymbol{o}-c \right){{\left( \boldsymbol{o}-c \right)}^{\text{T}}} \\ C=\frac{1}{S}\iint{\left( \boldsymbol{o}-c \right){{\left( \boldsymbol{o}-c \right)}^{\text{T}}}\text{d}S}= \\ \frac{1}{12S}\sum\limits_{i=1}^{N}{{{S}_{i}}}\cdot \text{ }[f({{A}_{i}})+f({{B}_{i}})\text{ }+f({{C}_{i}})+ \\ 9f(\text{ }\frac{{{A}_{i}}+{{B}_{i}}+{{C}_{i}}}{~3}\text{ })] \\ \end{matrix} $

(3)

对3维模型进行采样，${N_s}$为采样率，则采样点 (${\theta _i}$，${\phi _j}$) 采样公式为

$ \left\{ \begin{array}{l} {\theta _i} = \frac{{\left( {2i + 1} \right){\rm{\pi }}}}{{2{N_s}}}\\ {\phi _j} = \frac{{2{\rm{\pi }}\left( {2j + 1} \right)}}{{2{N_s}}} \end{array} \right. $

(4)

采样点与质心构成向量记为${\boldsymbol{u}_{ij}}$，其坐标为 (sin ${\theta _i}$ cos ${\phi _j}$，sin ${\theta _i}$ sin ${\phi _j}$，cos ${\theta _i}$)。易求得所有向量射线交于模型的交点与质心距离的最远值${\bar v_{\max }}$，求其与模型表面点最远距离并进行归一化处理，由采样值可构成球函数$D\left( {\theta, \phi } \right)$。

Liu等人^[11]对3维特征的提取通过对3维模型进行球面调和变换，得到不同频率的能量，使用有限带宽来进行简化计算。球函数$D\left( {\theta, \phi } \right)$频率小于$N$，则有

$ D\left( {\theta, \phi } \right) = \sum\limits_{\eta = 0}^N {\sum\limits_{\omega =-\eta }^\eta {{h_{\eta \omega }}Y_\eta ^\omega \left( {\theta, \phi } \right)} } $

(5)

${Y_\eta ^\omega \left( {\theta, \phi } \right)}$为球面调和函数，其满足球面调和方程

$ \begin{array}{*{20}{c}} {\frac{{\Phi \left( \varphi \right)}}{{\sin \theta }}\frac{{\rm{d}}}{{{\rm{d}}\theta }}\left( {\sin \theta \frac{{{\rm{d}}\Theta \left( \theta \right)}}{{{\rm{d}}\theta }}} \right) + \frac{{\Theta \left( \theta \right)}}{{{{\sin }^2}\theta }}\left( {\frac{{{{\rm{d}}^2}\Phi \left( \varphi \right)}}{{{\rm{d}}{\varphi ^2}}}} \right) + }\\ {\eta \left( {\eta + 1} \right)\Theta \left( \theta \right)\Phi \left( \varphi \right) = 0} \end{array} $

(6)

定义$D\left( {\theta, \phi } \right)$频率为$\eta $的能量特征为

$ {t_\eta } = \sqrt {\sum\limits_{\omega =-\eta }^\eta {{{\left| {{h_{\eta \omega }}} \right|}^2}} } $

(7)

可得到特征向量序列为$\left\{ {{t_\eta }\left| {\eta = 0, 1, \cdots, N-1} \right.} \right\}$。

可使用特征向量之间的欧氏距离衡量3维对象之间的特征差异，即

$ D\left( {{S_1}, {S_2}} \right) = \sqrt {\left( {\sum\limits_{\eta = 0}^{N-1} {{{\left( {t_\eta ^{{S_1}}-t_\eta ^{{S_2}}} \right)}^2}} } \right)} $

(8)

采用基于信息熵的特征向量选择算法可以优化特征分类，以$\phi $表示场景层级面板中所存在的场景模型个体，以$\mu $表示待特征确定的模型，特征向量为$\boldsymbol{T}$，则相似特征序列$\boldsymbol{A}_T^\mu $表示采用特征向量$\boldsymbol{T}$下对应的模型$\mu $与其他模型相似距离递增序列，以${\boldsymbol{P}_k}\left( {{\varphi _j}, \boldsymbol{A}_T^\mu } \right)$表示对于序列$\boldsymbol{A}_T^\mu $前$k$个模型中的属于模型类${\phi _i}$整体的比例，则特征向量$\boldsymbol{T}$对于模型$\mu $的$k$-信息熵非纯度可进行表示为

$ \begin{array}{*{20}{c}} {\varphi \left( {T,\mu ,k} \right) = }\\ { - \sum\limits_{i = 1}^m {\left\{ \begin{array}{l} {P_k}({\varphi _i},{\rm A}_T^\mu ){\rm{lo}}{{\rm{g}}_2}({P_k}({\varphi _i},{\rm A}_T^\mu ))\;\;\;\;\;{P_k} > 0\\ 0\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;其他 \end{array} \right.} } \end{array} $

(9)

假设序列$A_T^\mu $中前$k$个模型均属于同类模型，则非纯度值为0；否则其值为正。当$k$个模型所属模型类数目最大时其非纯度值最大。

假设$\mathit{\Psi = }\left\{ {{T_1}, {T_2}, \cdots, {T_n}} \right\}$为$n$种不同特征向量集合，根据$k$-信息熵非纯度选择函数

$ \begin{array}{*{20}{c}} {Ent_{{\rm{Selection}}}^{{\rm{lmp}}}({T^*}, \alpha, k) = }\\ {{\rm{arg}}\mathop {{\rm{min}}}\limits_{1 \le j \le n} \{ i({T_j}, \alpha, k)\} } \end{array} $

(10)

根据$k$-信息熵非纯度最小的特征向量来匹配模型$\mu $，从而确定模型的特征向量。这就涉及特征聚类，本文采用ART (adaptive resonance theory neural network) 网络来实现。

ART网络具有非离线学习的能力，同时具有较好的记忆和扩展能力。将3维场景对象特征向量作为模式序列，具体算法流程如下：

输入：模式序列$\boldsymbol{X} = \left\{ {{\boldsymbol{x}_1},{\boldsymbol{x}_2}, \cdots ,{\boldsymbol{x}_n}} \right\}$，

${\boldsymbol{x}_j} = {[{x_{1j}}, {x_{2j}}, \ldots, {x_{ij}}, \ldots, {x_{nj}}]^{\rm{T}}}, x \in \left[{0, 1} \right]$

使$M$=1，前馈权值矩阵初始化：$\boldsymbol{W}{\rm{ = }}{\left[{\frac{1}{{1{\rm{ + }}n}}} \right]_{M \times n}}$

反馈权值矩阵初始化：$\boldsymbol{T} = {\left[1 \right]_{M{\rm{ \times }}n}}$；

ART网络的警戒阈值$\rho \in \left( {0, 1} \right]$，学习速率$\beta \in \left( {0, 1} \right]$，其与训练时间$t$和邻域内第$j$个神经元与获胜神经元$j$^*之间的拓扑距离$H$呈现反比关系，本文采取退火函数$\beta \left( {t, H} \right) = \beta (t){e^{-H}}$对$\beta $改进。

输出：更新前馈权值$\boldsymbol{W}$、反馈权值$\boldsymbol{T}$及聚类数$M$，算法流程如下：

for $j$=1 to $N$ do

for $m$=1 to $M$ do ${S_{mj}} \leftarrow {W_m}{x_j}$ end for//识别层处理

$B = {W_m}{x_j}$

$B \leftarrow \left\{ {1, 2, \cdots M} \right\}$

while $B \ne \varphi $ do

$r \leftarrow \arg \;\;\mathop {\max }\limits_{{\rm{m}} \in {\rm{B}}} \left\{ {{S_{mj}}} \right\}$

if ${T_r}{\boldsymbol{x}_j}/{\rm{ }}\boldsymbol{x}_j^T{\boldsymbol{x}_j} > \rho $ then//识别层处理

${T_r} \leftarrow \left( {1-\beta } \right){T_r} + \beta ({T_r} \cdot {x_j})$

${W_r} \leftarrow (2{T_k} \cdot {x_j})/(1 + {T_k}{x_j})$

$\boldsymbol{T} \leftarrow \left[{ \cdots {T_{r-1}}, {T_t}, {T_{r + 1}} \cdots } \right]_{M \times n}^{\rm T}$

$\boldsymbol{W} \leftarrow \left[{ \cdots {W_{r-1}}, {W_r}, {W_{r + 1}} \cdots } \right]_{M \times n}^{\rm T}$

go to continue

else $B \leftarrow B\backslash r$ end if

end while

$\boldsymbol{M} \leftarrow M + 1, {W^*} \leftarrow {\left[{\frac{1}{{1 + \boldsymbol{x}_j^{\rm{T}}{\boldsymbol{x}_j}}}} \right]_{1 \times n}}$

$\boldsymbol{W} \leftarrow {\left[\begin{array}{l} W\\ {W^*} \end{array} \right]_{M \times n}}, \boldsymbol{T} \leftarrow {\left[\begin{array}{l} \boldsymbol{T}\\ x_j^{\rm{\boldsymbol{T}}} \end{array} \right]_{M \times n}}$

continue

end for

其中$\boldsymbol{B\backslash r}$表示从集合$\boldsymbol{B}$中剔除。

ART网络执行流程如下：

将3维特征作为输入模式进行输入：

$ \boldsymbol{X} = ({\boldsymbol{x}_1}, {\boldsymbol{x}_2}, \cdots, {\boldsymbol{x}_n}), {\boldsymbol{x}_i} \in {\left( {0, 1} \right)^n} $

当$G$1为1时允许输入模式直接从$C$层输出，并前馈至$R$层，与$R$层节点对应的所有对应连接权值${\boldsymbol{W}_j}$进行匹配度计算，即

$ ne{t_j} = \boldsymbol{W}_j^{\rm{T}}\boldsymbol{X}{\rm{ }} = \sum\limits_{i = 1}^n {{w_{ij}}{\boldsymbol{x}_i}}, j = 1, 2, \cdots, m $

特征向量相似性度量可采用内积法进行特征相似度距离计算，即

$ {\boldsymbol{X}^{\rm{T}}}{\boldsymbol{X}_i} = \left\| \boldsymbol{X} \right\|\left\| {{\boldsymbol{X}_i}} \right\|{\rm{cos}}\;\;\theta $

遴选胜利节点 (Winner Take All原则)，即

$ ne{t_{{j^*}}} = \mathop {\max }\limits_j \left\{ {ne{t_j}} \right\} $

相似度比较阶段非常重要，存在警戒门线值为$\rho $，其取值范围为0~1。设${t_{ij}}$为反馈连接权值，则有$\sum\limits_{i = 1}^n {{t_{i{j^*}}}{x_i}} $为反馈权值与输入模式之间的相似度比较，$\sum\limits_{i = 1}^n {{x_i}} $为输入样本中非零分量的个数。检查输入模式与模式类典型向量之间的相似性，即

$ N = \frac{{\sum\limits_{i = 1}^n {{t_{i{j^*}}}{x_i}} }}{{\sum\limits_{i = 1}^n {{x_i}} }} $

如果$N < \rho $则$\boldsymbol{X}$与典型特征向量的相似程度不满足要求，网络发出Reset信号使第一阶段匹配失败，获胜节点无效，网络重新进入搜索阶段。

如果$N > \rho $表明$\boldsymbol{X}$与获胜节点对应的类别模式非常接近，则$\boldsymbol{X}$与${T_{{j^*}}}$发生“共振”，匹配结果有效，则进入学习阶段调整${j^*}$对应的反馈权值向量

$ {t_{i{j^*}}}\left( {t + 1} \right) = {t_{i{j^*}}}\left( t \right){\boldsymbol{x}_i}, i = 1, 2, \cdots .n:{j^*}\;\; \in {J^*} $

其前馈连接权值按照以下规则调整，即

$ \begin{array}{*{20}{c}} {{w_{i{j^*}}}\left( {t + 1} \right) = \frac{{{t_{i{j^*}}}\left( t \right){x_i}}}{{0.5 + \sum\limits_{i = 1}^n {{t_{i{j^*}}}\left( t \right){x_i}} }} = }\\ {\frac{{{t_{i{j^*}}}\left( {t + 1} \right)}}{{0.5 + \sum\limits_{i = 1}^n {{t_{i{j^*}}}\left( {t + 1} \right)} }}} \end{array} $

(11)

如果遍历所有候选聚类都不能与输入模式共振，说明当前输入模式的全新的模式类，则由输入模式建立一个新聚类，同时将其前馈连接权值${W_{{j^*}}}$设计成当前输入模式向量，其反馈连接权值${T_{{j^*}}}$各分量全部设为1。该特征被记忆为新聚类$M$+1。通过上述方法实现对场景3维对象特征聚类。

基于特征聚类得到的标记，可以通过语法规则勾勒出建筑群落所包含的基本特征和组织形式，其一般形式如下：

$ \begin{array}{l} {\rm{LayoutConstruction}} \to \left( {Front} \right)\left( {Border} \right)\\ \{ \;Grou{p_0}Grou{p_1} \ldots Grou{p_{N-1}}\} \;\left( {Back} \right)\\ OrgGroup \to \{ \;Featur{e_0}Featur{e_1}Featur{e_2} \ldots \\ Featur{e_{K-1}}\} \end{array} $

其中，Layout Construction表示层次结构，($Front$)、($Border$)、($Back$) 分别表示层次划分边界，{$Group$₀，$Group$₁，…，$Group$_$N$-1}表示层次之间包含的特征组集合，$OrgGroup$表示层次中的特征组，{$Feature$₀，$Feature$₁，…，$Feature$_$K$-1}表示组内特征集合。

$ \begin{array}{l} {\rm{Unit}}Feature \to \{ {A_0}{A_1}{A_2} \ldots {A_{S-1}}\} \\ {\rm{Array}}A \to \{ {E_0}{E_1}{E_2} \ldots {E_{T-1}}\} \end{array} $

其中Unit $Feature$表示特征单元，内部元素可分解为$A$₀，$A$₁，…，$A$_$S$-1；每个元素$A$可视为数组对象，数组类型不同则元素不同，数组元素为基本的贴图和3维构件，以{$E$₀，$E$₁，…，$E$_$T$-1}表示。

若有表示立面纹理的数组，可记为$Facade$，数组元素为立面纹理特征如镂空效果 ($BC$)、雕梁画栋 ($FWPS$)、廊柱装饰 ($PS$)，则可以通过索引排列反映其立面组织形式。数组列中连续出现的重复性相似特征，可以通过正则表达式的Kleene星号来进行简化，即

$ Facade = \left( {BC} \right)\left( {FWPS} \right)*\left( {BC} \right)(PS) $

重复出现的特征组合可记为${E_i}, i = 1, 2, \cdots, n$。例如$Facade$组合中的$FWPS$即花窗 ($FW$) 与斗拱/雕栋 ($PS$) 组合，由于组合频率较高，可合并并标记为$E$₁。若存在符合上述特点的特征序列$E$₁、$E$₂、$E$₃，通过扫描特征数组并标记重复性终结的特征节点，可将毗邻重复实例标记组置换为单一标记组实例，并对连续重复性特征添加Kleene星号以表征其连续重复性，典型的推导案例如下：

$ \begin{array}{*{20}{c}} {{E_1}{E_1}{E_2}{E_1}{E_2}{E_2}{E_1}{E_3}{E_1}{E_3}{E_2} \to }\\ {{E_1}\left( {{E_1}{E_2}} \right)\left( {{E_1}{E_2}} \right){E_2}\left( {{E_1}{E_3}} \right)\left( {{E_1}{E_3}} \right){E_2} \to }\\ {{E_1}\left( {{E_1}{E_2}} \right)*{E_2}\left( {{E_1}{E_3}} \right)*{E_2}} \end{array} $

Wang等人^[12]提出通过对称性约束条件实现布局的重定向，并对布局约束的分类及表达进行研究。Song等人^[13]基于蚁群算法实现元件布局和管线路径优化。在3维模型空间的布局上，采用蚁群算法优化空间结构。优化的过程涉及到分层，对矩形布局区域采用“包围盒”的方法，其目的是通过蚁群算法的优化，使得场景建筑之间的组织关系更加优化，以实现较好的游戏用户体验。

蚁群算法 (ant colony algotithm) 由意大利学者Dorigo等人^[14]于20世纪90年代提出，其是一种基于种群的启发式仿生类并行智能进化算法。基于蚁群算法的包围盒布局模型的描述为

$ \max \;\;Fit = \frac{{\sum\limits_{i = 1}^n {\left( {({l_i} + \Delta l) \times \left( {{w_i} + \Delta w} \right) \times {h_i}} \right)} }}{{L \times W \times H}} $

(12)

式中，$Fit$为包围盒布局适应值函数 (包围盒利用率)；$n$为包围盒中矩形建筑区域个数；${l_i}$、${w_i}$、${h_i}$分别表示第$i$个纳入包围盒的建筑矩形区域其长、宽、高；$L$、$W$、$H$表示包围盒的长、宽、高；$\Delta l$、$\Delta w$为矩形区域为建筑周边预留的容积，视不同尺度设计而各异，可由设计师确定。

$ \left\{ \begin{array}{l} ({l_i} + \Delta l)/2 \le {x_i} \le L-({l_i} + \Delta l)/2\\ ({w_i} + \Delta w)/2 \le {y_i} \le W-({w_i} + \Delta w)/2\\ {h_i}/2 \le {z_i} \le H-{h_i}/2 \end{array} \right. $

$ \left\{ \begin{array}{l} {x_i}-({l_i} + \Delta l)/2 \ge {x_j} + ({l_j} + \Delta l)/2或\\ {x_j}-({l_j} + \Delta l)/2 \ge {x_i} + ({l_i} + \Delta l)/2\\ {y_i}-({w_i} + \Delta w)/2 \ge {y_j} + ({w_j} + \Delta w)/2或\\ {y_j} - ({w_j} + \Delta w)/2 \ge {y_i} + ({w_i} + \Delta w)/2\\ {z_i} - ({h_i} + \Delta h)/2 \ge {z_j} + ({h_j} + \Delta h)/2或\\ {z_j} - ({h_j} + \Delta h)/2 \ge {z_i} + ({h_i} + \Delta h)/2 \end{array} \right. $

式中，$({x_i}, {\rm{ }}{y_i}, {\rm{ }}{z_i})$和$({x_j}, {\rm{ }}{y_j}, {\rm{ }}{z_j})$分别表示第i个和第j个纳入的矩形3维局域中心点坐标；${l_j}$、${w_j}$、${h_j}$表示第$j$个纳入的3维对象长、宽、高。该部分实现了矩形区域块之间互不干扰的作用。

依托之前研究理论，对3维场景分层采用“盒子抽象 (Box-Abstraction)”方法，将基于某种特征阈值范围内的元素分离为一系列抽象盒子，分析的方法是进行逐层分解，至对称性元素不可再继续分解为止，见图 1、图 2。

将若干具有相似对称特征并与其他对象呈现轴对称特征的抽象盒子按原有组织结构提取，该扩展抽象盒隶属于整体结构中的部分规则网格，形成的前提是必须使其内部元素达到对称性最大化，即无法再扩充任何一个具有相同对称属性的元素归并至同一层级。

蚁群算法具有记忆功能，若建立记忆列表$tab{u_k}$($k$=1，2，…，$m$) 来存储蚂蚁所经历过的节点，则随着算法的进程而动态调整$tab{u_k}$。令${\tau _{ij}}$为$t$时刻残留在路径 ($i$，$j$) 上的信息素，蚂蚁开始搜索时初始化信息素${\tau _{ij}}$(0)=$C$($C$在各条路径上分布相等)，蚂蚁$k$($k$=1，2，…，$m$) 搜索过程中根据信息素来决定转移方向，可以得到$t$时刻位于节点$i$的蚂蚁$k$选择节点$j$为目标节点的概率计算公式为

$ p_{ij}^k(t) = \left\{ \begin{array}{l} \frac{{{{\left[{{\tau _{ij}}(t)} \right]}^\alpha } \cdot {{\left[{{\eta _{ij}}(t)} \right]}^\beta }}}{{\sum\limits_{k \subset allowe{d_k}} {{{\left[{{\tau _{ik}}(t)} \right]}^\alpha } \cdot {{\left[{{\eta _{ik}}(t)} \right]}^\beta }} }}\;\;\;\;j \subset allowe{d_k}\\ 0\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;其他 \end{array} \right. $

(13)

式中，$\alpha $为启发因子，反映了信息素对蚂蚁搜索的影响力；$\beta $为期望启发因子，反映了启发信息的重要程度；${{\eta _{ik}}}$为先验知识能见程度 (启发信息)，若${d_{ij}}$($i$，$j$=1，2，…，$n$) 表示建筑物$i$与建筑物$j$之间的距离，通常取${\eta _{ij}} = 1/{d_{ij}}$；概率$p_{ij}^k\left( t \right)$表示$t$时刻蚂蚁$k$由节点$i$转移到节点$j$的概率；$allowe{d_k}$={1，2，…，$n$－$tabu$}表示允许蚂蚁下一步继续寻找节点集合；$tab{u_k}$($k$=1，2，…，$m$) 表示蚂蚁$k$已经走过建筑节点的集合。

接下来基于蚁群算法来对空间3维对象的布局进行优化。在包围盒区域中采用吸引子法实现建筑模型的布局。可为包围盒区域设置$m$个吸引子，吸引子$\sigma $坐标为$({x_\sigma }, {\rm{ }}{y_\sigma }, {\rm{ }}{z_\sigma })$。由此可以得到待布局的3维对象$\eta $在点$({x_\eta }, {\rm{ }}{y_\eta }, {\rm{ }}{z_\eta })$处的定位函数为

$ \begin{array}{l} f\left( {{x_\eta },{y_\eta },{z_\eta }} \right) = \sum\limits_{\sigma = 1}^m {{\omega _\sigma }{\varphi _\sigma }} ({x_\eta },{y_\eta },{z_\eta }) = \\ \sum\limits_{\sigma = 1}^m {{\omega _\sigma }\left[ \begin{array}{l} {\kappa _\sigma }\left| {{x_{\eta }} - {x_\sigma }} \right| + \\ {\lambda _\sigma }\left| {{y_\eta } - {y_\sigma }} \right| + \\ {\mu _\sigma }\left| {{z_{\eta }} - {z_\sigma }} \right| \end{array} \right]} ,(\eta {\rm{ }} = {\rm{ }}1, \cdots ,n) \end{array} $

(14)

定位评价函数可表示为min$f$$({x_\eta }, {\rm{ }}{y_\eta }, {\rm{ }}{z_\eta })$是关于吸引子$\sigma $的定位评价函数，${\kappa _\sigma }$、${\lambda _\sigma }$、${\mu _\sigma }$为朝向$X$、$Y$、$Z$坐标轴方向的权重，且${\kappa _\sigma } + {\lambda _\sigma } + {\mu _\sigma } = 1$；${{\omega _\sigma }}$为吸引子自身权重因子，且$\sum\limits_{t = 1}^m {{\omega _t} = 1} $；$n$为待布局的总数。若权重因子为负值，则吸引子可视为排斥子。

通过蚁群算法来优化吸引子参数，其具体步骤如下：

1) 设置迭代次数$T$及蚂蚁数量$M$；

2) 初始化信息素$\;{\tau _{ij}}$，计算每只蚂蚁的适应度$Fit$($i$) 并获得适应度最大的个体，最优解的值记为$I$_best，其适应度标记为$Fit$($I$_best)，携带的信息素值为${\tau _{{I_{{\rm{best}}}}}}$；

3) 迭代次数$t$++，$i$=0；

4)$i$++；

5) 对信息素进行更新，各蚂蚁转移率为${p_{ij}} = {\rm{ }}\left| {{\tau _{{I_{{\rm{best}}}}}}-{\tau _{ij}}} \right|/{\tau _{{I_{{\rm{best}}}}}}$。

若$p$₀为蚂蚁转移概率的临界值，经过$\Delta t$时刻当${p_{ij}} \le {p_0}$时，${\tau _{ij}} = {\tau _{ij}}$，临近最优解；当${p_{ij}} \ge {p_0}$时，更新信息素

$ \left\{ \begin{array}{l} {\tau _{ij}}(t + \Delta t) = \left( {1-\rho } \right){\tau _{ij}}\left( t \right) + \Delta {\tau _{ij}}(t)\\ \Delta {\tau _{ij}} = \rho \cdot Fit({I_{{\rm{best}}}}) \end{array} \right. $

(15)

$\rho $为信息素挥发因子，其对蚁群算法的搜索能力和收敛速度有重大影响；$\rho $过小则导致无效区域被持续搜索从而影响收敛速度；$\rho $过大则会对可能有效路径进行排除从而影响到最优值的搜索。

6) 记更新后的适应度为$Fit$^*(i)，若$Fit$^*($i$)>$Fit$($I$_best)，则$Fit$($I$_best)=$Fit$^*($i$)，$I$_best=$I$_best^*；若当前循环执行完毕则转至步骤4)；

7) 若$t$ < $T$，转至步骤8)，否则转至步骤3)；

8) 输出蚂蚁$I$_best的信息、$Fit$($I$_best) 及布局方案。

若进入局部最优解，则算法停止。如果希望尽可能增大蚂蚁活动的周期，可通过占角顺序策略、下台阶法等减少算法陷入局部最优解的概率。

考虑到$ρ$=$c$×$\boldsymbol{K}$，$\boldsymbol{K}$为与$\rho $相关的常数，$c$为变量因子。减小$\rho $可提升全局搜索能力，但会降低收敛速度。可改进为

$ \rho \left( t \right) = \left\{ \begin{array}{l} {\rho ^2}\left( {t-1} \right)/c{\rm{ }}\;\;\rho \left( t \right) \ge {\rho _{{\rm{min}}}}\\ {\rho _{{\rm{min}}}}\;\;\;\;\;\;\;\;\;\;\;\;\;其他 \end{array} \right. $

(16)

可通过Sigmoid函数对其进行优化，即

$ c = \frac{{2a}}{{1 + {{\rm{e}}^{-b \cdot t}}}}-a $

(17)

式中，$t$为迭代次数，$a$、$b$为微调因子，可通过实验估算。$a$的取值范围为 (0，1]，b取值范围为 (0，2]。

经过20次迭代的相关参数值如表 1所示。

为了尽可能增加蚂蚁活动的可能性，需要防止算法陷入局部最优解，可考虑在$q$≥$q$₀采用轮赌法选择进行优化，即

$ sum = \sum\limits_{i = 1}^6 {(\tau {{\left( i \right)}^\alpha } \times \eta {{\left( i \right)}^\beta })} $

(18)

$ p\left( j \right) = \sum\limits_{i = 1}^j {\tau {{\left( i \right)}^\alpha } \times \eta {{\left( i \right)}^\beta }} $

(19)

式中，$\alpha $为各节点信息素浓度的启发因子，$\beta $为各节点的期望启发因子；$j$为蚂蚁下一步要选择的节点，${\tau \left( i \right)}$为下一个可选节点的信息素量，${\eta \left( i \right)}$为可选节点的启发式信息素，两者决定蚂蚁下一个行走节点。

包围盒抽象的处理过程概括了通过该方法进行纵向和横向扩充的过程，如图 3所示。

对于建筑群落，在优化过程中需要对每次分解后的节点进行对称性评价，而最终目标是得到所有分解层次内在节点的对称性之和。对称性评分难以使用显式函数表达，若以$Symmetry $$Value$来表示场景结点的对称性评分，则包含各层次结点$node$信息的全局对称性评分可表示为

$ \mathop {\arg \;\max }\limits_{Hierarchy} \left\{ {\sum\limits_{node} {Symmetry\;Value\left( {node} \right)} } \right\} $

(20)

比较直接的方法是基于贪婪策略 (greedy strategy) 逐步构建最优解，形成基于吸引子约束条件的包围盒布局，如图 4、图 5所示。

Gao等人^[15]采用简单遗传算法实现对建筑布局的重新排列，但较难处理复杂3维场景，具有一定局限性。基于布局约束实现3维建筑布局优化的本质是在满足上述布局约束的前提下使特定位置上建筑的摆放格局最优。如图 6所示，将3维建筑布局的区域划分为$m$×$n$个单元区域，3维建筑单体可以居于一个单元区域，也可以跨越多个区域，视其体量大小而不同。可以将该$m$×$n$个区域视为维度为$m$×$n$的矩阵，矩阵中的元素为不同建筑单体的特征基因型，如图 7所示。

布局矩阵中可发现该规律：相邻元素值相同则对应同一个3维对象的不同部分。在优化计算时使用矩阵编码的遗传算法，随机选择矩阵区块进行矩阵交叉及变异处理，使原矩阵维数发生改变从而生成新的布局类型。子代第$k$代种群${\boldsymbol{P}_k}$个体数目为$\eta $，${\boldsymbol{P}_k} = \left\{ {{\boldsymbol{A}_1}, {\boldsymbol{A}_2}, \cdots, {\boldsymbol{A}_\eta }} \right\}$，则若以A$i$表示$k$代种群中第$i$($i$∈{1，2，…，$\eta $}) 个矩阵染色体，其中$a_{pq}^i$($p$∈{1，2，…，$m$}，$q$∈{1，2，…，$n$}) 为其基因元素，即

$ {\boldsymbol{A}_i} = \left[{\begin{array}{*{20}{c}} {a_{11}^i}&{a_{12}^i}& \cdots &{a_{1n}^i}\\ {a_{21}^i}&{a_{22}^i}& \cdots &{a_{2n}^i}\\ \vdots & \vdots &{}& \vdots \\ {a_{m1}^i}&{a_{m2}^i}& \cdots &{a_{mn}^i} \end{array}} \right] $

选择交叉算子进行存优去劣处理，用适应度最优的染色体替换适应度最差的染色体，即若原来第$k$代种群染色体为$\left\{ {{\boldsymbol{A}_1}, {\boldsymbol{A}_2}, \cdots, {\boldsymbol{A}_k}, \cdots, {\boldsymbol{A}_j}, \cdots, {\boldsymbol{A}_\eta }} \right\}$，其最优适应度个体为${{\boldsymbol{A}_k}}$，最差适应度个体为${{\boldsymbol{A}_j}}$，其选择操作后的种群${\boldsymbol{P}_k}$为$\left\{ {{\boldsymbol{A}_1}, {\boldsymbol{A}_2}, \cdots, {\boldsymbol{A}_k}, \cdots, {\boldsymbol{A}_j}, \cdots, {\boldsymbol{A}_\eta }} \right\}$，然后任意选取两个矩阵块按照一定概率$\varphi $来进行交叉操作，以种群${\boldsymbol{P}_k}$中任意选取的两个矩阵染色体为例，即

$ \begin{array}{l} {\boldsymbol{A}_i} = \left[{\begin{array}{*{20}{c}} {a_{11}^i}&{a_{12}^i}& \cdots &{a_{1n}^i}\\ {a_{21}^i}&{a_{22}^i}& \cdots &{a_{2n}^i}\\ \vdots & \vdots &{}& \vdots \\ {a_{m1}^i}&{a_{m2}^i}& \cdots &{a_{mn}^i} \end{array}} \right]\\ {\boldsymbol{A}_j} = \left[{\begin{array}{*{20}{c}} {a_{11}^j}&{a_{12}^j}& \cdots &{a_{1n}^j}\\ {a_{21}^j}&{a_{22}^j}& \cdots &{a_{2n}^j}\\ \vdots & \vdots &{}& \vdots \\ {a_{m1}^j}&{a_{m2}^j}& \cdots &{a_{mn}^j} \end{array}} \right] \end{array} $

则经过交叉运算后则为

$ \begin{array}{l} {\boldsymbol{A}_i} = \left[{\begin{array}{*{20}{c}} {a_{11}^j}&{a_{12}^j}& \cdots &{a_{1n}^j}\\ {a_{21}^i}&{a_{22}^i}& \cdots &{a_{2n}^i}\\ \vdots & \vdots &{}& \vdots \\ {a_{m1}^j}&{a_{m2}^j}& \cdots &{a_{mn}^j} \end{array}} \right]\\ {\boldsymbol{A}_j} = \left[{\begin{array}{*{20}{c}} {a_{11}^i}&{a_{12}^i}& \cdots &{a_{1n}^i}\\ {a_{21}^j}&{a_{22}^j}& \cdots &{a_{2n}^j}\\ \vdots & \vdots &{}& \vdots \\ {a_{m1}^i}&{a_{m2}^i}& \cdots &{a_{mn}^i} \end{array}} \right] \end{array} $

矩阵变异操作本质是将染色体中某些基因值用其他等位基因值来替换，从而形成新的局部矩阵个体，基因片段是随机选取的，以${P_k}$的一个矩阵染色体为例，即

$ \begin{array}{l} {\boldsymbol{A}_i} = \left[{\begin{array}{*{20}{c}} {a_{11}^i}&{a_{12}^i}& \cdots &{a_{1n}^i}\\ {a_{21}^i}&{a_{22}^i}& \cdots &{a_{2n}^i}\\ \vdots & \vdots &{}& \vdots \\ {a_{m1}^i}&{a_{m2}^i}& \cdots &{a_{mn}^i} \end{array}} \right]\mathop \Rightarrow \limits^{单点变异} \\ \;\;\;\;\;\;{\boldsymbol{A}_i} = \left[{\begin{array}{*{20}{c}} {a_{11}^i}&{a_{12}^i}& \cdots &{a_{1n}^i}\\ {a_{21}^i}&{a_{22}^i}& \cdots &{a_{2n}^i}\\ \vdots & \vdots &{}& \vdots \\ {a_{m1}^i}&{a_{m2}^i}& \cdots &{a_{mn}^i} \end{array}} \right] \end{array} $

式中，$a$为按照上述规则操作后得到的基因值。

由于针对的是隐式性能指标优化问题，因此有必要对矩阵基因区块的遗传操作进行算法优化。若进化的候选对象记为$x$，则其第$n$个等位基因意义单元记为$U_n^{{m_t}}$，其适应值记为$F$($U_n^{{m_t}}$)，则候选对象$x$的适应值$F$($x$) 可表示为

$ F\left( x \right) = \sum\limits_{n = 1}^k {{\omega _n}F} (U_n^{{m_t}}) $

(21)

式中，${\omega _n}$为$n$代进化过程中的基因单元修正值。Kim等人^[16]认为严格意义上精准的$U_n^{{m_t}}$是不存在的，用户无法充分认识$U_n^{{m_t}}$但可以通过逐步进化个体信息从而提取出$U_n^{{m_t}}$的估计值，可利用的个体进化信息越多，对于适应值$U_n^{{m_t}}$的估计值越准确。

因为场景布局涉及主观审美，适应值$U_n^{mt}$可拆分为多项因子。借鉴建筑设计中对黄金分割特征及对称性特征的应用，同时结合空间利用率，将适应度函数设置为

$ \begin{array}{*{20}{c}} {F\left( x \right) = {\omega _1} \times H\left( x \right) + {\omega _2} \times S\left( x \right) + }\\ {{\omega _3} \times G\left( x \right) + {\omega _4} \times L(x)} \end{array} $

(22)

式中，$x$为选取的布局方案，$H$($x$)、$S$($x$)、$G$($x$)、$L$($x$) 分别为空间利用率、对称性、黄金分割度、路径优化度等度量值；${{\omega _1}}$、${{\omega _2}}$、${{\omega _3}}$、${{\omega _4}}$为各个度量值的权值，满足${{\omega _1}}$、${{\omega _2}}$、${{\omega _3}}$、${{\omega _4}}$∈[0,1]且满足$\sum\limits_{n = 1}^k {{\omega _n}} $=1。

假设进化第${{k_i}}$代最优秀个体为${{x_e}\left( {{k_i}} \right)}$，其适应值为${F\left( {{x_e}\left( {{k_i}} \right)} \right)}$，其中$K$_start≤${{k_i}}$≤$K$_final。使用开关量来控制${{x_e}\left( {{k_i}} \right)}$的组成，记为${\delta \left( {U_n^{{m_t}}, {k_i}} \right)}$。若$U_n^{{m_t}}$在${{x_e}\left( {{k_i}} \right)}$中，令${\delta \left( {U_n^{{m_t}}, {k_i}} \right)}$=0，则有

$ \left\{ \begin{array}{l} \hat F(U_n^{{m_t}}) = {\rm{ }}\frac{1}{\Delta }\sum\limits_{{k_i} = {K_{{\rm{start}}}}}^{{k_{{\rm{final}}}}-1} {\delta \left( {U_n^{{m_t}}, {k_i}} \right)F\left( {{x_e}\left( {{k_i}} \right)} \right)} \\ \Delta = \sum\limits_{{k_i} = {K_{{\rm{start}}}}}^{{k_{{\rm{final}}}}-1} {\delta \left( {U_n^{{m_t}}, {k_i}} \right)} \end{array} \right. $

(23)

Guo等人^[17]认为当进化种群对称性特征基因间的差异较小的时候，使用全局搜索很难再进行分层，并且难以提高算法性能，Gong等人^[18]采取达到此临界状态时终止全局搜索转而进入局部搜索的方法。

交互式遗传操作的重点是用户可以通过评价各类特征适应值，从而筛选出种群最优个体，从而驱动种群往更加优化的结果进化。整体算法流程如图 8所示。

实验初始化采用8组小规模的建筑组合作为初始输入对象，初始化参数如表 2所示。

采用基本遗传算法 (SGA)、基本交互式遗传算法 (SIGA) 作为对照实验，因本文算法结合多重预处理及其他算法协同处理，故标记为CIGA算法。处理初期在3维场景中导入对象，如图 9所示。

继续添加对象，将新旧场景的结构及层次进行混合，陆续导入其他建筑组合，通过蚁群算法进行布局优化，完成后进入本文所设计的CIAG遗传算法，筛选最优解并重构场景，如图 10所示。

CIGA进入后期，全局搜索进行分层达到终结状态。转而进入区域搜索阶段，通过遗传操作得出最优解，如图 11所示。

对照实验的SGA、SIGA所得出的最优解记为$f\left( {{k_i}} \right)$，本文提出的CIGA算法得到的输出为$\hat f\left( {{k_i}} \right)$，均为不同算法得出的${x_i}$适应值的估计值，易得测试误差为

$ \sigma = \sqrt {\frac{1}{N}\sum\limits_{i = 1}^N {\sigma _i^2} } $

(24)

式中，${\sigma _i} = f\left( {{k_i}} \right)-\hat f\left( {{k_i}} \right)$，如果满足$\sigma < {\sigma _i}$则说明得出的适应值精度满足要求。

表 3为SGA、SIGA与本文算法CIGA的性能对比。通过实验表明在满足适应值精度的要求下，本文所采取的CIGA方式在较少用户评价次数及进化代数下可以得到最优解。

由于人的认知过程具有渐进性，且偏好受心理因素及环境的影响而具有不稳定性，因此每代所对应的表现型会出现波动；以${x_e}\left( {{k_i}} \right)$表示第${{k_i}}$代用户认为的最优解，${x_e}$为CIGA操作稳定后的最优解，初期用户偏好呈现紊乱无规律分布，均随着进化代数的递进趋于稳定，如图 12所示。

不同用户对评价对象的层次结构及组织方式认识不同，系统根据其偏好得出进化个体的适应值，使场景扩充达到预期效果。该方法缺点是该方法倾向于对隐式性能指标的优化而无法建立明确的数学模型，对于评价各适应值的度量因子尚待优化。

针对复杂3维场景的重构及扩展问题，提出一种多方法协同处理的交互式遗传算法。

首先，将由设计师创作的3维场景对象作为输入对象，基于其内部组织结构及特征进行分层处理，并进行特征归类；其次，对典型特征模型进行蚁群算法布局，采用包围盒的方法实现优化；然后基于形成的布局进行交互式遗传算法优化以形成用户个性化设计，在全局搜索结束时，若某些对优秀特征基因仍无法提取，从而进入局部搜索，来求得各层进化个体最优解，得到重构的3维场景。该方法可以实现3维场景的扩充、混合和重构的效果，而减少琐碎而繁重的美工设计，同时能够提高游戏场景的良好用户体验感。不足之处是尚未建立系统的数学模型以研究其内在规律。实验证实该方法具有实际可操作性，有效提高了扩展复杂场景的运算效率，同时也增强了重构场景的各项美学指标。该方法在3维游戏设计、虚拟古迹复原及视景仿真领域具有实际意义。