遗传算法在计算机网络中的应用

丁 玲，范 平，闻 彬

（湖北科技学院计算机科学与技术学院,430074）

1 计算机的发展

社会是一个发展的过程，人类所使用的计算工具也是不断地更新和发展，例如计算工具就相继出现了算盘、计算尺、手摇机械计算机、电动机械计算机等。在1946年，美国发明了世界上第一台电子数字计算机，从此人类的计算工程发生了天翻地覆的变化。人们接着研究出了第二代计算机，这类计算机和第一代计算机相比有了很大的改进。接着是第三代计算机，这类计算机主要是以中、小规模集成电路作为电子器件，并且出现了操作系统，功能也是越来越强。第四代计算机机1970年以后采用的。这种计算机不仅运算速度比从前提高了不少，而且已经开始用于生活中的各种运算，性能已经是大幅度提高。我们现在所用的基本上都是第五代计算机。如果说前面几代计算机只是性能上的提高，那么第五代计算机可以说是从根本概念上有所突破，它彻底突破了以前的传统——冯·诺依曼机器的概念，第五代计算机实现了计算的高度统一，彻底改变人类的命运。

2 遗传算法的定义

遗传算法是一种借鉴生物界的进化规律演化而来的随机化搜索方法。它不同于一般的算法是它是直接对结构对象进行操作的。内在隐蔽性比较好而且相比之下有更好地全局寻优能力；并且这种算法是采取概率化的寻优方法，它主要的特点就是可以自动获取和指导优化的搜索空间，并且可以自动调整，不需要人为地来制定一些规则。

从遗传算法的定义中我们可以看出，遗传算法在搜索的时候是采用整体搜索策略和优化搜索方法的，所以它在计算的时候并不需要依赖于梯度信息或者别的辅助知识；它需要的只是一个目标函数，一个能影响搜索方向的函数和一些相适应的函数。正式遗传算法有这些优点，所以它的应用范围比较广泛，通常不需要确定具体的问题，它几乎可以用于任何领域，只要满足遗传算法的一些条件就可以了。比如说遗传算法就常用于函数的优化和组合优化。

3 遗传算法的重要性

前面简单的介绍了一下什么是遗传算法，那么遗传算法为什么会如此重要，应用为什么会如此广泛呢，这跟遗传算法的特征是密不可分的。一般的算法有可能从问题的单个解开始，但是遗传算法是从问题解的串集开始搜索，这就体现了遗传算法比传统算法的先进之处，传统的优化算法一般都是从单个初始值的迭代开始求最优解的，这样算法有一个很明显的缺点就是不能考虑到全局。而遗传算法就可以很好地考虑全局，全面有效的选择选择最优解。遗传算法在处理问题的时候会同时处理群体中的多个个体，这样也是为了避免传统优化算法的误区，避免陷入局部最优解，同时能实现算法本身的并行化。遗传算法的最大特点其实是它基本上不用搜索空间的知识和其他的一些辅助信息，而仅用适应度函数值来评估个体，在此基础上进行遗传操作。这种适应度函数可以不受连续可微的约束，而且它的定义域也是不受约束的，可以任意设定。遗传算法的这个特点使得遗传算法在应用中得到广泛使用。遗传算法是借鉴生物界的进化规律来模拟运算的，所以这种算法一般是不用确定一个特定的计算规律，而是根据概率的变迁规则来指导算法的搜索方向。等等一系列的特点使得遗传算法在计算机网络中应用得以如此广泛。

4 遗传算法在计算机网络中的应用

4.1 遗传算法在计算机网络优化设计中的应用

在一般的计算机网络优化设计中，有两个很重要的问题就是各条线路的容量分配和各个节点间的路由选择。如果一个算法中，网络拓扑结构和交换量都给定了，那么我们怎么确定各条链路的容量大小和选择各节点间的最佳路由呢？怎么样才能减小成本，并且可以保证质量，满足用户的需求呢？这就是我们需要考虑的问题。通常在传统的算法情况下我们遇到这种多条件限制的问题时通常都会先确定一个条件不变去考虑另外一个条件，然后在确定另外一个条件不变来考虑原来的条件。比如传统的算法就是先确定路由然后考虑容量分配问题，或者是先确定容量分配然后在考虑路由量。但是在这种计算机网络优化中，我们这样做是不太合适的，因为路由的选择和链容量的选择是确定相关的，因此最佳的方案是同时考虑这两个问题。我们可以看出来显然这是一个多约束条件的复杂非线性规划问题，对于这种问题，我们可以以遗传算法为基础，设计出一种遗传寻优算法。通过计算机遗传算实例表明这种算法可以算出近似最优解，而且精度比较高。

优化设计中的数学模型

在计算机网络中，中间节点一般会采用一种“存储转发”方式工作。通常节点处理都是需要时间的，比如本算法中的节点处理和链路处理都是需要时间的，但是由于这种处理的时间非常短，而且也不便测量，所以我们在计算的时候通常就是忽略这两种时延不计，仅仅考虑等待时延。在这种估算的情况下我们可以采用排队模型来处理，就是采用“先来先服务”规则。

4.2 遗传算法在计算机网络可靠度优化计算中的应用

计算机网络技术的迅速发展及其在各个领域中的应用的普及，致使网络用户节点不断增加网络规模日渐壮大，人们对网络的应用也在不断加强。现在全世界计算机普及率已经很高了，我们可以看出计算机的使用量在当今的这个社会是如此庞大。计算机有它的优点，其中人们就是利用了计算机便于储存信息的特点来储存大量的信息，很多重要的资料都存在计算机中。但是一旦计算机网络系统出现故障那么给人们带来的损失也将是非常惨重的，甚至是无法估计的。所以计算机是否可靠，我们又怎么样来提高计算机的可靠性呢？在降低计算机网络成本的同时提高计算机网络的可靠性是人们一直追求的问题。在传统求解方法对于这一复杂优化NP难题，人们通常显得力不从心，针对这一现象，本段提出了用于计算机网络可靠度优化计算的遗传算法，并且用实例实现了算法的执行过程。这种问题都可以转化成数学模型来做，但是由于模型比较复杂在这里就不做赘述了。当然遗传算法在计算机网络中的应用还不止这些，比如说在计算机网络划分优化用的应用，遗传算法在计算机网络划分应用中可以实现自动网络划分的目的，实验结果表明这种划分是可行并且有效地。还有就是遗传算法在计算机通信网容量分配和流量控制中的应用。

4.3 遗传算法在计算机辅助创新作曲中的应用

现代科技越来越发达了，而且历史也证明很多新的科学都是在不同领域学科的交叉点上完成的。上个世纪七十年代出现了一种新的音乐叫做“电脑音乐”就是音乐技术与信息科学技术所产生的交叉科学。近几年来电脑音乐已经取得了较大的进步和发展，也产生了很多的效果。比如说电子乐器，还有各种音频信号压缩等技术。许多采用遗传算法规律的算法都是采用基于实例的随机算法来处理算法的过程。遗传算法的核心就是根据生物进化规则来进行优胜劣汰的，它也是通过计算机创造染色体的方式来模拟生物进化法则从而算出结果来的。遗传算法在音乐方面的作用已经得到了充分的证实，但是也还是存在着许多问题。任然需要不断地改进。

5 结束语

进入90年代以来，遗传算法可以说是迎来了它的兴旺时期，这时候遗传算法得到了广泛的应用，无论是在理论研究领域还是在科学应用领域都得到了很大的应用。其中尤其是遗传算法的应用，人们更是不断地研究。而且利用遗传算法进行优化和规则学习的能力也是显著提高，同时遗传算法也应用于产业应用方面。遗传算法可以说已经涉及到现代科技发展的各个领域，在不同的领域都有着广泛的应用。随着科技的发展遗传算法的研究出现了几个新的方向特别引人注目，分别是：遗传算法的机器学习，遗传算法在不同学科中的交叉综合，前面所说的遗传算法在音乐中的应用就是一个很好地例子。还有就是遗传算法在人工生命方面的研究。总之遗传算法是一种新的科学运算规则，它在当今社会的很多领域都得到了广泛的应用，而且具有很多优点。但是遗传算法也还是有不足之处的。比如说遗传算法在效率上就比一般的传统优化算法低，这是因为遗传算法从全局考虑的原因。遗传算法的精度、可行度、计算复杂性等方面相比传统算法来说就缺少一种有效的定量分析方法。

［1］ 张顺颐，基于遗传算法利用网络时延解决路由问题的心算法[J]；通信学报，1999.20（12）:31-37

［2］ 孙力娟，吴新余.应用遗传算法求解计算机通信网的最佳路由——一种新的遍历匹配选择法[J]；南京邮电学院学报，1996,16（2）：26-28