基于细胞自动机的协同演化优化方法

摘要

细胞自动机是当前计算机科学的一个研究热点。细胞自动机本质上是一个时间离散化、空间离散化的动力学系统。它所具有的极度并行性、基本单元的简单性、细胞相互作用的局部性等特点引起众多学科的学者们越来越多的关注。
　　 当前在最优化领域，不断出现一些超大规模的非线性问题，由于这些问题的复杂性、强约束性、非线性、不确定性、建模困难，使得这类问题难于解答。针对这类问题的特点，用具有智能特性的优化方法在求解这类问题时能表现出较好的性能。目前广泛应用的智能优化算法有遗传算法、模拟退火算法、神经网络等，但这些算法的实现模式都还是基于串行模式。假如我们利用细胞自动机来解决优化问题，也就意味着能够建立极度并行的解决最优化问题的程序。未来的超级计算机具有每秒千万亿次甚至万万亿次浮点计算能力，这类计算机的一种可能的体系结构是基于细胞自动机的架构，为了适应未来的超级计算机结构，本文尝试探讨将演化算法与细胞自动机相结合，研究一类基于细胞自动机的演化算法，以充分发挥计算机和算法的高效运行能力。
　　 本文首先扩充细胞自动机概念，利用细胞自动机简单规则可导致复杂行为和细胞自动机局部化相互作用导致整体计算能力突现的重要特性，提出了基于细胞自动机的协同演化优化算法，通过定义细胞间简单的协同与合作演化规则来求解最优化问题，从理论上证明了在使用标准交叉算子的情况下算法的收敛性。运用本文提出的问题求解模式和协同演化算法求解了无约束函数优化问题、约束函数优化问题、组合优化问题。实验结果表明，算法在无约束函数优化和约束函数优化方面具有较好的性能，但对于组合优化问题的算法性能提高并不是很大。对函数优化问题的计算表明：在算法执行初期基本上以指数的速度收敛，在末期则每提高一位精度需要付出指数的时间，总体上收敛速度较理想。本文在函数优化问题上讨论了细胞自动机的维数对算法收敛速度的影响：在较高的维度收敛速度较快，但较容易陷入局部最优。本算法能运行在细胞架构的机器上。

目录

文摘

英文文摘

插图索引

附表索引

第1章 绪论

1.1 细胞自动机简介

1.2 细胞自动机研究现状

1.2.1 细胞自动机的理论研究

1.2.2 细胞自动机综合

1.2.3 细胞自动机的应用研究

1.2.4 细胞自动机的硬件环境

1.3 细胞自动机与复杂性研究

1.4 细胞自动机与下一代计算

1.5 课题研究意义

1.6 课题主要研究内容

1.7 本文结构

第2章 最优化问题及遗传算法

2.1 最优化问题简介

2.1.1 最优化问题

2.1.2 最优化算法

2.1.3 计算复杂性

2.2 遗传算法简介

2.2.1 遗传算法的结构

2.2.2 遗传算法中的技术要点

2.2.3 遗传算法的特点

2.2.4 遗传算法的评价

2.2.5 遗传算法的并行

2.3 本章小结

第3章 细胞自动机

3.1 细胞自动机的概念

3.2 细胞自动机的历史

3.3 细胞自动机的应用

3.4 细胞自动机的特点

3.5 细胞自动机分类

3.6 细胞自动机术语

3.7 本章小结

第4章 协同演化优化算法

4.1 协同演化优化算法介绍

4.2 收敛性证明

4.2.1 预备知识

4.2.2 算法收敛性

4.3 基于遗传算子的优化算法

4.3.1 遗传算子

4.3.2 算法描述

4.4 本章小结

第5章 演化算法求解函数优化实验与分析

5.1 无约束函数优化问题

5.2 有约束的函数优化问题

5.3 组合优化问题

5.4 自动机维数对算法性能的影响

5.5 本章小结

结论

参考文献

附录A 攻读学位期间发表的论文

致谢