首页 理论教育搜索算法的方法及技巧的介绍

搜索算法的方法及技巧的介绍

【摘要】:多目标优化问题大部分属于NP-hard问题,其优化搜索的结果得到问题最优解或Pareto最优解集。基于邻域搜索思想,采用动态插入快速启发式算法,可解决微波与激光混合链路中继系统在应急条件下的多目标资源调度问题。进化算法是模仿生物群体活动规律的一种全局优化概率搜索优化算法,采用迭代计算方式,从初始解开始通过迭代操作不断地改进当前解直到获得满意的可行解,主要包括遗传算法、进化策略、进化规划3类。

多目标优化问题大部分属于NP-hard问题,其优化搜索的结果得到问题最优解或Pareto最优解集。在解决实际应用问题时,问题的时间和空间复杂度很大,通过近似算法可获得多目标问题的有效最优解。近似算法主要包括启发式算法和进化算法。

启发式算法包括局部搜索算法和贪婪算法等,是一种通过启发式策略指导算法的搜索过程,在决策者能够接收的计算代价内获得问题可行解的算法。局部搜索算法的基本思想是首先选取一个可行解,构造其邻域,在搜索过程中始终选择邻域中距离目标最近的方向进行搜索,以找到更好的可行解。基于邻域搜索思想,采用动态插入快速启发式算法,可解决微波与激光混合链路中继系统在应急条件下的多目标资源调度问题。

进化算法是模仿生物群体活动规律的一种全局优化概率搜索优化算法,采用迭代计算方式,从初始解开始通过迭代操作不断地改进当前解直到获得满意的可行解,主要包括遗传算法、进化策略、进化规划3类。遗传算法是进化算法中最早产生、具有广泛应用和影响的研究领域。

1975年美国Michigan大学的J.Holland教授等人提出的遗传算法(GA)是受生物进化论的启发而形成的一种并行随机搜索方法,其基本原理是仿效生物界中的“物竞天择、适者生存”的自然选择机制。遗传算法中群体的每个个体代表问题的一个解,称为染色体,染色体的好坏用适应度来衡量,优秀个体根据适应度从父代选出,通过进行交叉、变异操作形成子代群体,通过重复遗传操作使算法收敛于最好的染色体,即得到问题的最优解。遗传算法除具有进化算法的优点,还具有自身独有的特点:遗传算法针对解的编码进行操作,可通过合理设置的适应度函数直接求解不同类型的问题,具有广泛的应用范围;通过选择、交叉、变异操作可快速收敛于全局最优解,全局优化能力强;对于目标函数及搜索空间特征无特别要求,通用性很强,适用于解决复杂的优化问题;算法各个基本操作可扩充性强、易与其他算法结合、普适性较好。

近年来人工智能和人工生命技术兴起,一些新型进化算法随之出现,如蚁群算法、粒子群算法、量子进化算法等。

由于进化算法具有良好的普适性及其广泛的应用,使其在求解复杂单目标优化问题时具有充分优势。通过将小生境思想引入到遗传算法中,提出了一种改进小生境遗传算法,用以解决微波与激光混合链路中继卫星系统资源调度问题,并通过仿真证明了算法能够有效得到优化问题的最优解。

实际科学研究和工程实际中许多优化问题具有相互冲突目标,这些问题的解方案是一个最优解集,即Pareto最优解集。针对这种多目标优化问题,出现了多目标优化算法。包括有向量评估遗传算法(VEGA)、多目标遗传算法(MOGA)、强度Pareto进化算法(SPEA)、改进强度Pareto进化算法(SPEA2)、非支配排序遗传算法(NSGA)等。这些算法大都基于Pareto优化方法,同时融入了多种概念和机制,进一步改善了算法搜索效率

微波与激光混合链路中继卫星资源调度问题中,为充分利用卫星终端资源,在满足时间窗口约束、任务传输约束等条件下,考虑到天线功耗的限制要求算法能够在尽可能短的时间内获得终端功耗最少的结果,同时为达到较好的中继效果还要求资源在一定时间内调度尽可能多的中继任务。而基于Pareto思想的多目标进化算法具有良好的全局搜索能力,不需要决策者提供各目标优先级权值,能够对混合系统静态初始资源调度进行综合求解。