基于GA的迷宫解决方案设计开题报告

《基于GA的迷宫解决方案设计开题报告》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、开题报告基于GA的迷宫解决方案设计一、选题的背景、意义历史背景避障寻径问题被证明是一类NP-Hard问题，一直以来都是计算机科学人工智能领域内的热门话题，渗透于我们日常生产生活中的各个领域，如无人机器侦查兵，无人驾驶运输车，城市内的车辆自动导航等等，其求解算法的研究，近年来受到广泛的关注[1]。二维迷宫求解从本质上来讲，是避障寻径模型的一个简单的数学描述。由于思想和方法的局限性，在现存的算法中，人们主要考虑比较简单的静态环境下的理想情况[2]。然而，在实际环境中遇到的问题并不如想象中的那么简单。二维迷宫求解是在一个具有许多障碍物的迷宫里

2、，寻找一条从起点避开障碍物到终点的路径问题[3,4]。图1就是一个二维迷宫，左边的黄色为起点，右边的红色为终点，中间的黑色表示障碍物，白色则表示可以正常通过。图2是一条从起点到终点的可行解（并非最优解）。对于二维迷宫求解问题，从广义上来讲，就是一个寻找路径的问题。二维迷宫求解使用遗传算法[5]，遗传算法是一种随机的种群搜索算法，它是对达尔文生物进化原理的计算机模拟。它通过用适应度函数对每一代群体中的个体进行评估，按照优胜劣汰的原则，保存较好的个体，淘汰较差的个体，并对个体进行繁殖，交叉，变异的遗传操作，使整个群体不断地进化。遗传算法有着

3、明确的搜索方向，它具有简单，通用性强，效果显著等特点，适合处理传统的搜索方法难以解决的复杂问题。迷宫问题实际上也是一个组合优化问题，本文研究使用遗传算法求解该问题的可行性。它的难度在于染色体如何编码，评估函数如何设计以及遗传操作的算子如何设计。本文在对这些问题进行研究的基础上，给出了求解该问题的遗传算法，并通过大量的实验证明该算法是有效的。相信通过对遗传算法求解迷宫问题的研究，能对其他一些用传统方法难以解决的优化问题提供一些启示[6]。国内外研究现状虽然在各种应用领域中，算法的具体实施细节有各自的特点，但遗传算法提供了一种求解复杂系统优

4、化问题的通用框架，它不依赖于问题的具体领域。遗传算法主要应用于以下几个主要领域：（1）函数优化函数优化是遗传算法的经典应用领域，也是对遗传算法进行性能评价的常用例子。很多人工构造的各种各样复杂形式的测试函数，有连续函数也有离散函数，有单峰函数也有多峰函数等，利用这些函数来评价遗传算法的性能。对于非线性、多目标的函数优化问题，用其他算法通常较难求解，但使用遗传算法却很方便并可以得到较好的结果。（2）组合优化随着问题规模的扩大，组合优化问题的搜索空间急剧增大，甚者有时无法求到精确最优解。对于这类复杂问题，使用遗传算法求解可行解就显得更加有实

5、际价值[7]。这类问题包括旅行商问题、背包问题、装箱问题和图形划分等。（3）生成调度生产调度问题在很多情况下所建立起来的数学模型难以精确求解，即使经过一些简化之后可以进行求解，也因简化太多而使得求解结果与实际相差甚远。因此目前现实生产中也主要靠一些经验进行调度。遗传算法已经成为解决复杂调度问题的有效工具，在单件生产车间调度、流水线生产车间调度、生产规划、任务分配等方面遗传算法都得到了有效的应用。（4）自动控制在自动控制领域中有很多与优化相关的问题需要求解。遗传算法已在其中得到了初步的应用，并显示出良好的效果。例如用遗传算法进行航空控制系

6、统的优化、使用遗传算法设计空间交会控制器、基于遗传算法的模糊控制器的优化设计、基于遗传算法的参数辨识、基于遗传算法的模糊控制规则的学习、利用遗传算法进行人工神经网络的结构优化设计和“权值”学习等。都显出了遗传算法在这此领域中应用的可能性[8]。（5）机器人学机器人是一类复杂的难以精确建模的人工系统，而遗传算法的起源就来自于人工自适应系统的研究。所以，机器人学理所当然地成为遗传算法的一个重要应用领域。例如，遗传算法已经在移动机器人路径规划、关节机器人运动轨迹规划、机器人逆运动学求解、细胞机器人的结构优化和行为协调等方而得到研究和应用[9]

7、。（6）图像处理图像处理是计算机视觉中的一个重要研究领域。在图像处理过程中，如扫描、特征提取、图像分割等不可避免地会存在一次误差，从而影响图像的效果。如何使这些误差最小是使计算机视觉达到实用化的重要要求。遗传算法在这些图像处理中的优化计算方面找到了用武之地。目前已在模式识别(包括汉字识别)、图像恢复、图像边缘特征提取等方而得到了应用。（7）人工生命人工生命是用计算机、机械等人下媒体模拟或构造出的具有自然生物系统特有行为的人造系统。自组织能力和自学习能力是人下生命的两大主要特征。人下生命与遗传算法有着密切的关系。基于遗传算法的进化模型是研

8、究人下生命现象的重要基础理论。虽然人下生命的研究尚处于启蒙阶段，但遗传算法已在其进化模型、学习模型、行为模型、自组织模型等方面显示出了初步的应用能力，并且必将得到更为深入的应用和发展。人工生命与遗传算法相辅