[0033] 在父染色体中寻找与母染色体交换部分中光纤链路相同的链路,并与父染色体交换部分对应地完成交换;
[0034] 在母染色体中寻找与父染色体交换部分中光纤链路相同的链路,并与母染色体交换部分对应地完成交换。
[0035] 优选地,所述将所述每组新的光纤链路序列以预设概率进行变异,生成子代种群,并将当前种群中个体适应度最大的染色体存放至备选集合中包括:
[0036] 将每组新的光纤链路序列中的一条光纤链路以预设概率随机与另一条光纤链路进行顺序的交换,完成变异,生成子代种群。
[0037] 本发明还提供了一种超低损耗光纤升级的装置,包括:
[0038] 编码模块,用于将光纤链路序列编码为染色体,所述光纤链路序列中的每条光纤链路作为染色体上的基因;
[0039] 基因库建立模块,用于建立基因库,所述基因库中的基因包括原光网络中的所有光纤链路;
[0040] 种群初始化模块,用于将所述基因库中的基因随机排序,生成n组不同的染色体,作为初始种群;
[0041] 父辈选择模块,用于计算当前种群中所有个体的个体适应度,根据所述个体适应度选择父辈,所述个体适应度为每个光纤链路序列进行超低损耗光纤升级后为光网络带来的性能增益;
[0042] 交叉模块,用于随机选择所述父辈中的两个个体作为父母染色体进行交叉,生成两组新的光纤链路序列,并重复该步骤直至生成n组新的光纤链路序列;
[0043] 变异模块,用于将所述每组新的光纤链路序列以预设概率进行变异,生成子代种群,并将当前种群中个体适应度最大的染色体存放至备选集合中;
[0044] 解码模块,用于判断所述子代种群的代数是否小于预设最大迭代次数,若不小于,则选取当前备选集合中个体适应度最大的染色体解码,得到光网络中超低损耗光纤升级的最优顺序。
[0045] 本发明还提供了一种超低损耗光纤升级的设备,包括:
[0046] 存储器,用于存储计算机程序;处理器,用于执行所述计算机程序时实现上述一种超低损耗光纤升级方法的步骤。
[0047] 本发明还提供了一种计算机可读存储介质,所述计算机可读存储介质上存储有计算机程序,所述计算机程序被处理器执行时实现上述一种超低损耗光纤升级方法的步骤。
[0048] 本发明的上述技术方案相比现有技术具有以下优点:
[0049] 本发明以基因算法为基础,主要研究超低损耗光纤在弹性光网络中的升级策略。将链路升级序列编码为染色体基因序列,通过交叉、变异、选择等过程进行迭代,最终选择出整体网络性能最好的链路升级序列,基因算法中的变异即为等位基因替换引起的基因结构的变化,其目的使保证群体的多样性,防止最终结果为局部最优解。本发明从提升整体网络性能出发,通过计算迭代后不同的链路升级序列所产生的增益,找到产生最大增益的序列。同时由于找到的升级序列是在固定成本下所产生增益最大的升级序列,所以很好的解决了现有技术成本高的缺点。此外,由于采用基因算法,该发明相比于现有的技术更加简单易懂,迭代速度更快,误差也相对较小。
附图说明
[0050] 为了使本发明的内容更容易被清楚的理解,下面根据本发明的具体实施例并结合附图,对本发明作进一步详细的说明,其中:
[0051] 图1是基于模拟退火算法升级策略示意图;
[0052] 图2是本发明超低损耗光纤升级方法的实现流程图;
[0053] 图3是14节点的光网络网络结构图;
[0054] 图4是种群数量100,迭代次数20次的仿真结果;
[0055] 图5是种群数量100,迭代次数30次的仿真结果;
[0056] 图6是种群数量100,迭代次数40次的仿真结果;
[0057] 图7是于链路升级最大增益策略的仿真结果;
[0058] 图8为本发明实施例提供的一种超低损耗光纤升级的装置的结构框图。
具体实施方式
[0059] 本发明的核心是提供一种超低损耗光纤升级方法、装置、设备及计算机存储介质,降低了成本、误差和算法复杂度。
[0060] 为了使本技术领域的人员更好地理解本发明方案,下面结合附图和具体实施方式对本发明作进一步的详细说明。显然,所描述的实施例仅仅是本发明一部分实施例,而不是全部的实施例。基于本发明中的实施例,本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例,都属于本发明保护的范围。
[0061] 基因算法属于启发式搜索算法,是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型,是一种通过模拟自然进化过程搜索最优解的方法。该算法通过数学的方式,将问题的求解过程转换成类似生物进化中的染色体基因的交叉、变异等过程。本发明采用编程语言Java编写代码,将基因算法应用于超低损耗光纤的升级中,整体实现思路如图2所示,具体操作步骤如下:
[0062] S101:将光纤链路序列编码为染色体,所述光纤链路序列中的每条光纤链路作为染色体上的基因;
[0063] 编码实际上是一种转换方法,通过某种方式将一个问题转化为另一个问题。在本发明中,由于我们要寻求最优的光纤链路升级顺序,因此研究对象即为光纤链路的升级序列。所以,本技术将光纤链路序列作为基因序列,即为生物学中的染色体,将光纤链路序列长度作为染色体长度,将序列中的每条光纤链路作为染色体上的基因。
[0064] S102:建立基因库,所述基因库中的基因包括原光网络中的所有光纤链路;
[0065] 所述基因库中的基因还包括光网络中所有节点之间,符合新拉超低损耗光纤原则的新建光纤链路。
[0066] 在本发明中,光纤链路分为两类,一类是光网络中原本存在的旧的光纤链路,另一类为新建的超低损耗光纤链路,即直接在光网络中的节点之间新拉超低损耗光纤,其长度即为两节点间的物理长度。此处要注意新拉超低损耗光纤的原则,即光不能在存在旧光纤链路的两个节点之间新拉超低损耗纤,也不能使新拉的超低损耗光纤与光网络中现存的旧的光纤链路相交叉。因此染色体上的基因应该是从原光网络中的所有光纤链路和所有光网络中节点之间可能存在的新建的光纤链路之中随机选取的。至此完成编码操作,将寻找最优的光纤链路升级顺序问题转化为生物学中的遗传问题。
[0067] S103:将所述基因库中的基因随机排序,生成n组不同的染色体,作为初始种群;
[0068] 种群是进化的基本单位,后续的交叉、变异、选择等操作都是在种群内进行的。而同一种群的所有生物共用一个基因库,而在本发明中,基因库对应着原光网络中的所有光纤链路和所有光网络中节点之间可能存在的新建的光纤链路。因此,为了后续操作的进行,我们选择采用随机排序的方式对光纤链路进行排序,生成100组光纤链路序列,作为初始种群,这也就完成了种群的初始化操作。同时,随机排序的操作也保证了种群的多样性,使结果更具有说服力。
[0069] S104:计算当前种群中所有个体的个体适应度,根据所述个体适应度选择父辈,所述个体适应度为每个光纤链路序列进行超低损耗光纤升级后为光网络带来的性能增益;
[0070] S105:随机选择所述父辈中的两个个体作为父母染色体进行交叉,生成两组新的光纤链路序列,并重复该步骤直至生成n组新的光纤链路序列;
[0071] S106:将所述每组新的光纤链路序列以预设概率进行变异,生成子代种群,并将当前种群中个体适应度最大的染色体存放至备选集合中;
[0072] S107:判断所述子代种群的代数是否小于预设最大迭代次数,若不小于,则选取当前备选集合中个体适应度最大的染色体解码,得到光网络中超低损耗光纤升级的最优顺序。
[0073] 若所述子代种群的代数不小于预设最大迭代次数,则将所述子代种群更新为当前种群,并重复步骤S104‑S107。
[0074] 通过上述选择、交叉、变异操作后,新一代更适应环境的种群就此产生。此时判断该种群的代数是否小于最大迭代次数。若此代种群的代数小于最大迭代次数,则重新计算新的个体适应度,通过计算出的新的个体的适应再对其重新进行选择、交叉、变异操作,如此循环,直至种群的代数已达到最大迭代次数,则跳出循环。同时在迭代的过程中不断比较每一代中的最好个体适应度,从而在迭代结束后能够找到所有代中个体适应度最大的染色体,即为升级后增益最大的光纤链路序列,进行后续解码操作。
[0075] 解码为编码的反过程,即将算法迭代后找到的个体适应度最大的染色体还原为光纤链路序列,该序列即为基因算法最终求解出的光网络中超低损耗光纤升级的最优顺序。逐条判断解码后的光纤链路序列中的光纤链路,若为原光网络中旧的光纤链路,则升级为超低损耗光纤链路,若为新建光纤链路,则在两节点间新拉超低损耗光纤。直到成本所支持的能够升级的链路达到最大为止。这样也保证了固定成本下整体网络性能提升的最大化。
至此,本发明基于基因算法成功地得到了超低损耗光纤在弹性光网络中的最优升级策略。
[0076] 基于以上实施例,本实施例对步骤S104‑S106进行进一步详细说明:
[0077] 采用轮盘赌算法选择i个个体作为所述父辈,其中各个体的选择概率与其个体适应度值成比例。传统的选择往往是依照优胜劣汰的原则,根据所计算出的个体的适应度,按照好坏顺序进行排列,选择其中适应度好的个体作为父辈来繁衍后代。而在本发明中,为了增加严谨性和减少误差,采用轮盘赌算法进行选择操作。轮盘赌算法是最简单也是最常用的选择方法,在该方法中,各个个体的选择概率和其适应度值成比例,适应度越大,选中概率也越大,就像进行转盘游戏一样。在计算出个体适应度即性能增益后,根据增益的大小可以让每个光纤链路序列以相应的概率被选为可以进行遗传操作的个体,从而完成选择操作。
[0078] 随机生成两个数a,b且a
[0079] 将每组新的光纤链路序列中的一条光纤链路以预设概率随机与另一条光纤链路进行顺序的交换,完成变异,生成子代种群。基因算法中的变异即为等位基因替换引起的基因结构的变化,其目的使保证群体的多样性,防止最终结果为局部最优解。在本发明中,以0.01的概率对种群进行基因突变,即种群中每个染色体有0.01的概率发生基因突变。若发生基因突变,其变异的基因位数为不超过光纤链路序列长度的随机数。理论上,基因突变为某个基因突变为基因库中随机另一基因,即某个链路变为光网络中随机另一条链路。但是考虑到光网络中不可能存在两个相同的链路,所以在这里采取另一种变异思路,即将光纤链路序列中的一条链路与随机另一条链路进行顺序的交换,从而完成变异操作。将变异后的所有光纤链路序列存入新的集合中,作为子代种群集合。至此完成一次遗传操作。
[0080] 首先,该发明能够区别于现有技术的地方就在于其考虑了在光网络的节点间直接新拉超低损耗光纤的情况,而非仅仅考虑对光网络中旧的光纤链路进行升级。考虑到直接新拉超低损耗光纤相比与对旧的光纤链路升级往往会为光网络带来更高的整体网络性能增益,因此该发明会使最终计算出的链路升级策略的性能相比于现有技术更加优越。
[0081] 其次,由于基因算法的整体搜索策略和优化搜索方法在计算时不依赖于梯度信息或其它辅助知识,而只需要影响搜索方向的目标函数和相应的适应度函数,所以遗传算法提供了一种求解复杂系统问题的通用框架,它不依赖于问题的具体领域,对问题的种类有很强的普适性,所以能够很好地应用于弹性光网络中超低损耗光纤的升级问题。并且根据技术实施结果显示,利用基因算法求解出的链路升级序列对整体网络性能的增益比当下广泛应用的基于链路升级最大增益策略所求解出的链路升级序列的增益高了接近2000。
[0082] 同时,利用达尔文生物进化论的自然选择和遗传学机理的生物进化过程,让结果始终朝着最优解前进。其中,选择操作让本发明在求解过程中始终放弃的都是增益低的链路升级序列。交叉操作在基因算法中起核心作用,通过交叉,基因算法的搜索能力得以飞跃提高,重复的交叉操作让本发明能够大范围搜索找到最优解。变异操作则维持了基因算法的群体多样性,以防止最后的结果陷入局部最优解中。
[0083] 此外,本发明相比于现有技术,由于使用了基因算法,从而让本技术方案能够做到既易于让人理解也极大的减少了运算复杂度。此外相比于其他技术,该技术方案能够在相同的成本下得到优于其他技术的结果,极大的减少了成本。
[0084] 基于以上实施例,本实施例为了验证本发明的可行性,基于技术方案,利用java编程语言编写程序仿真实施过程,具体如下:
[0085] 选取一个14节点的光网络作为待升级的网络,其网络结构图如如图3所示;
[0086] 其中,0—13为网络中的14个节点,节点间连线为待升级的光纤链路,其上的数字为链路的物理长度。如节点0和节点1之间的链路可以表示为N0‑N1,其物理长度为260。同理可以表示出其他所有链路。
[0087] 为了减少误差,使本发明更具有说服力,分别以100种群20代,100种群30代,100种群40代为例进行具体说明,同时变异概率均设置为0.01,可供升级的光纤链路长度均设置为所有链路总长度的80%。
[0088] 将种群数量设置为100,迭代次数设置为20次,然后利用事先编写好的程序运行,最终可以得到如图4所示的结果。其中,链路N4‑N5到链路N10‑N11为算法最终求解出的最优链路升级序列,而这个序列最后存在于第20代(geneI=0为第1代,因此geneI=19为第20代)的种群中。y为此序列能够为整体网络性能带来的增益,由图可知增益为22040,而对应的x的值为144。此处的x为光纤升级序列的频隙数,它的大小与增益呈负相关,频隙数越小,增益越大。此外,程序还计算出了一些其他参数,如最差个体适应度,平均适应度和种群适应度等。
[0089] 将种群数量设置为100,迭代次数设置为30次,同样利用事先编写好的程序运行,最终可以得到如图5所示的结果。其中,链路N4‑N5到链路N8‑N12为算法最终求解出的最优链路升级序列,而这个序列最后存在于第30代(geneI=0为第1代,因此geneI=29为第30代)的种群中。由图可知增益为22230,而对应的频隙数为143。与种群数量100,迭代次数20次得到的结果相比,我们可以看出,随着迭代次数的增加,程序找到了更优的结果。该光纤升级序列有着更小的频隙数和更大的增益,同时即使在最差个体适应度变得更差的情况下,算法仍找到了平均适应度和种群适应度更高的种群。因此不难看出种群数量100,迭代次数20次得到的结果为局部最优解,但是我们也不能断定种群数量100,迭代次数30次得到的结果为全局最优解,因此需要加大迭代次数进行进一步验证。
[0090] 将种群数量设置为100,迭代次数加大到40次,同样利用事先编写好的程序运行,最终可以得到如图6所示的结果。其中,链路N4‑N5到链路N6‑N7为算法最终求解出的最优链路升级序列,而这个序列最后存在于第40代(geneI=0为第1代,因此geneI=39为第40代)的种群中。由图可知增益为22230,而对应的频隙数为143。与种群数量100,迭代次数30次得到的结果相比,即使迭代次数的增加,程序并未找到增益最大的结果。事实上为了使结果更加严谨,我们将迭代次数逐步增加至50、60、70,均得到了相同的结果,在这里就不再赘述具体过程。因此可以判断频隙数为143,增益为22230的结果为全局最优解。但是不难发现即使增益相同,最终得到的链路升级顺序也不完全相同,事实上不同的链路升级顺序是可以带来相同的增益的,因此全局最优的链路升级顺序不唯一。
[0091] 为了使本发明的实施结果更具有说服力,在这里选择与当下较为常用的基于链路升级最大增益策略进行对比,与本发明相似,该策略同样可以使用java编写程序,仿真实施过程。因此采取与本发明实施过程所使用的完全一样的14节点光网络,同样将可供升级的光纤链路长度设置为所有链路总长度的80%进行仿真,得到的结果如图7所示,由图可知,链路N10‑N11到链路N2‑N5为算法最终求解出的最优链路升级序列,频隙数为152,对应的整体网络增益为20520。由此我们可以发现该技术求解出的链路升级序列其增益甚至比种群数量100,迭代次数20次得到的局部最优解的增益还要低,而本发明求解出的最优链路升级顺序对光网络整体性能的增益则比该策略求解出的增益高了接近2000。因此可以看出本发明相比于其他现有方法的优越性。
[0092] 请参考图8,图8为本发明实施例提供的一种超低损耗光纤升级的装置的结构框图;具体装置可以包括:
[0093] 编码模块,用于将光纤链路序列编码为染色体,所述光纤链路序列中的每条光纤链路作为染色体上的基因;
[0094] 编码模块100,用于将光纤链路序列编码为染色体,所述光纤链路序列中的每条光纤链路作为染色体上的基因;
[0095] 基因库建立模块200,用于建立基因库,所述基因库中的基因包括原光网络中的所有光纤链路;
[0096] 种群初始化模块300,用于将所述基因库中的基因随机排序,生成n组不同的染色体,作为初始种群;
[0097] 父辈选择模块400,用于计算当前种群中所有个体的个体适应度,根据所述个体适应度选择父辈,所述个体适应度为每个光纤链路序列进行超低损耗光纤升级后为光网络带来的性能增益;
[0098] 交叉模块500,用于随机选择所述父辈中的两个个体作为父母染色体进行交叉,生成两组新的光纤链路序列,并重复该步骤直至生成n组新的光纤链路序列;
[0099] 变异模块600,用于将所述每组新的光纤链路序列以预设概率进行变异,生成子代种群,并将当前种群中个体适应度最大的染色体存放至备选集合中;
[0100] 解码模块700,用于判断所述子代种群的代数是否小于预设最大迭代次数,若不小于,则选取当前备选集合中个体适应度最大的染色体解码,得到光网络中超低损耗光纤升级的最优顺序。
[0101] 本实施例的基于机器视觉的表面缺陷检测装置用于实现前述的超低损耗光纤升级方法,因此超低损耗光纤升级装置中的具体实施方式可见前文超低损耗光纤升级方法的实施例部分,例如,编码模块100,基因库建立模块200,种群初始化模块300,父辈选择模块400,交叉模块500,变异模块600,解码模块700,分别用于实现上述超低损耗光纤升级方法中步骤S101,S102,S103,S104,S105,S106和S107,所以,其具体实施方式可以参照相应的各个部分实施例的描述,在此不再赘述。
[0102] 本发明具体实施例还提供了一种超低损耗光纤升级的设备,包括:存储器,用于存储计算机程序;处理器,用于执行所述计算机程序时实现上述一种超低损耗光纤升级方法的步骤。
[0103] 本发明具体实施例还提供了一种计算机可读存储介质,所述计算机可读存储介质上存储有计算机程序,所述计算机程序被处理器执行时实现上述一种超低损耗光纤升级方法的步骤。
[0104] 本领域内的技术人员应明白,本申请的实施例可提供为方法、系统、或计算机程序产品。因此,本申请可采用完全硬件实施例、完全软件实施例、或结合软件和硬件方面的实施例的形式。而且,本申请可采用在一个或多个其中包含有计算机可用程序代码的计算机可用存储介质(包括但不限于磁盘存储器、CD‑ROM、光学存储器等)上实施的计算机程序产品的形式。
[0105] 本申请是参照根据本申请实施例的方法、设备(系统)、和计算机程序产品的流程图和/或方框图来描述的。应理解可由计算机程序指令实现流程图和/或方框图中的每一流程和/或方框、以及流程图和/或方框图中的流程和/或方框的结合。可提供这些计算机程序指令到通用计算机、专用计算机、嵌入式处理机或其他可编程数据处理设备的处理器以产生一个机器,使得通过计算机或其他可编程数据处理设备的处理器执行的指令产生用于实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能的装置。
[0106] 这些计算机程序指令也可存储在能引导计算机或其他可编程数据处理设备以特定方式工作的计算机可读存储器中,使得存储在该计算机可读存储器中的指令产生包括指令装置的制造品,该指令装置实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能。
[0107] 这些计算机程序指令也可装载到计算机或其他可编程数据处理设备上,使得在计算机或其他可编程设备上执行一系列操作步骤以产生计算机实现的处理,从而在计算机或其他可编程设备上执行的指令提供用于实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能的步骤。
[0108] 显然,上述实施例仅仅是为清楚地说明所作的举例,并非对实施方式的限定。对于所属领域的普通技术人员来说,在上述说明的基础上还可以做出其它不同形式变化或变动。这里无需也无法对所有的实施方式予以穷举。而由此所引伸出的显而易见的变化或变动仍处于本发明创造的保护范围之中。