《数学建模电梯调度问题.pdf》由会员分享,可在线阅读,更多相关《数学建模电梯调度问题.pdf(27页珍藏版)》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、电梯调度问题电梯调度问题摘要:本题为一个电梯调度的优化问题,在一栋特定的写字楼内,利用现有的电梯资源,如何使用电梯能提高它的最大运输量,在人流密度十分大的情况下,如何更快的疏通人流成为一个备受关注的问题。为了评价一个电梯群系统的运作效率,及运载能力,在第一问中,我们用层次分析发,从效益、成本两大方面给出了六个分立的小指标,一同构成电梯群运载效率的指标体系。对第二问,本文根据题目情况的特殊性,定义忙期作为目标函数,对该电梯调度问题建立非线性规划模型,最后用遗传算法对模型求解。第三问中,本文将模型回归实际,分析假设对模型结果的影响,给出改进方案。对于问题一,本文用评价方法中的层次分析法对电梯群系统
2、的运作效率及运载能力进行分析。经分析,本文最终确定平均候梯时间、最长候车时间、平均行程时间、平均运营人数(服务强度)、平均服务时间及停站次数这六个指标作为电梯调度的指标体系。在这些评价指标的基础上,本文细化评价过程,给出完整的评价方案:首先,采用极差变换法对评价指标做无量纲化处理。然后,采用综合评价法对模型进行评价。在这个过程中,本文采用受人主观影响较小的夹角余弦法来确定权重系数。对于第二问,本文建立非线性优化模型。借鉴排队论的思想,本文定义忙期,构造了针对本题中特定情形的简单数学表达式,作为目标函数。利用 matlab 软件,采用遗传算法对模型求解。多次运行可得到多个结果,然后用第一问中的评
3、价模型进行评价,最终选出较优方案。最得到如下方案:第一个电梯可停层数为:1,2,3,4,5,6,7,10,14,15,16,19,20,22第二个电梯可停层数:1,4,5,7,10,13,16,18,19,20,21第三个电梯可停层数:1,2,3,4,6,8,10,11,12,15,16,20,22第四个电梯可停层数:1,2,3,4,7,10,11,17,18,19,21,22第五个电梯可停层数:1,2,4,7,8,9,17,18,19,20,21第六个电梯可停层数:1,4,5,6,7,8,9,11,13,18,19,20此方案平均忙期为:分钟。对于第三问,本文是从每分钟到达人群数的分布角度改
4、进模型的。第二问中假设在忙期,每分到达人数服从均匀分布,而在实际中,我们可以首先对此进行调查统计,跟据统计数据可以拟合出更符合实际分布函数,可以改进结果。关键字:电梯调度;层次分析;非线性规划;神经网络;极差法;夹角余弦一、问题重述随着社会经济的持续发展,高层建筑的数量不断增加,其建设高度更令人瞩目,电梯也开始为高层建筑的垂直交通提供保障。然而建筑高度的提升使电梯交通系统需求变得越来越复杂,有效的电梯垂直交通系统面临许多挑战。其中,人们在要求减少电梯设备占用建筑物的核心空间的同时,要求电梯交通系统的服务数量和质量有大幅度提高。特别在工作日里每天早晚上下班高峰期,电梯是非常拥挤的。如何对现有资源
5、合理利用,缓解电梯的运输压力,缩短人们的等待时间,是高层建筑垂直交通系统所必须解决的问题。由此便产生了电梯的调度问题。我们将针对对早晚高峰期的人流情况,对电梯调度问题建立数学模型,以期获得合理的优化方案。本文考虑解决以下问题:1.2.给出若干合理的模型评价指标针对该特定写字楼的简化情况给出一个合理的调度方案3.在第二问的基础上,将数学模型进一步实际化,以期能够尽量适用于实际情况,用于解决现实的电梯调度问题。二、问题分析(一)问题一的分析为了实现电梯群系统的优化调度,本文分别从效益和成本两个方向出发,考虑该数学模型的评价指标。效益即电梯的运输强度,成本即电梯运行的耗能量,其中耗能量可用平均行程来
6、反映。效益也可从多方面考虑:从服务质量的角度说,人们总是希望候梯时间与乘梯时间的总和越短越好;从服务数量的角度说,总是希望电梯交通系统具有最经济的电梯配置,同时能够提供较高的运送处理能力。在寻找指标时,需要指标既有代表性,能反映系统的工作情况,又有易衡量性,容易通过调查统计来获得。即使我们在评价模型时可以较为容易的得到评价指标数据便于人们得到评价结果。因此,本文通过层次分析发,提出了多个评价指标,包括:平均候梯时间、最长候车时间、平均行程时间、平均运营人数(服务强度)、平均服务时间及停站次数。上述个指标的单位不尽相同,为统一评价指标的属性,本文采用极差法对各指标进行无量纲化处理。指标权重的合理
7、确定是综合评价结果是否可信的一个核心问题。为减少主观影响,本文采用客观赋权值法变异系数发得到权重系数。最终建立了综合评价模型,对电梯调度模型进行评价。(二)问题二的分析本题中,已给出每层楼间电梯的平均运行时间,电梯在各层的平均停留时间,各层办公人数,电梯的最大容量。为了提高电梯的使用率,我们通过电梯的分组管理每组的电梯只可在特定的楼层停留,不同组的可停层数不同来达到对电梯运行的时间的优化。具体对每种方案,我们要确定如下三组数据:1.分为几组;2.每组有多少个电梯;3.每组分别可达的楼层。本问题非一般的线性优化模型,因此本题选用遗传算法求解。第一问提供了多个评价指标,若综合考虑这些指标,则问题归
8、结为一个多目标规划问题,情况就会较为复杂。由于其中许多指标在该特定情况(针对早晚上下班高峰期的电梯运行情况)下的影响甚微,于是可以得到简化的规划模型。如:服务时间。每个人从进入电梯开始至到达目的楼层所需时间的可变行小。从概率角度说,当乘电梯的人较多时,每一时刻电梯内人的目的楼层会基本覆盖所有电梯可达楼层,即可视为:电梯会在每个可达楼层停留。所以,优化模型中可以不考虑此项指标。平均行程时间。针对早晚高峰期,人流方向是相当固定的。例如:在上班高峰期,几乎所有人都是从一层进入,分别到达个各楼层,而中途只下不上。因此个各电梯的运行路程都是从一层到达该电梯能到达的最高层再下来,如此做往复运动。在特定的电
9、梯分组方案中,该项指标的可变性也不大。本文通过对各种可能影响因素的细致分析,分析各个指标的可能表达情况及影响因素,考虑考虑增大电梯单位时间的运载量,减少人们的等待时间是大家更为关注的问题,直接的想法为:从每个等待个体角度出发,以等待时间为目标函数。但这种方法表达式复杂,不易在遗传算法里实现。因此我们变换思路,从电梯角度出发,以电梯最大运载能力为目标,针对本题当人流蜂拥而至时,我们选取将所有人全部运到目的楼层电梯组所需的总时间为目标函数,并作为适应值函数,在遗传算法中作为选择算子进行计算。(三)对问题三的分析在问题二中的模型中用了一些假设使得模型与实际有写偏差。本文的视角不同也会对模型的对实际情
10、况的拟合度有影响。在第三问中,我们将根据第二问的运行结果,结合实际,改进模型。三、模型假设1.假设人们均在特点时间段达到,并在该时间中,每时刻到达人数服从均匀分布;2.假设每层楼之间电梯的平均运行时间是 3 秒,最底层(地上一层)平均停留时间是 20 秒,其他各层若停留,则平均停留时间为 10 秒,电梯在各层的相应的停留时间内乘梯人员能够完成出入电梯;3.假设各层人员都乘坐电梯,并对电梯无偏见;4.假设人们都在忙期到达,忙期内到达人数服从均匀分布;5.假设每个电梯在运行时都满载。四、定义与符号说明等待时间N停站次数(第一项评价指标)T平均服务时间(第二项评价指标)R平均运营人数(第三项评价指标
11、)r平均运行时间(第四项评价指标)m最长等待时间(第五项评价指标)平均等待时间(第六项评价指标)aij表示第i种方案关于第j项评价因素的指标值AiT=(ai1,ai2.ai3,ai4,ai5,ai6)是底i个方案关于这六项评价指标的指标值向量TTTA A1T,A2,A3,An为n个决策方案的集合Hibijwj第i个指标的综合评价得分j16k第k个电梯l第l层Rl第l层办公人数nk第k个电梯完成总目标的运行次数xkl第k个电梯在l层的停留情况Xk(xk1,xk2,xk22)为第k个电梯的运行模式TTTTTX (X1T,X2,X3,X4,X5,X6)为这六个电梯组的运行模式,及电梯组的调度情况W电
12、梯群的忙期的长短W电梯的平均忙期tk第k个电梯单次运行时在楼层停留时间rk第k个电梯单次运行时在楼层间行进时间nk表示第k个电梯在忙期运行次数F(Xk):第k个电梯单次运行时间五、模型的建立与求解(一)问题一 电梯调度的评价模型1)用层次分析法1寻找评价指标。对模型进行评价首先要找出合理的评价指标。因此我们采用层次分析法,对模型全面分析,寻找评价指标。对此,我们分别从效益、成本两个方面出发,建立了如下层次图,如图一:图中,从左至又,分别表示第 j 项评价因素,其中 j=1,2,3,4,5,6。aij表示第 i 种方案关于第 j 项评价因素的指标值。AiT=(ai1,ai2.ai3,ai4,ai
13、5,ai6)是底i个方案关于这六项评价指标的指标值向量TTTA A1T,A2,A3,An为 n 个决策方案的集合2)运用极差变换法2建立无量纲的效益型矩阵B。变换公式为:(maxaijaij)j(j1,4)(maxaijminaij)jjB(bij)n6,bij(amina)ijijj(j2,3,5,6)(maxaminaij)jiij3)计算评价指标的权重。运用夹角余弦法3由矩阵B来确定各指标的权重。夹角余弦法的基本概念:由无量纲的效益矩阵B (bij)n*m,则可得到各方案与理想最佳和最劣的相对偏差矩阵为:U (uij)n*m,V (vij)n*m式中,uijmaxbijbijjmaxbi
14、jminbijjj,vijbijminbijmaxbijminbij,再计算 U,V 对jjj应列向量的夹角余弦得到初始权重,归一化后得到客观性权向量w。运用夹角余弦法建立客观性权重向量。首先由指标矩阵 A 得到各方案与理想最佳和最劣方案的相对偏差矩阵 R 与矩阵 T,然后求出 R 与 T 两矩阵对应列向 量 的 夹 角 余 弦,并 最 为 初 始 权 重,归 一 化 后 得 到 客 观 性 权 向 量w (w1,w2,w3,w4,w5,w6).4)计算综合评价值。由矩阵B可得到第i个指标的综合评价得分Hibijwj,且Hi值越大越好。j16用 matlab 编程,对给定的评价矩阵可以直接计算
15、出结果。程序见附录:(二)问题二 电梯调度的优化模型1.建立优化模型。通过分析,本文首先对电梯调度方案进行量化,即要表达出电梯分组情况和每组电梯可停留楼层的情况。因此我们用六个向量分别表示各个电梯可停留楼层的情况,具体如下:我们用 0-1 变量xkl表示第 k 个电梯在 l 层停留情况(表示第1k个电梯在l层停留xkl0k个电梯不在l层停留)(表示第Xk(xk1,xk2,xk22)为第 k 个电梯的运行模式;为这六个电梯组的运行模式,及电梯组的调TTTTTX (X1T,X2,X3,X4,X5,X6)度情况;在早晚人流高峰期时,常常会造成人流拥堵,即会在某个连续的时间段内,等待接受服务的人数大于
16、电梯所能提供服务的最大人数,这就使部分人不能及时接受到服务,引用排队论里的说法就是队长超过了一定的限额。在这段时间内,电梯每次都应是最高效率工作,对上班高峰期来说,就是每次会在第一层满载后再上楼,对下班高峰期来说,就是电梯下到第一层是满载情况。本文定义此段时间为忙期。因此本文选取忙期的长短作为衡量电梯运行的效率的指标,以此来作为目标函数,对电梯群的调度情况进行优化。电梯群的调度情况用一个矩阵来表示,即X。目标函数的表示,即忙期的长短,本文记做 W。首先考虑上班高峰期。在这期间,人们大多到达时间比较集中,不妨假设所有人均在忙期到达,等待接收服务,并且每个时刻到达的人数服从均匀分布。则忙期即为电梯
17、把人全部运到指定楼层所用的时间。这又可以表示为每个电梯往复一次的运行时间乘以运行次数得到值的最大值。在这期间,人的流动方向是固定的,在忙期,乘电梯的人较多,所有从概率的角度来讲,每一时刻电梯内人的目的楼层会基本覆盖所有电梯可达楼层,即可视为:电梯会在每个可达楼层停留。因此第 k 个电梯单次运行时间内,在楼层停留的时间可以表示为:tk10 xkll122在楼层间行进时间为:rk2*3(l1)xkll122则第 k 个电梯单次运行时间为:F(Xk)10 xkl2*3(l1)xkll1l12222nk表示第 k 个电梯在忙期运行次数则nk满足的条件为:20*k16Rlxl122*nkxklRlRlk
18、l因此,电梯群的忙期可以表示为:W G(X)max nk(F(Xk)20)20每个电梯的平均忙期为:W(nk16k(F(Xk)20)20)6对于每组Xk,相同的为一组;2.模型求解本文采用遗传算法求解。标准的遗传算法可用 6 个参数来描述。GA (P0,M,t)P0是初始群体,M是总体体积,是选择运算,是杂交算子,是变异算子,t是停机条件。因为Xk,X均为 0-1 构成的矩阵,可直接作为遗传编码,即:Xk为染色体X为个体的染色体组1)遗传算子:重要的遗传算子有 3 种:选择、交叉和变异.选择是指从当前种群中根据适应度的高低将个体直接复制到下一代种群的过程.交叉是遗传算法中最重要的步骤,它对遗传
19、算法的性能和收敛影响很大,通过交叉,种群中的优良基因得到保存与传播.变异发生的概率一般很小,变异操作的目的是为了保持基因的多样性。42)选择:将种群中的个体按适应度从高到低排序,选择概率为 Ps,选定适应度最小的最后共 POP-SI ZE*P s个个体,将其淘汰。从高适应度的个体中选取若干个做父体,使用下述的交叉、变异等操作生成同样数量的新子代补充至种群中。3)交叉:每层基因各自进行一次交叉操作。对于第一、二层,使用较小的交叉概率进行单点交叉,即根据交叉概率 P c1=P c2=0005 在基因组上选定一个数位作交叉点,互换两父体交叉点后的基因。对于第三层,使用较大的交叉概率进行两点交叉,交叉
20、概率 Pc3=001。4)变异:变异也是各层独立进行。对于第一、二层,以变异概率 Pm1=Pm2=,确定 u 个变异位置 S1,S2,S3,Su,将这些位置上的基因取反。对于第三层,以变异概率 Pm3=确定变异位置后,将这些位置上的数换成一个-10,10间的高斯分布随机小数,即:Wi,j=Gaussian(-10,10)式中 Gaussian(-10,10)表示呈高斯分布的-10,10间的随机小数。5)迭代判断:若遗传最大迭代次数已到,判断种群中是否出现了网络总误差 E 达到用户指定精度的个体,如果有,则选出适应度最大者作为迭代结果,如果没有,则本次运算不收敛;若未完成迭代,计算各染色体的适应
21、度,并将各染色体按适应度从高到低排序,转“选择”处继续。56)适应值函数:为了引导遗传搜索,应定义一个适应度函数。电梯调度问题的目的是将忙期尽可能缩小,即将G(X)最小化。然而,遗传算法则是努力将基因的适应度函数最大化,基于该原因,适应度函数定义如下:S1/G(X)平均电梯忙期时间更容易表达,且可以缩短计算时间,并且效果也相当,因此我们用W(X)代替G(X),将其倒数作为适应值函数。根据以上的基因表示,设计相应的遗传操作并定义适应度函数,遗传算法可以得以实现。程序流程图如下所示:初始化参数随机生成初始群计算初始群适应值是否满足循环次数是输出最优结果选择交叉循环次数+1变异计算新群适应值新群替换
22、原群记录最优结果将程序运行多次得到多个优化结果:3.结果整理1)方案一:第一次运行结果:Bestpopulation=Columns 1111101Columns 23101100Columns 45111011Columns 67010111Columns 89000100Columns 111111100through221110through441000through660111through881101through1100010through132101111100001000101000101110000111001101010000010110000110000111100111
23、0010110Besttargetfunvalue=918(说明:说明:程序设计所求的程序设计所求的 BesttargetfunvalueBesttargetfunvalue 是六个电梯是六个电梯忙期的累忙期的累 加和,即加和,即 6 6W(X)W(X),且单位是秒,即且单位是秒,即 918918 秒秒)程序运行的适应度函数图像为:即:第一个电梯可停层数为:1,2,3,4,5,6,8,12,14,15,16,19,20,22第二个电梯可停层数,1,3,4,8,10,12,13,15,17,20第三个电梯可停层数:1,2,3,5,6,7,8,9,11,16,18,19,21,22第四个电梯可停层
24、数:1,2,4,5,7,10,15,18,19,20第五个电梯可停层数:1,6,11,15,18,19,20第六个电梯可停层数:1,2,3,4,6,7,10,11,12,15,17,18,20这六个电梯的平均忙期为:分钟2)方案二:3)第二次运行结果Bestpopulation=Columns 1through221111111001000111001101Columns 23through4410011010110Columns 45through6601110101101Columns 67through8801110010011Columns 89through1100101001111
25、0Columns 111 through13210011111100Besttargetfunvalue=918程序运行的适应度函数图像为:0100110111001010101000000000100101100010010001100111111即:第一个电梯可停层数为:1,2,3,4,5,6,7,10,14,15,16,19,20,22第二个电梯可停层数:1,4,5,7,10,13,16,18,19,20,21第三个电梯可停层数:1,2,3,4,6,8,10,11,12,15,16,20,22第四个电梯可停层数:1,2,3,4,7,10,11,17,18,19,21,22第五个电梯可停层
26、数:1,2,4,7,8,9,17,18,19,20,21第六个电梯可停层数:1,4,5,6,7,8,9,11,13,18,19,20这六个电梯的平均忙期为:分钟4)方案三:第三次运行结果Bestpopulation=Columns 1through2211111110010Columns 23through4411111111111Columns 45through6600100011111Columns 67through8810101101100Columns 89through11011000011101Columns 111 through13201100100111Besttarge
27、tfunvalue=918程序运行的适应度函数图像为:110001011010110111000011010110000111010111010011000100001000011110即:第一个电梯可停层数为:1,2,3,4,5,6,7,9,10,16,21第二个电梯可停层数:1,2,3,4,5,6,7,8,11,13,14,15,16,17,18,20,21,22第三个电梯可停层数:1,3,7,8,10,11,13,16,20,21,22第四个电梯可停层数:1,3,5,6,810,12,13,16,17,19,20第五个电梯可停层数:1,2,7,8,9,10,18,19,20,22第六个电
28、梯可停层数:1,2,3,6,9,10,11,12,13,14,15,18,20,21,22这六个电梯的平均忙期为:分钟4.结果分析对以上三种方案进行评价:方案一:单次运行的停车次数:68平均运营人数:300(总人数/总时间)方案二:单次运行的停车次数:70平均运营人数:300(总人数/总时间)方案三:单次运行的停车次数:75平均运营人数:300(总人数/总时间)得到不完整的评价矩阵为:68300A7030075300比较三种结果我们采用第一种方案即:运行第一题的程序得到各个第一个电梯可停层数为:1,2,3,4,5,6,7,10,14,15,16,19,20,22第二个电梯可停层数:1,4,5,
29、7,10,13,16,18,19,20,21第三个电梯可停层数:1,2,3,4,6,8,10,11,12,15,16,20,22第四个电梯可停层数:1,2,3,4,7,10,11,17,18,19,21,22第五个电梯可停层数:1,2,4,7,8,9,17,18,19,20,21第六个电梯可停层数:1,4,5,6,7,8,9,11,13,18,19,20(三)问题三 模型修正在第二问的模型中,我们假设人们均在忙期到达,在忙期中,每分钟到达人数服从均匀分布,这点不大符合实际。事实上,不可能每个人都在忙期到达。若用泊松分布代替平均分布,计算当在一定时间内到达人数超过某一特定值时则进入忙期,应该会更
30、接近实际,而这需要通过实际调查,找出统计数据,根据统计数据确定分布函数的参数。或者是根据实际数据拟合出其他形式的找到最符合的每分钟到达人数分布函数。为简化模型求解,问题二的模型只选取了其中一个角度作为优化的目标函数,也就是说我们在优化时以尽快疏散到达人群为首要目标。虽然这已经可以较好的反映问题,但在写字楼中,人流大的时间较短,且人流总量有限,忙期持续时间不会太长。它毕竟不同于火车站、飞机场,人流动量十分可观,且忙期较长,一旦造成人流的拥堵这影响时间长,要求有最快的运输能力。电梯系统的服务范围小,因此我们将忙期限制在某个范围内就行,然后将其作为一个约束条件放在该规划模型中。这样我们可以对每个人的
31、最长的等待时间最短为目标,及模型可以优化为当使电梯的忙期在一定范围内时,如果能让每个人的最长等待时间缩短,那么将会更满足人们的需要。当然,这个范围的确定,要参照第二问的结果,不能太高也不能太低。六、对模型的评价比较上述模型的多次运行结果,每次方案虽略有不同,但他们的平均电梯忙期是相同的,可以认为,这种方法是可靠的。但是单看 15 分钟左右的忙期也略微显长。求出六个电梯在每层都可停的方案在本文的假设下的平均忙期值,这可通过比较我们的节约时间来评价。而对模型的评价也很不充分,应该将优化后的调度方案的结果与不加调度方案的结果相比较。而问题一中的评价指标均易通过实际调查来获得,通过统计数据的简单处理便
32、可以得到满意的评价指标矩阵,但由于我们不能得第一手资料,所以得到完整可信的评价指标值是很困难的,本文也只是在理论上阐述了评价方案和计算程序。七、参考文献1 喻湘存,熊曙初.系统工程教程.北京:清华大学出版社 北京交通大学出版社,227-2372 马莉.MATLAB 数学实验与建模.北京:清华大学出版社,2010.121-1234 席卫东,乔兵,朱剑英 基于改进遗传算法的柔性作业车间调度J.哈尔滨工业大学学报,2007,第 39 卷第 7 期:1152-11535 冯锋,徐 琪.基于神经网络模式的遗传算法在 CRM 的数据挖掘优化研究J黑龙江大学自然科学学报,2010,第 27 卷第六期:798
33、八、附录一:评价模型的 matlab 程序:A=;.A=;.;%运用极差法建立无量纲运用极差法建立无量纲的效益矩的效益矩阵阵 B BB=(A(:,1:3)-ones(4,1)*min(A(:,1:3),(ones(4,1)*max(A(:,4:5)-A(:,4:B=(A(:,1:3)-ones(4,1)*min(A(:,1:3),(ones(4,1)*max(A(:,4:5)-A(:,4:5),.5),.A(:,6)-min(A(:,6)./(ones(4,1)*range(A)A(:,6)-min(A(:,6)./(ones(4,1)*range(A)%理想最佳和最劣方案向量理想最佳和最劣方
34、案向量 U U 与与 V VU=max(A(:,1:3),min(A(:,4:5),max(A(:,6)U=max(A(:,1:3),min(A(:,4:5),max(A(:,6)V=min(A(:,1:3),max(A(:,4:5),min(A(:,6)V=min(A(:,1:3),max(A(:,4:5),min(A(:,6)%计计算相算相对对偏差矩偏差矩阵阵 R R 与与 T TR=abs(A-ones(4,1)*U)./(ones(4,1)*range(A)R=abs(A-ones(4,1)*U)./(ones(4,1)*range(A)T=abs(A-ones(4,1)*V)./(o
35、nes(4,1)*range(A)T=abs(A-ones(4,1)*V)./(ones(4,1)*range(A)%运用夹运用夹角余弦法建立角余弦法建立权权重向量重向量 w wr=normc(R);r=normc(R);t=normc(T);t=normc(T);w=sum(r.*t)/sum(sum(r.*t)w=sum(r.*t)/sum(sum(r.*t)%计计算算综综合合评评价价值值H=B*(w)H=B*(w)附录附录二:matlab 的遗传算法设计:%遗传遗传算法主程序算法主程序popsize=50;%popsize=50;%初始种初始种群大小群大小Generationnmax=1
36、00;%Generationnmax=100;%最大代数最大代数pcrossover=;%pcrossover=;%交配概率交配概率pmutation=;%pmutation=;%变变异概率异概率%产产生初始生初始种种群群population=round(rand(popsize,132);population=round(rand(popsize,132);%计计算适算适应应度度,返回适应度返回适应度 FitvalueFitvalue 和累积和累积概率概率 cumsumpcumsumpFitvalue,cumsump=fitnessfun(population);Fitvalue,cumsu
37、mp=fitnessfun(population);Generation=1;Generation=1;while GenerationGenerationnmax+1while GenerationGenerationnmax+1 for j=1:2:popsize for j=1:2:popsize%选择选择操作操作 seln=selection(population,cumsump);seln=selection(population,cumsump);%交叉操作交叉操作 scro=crossover(population,seln,pcrossover);scro=crossover(
38、population,seln,pcrossover);scnew(j,:)=scro(1,:);scnew(j,:)=scro(1,:);scnew(j+1,:)=scro(2,:);scnew(j+1,:)=scro(2,:);%变变异操作异操作 smnew(j,:)=mutation(scnew(j,:),pmutation);smnew(j,:)=mutation(scnew(j,:),pmutation);smnew(j+1,:)=mutation(scnew(j+1,:),pmutation);smnew(j+1,:)=mutation(scnew(j+1,:),pmutation
39、);end end population=smnew;%population=smnew;%产产生了新的生了新的种种群群%计计算新算新种种群的适群的适应应度度 Fitvalue,cumsump=fitnessfun(population);Fitvalue,cumsump=fitnessfun(population);%记录记录当前代最好的适当前代最好的适应应度和平均适度和平均适应应度度 fmax,nmax=max(Fitvalue);fmax,nmax=max(Fitvalue);fmean=mean(Fitvalue);fmean=mean(Fitvalue);ymax(Generatio
40、n)=fmax;ymax(Generation)=fmax;ymean(Generation)=fmean;ymean(Generation)=fmean;%记录记录当前代的最佳染色体个体当前代的最佳染色体个体 x=population(nmax,:);x=population(nmax,:);Generation=Generation+1 Generation=Generation+1endendGeneration=Generation-1;Generation=Generation-1;Bestpopulation=xBestpopulation=xBesttargetfunvalue=
41、targetfun(x)Besttargetfunvalue=targetfun(x)%绘绘制制经过遗传经过遗传运算后的适运算后的适应应度曲度曲线线。figure(1);figure(1);hand1=plot(1:Generation,ymax);hand1=plot(1:Generation,ymax);set(hand1,linestyle,-,linewidth,marker,*,markersize,6)set(hand1,linestyle,-,linewidth,marker,*,markersize,6)hold on;hold on;hand2=plot(1:Generati
42、on,ymean);hand2=plot(1:Generation,ymean);set(hand2,color,r,linestyle,-,linewidth,.set(hand2,color,r,linestyle,-,linewidth,.marker,h,markersize,6)marker,h,markersize,6)xlabel(xlabel(进进化代数化代数);ylabel();ylabel(最大最大/平均适应平均适应度度);xlim(1 Generationnmax););xlim(1 Generationnmax);legend(legend(最大适应最大适应度度,平均适
43、应平均适应度度););box off;hold off;box off;hold off;%子程序:新种子程序:新种群交叉操作群交叉操作,函数名称存储为函数名称存储为function scro=crossover(population,seln,pc);function scro=crossover(population,seln,pc);BitLength=size(population,2);BitLength=size(population,2);pcc=IfCroIfMut(pc);%pcc=IfCroIfMut(pc);%根据交叉概率决定是否进根据交叉概率决定是否进行交叉操作,行交叉
44、操作,1 1 则则是,是,0 0 则则否否if pcc=1if pcc=1 chb=round(rand*(BitLength-2)+1;%chb=round(rand*(BitLength-2)+1;%在在1,BitLength-11,BitLength-1范围范围内随机内随机产产生一个生一个交叉位交叉位 scro(1,:)=population(seln(1),1:chb)scro(1,:)=population(seln(1),1:chb)population(seln(2),chb+1:BitLength);population(seln(2),chb+1:BitLength);scr
45、o(2,:)=population(seln(2),1:chb)scro(2,:)=population(seln(2),1:chb)population(seln(1),chb+1:BitLength);population(seln(1),chb+1:BitLength);elseelse scro(1,:)=population(seln(1),:);scro(1,:)=population(seln(1),:);scro(2,:)=population(seln(2),:);scro(2,:)=population(seln(2),:);endend%子程序:计子程序:计算适算适应应度
46、函数度函数,函数名称存储为函数名称存储为 fitnessfunfitnessfunfunction Fitvalue,cumsump=fitnessfun(population);function Fitvalue,cumsump=fitnessfun(population);popsize=size(population,1);%popsize=size(population,1);%有有 popsizepopsize 个个体即个个体即 5050for i=1:popsizefor i=1:popsize x=population(i,:);x=population(i,:);Fitvalu
47、e(i)=targetfun(x);%Fitvalue(i)=targetfun(x);%计计算函数算函数值值,即适,即适应应度度endend%计计算算选择选择概率概率fsum=sum(Fitvalue);fsum=sum(Fitvalue);Pperpopulationl=Fitvalue/fsum;Pperpopulationl=Fitvalue/fsum;Pperpopulation=Pperpopulationl;Pperpopulation=Pperpopulationl;%计计算累算累积积概率概率cumsump(1)=Pperpopulation(1);cumsump(1)=Ppe
48、rpopulation(1);for i=2:popsizefor i=2:popsize cumsump(i)=cumsump(i-1)+Pperpopulation(i);cumsump(i)=cumsump(i-1)+Pperpopulation(i);endendcumsump=cumsump;cumsump=cumsump;%子程序:判断遗传子程序:判断遗传运算是否需要运算是否需要进进行交叉或行交叉或变变异异,函数名称存储为函数名称存储为function pcc=IfCroIfMut(mutORcro);function pcc=IfCroIfMut(mutORcro);test(1
49、:100)=0;test(1:100)=0;l=round(100*mutORcro);l=round(100*mutORcro);test(1:l)=1;test(1:l)=1;n=round(rand*99)+1;n=round(rand*99)+1;pcc=test(n);pcc=test(n);%子程序:新种群变异操作,函数名称存储为function snnew=mutation(snew,pmutation);function snnew=mutation(snew,pmutation);BitLength=size(snew,2);BitLength=size(snew,2);sn
50、new=snew;snnew=snew;pmm=IfCroIfMut(pmutation);%pmm=IfCroIfMut(pmutation);%根据变根据变异概率决定是否异概率决定是否进进行行变变异操作,异操作,1 1 则则是,是,0 0 则则否否if pmm=1if pmm=1 chb=round(rand*(BitLength-1)+1;%chb=round(rand*(BitLength-1)+1;%在在1,BitLength1,BitLength范围范围内随机内随机产产生一个生一个变变异位异位 snnew(chb)=abs(snew(chb)-1);snnew(chb)=abs(s