课题名称

遗传算法在玻璃原料配送中的应用与研究 

学生姓名

 

专业班级

 

课题类型

软件工程

指导教师

 

职称

高工

课题来源

工程

1. 综述本课题国内外研究动态，说明选题的依据和意义

1.1国内外研究动态

    遗传算法(GeneticAlgorithms，简称GA)是人工智能的一个重要分支，它是基于Darwin的进化论，在计算机上模拟生命进化机制而发展起来的一门新学科，是生命科学与工程科学互相交叉、互相渗透的产物。遗传算法由美国J．H．Holland博士1975年提出，随后经过多年的发展，取得了丰硕的应用成果和理论研究的进展。从1985年在美国卡耐基一梅隆大学召开的第一届国际遗传算法会议到1997年，遗传算法作为具有系统优化、适应和学习高性能计算和建模方法的研究渐趋成熟。 

遗传算法本质上是一种求解问题的高度并行性全局搜索算法，它能在搜索过程中自动获取和积累有关搜索空间的知识，并自适应地控制搜索过程以求得最优解。遗传算法提供了一种求解复杂系统优化问题的通用框架，它不依赖于问题的具体领域，对问题种类有很强的鲁棒性，因此能够广泛应用于很多学科。目前，遗传算法已在函数优化、组合优化、生产调度问题、自动控制、机器人智能控制、图像处理、模式识别、人工智能、遗传程序设计和机器学习等领域投入应用并取得了一定的成果。 

    旅行商问题(Traveling Salesman Problem，简记TSP)是组合数学中一个古老而又困难的问题，也是一个典型的组合优化问题，现已归入NP完备问题类。TSP问题的历史可以分成以下几个阶段：1800—1900年，首次描述TSP；1920-1950年,开始意识到TSP是一个相当“难"的问题；1954年，42城市的TSP求得最优解。从1954年以后，求得最优解的TSP规模越来越大，在1998年，求得了模拟美国13509个城镇的最优解，在2001年，求得了模拟德国15112个城镇的最优解，但这一工程代价也是巨大的。据报道，解决15112个城镇问题的TSP共使用了美国Rice大学和普林斯顿大学之间网络互连的、由速度为500MHz的CompaqEV6 Alpha处理器组成的110台计算机，所有计算机花费的时间之和为22．6年。在2004年5月，瑞典求得了模拟24978城镇的最优解。 

    TSP可能的路径总数与城市数目n是成阶乘数增长的，故一般很难精确地求出其最优解。对于这个问题，不论是传统的动态规划、分枝定界法、贪婪法等方法，还是在近些年的研究过程中采用的各种智能优化算法(禁忌搜索(tabusearch)、模拟退火(simulated annealing)、遗传算法(genetic algorithms)、人工神经网络(neural networks)、蚂蚁算法(ant algorithms)以及它们的混合算法等)，都存在解的质量不高或者需要的时空开销太大等问题。 

1.2选题依据及意义

    实现玻璃原料配送成本的降低，必须对玻璃原料配送方案进行合理规划。玻璃原料配送的合理规划涉及到时间、财务、环境三方面的因素，首先从时间要考虑准时性、快速响应；财务上要考虑玻璃原料配送涉及的各种开支(车辆购置成本和消耗、司机薪酬、油耗等)；环境上要尽可能减少不必要的行驶距离，避免交通不便、空气粉尘以及噪音等不利因素。这些可以通过改进玻璃原料配送方式、线路规划等方法来加以改善。其中玻璃原料配送方式属于“硬”技术的问题。是可以通过设施的完善和提高玻璃原料配送的效率,降低相应成本。玻璃原料配送的线路规划主要是利用各种先进的信息技术对车辆及其路线进行规划，实现对车辆合理有效的利用，从而节省大量的时间和成本。而物流中心配送作业的重点就是如何将车辆有效的使用并决定其最经济的行驶路线图，使原料能在最短的时间内送到粉碎车间。该问题归纳为：从车辆配送中心派车向各个原料点装料，每个原料点的位置和需求量一定,每辆车的载重量一定，要求合理安排车辆路线，使总运距最短，并满足以下条件：(1)每条配送路径上各需求点的需求量之和不超过车辆载重量；(2)每条配送路径的长度不超过车辆一次配送的最大行驶距离；(3)每个需求点必须满足,且只能由一辆车送货。达到一定的目标(如路程最短、费用最少、时间尽量少、使用车辆数尽量少等)。 

    通过科学合理的手段制定配送路线，在配送活动中是很重要的一个环节。合理的选择配送路线，对于社会和企业具有重要意义。对于企业，配送路线的优化，可以简化配送程序、提高配送效率，充分利用配送车辆运力、降低空载率、减少配送次数、尽量使配送成本降低；同时优化配送路线可以加快企业对客户需求的响应速度，准时、快速的把原料送达目的地，提高用户的满意程度。对于社会，配送路线优化可以节省作业车辆，进而缓解交通拥堵状况，减少噪声、尾气的排放，为保护生态环境做出贡献。所以研究配送车辆路线优化问题及算法具有重要的现实意义。

 

 

 

 

 

2. 研究的基本内容，拟解决的主要问题

    (1) 研究的基本内容

通过遗传算法来解决从10个料场(分别存放白云石、长石、萤石、海砂等)将玻璃原料运送到粉碎车间的TSP问题。即一辆大型货车需要经过10个料场装载原料，每个料场必须且仅能经过一次，最后回到粉碎车间。要求依据该现实问题求出最短路径。

针对某一玻璃原料配送区域，在此区域内分布着一些玻璃原料的堆放点，要求在此区域中确定玻璃原料配送中心，建立此区域内的合理的配送系统，实现对各场地的玻璃原料分发。总原则是尽量使在选出地址上建立的配送中心与各分布点形成的配送系统总配送费用最省。本文建立解决TSP问题的数学模型，设计解决方法，如何使用遗传算法求解问题，并在仿真实验中得到一定的验证。

(2) 拟解决的主要问题

1)在设计交叉算子和变异算子的过程中，利用最短路径的数学性质和统计学规律，设计出改进的启发式顺序交叉算子和启发式变异算子，并与既有的OX、CX、ERC等算子进行比较和分析。对基因规模、变异概率和交叉概率随着代数的增加而变化的动态性质进行实验。并对遗传算子、每代最优解的进入和退出演化过程的性能进行分析。 

2)在程序实现时，有效利用STL和Boost的既有数据结构和算法，并利用设计模式的知识，使程序的实现更加灵活高效。  

3)将改进的遗传算法应用于玻璃原料运送中，取得良好的效果。

 

 

3.研究步骤、方法及措施 

(1) 研究步骤

1)需求分析。首先向用户了解基本需求，然后列出系统组成的功能模块，每个大功能模块再细化成小的功能模块。

2)概要设计。对软件系统的设计进行考虑，包括基本模块，功能分配，运行设计等，为详细设计奠定基础。

3)详细设计。将模块具体涉及到的算法、数据结构、类的层次结构以及调用关系进行进一步设计。

4)编码。根据数据结构和算法分析开始编写软件，用编程语言分别实现各个模块的基本功能。

5)测试。测试编写完成的系统功能，交给用户体验，提出修改意见。试完成后，完成验收并形成必要的文档。

6)维护。根据用户需求或者环境变化，对相应的应用程序进行修改。

(2)采用的方法及措施

1)算法设计

先采用经典的遗传算法理论及个体整数编码方法设计算法。考虑算法的实现结果虽然可得到相对最优解，但是当群体规模较大时，算法在运行过程中可能出现局部早熟的现象。所以拟对算子的选取进行改进重组，重新设计各个算子，试图进一步探索TSP组合优化问题的有效解决方案。  

2)采取的措施

    广泛收集各方面的资料,提出自己的观点，并与老师、同学进行讨论和分析。 

用定量化方法了解和解释系统、为决策提供科学依据。首先把有关的现实系统归结成数学模型，然后用数学方法进行定量分析和比较，求得合理运用人力、物力和财力的系统运行最优方案。充分利用运筹学知识，它有广阔的应用领域，是软科学中“硬度”较大的一门学科，兼有逻辑的数学和数学的逻辑的性质，是系统工程学和现代管理科学中的一种基础理论和不可缺少的方法、手段和工具。 

在运筹学中有解决物流配送问题的有效方法。该系统应用遗传算法解决TSP问题，通过编程来验证，在研究过程中了解浮点数编码、适应度函数、交叉算子和变异算子，遗传算法的三个基本运算（选择、交叉、变异）等问题。在求解TSP问题的各种遗传算法中，多采用以遍历城市的次序排列进行编码的方法，本文也采用这种最自然的编码方式，即以n个原料点的遍历次序作为遗传算法的编码。每一个解的码串形如：，其中，表示遍历原料点的序号。程序中的解定义为一维数组A(N)，N表示TSP问题中的原料点数目，数组中的各个元素A(i)(i∈{1,2,„,N})的取值为1至N间的整数，分别表示原料点的序号，根据问题的约束条件，每一整数内的各元素值互不相同。  

 

 

 

 

4. 研究工作进度

第4-6周：  查阅资料；了解国内外的研究动态及目前国内的应用现状，熟悉算法；对系统进行需求分析并撰写需求分析报告。

第7-9周：   进行系统的总体设计。

第10-13周：模块设计及程序代码编写。

第14-16周：系统调试、功能测试与完善；撰写毕业设计论文。

第17周：      毕业设计答辩。

 

 

 

 

 

 

 

 

5. 主要参考文献

[1]贾丽媛，杜欣.并行遗传算法研究[J].湖南城市学院院报（自然科学版），2006,28(3):249-252. 

[2]王小平，曹立明.遗传算法—理论应用与软件实现[M].西安：西安交通大学出版社，2002.  

[3]毛盛贤，刘国瑞.遗传工程的应用与展望[M].北京师范大学出版社，1986. 

[4]刘立平. 遗传算法综述[J].东莞理工学院学报，2005,28(3):249-252.

[5]李艺.工程结构化设计的混合遗传算法[J].四川大学学报，2005,28(3):249-252.

[6]傅清祥，王晓东.算法与数据结构[M].北京：电子工业出版社，1998. 

[7]邵军力，张景，魏长华.人工智能基础[M].北京：电子工业出版社，2000. 

[8]李鑫，陆海东.遗传算法及起应用[J].吉林化工学院院报，2005. 

[9]谭家幀.基因和遗传[M].北京：科学普及出版社，1981.  

[10]李金鹏.遗传算法原理及在结构优化设计中的应用[J].辽宁工学学院报，2004,28(3):249-252.

[11]周明，孙树冻.遗传算法及其应用[M].北京：国防工业出版社，1999. 

[12]张文修，梁怡.遗传算法的数学基础[M].西安：西安交通大学出版社，2000. 

[13]魏英资，赵明杨，黄雪梅，胡玉兰[J]。求解TSP问题的贪心遗传算法，2004. 

 

 

学院意见