摘要
作为导向人类复杂系统研究的一个过渡，科学家们通过对群体生物的观察与研究产生了以模仿自然界群体生物行为特征的群智能研究领域。群智能是指任何受群体生物集体行为启发而设计的算法与分布式问题解决装置。 本文从一维细胞自动机入手，设计了适于求解二元离散优化问题的二元蚁群算法（BACO）和二元粒子群算法（BPSO-CA）。Agent（包括ant 和particle）从起始细胞出发，根据相应的函数转换规则随机从细胞状态集合中进行选择，实现复杂智能的“涌现”。随后将BACO及BPSO-CA应用于二元离散优化问题——单0/1背包问题的求解，对其时间复杂度、空间复杂度、算法收敛性进行分析，并通过拉长细胞自动机或增加细胞状态集合中元素数目的方式来对BACO及BPSO-CA进行扩展，适用于多维0/1背包问题的求解。但在问题求解的过程中，不可避免的会产生一些非法的个体，当agent（包括ant 和particle）完成了它们的路径构建步骤之后，将具有局部搜索性能的贪心算法引入到具有全局搜索性能的群智能算法中对其进行修正。 通过对Zuse Institute Berlin公布的测试集进行实验，表明本文提出的算法均能在多项式时间内完成0/1背包问题的求解，且实验结果均优于测试集记录的结果。为进一步验证本文设计算法的有效性，将BACO、BPSO-CA及其扩展模型应用于组卷问题的求解中，实现一次性产生单套或多套试卷，具有较强的实用价值。
NETL