摘 要

Abstract 8

1 绪论 9

1.1 研究背景 9

1.2 目的及意义 9

1.3 国内外研究现状 10

1.4 基本内容和技术方案 11

2 实现方法概述 12

2.1 游戏规则 12

2.2 项目目标 12

2.3 游戏数据读取 13

2.3.1 HSV 13

2.3.2 识别游戏区域和颜色归类 13

3 遗传算法设计与实现 15

3.1 遗传算法简介 15

3.2 设计思路 15

3.3 代码实现 16

4 粒子群算法设计与实现 18

4.1 粒子群算法简介 18

4.2 设计思路 18

4.3 代码实现 19

5 蚁群算法设计与实现 20

5.1 蚁群算法简介 20

5.2 设计思路 20

5.3 代码实现 22

6 测试结果分析与总结 23

6.1 遗传算法 23

6.2 粒子群算法 24

6.3 蚁群算法 25

6.4 工作总结 26

7 结语 28

7.1 工作展望 28

参考文献 29

致谢 30

摘 要

现如今，生活中人们经常会遇到需要达成多个目的并尽可能达到最好的问题,这些目的互相影响甚至存在冲突，如何同时使它们达到最佳就是多目标优化问题的研究内容。大多数多目标优化问题存在着多个互相矛盾的目标，这些目标无法同时达到最优，只能尽可能对各个目标平衡和折中处理，才能让总体性能达到最大值。本文对消灭星星求解中存在的多目标优化问题进行探究，主要工作内容如下：

（1）图片处理获取游戏数据

本文通过对游戏截图的截取和缩小获取代表游戏场景布局的10*10维像素，

并转化为相应的二维数组作为算法输入数据。

（2）三种进化算法的设计与实现

本文使用遗传算法、粒子群算法、蚁群算法的进化思想对消灭星星问题求解，设计出相应的算法，并对算法有效性进行了测试和分析。

（3）实验结果分析与比较

本文通过多个游戏场景截图对不同算法进行多次测试，得出这三个算法的平均得分分别在4100、4600和3800左右。因为不同场景对算法得分有较大影响，所以仅比较这三个算法在同一场景下的得分，实验结果证明粒子群算法有着最高的性能，遗传算法稳定性更高，蚁群算法适应度较低。

最终本文还提供了对其中两个算法性能优化的可行方案，主要是对遗传算法中交叉算子的和粒子群算法中初始化粒子群的优化，以提高算法求解的效率。

关键词：多目标优化问题；图片处理；遗传算法；粒子群算法；蚁群算法

Abstract

Nowadays, people in daily life often encounter problems that need to achieve multiple goals and reach the best possible. These goals affect each other and even conflict with each other. How to make them the best at the same time is the research content of multi-objective optimization problems. Most multi-objective optimization problems have multiple contradictory goals. It is impossible to achieve the goal of optimizing all the objectives at the same time. It may be possible to balance the goals so that the overall performance can be maximized. This article explores the multi-objective optimization problem in the solution to the elimination of stars. The main tasks are as follows:

(1) Image processing to obtain game data

This article acquires 10*10-dimensional pixels representing the layout of the game scene by intercepting and reducing the screenshots of the game.

And into a corresponding two-dimensional array as the algorithm input data.

(2) Design and implementation of three evolutionary algorithms

This paper uses the evolutionary ideas of genetic algorithm, particle swarm algorithm and ant colony algorithm to solve the star elimination problem, designs corresponding algorithms, and tests and analyzes the effectiveness of the algorithm.

(3) Analysis and comparison of experimental results

In this paper, several algorithms are used to perform multiple tests on different algorithms. It is concluded that the average scores of these three algorithms are around 4100, 4600 and 3800 respectively. Because different scenes have a greater influence on algorithm scores, only the scores of the three algorithms are compared in the same scene. The experimental results show that the particle swarm algorithm has the highest performance, the genetic algorithm has higher stability, and the ant colony algorithm has a lower degree of fitness. .

Finally, this paper also provides a feasible solution to optimize the performance of two algorithms, mainly the optimization of the initial particle swarm optimization in the crossover operator and the particle swarm optimization algorithm in the genetic algorithm to improve the efficiency of the algorithm.

Keywords: multi-objective optimization problem; image processing; genetic algorithm; particle swarm algorithm; ant colony algorithm

1 绪论

1.1 研究背景

根据系统分析理论和方法，将复杂的现实问题转化为可以理解的数学模型并基于给定的数学模型，从满足条件约束的所有可行解中选择最合理一种解，以最大化或最小化目标，这种做出合理决策的求解方案就是我们常说的最优化问题(optimization problem)。最优化问题作为一个由来已久的研究课题，普遍存在于现实生活中，只有一个目标需要优化的问题被叫做单目标优化问题，而多目标优化问题(multi-objective optimization problem，MOP)中存在多个需要同时优化的目标。MOP在工程应用等现实生活中非常普遍并且扮演非常重要的角色^[1]，比如此次对消灭星星问题求解的研究，这里要考虑到单次消除最大得分、全消后奖励得分、单次消除后对全局的影响等因素，每次消除都会对局面产生影响，单一追求单次消除得分最大可能大大降低拿到最终奖励得分的概率，反之亦然。从单目标优化到多目标优化的演变不单是目标数量的增加这么简单，在解决方案和最终解决方案集上都存在根本性差异。

大多数多目标优化问题存在着多个互相矛盾的目标，在提高某个目标性能同时，通常会降低其它多个目标的性能，所以要想全部目标同时达到最优是不可能的，只能尽可能让各个目标处于平衡状态，才能让总体性能达到最大值。所以多目标优化问题的最终解是满足一组各个目标值所折中的解决方案，这被称为Pareto最优集。^[2]，Francis Edgeworth首次提出了“最优”这一概念，后被Vilfredo Pareto将最优概念系统化，我们通常称其为“Pareto最优”。

1.2 目的及意义

多目标优化无疑是科学家和工程师非常重视的研究课题，因为工程和科学问题大多数都是MOP问题，存在多个彼此冲突的目标，他们也一直在研究如何得到这些MOP问题的最优解，而且多目标优化的问题广泛存在于现实生活中，经常难以处理。作为进化算法最基础和最重要的研究和应用领域之一,组合优化的巨大成功激发了人们更多的关注多目标优化领域，将人工进化理论应用到MOP问题中，从而相继出现许多种有效的MOEAs。现在计算机技术飞速发展，可以并行运算的随机搜索算法可以充分利用这些高性能的设备，MOEAs在更多领域得以成功应用，多数成功的MOEA都能够很好处理一些不连续的、有约束条件的的组合优化问题。

多目标进化算法为解决复杂系统优化问题提供了一个通用方案^[3]，它不依靠实际问题存在的具体环境，具有很强的通用性，所以它在很多领域中被广泛使用。随着研究和开发的进一步深入，多目标演化算法将在更广泛的领域发挥出更大的作用。 虽然多目标进化算法取得了较大的发展，但仍存在一些不足，如未成熟收敛、局部搜索能力差等，实现收敛与多样性之间的平衡是进化多目标优化中的一个关键问题^[4]。

因此对多目标进化算法的研究是很有必要的，消灭星星求解作为一个MOP问题，如何利用多目标进化算法求解就是我的研究课题。此次旨在通过对算法的设计深入理解多目标进化算法的理论和思想，并在理解的基础上针对本问题作出合适的设计，找到最佳的进化（迭代）策略，以获取问题的相对最优解。

1.3 国内外研究现状

进化多目标优化思想始于1967年，R.S. Rosenberg在博士论文中提出了可以采用选择遗传的思路来解决MOP。多目标优化问题从20世纪60年代提出至今，已经有很多对MOP问题的求解方法。进化计算是一种新兴的模拟自然进化过程的优化方法，它起源于20世纪50年代末，之后遗传算法、进化规划等进化算法陆续出现，它们基于进化思想，从一组候选的解决方案开始进化，在进化过程中更新最优解。由于进化算法机制简单，通用性和解决效率高，在研究复杂组合优化问题中取得不错的成果。自Schaff首次应用遗传算法求解MOP问题以来，多目标进化算法的研究和应用一直十分热门。

现如今，对多目标进化算法领域的研究迈入新的阶段，多目标进化遗传算法（MOGA）开始引入各种新的概念和策略（如动态进化策略、差分进化策略、混合策略、协同进化策略、并行策略等），对算法的性能和效率大大改善；像粒子群算法、蚁群算法、人工免疫算法、模拟退火算法这些新的进化算法也被引进多目标优化领域，同时在动态多目标优化问题和高维多目标优化问题的应用也有了初步的成果。近年来，在很多领域的应用研究上，多目标进化算法已经取得了很多成果，如如优化控制，数据挖掘，网络路由，物流配送，逻辑电路设计，机械设计，移动网络规划，森林规划优化，车间调度、模糊优化和神经网络等现代技术。

作为最早提出的一种进化算法，遗传算法的研究在几个方面有了新的发展，一是在神经网络、模糊推理等其它智能计算方法的应用，二是对并行处理的GA进行研究，三是基于遗传算法的机器学习。随着应用领域的扩展，遗传算法的钻研大大提高了求解一些组合优化问题的效率。

从粒子群算法被提出以来，由于它简单容易实现并且没有许多参数的调节的特点，特别适合于处理组合优化问题，并逐渐得到研究者的注意。近年来，在工程应用和科学研究上粒子群算法的理论和应用发挥了很大作用，已被广泛应用于神经网络训练、函数优化、入侵检测以及其他应用领域。到目前为止，PSO大体可分为两类，一是基本粒子群优化算法，二是广义粒子群优化算法，基本粒子群优化算法中粒子更新迭代的方式局限于速度—位移更新算子，无法在组合优化领域得到有效应用。广义PSO同遗传算法类似，粒子的更新迭代用交叉变异代替，同时它也存在PSO的本质思想，如与全局最优编码和局部最优编码交叉，变异等。

蚁群算法由于很高的灵活性和健壮性，通常被作为在图中随机寻找最佳路径的机率型算法。蚁群优化算法最初用于解决旅行商问题，为组合优化问题的处理提供了新方案，由于蚁群算法对问题求解的快速性和全局优化性，逐渐引起相关领域研究人员的重视。经过多年的发展，已经很快被应用到其它组合优化问题，如，图着色问题、数据挖掘、车辆调度问题、网络路由优化和其它经典组合优化问题，同时ACO算法也越来越多地应用到数据分析、电力、水利、通信、采矿、交通等领域。

1.4 基本内容和技术方案

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

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

2、 求解算法设计：一般的搜索算法对于消灭星星游戏来说显然是不够有效的。因此，拟采用遗传算法，蚁群算法，粒子群算法等多种优化算法进行设计，选择出其中最有效的算法，并在算法的设计过程中针对本问题做出特别的设计；

3、算法有效性检验：在设计完成一个算法后，需要解决的问题就是如何评价这个算法的有效性。找到一个评价参数评价本次设计的算法的有效性是必要的，并介绍本次设计的算法之间的异同。

2 实现方法概述

2.1 游戏规则

游戏场景是一个10*10的方格，填满了5种颜色的正方形方块。同一种颜色相连的方块即可消除，一次消除的方块越多给分越多，给予分数与消除方块数的方程是y=5x^2。当消除一个方块后在它上方方块都会向下落，每一纵列10个方块全消后在其右边方块会全部向左移。而每关不能再消除方块就结束，玩家消除消除的多，剩下的少会分数有奖励，奖励得分的公式是Y=-20x^2 2000，最终得分（y Y）只要积累超过每关设定的分数即可前往下一关。由此可以总结出三条规则：

1、游戏没有时间限制但每阶段都需要达到目标分；

2、一次消除更多的方块，得到的分数成幂数增加；

3、要想得到更多奖励分就必须尽可能消除更多星星。

2.2 项目目标

该项目包括遗传算法设计与实现，粒子群算法设计与实现，蚁群算法设计与实现和算法的分析比较几个部分。而总的来说完成该项目有三个要求：

（1）读取游戏数据的准确性

游戏数据的读取是算法设计的第一步，必须准确的识别图片中的游戏区域和每个星星的颜色，才能在算法中模拟消除后场景的变化。所以识别的准确性是最重要的。

（2）算法的有效输出

算法的运行结果必须包含能够计算出的最大得分和模拟消除过程中对星星的点击顺序，也可以输出游戏场景的最终局面。必须确保最大得分能通过点击顺序得到。

（3）算法的运行时间

因为本次是轻量级的算法设计，所以算法的参数不宜设置较大，如迭代次数，个体总数等，导致算法运行时间过长，同时也要避免算法进入死循环等情况。

2.3 游戏数据读取

2.3.1 HSV

图像处理中，通常用于色彩表示和图像处理的空间模型就是RGB模型，并且颜色由原色的组合定义，理解这个模型很简单。

而HSV模型，是一类注重人的观感的颜色空间模型，用我们更熟悉的方式包装了关于色彩的信息，其中HSV即（hue、saturation、value）分别表示色相、饱和度和色调。相较于RGB，它更侧重于色彩表示，代表我们看到某种色彩的直观感受：“颜色是什么？深浅如何？亮度如何？”^[5]

为了能更方便的知道每个星星的具体颜色，先将相应星星的RGB转换为HSV，然后根据颜色范围表做匹配就能进行五种颜色的归类了

2.3.2 识别游戏区域和颜色归类

首先利用ADB工具对手机游戏界面自动截图并将1980*1080像素图片传输到工程目录文件下，而游戏区域只占图片中间的一部分，所以需要截取图片的一部分。通过游戏背景与星星颜色亮度之间的明显差异得到游戏区域的上边界（image_top）,然后从上边界截取1080*1080的正方形游戏区域，再将其缩小成10*10像素，这样每个像素的色相就代表一个星星的颜色。截取并缩小过程的代码如下：

BufferedImage img_portion= bi.getSubimage(0,image_top,width,width);
int size=10;
int newWidth=size;
int newHeight=size;
BufferedImage newImage = new BufferedImage(newWidth, newHeight, BufferedImage.TYPE_INT_BGR);
Graphics graphics = newImage.createGraphics();
graphics.drawImage(img_portion, 0, 0, newWidth, newHeight, null);
File outFile = new File("src\\img\\star_portion.png");
OutputStream os=new FileOutputStream(outFile);
ImageIO.write(newImage, "png", os);