智能优化算法的性能及搜索空间研究

《智能优化算法的性能及搜索空间研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、山东大学博士学位论文摘要优化作为一个重要的科学分支，一直受到人们的广泛重视，它对多个学科产生了重大影响，并在诸多工程领域得到迅速推广和应用，己成为不同领域中很多工作不可或缺的工具。优化算法基于某种思想和机制，通过一定的途径来得到满足用户要求的解。现在，求解线性规划、非线性规划以及随机规划、几何规划、整数规划等各种最优化问题的理论研究发展迅速，新方法不断出现，实际应用日益广泛。在计算机技术的推动下。最优化理论与方法在经济计划、工程设计、生产管理、交通运输等方面得到了广泛应用，成为一门十分活跃的学科。很多优化问题如旅行商问题、设备布局问题

2、、生产调度问题等等，已被证明是NP完全问题，至今没有有效的多项式时间解法。用传统的最优化方法求解，需要的计算时间与问题的规模成指数关系。因此，人们转而求其次，发展了很多随机性搜索算法，希望在有限的时间内求得问题的次优解或近优解，如蒙特卡罗模拟、模拟退火、遗传算法、禁忌搜索及其混合优化策略等。智能优化算法作为新兴的搜索算法，一般是指利用自然界的生物系统与优化过程的某些相似性而逐步发展起来的优化算法，如遗传算法、粒子群算法、蚁群算法等，它们通过对搜索空间中的一组解按某些概率规则操作得到下一组解．因此算法本身的搜索机制决定算法对空间的全局搜

3、索能力和局部寻优能力，从而决定算法的搜索性能，即是否能较快地收敛于全局最优解。同时，由于变量取值、约束复杂等使得搜索空间中可行解与不可行解交叉分布，空间结构很不规则，往往造成智能优化算法得到不可行解的无效接索过多，极大地影响搜索速度，且算法不能很好地收敛到最优解。因此，本论文主要围绕智能优化算法的空间搜索能力，从算法搜索机制和搜索空间结构两个方面，研究增强算法的全局搜索能力的方法，同时兼顾局部寻优能力，以避免算法陷入局部最优，提高搜索性能。此前的智能优化算法，在搜索过程中不断繁殖好解并择优保留个体，导致有效成分缺失，群体多样性降低，从

4、而使算法失去了探索新空间区域的能力，易于陷入局部最优。而算法运行后期局部搜索能力不强，收敛速度过慢，山东大学博士学位论文得到的解的质量不高。权衡算法的空间探测和开发能力，即大范围全局搜索和小范围局部寻优能力，并且在算法运行过程中有效控制搜索的进行，才能使算法具有较好的搜索性能，提高收敛速度和解的质量。1，针对算法种群多样性减小导致的算法失去空间探索能力的问题，在算法迭代过程中以合理的方式接受劣解，以增加种群的多样性，可以避免算法陷入局部最优，从而提高算法的搜索性能。变异操作是产生种群多样性的根本，交叉(包括信息交互或传递)起加速作用。

5、因此选用仅包含变异操作的进化规划算法，引入退火概率的选择方式，每次迭代以退火概率接受劣解，形成退火进化规划算法。经证明这种算法是全局收敛的，可有效地避免局部最优，较快地达到最优解。通过估计算法种群以概率l包含最优解的速度和达到收敛的最大时间，发现退火因子会影响算法的收敛速度，通过选择合适的退火因子，可以提高算法的收敛速度。2．在算法的搜索过程中以当前信息为基础不断产生新解，在牺牲部分时间性能的条件下，也可以扩展搜索范围。本文利用组合优化问题的解的模式概念，通过比较种群中的解包含的相同模式，在迭代过程中产生新解来提高算法的全局搜索能力和

6、解的质量。(1)首先改变利用极值操作的个体解的变量适应度定义，使其与目标函数相关。经实验证实，新的目标函数适应度可较大程度提高个体的搜索能力。应用新的变量适应度定义，设计了基于模式的极值进化算法。解的模式信息的利用增强了算法的局部搜索能力，较好地改善了解的质量。最后证明了算法的收敛性。(2)基于新的目标函数适应度，分析迭代过程中产生的新解对搜索的影响作用。然后以拓扑进化网络描述的生物进化模型为结构，设计具有可变种群规模的网络拓扑进化算法。经过对比，该算法明显扩展了搜索的范围。由于网络拓扑进化算法不设定解的变异方式，因而可以采用各种现有

7、的变异方法，具有广泛的可结合性。该算法主要用于离散优化问题，然而通过将连续变量转换成二进制编码，以相同取值的二进制“位”表示解的相同部分，算法也可应用于连续函数优化。Ⅱ山东大学博士学位论文优化问题搜索空间庞大、算法搜索的随机性与搜索速度之间的矛盾，也在很大程度上影响了算法性能。大部分智能优化算法属于全局搜索算法，都是在问题的全空间上进行搜索，当问题规模变大时，搜索空间迅速膨胀．此前的智能优化算法都是在不明确空间结构的情况下进行寻优，所以其盲目性很大，随着优化问题规模的增大，算法的搜索时间往往以指数速度增长。目前所研究的确定型模型，一般

8、都有确定的空间结构，但是算法在搜索过程中不了解最优解和空间结构的关系，因此要改善算法的性能，除了设计更为合理的搜索机制，研究问题的搜索空间也有重要意义。1．智能优化算法通过在空间的搜索来寻找问题的最优解，因此了解搜索空间