组合优化问题的表示方式与进化优化算法研究

发布时间：2024-05-18 18:35

　　组合优化作为一类重要的优化问题,其涉及的领域甚为广泛,如信息技术领域、工业工程领域、交通运输领域以及经济管理领域。因此对组合优化问题的研究具有非常重要的实际意义。随着人工智能的发展,从上世纪80年代开始,进化算法逐渐成为求解组合优化问题的重要手段,在诸多领域得到了广泛的应用。在使用进化算法等智能优化算法求解组合优化问题的研究中,问题的表示方式在很大程度上决定了搜索空间的大小与形态,从而决定了问题的难度、影响着优化算法的性能。因此,本文以求解组合优化问题为核心目的,围绕组合优化问题的表示方式和单目标、多任务以及多目标进化优化算法两方面展开研究。主要工作可概括如下:1.针对约束满足问题设计了直接和间接混合的表示方式,进而基于混合表示方式设计了相应的多智能体进化算法。混合表示方式结合了直接表示方式操作简单、易于评价的优点和间接表示方式能解码生成质量较好的解的优点。另外针对问题特性和混合表示方式设计了邻域交叉算子、变异算子以及自学习算子等多智能体进化算法中智能体的若干行为。在250个标准二元约束满足问题测试集和79个图染色问题测试集上验证了所设计的基于混合表示方式的多智能体进化算法,实验结果表...

【文章页数】：133 页

【学位级别】：博士

【部分图文】：

图２．１图染色示例??例?２．１：??

构成，｜Ｄ，｜表示Ａ包含的离散值的个数。??（３）?—组约束Ｃ??Ｃ＝｛Ｃｉ（ｊｃ１），?Ｃ．ｉｘ１），，?Ｃｍ（ｘＪＴ，）｝?（２－２）??其中Ａ－＇，?／＝?１，?２，…，Ｗ为变量；Ｃ的一组子集，每个元组Ｇ（Ａ〇?＝沾，匈表示属于Ａ：＇的变量〈ｘ｛，??４〉￡分不能同时取值为....

图２．２智能体网格??２．４．２?针对智能体的进化算子??由２．３节可知，每个智能体包含直接表示方式和间接表示方式ｉ＜Ｐ＞两部分，??

第二章求解约束满足问题的混合表示方式及多智能体进化算法??麗濯＝??！??图２．２智能体网格??２．４．２?针对智能体的进化算子??由２．３节可知，每个智能体包含直接表示方式和间接表示方式ｉ＜Ｐ＞两部分，??因此进化算子既可以作用于也可以作用于Ｌ＜Ｐ＞。本章使用ＭＣＤ解码算法将Ｚ....

图２．３?ｉ，．，：对ＭＡＥＡＤ＆Ｉ－ＣＳＰ性能的影响??２．５．２?图染色测试集上的实验结果??

第二章求解约束满足问题的混合表示方式及多智能体进化算法??ＡＥＳ值。测试结果如图２．３所示，可以看出种群的大小对ＳＲ和ＭＥ指标的影响较小，??虽然ＡＥＳ的值不稳定，但是和种群大小没有明显的相关性。据此可以得知，??ＭＡＥＡＤ＆Ｉ－ＣＳＰ对种群大小的设置并不敏感，故在本章中，根据经....

图３．２四种初始化位置??定义３．２：?—个ＭＢＳ由模块列表和移动模式列表两部分组成，表示如下：??

始化到初始位置１，之后只能平行向左移动到不能再移动为止；??移动模式２：模块初始化到初始位置２，模块重复向下向左移动到不能再移动为止，??其中向下移动的优先级高于向左移动；??移动模式３：模块初始化到初始位置３，模块重复向左向下移动到不能再移动为止，??其中向左移动的优先级高于向....

本文编号：3977195