数学建模竞赛论文范文样本.docx

《数学建模竞赛论文范文样本.docx》由会员分享，可在线阅读，更多相关《数学建模竞赛论文范文样本.docx（25页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、宜宾学院数模竞赛论文模版：宜宾学院第三届高校生数学建模竞赛（2012年5月19日5月28日）参赛题目（在所选题目上打勾） A B 参赛编号（竞赛组委会填写） 参赛队员1参赛队员2参赛队员3姓名学号学院专业年级 Email评阅记录（竞赛评审委员会评阅时运用）：评阅人评分备注论文题目摘 要1、摘要:本文解决什么问题,解决问题的方法,结论.提请大家留意：摘要应当是一份简明扼要的具体摘要（包括关键词），在整篇论文评阅中占有重要权重，请仔细书写（留意篇幅不能超过一页，且无需译成英文）。关键词：2、正文一、问题的提出:叙述问题内容及意义.二、根本假设:写出问题的合理假设.三、建立模型:具体叙述模型、变量、

2、参数代表的意义和满足的条件及建模思想.四、模型求解:求解、算法的主要步骤.五、结果分析与检验:(含误差分析).六、模型评价:优缺点及改良意见.七、参考文献:限公开发表文献,指明出处.3、附件:计算框图、程序及打印结果.参考文献 例子1吕显瑞等. 数学建模竞赛辅导教材M. 长春: 吉林高校出版社, 2002: 56-982刘来福,曾文艺. 数学模型与数学建模M. 北京: 北京师范高校出版社, 1997: 78-893熊慧. 论人口预料对上海市将来十年人口总数的预料. 人口讨论J, 2003, 28(1): 88-9042003年国民经济和社会开展统计公报, Http:/ , 2008年9月20日

3、l 引用别人的成果或其他公开的资料(包括网上查到的资料) 必需根据规定的参考文献的表述方式在正文引用途和参考文献中均明确列出。正文引用途用方括号标示参考文献的编号，如13等；引用书籍还必需指出页码。参考文献按正文中的引用次序列出，其中书籍的表述方式为：编号作者. 书名. 出版地: 出版社, 出版年: 页码范围参考文献中期刊杂志论文的表述方式为：编号作者. 论文名. 杂志名. 出版年, 卷期号: 起止页码参考文献中网上资源的表述方式为：编号作者. 资源标题. 网址, 访问时间（年月日）注：多名作者姓名之间用：英文逗号+空格范文：基于双种群遗传算法的公交路途查询问题摘 要 本文讨论的是公交路途选择

4、而开发的查询系统.以两站点之间所花时间的最小值作为主要目的函数，利用双种群遗传算法的原理建立公交路途选择数学模型，再通过MATLAB程序来实现整个流程和迭代，最终求出全局近似最优解，即最优权重线路，以起点和终点查询到近似的最优公交路途，并进展了误差分析,模型的评价与推广. 问题一：仅考虑公汽线路，对数据进展初步分析和处理后，考虑到数据的困难性和数据搜寻范围的广度，我们应用比拟成熟的双种群遗传算法建立数学模型. 通过MATLAB强大的矩阵运算功能得到站点之间的邻接矩阵，用时间加权. 其流程思想为基于双种群初始群体A、B，对染色体进展整数编码，用竞争选择法选择出较优个体作为繁殖下一代的母体，根据选

5、择性集成思想，等概率运用两点穿插法和区域穿插法对染色体进展穿插操作与运用邻居交换变异和两点交换变异进展染色体变异操作，并结合MATLAB反复迭代，最终给出了六对起始站与终点站的六条近似最优路途. 该法扩大遗传算法的搜寻范围，避开过早收敛. 问题二：在数据处理上用时间加权把地铁站点和汽车站点统一化，可得全部站点之间的邻接矩阵. 其求解原理与问题一相像，但由转车方式的不同生成了8种不同的适应度函数,再根据适应度函数来进展问题的求解. 问题三：我们将随意两个站点之间的步行时间作为矩阵中相应位置的权，这时构建的邻接矩阵中的权就由两站点之间公汽到公汽的时间,公汽到地铁的时间,地铁到公汽的时间,地铁到地铁

6、的时间和两点之间的步行时间构成. 但其求解原理与问题一相像，但由转车方式的不同就会生成不同的适应度函数,再根据适应度函数来进展问题的求解. 双种群遗传算法供应了一种求解困难系统优化问题的通用框架，它不依靠于问题的具体领域，对问题的种类有很强的鲁棒性，具有自组织、自适应和自学习性. 关键词：双种群遗传算法；竞争选择法；离散赌轮选择算子；选择性集成思想一、问题的重述第29届奥运会明年8月将在北京实行，届时有大量观众到现场观看奥运竞赛，其中大部分人将会乘坐公共交通工具（简称公汽，包括公汽、地铁等）出行. 北京市的公汽线路已达800条以上，使得公众的出行更加通畅、便利，但同时也面临多条线路的选择问题.

7、 针对市场需求，某公司打算研制开发一个解决公汽线路选择问题的自主查询计算机系统. 为了设计这样一个系统（核心是线路选择的模型与算法），从实际状况动身，满足查询者的各种不同需求. 须要讨论的问题如下：问题一：只考虑公汽线路状况，给出随意两公汽站点之间线路选择问题的一般数学模型与算法. 并根据根本参数设定中的数据，利用其模型与算法，求出6对起始站终到站之间的最佳路途，并要有清楚的评价说明. 见下表：123456起始站S3359S1557S0971S0008S0148S0087终点站S1828S0481S0485S0073S0485S3676问题二：同时考虑公汽与地铁线路，解决以上问题. 问题三：假

8、设知道全部站点之间的步行时间，给出随意两站点之间线路选择问题的数学模型. 其中根本参数设定：相邻公汽站平均行驶时间(包括停站时间)：3分钟相邻地铁站平均行驶时间(包括停站时间)：2.5分钟公汽换乘公汽平均耗时：5分钟(其中步行时间2分钟)地铁换乘地铁平均耗时：4分钟(其中步行时间2分钟)地铁换乘公汽平均耗时：7分钟(其中步行时间4分钟)公汽换乘地铁平均耗时：6分钟(其中步行时间4分钟)公汽票价：分为单一票价与分段计价两种，标记于线路后；其中分段计价的票价为：020站：1元；2140站：2元；40站以上：3元地铁票价：3元（无论地铁线路间是否换乘）注：以上参数均为简化问题而作的假设，未必与实际数

9、据完全吻合. 公汽线路及相关信息见数据文件B2007data.rar. 二、模型的假设1. 转车的次数限制在2次以内；2. 相邻公汽站平均行驶时间(包括停站时间)：3分钟；3. 相邻地铁站平均行驶时间(包括停站时间)：2.5分钟；4. 公汽换乘公汽平均耗时：5分钟(其中步行时间2分钟)；5. 地铁换乘地铁平均耗时：4分钟(其中步行时间2分钟)；6. 地铁换乘公汽平均耗时：7分钟(其中步行时间4分钟)；7. 公汽换乘地铁平均耗时：6分钟(其中步行时间4分钟)；8. 公汽票价：分为单一票价与分段计价两种，标记于线路后，其中分段计价的票价为：020站：1元，2140站：2元，40站以上：3元；9.

10、地铁票价：3元（无论地铁线路间是否换乘）；10. 知道全部站点之间的步行时间.三、符号说明C：只考虑公汽线路的状况下，每个个体对应路途总长；D：考虑公汽和地铁线路的状况下，每个个体对应路途部长；：相邻公汽站平均行驶时间(包括停站时间)；：相邻地铁站平均行驶时间(包括停站时间)；：第k个个体所对应的适应度值；A：每个个体所对应的适应度比例；P：每个个体所对应的选择概率（适应度比例）；：全部站点之间的步行时间；：表示转车换乘所耗时间之和.四、模型的建立与求解（一）问题一1.1 问题分析该问题是一个组合优化问题. 对于此类问题，只有当其规模较小时，才能求其准确解. 在本文中公汽路途总数与站点数是成指

11、数型增长的，所以一般很难准确地求出其最优解，因此找寻出有效的近似求解算法就具有重要意义. 由于L406公汽线路的路途是环形的，而数据中没有标示出来，所以我们用相邻站点整体路途也相邻，推断出该公汽线路是环行的，所以应当作环行处理. 对于该问题，我们先求出其站点与站点之间的邻接矩阵（权用时辰表示），其矩阵大小为，数据量太多，不能输出，只能把放在内存中. 很多智能算法被用于求解两点间线路问题. 如禁忌搜寻、模拟退火、蚁群算法等. 其中遗传算法是被讨论最多的一种算法. 但标准遗传算法简单陷入部分极值解，出现“早熟收敛”现象. 为此人们提出了多种改良方法，如将遗传算子中的穿插算子进展改良，应用单亲遗传算

12、法，将遗传算子与启发式算法结合等. 遗传算法的核心思想为自然选择，适者生存. 遗传算法作为一种模拟生物进化的一种算法，供应了一种求解困难系统优化问题的通用框架，它不依靠于问题的具体领域，对问题的种类有很强的鲁棒性，具有自组织、自适应和自学习性. 其也是一种迭代算法，从选定的初始解动身，通过不断地迭代，逐步改良当前解，直到最终搜寻到最优解或满足解，其迭代过程是从一组初始解(群体)动身，采纳类似于自然选择和有性繁殖的方法，在继承原有优良基因的根底上生成具有更好性能的下一代解的群体. 遗传算法的流程图见下图：开场初始化群体是否满足条件选择退出算法穿插变异否个体评价是 遗传算法流程图标准遗传算法是针对

13、一个宏观的种群进展选择、穿插、变异三种操作. 双种群遗传算法是一种并行遗传算法，它运用多种群同时进化，并交换种群之间优秀个体所携带的遗传信息，以打破种群内的平衡态到达更高的平衡态，跳出部分最优. 在双种群遗传算法中，每一种群都是根据标准算法进展操作. 在操作时，首先建立两个遗传算法群体，即种群A和种群B，分别独立地进展选择、穿插、变异操作，且穿插概率、变异概率不同. 当每一代运行完毕以后，产生一个随机数n，分别从A，B中选出最优染色体和n个染色体进展杂交，以打破平衡态. 因为在双种群遗传算法中，每一种群都是根据标准算法进展操作的. 由上分析，对于本问题，我们釆用双种群遗传（double pop

14、ulations genetic algorithm）在选择公汽路途问题中的应用. 遗传算法的创始人美国闻名学者、密西根高校教授John H.Holland认为，可以用一组编码来模拟一组计算机程序，并且定义了一个衡量每个“程序”的度量：“适应值”. Holland模拟自然选择机制对这组“程序”进展“进化”，直到最终得到一个正确的“程序”为止. 编码方式有：二进制编码、十进制编码和符号编码等方法. 整数编码与符号编码一般用于与依次有关的组合优化方面的问题. 根据公汽路途的特点，本文的工作采纳整数. 染色体长度与公汽路途结点个数一样，染色体的每个基因的编码即为公汽路途结点的编号. 因此，每条染色体

15、由1到n（3957）的一个全排列组成. 在对染色体进展时,考虑到适应度比例法(轮盘赌选择法)与最佳个体保存法各自的优缺点，差异性较大，根据选择性集成思想,表现好的个体学习器越准确、差异越大，集成后可以获得的结果越好. 而竞争选择法集成了上述两种的优点克制了它们的缺点，因此本文釆用竞争选择法. 其中竞争选择法是釆用适应度比例法进展选择，穿插后产生下一代，再利用最佳个体保存法将上一代的最佳个体干脆保存下来，然后从新群体中淘汰一个适应度最差的个体，进步了问题求解的收敛速度，表达了遗传算法自适应环境的实力. 在对染色体进展穿插时,对于由整数编码的染色体，穿插操作会形成染色体中的非法基因，即重复基因.

16、所以实现染色体穿插要将重复的基因去除. 只运用一种穿插方法简单引起过早收敛，即“早熟”. 根据选择性集成思想 ,等概率运用两点穿插法和区域穿插法这两种穿插方法，扩大遗传算法的搜寻范围，避开过早收敛. 在染色体的变异中，与穿插方法一样，假如运用一种变异方法，同样可能会引起“早熟”. 为了避开过早收敛，根据选择性集成思想选择邻居交换变异和两点交换变异这两种特性好且差异性较大的变异方法，等概率运用以扩大搜寻范围. 1.2 模型建立1.2.1 从起点站到终点站不转车，则双种群遗传算法的流程如下：（1）产生邻接矩阵 邻接矩阵的MATLAB程序实现见附件一. （2）基于站点序号的编码 一般来说种群规模越大

17、越简单收敛到最优解，但是要保证其初始种群中的每个个体都是互异的，m不能设置过大，否则无法产生初始种群，且m过大其收敛速度必定降低，也会消耗更多的计算资源,并基于一般遗传算法中初始群体大小的选择，本文中取m=30. 公汽路途问题中每一种起点站到终点站的方案对应于解空间的一个解 ，解空间中的数据是遗传算法的表现形式，从表现到基因型的映射称为编码. 最初遗传算法是采纳二进制编码方法，但在大量实际问题中，二进制编码操作不简便，不易进展变异穿插操作，易产生大量非可行解，所以针对特别的问题，可以敏捷采纳不同的编码方法. 本文在公汽线路求解中，采纳基于站点序号的实数编码，将染色体定义为公汽线路的一条解路途中

18、的站点号序列，在MATLAB中为一个没有重复数字的行向量来表示. 设有n个站点的某个全排列为，则个体的染色体表示为，n=3957. （3）产生初始群体种群中每一个体为n（3957）个站点的一个全排列，随机生成m（m=30）个1n 的随机排列，得到m个个体的初始种群，m为种群大小，n为染色体长度. 生成初始群体的具体算法的MATLAB程序实现见附件二. A、B初始群体的数据矩阵为，由于数据太多，文中就不给出数据（其结果可运行程序得出）. （4）适应度函数与染色体的选择在遗传算法进展搜寻时只以适应度函数为根据，利用种群中个体每个的适应度值来进展搜寻，适应度值是进化时优胜劣汰的根据，应用中总是根据问

19、题的优化指标来定义. 对于公汽线路问题，以个体对应路途所发的时间之和作为个体适应度，其适应度越小,说明该个体越优. 则该个体对应为：其中（3（分钟）表示相邻公汽站平均行驶时间(包括停站时间)，表示站点和之间的间隔 ，表示起始点与终点站之间的间隔 .一般来说，选择算子设计使得个体被选中并遗传到下一代群体中的概率与该个体的适应度大小有关. 适应度是越高越好，而在公汽线路问题中，假如适应度是所经过的对应路途所花的时间之和，路途所花时间之和是越小越好，为了使公汽线路问题的适应度与一般遗传算法中的适应度一样. 这里用选择概率来进展衡量. 则每个个体的选择概率（适应度比例）就是每个个体的适应度与全部个体适

20、应度的总和之比，即：其中表示全部个体适应度的总和. 但当途径所花时间特别大(例如：10000)，这样其适应度比例的最高数据位将在小数点后的第四位，这样不利于计算，为此要进展尺度变换. 为确保适应度有两位整数，此处将适应度放大倍数L(本题中 L=lOOO) 因此适应度比例的表达式为：遗传算法中选择算子设计经典的是用适应度成比例的概率方法 ，但是这里存在的问题是由于很多个体的适应度比例很小几乎没有时机复制个体，从而被过早地淘汰. 这样整个群体多样性就无法得到保证，这里采纳一种新的赌轮选择算子离散赌轮选择，将有效地避开了这个问题. 在本题中是由30个个体构成初始群体，即：，其所占的适应度比例分别是，

21、在保持这个比例的状况下对这个取值范围放大1000倍. 根据依次在11000内分别占不同的区间，当随机函数产生11000以内的时，即使是适应度比例最小的也有可能被选中，从而较好的保持了群体的多样性. 由上所述则可选择出适应力强的，淘汰适应力弱的个体从而得到总体适应实力强的群体. 经过选择算子得出总体适应实力强的A、B群体数据矩阵为，因数据量太大，文中就不给出具体数据. （5）穿插重组根据选择性集成思想 ,等概率运用两点穿插法和区域穿插法这两种差异性较大的穿插方法，扩大遗传算法的搜寻范围，避开过早收敛. 其中，两点穿插法是先随机设定两个基因穿插位置，将父辈两个个体在这两个穿插点之间的基因链码互相交

22、换，从而形成新的个体；区域穿插法是随机在染色体中选择一个穿插区域，将第二条染色体的穿插区域加在第一条染色体的前面，第一条染色体的穿插区域加在第二条染色体的前面，在穿插区域后依次删除与穿插区域一样的基因，得到最终的两条子染色体. 将第（3）步得到的关于A，B种群的数据分别用两种穿插算法来实现操作. 其中一半数据用两点穿插法，另一半的数据用区域穿插法来进展染色体的穿插重组. 其具体算法的MATLAB程序实现见附件四. 经过穿插重组得出的A、B群体数据矩阵为，因数据量太大，文中就不给出具体数据. （6）染色体的变异为了避开过早收敛，根据选择性集成思想选择邻居交换变异和两点交换变异这两种特性好且差异性

23、较大的变异方法，等概率运用以扩大搜寻范围. 其中，邻居交换变异是产生一个随机数，将该数对应的基因和其后的基因交换；若该数对应的基因是染色体中的最终一个基因，则将该基因与染色体的第一个基因交换；两点交换变异是先产生两个不同的随机数，确定两个交换点，然后对个体在此两点的基因进展交换. 经过染色体变异得出的A、B群体数据矩阵为，因数据量太大，文中就不给出具体数据. （7）种群穿插将两个种群中的最优解取出，再在每个种群中随机选取n个染色体，将这n+1个染色体互换，进入对方种群. 经过种群穿插得出的A、B群体数据矩阵为，因数据量太大，文中就不给出具体数据. （8）最佳个体保存法 要把群体中适应度最高的个

24、体不经过配对穿插干脆复制到下一代中，然后从新群体中淘汰一个适应度最差的个体. 分别对A、B进展独立的操作. 经过最佳保存法选择后得出的A、B群体数据矩阵为，因数据量太大，文中就不给出具体数据. （9）迭代的完毕条件 在本文中，采纳进化的代数N作为循环迭代过程的完毕，假如等于N，则算法完毕，输出适应值最高的解；否则，接着重复上述过程. 重复步骤（3），（4），（5），（6），（7），（8）依次进展循环迭代，本题中设定迭代次数为N=1000. 最终得到30个近似的最优解. 以上（2）（9）流程的MATLAB程序实现见附件二. （10）结果选出这30个近似最优解中以时间作为权值最小的那一组解作为题设

25、中要求的近似最优解. 其中满足要求的基因链码（站点数）的依次即是顾客所需从起始点到终点站的路途1.2.2 从起点站到终点站转一次车从起点站到终点站转一次车遗传算法流程中基于站点序号的编码，穿插重组，染色体的变异，种群穿插，迭代的完毕条件和结果的原理与从起点站到终点站不转车一样. 只有在适应度函数与选择流程中每一个个体所对应的适应度函数处有所变更，其函数为：其中5（分钟）表示公汽换乘公汽一次耗时(其中步行时间2分钟).除这之外，这一流程中的其他的原理没变. 1.2.3 从起点站到终点站转两次车从起点站到终点站转两次车遗传算法流程中基于站点序号的编码，穿插重组，染色体的变异，种群穿插，迭代的完毕条

26、件和结果的原理与从起点站到终点站不转车一样. 只有在适应度函数与选择流程中每一个个体所对应的适应度函数处有所变更，其函数为： 其中（分钟）表示公汽换乘公汽两次耗时(其中步行时间分钟).除这之外，这一流程中的其他的原理没变. 1.3 模型求解1.3.1从起点站到终点站不转车 由程序运行最终得出：找不一条路途使从起点站到终点站不转车. 1.3.2 从起点站到终点站转一次车起始站第一次路途中转站第二次路途终点站S3359L436S3695L217S1828S0008L200S3092L282S0073S0971L013S2607L377S0485S0087-L454S1893L209S36761.3

27、.3从起点站到终点站转两次车起始站路途一中转站一路途二中转站二路途三终点站S1557L084S1919L417S0871L447S0481S0148L308S1419L166S0248L469S0485（二）问题二2.1 问题分析考虑到参加地铁及公汽的穿插通道，在数据处理上用时间加权把地铁站点和汽车站点统一化，可得全部站点之间的邻接矩阵. 其求解原理与问题一相像，但由转车方式的不同就会生成相对应的适应度函数,再根据适应度函来对问题求解. 2.2 模型建立2.2.1 产生邻接矩阵首先运用MATLAB强大的矩阵运算功能把其邻接矩阵得出,该矩阵是,由于数据量太大不能把其具体表示出来,只能把所得到的数

28、据放在内存中,在运用的时候再从内存中调用. 2.2.2 只坐地铁（不换乘）对于该问题遗传算法流程中基于站点序号的编码，穿插重组，染色体的变异，种群穿插，迭代的完毕条件和结果的原理与仅考虑公汽线路从起点站到终点站不转车一样. 只有在适应度函数与选择流程中每一个个体所对应的适应度函数处有所变更，其函数为：其中表示相邻地铁站平均行驶时间(包括停站时间),表示站点和之间的间隔 ，表示起始点与终点站之间的间隔 .除这之外，这一流程中的其他的原理没变. 2.2.3 地铁到地铁（换乘一或两次）对于该问题遗传算法流程中基于站点序号的编码，穿插重组，染色体的变异，种群穿插，迭代的完毕条件和结果的原理与仅考虑公汽

29、线路从起点站到终点站不转车一样. 只有在适应度函数与选择流程中每一个个体所对应的适应度函数处有所变更，其函数为：其中(2.5(分钟)表示相邻地铁站平均行驶时间(包括停站时间),表示站点和之间的间隔 ，表示起始点与终点站之间的间隔 ,4(分钟)表示地铁换乘地铁平均耗时(其中步行时间2分钟).除这之外，这一流程中的其他的原理没变. 2.2.4 地铁到公汽对于该问题遗传算法流程中基于站点序号的编码，穿插重组，染色体的变异，种群穿插，迭代的完毕条件和结果的原理与仅考虑公汽线路从起点站到终点站不转车一样. 只有在适应度函数与选择流程中每一个个体所对应的适应度函数处有所变更，其函数为：除这之外，这一流程中

30、的其他的原理没变. 2.2.5 公汽到地铁为了简化模型，将地铁换乘公汽平均耗时与公汽换乘地铁平均耗时都假设为7分钟，因为耗时相差不大. 则地铁到公汽与公汽到地铁是一样的. 对于该问题遗传算法流程中基于站点序号的编码，穿插重组，染色体的变异，种群穿插，迭代的完毕条件和结果的原理与仅考虑公汽线路从起点站到终点站不转车一样. 只有在适应度函数与选择流程中每一个个体所对应的适应度函数处有所变更，其函数为：除这之外，这一流程中的其他的原理没变. 2.2.6 公汽到地铁再到公汽对于该问题遗传算法流程中基于站点序号的编码，穿插重组，染色体的变异，种群穿插，迭代的完毕条件和结果的原理与仅考虑公汽线路从起点站到

31、终点站不转车一样. 只有在适应度函数与选择流程中每一个个体所对应的适应度函数处有所变更，其函数为：除这之外，这一流程中的其他的原理没变. 2.2.7公汽到地铁再到地铁对于该问题遗传算法流程中基于站点序号的编码，穿插重组，染色体的变异，种群穿插，迭代的完毕条件和结果的原理与仅考虑公汽线路从起点站到终点站不转车一样. 只有在适应度函数与选择流程中每一个个体所对应的适应度函数处有所变更，其函数为：除这之外，这一流程中的其他的原理没变. 2.2.8地铁到公汽再到公汽对于该问题遗传算法流程中基于站点序号的编码，穿插重组，染色体的变异，种群穿插，迭代的完毕条件和结果的原理与仅考虑公汽线路从起点站到终点站不

32、转车一样. 只有在适应度函数与选择流程中每一个个体所对应的适应度函数处有所变更，其函数为：除这之外，这一流程中的其他的原理没变. 2.2.9地铁到公汽再到地铁对于该问题遗传算法流程中基于站点序号的编码，穿插重组，染色体的变异，种群穿插，迭代的完毕条件和结果的原理与仅考虑公汽线路从起点站到终点站不转车一样. 只有在适应度函数与选择流程中每一个个体所对应的适应度函数处有所变更，其函数为：除这之外，这一流程中的其他的原理没变. 2.3 模型求解2.3.1 只坐地铁由程序运行最终得出：对六对起点到终点找不一条路途为只做地铁.2.3.2 地铁到地铁由程序运行最终得出：对六对起点到终点找不一条路途地铁到地

33、铁.2.3.3 地铁到公汽由程序运行最终得出：对六对起点到终点找不一条路途为地铁到公汽.2.3.4 公汽到地铁由程序运行最终得出：对六对起点到终点找不一条路途为公汽到地铁.2.3.5 公汽到公汽1.换一次车起始站第一次路途中转站第二次路途终点站S3359L436D12L217S1828S0008L200D15L282S0073S0971L013D08L377S0485S0087-L454D24L209S36762.换两次车起始站路途一中转站一路途二中转站二路途三终点站S1557L084D35L417D01L447S0481S0148L308D28L166D32L469S04852.3.6 公汽

34、到地铁再到地铁由程序运行最终得出：对六对起点到终点找不一条路途为公汽到地铁再到地铁.2.3.7 地铁到公汽再到公汽由程序运行最终得出：对六对起点到终点找不一条路途为地铁到公汽再到公汽.2.3.8 地铁到公汽再到地铁由程序运行最终得出：对六对起点到终点找不一条路途为地铁到公汽再到地铁.（三）问题三3.1 问题分析在该问题中假设知道全部站点之间的步行时间,即随意两个站点之间都是可以到达的,只是以步行的方式来实现. 我们以两个站点之间的步行时间作为矩阵中的权. 这时构建的邻接矩阵中的权由两站点之间公汽到公汽的时间,公汽到地铁的时间,地铁到公汽的时间,地铁到地铁的时间和两点之间的步行时间构成. 3.2

35、 模型建立对于该问题遗传算法流程中基于站点序号的编码，穿插重组，染色体的变异，种群穿插，迭代的完毕条件和结果的原理与仅考虑公汽线路从起点站到终点站不转车一样. 只有在适应度函数与选择流程中每一个个体所对应的适应度函数处有所变更，其函数为：其中表示随意两个站点之间的步行时间，表示站点和之间的间隔 ，表示起始点与终点站之间的间隔 ，表示转车换乘所耗时间总和.除这之外，这一流程中的其他的原理没变. 五、模型的误差分析本文针对公交线路问题釆用的是双种群遗传算法，其中运用到的思想为基于双种群初始群体，对染色体进展整数编码，再通过竞争选择法对其染色体进展选择，根据选择性集成思想，等概率运用遗传算子分别对染

36、色体的穿插与变异进展操作，在这之中每一个算法思想均是想尽力扩大其搜寻范围，减缓其收敛度. 其中穿插率与变异率不同，就会造成结果与最优解存在不同产差异. 六、模型的评价1.模型的优点1.1 遗传算法与其他搜寻算法相比拟：遗传变异法不是干脆作用在参变量群上，而是作用在这个群的某种编码上；遗传算法从初始解群体开场搜寻，不是从单个解开场搜寻，算法具有较高的并行性；遗传算法在搜寻过程中只运用适应度函数计算，而不用导数或其他信息，具有较强的通用性；遗传算法运用概率转换规则而不是运用确定性的规则，具有全局寻优的特点. 1.2 本文设计了针对公汽线路系统特点的整数编码的遗传算法，基于两个初始种群，运用竞争选择

37、法来对染色体进展选择并保存若干最佳个体，并运用相应的等概率穿插算子和等概率变异算子实现算法，获得了良好的效果. 1.3本文所釆用的双种群遗传算法是一种并行遗传算法，它运用两个种群同时进化，并交换种群之间优秀个体所携带的遗传信息增加个体的多样性，扩展解的搜寻空间，以打破种群内的平衡态到达更高的平衡态，跳出部分最优. 收敛时最优结果，所花时间和迭代次数等方面单双种群遗传算法都优于一般遗传算法. 1.4 在进展染色体的选择时，我们采纳了一种新的赌轮选择算子离散赌轮选择算子，将有效地避开了整个群体多样性无法得到保证问题. 1.5 忽视困难计算. 例如可以对穿插操作后的修正操作适度简化甚至可以全部去掉，

38、只须要作出保证遗传可正常进展的操作即可. 2.模型的缺乏本文所釆用的算法所花费的运算时间相对其他的搜寻算法较长. 七、模型的改良及推广1.模型的改良1.1 在进展染色体变异操作中，在运用等概率变异算子时，可再参加其他的特性好且差异性较大的变异方法，运用以扩大搜寻范围. 1.2 在算法施行过程中，初始群体大小，迭代次数，穿插概率，变异概率等参数值的设定对于问题能否找到满足解起着特别重要的作用假如初始群体大小与迭代次数太小，则不简单找到最优解，反之，则计算时间长. 对于穿插概率来说，假如取值过大，则会破坏以前遗传的结果，因此穿插概率不能获得太大. 对于变异概率，其目的是为了保证算法对解空间的覆盖，

39、但其太大，会破坏遗传和穿插选出的染色体而变成随机搜寻，反之，染色体种群又会过于单调，从而陷入部分极值. 因此在实际计算时，要根据具体问题，来选择适宜的参数. 2.模型的推广 解决公汽线路问题的算法在对钻孔路途方案，物流配送系统，网络布线，铁路网优化等问题中有着广泛的应用，所以改良和讨论解决公汽线路问题的算法对实际的工业消费是有重要意义的. 八、参考文献1 张立科，MATLAB 7.0从入门到精通M，北京：人民邮电出版社，2006. 2 赵静，但琦，数学建模与数学试验（第2版）M，北京：高等教化出版社，2003. 3 汪国强，数学建模优秀案例选编M，广州：华南理工大出版社，2001. 4 阎平凡

40、，张长水，人工神经网络与模拟进化计算（第2版）M，北京：清华高校出版社，2005,（549-609）. 5 李飞，白艳萍，用遗传算法求解旅行商问题J，中北高校学报（自然科学版），28（1）：49-52，2007. 6 赵燕伟，吴斌，蒋丽，董红召，王万良，车辆途径问题的双种群遗传算法求解法J，计算机集成制造系统-CIMS， 10（30）：303-306，2004. 7 蒋望东，林士敏，基于选择性集成的整数编码遗传算法及TSP问题求解J，计算机与现代化，（5）：38-40，2007. 8 吴值民，吴凤丽，邹赟波，李雄伟，卢厚清，退火单亲求解旅行商问题及MAYLAB实现J，解放军理工高校学报（自然科

41、学版），8（1）：44-48，2007. 9 周涛，基于改良遗传算法的TSP问题讨论J，微电子学与计算机， 23（10）：104-106，2006. 九、附录附件一%产生邻接矩阵clear;clc;load bssj;i3=zeros(3958,3958);for i1=1:520 for i2=2:87 for i4=2:90 a1=data(find(data(:,1)=i1)+2),i4); a2=data(find(data(:,1)=i1)+2,i2); if a1=0 & (i4-i2)=0 %a1不为空值时，把i3矩阵赋值 i3(a2,a1)=0; elseif a1=0 & (

42、i4-i2)=1 i3(a2,a1)=3; elseif a1=0 & (i4-i2)1 i3(a2,a1)=inf; elseif a1=0 break end a3=data(find(data(:,1)=i1)+3),i4); a4=data(find(data(:,1)=i1)+3,i2); if a3=0 & (i4-i2)=0 %a1不为空值时，把i3矩阵赋值 i3(a3,a4)=0; elseif a3=0 & (i4-i2)=1 i3(a3,a4)=3; elseif a3=0 & (i4-i2)1 i3(a3,a4)=inf; elseif a3=0 break end en

43、d endendfor j1=1:3958 for j2=1:3958 if j1=j2 & i3(j1,j2)=3 i3(j1,j2)=inf; elseif j1=j2 i3(j1,j2)=0; end endend 附件二%遗传算法流程实现%yic.mclear;clc;M=30;num=3957;popm1=zeros(M,num); %生成初始群体1for k1=1:M popm1(k1,:)=randperm(num); %随机产生一个由自然数1到num 组成的全排列endpopm2=zeros(M,num); %生成初始群体2for k2=1:M popm2(k2,:)=rand

44、perm(num); %随机产生一个由自然数1到num 组成的全排列enda1=3395;a2=1828;a3=;a4=;for k3=1:30a3(k3)=abs(find(popm1(k3,:)=a1)-find(popm1(k3,:)=a2);%群体1中，不同个体a1和a2的站点差a4(k3)=abs(find(popm2(k3,:)=a1)-find(popm2(k3,:)=a2);%群体2中，不同个体a1和a2的站点差enda5=3.*a3+3956*3;%种群1的不同个体适应度a6=3.*a4+3956*3;%种群1的不同个体适应度a7=;a8=;a7=(a5./sum(a5).*1000;%种群1的不同个体选择概率a8=(a6./sum(a6).*1000;%种群2的不同个体选择概率