遗传算法是一类借鉴生物界自然选择和遗传机制的自适应全局优化随机搜索算法。遗传算法直接对结构对象进行操作,不存在函数可微性和连续性的限定,具有全局性,鲁棒性和隐并行性等优越性。 神经网络是对人脑的信息处理方式进行模拟的产物。1982年,Hopfield提出离散神经网络模型并将其成功应用于组合优化问题。至今应用最为广泛的神经网络BP网络不仅具有强大的非线性映射能力,可以实现非常复杂的因果关系,而且具有自适应、自学习和高容错性等优良特性。 布局问题是运筹学的一个重要分支,属于复杂的组合优化问题。20世纪70年代以来的研究表明,求解NPC问题不存在既完整严格又不太慢的求解算法。因此遗传算法和神经网络便理所当然地成了解决组合优化问题并在速度和精度之间寻求平衡的工具。但将二者结合用于布局问题的研究还很少见到,这方面课题有待进一步研究,也具有一定的现实意义。 本文主要内容如下: 1.构造了同构不干涉布局化算法。给出一个已知不干涉布局方案,该算法可以保证产生的布局方案与已知布局方案同构。 2.回顾遗传算法的理论和应用研究方面的进展,定义了新的变异算子。给出了保持图元邻接关系的方法,构造了同构布局等价类的改进遗传算法。该算法不但能保证图元的邻接关系不变,并且能以较快的收敛速度搜索到全局最优布局方案。 3.将神经网络应用到布局问题中,给出了布局问题的前向网络。结合遗传算法,构造了布局子问题的遗传神经网络算法。给出一组合理的训练样本,该算法能较快地训练出适合的权值和阈值,并且能稳定地收敛到较优的布局方案。数值试验表明该算法是有效可行。