---

(武汉大学遥感信息工程学院，武汉430079)

  【摘 要】阐述了 GIS 网络分析中不确定性选址问题的基本模型及特性。从问题的定义可知其为 NP 完备类问题。推导了最优解在紧条件的下界算法，并结合广义 Powell 算法及遗传算法，提出了不确定性选址问题的混合遗传算法，实验证明，在最优解的品质和收敛速度上都达到了比较好的效果。同时，实验的结果从另一个角度证明，如果兼顾收敛速度和解的品质这两个指标，单纯的遗传算法未必比其他搜索算法更优越，采用一些局部搜索性能较好的算法结合遗传算法，可以从两方面改善求解效果。

【关键词】GIS；不确定性选址；广义Powell算法；遗传算法

【中图分类号】P208    【文献标识码】A       【文章编号】1009-2307(2003)03-0046-04

1  引言

    选址问题，是指为一个或几个服务设施在一定区域内选定它的位置，使某一指标达到最优值。这类问题，在规划建设中经常可以碰到，这里所谓服务设施，可以是某些公共服务设施，如医院、消防站等。也可以是生产服务设施，如仓库，转运站等等。而区域则可以通过GIS网络形式来表示服务设施所服务的范围及其联系关系。可以认为，选址问题，就是把服务设施与服务对象，反映于统一的网络中，以便用GIS网络的关系进行研究。尽管对选址的目标、要求有不同的评判标准，但是要求服务对象与服务设施之间易于沟通、易于达到则是共同的^[1]。

        在网络分析中的选址问题一般分为两类，一类选址问题限定设施必须位于某个结点或位于某条网线上，或者限定在若干候选地点中选择位置，对于这类选址问题，基本可以看作是有确定解的选址，目前有多种算法可取得最优解。而另一类选址问题则未明确限定设施的位置，或未定义候选点的数量。可以证明该类问题属于NP问题，又可称为不确定性选址问题。在本文以下篇幅中，将对这类选址问题进行一致性建模并讨论其适应算法。

2  问题建模及算法思想

2.1不确定性选址的模型

    不确定性选址问题，主要考虑的问题是服务点数可以有多个，需要综合权衡选址的费用与设施日常经营过程的费用。如一些企业的仓库设置问题。

2.1.1无容量设施的不确定性选址

其基本模型如下：

目标：

 

其中 C为全体服务对象的集合；F为设施可能选址位置的集合；若设施置于i位置，y_i=1；若设施不置于i位置，y_i=0。

若位于i设施，向j点提供服务，x_ij＝1；则x_ij＝0。

C_ij为位于i点的设施向j点顾客提供服务的费用。

f_i为在 i点的设施向j点顾客提供服务的费用。

    在以上模型中，各个点对之间设施的单位营运费用可以各不相同，并且服务的需求量也可不相同。模型通过系数C_ij统一协调，同时在上述模型中不考虑容量问题，即不论i、j点如何选择，设施对服务的需求可以不加限制，或者也可以理解为x_ij取1则表示i设施能够完全满足j的需求，否则取0。

    多目标的简单选址问题，可以看做在二分图Km，n上求n条边的集合问题(对集问题)，每一条边表示服务设施与用户的服务关系。因此，与这些边有关的两个参数为各条边的权重以及与边关联的顶点的权重，分别对应服务费用及设置费用。满足和值取最小的边集即为问题的解。

结论1  在系数（c_ij，f_i）条件下的不确定性选址问题的最优解，亦是系数为（c^·_ij，f_i）条件下的最优解，在这里

结论1可以这样证明:任意一个可行解，恰好有一条边与每一用户关联，并且在系数(c_ij，f_i）条件下的解值与在系数（c^·_ij，f_i）条件下的解值，其差值相同。由于每一可行解以相同数值减少，所以得系数(c_ij，f_i）条件下的最优解与系数（c_ij，f_i）条件下的最优解相同。

可以进一步证明，若取

即可证明是最优解值的下界。

   若取因为与第i设施有关的运营费用Cij皆取最小值，且不考虑设施的固定费用，据此，按用户求和以后所得的值必为解的最低极限。

    由于每一设施的设置必导致固定费用的增加，任何方案至少应建立一个设施，假定每一设施的固定费用fi平均分配到全部用户，由此，可导出不确定性选址问题的紧条件。

    结论2  若为任意数集，且有。     则是不确定性选址问题的下界。

 

2．1．2  有容量设施的不确定性选址

      根据以上讨论，可以更一般性地推导有容量设施的不确定性选址模型，其公式如下：

约束条件如前。

 由定理条件1 和 2 以及可得：

   

因此，根据结论1，在系数为条件下，最优值minS_L 给出了多目标一般选址问题的一个下界。

    令为集的第 k最小元素，对所有。

求该类选址问题的下界算法如下：

令对所有，令，对所有。

若终止于下界等于，否则k＝k＋1返回上一步。

进一步假定，在选址问题中增加设施数的限制，即增加约束，，其下界可由系数为的不确定性选址问题的任一下界中减去而得到。

2.2广义Powell算法

    广义Powdl算法是一类适用于一般目标函数的直接搜索算法^[2]，与其他搜索算法相比，该算法无需目标函数的连续可导，因此，算法的适应面较广。其算法基本思想描述如下:

   (l)给定初始点X₀^（1），n个坐标轴方向P_i^（1）＝e，i＝1，2…n及，置k=l；

   (2)从X₀^（k）幼出发沿n个方向P_i^（k）进行一维搜索，

得：

      

（3)计算总移步方向：

         

从Xn^(k)出发，沿P^(k)方向移动，得：

      

(4)计算在第k阶段中函数的最大缩减量：

   

即在第m个方向Pm^(k)上目标函数值下降量最大。

  令

（5)检验：

     算法描述如下：是否成立，若成立，则转入6)；否则令 （即下一阶段的搜索方向仍采用这一阶段的搜索方向向)，并取X_n^(k)与X_n+1^(k)中

的较优者作为X₀^(k+1)，置k=k十1，转入(2)。

(6) X_n^(k)出发沿P^(k)方向进行一维搜索，得：

置

(7)检验 （）（7）检验是否成立，若成立，则迭代终止，取,否则置k=k十1转入(2)

    

 

 

 

 

 

2.3  PGA算法思想

       对于不确定性选址问题，上节仅给出了确定下界的算法，由于问题属于NP完备类，求解困难，本文拟采用全局搜索效率高、收敛速度快的遗传算法，并结合广义Powell算法控制其繁殖代数，通过下界算法检验可行解的质量，简称PGA算法。

    在具体的数据实验中，笔者针对单纯的遗传算法作过测试，对相同数据给定相同的遗传操作参数，即初始群体的大小m，交叉概率Pc，变异概率Pm。实验结果显示，由于初始群体的选择是随机的，在100次实验中，存在5-10次不同解的情况，这说明，遗传算法还存在求解不稳定的情况。笔者重新针对不同数据量的数据进行相同参数的实验，实验显示，在取得最优解的遗传后代数这一指标上，大数据量数据和小数据量数据没有明显的差距，也就是说，数据量的大小没有影响到算法的执行速度。两类实验证明，在不确定性选址问题的求解中，单纯的遗传算法，在解的质量和收敛速度上都存在问题。

       PGA算法实际上是一种混合的遗传算法，其目的是改善基本遗传算法的局部搜索能力，进一步提高优化质量和搜索效率，以弥补单一优化方法的某些不足之处。其算法步骤如下:

     (1)确定编码方案。

     (2)计算基本模型的下界，保存此下界为评价指标，评估当前群体的解质量。

     (3)确定群体规模随机产生m个个体，构成初始群体G₀＝[g₁,g₂,…,g_p], 代数为0。

     (4)针对初始群体，执行广义Powell搜索，求得局部最优解。

     (5)选择  针对④求得的局部最优解，计算其个体适应度，根据其个体的适应值从大到小重新排列个体，重排后的个体g₁性能最优，根据排序决定每个个体复制到下一代的概率，其中，k为代数，g(X)为适应度函数。  

 (6)交叉  确定其交叉概率Pc，对新个体依次进行随机选点的部分匹配交叉。

    (7)变异  确定其变异概率Pm，对个体进行位点变异。

    (8)根据(2)所提供的下界来评价当前解。若当前解未达到预定要求，则转入(4)。

    在应用PGA方法时，几个重要的关键因子的确定如下:

    (l)编码与适应度函数

    遗传编码是遗传算法的第一步，对于不确定性选址问题，具体的编码方法是直接以候选位置的随机组合形成解个体，随机运算以解的个数和候选位置为自变量。这种方式能够适

应不确定性选址问题的原始模型。在不确定性选址模型中，问题求解的目标是最小的费用，而遗传算法所求解的是适应度函数的最大值，而且必须是正值。因此必须将目标函数映射成

求最大值的形式。在本文中，适应度函数g（x)=1/s(x)，即取目标函数的倒数作为适应度函数。

 

    (2)交叉方法

    上述采用的编码方法，使得在考虑遗传算法的交叉问题上，不能简单地采用点交叉或多点交叉方法，否则易导致解的极早收敛。有效的方法是对交叉、变异操作进行适当地修正，使其自动适应不确定性选址问题的约束条件。常用的方法有部分匹配交叉、顺序交叉、循环交叉和基于知识的交叉等。一般而言，对于交叉方法的选择应考虑遗传的特点，子串能够部分或全部地继承父串的结构特征和有效基因。交叉概率能控制交叉操作被使用的频度。较大的交叉概率可增强算法开辟新的搜索区域，但易破坏高性能的计算模式；交叉概率太低，算法可能陷入迟钝状态。因此，本算法交叉概率取0.45。

       (3)变异方法

    遗传算法主要通过选择和交叉来完成解的进化过程，变异只是对选择和交叉的功能补充。适应于不确定性选址问题的变异方法有位点变异、逆转变异、对换变异和插入变异等。其中逆转变异的局部优化的精度较高，但由于码串的位置变化较大，计算也就稍显复杂，对换变异是常被采用的变异方法，其计算简单，但局部优化精度稍差。变异的重要目的是维

持群体的多样性。一般而言，低频度的变异可防止群体中重要的、单一基因的丢失，高频度的变异将算法趋于纯粹的随机搜索。在本算法中，取变异概率为0.001。

     (4)选择机制

    以适应度的高低概率来选择群体是遗传算法较常见的选择机制〔3〕，在一定规模的群体中，适应度较高的个体繁殖下一代的概率较大，这符合遗传的适者生存规则。

    对于新一代群体的构成，基本上有四种方式。一是N方式，即全部更换上一代群体的全刷新方式；二是E方式，即保留一个最佳的父串，其余全部更换为最佳保留群体构造方式； 三是G方式，即按比例更新部分个体的部分更新方式；四是B方式，即从产生的子代和父代中挑选最好的个体构成新群体的方式。一般而言，B方式的收敛速度最快，但全局搜索性能最差；N方式相反，全局搜索能力最好，但收敛速度最慢； E方式和B方式的性能介乎两者之间，在不确定性选址问题上，常采用E方式。

    以上介绍了无约束优化问题的求解。对于约束优化问题，可以通过添加惩罚函数或乘子法技术进行转化，使之变为无约束优化问题。具体转化方法，不在此赘述。

3 算例

    以一物流配送网络为例，如表1所示，某公司有5个需求点要使用一种特殊的原材料，计划建造1个或多个仓库，成批存放这种原材料，有4个地方i可供选择，点i建库费用为fi，每吨原材料从i送到需求点的运输费用Cij，求解综合成本最小的仓库设置方案。用PGA法进行运算，进化4代，每代2个个体，最后得优化配送中心为1，2，如表2所示，最终综合费用为47个单位，是全局最优解。而用单纯遗传算法进行迭代至配送中心为2，3时，在各中心配送范围内移动配送中心时不再有综合费用的下降，迭代停止，陷入局部最优解，其最终综合费用为52个单位。相应配送方案如表3，劣于本文提供的PGA方法。

 

 

 

4 结束语

    本文阐述了GIS网络分析中不确定性选址问题的基本模型及特性。从问题的定义可知其为NP完备类问题。推导了最优解在紧条件的下界算法，并结合广义Powell算法及遗传算法，提出了不确定性选址问题的混合遗传算法，实验证明，在最优解的品质和收敛速度上都达到了比较好的效果。同时，实验的结果从另一个角度证明，如果兼顾收敛速度和解的品质这两个指标，单纯的遗传算法未必比其他搜索算法更优越，采用一些局部搜索性能较好的算法结合遗传算法，可以从两方面改善求解效果。

                          参考文献

[l] DU Duan-fu. Operational Theory of Graph[M].Beijing: Beijing Aviation University Press，1990 [杜端甫.运筹图 论[M].北京:北京航空航天大学出版社，1990].

[2]WU Yi，et al. The theory and practice of mathematical Modeling[M]. Changsha: Technical University of Nation Defence Press，1999 [吴诩，等.数学建模的理论与实践 [M].长沙:国防科技大学出版社，1999].

[3] CHEN Guo-liang，et al. Genetic algorithm and its application [M].Beijing: People Post Press，1996[陈国良，等.遗传算法及其应用[M].北京:人民邮电出版社，1996].

 

作者简介:王亚(1974-)男，武汉大学博士研究生，主要研究方向为空间数

据库及空间分析。wangya82@hot-mail.com