复杂组合优化问题的智能搜索方法
发布时间：2020-08-06 21:10
【摘要】：组合优化问题广泛存在于交通运输、网络规划、物流配送、云计算、大数据、生产制造等诸多领域。求解多约束、多目标、复杂组合优化问题的智能搜索方法是提高企业效率、优化资源成本、改善用户体验、节省消耗能源等诸多方面的核心技术。本文考虑了求解组合优化问题的两种搜索方法:简单构造式搜索和迭代构造式搜索,结合不同问题场景,依据具体问题特性,对不同的搜索方法进行了相关研究。论文的主要工作体现在:(1)针对基于位置学习效应的最短路径不满足最优子结构、无法直接使用传统A*系列算法求解的问题,提出了基于学习效应最短路径的启发式精确性搜索AA*算法,保留潜在最优解的子路径,形成搜索图:证明了算法的可采纳性;结合问题具体特性,重新定义了启发函数的单调性和一致性;比较了所提AA*算法中启发函数与A*算法中启发函数单调性/一致性之间的关系;分析并证明了在单调性和一致性满足的前提下启发函数大小对搜索效率影响的相关性质;通过仿真实验验证了所提算法的有效性。(2)针对求出双目标最短路径问题所有非支配解花费时间长(尤其是大规模问题)、非支配解数量随着问题规模增加急剧增加的问题,提出了一种增量式、用户驱动的迭代构造启发式搜索算法UDBA*,通过充分利用之前的搜索信息避免重复搜索,在很短时间内快速得到勾画Pareto前沿面的部分分布均匀的非支配解,以满足用户决策需求;证明了所提算法的可采纳性;分析了启发函数的单调性和一致性对搜索效率的影响;通过仿真实验验证了所提算法的有效性。(3)针对更加一般化的、等待和无等待约束同时存在的混合等待流水调度问题,建立了数学模型;设计了一种最大完工时间的快速计算方法;提出了一种改进迭代贪心算法,通过抽取工件数量动态自适应变化策略以及结合模拟退火思想提高搜索多样性,构造可变邻域搜索增加搜索力度;经过参数和算子修正,将所提算法与五个求解类似问题的算法在修正的Taillard benchmark标准测试例上进行实验比较,结果表明所提算法优于其它算法。
【学位授予单位】：东南大学
【学位级别】：博士
【学位授予年份】：2018
【分类号】：TP18
【图文】：
右上角的终点。司机希望最小化时间和油耗。有可能一些路径比其它路径短，由此需要逡逑耗费的油量较少，但是这些路径可能存在严重的交通拥堵，所以，需要的时间很长。另逡逑外一些路径可能相反。如图１．１所示，实心圆点表示某２０邋ｘ邋２０网格双目标最短路径问题逡逑的所有非支配解。希望开始时找到一部分分布均匀的非支配解（如巧、巧和巧）。如逡逑果这些解能满足司机决策需求，那么停止搜索，否则，继续搜索，继而找到解巧、巧逡逑和户６，重复判断、搜索，直到满足司机决策需求或者允许的运行时间结束。极端的情逡逑况，可能需要找到所有非支配解。那么，如何在尽快找到满足用户决策需求的、均匀分逡逑布的部分非支配解是实际存在且需要解决的一个问题。逡逑２２０邋—Ｐ－．－逡逑２００邋逦％逦—逦—逡逑１８０邋逦逦—逦逦逡逑１６０邋．．．．．．．．．．．．．－逦—逦—逦逡逑Ｐ，邋＊逡逑１４0邋—逦逦—￣逦逡逑Ｐ－邋＇邋．．逡逑１２０逦逦ｉ逦逡逑Ｐ】逡逑１００邋－Ｉ逦１逦１逦１逡逑１１０邋１６０邋２１０邋２６０逡逑图１．１邋２０ｘ２０网格双目标最短路径问题的Ｐａｒｅｔｏ最优解集逡逑当问题规模变大、问题更加复杂时（如ＮＰ难问题），如果采用上述简单构造式搜逡逑索方法，或者需要时间太长而无法在可接受时间内找到最优解，或者通过某些启发策略逡逑快速构造得到的解质量较差。此时，需要进行多次迭代搜索，也就是第二种搜索方法，逡逑迭代构造式搜索。在该搜索方法的每一次迭代过程中
当比较图放大时更容易看出该结论。当结点数量大于２２时回溯法所需时间呈指逡逑数级增长。事实上，当结点数量大于４４时，回溯法不能够在４８小时内运行结束。类逡逑似的，如图２．１１所示，当图中弧的数量大于４５时，ＡＡ＊算法搜索时间远远小于回溯法。逡逑当弧的数量大于８０时，回溯法所需时间显著增加。与之相反，相比较回溯法，ＡＡ＊算逡逑法运行时间随着图中结点（弧）数量增加增长缓慢。逡逑６．５逦ｐ逦＿逡逑．逦算法逦？逡逑：＋回溯法逦ｉ逦－逡逑４．５逦－邋－Ｍ－逦ＡＡ＊，逦－逡逑－３．５邋Ｌ＿逦Ｉ逡逑寸邋ＶＯＯＯＯＮＯＣＳ寸逦—邋ＣＮ寸邋0邋卜邋ＯＯＯＣＮＣＯ＇ＯＯＮＯＣＭ逡逑ｔ￣ｈ邋—邋—邋一邋—邋—邋ｃ＾＜Ｎ＜Ｎｒ＾
ｔ￣ｈ邋—邋—邋一邋—邋—邋ｃ＾＜Ｎ＜Ｎｒ＾ｃ＾ｃ＾＜Ｎｒ0ｒ0邋ｃ0邋ｒ0邋寸寸逡逑顶点数量逡逑图２．１０算法在９５％Ｔｕｋｅｙ置信区间下顶点数量对运行时间影响的比较逡逑７Ｆ邋ｍ．逦：逡逑；－ａ－回溯？法逦；逡逑５邋－逦ａａ！＞逦上邋ｊ」逡逑ＡＡ２逦Ｗ逦－逡逑１３「—４逦：逡逑￣￣0￣￣￣￣＾￣￣＾邋0￣￣￣＾邋＾￣0邋＾５邋＾￣￣＾邋＾逡逑0４0４（＾＞寸逦卜邋ＯＯＯＯＯＮ邋—邋（Ｎｍ逡逑弧数量逡逑图２．１１算法在９５％Ｔｕｋｅｙ置信区间下弧数量对运行时间影响的比较逡逑２７逡逑
本文编号：2782965
【学位授予单位】：东南大学
【学位级别】：博士
【学位授予年份】：2018
【分类号】：TP18
【图文】：
右上角的终点。司机希望最小化时间和油耗。有可能一些路径比其它路径短，由此需要逡逑耗费的油量较少，但是这些路径可能存在严重的交通拥堵，所以，需要的时间很长。另逡逑外一些路径可能相反。如图１．１所示，实心圆点表示某２０邋ｘ邋２０网格双目标最短路径问题逡逑的所有非支配解。希望开始时找到一部分分布均匀的非支配解（如巧、巧和巧）。如逡逑果这些解能满足司机决策需求，那么停止搜索，否则，继续搜索，继而找到解巧、巧逡逑和户６，重复判断、搜索，直到满足司机决策需求或者允许的运行时间结束。极端的情逡逑况，可能需要找到所有非支配解。那么，如何在尽快找到满足用户决策需求的、均匀分逡逑布的部分非支配解是实际存在且需要解决的一个问题。逡逑２２０邋—Ｐ－．－逡逑２００邋逦％逦—逦—逡逑１８０邋逦逦—逦逦逡逑１６０邋．．．．．．．．．．．．．－逦—逦—逦逡逑Ｐ，邋＊逡逑１４0邋—逦逦—￣逦逡逑Ｐ－邋＇邋．．逡逑１２０逦逦ｉ逦逡逑Ｐ】逡逑１００邋－Ｉ逦１逦１逦１逡逑１１０邋１６０邋２１０邋２６０逡逑图１．１邋２０ｘ２０网格双目标最短路径问题的Ｐａｒｅｔｏ最优解集逡逑当问题规模变大、问题更加复杂时（如ＮＰ难问题），如果采用上述简单构造式搜逡逑索方法，或者需要时间太长而无法在可接受时间内找到最优解，或者通过某些启发策略逡逑快速构造得到的解质量较差。此时，需要进行多次迭代搜索，也就是第二种搜索方法，逡逑迭代构造式搜索。在该搜索方法的每一次迭代过程中
当比较图放大时更容易看出该结论。当结点数量大于２２时回溯法所需时间呈指逡逑数级增长。事实上，当结点数量大于４４时，回溯法不能够在４８小时内运行结束。类逡逑似的，如图２．１１所示，当图中弧的数量大于４５时，ＡＡ＊算法搜索时间远远小于回溯法。逡逑当弧的数量大于８０时，回溯法所需时间显著增加。与之相反，相比较回溯法，ＡＡ＊算逡逑法运行时间随着图中结点（弧）数量增加增长缓慢。逡逑６．５逦ｐ逦＿逡逑．逦算法逦？逡逑：＋回溯法逦ｉ逦－逡逑４．５逦－邋－Ｍ－逦ＡＡ＊，逦－逡逑－３．５邋Ｌ＿逦Ｉ逡逑寸邋ＶＯＯＯＯＮＯＣＳ寸逦—邋ＣＮ寸邋0邋卜邋ＯＯＯＣＮＣＯ＇ＯＯＮＯＣＭ逡逑ｔ￣ｈ邋—邋—邋一邋—邋—邋ｃ＾＜Ｎ＜Ｎｒ＾
ｔ￣ｈ邋—邋—邋一邋—邋—邋ｃ＾＜Ｎ＜Ｎｒ＾ｃ＾ｃ＾＜Ｎｒ0ｒ0邋ｃ0邋ｒ0邋寸寸逡逑顶点数量逡逑图２．１０算法在９５％Ｔｕｋｅｙ置信区间下顶点数量对运行时间影响的比较逡逑７Ｆ邋ｍ．逦：逡逑；－ａ－回溯？法逦；逡逑５邋－逦ａａ！＞逦上邋ｊ」逡逑ＡＡ２逦Ｗ逦－逡逑１３「—４逦：逡逑￣￣0￣￣￣￣＾￣￣＾邋0￣￣￣＾邋＾￣0邋＾５邋＾￣￣＾邋＾逡逑0４0４（＾＞寸逦卜邋ＯＯＯＯＯＮ邋—邋（Ｎｍ逡逑弧数量逡逑图２．１１算法在９５％Ｔｕｋｅｙ置信区间下弧数量对运行时间影响的比较逡逑２７逡逑
【参考文献】
相关期刊论文 前1条
1 Xin MA;Ya XU;Guo-qiang SUN;Li-xia DENG;Yi-bin LI;;State-chain sequential feedback reinforcement learning for path planning of autonomous mobile robots[J];Journal of Zhejiang University-Science C(Computers & Electronics);2013年03期
本文编号：2782965
本文链接：https://www.wllwen.com/kejilunwen/zidonghuakongzhilunwen/2782965.html
