英语原文共 9 页，剩余内容已隐藏，支付完成后下载完整资料
通过遗传算法实现给定的网络连接稳定性的最优化
摘要
稳定性是系统能否实现它的设计目的最重要的方法之一，并且在算数上是一个系统能在一个给定的最短周期内完美地运行的可能。当一个系统被一个连接的网络节点和链接所描述时，系统的稳定性变成一个困难的网络设计问题，它的解决方案在科学和工程上有重要的实际利益。这篇文章将讨论使用遗传算法找到在给定的节点和链接当中最可靠的数学方案。对于一个给定的网络拓扑结构，稳定性是用邻接矩阵计算。对于搜索所有可能的被节点和链接所连接的拓扑空间，遗传算子，例如：变异和交叉，被通过一个字符串的形式应用到邻接矩阵当中。在图表环境当中，当交叉和子图的转变相符时，遗传算法的字符串的突变和图片重新搭线相符。对于最可靠的网络能被全面搜索找到的小型网络，遗传算法非常的高效。对于大型网络，我们的研究结果，不仅说明了我们的遗传算法的高效，并且意味着最可靠的网络有着高度的对称性。
- 介绍
对于实现一个系统的设计目的来说，提高网络各个组成部分和它们连接的稳定性，是一个很重要的措施，这为系统在一个给定的最短周期内完美运行提供了可能。当然，系统的稳定性既依赖于节点的稳定性，也依赖于节点的连接方式。因此，我们可以通过多种方式提高系统的稳定性。提高各个节点连接的稳定性方法中，最简单的就是将并联冗杂用于链接。然而，用这种方法提高系统稳定性将耗费更多的资源，因此我们需要一个实现系统稳定性和资源消耗平衡的更优方案。如果我们假设相同的节点稳定性，我们能通过对节点连接方式进行合理选择提高稳定性。第二方案意在找到在所有网络，i.e.，全部节点连接的可能方式的全部拓扑当中找到最稳定的网络。这是一个关于网络设计的数学难题，它的解决方案提供了供全世界网络结构及其相关的许多全球应用的参考，例如：电信，计算机网络，污水下水道系统，石油和天然气管道。事实上，网络稳定性在科学和工程上的重要性也能在近几十年间有关稳定性的专业杂志上证实，例如：IEEE Transaction on Reliability。在统计物理学当中，我们可以把网络设计问题和复杂网络的渗透过程联系起来。如果我们随机地将两边设为“打开”或者“关上”。那么，有关各种结果的形式的性质的研究是一个关于渗透的话题。记住这个，我们的网络设计问题和网络可靠性的键渗流问题有关。
在网络设计当中，各种方式已经被尝试过了。其中，最近的一种是将网络稳定性问题看做是网络电阻，在发现稳定性于网络电阻负相关后（小的网络电阻对应高稳定性）。我们可以指出一个链接在网络电阻移动后的改变的方面十分重要，以便能够找到方法来保护那些移动后可以将网络电阻最大化的链接。通过联合这些移动后网络电阻最小的链接和减少移动后网络电阻最大的链接，我们能提高网络的稳定性。另一种方法是从流行病学的方面考虑网络稳定性。在这些工作当中，我们找到的最优的解决方案是，使用遗传算法是一个解决网络稳定性这一复杂数学问题的实用方案。
我们引入第二部分关于稳定性和数字化使用遗传算法来解决最优约束的一个叫做“全部终端”的概念。在第三部分我们将介绍一个在给定的网络中计算稳定性的方法。为了有一个供比较的基准，我们可靠性制成表格，最可靠的网络是通过在第四部分全面搜索小节点得到的。第五部分是主要部分，在这部分我们主要讨论用遗传算法找最稳定的拓扑结构的方法。然后，在第六部分，我们比较全部搜索的遗传算法的表现和完成我们算法的时间。有关更大网络的更多结果，在第七部分，我们会和对称性在图形网络稳定性的中的重要性一起展示。
- 问题阐述
我们着重于那些假定系统由节点和准确提供的连接它们的链接的系统的网络设计。在任何两个节点当中，有1或者0的连接。在这里，我们假设每一个网络链接有相同的稳定性，给定一个链接正常工作的概率参数p（q=1-p,为链接不工作）。这个p被称为健壮性参数。这一健壮性参数和键渗流开放概率p一样，我们假设每一个网络链接，被随机的分配“开放”或者“关闭” 并且链接开放的概率为p。
我们根据在签名理论建立好的框架当中分析网络的稳定性。在稳定性方面系统的成功意味着每一对组元（在网络语言当中的节点），有至少一条路径连接着它们（叫做路径连接）。系统的稳定性因此是一个给定健壮性参数为p的，系统工作成功概率R。在外行来说，网络稳定性是指每一个节点能和任意一个其他节点连接的概率。这一对系统稳定性的描述，我们叫做“全部终端”稳定性，它要求网络由每一个单独连接的节点组成。还其他的测量稳定性的方法，像两个终端稳定性，或者在流行病学中使用的“罹患率”稳定性。在“全部终端”稳定性方面，网络稳定性问题的最优化是和以下的问题等效：给定节点和链接，找到最稳定的拓扑。在这篇文章，我们假设我们的网络是最简单的，无向的，未加权的网络。如果我们的网络是全部连接的，那么就有Lmax = N(N-1)/2 个链接。另一方面一个由N个节点组成的连接网络至少需要N-1个链接，这就是一个树状拓扑结构。因此一个一般的有N个节点的网络，其链接数是在N-1和N(N -1) / 2之间的。网络的关联性由rho;==L/Lmax=2L/（N(N-1)）定义。在给定节点链接的条件下，这个网络设计问题是为了在C（**）多种可能的图形当中找到最稳定的一个。我们可以看到，结果空间非常大，并且我们网络链接的稳定性问题，是一个非常难的组合最优化问题。此外，当不是常规的方案或者平行结构时，对给定的网络稳定性的评估，是非常困难的，因为它依赖于健壮性参数和网络的拓扑结构。在Moore和Shannon的著名工作后，我们知道，在健壮性参数中互联网的稳定性可以由多项式表示。对于一个给定的拓扑网络，系统稳定性的工作是一个单调的，包括一个像Fremi功能一样的健壮性参数功能。当p=0时网络稳定性为0，当p=1时网络稳定性为1.在这篇文章中，我们假设健壮性参数p设定为0.7，在我们给定的数字化稳定性模仿中。我们的关注点在网络拓扑。
一般来说，我们期待的通过全面搜索来找大型N节点网络的最稳定网络是不可计算的。因此，我们把目标设定在算法层面，来数字化地找最稳定网络。希望从我们的数字化工作当中，我们在最稳定拓扑结构当中的一般特征方面可以有一些顿悟。我们的目的是设计一个遗传算法来找到给定大型节点和链接当中的最稳定网络。
- 稳定性评估
在我们寻找最好的有关稳定性的拓扑当中之前，我们需要评估一个给定健壮性参数p和一个拓扑结构的网络稳定性R。因为我们注重于最简单的，无向的，未加权的，在两节点之间无多余链接的网络，我们可以把这些描述成带有特殊邻接矩阵的拓扑。最初，所有的节点被标记成从1到N，邻接矩阵A,是一个N*N的矩阵，并且在项Aij当中，如果节点i和j连接，则项Aij=1,否则为0。这个矩阵表示在估算网络数字性的稳定性工作当中非常地实用，当我们把健壮性参数包含在网络当中时。为了估算邻接矩阵A和健壮性参数p的稳定性，我们在运算法则1中介绍一个随机矩阵A rand来计算使用Monte Carlo Method得到的A的稳定性R=（p;N,L）。
Algorithm 1 Evaluate network reliability for a given
matrix A with a given robustness
n_exp: = number of experiment n_success:= 0
for n = from 1 to n_exp do
let Arand be a random Ntimes;N matrix whose entries are
random number in the interval [0,1]
if the ijth entries of Arand is smaller than p and the
corresponding ijth of A is 1
then let the ijth entries of Arand be 1
else let the ijth entries of Arand be 0
if Arand is connected
then let n_success = n_success 1
end for
R = n_success/n_exp
在这个算法当中，我们需要核实带有邻接矩阵的网络是否被连接，换句话说，它的连接路径。An的第ij个项是连接节点i,j的路径长度的数字。因此，当An的i,j项是0时，没有连接节点i,j的路径长度，并且我们称，节点ij不由长度为n的路径连接。如果节点ij对于所有的n的可能值（n取1,2,3hellip;hellip;N，两个节点之间的最大路径为N）都不由长度为n的路径连接，那么我们称节点ij之间无路径连接。数学上，这意味着，当第ij项对于所有的Ai，i从1到N，都为0的话，那么ij无路径连接。节点ij之间的路径的数量都由以下的矩阵给定，I是一个N*N的单位矩阵。
为了核实网络是否连接，我们通过算法二核实路径连接。
在使用算法二来核实A在算法1当中是否连接，我们可以完成路径1 当中的所有步骤，并获得给定的网络A中的稳定性。注意网络稳定性评估包含随机的错误。这些错误可以被增长的实验次数所减少，n_exp。
在这两种算法当中，我们看到稳定性的评估消耗了大量的计算资源。
- 穷举搜索
一个关于我们遗传算法的关键步骤既在于产生一个新的网络，这个网络在评估计算当中形成一个“染色体”，也在于评估它的真实性，这是适应性功能的评估。为了获得在遗传算法当中的完美运行，我们需要把未知结果和穷举搜索进行比较。
这一当N=4，5，6并对应不同L的穷举搜索结果在图表1中显示出来。键渗流被设置为0.7，n_exp为1000。
然而，穷举搜索要求搜索全部的可能网络，当我们注意到介绍当中有N个节点，L个链接的所有可能网络的空间有种可能结果或步骤，它的顺序是，网络的连接性系数。我们可以看到，对于大型N节点和非平凡连接来说，这是一个天文数字，这让穷举搜索在实际当中不可能实现。（注意到0连接的平凡情况，网络中没有链接并且不能变的稳定，当链接性为1时，网络总是稳定的）因此，我们规定自己首先比较小型的和中型的网络连接。
- 遗传算法
这里会介绍一种用遗传算法搜索图片的方法。我们的遗传算法在搜索最稳定网络方面将在算法4中介绍。这一适当措施是网络稳定性。
每个候选网络都是一个种群中的一个染色体。我们选择网络稳定性最高的最合适的方案，并且通过三种方式改变种群中的其他网络：遗传重组，突变和染色体交叉互换。在我们的遗传算法中，终止条件决定算法的输出质量。当N为大型时，我们不知道确定解的信息，我们使用以下终止条件：当终止条件不改变n_tor的生成时，算法将会终止。这里，我们通过增加n_tor 来增加输出质量。
5.1遗传表示
网络通过邻接矩阵表示对网络稳定性的评估十分有效，但它在实现遗传算法时并不有效，染色体是一个线性的。这里我们首先介绍一个从邻接矩阵到字符串的映射。一开始，邻接矩阵的上三角项被从第一行开始到最后一行逐行标记。由于我们只处理无定向网络它们相关的矩阵只在独立项在N*N的邻接矩阵当中对称。这就意味着上三角矩阵A，如果被按顺序逐行标记，它就对应一个长度为Lmax的二进制字符串。这个项的长表示要么是0要么是1.比如，图一的网络能被二进制字符串1001111101代替。然而如果我们只关注网络链接，那么在字符串长度Lmax当中，我们可以看到有L种可能是1剩下的Lmax-L种是0.因此，我们可以通过使用更短的字符串长度L简化字符串长度，所以网络由唯一的一
全文共14540字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[13682]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
