（交通运输规划与管理专业论文）公共交通客流OD矩阵推算方法研究.pdf

t h es t u d p u b l i c f o rt h e b y z h a 0j i n h u a n s u p e r v i s e db y p r o f l iw e n q u a n s c h o o lo f t r a n s p o r t a t i o n s o u t h e a s tu n i v e r s i t y n a n j i n g j a n2 0 1 0 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表或撰写过的研究成果，也不包含为获得东南大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 研究生签名：匙主垦逸日期：址y 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位 论文的复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人 电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论 文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分内容。论文的公布( 包 括刊登) 授权东南大学研究生院办理。 研究生签名：凄查圭暨盘导师签名：弛 f 摘要 一摘要 公共交通客流o d 矩阵是城市公交网络规划和管理的基础数据，为公交线网优化布设、 公交运营调度提供最可靠的数据支持，只有精确的客流o d 才能保证运营计划科学制定，人、 车资源合理调配。因此本文分别从单条公交线路和公交网络着手，对公交客流o d 矩阵推算 方法进行研究。 + 二 ” 公交客流量是o d 矩阵推算的基础，针对短期公交客流的非线性、随机性和复杂性，本 文提出一种基于最小二乘支持向量机的公交客流预测方法，并且利用改进的遗传算法对支持 向量机中的惩罚参数和核参数进行优化。算例分析结果证实了本文方法的有效性。 针对单条公交线路，本文以公交停靠站上下车人数为基础，提出客流0 d 矩阵受居民出 行特征、停靠站附近用地性质以及停靠站换乘功能这三个因素影响。首先通过k - s 检验可 知出行站数服从泊松分布，进一步计算即可获得基于居民出行特征的客流o d i 然后提出公 交站点的吸引系数和吸引权等概念，建立基于停靠站附近用地性质的客流o d 推算模型；考 虑到停靠站的重要系数与该站的起始、终点和中途停靠的线路数有关，建立了基于站点换乘 功能的客流o d 推算模型。最后利用层次分析法组合上述三个模型，得到公交客流o d 矩阵， 并进行算例分析。 对于公交网络，本文给出一种基于双层规划的公交网络o d 矩阵推算方法：其中上层规 划的目标函数选择广义最小二乘模型，由先验o d 矩阵与估计o d 矩阵的误差以及上车的乘 客数与公交网络分配乘客的误差组成；考虑到公交线路容量限制以及发车频率可变的条件， 下层规划采用基于l o g i t 模型的公交网络随机用户分配模型( s u e ) 进行客流分配。最后采 用粒子群优化算法求解双层规划模型。对比实验结果表明由本文方法获得的o d 矩阵的精度 比启发式算法得到的更高 本文最后从o d 推算的对象、数据要求、计算复杂性、适应性等角度，对提出的两种推 算方法进行对比分析。 关键词：公交客流，o d 矩阵，最d 、- - - - 乘支持向量机，双层规划，粒子群优化，推算 a b s t r a c t p u b l i ct r a n s p o r tp a s s e n g e rf l o wo r i g i n - d e s t i n a t i o nm a t r i xi st h eb a s i cd a t ai nu r b a np u b l i c n e t w o r kp l a n n i n ga n dm a n a g e m e n t ，w h i c hp r o v i d e st h em o s tr e l i a b l es u p p o r tf o rt h eb u sn e t w o k o p t i m i z a t i o na n dp u b f i cu m l s p o r ts c h e d u l i n g o n l yt h ea c c u r a t et r a f f i cf l o wo dc a ne n s u r et h e s c i e n t i f i co p e r a t i o np l a n sa n dr a t i o n a lu t i l i z a t i o no fs t a f f sa n dv e h i c l e s t h e r e f o r e ，t h eo dm a t r i x e s t i m a t i o no f p u b l i ct r a n s p o r ti ss t u d i e d ，s e p a r a t e l yf r o mas i n g l eb u sl i n ea n db u sn e t w o r k p u b l i ct r a n s p o r t a t i o nf l o wi st h eb a s eo fo dm a t r i xe s t i m a t i o n t h ep a p e rp r e s e n t san e w t r a n s i tf l o wp r e d i c t i o nm o d e lb a s e do nl e a s t s q u a r e ss u p p o r tv e c t o rm a c h i n ek s - s v m ) ， a c c o r d i n gt ot h ef l o w sc h a r a c t e r i s t i c so fn o n - l i n e a r , s t o c h a s t i ca n dc o m p l e x i m p r o v e dg e n e t i c a l g o r i t h m ( g 舢i su s e dt oo p t i m i z ep e n a l t yp a r a m e t e ra n dn u c l e a rp a r a m e t e r n u m e r i c a le x a m p l e s s h o wt h ev a l i d i t yo f t h ea p p r o a c h f o rt h es i n g l eb u sl i n e ，t h ea r t i c l ep u t sf o r w a r dt h ei d e at h a tt r a 伍cf l o wo di sa f f e c t e db yt n p c h a r a c t e r i s t i c s ，l a n du s e a n dt r a n s f e r r i n gf u n c t i o na r o u n db u ss t o p s ，c o m b i n e dw i t ht h ep a s s e n g e r s b o a r d i n ga n da l i g h t i n g f i r s t l y , t h ek - st e s ti sa d o p t e dt oa n a l y z et h es t a t i o nn u m b e r so f p u b l i ct r i p a n dt h er e s u l ts h o w si tf o l l o w sap o i s s o nd i s t r i b u t i o n ，a n dt h e nt h eo de s t i m a t i o nb a s e do nt r i p c h a r a c t e r i s t i c si s p r e s e n t ；s e c o n d l y , t h ep a p e rp r o p o s e st h ec o n c e p t i o ni n c l u d i n ga t t r a c t i n g c o e f f i c i e n ta n da t t r a c t i n gw e i g h t , a l s ow ec a ng e tt h eo dm a l r i xe s t i m a t i o nb a s e do nt h el a n du s e ； b e s i d e s ，t h ep a 矗p u t sf o r w a r dt h a tt h es t o ps i g n i f i c a n tc o e f f i c i e n ti sr e l a t e dt ob u sr o u t en u m b e r s o fs t a r t i n g , e n d i n ga n dm i d w a y , a n dt h eo de s t i m a t i o nb a s e do nt r a n s f e r r i n gf u n c t i o ni sp r e s e n t t h el a s t ，a h pi su s e dt oc o m b i n et h ea b o v et h r e ei n f l u e n c ef a c t o r sa n do b t a i n st h eo dm a t r i x f u r t h e rm o r e ，n u m e r i c a le x a m p l e sa r eg i v e n a b o u tt h ep u b l i ct r a n s p o r tn e t w o r k , b i - l e v e lp r o g r a m m i n gm o d e li sp r e s e n tf o ro dm a t r i x e s t i m a t i o n t h eg e n e r a l i z e dl e a s ts q u a r e sm o d e li ss e l c e t e d 弱u p p e ro b j e c t i v ef u n c t i o n , w h i c h c o n t a i n st h ee r r o rb e t w e e np r i o r io dm a t r i xa n dt h ee s t i m a t e do dm a u i x ，t o g e t h e rw i t ht h ee r r o r b e t e e np a s s e n g e r sb o a r d i n ga n dp a s s e n g e r sa s s i g n e db yp u b l i ct r a n s p o r tn e t w o r k t a k i n gi n t o a c c o u n tc a p a c i t yc o n s t r a i n t sa n de l a s t i cl i n ef r e q u e n c y , t h el o w e rp r o g r a m m i n ga d o p t ss t o c h a s t i c u s e re q u i l i b r i u m ( s u e ) a s s i n g m e n tm o d e l ，b a s e do nt h el c i g i tm o d e l t h e np a r t i c l es w a r m o p t i m i z a t i o ni sg i v e nt os o v l et h eb i - l e v e lp r o g r a m m i n gm o d e lt h ec o n t r a s tt e s ts h o w s t h eh i g h e r p r e c i s i o nu s i n gt h ep r e s e n tm e t h o dt h a nh e r i s t i ca l g o r i t h m t h ef i n a l l y , t h et w oe s t i m a t i o nm e t h o d sa r ec o m p a r e af r o mo b j e c t , d a t ar e q u i r e m e n t ， c o m p u t a t i o n a lc o m p l e x i t ya n da d a p t a b i l i t y , a n ds oo n k e yw o r d s ：p u b h ct r a n s p o r tp a s s e n g e rf l o w , o dm a t r i x , l e a s ts q u a r e ss u p p o r tv e c t o r m a c h i n e ，b i l e v e lp r o g r a m m i n gm o d e l ，p a r t i c l es w a r mo p t i m i z a t i o n ，e s t i m a t i o n 目录 目录 摘要】【 a b s t r a c t i i l ；i 录 第一章绪论1 1 1 研究背景及意义1 1 2 研究概况- - 2 1 2 1 国外研究概况2 1 2 2 国内研究概况2 1 2 3 国内外研究总结3 1 3 研究目标和主要内容3 1 3 1 研究目标3 1 3 2 主要内容。4 1 4 重点难点和解决办法4 1 5 论文主要结论及组织结构5 1 6 本章小结6 第二章基于最小二乘支持向量机的公交客流预测7 2 1 最小二乘支持向量机概述7 2 1 1 支持向量机原理。7 2 1 2 支持向量回归机7 2 1 3 支持向量机中的核参数8 2 1 a 最小二乘支持向量机8 2 2 基于遗传算法的最小二乘支持向量机参数优化1 0 2 2 1 遗传算法原理l o 2 2 2 评价指标1 1 2 2 3 遗传算法设计1 2 2 3 基于最d x - - 乘支持向量机的公交客流预测模型。1 3 2 3 1 公交客流影响因素分析1 3 2 3 2 模型建立及其求解1 4 2 4 算例分析1 5 2 4 1 公交客流年客运量预测l5 2 4 2 短期公交客流预测1 7 2 5 本章小结2 1 第三章单条公交线路客流0 d 矩阵推算2 2 3 1 公交线路客流o d 矩阵推算原理2 2 3 2 基于不同影响因素的公交客流o d 矩阵推算。2 3 3 2 1 基于乘客出行行为特征的公交客流o d 矩阵推算2 3 3 2 2 基于公交停靠站附近用地性质的公交客流o d 矩阵推算2 5 3 2 3 基于公交停靠站换乘功能的公交客流o d 矩阵推算2 7 3 3 基于层次分析法的公交客流组合o d 矩阵推算2 8 3 3 1 层次分析法介绍2 8 3 3 2 层次分析法组合三个影响因素的公交客流o d 矩阵3 0 3 4 算例分析31 1 i 目录 3 5 本章小结3 6 第四章基于双层规划的公交网络0 d 矩阵推算模型建立3 7 4 1 机动车0 1 3 矩阵推算3 7 4 1 1 机动车o d 矩阵推算基本原理3 7 4 1 2 常用的o d 矩阵推算模型3 7 4 2 基于双层规划的公交客流o d 矩阵推算。3 8 4 2 1 双层规划基本原理3 8 4 2 2 基于双层规划的公交客流o d 矩阵推算形式3 9 4 3 公交网络客流分配技术3 9 4 3 1 公交网络客流分配技术概述4 0 4 3 2 公交网络表示方法4 0 4 3 3 容量限制下的公交网络随机用户平衡分配模型4 2 4 3 4 发车频率可变的公交网络客流分配4 6 4 3 5 公交客流分配求解方法4 8 4 4 基于双层规划的公交网络o d 矩阵推算模型4 9 4 5 本章小结。4 9 第五章公交网络0 d 矩阵双层规划模型求解5 0 5 1 双层规划模型求解方法概述5 0 5 2 基于粒子群优化算法的双层规划模型求解5 0 5 2 1 粒子群优化算法5 0 5 2 2 模型求解5 2 5 3 算例分析5 3 5 4 两种推算方法对比研究5 6 5 5 本章小结。5 7 第六章结论与展望5 8 6 1 论文主要研究内容5 8 6 2 主要创新点。5 8 6 3 研究展望5 9 j l l 【谢t ；( 1 参考文献6 l 攻读硕士学位期间发表论文及参与科研情况。“ i v 第一章绪论 1 1 研究背景及意义 第一章绪论 改革开放以来，我国交通建设和管理取得了巨大的发展，管理技术和设施装备水平显著 提高，有力地促进了我国城乡经济的高速发展。但随着国民经济的持续发展和城市化进程的 进一步推进，城市人口和小汽车保有量快速增长，交通拥挤、交通污染、交通安全状况也越 来越严重。面对日益严峻的交通问题，国家提出“发展一个综合运输体系，解决交通拥堵、 交通环保、交通安全三个热点问题”的交通科技政策。缓解城市交通拥堵已经成为我国各级 政府和广大市民普遍关注的问题。 众所周知，公共交通是城市发展的必然产物，也是城市赖以生存的重要基础设施之一， 优先发展城市公交已经成为国内外城市交通发展的目标和方向公共交通主要是由轨道交 通、常规公共交通和准公共交通三个部分组成。城市常规公共交通系统具有运载量大、运送 效率高、能源消耗低、相对污染少、运输成本低、投资小、见效快【l 】等优点因此，在我国 城市人口密集度较大、道路资源相对十分有限的情况下，研究公交优先技术、提高居民公交 出行比例是缓解我国城市交通拥堵问题的关键措施和有效途径。 公共交通客流o d ( o r i g i n - d e s t i n a t i o n ) 矩阵是城市公交网络规划和管理的基础数据 为公交运营调度、公交线网优化布设提供最可靠的数据支持。为了获得单条公交线路客流 o d 矩阵，传统的调查方法是在乘客上车时发放调查表格按照乘客的出行起终点如实填写 表格，然后在下车时回收表格。这种调查方法不但繁琐，浪费大量的入力、物力和财力，而 且在实际操作时会遇到很多困难，如乘客填写表格的方便性、乘客的配合程度等，很难保证 调查数据的准确性。 为了获得公交网络的客流o d 矩阵，通常需要开展大量的o d 调查工作，即居民出行 o d 调查、流动人口o d 调查、车辆出行o d 调查等，然后对调查数据进行分析、整理来推 算得到。进行一次全面的o d 调查，固然可以得到整个城市较为完全、精确的公交客流o d 矩阵，但其操作难度较大，调查所需的经费也难以承受，且调查数据时效有限。 公共交通是解决城市交通拥挤的最有效出行方式，而公交客流o d 矩阵是公交网络规划 的最基础数据，但其调查难度和成本高，因此若能方便、准确地获得公交客流o d 矩阵将是 一件很有意义的工作。本文在总结国内外优秀研究成果基础上，分别以单条公交线路和公交 网络作为研究对象，对公交客流o d 矩阵推算方法进行分析研究，找到既不需要进行大规模 o d 调查，又能得到满足精度要求的o d 矩阵的推算方法，从而能够节省大量的人力、物力、 财力。 本论文依托于国家高技术研究发展计划( 8 6 3 计划) 探索导向类专题课题城市常 规公共交通智能化运营调度关键技术研究( 编号：2 0 0 7 a a l l z 2 1 0 ) 开展关于公交客流o d 矩阵推算的研究工作。 第一章绪论 1 2 研究概况 公交客流o d 矩阵反推起源于机动车o d 矩阵反推，后者研究比较多，目前有最大熵模 型、极大似然模型、最小信息量模型、广义最j 、- - 乘模型等比较成熟的模型【2 】。随着公共交 通地位的日益提高，国内外众多学者致力于公交客流o d 矩阵推算的研究。取得了不少的成 果。 1 2 1 国外研究概况 1 9 6 7 年，l a m o n d 等提出平衡法，其核心就是对o d 矩阵某一行的每个元素乘以一个常 数，使得该行的和符合它代表的停靠站的实际上车人数；对矩阵的每一列重复上述操作，使 得列和符合下车人数；连续迭代直到满足精度要求【3 】。1 9 8 5 年，针对上述平衡法受限制于所 谓的“非结构性0 问题”( b e n - a k i v a 【4 】) ，s i m o n 等把车上的乘客看作是一混合流：上车的乘 客被加到该流中，下车的乘客则被等概率地从该流中分离出去【5 】。2 0 0 1 年，n u z z o l o 等提出 随时间和上车乘客数变换的动态o d 矩阵推算模型，并且利用广义的最小二乘估计求解该算 法【6 】。2 0 0 7 年，l i 和c a s s i y 把公交停靠站分成大站和小站，对于大站和小站，分别给予乘 客不同的上车概率和下车概率，通过概率和公交停靠站上下车人数得到o d 矩阵【丌。2 0 0 8 年，b a i b i n gl i 提出利用公交停靠站上下车人数，得到基于马尔科夫链和贝叶斯分布的公交 客流o d 反推模型【引。 1 2 2 国内研究概况 国内对公交客流o d 矩阵研究起步较晚，近几年才受到国内学者的广泛关注和研究，取 得了一系列的成就。 1 9 9 7 年，夏志浩等把路段断面车流量推算道路网中车辆出行o d 分布的新方法移植到 公交系统，根据各线路各车站调查的上下车人数推算公交客流的o d 分布，并利用最大熵模 型求解【9 】。1 9 9 8 年，w o n g 和s o n g 提出基于调度时刻表和各停靠站上下车客流数的实时动 态公交o d 矩阵推算模型，并利用最大熵算法和稀疏矩阵算法求解该模型【l o 】。2 0 0 4 年，冯 树民经过调查分析，认为公交出行属于中长距离的出行，引入概率修正系数( 与出行站数有 关) ，提出了公交客流o d 由站点上下车人数进行推算的计算方法【1 1 1 2 0 0 5 年，窦庆峰认为 每条公交线路的客运一般为公交出行o d 量的线性组合，引入一个分配函数，把每条公交线 路的客流按合理比例直接分配到其经过的相关交通小区之间的现状公交o d 表中进行累加 修正，得到交通小区之间现状客流o d 分布【1 2 】。2 0 0 6 年，俞洁等提出了以改进b p 神经网络 为基础，根据公交站点上下客数建立公交线路o d 矩阵的推算模型，并设计了o d 推算神经 网纠1 3 1 。周晶等利用公交i c 卡数据建立了公交系统o d 矩阵的双层数学规划模型，上层问 题为广义最小二乘模型，下层问题为以变分不等式表示的基于超路径的公交网络均衡分配模 型，采用启发式算法求解该双层数学规划模型【1 4 1 。2 0 0 7 年，任其亮等根据重力模型法，建 立了公交客流分布函数模型，利用公交线路的日均客运量以及区域人口、社会经济、用地性 质等之间的内在联系提出了一种免o d 调查的公交客流o d 矩阵的反推算法【1 5 1 。周涛等利用 2 第一章绪论 公交i c 卡统计换乘次数、出行次数等公交出行信息，提出各站点下车人数推算方法；利用 数据挖掘技术，分别对公交线路站点o d 和区间出行o d 的推算方法进行了研究【1 日。窦慧丽 等提出公交乘客出行站数服从泊松分布，并以此建立公交客流o d 矩阵反推的概率模型【l n 。 刘翠等分析居民公交出行规律，建立了根据公交乘客上下车人数推算公交线路客流o d 矩阵 的极大熵模型，分别采用原始资料作为先验o d 和重力模型形式的先验o d 对模型进行求解 【1 8 1 。 另外，郭婕在其硕士论文 0 ， 基于结构风险最小化目标，通过推广的平分最近点法或推广的最大间隔法，将分类问题转化 为最优化问题。对于非线性分类问题，其基本思想是引进核函数，把问题转化为高维空间中 的线性分类问题，从而构造决策函数。支持向量机的结构类似于一个神经网络，输出的是中 间节点的线性组合，中间的每个节点对应于一个支持向量。 2 1 2 支持向量回归机 支持向量回归机( s u p p o r tv e c t o rr e g r e s s i o n ，简称s v r ) 是支持向量机在回归估计问题 中的扩展和应用。对于线性回归问题，首先基于结构风险最小化原则，通过推广的平分最近 点回归法或推广的最大间隔回归法，把原问题转化为一个最优化问题，并通过求解其对偶问 7 第二章基于最小二乘支持向量机的公交客流预测 题获得相应的最优解，进而构造决策函数。对于非线性回归问题，其基本思想是引进核函数， 把问题转化为高维空间( h i l b o r t 空间) 中的线性回归问题，从而构造决策函数。 应用支持向量回归机解决实际问题的过程主要涉及到支持向量机的类型( 包括s 一支持 向量回归机、y 支持向量回归机和最小二乘支持向量回归机) 、核函数以及损失函数的选 择问题。在确定了s v r 的类型、核函数以及损失函数，并且选择了相应的参数之后，就可 以利用支持向量回归机的算法，针对实际问题进行建模，求解最优化问题，构造最后的决策 函数，用于解决实际问题。 2 1 3 支持向量机中的核参数 核函数刻画的是特征空间中的内积，因此选择不同的核函数相当于选择不同的内积，这 意味着用不同的标准对相似性和相似程度进行度量。通过引入核函数，高维特征空间的内积 运算就可以通过原始输入空间的一个核函数来隐含地进行运算，也就是说，高维特征空间的 所有向量的内积运算都是通过原始空间的核函数来完成的，不需要直接利用映射后的样本在 特征空间中进行复杂的运算。升维后，只是改变了内积运算，并没有使算法的复杂度随着维 数的增加而增加，并且在特征空间的推广能力并不受维数影响。核函数的引入极大地提高了 学习机器的非线性处理能力，同时也保持了学习机器在高维空间中的内在线性，从而使得学 习很容易得到控制。目前常用的核函数主要有： ( 1 ) 傅里叶核函数 七似| ) 。而百面1 - - 丽q ，坛，x r ( 2 - 1 ) 式中g 为满足1 q 0 ，c 0 为惩罚参数，为求解上述优化问题，建立对应的拉格朗日函 数： l ( w , b ，f ，口) = 丢矿w + 考窆等一之【矿( x ) + b + 磊一乃】 ( 2 7 ) 二 = li = 1 由k a r u s h - k u h n - t u c k e 条件( 简称k k t ) ：a 工a 咿= o ，吼钆= o ，丸气= o ，得到 刀一 w = 矽( 五) ，q = o ，q = 鹰，矽( 五) w + 6 + 磊一乃= o ( 2 - 8 ) 扣li = i 消去缈和善可得线性方程组： 兰g g ；二y 一。 ，。“。“。 三 = ； c 2 9 ， 9 、 第二章基于最, j , - - 乘支持向量机的公交客流预测 其中e 为元素为 1的z 1 向量，为，z 的单位矩阵； 口= ( q ，) r ，y = ( 乃，儿，只) r ，g = ( ( 五) r ，( 吃) r ，( 而) r ) r 为核参数矩 阵。由m e r c e r 条件，定义核函数k ( 鼍，x ，) = 矽( 五) 矽 ，) ，得到线性决策函数为 l f ( x ) = a t k ( x f ，功+ 6 ( 2 1 0 ) t - i 2 2 基于遗传算法的最小二乘支持向量机参数优化 l s s v m 中惩罚参数y 和核参数盯的取值将直接关系到向量机的泛化性能。在实际应用 中，较为常用的参数选取方法是网格法 2 r j ，它的主要思想如下：首先选取一组合适的核参 数、惩罚参数的范围，即确定参数搜索的范围；然后设定固定的搜索步长，这样在由核参数 和惩罚参数构成的坐标系上就得到一个二维网络。对应网格上的每一组参数值，按照交叉验 证方法计算出测试准确率，最后将各组参数值对应的准确率用等高线描出，得到一个等高线 图，进而选出最优的参数值。网格法搜索最优参数值比较直接、简单。若参数较少，网格搜 素的时间消耗少；但是当参数较多，或者参数的范围选取得不适当、搜索步长的不确定，会 导致结果的不准确性以及搜索时间的消耗大，实验比较复杂。 本文提出新的评价指标，把该指标作为遗传算法中的适应度函数，然后用遗传算法对参 数惩罚参数和核参数优化。 2 2 1 遗传算法原理 遗传算法c 2 8 1 ( g e n e t i ca l g o r i t h m ，简称g a ) 起源于对生物系统所进行的计算机模拟， 是美国m i c h i g a n 大学大学的j o h nh h o l l a n d 教授及其学生受到生物模拟技术的启发而创造 出来的一种基于生物在自然环境中的遗传和进化机制的适合于复杂系统优化的自适应概率 优化技术。2 0 世纪7 0 年代是遗传算法兴起阶段，2 0 世纪8 0 年代是遗传算法的发展阶段， 而到了2 0 世纪9 0 年代则是遗传算法的高潮阶段。遗传算法发展迅速，在许多学科如生物技 术、化学工程、物理学、医学、人工智能的多个领域得到广泛应用，已经成为一种实用、高 效、鲁棒性强的启发式优化技术。遗传算法的各要素如下： ( 1 ) 编码 遗传算法采用编码的方式来表示群体中的个体，其目的是为实现交叉、变异等类似于生 物界的遗传操作。编码方式有很多种，它与求解速度、计算精度有直接关系，对算法有重要 影响。常用的编码方式有实数编码、二进制编码等。 ( 2 ) 选择依据：适应度 适应度，通俗地讲，就是个体生存能力的一个度量。适应度函数与目标函数相关联，可 以理解为个体所产生效益的表示，是个体空间到实数空间的映射。遗传算法中每个个体遗传 到下一代群体中的概率与个体适应度值成正比。为正确计算这个概率，要求所有个体的适应 度值必须大于等于零，且目标函数的优化方向对应适应度值增大的方向。 1 0 第二章基于最小二乘支持向量机的公交客流预测 ( 3 ) 选择方法 一t - r 适应度决定了个体的生存能力，但“适者生存一的过程还要靠一定的选择规则来实现。 选择就是按一定方式从旧个体中选出若干个个体作为父本来产生下一代的过程，适应度值高 的个体被选择机会就高。较常用的选择方法有以下两种：轮盘赌选择法和锦标赛选择法。 ( 4 ) 交叉 交叉是结合来自于父代交配种群中的信息产生新的个体的过程。它的操作过程是：任选 两个染色体，随机选择一个或多个交换点位置；交换双亲染色体交换点右边的部分，即可得 。到两个新的染色体编码串。对于二进制编码通常采取单点交叉、多点交叉、均匀交叉；对于 实数编码，通常采取算术交叉、启发式交叉。 ( 5 ) 变异 变异是用来模拟生物在自然遗传环境中由于各种偶然原因引起的基因突变，它以很小的 随机概率改变遗传基因的值。变异使得搜索可以在初始基因组合以外的空间进行，避免了寻 优过程在早期就陷入局部解而终止。对于二进制编码，通常可以采取均匀变异；对于实数编 码，通常采取正态变异，非均匀变异等。 2 2 2 评价指标 为优化惩罚参数y 和核参数1 7 ，文献 2 9 1 采用预测值和实际值的负均方根误差( - r m s e ) 作为评价指标，即： f = 一 ( 2 1 1 ) 其中f 为评价指标，为训练样本的数目，以为实际值，允为预测值。但该指标仅考 虑训练样本对参数的影响，未考虑验证样本对参数的影响。因此本文在其基础上进一步提出 训练性能评价指标u 和验证性能评价指标矿。 首先将给定的样本集r 等间隔分成p 个互不相交的样本子集z ，每个子集包含所个样 本，即互= ( h ，虼) ，( 五2 ，y s 2 ) ，( ，) ) ，- - 1 ，2 ，p 。每次取一个子集作为验证样 本集，剩余的p 一1 个子集作为训练样本集。假设第i 次实验采用的验证子集为霉，为刻画 由相应的训练样本集得到的最小二乘支持向量回归机性能，本文分别采用训练性能评价指标 u 和验证性能评价指标k ，定义如下： 配= k = ，i = 1 ，2 ，p ( 2 - 1 2 ) ，i = 1 ，2 ，p ( 2 - 1 3 ) 第二章基于最小二乘支持向量机的公交客流预测 假设旯为u 和k 的平衡系数，那么第f 次实验的总性能指标e 为： e = 2 u , + ( 1 一旯) 巧 = a + ( 1 - ；d ，i = 1 ，2 ，p ( 2 - 1 4 ) 从公式厂( 石) = 喜q k “，x ) + 6 = 喜哆唧( 一峰；玛+ 6 可以看出厂( 功是关于盯 的函数；从公式2 - 5 和2 击中也可看出，线性决策函数f ( x ) 与惩罚参数y 有关，因此f 是 关于y 和仃的函数，从而建立以y 和盯为变量的优化问题： r a i n f = ( 墨+ 互+ + ) p ( 2 - 1 5 ) ，仃 问题( 2 1 5 ) 的最优解即为参数，和仃的最佳值。 2 2 3 遗传算法设计 本文采用上文提到的遗传算法对最小二乘支持向量机中的参数进行优化，主要包括以下 几个部分：编码、种群初始化、适应度函数、选择方法、交叉、变异、终止条件。 ( 1 ) 编码方式：采用实数编码方式，这样可以避免二进制编码在遗传操作时反复译码、 编码的操作以及二进制字符串有限的长度对进化算法性能和求解精度的影响。 ( 2 ) 种群初始化：由于正则化参数y 和核参数盯在理论上只需满足大于零条件，根据 经验，种群规模一般3 0 - 一1 0 0 ，种群太小优化精度较低，种群太大计算复杂，种群规模取 m = 8 0 。 ( 3 ) 适应度函数：由于适应度函数的作用是对个体作评价，因此适应度函数的设计至 关重要，本文采用公式( 2 1 4 ) 所示的性能评价指标作为适应度函数。 ( 4 ) 选择方法：采用轮盘赌选择法，按适应度排序，并配以相应的概率值，个体f 被 采用的概率只可以表示成如下： 其中z 表示个体i 的适应度值，m 为种群规模。 ( 5 ) 交叉和变异：当遗传代数较小时，应取较大的交叉率和变异率，从而加大搜索范 围，保持群体多样性；相反当遗传代数很大时，应取较小的交叉率和变异率，以防止优良个 体被破坏，针对交叉率和变异率，本文做如下改进： 1 2 )6二( 五 m 埘 z = 毋 第二章基于最小二乘支持向量机的公交客流预测 f 眈o 1 腑，皿= o 9 ，玩= o 0 5 o 1 肫 d c 0 9 讹，皿= 0 7 ，以= o 0 1 ( 2 - 1 7 ) 【0 9 宰n c d c n c ，琏= 0 5 ，乜= 0 0 0 1 其中上) c 表示迭代次数，讹表示最大迭代次数，皿表示交叉率，日，表示变异率。 ( 6 ) 终止条件：采用达到预先设定的代数或者根据问题定义测试种群中最优个体的性 能作为终止条件，本文取最大迭代次数c - 5 0 0 。 利用遗传算法求解最小二乘支持向量机中参数，和盯最优值的过程如图2 1 所示： 图2 _ l 基于遗传算法的l s - s v m 参数优化流程图 2 3 基于最4 - - - 乘支持向量机的公交客流预测模型 2 3 1 公交客流影响因素分析 公交客流年客运量不仅与公交系统自身发展水平有关，而且与城市社会经济发展水平、 城市用地、人口分布等因素息息相关。公共线网密度越大，公交车辆越多，吸引的公交乘客 就会越多。随着城市社会经济水平的发展，居民收入的提高，除了必要的上班、上学、回程 等生存出行外，购物、旅游、文体活动等弹性出行次数增多，公交客流量也会增大。城市用 地开发程度越高，城市人口越多，公交客流越多。 公交短时客流受天气变化，竞争线路等多种因素影响，具有很强的复杂性和随机性【1 删。 同时，公交客流一般呈七天为一个周期的循环性变化，即比如星期一的公交客流量与前m 周 的星期一的客流量相关。此外，公交客流与前几天的客流有着必然联系，就可以利用前力天 的公交客流数据序列去预测未来的客流。假设短期预测的时间周期为t o ( 瓦以分钟为单位) ， 某车次公交车一天总运营时间为r 分钟，则可以分为n o ( n o = r t o ) 个观测时段。若某一 1 3 第二章基于最小二乘支持向量机的公交客流预测 时段的公交客流量与前s 个观测时段密切相关，那么某一天某一时段的公交客流量巧与 肼，硅，最。，f d - ：，f d - 。，巧时，e 一，e 。1 有关，其 中d 表示日期，f 表示观测时段。特别地，当时间周期瓦= 6 0 ( m i n ) 时，对应的预测量即为 公交客流小时客流量。 2 3 2 模型建立及其求解 ( 1 ) 公交客流年客运量预测 假设公交客流年客运量有m 个影响因素，包括国内总产值、工业总产值、城市人口、 居民收入水平等。记第f 年的公交客流量为乃，对应的影响因子为t = ( ，墨2 ，) ，其 中表示影响第f 年公交客流量的第，个影响因素，f = 1 ，2 ，z ，歹= 1 ，2 ，m 由此建 立训练集 ( 墨，m ) ，“，乃) ，“，乃) ) ，为训练样本个数，即 输入变量x = 至 y = k 儿m r 。 五l 而2 恐l 嘞 而l而l兰i ，对应的公交客流年客运量 然后把上述训练集 ，y ) 代入到最小二乘支持向量机中，通过非线性映射把数据集映射 到高维特征空间，把非线性拟合问题转化为线性拟合问题，再根据风险最小化原理，建立相 应的约束优化问题 ra咄in。!矿w+兰圭1=12 2 等( 2 - 1 8 ) 一