面向设施配置空间优化的量子进化算法及软件

成果编号：32523

价格：面议

完成单位：南京邮电大学

单位类别：其他高校

完成时间：2022年

成熟程度：其他

服务产业领域：其他

我要对接关注发送消息

发布人：zhouxinxin 离线

发送消息

设施配置空间优化旨在形成设施空间布局和调度的规划方案，是以地理信息为研究基础，以运筹建模为方法内核，以城市规划为应用导向的交叉研究问题，是一种典型高维多峰NP-Hard组合优化问题。设计并改进设施配置空间优化算法对提升规划方案适应度具有重要价值。通过剖析设施配置空间优化基本特征，引入实数编码量子进化算法，并重点构造四倍体量子染色体编码算子、总量约束算子，形成面向设施配置空间优化的量子进化算法（Quantum evolutionary algorithm for spatial optimization of facility allocation，QEA-SOFA）。基于急救设施配置空间优化实例分析，QEA-SOFA算法可有效提升急救服务设施重定位优化公平性，较实数编码遗传算法提高66%。结果表明QEA-SOFA算法在高维多峰空间优化问题上全局搜索能力更强，且对空间异质区域局部搜索具有更大探测尺度，也揭示了量子进化机制在地理空间优化问题中的巨大潜力。

1928 次浏览分享到

成果介绍

科技计划：国家级：

成果形式：新技术

合作方式：技术开发、技术咨询、技术服务

参与活动：首届江苏产学研合作对接大会

专利情况：未申请专利

成果简介

综合介绍

创新要点

以有容量约束的离散型服务设施选址为设施配置基础模型，目标函数R(t)可为最小化/最大化代价函数（例如：最小化通行时间、最大化公平性），讨论并设计基于实数编码的量子进化算法，提出面向设施配置空间优化的量子进化算法（Quantum evolutionary algorithm for spatial optimization of facility allocation, QEA-SOFA）。主框架与经典量子进化算法保持一致，包含“种群生成-种群进化-种群评价”，在编码结构、量子变异、离散交叉等算子上改进。首先是编码：提出一种四倍体量子染色体编码方式，染色体同时记录数值、两种量子比特态、是否更新标记状态量。四倍体量子染色体编码避免繁琐的编码和解码过程，提升了个体信息的保持，适用于存在条件约束的设施配置空间优化问题，其优势在于染色体长度大幅缩短、进化效率提升、量子比特通过量子逻辑门算子更新旋转得到更多样化的候选解。四倍体量子编码染色体较之前研究中的三倍体量子编码染色体加入了无效变异标记符g_j^t，g_j^t的初始值均为0，记录量子变异的有效性次数，用于控制个体的量子变异循环停止条件。其次是总量约束算子：基于四倍体量子染色体编码，在调整单个个体容量的同时，增加同步调整逻辑，完成对β_rj^t，α_rj^t调整，形成传导过程。总量约束算子主体分为个体初始化、初步调平和精细调平3部分。然后是量子变异算子：量子变异算子设计旨在模拟量子坍塌观测操作，直接采用三角函数变换更新模拟观测。最后是量子交叉算子：QEA-SOFA算法中的量子交叉算子采用离散交叉模式，迭代一定代数τ_c之后，实施一次四倍体量子染色体之间的交叉操作，具体交叉方式如下：首先对种群P(t)={q_1^t,q_2^t,…,q_r^t…,q_L^t }，评价适应度，得到适应度集合R(t)。然后对R(t)进行适应度排序，选取一定数量的、排名靠前的优秀个体，作为临时父代。最后，从临时父代中随机抽取q_u^t和q_v^t，实施多点交叉，交换被随机抽取的多点基因位的值，得到交叉后的新个体q_u^(t+1)和q_v^(t+1)。

技术指标

选取实数编码遗传算法（Real-coding Genetic Algorithm，RCGA）为对照组，并以Ackley和Griewank函数为标准测试函数，优化目标为求解全局最小值。Ackley和Griewank函数维度设定为100维，且存在上下边界，2个测试函数的理论最优值均为0。QEA-SOFA算法与RCGA算法参数设置一致，变异概率设置为0.05，交叉概率为0.66，种群规模为200个，进化代数为2000代，染色体长度为100；QEA-SOFA算法的特有参数设置，变化幅度初始值，学习率设置为0.05。实验分2组对比场景，场景1是无约束条件场景，场景2是有约束条件场景（具体约束条件为总量约束和整数编码约束，Ackley函数的总量约束参数E_setting设置为500，上边界UP设置为10，下边界BOTTOM设置为1；Griewank函数的总量约束参数设置为1000，上边界UP设置为50，下边界BOTTOM设置为1）。

其他说明

完成人信息

姓名：对接成功后可查看

所在部门：对接成功后可查看

职务：对接成功后可查看

职称：对接成功后可查看

手机：对接成功后可查看

E-mail：对接成功后可查看

电话：对接成功后可查看

传真：对接成功后可查看

邮编：对接成功后可查看

通讯地址：对接成功后可查看

联系人信息