求解最小双连通支配集问题的变邻域禁忌搜索算法

针对经典NP难优化问题——最小双连通支配集问题,提出了一种元启发式求解算法——变邻域禁忌搜索算法。算法将原优化问题的求解转换为一系列判定问题——k双连通支配集问题的求解,使用两种邻域结构更加有效地覆盖解空间,同时使用扰动及禁忌机制帮助算法跳出局部最优陷阱。通过与现有文献中的精确算法、启发式算法在国际文献公开的38个双连通图算例上的实验对比,结果表明变邻域禁忌搜索算法能够有效求解最小双连通支配集问题,可求得所有公开算例的最优解,并且在稠密图中计算效率明显优先于其他算法。

禁忌遗传算法求解最小支配集

如何寻找一个网络图的最小支配集是NP难题。分别设计了逆序启发式算法和禁忌搜索算法,并在此基础上提出了禁忌遗传算法(TSGA)用于求解最小支配集;将禁忌搜索和遗传算法结合起来,弥补了彼此的不足,既有效地避免了算法易陷入局部最优解的缺陷,又加快了算法的收敛速度。经对大量随机网络图的测试和对物流网络选址问题的求解,验证了TSGA算法的优越性。

基于人工蜂群算法的环网方向保护配合最小断点集计算

在对复杂环网方向保护进行整定计算时,确定其最优配合顺序的核心步骤就是求解最小断点集(MBPS)。将MBPS的求解问题转化为一个0-1整数规划问题。引入最大独立断点集的概念,改进目标函数。运用人工蜂群算法对模型进行求解,并对算法进行了改进,将禁忌搜索引入人工蜂群算法,进而减少了算法所需迭代的次数,并能通过一次计算就得到多组MBPS。通过算例验证方法的正确性。

最小控制集问题的群集策略智能算法研究

图的最小控制集是一个经典的NP完全问题,其广泛应用在生物信息学、计算机通讯、工程设计等方面。目前搜索最小控制集算法有多种,例如:贪心算法、模拟退火算法、基于禁忌搜索的模拟退火算法等。当搜索结构复杂的多点图时,很多算法的搜索效果并不好。为了提高搜索效果,提出并实现一种群集策略智能算法;同时还对群集策略算法进行了非常重要的扰动改进。为了验证算法的搜索效果,利用Petersen图和随机图完成了对群集策略算法的搜索测试实验;同时也完成了对群集策略算法、贪心算法、基于禁忌搜索的模拟退火算法的比较测试实验,通过实验结果也验证了群集策略算法搜索效果最好。

MMPC-Tabu混合算法的贝叶斯网络模型在高脂血症相关因素研究中的应用

目的本研究采用MMPC-Tabu混合算法构建山西省高脂血症的贝叶斯网络模型,研究高脂血症及其相关因素间的网络关系及相关程度,并通过贝叶斯网络对高脂血症进行患病风险推理,为慢病影响因素分析提供更合理的建模方法。方法采用logistic回归对山西省18岁以上居民高脂血症的调查数据进行变量初步筛选,再以MMPC-Tabu混合算法和极大似然估计法构建贝叶斯网络。结果2013年山西省高脂血症患病率为42.6%(95%CI:41.1%~44.1%)。将logistic回归初筛与高脂血症有关的9个变量,采用MMPC-Tabu算法构建高脂血症的贝叶斯网络模型,结果显示:中心性肥胖和BMI与高脂血症直接相关,是高脂血症的父节点,即它们与高脂血症的发生有关;高血压、身体活动、性别、年龄、地区、糖尿病通过影响中心性肥胖和BMI间接影响高脂血症的发生。结论贝叶斯网络可以反映因素与疾病整体联动效应,揭示高脂血症直接和间接相关的因素和关联强度,同时阐明除高脂血症以外的其他影响因素间的关系,可为慢性病与相关因素的研究提供合理的方法。

基于图论的电力系统PMU布点优化算法

基于最小支配集理论和电力系统线性量测模型,提出了可观测节点集合、WAMS可观测矩阵两个概念以及一种新的节点可观测性计算规则。以保证系统的完全可观测性和以系统图的最小支配集为搜索范围构成约束条件,以电力系统状态完全可观测和相量测量装置(PMU)配置数目最小为目标,形成了PMU配置优化问题。并应用禁忌搜索(TS)方法求解该问题,保证了全局寻优。最后采用IEEE14、30、57、118节点系统和新英格兰39节点系统对该方法进行了验证,仿真结果表明该方法的有效性和可行性。