【摘要】：通常邻域是指以点为中心、以ε为半径的圆的内部点的全体，即集合叫做点的邻域，并称点为邻域的中心。在函数极值的数值求解中，邻域是一个非常重要的概念，函数的下降或上升都是在一点的邻域中寻求变化方向。在组合优化问题中，上述所讲的邻域的概念通常已不再适用。因此，在组合优化问题中，需要重新定义邻域的概念。组合优化问题的求解算法主要就是求得问题的全局最优解或近似最优解。
通常邻域是指以点为中心、以ε为半径的圆的内部点的全体，即集合叫做点的邻域，并称点为邻域的中心。在函数极值的数值求解中，邻域是一个非常重要的概念，函数的下降或上升都是在一点的邻域中寻求变化方向。在组合优化问题中，上述所讲的邻域的概念通常已不再适用。因此，在组合优化问题中，需要重新定义邻域的概念。
定义5．1：对于组合优化问题（D，F，f），D上的一个映射：N：S∈D→N（S）∈2D
称为一个领域映射，其中2D表示D的所有子集组成的集合， N（S）称为S的领域，S′∈N（S）称为S的一个邻居。
有了邻域的定义后，就可以定义局部最优解和全局最优解的概念。
定义5．2：若s*满足f（s*）≤（≥）f（s），其中，s∈N（s*）∩F，则称s*为f在F上的局部（Local）最小（最大）解。若f（s*）≤（≥）f（s），其中，s∈F，则称s*为f在F上的全局（Global）最小（最大）解。
以一维变量x为例，定义域为区间［1，10］中的整数点，如果采用如下领域定义：N（x） {＝ y∈Z＋｜ y－x≤ }1 ，目标值如图5-1所示，则x＝9为f的全局最优（最小）点，x＝5为f的局部最优（最小）点。
对于此组合优化问题，传统的求解算法是从一个初始点出发，在邻域中寻找使目标函数值更小的点，最后达到一个无法使目标函数值再下降的点。如图5-1所示，若以x ＝4为起点按传统的优化方法搜索最小值点，则搜索到x ＝5而停止，搜索到局部最优解，但不一定是问题的全局最优解。组合优化问题的求解算法主要就是求得问题的全局最优解或近似最优解。
图5-1 目标值图
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
