本发明提出了一种基于超启发式算法的智慧城市智能感知终端选址方法，它涉及一种基于超启发式算法的智慧城市智能感知终端选址方法，属于运筹学及选址优化技术领域。
背景技术：
智慧城市的建设与发展，往往与物联网技术密不可分，物联网系统借助各种先进的传感设备，对连接对象的诸如位置、生物、光等信息进行实时采集，传送至互联网，且进行通信与交换，以此来监控、管理、定位与识别连接对象。近年来，信息技术高速发展，为了满足智慧城市中复杂应用场景的需求，往往会在现有标准物联网架构的基础上进行改进，采用具备感知能力，同时也具备强大的计算能力的智能感知终端对信息进行收集、处理、分析和控制，即原始数据的加工、处理、协同等任务不再只依靠云端的软硬件系统，智能感知终端也可承担数据预处理、运算、简单决策等任务。为此，如何高效控制前端传感器，并尽可能降低智能感知终端的建设成本，是智慧城市提高运行效率和服务质量的关键。
智慧城市在建设的过程中，每个应用场景都有其自身的特点，要做到合理配置智能感知终端资源，就需要根据特定场景的约束条件有针对性地进行智慧城市应用场景建模，并设计相应的方法进行求解。目前智慧城市智能感知终端的相关选址方法还很少，不过智慧城市智能感知终端选址问题可以简单地描述为在满足终端计算能力、通信方式、终端体积的应用场景备选终端建设位置中，部署一定数量的智能感知终端，使得所有传感器都与至少一台终端相连，并尽可能满足城市管理者的需求，譬如最小化智能感知终端建设成本。由此可见该选址问题属于一类典型的带复杂约束集合覆盖问题，对于该问题目前的求解方法主要分为两类，一类是采用分支定界和拉格朗日松弛等精确算法进行求解，一类是采用遗传算法、变领域搜索算法等元启发式算法进行求解。这两类方法都有其各自的弊端：
1、精确算法在面对小规模问题时虽然可以保证求得问题的最优解，但是在面对大规模问题时求解时间过长，难以在短时间内获得问题的满意解。
2、元启发式算法通常采用某种固定的搜索框架，并在其中融合特定的局部搜索操作，此类求解算法对算法参数的设置依赖较大，需要根据特定问题精心调整参数才可能获得较好的解。
3、用元启发式算法求解时通常要建立排序模型，根据约束条件确定编解码方式。目前使用元启发式算法求解集合覆盖问题时，大多采用基于行的二进制编码方法，编码串每一位代表一个备选点，若值为1则代表被选中，为0则代表不选，这种编码方式在进行解的更新时会产生大量非法解，导致算法收敛较慢且容易陷入局部最优。
本发明针对以上问题提出一种有效的选址方法。本发明对智慧城市智能感知终端建设过程建立一种选址模型，在此基础上设计一种基于传感器位置的编码方式，进而使用一种超启发式算法对智能感知终端选址问题进行求解，可在较短时间内获得选较优的选址方案，提升智慧城市建设效率，降低建设成本。
技术实现要素：
针对现有技术中存在的缺陷，本发明的目的在于提供一种基于超启发式算法的智慧城市智能感知终端选址方法。本发明基于实际智慧城市应用场景的需求和约束条件建立智能感知终端的选址模型，在此基础上使用一种基于传感器位置的编码方法来表示选址模型的解，进而使用一种超启发式算法对智能感知终端选址问题进行求解。该方法即考虑到智慧城市建设过程中不同场景的实际限制，也考虑到兼顾求解问题的速度和质量，可有效提升智慧城市建设效率，降低建设成本。
为了实现上述目的，本发明所采用的技术方案是：一种基于超启发式算法的智慧城市智能感知终端选址方法，其步骤如下：
步骤a：根据智慧城市应用场景的需求和限制条件建立智能感知终端选址模型；
步骤b：采用基于传感器位置的编码方式生成选址方案的初始解；
步骤c：使用超启发式算法求解获取智能感知终端选址方案；
所述步骤a其具体做法为：根据智慧城市建设需求，收集应用场景的限制条件，包括通电条件、基础通讯设施、可部署终端的位置、可部署终端的空间大小、建设预算、传感器位置等；根据建设实际需要确定选址优化目标；在此基础上，建立智能感知终端选址模型，并得到集合覆盖矩阵，步骤a的具体做法包含以下三个步骤：
步骤a1：收集智慧城市应用场景的限制条件；
步骤a2：明确智能感知终端选址的优化目标；
步骤a3：建立选址优化模型并得到集合覆盖矩阵；
所述步骤a1其具体做法如下：实地调研考察，确认应用场景中是否有电源、电源的位置、具备哪些通讯网络(4g/5g/wifi/lora/rs485)、可部署终端的位置、可部署终端的空间大小、建设预算、传感器位置；
所述步骤a2具体做法如下：根据建设者的实际需求，包括：经费有限、设备数量有限、可靠性要求较高等，确定在进行智能感知终端选址优化时的优化目标；
所述步骤a3具体做法如下：将步骤a1所收集的限制条件转化为数学表达式作为模型的约束条件，将步骤a2所确定的优化目标作为模型的目标函数，得到完整的终端选址优化模型。
m为传感器个数
n为终端部署备选点个数
得到完整的终端选址优化模型：
目标函数：
约束条件：
其中a(j)为终端j可以覆盖的需求点的集合，b(i)为可以覆盖需求点i的终端集合，xj为0-1变量，若在j点布设终端则xj＝1，若没有布设则xj＝0。
在此基础上可得到集合覆盖矩阵a，矩阵的行代表场景中各个传感器，列代表场景中各个智能感知终端，a的元素ai,j为1代表第j个智能感知终端可以与第i个传感器相连，为0则代表不能相连，该矩阵可直观地反映应用场景中的约束条件，选址优化模型的目标就是从列的集合中选出最满足目标函数的子集。
该矩阵可直观地反映应用场景中的约束条件，选址优化模型的目标就是从列的集合中选出最满足目标函数的子集。
所述步骤b具体做法为：采用基于传感器位置的编码方法随机生成p个初始的解(即选址方案)，p可以根据实际情况进行调节，且必须大于0；p作为步骤c中算法的初始种群，并计算各个解对应的目标函数值。基于传感器位置的编码方式是指，每一个解的编码串长度等于传感器的总数，编码串的每一位代表一个传感器，这一位的数值代表哪一个智能感知终端与该传感器相连。
所述步骤c具体做法为：将步骤b中生成的p个初始的解作为初始种群，利用超启发式算法进行求解获得较优的选址方案。所述“超启发式算法”是本发明设计的一种智能优化算法，算法整体框架可分为策略域和问题域，策略域中的个体是由多个启发式操作构成的操作序列，所有的策略域个体构成策略域种群，问题域中的个体对应选址问题的解，所有问题域个体构成问题域种群，策略域个体数量与问题域相同，策略域个体的优劣由个体评价值决定，一个策略域个体评价值的计算方式为：使用组成该个体的所有启发式操作依次更新问题域个体，每次操作更新完获得一个新问题域个体，若该问题域个体目标函数值优于旧解，则该策略域个体评价值加1(初始值均为0)。该步骤的具体做法包含以下6个步骤：
步骤c1：初始化策略域，获得策略域种群old_pop；
步骤c2：使用old_pop中的个体所代表的操作来更新问题域中的解，同时获得old_pop中每个个体的评价值；
步骤c3：对old_pop中的每个个体进行扰动操作获得新的策略域种群new_pop；
步骤c4：使用new_pop中的个体所代表的操作来更新问题域中的解，若得到的新解目标函数值优于旧解目标函数值则将之替换，进而得到new_pop中每个个体的评价值；
步骤c5：将old_pop和new_pop合并进行保优操作，得到的种群作为新的old_pop；
步骤c6：判断是否达到迭代终止条件，若达到则输出问题域中目标函数值最优的解作为最终选址方案，若没达到则执行步骤c3。
所述步骤c1具体做法如下：随机生成p个策略域个体作为策略域种群old_pop，每个个体是一个长度为6的编码，编码每一位的数字代表一种启发式操作，共有4种启发式操作，用于对问题域个体进行更新，以问题域个体t1举例，分别是:
①两点交叉操作，随机从问题域中选择一个个体t2与t1进行两点交叉形成新解tnew，两点交叉是指在编码串长度范围内随机选择两个点位a和b，t1点位a到b的值作为tnew点位a到b的值，t2a到b之外点位的值作为tnew对应点位的值；
②优先保存交叉操作，随机生成0-1序列c，t1将c中为1的点位的值作为tnew对应点位的值，t2将c中为0的点位的值作为tnew对应点位的值；
③随机变异操作，随机选择t1中n个点位，将点位上的值随机变为满足问题约束条件的值，形成新解tnew；
④贪心迭代操作，随机选择t1中1个点位，将点位上的值随机变为满足问题约束条件的值，形成新解tnew，下次若对该解进行相同操作时，依然选择这个点位进行调整，且不再调整为已试过的值，直到满足该点位的值都试过才会更换点位；
所述步骤c2具体做法如下：依次使用old_pop中的个体来对问题域中的个体进行更新，策略域个体1更新问题域个体1，策略域个体2更新问题域个体2，以此类推。更新时，以问题域个体t1和策略域个体h1举例，依次使用h1中的启发式操作更新t1，每个操作进行m次,m可以根据实际情况进行调节，且必须大于0；每次获得一个新问题域个体，若目标函数值优于旧解，则h1评价值加1(初始值均为0)；
所述步骤c3具体做法如下：使用扰动操作来更新old_pop中的每个个体，获得新的策略域种群new_pop，扰动操作包含随机插入和随机变换，每次使用扰动时随机选择一种启发式操作进行更新，以策略域个体h1举例①随机插入，是指随机选择h1的一个点位a，然后随机选择另一个点位b，若a>b将a上的值插入到点位b之前，若a<b将b上的值插入到点位a之前，形成新策略域个体②随机变换，是指随机选择h1的一个点位a，将该点位的值变为随机变为另外一种启发式操作编号；
所述步骤c5其具体做法如下：将old_pop和new_pop合并，根据每个个体的评价值进行排序，将其中评价值最高的前p个个体作为新的old_pop。
与现有技术相比，本发明具有如下的有益效果：
1.目前智慧城市智能感知终端的相关选址方法还很少，然而智能感知终端是智慧城市物联网架构中至关重要的一环，本发明创新性地根据应用场景的实际限制条件和建设需求，将智慧城市智能感知终端选址问题抽象为一个带复杂约束的集合覆盖问题进行求解，可以通过设置优化目标函数更加合理地部署智能感知终端，提高智慧城市的运行效率和资源利用率；
2.本发明在求解时采用一种基于传感器位置的编码方式，并根据编码特定设计了4种启发式操作，确保在进行解的更新时不会产生非法解，大大提高了算法的整体搜索效率，有助于获得更优的选址方案；
3.传统求解算法要么面对大规模问题时求解缓慢，无法应对智慧城市种具有大量传感器的应用场景，要么算法搜索质量严重依赖于参数设置，通用性较差。而本发明所设计的超启发式算法可以在可接受时间内获得问题的满意解，对参数依赖性也较小，在面对不同问题实例时具有较强的通用性。
综上，这种基于超启发式算法的智慧城市智能感知终端选址方法能在实际中提高智能感知终端选址的合理性，为智慧城市的建设提供很好的支撑。
附图说明
图1是本发明所述方法整体流程图；
图2是本发明所述基于传感器位置的编码方式的示意图(6个传感器8个终端布设备选点)；
图3是本发明所述超启发式算法策略域个体的示意图；
图4是本发明所述基于超启发式算法对智慧城市智能感知终端选址问题目标函数进行求解的流程图。
具体实施方式
下面结合附图说明及具体实施方式对本发明进一步说明。
本发明实施以某市a的智慧消防应用场景下智能感知终端部署为例，阐述本发明方法。具体来说，该市某场馆约有50个不同的传感器(一氧化碳浓度检测、二氧化碳浓度检测、温湿度检测、烟雾检测、电压检测等)用于采集前端数据，每个智能感知终端的成本和体积都一样，但都需要wi-fi无线网络和电源接入，场馆内满足要求的终端部署备选点约有20个，现需要结合已有的限制条件，考虑如何以最少的智能感知终端连接控制所有的传感器，并确定最终部署选址方案。如图1所示，其步骤如下：
步骤a：根据智慧城市应用场景的需求和限制条件建立智能感知终端选址模型；
步骤b：采用基于传感器位置的编码方式生成选址方案的初始解；
步骤c：使用超启发式算法求解获取智能感知终端选址方案。
所述步骤a的具体作法包含以下三个步骤：
步骤a1：收集智慧城市应用场景的限制条件：实地调研考察，确认该场馆中是否有电源、电源的具体位置、具备哪些通讯网络(4g/5g/wifi/lora/rs485)、可部署终端的位置、可部署终端的空间大小、建设预算、传感器位置；
步骤a2：明确智能感知终端选址的优化目标：根据建设者的实际需求(譬如经费有限、设备数量有限、可靠性要求较高等)确定在进行智能感知终端选址优化时的优化目标为最小化智能感知终端使用量；
步骤a3：建立选址优化模型并得到集合覆盖矩阵。将步骤a1所收集的限制条件转化为数学表达式作为模型的约束条件，将步骤a2所确定的优化目标作为模型的目标函数，得到完整的终端选址优化模型：
目标函数：
约束条件：
其中a(j)为终端j可以覆盖的需求点的集合，b(i)为可以覆盖需求点i的终端集合，xj为0-1变量，若在j点布设终端则xj＝1，若没有布设则xj＝0。
在此基础上可得到集合覆盖矩阵a，矩阵的行代表场景中各个传感器，列代表场景中各个智能感知终端，a的元素ai,j为1代表第j个智能感知终端可以与第i个传感器相连，为0则代表不能相连，下图是6个传感器8个终端备选点的简单示意：
该矩阵可直观地反映应用场景中的约束条件，选址优化模型的目标就是从列的集合中选出最满足目标函数的子集。
步骤b：采用基于传感器位置的编码方法随机生成50个初始的解(即选址方案)作为步骤c中算法的初始种群，并计算各个解对应的目标函数值。基于传感器位置的编码方式是指，每一个解的编码串长度等于传感器的总数，编码串的每一位代表一个传感器，这一位的数值代表哪一个智能感知终端与该传感器相连，6个传感器8个终端备选点的编码示意如图2所示。
步骤c：将步骤b中生成的50个初始的解作为初始解，利用超启发式算法进行求解获得较优的选址方案。
步骤c1：随机生成50个策略域个体作为策略域种群old_pop，每个个体是一个长度为6的编码，编码每一位的数字代表一种启发式操作，共有4种启发式操作，用于对问题域个体进行更新；
步骤c2：依次使用old_pop中的个体来对问题域中的个体进行更新，策略域个体1更新问题域个体1，策略域个体2更新问题域个体2，以此类推。更新时，以问题域个体t1和策略域个体h1举例，依次使用h1中的启发式操作更新t1，每个操作进行30次，每获得一个新问题域个体，若目标函数值优于旧解，则h1评价值加1(初始值均为0)；
步骤c3：使用扰动操作来更新old_pop中的每个个体，获得新的策略域种群new_pop，扰动操作包含随机插入和随机变换，每次使用扰动时随机选择一种操作进行更新，以策略域个体h1举例①随机插入，是指随机选择h1的一个点位a，然后随机选择另一个点位b，若a>b将a上的值插入到点位b之前，若a<b将b上的值插入到点位a之前，形成新策略域个体②随机变换，是指随机选择h1的一个点位a，将该点位的值变为随机变为另外一种启发式操作编号；
步骤c4：使用new_pop中的个体所代表的操作来更新问题域中的解，若得到的新解目标函数值优于旧解目标函数值则将之替换，进而得到new_pop中每个个体的评价值；
步骤c5：将old_pop和new_pop合并，根据每个个体的评价值进行排序，将其中评价值最高的前50个个体作为新的old_pop。
本发明未详细阐述部分属于本领域公知技术。
以上所述，仅为本发明部分具体实施方式，但本发明的保护范围并不局限于此，任何熟悉本领域的人员在本发明揭露的技术范围内，可轻易想到的变化或替换，都应涵盖在本发明的保护范围之内。
1.一种基于超启发式算法的智慧城市智能感知终端选址方法其步骤如下：
步骤a：根据智慧城市应用场景的需求和限制条件建立智能感知终端选址模型；
步骤b：采用基于传感器位置的编码方式生成选址方案的初始解；
步骤c：使用超启发式算法求解获取智能感知终端选址方案；
所述步骤a的具体做法包含以下三个步骤：
步骤a1：收集智慧城市应用场景的限制条件；
步骤a2：明确智能感知终端选址的优化目标；
步骤a3：建立选址优化模型并得到集合覆盖矩阵；
所述步骤c的具体做法包含以下六个步骤：
步骤c1：初始化策略域，获得策略域种群old_pop；
步骤c2：使用old_pop中的个体所代表的操作来更新问题域中的解，同时获得old_pop中每个个体的评价值；
步骤c3：对old_pop中的每个个体进行扰动操作获得新的策略域种群new_pop；
步骤c4：使用new_pop中的个体所代表的操作来更新问题域中的解，若得到的新解目标函数值优于旧解目标函数值则将之替换，进而得到new_pop中每个个体的评价值；
步骤c5：将old_pop和new_pop合并进行保优操作，得到的种群作为新的old_pop；
步骤c6：判断是否达到迭代终止条件，若达到则输出问题域中目标函数值最优的解作为最终选址方案，若没达到则执行步骤c3。
2.根据权利要求1所述的一种基于超启发式算法的智慧城市智能感知终端选址方法，其特征在于所述的步骤a3：具体做法如下：将步骤a1所收集的限制条件转化为数学表达式作为模型的约束条件，将步骤a2所确定的优化目标作为模型的目标函数，得到完整的终端选址优化模型，在此基础上可得到集合覆盖矩阵a，矩阵的行代表场景中各个传感器，列代表场景中各个智能感知终端，a的元素ai,j为1代表第j个智能感知终端可以与第i个传感器相连，为0则代表不能相连，该矩阵可直观地反映应用场景中的约束条件。
3.根据权利要求1或2所述的一种基于超启发式算法的智慧城市智能感知终端选址方法，其特征在于所述步骤b具体做法为：采用基于传感器位置的编码方法随机生成p个初始的解作为步骤c中算法的初始种群，并计算各个解对应的目标函数值。
4.根据权利要求1或2所述的一种基于超启发式算法的智慧城市智能感知终端选址方法，其特征在于所述步骤c具体做法为：将步骤b中生成的p个初始的解作为初始种群，利用超启发式算法进行求解获得较优的选址方案；所述超启发式算法整体框架可分为策略域和问题域。
5.根据权利要求1或2所述的一种基于超启发式算法的智慧城市智能感知终端选址方法，其特征在于所述步骤c具体做法如下：随机生成p个策略域个体作为策略域种群old_pop，每个个体是一个长度为6的编码，编码每一位的数字代表一种启发式操作，共有4种启发式操作，用于对问题域个体进行更新。
6.根据权利要求5所述的一种基于超启发式算法的智慧城市智能感知终端选址方法，其特征在于所述4种启发式操作包括：①两点交叉操作，②优先保存交叉操作，③随机变异操作，④贪心迭代操作。
7.根据权利要求1或2所述的一种基于超启发式算法的智慧城市智能感知终端选址方法，其特征在于所述步骤c2具体做法如下：依次使用old_pop中的个体来对问题域中的个体进行更新，策略域个体1更新问题域个体1，策略域个体2更新问题域个体2，以此类推，每个操作进行m次，每次得一个新问题域个体，若目标函数值优于旧解，则策略域个体评价值加1。
8.根据权利要求1或2所述的一种基于超启发式算法的智慧城市智能感知终端选址方法，其特征在于所述步骤c3其具体做法如下：使用扰动操作来更新old_pop中的每个个体，获得新的策略域种群new_pop，扰动操作包含随机插入和随机变换，每次使用扰动时随机选择一种启发式操作进行更新。
9.根据权利要求1或2所述的一种基于超启发式算法的智慧城市智能感知终端选址方法，其特征在于所述步骤c5具体做法如下：将old_pop和new_pop合并，根据每个个体的评价值进行排序，将其中评价值最高的前p个个体作为新的old_pop。
10.根据权利要求2所述的一种基于超启发式算法的智慧城市智能感知终端选址方法，其特征在于所述目标函数，步骤a1所收集的限制条件表达式如下：
目标函数：
约束条件：
其中m为传感器个数，n为终端部署备选点个数，a(j)为终端j可以覆盖的需求点的集合，b(i)为可以覆盖需求点i的终端集合，xj为0-1变量，若在j点布设终端则xj＝1，若没有布设则xj＝0。
技术总结