论文部分内容阅读
演化计算是计算机模拟大自然的演化过程，特别是生物的进化过程，来求解复杂问题的一类计算模型。由于演化计算具有自组织、自学习、自适应的智能特征和简单、通用、鲁棒性强、适于并行处理等优点，因此在组合优化、数据挖掘、工程优化等领域得到了广泛的应用。基于近年来逐渐丰富和完善的演化计算理论，本文对组和学中的两类经典组合优化问题TSP问题和SAT问题的求解进行了一定的探索，设计出性能更好的新算法用于求解这两类NP难问题。此外，本文还分别探讨了演化计算在数据挖掘领域用来搜索分类规则和在卫星通信领域用来解决信道分配与优化问题，通过提出一些新思想，新方法，使用演化算法有效地解决了这两个问题，从而展示了演化计算强大的搜索与优化能力。关于TSP问题，本文设计了新的演化算子，并通过增加一些控制策略，提出一种改进的郭涛算法(IGT)，加速了郭涛算法的收敛速度。继而基于IGT算法提出一种分布式演化算法，能对大规模TSP问题进行有效求解，此外，还提出了演化算法的一种新的并行机制，并进行了有效性分析。数值实验表明，IGT算法能有效求解中小规模的TSP问题，分布式IGT算法采用一定数量的并行进程以后能对大规模TSP问题进行有效求解。关于SAT问题，在演化算法中引入了一种用于跳出局部陷阱的拟人策略，并通过对杂交和变异算子的改良设计，提出一种求解SAT问题的快速的演化算法(SAT-IEA)，该方法不仅具有演化算法的全局收敛性质，而且具有一定的并行性、继承性。数值实验表明，对于随机产生的3-SAT测试实例和SATLIB库中的部分测试实例，采用该算法在求解速度、成功率和求解问题的规模等方面的性能都明显优于一般的演化算法，和另一种快速的求解算法Solar算法性能相当。关于数据挖掘中的分类问题，通过设计新的适应函数、初始化群体的优化、增加新的演化算子以及采用新的淘汰策略等对原始基因表达式程序设计方法进行改进，提出新的基因表达式程序设计方法。数值实验表明，将新方法用于数据挖掘中进行分类规则的挖掘，其精度要好于传统方法。关于动态信道分配问题，将中国36小区的卫星动态信道分配问题进行建模，提炼出该类问题的一个数学模型，并在理论上对其进行了分析，证明该类问题可以转化为图着色问题，从而为该类问题的求解指明了新的方向。针对中国36小区的卫星动态信道分配问题，提出了三种求解策略：演化算法、确定算法和两种算法相结合的混合算法。数值实验表明，对于中国36小区的动态信道分配问题，混合算法求解质量好，且时间性能良好。