首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到10条相似文献,搜索用时 93 毫秒
1.
This paper presents the investigation of an evolutionary multi-objective simulated annealing (EMOSA) algorithm with variable neighbourhoods to solve the multi-objective multicast routing problems in telecommunications. The hybrid algorithm aims to carry out a more flexible and adaptive exploration in the complex search space by using features of the variable neighbourhood search to find more non-dominated solutions in the Pareto front. Different neighbourhood strictures have been designed with regard to the set of objectives, aiming to drive the search towards optimising all objectives simultaneously. A large number of simulations have been carried out on benchmark instances and random networks with real world features including cost, delay and link utilisations. Experimental results demonstrate that the proposed EMOSA algorithm with variable neighbourhoods is able to find high-quality non-dominated solutions for the problems tested. In particular, the neighbourhood structures that are specifically designed for each objective significantly improved the performance of the proposed algorithm compared with variants of the algorithm with a single neighbourhood.  相似文献   

2.
蚁群遗传混合算法   总被引:2,自引:0,他引:2  
将蚁群遗传混合算法分别求解离散空间的和连续空间优化问题.求解旅行商问题的混合算法是以遗传算法为整个算法的框架,利用了蚁群算法中的信息素特性的进行交叉操作;根据旅行商问题的特点,给出了4种变异策略;针对遗传算法存在的过早收敛问题,加入2-0pt方法对问题求解进行了局部优化.与模拟退火算法、标准遗传算法和标准蚁群算法进行比较,4种混合算法效果都比较好,策略D的混合算法效果最好.求解连续空间优化问题是以蚁群算法为整个算法的框架,加入遗传算法的交叉操作和变异操作,用测试函数验证了混合蚁群算法的正确性.  相似文献   

3.
Aiming at constructing a delay and delay variation bounded Steiner tree in the real-time streaming media communication, in this paper, we discuss a multicast routing algorithm based on searching a directed graph (MRASDH). During the process of the construction of the multicast tree, some nodes and links in the network topology do not affect the outcome of the constructed tree. Therefore, based on the thought of shrinking the search space through deleting these non-relative nodes and edges to the utmost, the ant algorithm is utilized to generate a directed sub-graph of the network topology for each destination node, in which each node owns a bounded out-degree. And all these sub-graphs can be merged into a new directed graph that serves as the new search space. In the new space, the simulated annealing algorithm is applied to obtain a multicast tree that satisfies the condition for the optimization. The performance analysis and simulation results demonstrate that this algorithm can effectively construct a delay and delay variation bounded multicast tree. They also show that the algorithm have lower time complexity than the current ones, which means a much better result would be achieved when the system scale rises greatly.  相似文献   

4.
提出了一种理想化的模拟仿生搜索算法——扰动算法 ,以此方法为基础 ,分析了遗传算法的搜索过程和效率问题 ,阐明了遗传算法作为一种次优算法的有效性 .相对于遗传算法的生物解释 ,本文给出了相应的物理解释 .同时 ,本文为遗传算法、进化策略和模拟退火算法找到了一种统一的物理解释 ,揭示了这些重要的仿生类算法实质上的相似性 .  相似文献   

5.
Stochastic global search algorithms such as genetic algorithms are used to attack difficult combinatorial optimization problems. However, genetic algorithms suffer from the lack of a convergence proof. This means that it is difficult to establish reliable algorithm braking criteria without extensive a priori knowledge of the solution space. The hybrid genetic algorithm presented here combines a genetic algorithm with simulated annealing in order to overcome the algorithm convergence problem. The genetic algorithm runs inside the simulated annealing algorithm and provides convergence via a Boltzmann cooling process. The hybrid algorithm was used successfully to solve a classical 30-city traveling salesman problem; it consistently outperformed both a conventional genetic algorithm and a conventional simulated annealing algorithm. This work was supported by the University of Colorado at Colorado Springs.  相似文献   

6.
A comparison of local search methods for flow shop scheduling   总被引:1,自引:0,他引:1  
Local search techniques are widely used to obtain approximate solutions to a variety of combinatorial optimization problems. Two important categories of local search methods are neighbourhood search and genetic algorithms. Commonly used neighbourhood search methods include descent, threshold accepting, simulated annealing and tabu search. In this paper, we present a computational study that compares these four neighbourhood search methods, a genetic algorithm, and a hybrid method in which descent is incorporated into the genetic algorithm. The performance of these six local search methods is evaluated on the problem of scheduling jobs in a permutation flow shop to minimize the total weighted completion time. Based on the results of extensive computational tests, simulated annealing is found to generate better quality solutions than the other neighborhood search methods. However, the results also indicate that the hybrid genetic descent algorithm is superior to simulated annealing.  相似文献   

7.
The vehicle routing problem (VRP) under capacity and distance restrictions involves the design of a set of minimum cost delivery routes, originating and terminating at a central depot, which services a set of customers. Each customer must be supplied exactly once by one vehicle route. The total demand of any vehicle must not exceed the vehicle capacity. The total length of any route must not exceed a pre-specified bound. Approximate methods based on descent, hybrid simulated annealing/tabu search, and tabu search algorithms are developed and different search strategies are investigated. A special data structure for the tabu search algorithm is implemented which has reduced notably the computational time by more than 50%. An estimate for the tabu list size is statistically derived. Computational results are reported on a sample of seventeen bench-mark test problems from the literature and nine randomly generated problems. The new methods improve significantly both the number of vehicles used and the total distances travelled on all results reported in the literature.  相似文献   

8.
Recently proved successful for variants of the vehicle routing problem (VRP) involving time windows, genetic algorithms have not yet shown to compete or challenge current best search techniques in solving the classical capacitated VRP. A new hybrid genetic algorithm to address the capacitated VRP is proposed. The basic scheme consists in concurrently evolving two populations of solutions to minimize total travelled distance using genetic operators combining variations of key concepts inspired from routing techniques and search strategies used for a time variant of the problem to further provide search guidance while balancing intensification and diversification. Results from a computational experiment over common benchmark problems report the proposed approach to be very competitive with the best-known methods.  相似文献   

9.
In this article, we intend to model and optimize the bullwhip effect (BWE) and net stock amplification (NSA) in a three-stage supply chain consisting of a retailer, a wholesaler, and a manufacturer under both centralized and decentralized scenarios. In this regard, firstly, the causes of BWE and NSA are mathematically formulated using response surface methodology (RSM) as a multi-objective optimization model that aims to minimize the BWE and NSA on both chains. The simultaneous analysis of the BWE and NSA is considered as the main novelty of this paper. To tackle the addressed problem, we propose a novel multi-objective hybrid evolutionary approach called MOHES; MOHES is a hybrid of two known multi-objective algorithms i.e. multi-objective electro magnetism mechanism algorithm (MOEMA) and population-based multi-objective simulated annealing (PBMOSA). We applied a co-evolutionary strategy for this purpose with eligibility of both algorithms. Proposed MOHES is compared with three common and popular algorithms (i.e. NRGA, NSGAII, and MOPSO). Since the utilized algorithms are very sensitive to parameter values, RSM with the multi-objective decision making (MODM) approach is employed to tune the parameters. Finally, the hybrid algorithm and the singular approaches are compared together in terms of some performance measures. The results indicate that the hybrid approach achieves better solutions when compared with the others, and also the results show that in a decentralized chain, the order batching factor and the demand signal processing in wholesaler are the most important factors on BWE. Conversely, in a centralized chain, factors such as rationing, shortage gaming, and lead time are the most effective at reducing the BWE.  相似文献   

10.
On the basis of modularity optimization, a genetic algorithm is proposed to detect community structure in networks by defining a local search operator. The local search operator emphasizes two features: one is that the connected nodes in a network should be located in the same community, while the other is “local selection” inspired by the mechanisms of efficient message delivery underlying the small‐world phenomenon. The results of community detection for some classic networks, such as Ucinet and Pajek networks, indicate that our algorithm achieves better community structure than other methodologies based on modularity optimization, such as the algorithms based on betweenness analysis, simulated annealing, or Tasgin and Bingol's genetic algorithm. © 2009 Wiley Periodicals, Inc. Complexity, 2010  相似文献   

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

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