首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 31 毫秒
1.
This paper presents a new class of heuristics which embed an exact algorithm within the framework of a local search heuristic. This approach was inspired by related heuristics which we developed for a practical problem arising in electronics manufacture. The basic idea of this heuristic is to break the original problem into small subproblems having similar properties to the original problem. These subproblems are then solved using time intensive heuristic approaches or exact algorithms and the solution is re-embedded into the original problem. The electronics manufacturing problem where we originally used the embedded local search approach, contains the Travelling Salesman Problem (TSP) as a major subproblem. In this paper we further develop our embedded search heuristic, HyperOpt, and investigate its performance for the TSP in comparison to other local search based approaches. We introduce an interesting hybrid of HyperOpt and 3-opt for asymmetric TSPs which proves more efficient than HyperOpt or 3-opt alone. Since pure local search seldom yields solutions of high quality we also investigate the performance of the approaches in an iterated local search framework. We examine iterated approaches of Large-Step Markov Chain and Variable Neighbourhood Search type and investigate their performance when used in combination with HyperOpt. We report extensive computational results to investigate the performance of our heuristic approaches for asymmetric and Euclidean Travelling Salesman Problems. While for the symmetric TSP our approaches yield solutions of comparable quality to 2-opt heuristic, the hybrid methods proposed for asymmetric problems seem capable of compensating for the time intensive embedded heuristic by finding tours of better average quality than iterated 3-opt in many less iterations and providing the best heuristic solutions known, for some instance classes.  相似文献   

2.
In this paper we apply the kernel search framework to the solution of the strongly NP-hard multi-dimensional knapsack problem (MKP). Kernel search is a heuristic framework based on the identification of a restricted set of promising items (kernel) and on the exact solution of ILP sub-problems. Initially, the continuous relaxation of the MKP, solved on the complete set of available items, is used to identify the initial kernel. Then, a sequence of ILP sub-problems are solved, where each sub-problem is restricted to the present kernel and to a subset of other items. Each ILP sub-problem may find better solutions with respect to the previous one and identify further items to insert into the kernel. The kernel search was initially proposed to solve a complex portfolio optimization problem. In this paper we show that the method has general key features that make it appropriate to solve other combinatorial problems using binary variables to model the decisions to select or not items. We adapt the kernel search to the solution of MKP and show that the method is very effective and efficient with respect to known problem-specific approaches. Moreover, the best known values of some MKP benchmark problems from the MIPLIB library have been improved.  相似文献   

3.
Hyper-heuristics are emerging methodologies that perform a search over the space of heuristics in an attempt to solve difficult computational optimization problems. We present a learning selection choice function based hyper-heuristic to solve multi-objective optimization problems. This high level approach controls and combines the strengths of three well-known multi-objective evolutionary algorithms (i.e. NSGAII, SPEA2 and MOGA), utilizing them as the low level heuristics. The performance of the proposed learning hyper-heuristic is investigated on the Walking Fish Group test suite which is a common benchmark for multi-objective optimization. Additionally, the proposed hyper-heuristic is applied to the vehicle crashworthiness design problem as a real-world multi-objective problem. The experimental results demonstrate the effectiveness of the hyper-heuristic approach when compared to the performance of each low level heuristic run on its own, as well as being compared to other approaches including an adaptive multi-method search, namely AMALGAM.  相似文献   

4.
The solution of intractable problems implies the use of heuristics. Quantum computers may find use for optimization problems, but have yet to solve any NP-hard problems. This paper demonstrates results in game theory for domain transference and the reuse of problem-solving knowledge through the application of learned heuristics. It goes on to explore the possibilities for the acquisition of heuristics for the solution of the NP-hard TSP problem. Here, it is found that simple heuristics (e.g., pairwise exchange) often work best in the context of more or less sophisticated experimental designs. Often, these problems are not amenable to exclusive logic solutions; but rather, require the application of hybrid approaches predicated on search. In general, such approaches are based on randomization and supported by parallel processing. This means that heuristic solutions emerge from attempts to randomize the search space. The paper goes on to present a constructive proof of the unbounded density of knowledge in support of the Semantic Randomization Theorem (SRT). It highlights this result and its potential impact upon the community of machine learning researchers.  相似文献   

5.
Functional decomposition is a process of splitting a complex circuit into smaller sub-circuits. There exist two major strategies in decomposition, namely, serial and parallel decomposition. In serial decomposition the problem the complex function represented as a truth table with support set variables and partitioned into free and bout set variables. The minterms corresponding to the bound set variables are represented as an equivalent function called the predecessor function. Equivalent minterms of the bound set variables are assigned an output code. The assigned output codes and the free set variable minterms are represented as the successor function. Serial decomposition is further categorized into disjoint and non-disjoint decomposition, when the free and bound set variables are disjoint and non-disjoint respectively. This paper deals with the problem of determining the set of best free and bound variables (variable partitioning problem) for disjoint serial decomposition. Variable partitioning is the first step in decomposition process. An efficient variable partition algorithm is one that determines the set of all free and bound set variables that satisfy the decomposition theorem in minimal time and by exploring the search space effectively. This will allow the decomposition algorithm to determine the best variable partition of a function that results in smaller decomposed functions and with maximum number of do not cares in these functions. Classical approaches to determine the best free and bound set use exhaustive search methods. The time and memory requirements for such approaches are exponential or super exponential.A novel heuristic search approach is proposed to determine the set of good variable partitions in minimal time by minimally exploring the search space. There are two heuristics employed in the proposed search approach, (1) r-admissibility based heuristic or pruned breadth first search (PBFS) approach and (2) Information relation based heuristic or improved pruned breadth first search (IPBFS) approach. The r-admissibility based heuristic is based on r-partition characteristics of the free and bound set variables. The information relation and measure based heuristic is based on information relationship of free and bound set variables that are expressed as r-partition heuristics. The proposed variable partition search approach has been successfully implemented and test with MCNC and Espresso benchmarks and the results indicate that the time complexity is comparable to r-admissible heuristic algorithm and the quality of solution is comparable to exact variable partitioning algorithm. A comparison of PBFS and IPBFS heuristics for certain benchmarks are also discussed in this paper.  相似文献   

6.
The paper addresses the problem of multi-depot vehicle routing in order to minimize the delivery time of vehicle objective. Three hybrid heuristics are presented to solve the multi-depot vehicle routing problem. Each hybrid heuristic combines elements from both constructive heuristic search and improvement techniques. The improvement techniques are deterministic, stochastic and simulated annealing (SA) methods. Experiments are run on a number of randomly generated test problems of varying depots and customer sizes. Our heuristics are shown to outperform one of the best-known existing heuristic. Statistical tests of significance are performed to substantiate the claims of improvement.  相似文献   

7.
A bi-objective competitive facility location and design problem is considered. The problem of obtaining a complete representation of the efficient set and its corresponding Pareto-front has been previously tackled through exact general methods, but they require high computational effort. In this work, we propose a new evolutionary multi-objective optimization algorithm, named FEMOEA, which deals with the problem at hand in a fast and efficient way. It combines ideas from different multi-objective and single-objective optimization evolutionary algorithms, although it also incorporates new devices which help to reduce the computational requirements, and also to improve the quality of the provided solutions. The performance of the algorithm is analyzed by comparing it to other (meta)heuristics previously proposed in the literature. In particular, the reference algorithms MOEA/D, SPEA2 and NSGA-II have been considered. A comprehensive computational study shows that the new heuristic method outperforms, on average, the three heuristic algorithms. Additionally, it reduces, on average, the computing time of the exact methods by approximately 99%, and this offering high-quality discrete approximations of the true Pareto-front.  相似文献   

8.
This paper examines optimization problems associated with computer network design and routing. The emphasis is focused on modifying conventional heuristic search procedures to enhance their solution optimization capability.The techniques discussed include fuzzy heuristics, adaptive compositions of heuristics and suboptimum algorithms based on dynamic programming concepts. The discussion is illustrated with examples and experimental computer implementation results.The results obtained demonstrate that the application of the above methods improves solutions derived by means of conventional heuristic procedures and brings such solutions closer to optimum ones.  相似文献   

9.
In a recent paper by Liu et al. [Exact algorithm and heuristic for the closest string problem, Computers & Operations Research 2011;38:1513-20], a polynomial time heuristic procedure is proposed for the closest string problem (CSP). Such heuristic called LDDA_LSS is a combination of a previously published approximation algorithm and local search strategies. This paper points out that an instant algorithm deriving a feasible solution directly from the continuous relaxation solution of a standard ILP formulation of CSP already strongly outperforms LDDA_LSS both in terms of solution quality and computing time. Two core based procedures are then proposed that further improve the results of the instant algorithm. Based on these results, we conclude that such LP-based approaches for their efficiency and simplicity should be used as a benchmark for future heuristics on CSP.  相似文献   

10.
李婷  吴敏  何勇 《控制与决策》2013,28(10):1513-1519
提出一种相角粒子群优化算法求解多目标优化问题。该算法采用相角映射实现了粒子在相角空间上仅依赖于归一化多目标函数的快速搜索,在粒子飞行信息共享机制上引入共享池概念,提出基于关联支配排序和相似度排序的共享池更新策略,提高了Pareto解的多样性。采用Sigma领导策略和混沌变异操作,平衡了算法的快速搜索能力和全局寻优能力。标准多目标测试函数和电力系统广域阻尼控制多目标优化算例表明了所提出算法的可行性和有效性。  相似文献   

11.
In this paper, we address the 2-stage assembly scheduling problem where there are m machines in the first stage to manufacture the components of a product and one assembly station (machine) in the second stage. The objective considered is the minimisation of the total completion time. Since the NP-hard nature of this problem is well-established, most previous research has focused on finding approximate solutions in reasonable computation time. In our paper, we first review and derive a number of problem properties and, based on these ideas, we develop a constructive heuristic that outperforms the existing constructive heuristics for the problem, providing solutions almost in real-time. Finally, for the cases where extremely high-quality solutions are required, a variable local search algorithm is proposed. The computational experience carried out shows that the algorithm outperforms the best existing metaheuristic for the problem. As a summary, the heuristics presented in the paper substantially modify the state-of-the-art of the approximate methods for the 2-stage assembly scheduling problem with total completion time objective.  相似文献   

12.
This paper presents comparisons of some recent improving strategies on multi-objective particle swarm optimization (MOPSO) algorithm which is based on Pareto dominance for handling multiple objective in continuous review stochastic inventory control system. The complexity of considering conflict objectives such as cost minimization and service level maximization in the real-world inventory control problem needs to employ more exact optimizers generating more diverse and better non-dominated solutions of a reorder point and order size system. At first, we apply the original MOPSO employed for the multi-objective inventory control problem. Then we incorporate the mutation operator to maintain diversity in the swarm and explore all the search space into the MOPSO. Next we change the leader selection strategy used that called geographically-based system (Grids) and instead of that, crowding distance factor is also applied to select the global optimal particle as a leader. Also we use ε-dominance concept to bound archive size and maintain more diversity and convergence in the MOPSO for optimizing the inventory control problem. Finally, the MOPSO algorithms created using these strategies are evaluated and compared with each other in terms of some performance metrics taken from the literature. The results indicate that these strategies have significant influences on computational time, convergence, and diversity of generated Pareto optimal solutions.  相似文献   

13.
A selection hyper-heuristic is a high level search methodology which operates over a fixed set of low level heuristics. During the iterative search process, a heuristic is selected and applied to a candidate solution in hand, producing a new solution which is then accepted or rejected at each step. Selection hyper-heuristics have been increasingly, and successfully, applied to single-objective optimization problems, while work on multi-objective selection hyper-heuristics is limited. This work presents one of the initial studies on selection hyper-heuristics combining a choice function heuristic selection methodology with great deluge and late acceptance as non-deterministic move acceptance methods for multi-objective optimization. A well-known hypervolume metric is integrated into the move acceptance methods to enable the approaches to deal with multi-objective problems. The performance of the proposed hyper-heuristics is investigated on the Walking Fish Group test suite which is a common benchmark for multi-objective optimization. Additionally, they are applied to the vehicle crashworthiness design problem as a real-world multi-objective problem. The experimental results demonstrate the effectiveness of the non-deterministic move acceptance, particularly great deluge when used as a component of a choice function based selection hyper-heuristic.  相似文献   

14.
The set multicovering or set k-covering problem is an extension of the classical set covering problem, in which each object is required to be covered at least k times. The problem finds applications in the design of communication networks and in computational biology. We describe a GRASP with path-relinking heuristic for the set k-covering problem, as well as the template of a family of Lagrangean heuristics. The hybrid GRASP Lagrangean heuristic employs the GRASP with path-relinking heuristic using modified costs to obtain approximate solutions for the original problem. Computational experiments carried out on 135 test instances show experimentally that the Lagrangean heuristics performed consistently better than GRASP as well as GRASP with path-relinking. By properly tuning the parameters of the GRASP Lagrangean heuristic, it is possible to obtain a good trade-off between solution quality and running times. Furthermore, the GRASP Lagrangean heuristic makes better use of the dual information provided by subgradient optimization and is able to discover better solutions and to escape from locally optimal solutions even after the stabilization of the lower bounds, when other Lagrangean strategies fail to find new improving solutions.  相似文献   

15.
Minimizing the amount of spill code is still an open problem in code generation and optimization. The amount of spill code depends on both the register allocation algorithm and the pre‐allocation instruction scheduling algorithm that controls the register pressure. In this paper, we focus on the impact of pre‐allocation instruction scheduling on the amount of spill code. Many heuristic techniques have been proposed to do instruction scheduling with the objective of minimizing register pressure and consequently the amount of spill code. However, the performance of these heuristic techniques has not been studied relative to optimality on real large‐scale programs. In this paper, we present an experimental study that evaluates the performance of several pre‐allocation scheduling heuristics. The evaluation involves computing an experimental lower bound on the size of gap between each heuristic's performance and optimal performance. We also propose a simple heuristic technique based on a specific permutation of two basic priority schemes and experimentally evaluate the performance of this technique compared with other heuristics, including the heuristics implemented in the LLVM open‐source Compiler. The evaluation is carried out by running SPEC CPU2006 on real x86‐64 hardware and measuring both the amount of spill code and the execution time. The results of our study show that the proposed heuristic technique gives better overall performance than LLVM's best heuristic on x86‐64, although it produces slightly more spilling. The proposed heuristic has better overall performance, because it achieves a better balance between register pressure and instruction‐level parallelism (ILP). This result shows the importance of ILP in pre‐allocation scheduling even on out‐of‐order machines. Furthermore, the results of the study show that there is a large gap between the performance of any of the studied heuristics and optimal performance; even the best heuristic in the study produces significantly more spill code than the optimal amount. This experimental result quantifies the intuitive belief that it is unlikely to find a heuristic that works well in all cases, thus showing the need for more rigorous solutions using combinatorial approaches. The paper discusses the challenges and complexities that are involved in developing such rigorous solutions. Copyright © 2014 John Wiley & Sons, Ltd.  相似文献   

16.
As an evolutionary approach to solve constrained multi-objective optimization problems (CMOPs), recently an algorithm using the two-stage non-dominated sorting and the directed mating (TNSDM) was proposed. In TNSDM, the directed mating utilizes infeasible solutions dominating feasible solutions in the objective space to generate offspring. The directed mating significantly contributes to the search performance improvement in evolutionary constrained multi-objective optimization. However, the conventional directed mating has two problems. First, since the conventional directed mating selects a pair of parents based on the conventional Pareto dominance, two parents having different search directions may be mated. Second, the directed mating cannot be performed in some cases especially when the population has few useful infeasible solutions. In this case, the conventional mating using only feasible solutions is performed instead. Thus, the effectiveness of the directed mating cannot always be achieved depending on the number of useful infeasible solutions. To overcome these problems and further enhance the effect of the directed mating in TNSDM, in this work we propose a method to control the selection area of useful infeasible solutions by controlling dominance area of solutions (CDAS). We verify the effectiveness of the proposed method in TNSDM, and compare its search performance with the conventional CNSGA-II on discrete m-objective k-knapsack problems and continuous mCDTLZ problems. The experimental results show that the search performance of TNSDM is further improved by controlling the selection area of useful infeasible solutions in the directed mating.  相似文献   

17.
Transportation and logistics organizations often face large-scale combinatorial problems on both operational and strategic levels. By exploiting problem-specific characteristics, classical heuristic methods--such as constructive and iterative local search methods--aim at a relatively limited exploration of the search space, thereby producing acceptable-quality solutions in modest computing times. In a major departure from a classical heuristic, a metaheuristic method exploits not only the problem characteristics but also ideas based on artificial intelligence methodologies, such as different types of memory structures and learning mechanisms, as well as analogies with optimization methods found in nature. Solutions produced by metaheuristics typically are of a much higher quality than those obtained with classical heuristic approaches.This article is part of a special issue on advanced heuristics in transportation and logistics.  相似文献   

18.
In recent years, evolutionary algorithms (EAs) have been extensively developed and utilized to solve multi-objective optimization problems. However, some previous studies have shown that for certain problems, an approach which allows for non-greedy or uphill moves (unlike EAs), can be more beneficial. One such approach is simulated annealing (SA). SA is a proven heuristic for solving numerical optimization problems. But owing to its point-to-point nature of search, limited efforts has been made to explore its potential for solving multi-objective problems. The focus of the presented work is to develop a simulated annealing algorithm for constrained multi-objective problems. The performance of the proposed algorithm is reported on a number of difficult constrained benchmark problems. A comparison with other established multi-objective optimization algorithms, such as infeasibility driven evolutionary algorithm (IDEA), Non-dominated sorting genetic algorithm II (NSGA-II) and multi-objective Scatter search II (MOSS-II) has been included to highlight the benefits of the proposed approach.  相似文献   

19.
The problem of sequencing n-jobs on one machine (n/1) to minimize maximum job lateness has been the subject of much prior research. Most of this research has been directed at identifying optimal solutions to the problem via algorithmic search techniques. A weakness in employing an algorithm for solving the problem, however, is that lengthy computational times may result because of the necessity of searching n! sequences. By employing a multiple heuristic approach this limitation can be avoided. An optimal or near optimal schedule can be identified in a finite number of steps.This paper describes a multiple heuristic model that is effective more than eighty-ninety percent of the time in providing an optimal schedule for the N/l/L max scheduling program. Ten separate heuristics are described, and the results of testing the heuristics over fifteen hundred and sixty randomly generated problems is presented. Three of the heuristics are combined to form the heuristic-scheduling model.  相似文献   

20.
电力系统动态环境经济调度优化隶属于非线性优化问题范畴,并具有多目标、高维、多约束条件等特点。经 典的数学规划方法无法处理此类复杂问题。为此,提出了新的方法来解决这个问题。首先,通过代价惩罚因子将双目 标优化问题转化为单目标优化问题。然后,设计启发式搜索策略来解决调度问题中的爬坡约束、动态电力平衡约束。 采用启发式策略修正解决方案,能够提高群体的多样性,拓展搜索空间。基于优先列表的启发式策略能够使能耗低的 火力发电机拥有更高的优先级进行更多的电力输出,以得到更优的调度解决方案。最后,改进差分进化算法,以加快 搜索的速度并提高解决方案的质量。  相似文献   

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

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