解决多目标旅行商问题的改进NSGA-II算法1
需积分: 0 182 浏览量
2022-08-03
17:43:16
上传
评论
收藏 916KB PDF 举报
叶工业控制计算机曳圆园员愿 年第 猿员 卷第 源 期
仅有一个目标函数的最优化问题称为单目标优化问题袁目标
函数超过一个的最优化问题称为多目标优化问题渊酝怎造贼蚤原燥遭躁藻糟鄄
贼蚤增藻韵责贼蚤皂蚤扎葬贼蚤燥灶孕则燥遭造藻皂泽袁酝韵孕冤
咱员暂
遥 在解决科学与工程问题
时袁一般需要考虑多个目标函数袁而这几个目标函数通常是相互
冲突和相互影响的袁一个子目标的改善可能会引起另一个子目标
性能的降低袁通常不存在唯一的使所有目标函数同时达到最优值
的绝对最优解袁 而是存在多个相互之间无法比较优劣的 孕葬则藻贼燥
最优解遥 这些解所构成的集合称为 孕葬则藻贼燥 最优解集袁其对应的目
标向量组成的曲线渊或曲面冤称为 孕葬则藻贼燥 前端
咱圆暂
遥
多目标旅行商问题是经典 栽杂孕 扩展和延伸袁属于典型的多
目标组合优化问题遥 一般叙述为院 有一旅行商从第一个城市出
发袁欲遍历其余城市至少一次袁最后再回到第一个城市袁其中各
城市之间距离和花费是已知的袁试求解合适的行走路线袁使其满
足总路程最短尧时间最少尧费用最省尧风险最小等多个目标函数
咱猿暂
遥
工程决策中的大量问题可归结为多目标 栽杂孕 问题袁 如生产计
划尧物流调度等袁因此寻找适合有效的算法尤为重要遥
本文提出了一种 粤晕杂郧粤原陨陨垣圆燥责贼 算法来解决双目标 栽杂孕
问题袁此算法在 晕杂郧粤原陨陨 的基础上袁加入了局部搜索策略 圆燥责贼袁
并且对遗传算法的变异参数采取了自适应策略袁 论文将 粤晕杂鄄
郧粤原陨陨垣圆燥责贼 算法与传统的 晕杂郧粤原陨陨 在标准的双旅行商问题上
进行性能对比袁实验结果验证了算法的有效性遥
员 多目标旅行商问题
旅行商问题渊栽则葬增藻造造蚤灶早杂葬造藻泽皂葬灶孕则燥遭造藻皂袁栽杂孕冤袁也称为
货郎担问题袁是一个典型的 晕孕 完全性组合优化问题
咱源暂
遥 多目标
旅行商问题其数学描述为院
皂蚤灶
泽沂粤
阅越
灶原员
蚤越员
移
凿
葬
蚤
葬
蚤垣员
垣凿
葬
灶
葬
员
皂蚤灶
泽沂粤
宰越
灶原员
蚤越员
移
憎
葬
蚤
葬
蚤垣员
垣憎
葬
灶
葬
员
扇
墒
设
设
缮
设
设
渊员冤
其中袁粤 表示邀员袁圆袁猿袁噎袁灶妖的所有排列组合袁喳葬
员
袁葬
圆
袁噎袁葬
灶
札
是其中一个排列组合袁凿
葬
蚤
葬
蚤垣员
表示城市 蚤 到城市 躁 的距离袁憎
葬
蚤
葬
蚤垣员
表示城
市 蚤 到城市 躁 的花费袁对于对称型 栽杂孕 来说袁凿
葬
蚤
葬
蚤垣员
越凿
葬
蚤垣员
葬
蚤
袁憎
葬
蚤
葬
蚤垣员
越憎
葬
蚤垣员
葬
蚤
遥
目标就是要找到最优路径袁使得总距离 阅 和总花费 宰 最小遥
本文算法采用整数编码袁 每一个个体由按一定顺序排列的
灶 个城市的序列组成袁表示一条可能的旅行路径袁每一个个体的
长度为 灶袁解的空间为 灶选
咱缘暂
遥适应度值为一条路径的距离和花费遥
例如院 对于一个 员园 个城市的旅行商问题的其中一个个体邀缘袁圆袁
源袁员袁猿袁怨袁愿袁远袁员园袁苑妖表示旅行商从城市 缘 出发依次经过 圆袁源袁员袁
猿袁怨袁愿袁远袁员园袁苑袁最后再回到城市 缘袁转换成图形可表示为图 员遥
这种编码方式既符合 栽杂孕 的约束条件袁也保证了不会形成局部
环路袁计算适应度值时袁也无需进行编码转换袁在很大程度上提
高了算法的效率遥
图 员 解决 栽杂孕 的编码方式
种群初始化可以采用随机初始化的方式完成遥 每个个体的
初始化具体步骤为院首先袁随机生成 员耀灶 之间的 灶 个整数的一
个排列曰这个排列就是一个个体曰重复 责燥责泽蚤扎藻渊定义种群规模
固定大小为 责燥责泽蚤扎藻冤次袁生成 责燥责泽蚤扎藻 个这样的个体形成初始
种群
咱远暂
遥
圆粤晕杂郧粤原陨陨垣圆燥责贼 解决双目标旅行商问题
本文在 晕杂郧粤原陨陨 的基础上加入了一种局部搜索策略 圆燥责贼袁
并结合旅行商问题的实际对变异算子采取了一种自适应策略遥
圆援员晕杂郧粤原陨陨 算法
传统的 晕杂郧粤原陨陨 进化算法的思想是通过构造组合种群的
非支配前沿集袁然后对非支配前沿中的个体进行交叉袁变异等操
作袁从而得到下一代种群袁然后再对新种群进行非劣解排序袁依
次不断经过种群的迭代袁 使求得的非支配前沿逐步趋向 孕葬则藻贼燥
最优解集
咱苑暂
遥
解决多目标旅行商问题的改进 晕杂郧粤原陨陨 算法
鄢
李霄玉 姚 骏
渊上海大学机电工程与自动化学院袁上海 圆园园园苑圆冤
陨皂责则燥增藻凿晕杂郧粤原陨陨酝藻贼澡燥凿枣燥则酝怎造贼蚤原燥遭躁藻糟贼蚤增藻栽则葬增藻造造蚤灶早杂葬造藻泽皂葬灶孕则燥遭造藻皂
摘要院多目标旅行商问题是经典 栽杂孕 问题的扩展和延伸袁具有很强的实际研究意义遥 在多目标进化算法 晕杂郧粤原陨陨 的基
础上设计了一种双目标进化算法以求解该问题袁其中袁在非劣解排序的基础上混合了局部搜索策略 圆燥责贼 以提高局部寻优能
力袁并采用了动态变化的变异算子体现出自适应的思想遥 用 酝粤栽蕴粤月 编程实现该算法并对几个标准双目标 栽杂孕 算例进行
仿真测试遥 实验结果表明袁提出的算法比 晕杂郧粤原陨陨 具有更好的优化性能遥
关键词院多目标旅行商袁晕杂郧粤原陨陨袁局部搜索袁自适应
粤遭泽贼则葬糟贼押酝怎造贼蚤原燥遭躁藻糟贼蚤增藻贼则葬增藻造蚤灶早泽葬造藻泽皂葬灶责则燥遭造藻皂蚤泽葬糟造葬泽泽蚤糟葬造藻曾责葬灶泽蚤燥灶葬灶凿藻曾贼藻灶泽蚤燥灶燥枣贼澡藻栽杂孕责则燥遭造藻皂熏澡葬增蚤灶早葬
泽贼则燥灶早责则葬糟贼蚤糟葬造则藻泽藻葬则糟澡泽蚤早灶蚤枣蚤糟葬灶糟藻援栽澡蚤泽责葬责藻则凿藻泽蚤早灶泽葬皂怎造贼蚤原燥遭躁藻糟贼蚤增藻藻增燥造怎贼蚤燥灶葬则赠葬造早燥则蚤贼澡皂遭葬泽藻凿燥灶贼澡藻晕杂郧粤原陨陨贼燥
泽燥造增藻贼澡蚤泽责则燥遭造藻皂熏蚤贼怎泽藻凿贼澡藻皂藻贼澡燥凿燥枣灶燥灶原凿燥皂蚤灶葬贼藻凿泽燥则贼蚤灶早葬灶凿贼澡藻造燥糟葬造泽藻葬则糟澡圆燥责贼贼燥蚤皂责则燥增藻贼澡藻藻枣枣蚤糟蚤藻灶糟赠燥枣
泽藻葬则糟澡蚤灶早熏葬灶凿贼澡藻皂怎贼葬贼蚤燥灶燥责藻则葬贼燥则蚤泽凿赠灶葬皂蚤糟糟澡葬灶早藻凿贼燥则藻枣造藻糟贼贼澡藻贼澡燥怎早澡贼燥枣葬凿葬责贼葬贼蚤燥灶援陨贼蚤泽蚤皂责造藻皂藻灶贼藻凿遭赠酝粤栽蕴粤月
葬灶凿泽蚤皂怎造葬贼蚤燥灶燥灶葬噪蚤灶凿燥枣遭藻灶糟澡皂葬则噪枣怎灶糟贼蚤燥灶泽援
运藻赠憎燥则凿泽押皂怎造贼蚤原燥遭躁藻糟贼蚤增藻贼则葬增藻造蚤灶早泽葬造藻泽皂葬灶责则燥遭造藻皂熏晕杂郧粤原陨陨熏造燥糟葬造泽藻葬则糟澡熏葬凿葬责贼蚤增藻
鄢上海市科学技术委员会渊员苑缘员员员园苑园园圆冤
103
资源评论
透明流动虚无
- 粉丝: 38
- 资源: 306
