论文部分内容阅读
随着电信技术的日新月异以及互联网技术的迅速发展,传统电信网(PSTN)、计算机网和广播电视网相互融合已成为国际化的大趋势,在“三网合一”过程中,“两网”融合要先行,也就是首先要实现电信网和计算机网的融合。计算机公话系统正是顺应技术和市场的发展,在向着下一代网络(NGN)方向演进的道路上提出的。计算机公话系统将公话业务与数字网络成功嫁接,在新兴数字网络技术的推动下,从单一的语音业务向着提供语音、数据、图像等多业务方向发展,拓宽了公话业务的空间。
计算机公话系统采用分布式网络结构,其中的任务调度问题,对发挥系统的并行性能和保持负载平衡具有非常重要的意义。由于任务调度问题无法在多项式时间内求得最优解,因而被公认为一个NP完全问题,这也促使人们不断的研究如何设计调度算法,用有限的代价获得更好的解。近年来兴起的遗传算法(GA,GeneticAlgorithm)是一种较好的解决方案,已被广泛用于解决各类NP问题。
本文从提高算法搜索效率的角度,提出了一种分布式遗传算法,该算法在选择、杂交和变异遗传算子的设计方法上都与传统的遗传算法有明显的不同:编码方式采用二维编码,该编码能够自然的表示出任务调度和任务分配的先后关系;杂交方式为内部杂交,即选取三个父本进行轮转杂交,使每一代的搜索范围扩大,从而提高了算法的搜索效率;变异算子在设计方法上采用迁移机制,使得变异后形成的新解仍然是合法解。本文证明了该算法的全局收敛性,并将其应用于解决计算机公话系统任务调度的实际问题中。实验结果表明,该算法在搜索效率和搜索最优解方面与传统遗传算法相比都有了明显的改善,很好的解决了计算机公话系统中的任务分配和任务调度问题,保证了系统运行过程中的稳定性和可靠性。