基于遗传算法的混合度量维数问题研究

发布时间：2022-12-04 22:35

　　图的度量维数、边度量维数和混合度量维数问题是图论和组合优化研究的重要问题,在货币称重,网络发现和验证,机器人导航,声呐,药物化学等领域有广泛的应用.设G＝（V,E）是一个图,S是顶点集合V的一个非空子集.如果图G中任意两个元素（顶点或边）可以被S中某个顶点区分,那么S称为图G的一个混合度量生成集.含有顶点最少的混合度量生成集的基数称为图G的混合度量维数.求解图的混合度量维数问题在一般情况下是NP-难问题.本文研究简单连通图的混合度量维数问题,设计了遗传算法（GA）,给出了遗传算法在Hamming图、超立方体图和图G□Pm上的应用结果,并分析指出在有些情况下得到的结果就是其混合度量维数. 

【文章页数】：38 页

【学位级别】：硕士

【文章目录】：
中文摘要
英文摘要
引言
第一章 预备知识
    1.1 图的基本概念
    1.2 图的度量维数,边度量维数和混合度量维数
    1.3 遗传算法的基本原理
        1.3.1 编码
        1.3.2 适应度函数
        1.3.3 遗传算子
        1.3.4 参数设定
第二章 图的混合度量维数
    2.1 图的混合度量维数问题
    2.2 遗传算法流程图
    2.3 遗传算法的实现
第三章 一些特殊图的混合度量维数
    3.1 Hamming图的混合度量维数
    3.2 超立方体图的混合度量维数
    3.3 图G□P_m的混合度量维数
结论
参考文献
致谢


【参考文献】：
期刊论文
[1]应用遗传算法设计自动交会控制器[J]. 陈根社，陈新海.  西北工业大学学报. 1994(02)



本文编号：3709114