网络拓扑结构的数学模型及遗传算法

江西电力职业技术学院学报

Journal of Jiangxi Vocational and Technical College of Electricity

Vol.32 No.5Mar.2019

网络拓扑结构的数学模型及遗传算法

侯 杰

（江苏城乡建设职业学院，江苏 常州 213000）

摘 要：网络性能最优，成为网络拓扑结构热点问题。对网络拓扑结构的定义进行了分析，从常见的网络数学模型出发，阐述了遗传算法的发展史，并对遗传算法在网络性能优化方面的应用进行了分析，说明运用遗传算法解决网络拓扑结构问题具有很大的优势。

关键词：数学模型；网络拓扑结构；遗传算法

中图分类号：TP393.03 文献标识码：B 文章编号：1673-0097(2019)05-0066-02

0 引言

一般网络系统中由若干节点及其联系构成，在给定网络信息量、网络终端数目的条件下，如何安排使得网络性能最优，成为网络拓扑结构问题。如何最有效地解决网络拓扑结构问题，就要用到遗传算法进行完整 解答。

1 网络拓扑结构的定义 

“拓扑”一词最早见于几何学，被引用到网络拓扑结构中。本义是研究几何图形在持续转换状态后某些特性维持不变，而网络拓扑则是代表网络状态，或是网络在物理上的联通性。网络拓扑结构是将各种设备与输送媒

［1］

。即在网络中，采用某种方法将各介相连的物理制定

种仪器连接起来，这是一般情况下的概念。网络拓扑结构也繁杂多样。最为常见的有以下几种：环型结构、总线结构、分布式结构、星型结构、蜂窝状结构、网状结构、

［2］

树状结构等。下面将对这些常见网络拓扑结构逐一进行粗略的解释。

环型结构比较常见的是在LAN中的使用。因传输过程中，传输媒体从一端到另一端用户，直至将所有用户连接呈环状而得名。这种结构削弱了用户端对中心系统的依赖性，数据在环路中沿着方向指定传输，信息也从一个节点传往下一个节点。每个节点处均有收发信息功能。各节点通过电缆直线连接，因而总线结构所需电缆在网络拓扑结构中最少。

分布式结构的网络是将计算机整合在不同点的情况下，通过线路互相的连接起来的形式。采用分散控制，即使某一环节出现故障，也不影响整个网络结构，具有较高的可靠性。各节点间可直接构成联系，便于信息共享。比较久远的一种连接方式就是星型结构，它同时也是运用最多、最广的一种网络拓扑设计。在生活中，一般情况下的网络环境，大都被设计成星型结构，我们常用的电话就是采用的星型结构。因每个节点都必须经过中央系统的控制，它有便于集中控制、容易维护等优点，提高了系统的可靠性。

无线局域网间通用的拓扑结构是蜂窝状结构，特征是以无线输送介质点到点或多点输送，适用于各种公

共区域网络。网状拓扑结构使用输送线将各节点进行

结合，每个节点都至少与两个节点以上连接，因呈网状而得名。由于其复杂的结构、高昂的费用，使其不常见于局域网的运用中。树型结构是典型的分级聚合操纵网络。它较星型网络通信结构少，所需费用低，节点扩展简单，但任一节点受损都有可能导致整个网络系统受到影响，因此它的可靠性较低。2 常见网络的数学模型

我们以常见的ATM网络结构为例进行研究。在常用的ATM网络中，DCS网络的上层建筑单元是由电容开关容量构成。我们可以提出一个问题：在网络线路中，增加一些节点和这些节点的连接边，将信息量、终端数目及网络信息量矩阵确定下来，在此基础上确定网络连接方式、终端的信息处理能力、安排信息量矩阵给定的信息量等，使得该网络的性能可以处在一个最佳的状态。这就转化为了一个与网络拓扑结构相关的问题。在分析清楚这一点后，我们就能明确所要解决的问题便是如何获得这个网络拓扑结构。一般而言，我们可以将网络拓扑结构进行简化优化，使之成为一个将网络线路繁忙程度用来描述网络拥堵相关问题的最小化问题。然后构建以下的数学模型。（1）不考虑费用情况下的数学模型：

（2）考虑费用情况下的数学模型：

收稿日期：2019-03-29

作者简介：侯杰（1988-），男，江苏淮安人，讲师，研究方向：随机分析.

第 5 期网络拓扑结构的数学模型及遗传算法67

在确定出两种数学模型后，我们将其转换，则有：

（1）考虑费用的网络拓扑结构:

（2）不考虑费用的网状拓扑结构：

分析式中的信息量，可以列出各种变量间的关系。考虑费用的数学模型属于多目标整数规划，常用解法有有效解法、效用系数法，也叫加权系数法、序列级法。3 遗传算法的背景和历史“遗传算法”一词最早出现于1967年，霍兰德的学生在其博士论文中首次提出。此后，霍兰德便致力于指导学生完成了许多与遗传算法相关的著作。1975，霍兰德标志着遗传算法的正式诞生的著作《自然系统与人工系统的自适应》出版，这是最早的系统论述遗传算法学科的专著，该书较为整体的来阐述了遗传算法的一般理论，并提出了一个重要理论：他认为结构重组遗传操作，是非常重要

的一步［3］

。这一理论对遗传算法今后的发展都产生深远影响，被看作是该学科发展的一个里程碑。

在此时，霍兰德和他的学生将遗传算法中交叉、变异、选择等一些操作进一步优化和完善，使它们变得更加系统和直观。他们的许多理论指导为后来的遗传运算学延续奠定了一个坚实的基础，并一直对后来有着深远的影响。到现在为止，遗传算法的应用早已越过了学术界，被广泛应用到实际社会生活和各种工程运用中。

在现在科学飞速进展的数据社会中，各式学科科学

相互交错、融合、影响，这是近现代科学前进的趋势。遗传算法学科的进展，也正符合了不同学科交叉渗透、相互影响的优势。

遗传算法指的是一种对问题的求解方法，它是用较为简洁的编码技术来构造各式各样或复杂或简单的结构，通过简单的编码操作来达到明确学习搜索的方向的目的。近年来，遗传算法被广泛运用到交通管理运输、金融行业、经济答理、工业技术等诸多方面，比如流水车间调节、可利用性的改善、装置设置、机器调度、作业车间调度、数据挖掘、图像处理等，作用范围相对较宽。4 遗传算法基本理论及应用

遗传算法最早的思想其实是来源于生物学，早在20世纪50年代初，就有科学家尝试在计算机里勾勒系统模型，达尔文提出的“物竞天择，适者生存”这一生物进化论典型论说为遗传算法奠定思想基础，诞生了相关的思想理论。霍兰德提出并创建了系统遗传算法的理论体系。作为一种可以使得大多数复杂问题简化的优化方法，遗传算法一经问世便得到了广泛的应用，渗透到软件技术、图像处理、人工智能、模式识别、机器学习等计算机科学的各个领域。其基本原理就是将单独的集合也就是群体作为对象，使用遗传运算操纵，经过交换、突变、选择使这个作为处理对象的“群体”不断，产生“进化”“演变”，直到它演变成满足条件的最优解。这就是遗传算法的一般构思。

函数优化是遗传算法非常典型的使用实例，也能较为系统全面地对它进行综合性能评价。测试函数各式各样，或简单或复杂，包括但不限于离散函数和连续函数、凹函数和凸函数、孤峰值函数和多峰值函数、效用函数和需求函数等，这些函数都是各具几何特性的，用遗传算法进行简化优化后，更能直观地反映其本质特点。这些复杂的、多模型、多维度的函数求解用一般算法是很麻烦的，可是用遗传算法却能较为简洁地得到准确的结果。

同理，在分析了传统算法网络拓扑结构优化方式后，遗传算法相较而言，更加简化和准确。传统运算多以经验为基础，加以简单计算，降低了网络问题的难度，但其弊端也是容易识别的。其他算法如爬山法、梯度法、列举法，都各有其局限之处。而遗传运算则是以如何使网络投资最小为目标，再进行优化和求解。这点与传统算法和其他算法区别开来，然后获得一个网络投资最小的最优方案。5 结束语

运用遗传算法解决网络拓扑结构问题有着很大的优势，这是大部分传统算法和其他算法都不能比拟的，它可以在一定的搜索区域内高速有效地获得该问题解题步骤，是具有说服力的，且是区别于传统方案中忽略某些因素得出的最优解。可以看出，由信息支撑的许多

网络流动一类问题均可转换为网络拓扑结构

（下转第76页） 76江西电力职业技术学院学报第 32 卷

更加深入地明白文章的主题，使主题得到了升华，让学生的思维得到了扩展和思辨，整堂课就是一种精神享受。3 结束语

语文课是将学生的思维打开，而不是一味地将知识储存。钱梦龙在进行《愚公移山》教学时考虑非常全面，比如巧妙利用问题引导，建构完整的知识体系，教学环节层层递进，激发学生的思辨能力，全程突出以学生为主的教学等。这也是为什么他教的《愚公移山》这门课成为经典课例的原因，这样的导读法不仅是一门技术，而且更是一门艺术！每个教师都会有自己的一套教学方法，但是最终这方法的可行性都是需要从学生的身上得到反馈，最后才能对自己的教学进行合理的调整，而作为教师不能一味地把学生当成试验品进行教学，要学会不断地提升自己，多看经典课例，把从中学到的方法与

自己的教学相结合，找到属于自己的独特教学风格是极

其重要的。而钱梦龙的独特教学风格也是我们作为语文教育者需要深入的挖掘、研究和学习的。

参考文献：

［1］ 中华人民共和国教育部.义务教育语文课程标准(2011年

版［)M］.北京:北京师范大学出版社,2012.

［2］ 姚泓伊.导读法之我见——以钱梦龙执教《愚公移山》为例

［J］.牡丹,2018(17).

［3］ 钱梦龙著,彭尚炯编选.钱梦龙经典课例品读［M］.上海:华

东师范大学出版社,2015.

［4］ 王志芬.引导是一门艺术——钱梦龙《愚公移山》教学片段

赏析［J］.江西教育,2017(35).

［责任编辑 韩翠丽］

（上接第67页）问题来求解。

安电子科技大学,2012.

［3］ 李莉.配电网络拓扑分析与网络重构［D］.南京:南京师范大

学,2011.

参考文献：

［1］ 王琼,夏文云,马晓亮.基于遗传算法的通信系统传输网络

拓扑架构研究［J］.山西电子技术,2018(5):89~92,96.［2］ 李永辉. 面向应用片上网络拓扑生成算法研究［D］.西安:西

［责任编辑 袁 懿］

（上接第69页）加分项。“加分”对于综测排名可能很重要，但识，增长智慧，激发学习兴趣。

对于自己的大学生活和人生，加分真的是最重要的吗？

寻找并坚持自己觉得真正有意义的事情，并享受地去努力，这才是对于我们人生更重要的加分项。5 结束语

第二课堂活动是学校培养人才的重要途径，学校第二课堂活动以学生学习兴趣为切入点，提供有效的学习手段和新颖的活动内容，可以使学生开阔视野，丰富知

参考文献：

［1］ 罗润生“以就业为导向”.高职人才培养体系的构建［J］.教育

学术月刊,2008(7):84~85.

［2］ 刘当远.发挥第二课堂作用 提高人才培养质量［J］.重庆科

技学院学报(社会科学版),2008(2):185~186.

［责任编辑 韩翠丽］

（上接第71页）4 结束语参考文献：

［1］ 王文琴,秦福高.中外合作办学背景下双语课程的设置与教

学改革［J］.计算机教育,2014(11):46~49.

［2］ 孙文高.基于中外合作背景的双语教学课程体系构建分析

［J］.西部素质教育,2016,2(22):57~58.

我国在多年来的中外合作办学探索中，双语教学得到了许多国内外院校的指导和支持，教学资源日益丰富。实践表明，中外办学设置双语课程，弥补了国内外语言教学间的“断层”，为社会培养大批双语应用型人才，为国家落实人才战略打下了坚实基础。

［责任编辑 袁 懿］

（上接第73页） 参考文献：

［1］ 何克抗.从“翻转课堂”的本质,看“翻转课堂”在我国的未来

发展［J］.电化教育研究,2014,35(7):5~16.

［2］ 张学新.对分课堂:大学课堂教学改革的新探索［J］.复旦教

育论坛,2014,12(5):5~10.

［3］ 余清臣,徐苹.当代课堂教学模式改革的实践内涵:一种反

思的视角［J］.教育科学研究,2014(1):15~18.

［4］ 宁建花.融“翻转”“对分”于一体的混合教学模式的构建与

应用［J］.成都师范学院学报,2017,33(10):66~71.

［责任编辑 韩翠丽］