《模型建立于蚁群算法》由会员分享，可在线阅读，更多相关《模型建立于蚁群算法（8页珍藏版）》请在金锄头文库上搜索。
1、确定型模型的建立确定型模型的建立1、模型的基本假设与前提模型中包含一个回收中心和多个回收客户点，每辆车都由回收中心出发，经由各个客户点完成回收任务后，再次回到回收中心。回收中心的容量没有限制。每个回收客户点的回收量已知。回收中心同各回收客户点相对位置坐标己知，且路径长度对称。每个回收客户点仅被一辆车服务一次。每辆车的载重能力和总容积限制已知，单个回收客户点的回收量不能超出单车载重能力和容积约束的 1/2。对于每一辆车，只有当其路径上所有回收量大于最小载重量和最小容积时才能出车。每辆车每次任务的总行驶里程不能超过车辆允许最大行驶距离。回收的货物可以混装。单位运输成本同运输距离呈线性关系。2、模型
2、参数及变量定义P:所有节点集合，P=i，i=0 表示回收中心，i=1，2，n 表示回收客户点S:回收客户点集合，且 P=SU0V:所有车辆集合，V=k，k=1，2，mD:各节点间距离矩阵，D=)1)*(1(nnijd:各节点间距离，且,ijd0jjiiddjiijddPji ,:第 k 辆车的固定成本，即增加一辆车所产生的费用kC0：第 k 两车的单位距离费用kC：第 k 辆车的额定最大载重量kZmax：第 k 辆车的额定最小载重量kZmin：第 k 辆车的额定最大容积kRmax：第 k 辆车的额定最小容积kRmin：第 k 辆车允许的最大行驶距离kL：第 i 个回收客户点出货物的总重量iw：
3、第 i 个客户点处货物的总体积iv：0-1 变量，当第 k 辆车从 i 至 j 进行回收时，值为 1，否则为 0ijkx：0-1 变量，当第 k 辆车服务第 i 个回收客户点时，值为 1，否则为 0iky（3）目标函数（1） VkPiPjVkijkijkkxdCCF0min(4)约束条件n=3,m=2 Vkiky1)n2 , 1 (Si（2） Pjikijkyx)2 , 1 (),2 , 1 , 0(mVknPi（3） Pijkijkyx), 2 , 1 (),2 , 1 , 0(mVknPj（4）ksiikiZywmax ), 2 , 1 (mVk（5）(6) Sik ikiZywmin),
4、 2 , 1 (mVk(7)kSiikiRyvmax ), 2 , 1 (mVk(8) Sik ikiRyvmin), 2 , 1 (mVk(9) PiPjkijkijLxd), 2 , 1 (mVk点进行回收开至辆车从点，第 否则jik ijkx1 , 0), 2 , 1 (mVk（10）(11)的货物辆车回收点，第 否则i ikyk1 , 0), 2 , 1 (mVk目标函数（1）表示车辆使用、运行成本最小；约束条件（2）保证每个客户点均被服务；（3） 、 （4）保证驶入和驶出某个客户点的车辆为同一辆，保证每个节点仅被服务一次；（5） 、 （6）为车辆最大、最小载重限制；（7） 、 （8）
5、为车辆最大、最小容积约束；（9）为车辆最大行驶距离约束；（10） 、 （11）为变量、取值。ijkxiky不确定型模型的建立不确定型模型的建立1、模型的基本假设与前提模型中包含一个回收中心和多个回收客户点，每辆车都由回收中心出发，经由各个客户点完成回收任务后，再次回到回收中心。回收中心的容量没有限制。每个回收客户点回收物品的重量和体积均为随机变量，且服从的分布己知。回收中心同各回收客户点相对位置坐标己知，且路径长度对称。每个回收客户点仅被一辆车服务一次。每辆车的载重能力和总容积限制已知，允许单个回收客户点的回收量在一定置信水平下满足单车辆的载重能力和容积限制。对于每一辆车，只有当其路径上所有回
6、收量大于最小载重量和最小容积时才能出车。允许每辆车每次任务的总行驶里程在一定置信水平下满足车辆允许最大行驶距离。单位运输成本同运输距离呈线性关系，回收的货物可以混装。2、模型参数及变量定义P:所有节点集合，P=i，i=0 表示回收中心，i=1，2，n 表示回收客户点S:回收客户点集合，且 P=SU0V:所有车辆集合，V=k，k=1，2，mD:各节点间距离矩阵，D=)1)*(1(nnijd:各节点间距离，且,ijd0jjiiddjiijddPji ,:第 k 辆车的固定成本，即增加一辆车所产生的费用kC0：第 k 两车的单位距离费用kC：第 k 辆车的额定最大载重量kZmax：第 k 辆车的额定
7、最小载重量kZmin：第 k 辆车的额定最大容积kRmax：第 k 辆车的额定最小容积kRmin：第 k 辆车允许的最大行驶距离kL：第 i 个回收客户点出货物的总重量iw：第 i 个客户点处货物的总体积iv：0-1 变量，当第 k 辆车从 i 至 j 进行回收时，值为 1，否则为 0ijkx：0-1 变量，当第 k 辆车服务第 i 个回收客户点时，值为 1，否则为 0iky:目标函数的置信水平:单车辆载重能力约束置信水平1:单车辆容量约束置信水平2:单车辆总行驶里程约束置信水平3:目标函数在置信水平为刀时所取的最小值FPr.:.中事件成立的概率(3)构建需求不确定情况下车辆配置及路径优化问题
8、的机会约束模型:目标函数: （1）Fmin约束条件: （2） Pr0 VkPiPjVkijkijkkFxdCC（3） Vkiky1)n2 , 1 (Si（4） Pjikijkyx)2 , 1 (),2 , 1 , 0(mVknPi（5） Pijkijkyx), 2 , 1 (),2 , 1 , 0(mVknPj（6）1maxmin,PrSik ikikVkZywZ（7）2maxmin,PrSik ikikVkRyvR（8）3,Pr PiPjkijkijVkLxd（9）点进行回收开至辆车从点，第 否则jik ijkx1 , 0), 2 , 1 (mVk（10）的货物辆车回收点，第 否则i iky
9、k1 , 0), 2 , 1 (mVk目标函数(1)表示目标函数(车辆使用、运行成本最小，同时使车辆回收货物小于/大于车辆额定载重/容积时)在置信水平为厂时所取的最小值;约束条件(2)表示目标函数取得最小值的概率应不小于置信水平;约束条件(3)保证每个客户点均被服务，且每辆车均从回收中心出发;(4)(5)保证驶入和驶出某一客户点的车辆为同一辆，保证每个节点仅被服务一次;(6)表示满足单车辆载重限制的概率应不小于置信水平;(7)表示满足车辆容量限制的概率应大1于置信水平;（8）表示车辆最大行驶路程约束的概率应大于置信水平;(9)(10)为变量23、取值。ijkxiky蚁群算法蚁群算法1、觅食示意
10、图2、 蚂蚁觅食原理如图所示, 设 A 是巢穴, E 是食物源, HC 为一障隘物. 由于障随物存在, 蚂蚁只能经由 H 或 C 由 A 到达 E, 或由 E 到达 A. 设每个时间单位有 30 只蚂蚁由 A 到达 B, 有 30 只蚂蚁由 E 到达 D 点, 蚂蚁过后留下的激素物质量(以下我们称之为信息) 为 1. 为方便, 设该物质停留时间为 1. 在初始时刻, 由于路径 BH、BC、DH、DC 上均无信息存在, 位于 B 和 E 的蚂蚁可以随机选择路径. 从统计的角度可以认为它们以相同的概率选择 BH、BC、DH、DC. 经过一个时间单位后, 在路径 BCD 上的信息量是路径 BHD 上
11、信息量的二倍. t= 1 时刻, 将有 20 只蚂蚁由 B 和 D 到达 C, 有 10 只蚂蚁由 B 和 D 到达 H. 随着时间的推移, 蚂蚁将会以越来越大的概率选择路径 BCD, 最终完全选择路径 BCD. 从而找到由蚁巢到食物源的最短路径. 3、基本蚂蚁算法的特点可以概括如下:(1)、较强的鲁棒性，对蚂蚁算法的模型稍加修改，便可以应用于其它问题。(2)、分布式计算，蚂蚁算法是一种基于种群的进化算法，可以避免过早的收敛，本质上具有并行性，其搜索过程不是从一点出发，而是从多个点同时进行，这种分布式多智能体的协作是异步并发进行的，分布并行的模式将大大提高整个算法的运行效率和快速反应的能力。(
12、3)、易于与其它方法结合，蚁群算法很容易与多种启发式算法结合，以改善算法的性能，如同遗传算法、禁忌搜索算法、人工免疫算法等算法的结合都衍生出多种混合算法。(4)、正反馈，从而能迅速找到好的解。(5)、强启发式，能在早期的寻优中迅速找到合适的解决方案.4、具体算法设蚁群中蚂蚁的数量为 m , dij ( i , j = 1 , 2 , , n) 表示点 i 和点 j 之间的距离.bi ( t) 表示 t 时刻位于点 i 的蚂蚁的个数. 显然 bi ( t) =m.ij ( t) 表示 t 时刻在点 i , j 连线上残留的信息量. 初始时刻,各条路径上信息量相等,设 ij (0) = C( C
13、为常数) . 蚂蚁 k ( k = 1 ,2 , , m) 在运动过程中,根据各条路径上的信息量决定转移方向.在 t 时刻蚂蚁 k 由点 i 转移到点 j 的概率 (11) kktabutijijijijktabujntttabujk ijtp ,)()()()(, 0)(ij 先验知识或称为能见度, 在 TSP 问题中为点 i 转移到点 j 的启发信息; 在路径 ij 上残留信息的重要程度; 启发信息的重要程度; tab 记录蚂蚁 k 当前所走过的城市, 称为记忆列表, 集合 tab随着进化过程作动态调整.kuku经过 n 个时刻, 所有蚂蚁都完成了一次遍历. 此时, 计算每一只蚂蚁所走过的
14、路径, 并保存kL最短路径 Lmin = min Lk ， k = 1 , 2 , , m . 在蚂蚁完成一次循环以后, 各路径上的信息量进行如下调整(12)ijijijtnt)()1 ()(13) lsk ijij 1为蚂蚁 k 在本次循环中在点 i 和点 j 之间留下的信息量, 一般有两种更新方式：（1） 、每只蚂蚁每前进一步都会释放信息素并更新经过路径上的信息素浓度（2） 、只在结束整个循环后才更新. 5、步骤(l)、参数初始化:令 t=0，循环次数=0，设置最大循环次数，将 l 只蚂蚁随机地放到 ncNmaxcN个城市，将每条边(i，j)上的信息素设为一个常数，且，将出发点城市设置到禁忌表0ij中;(2、)按状态转移式(11)选择下一个城市;(3)、修改禁忌表，即选择好之后将蚂蚁移动到下一个城市，并把该城市移动到蚂蚁个体的禁忌表中;(4)、循环执行第(2)步和第(3)步，直到每只蚂蚁都生成一条路径;(5)、计算第 s 只蚂蚁所走路径的总长度 Ls;(6)、根据式(12)和式(13)更新所有路径上的信息量;(7)、若循环次数从，则循环结束并输出计算结果，否则清空禁忌表并转到第(2)步。maxccNN
