首页 | 官方网站   微博 | 高级检索  
相似文献
 共查询到19条相似文献,搜索用时 140 毫秒
1.
Tabu Search中集中性和多样性的自适应搜索策略   总被引:15,自引:0,他引:15  
近年来的研究表明,集中性与多样性策略在禁忌搜索中是非常重要的,但集中性与多样性常常又是矛盾的,如何解决集中性与多样性之间的矛盾就成为一个值得关注的话题,以组合优化中的著名难题TSP(traveling salesman problem)为例,提出了一种新颖的自适应搜索策略,通过邻域和候选集的相互配合,动态地调整候选集中分别用于集中性搜索与多样性搜索的元素个数,较好地解决了集中性与多样性的冲突问题.仿真实验表明,该算法是可行的和有效的。  相似文献   

2.
针对以旅行商问题(TSP)为代表的组合优化问题提出一种基于Rough集理论的两阶段禁忌搜索算法.该算法没有采用多数自适应禁忌搜索算法所用的动态调整禁忌搜索参数的方式平衡集中性搜索和多样性搜索,而是采用两阶段搜索策略.第一阶段着眼于多样性搜索.通过激励搜索过程远离起点,对解空间进行相当程度的探索,在此基础上构造希望区域决策表,继而获得希望区域.第二阶段着眼于集中性搜索.以包含希望区域的最佳解作为起点进行集中性搜索.在选择当前解时,利用多样性搜索得到的路径信息进行有条件的限制.TSP基准问题的计算结果表明该算法是可行有效的.  相似文献   

3.
多层前向神经网络的自适应禁忌搜索训练   总被引:2,自引:1,他引:2  
针对BP算法属于局部优化算法的不足,提出了一种新的全局优化算法——自适应禁忌搜索作为前向神经网络的训练算法。该算法通过邻域和候选集的相互配合,动态地调整候选集中分别用于集中性搜索与多样性搜索的元素个数,提高了算法运行的质量和效率。以经典的异或问题(XOR)为例,进行了对比研究。实验结果表明,该算法与BP算法相比明显提高了网络的收敛概率和收敛精度。  相似文献   

4.
独立任务分配的贪婪随机自适应搜索过程   总被引:2,自引:0,他引:2  
提出了一种贪婪随机自适应搜索过程求解异构环境下的独立任务分配问题。使用随机化的最小最小完成时间算法来产生问题的初始解,再通过变邻域下降算法来改进这个解,在变邻域下降算法中,为增强算法的空间勘探能力,外层局部搜索采用允许接收劣质解的策略,使用禁忌表来防止迂回搜索,使算法在多样性和集中性间取得了较好的平衡。与领域中的典型算法进行了仿真比较,结果表明提出的算法具有良好的性能。  相似文献   

5.
序列扩频系统的性能受到多用户干扰的严格制约。多用户检测方法被证明是限制这种干扰的一种有效方法。本文提出一种自适应Tabu搜索算法,用于序列扩频系统中的多用户检测,其中引入自适应集中性和多样性搜索策略,充分发挥短禁忌周期彻底搜索局部空间的能力。仿真实验表明,这种多用户检测方法具有接近最佳检测的误比特性能和较好的抗远近效应能力,并具有多项式计算复杂度。  相似文献   

6.
为提高组搜索优化算法求解多维函数优化问题的性能,提出一种结合逐维搜索、Metropolis准则、反方向视角和禁忌表策略的改进组搜索优化算法.逐维搜索策略逐维更新并评价成员位置,在每一维,更新的值与其他维组成候选位置,使用模拟退火的Metropolis准则来决定是否接受候选位置.反方向视角策略使成员按一定的概率做反方向搜索,禁忌表策略避免生产者始终保持不变.这些策略能更好地平衡算法的集中性和多样性.在典型测试函数上进行了仿真,结果表明改进策略是有效的,提高了组搜索算法求解多维函数优化问题的全局寻优能力和收敛速度.  相似文献   

7.
本文针对最小完工时间的Job-Shop调度问题提出了一种禁忌搜索算法,该算法使用插入算法构造尽可能好的初始解,然后用禁忌搜索算法改进当前解,在算法中对未被选中的候选解信息进行记忆,合理平衡了集中搜索与分散搜索。最后用基准实例进行仿真,实验结果表明该算法是可行的和有效的。  相似文献   

8.
为了增强局部搜索算法在求解最大割问题上的寻优能力,提高解质量,提出了一种多启动禁忌搜索(MSTS)算法。算法主要包括两个重要组件:一是用于搜索高质量局部优化解的禁忌搜索算法;二是具有全局搜索能力的重启策略。算法首先通过禁忌搜索组件获取局部优化解;然后应用设计的重启策略重新生成初始解并重启禁忌搜索过程。重启策略基于随机贪心的思想,综合利用了“构造”和“扰动”这两种方法生成新的起始解,来逃离局部最优的陷阱从而找到更高优度的解。采用了国际文献中公认的21个算例作为本算法的测试实验集并进行实算, 并与多个先进算法进行比较,MSTS算法在18个算例上得到最好解值,高于其他对比算法。实验结果表明,MSTS算法具有更强的寻优能力和更高的解质量。  相似文献   

9.
针对引力搜索算法局部搜索能力较弱,搜索过程容易出现早熟的现象,提出一种基于多样性和局部优化能力协同优化的引力搜索算法。将粒子群算法中局部最优解和细菌趋化中排斥操作的概念引入到引力搜索算法中,通过帮助粒子接近最优位置和逃离最差位置,改进了搜索算法中粒子的局部优化能力及种群多样性,并使用标准函数进行测试。结果表明,该算法能够实现全局搜索与局部搜索的平衡,最大程度地保持种群多样性,提高算法搜索能力。  相似文献   

10.
粗糙集理论中属性约简算法在保证解质量的情况下,效率比较低.针对这个问题提出一种基于记忆的启发式禁忌搜索算法,该算法称为TSAR(Tabu Search Attribute Reduction),是一个长期记忆的高性能TS算法.TSAR在利用邻域搜索方法的同时,又采用了广泛性和集中性模式,通过调用三个过程来产生及约简候选解,多参数智能化控制迭代次数,增大获得全局最优的机会,避免过早地陷入局部最优.TSAR和文献中算法相比,在解的质量上表现优异,而且计算的开销也很低.  相似文献   

11.
This paper addresses the application of the principles of feedback and self-controlling software to the tabu search algorithm. We introduce two new reaction strategies for the tabu search algorithm. The first strategy treats the tabu search algorithm as a target system to be controlled and uses a control-theoretic approach to adjust the algorithm parameters that affect search intensification. The second strategy is a flexible diversification strategy which can adjust the algorithm’s parameters based on the search history. These two strategies, combined with tabu search, form the Self Controlling Tabu Search (SC-Tabu) algorithm. The algorithm is implemented and tested on the Quadratic Assignment Problem (QAP). The results show that the self-controlling features of the algorithm make it possible to achieve good performance on different types of QAP instances.  相似文献   

12.
组合优化近似搜索算法中的超启发式发展趋势   总被引:1,自引:0,他引:1  
对组合优化中近似搜索算法采用的超启发式策略进行了总结和分类,并着重从强化和变化两个概念出发分析了不同超启发式的优缺点,探讨了其发展趋势,目的是为开发博采众长的混合近似搜索算法提供参考和指导。  相似文献   

13.
Nowadays, a promising way to obtain hybrid metaheuristics concerns the combination of several search algorithms with strong specialization in intensification and/or diversification. The flexible architecture of evolutionary algorithms allows specialized models to be obtained with the aim of providing intensification and/or diversification. The outstanding role that is played by evolutionary algorithms at present justifies the choice of their specialist approaches as suitable ingredients to build hybrid metaheuristics.This paper focuses on hybrid metaheuristics with evolutionary algorithms specializing in intensification and diversification. We first give an overview of the existing research on this topic, describing several instances grouped into three categories that were identified after reviewing specialized literature. Then, with the aim of complementing the overview and providing additional results and insights on this line of research, we present an instance that consists of an iterated local search algorithm with an evolutionary perturbation technique. The benefits of the proposal in comparison to other iterated local search algorithms proposed in the literature to deal with binary optimization problems are experimentally shown. The good performance of the reviewed approaches and the suitable results shown by our instance allow an important conclusion to be achieved: the use of evolutionary algorithms specializing in intensification and diversification for building hybrid metaheuristics becomes a prospective line of research for obtaining effective search algorithms.  相似文献   

14.
In this paper, the resource-constrained project scheduling problem with multiple execution modes for each activity is explored. This paper aims to find a schedule of activities such that the makespan of the schedule is minimized subject to the precedence and resource constraints. We present a two-phase genetic local search algorithm that combines the genetic algorithm and the local search method to solve this problem. The first phase aims to search globally for promising areas, and the second phase aims to search more thoroughly in these promising areas. A set of elite solutions is collected during the first phase, and this set, which acts as the indication of promising areas, is utilized to construct the initial population of the second phase. By suitable applications of the mutation with a large mutation rate, the restart of the genetic local search algorithm, and the collection of good solutions in the elite set, the strength of intensification and diversification can be properly adapted and the search ability retained in a long term. Computational experiments were conducted on the standard sets of project instances, and the experimental results revealed that the proposed algorithm was effective for both the short-term (with 5000 schedules being evaluated) and the long-term (with 50000 schedules being evaluated) search in solving this problem.   相似文献   

15.
The article describes the proposition and application of a local search metaheuristic for multi-objective optimization problems. It is based on two main principles of heuristic search, intensification through variable neighborhoods, and diversification through perturbations and successive iterations in favorable regions of the search space. The concept is successfully tested on permutation flow shop scheduling problems under multiple objectives and compared to other local search approaches. While the obtained results are encouraging in terms of their quality, another positive attribute of the approach is its simplicity as it does require the setting of only very few parameters.The metaheuristic is a key element of the Multi-Objective Optimization and Production Planning Solver MOOPPS. The software has been awarded the European Academic Software Award in Ronneby, Sweden (http://www.bth.se/llab/easa_2002.nsf), and has since been used for research and higher education in the mentioned problem domain (Geiger, 2006).  相似文献   

16.
We confront the job shop scheduling problem with sequence-dependent setup times and weighted tardiness minimization. To solve this problem, we propose a hybrid metaheuristic that combines the intensification capability of tabu search with the diversification capability of a genetic algorithm which plays the role of long term memory for tabu search in the combined approach. We define and analyze a new neighborhood structure for this problem which is embedded in the tabu search algorithm. The efficiency of the proposed algorithm relies on some elements such as neighbors filtering and a proper balance between intensification and diversification of the search. We report results from an experimental study across conventional benchmarks, where we analyze our approach and demonstrate that it compares favorably to the state-of-the-art methods.  相似文献   

17.
The dynamic space allocation problem (DSAP) presented in this paper considers the task of assigning items (resources) to locations during a multi-period planning horizon such that the cost of rearranging the items is minimized. Three tabu search heuristics are presented for this problem. The first heuristic is a simple basic tabu search heuristic. The second heuristic adds diversification and intensification strategies to the first, and the third heuristic is a probabilistic tabu search heuristic. To test the performances of the heuristics, a set of test problems from the literature is used in the analysis. The results show that the tabu search heuristics are efficient techniques for solving the DSAP. More importantly, the proposed tabu search heuristic with diversification/intensification strategies found new best solutions using less computation time for one-half of all the test problems.  相似文献   

18.
ABSTRACT

Biclustering in gene-expression data is a subset of the genes demonstrating consistent patterns over a subset of the conditions. Recently, the most of research in biclustering involving statistical and graph-theoretic approaches by adding or deleting rows and/or columns in the data matrix based on some constraints. This is an exhaustive search of the space, and hence the solutions may not be feasible. The proposed work finds the significant biclusters in large expression data using shuffled cuckoo search with Nelder–Mead (SCS-NM). The diversification and intensification of the search space are obtained through shuffling and simplex NM, respectively. The proposed work is tested on four benchmark datasets, and the results are compared with the swarm intelligence techniques and the various biclustering algorithms. The results show that there is significant improvement in the fitness value of proposed work SCS-NM. In addition, the work determines the biological relevance of the biclusters with Gene Ontology in terms of function, process and component.  相似文献   

19.
In this paper a new VRP variant the Multiple Trip Vehicle Routing Problem with Backhauls (MT-VRPB) is investigated. The classical MT-VRP model is extended by including the backhauling aspect. An ILP formulation of the MT-VRPB is first presented and CPLEX results for small and medium size instances are reported. For large instances of the MT-VRPB a Two-Level VNS algorithm is developed. To gain a continuous balanced intensification and diversification during the search process VNS is embedded with the sequential VND and a multi-layer local search approach. The algorithm is tested on a set of new MT-VRPB data instances which we generated. Interesting computational results are presented. The Two-Level VNS produced excellent results when tested on the special variant of the VRPB.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司    京ICP备09084417号-23

京公网安备 11010802026262号