1. 研究目的与意义（文献综述）

1)目的和意义

生活中,许多问题都是由相互冲突和影响的多个目标组成。人们会经常遇到使多个目标在给定区域同时尽可能最佳的优化问题,也就是多目标优化问题(multi-objective optimizationproblem,mop)。工程实践和科学研究中优化问题大多是多目标优化问题,各目标之间通过决策变量相互制约，对其中一个目标优化必须以其他目标作为代价，而且各目标的单位又往往不一致，因此很难客观地评价多目标问题解的优劣性。例如，在设计一座桥梁时，我们一方面希望建设桥梁的费用最小，另一方面希望桥梁具有最大的安全性。与单目标优化问题的本质区别在于，多目标优化问题的解不是唯一的，而是存在一个最优解集合，集合中元素称为pareto最优或非劣最优(non-dominance)。求解它们需要用不同于单目标优化的数学工具，甚至最优的含义也发生了变化。

多目标优化问题在工程应用等现实生活中非常普遍并且处于非常重要的地位,这些实际问题通常非常复杂、困难,是主要研究领域之一。自1975年johnholland提出遗传算法(genetic algorithm,ga)以来，基于生物模拟的进化算法(evolutionary algorithm,ea)得到了深入研究。由于其具有并行、不需要求导或其他辅助知识、一次产生多个解和简单易于实现等优点，被视为求解mop的有效方法。多目标进化算法(multi-objectiveevolutionary algorithm，moea)即是将进化算法用于求解多目标优化问题。

2. 研究的基本内容与方案

消灭星星是一款十分热门的手机游戏。该游戏玩法简单，但充满技巧性，大多数玩家只能获得几千分，而该游戏的分数的没有上限的。本次毕业设计希望设计一个有效的求解算法，来取得最高的游戏分数。一般的搜索算法对于消灭星星游戏来说，效果是非常有限的，通过对进化多目标优化算法的了解，决定采用遗传算法，蚁群算法，粒子群算法等多种优化算法来达到目的。设计内容如下：

1、对游戏的数据读取:由于算法的有效性需要通过实际测试去检验，所以如何获取游戏的数据是一个重要的过程。我准备使用图片处理技术获取各个关卡的实时数据，有了游戏的数据后再使用设计的算法进行下一步的求解；

3. 研究计划与安排

完成任务的时间节点

(1)2018/1/14—2018/3/5：确定选题，查阅文献，外文翻译和撰写开题报告；

(2)2018/3/6—2018/4/30：系统架构、程序设计与开发、系统测试与完善；

4. 参考文献（12篇以上）

1)cormen, thomash.(edt), introduction to algorithms [m]. mit press, 2005: 07.

算法的形式定义可以看作是任意一个良定义的计算过程，它以一个或一些值作为输入，并产生出一个或一组值作为输出。因而，一个算法也就是一系列的将输入转换为输出的计算步骤。

一个算法还可以被看作是用来解决一个良定义计算问题的工具。对问题的描述使用一般的语言来规定输入和输出之间的关系，而对应的算法则给出一个可以获得输入输出关系的计算过程。