计算机游戏已经成为人工智能研究中一个重要并且活跃的领域,它不仅提供了一个合适的技术评估平台,同时围绕着计算机游戏所衍生出的人工智能研究领域——游戏人工智能,正推动着人工智能研究的发展。“星际争霸”是由暴雪娱乐公司开发的一款著名的即时战略游戏,围绕着星际争霸游戏进行的人工智能研究已有多年,包括策略制定、多智能体控制、对手建模以及预测等等。星际争霸的开局建造顺序属于策略制定的一种,是星际争霸游戏早期需要考虑的问题,玩家需要制定合理的开局建造策略来规划建筑物的建造、战斗单位的生产、科技的升级以及技能的研究等操作,以便在游戏初期取得优势。为此,本文给定建造目标,在游戏初期最大化战斗单位的生产数量,同时希望在每个规定时间段内拥有不同种类和不同数量的战斗单位,以应对敌人的进攻或者执行其他任务。本文称这个问题为:带单位生产数量约束的建造顺序最优化问题(Production Constrained Build-order Optimization Problem,简称PC-BO 问题)。针对这个问题,本文进行了如下工作:(1)单位生产数量约束是一个不确定约束,它同对手在游戏中的建造策略以及游戏的其它因素密切相关。考虑到大量游戏玩家回放数据的存在,这些游戏回放数据记录了玩家在游戏中的操作,包括建造动作、建造时间、单位的生产类型和数量等等,因此本文给出了一个数据驱动的方法从游戏玩家回放文件中获取单位生产约束的具体值。(2)求解PC-BO问题需要评估大量的建造顺序,而直接在星际争霸游戏中运行这些建造顺序需要大量的计算时间,因此本文给出了一个星际争霸建造模拟器,用它来评估在求解过程中产生的建造顺序。(3)采用改进的遗传算法——遗传模拟退火算法来求解PC-BO问题。同时为提高遗传算法的求解性能,本文使用了游戏玩家的建造顺序参与遗传算法初始种群的生成。实验结果表明了这种方法的有效性。