课程表问题的一种模拟退火超启发式算法

课程表问题是经典的组合优化问题,属于NP-hard问题.长期以来人们一直都在寻求快速高效的近似算法,以便在合理的计算时间内准确解决大规模课程安排问题,并提出许多有效且实用的启发式和元启发式算法.在此基础上提出了一种基于多个图染色启发式规则的模拟退火超启发式算法.在超启发式算法的框架中,用模拟退火算法作为高层搜索算法,多个图染色启发式规则为底层的构造算法.与现有的方法相比,该算法具有很好的通用性,可以很容易推广到考试时间表、会议安排.旅行商问题、背包问题等应用领域.实验表明,该算法是可行有效的,且无一例时间、空间冲突.     

基于模拟退火与贪心策略的平衡聚类算法

针对现实应用通常要求聚类的结果相对平衡的问题,提出了一种基于模拟退火与贪心策略的平衡聚类算法（BCSG）,该算法包括基于模拟退火的初始点选择算法（SACI）与基于贪心策略的平衡聚类算法（BCGS）2个步骤,以提高平衡聚类算法的聚类效果与时间性能。首先基于模拟退火在数据集中快速定位出K个合适的数据点作为平衡聚类初始点,然后每个中心点分阶段贪婪地将距离其最近的数据点加入簇中直至达到簇规模上限。在6个UCI真实数据集与2个公开图像数据集上进行的聚类对比实验结果表明：在簇数目较大时相比Fuzzy C-Means聚类结果平衡度最高提升了50%以上;聚类结果的准确率相比Balanced K-Means、BCLS两个表现较好的算法平均提高了8个百分点;算法时间复杂度也更低,在较大规模的数据集上运行时间比Balanced K-Means最高减少了近40%。实验结果表明BCSG具有更佳的聚类效果和时间性能。     

Efficient greedy feature selection for unsupervised learning

Reducing the dimensionality of the data has been a challenging task in data mining and machine learning applications. In these applications, the existence of irrelevant and redundant features negatively affects the efficiency and effectiveness of different learning algorithms. Feature selection is one of the dimension reduction techniques, which has been used to allow a better understanding of data and improve the performance of other learning tasks. Although the selection of relevant features has been extensively studied in supervised learning, feature selection in the absence of class labels is still a challenging task. This paper proposes a novel method for unsupervised feature selection, which efficiently selects features in a greedy manner. The paper first defines an effective criterion for unsupervised feature selection that measures the reconstruction error of the data matrix based on the selected subset of features. The paper then presents a novel algorithm for greedily minimizing the reconstruction error based on the features selected so far. The greedy algorithm is based on an efficient recursive formula for calculating the reconstruction error. Experiments on real data sets demonstrate the effectiveness of the proposed algorithm in comparison with the state-of-the-art methods for unsupervised feature selection.     

一种分片混沌贪婪振荡退火TSP优化算法

引入自适应升温策略或使用蒙特卡罗策略的模拟退火算法在复杂TSP求解时分别表现出收敛缓慢和全局最优逼近能力有限的问题;而现有的混沌优化算法由于logistic映射的缺陷,削弱了其跳出局部最优的能力.故设计一种融合型算法框架,在框架中嵌入分片Lorenz混沌映射系统,加强混沌算法对邻域解的搜索均匀度;引入了贪婪策略构造逼近全局最优解的初始解,使算法具有跃迁到全局最优解邻域的能力;此外设计了振荡退火互补机制,改善了子迭代解筛选过程,增强算法全局搜索性能.实现算法后,使用国际公开TSPLIB算例,经过多轮对比测试,验证了新算法对TSP的求解性能指标优于对比组模拟退火算法和logistic混沌优化算法,具有更短的收敛时间和更强的全局最优逼近能力.     

A multi-objective hyper-heuristic based on choice function

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.     

基于贪心算法和模拟退火算法的软硬件划分

软硬件划分是嵌入式系统设计过程中一个关键环节,已经被证明是一个NP问题。针对目前算法在进行大任务集下的软硬件划分时计算复杂度高、不能快速收敛,且找到的全局最优解的质量不佳等问题,提出一种基于贪心算法和模拟退火算法相融合的软硬件划分方法。首先将软硬件划分问题规约为变异的0-1背包问题,在求解背包问题的算法基础上用贪心算法构造出初始划分解;然后,对代价函数的解空间进行合理的区域划分,并基于划分的区间设计新的代价函数,采用改进的模拟退火算法对初始划分进行全局寻优。实验结果表明,与目前已有的类似改进算法相比,新算法在任务划分质量和算法运行时间两个方面的提升率最大可达到8%和17%左右,具有高效性和实用性。     

A hyper-heuristic approach to aircraft structural design optimization

The conceptual design of an aircraft is a challenging problem in which optimization can be of great importance to the quality of design generated. Mass optimization of the structural design of an aircraft aims to produce an airframe of minimal mass whilst maintaining satisfactory strength under various loading conditions due to flight and ground manoeuvres. Hyper-heuristic optimization is an evolving field of research wherein the optimization process is continuously adapted in order to provide greater improvements in the quality of the solution generated. The relative infancy of hyper-heuristic optimization has resulted in limited application within the field of aerospace design. This paper describes a framework for the mass optimization of the structural layout of an aircraft at the conceptual level of design employing a novel hyper-heuristic approach. This hyper-heuristic approach encourages solution space exploration, thus reducing the likelihood of premature convergence, and improves the feasibility of and convergence upon the best solution found. A case study is presented to illustrate the effects of hyper-heuristics on the problem for a large commercial aircraft. Resulting solutions were generated of considerably lighter mass than the baseline aircraft. A further improvement in solution quality was found with the use of the hyper-heuristics compared to that obtained without, albeit with a penalty on computation time.     

A unified hyper-heuristic framework for solving bin packing problems

One- and two-dimensional packing and cutting problems occur in many commercial contexts, and it is often important to be able to get good-quality solutions quickly. Fairly simple deterministic heuristics are often used for this purpose, but such heuristics typically find excellent solutions for some problems and only mediocre ones for others. Trying several different heuristics on a problem adds to the cost. This paper describes a hyper-heuristic methodology that can generate a fast, deterministic algorithm capable of producing results comparable to that of using the best problem-specific heuristic, and sometimes even better, but without the cost of trying all the heuristics. The generated algorithm handles both one- and two-dimensional problems, including two-dimensional problems that involve irregular concave polygons. The approach is validated using a large set of 1417 such problems, including a new benchmark set of 480 problems that include concave polygons.     

A hyper-heuristic based framework for dynamic optimization problems

Most of the real world problems have dynamic characteristics, where one or more elements of the underlying model for a given problem including the objective, constraints or even environmental parameters may change over time. Hyper-heuristics are problem-independent meta-heuristic techniques that are automating the process of selecting and generating multiple low-level heuristics to solve static combinatorial optimization problems. In this paper, we present a novel hybrid strategy for applicability of hyper-heuristic techniques on dynamic environments by integrating them with the memory/search algorithm. The memory/search algorithm is an important evolutionary technique that have applied on various dynamic optimization problems. We validate performance of our method by considering both the dynamic generalized assignment problem and the moving peaks benchmark. The former problem is extended from the generalized assignment problem by changing resource consumptions, capacity constraints and costs of jobs over time; and the latter one is a well-known synthetic problem that generates and updates a multidimensional landscape consisting of several peaks. Experimental evaluation performed on various instances of the given two problems validates that our hyper-heuristic integrated framework significantly outperforms the memory/search algorithm.     

Simulated annealing for supervised gene selection

Genomic data, and more generally biomedical data, are often characterized by high dimensionality. An input selection procedure can attain the two objectives of highlighting the relevant variables (genes) and possibly improving classification results. In this paper, we propose a wrapper approach to gene selection in classification of gene expression data using simulated annealing along with supervised classification. The proposed approach can perform global combinatorial searches through the space of all possible input subsets, can handle cases with numerical, categorical or mixed inputs, and is able to find (sub-)optimal subsets of inputs giving low classification errors. The method has been tested on publicly available bioinformatics data sets using support vector machines and on a mixed type data set using classification trees. We also propose some heuristics able to speed up the convergence. The experimental results highlight the ability of the method to select minimal sets of relevant features.     

Carousel greedy: A generalized greedy algorithm with applications in optimization

In this paper, we introduce carousel greedy, an enhanced greedy algorithm which seeks to overcome the traditional weaknesses of greedy approaches. We have applied carousel greedy to a variety of well-known problems in combinatorial optimization such as the minimum label spanning tree problem, the minimum vertex cover problem, the maximum independent set problem, and the minimum weight vertex cover problem. In all cases, the results are very promising. Since carousel greedy is very fast, it can be used to solve very large problems. In addition, it can be combined with other approaches to create a powerful, new metaheuristic. Our goal in this paper is to motivate and explain the new approach and present extensive computational results.     

A graph coloring constructive hyper-heuristic for examination timetabling problems

In this work we investigate a new graph coloring constructive hyper-heuristic for solving examination timetabling problems. We utilize the hierarchical hybridizations of four low level graph coloring heuristics, these being largest degree, saturation degree, largest colored degree and largest enrollment. These are hybridized to produce four ordered lists. For each list, the difficulty index of scheduling the first exam is calculated by considering its order in all lists to obtain a combined evaluation of its difficulty. The most difficult exam to be scheduled is scheduled first (i.e. the one with the minimum difficulty index). To improve the effectiveness of timeslot selection, a?roulette wheel selection mechanism is included in the algorithm to probabilistically select an appropriate timeslot for the chosen exam. We test our proposed approach on the most widely used un-capacitated Carter benchmarks and also on the recently introduced examination timetable dataset from the 2007 International Timetabling Competition. Compared against other methodologies, our results demonstrate that the graph coloring constructive hyper-heuristic produces good results and outperforms other approaches on some of the benchmark instances.     

A Tabu Search hyper-heuristic strategy for t-way test suite generation

This paper proposes a novel hybrid t-way test generation strategy (where t indicates interaction strength), called High Level Hyper-Heuristic (HHH). HHH adopts Tabu Search as its high level meta-heuristic and leverages on the strength of four low level meta-heuristics, comprising of Teaching Learning based Optimization, Global Neighborhood Algorithm, Particle Swarm Optimization, and Cuckoo Search Algorithm. HHH is able to capitalize on the strengths and limit the deficiencies of each individual algorithm in a collective and synergistic manner. Unlike existing hyper-heuristics, HHH relies on three defined operators, based on improvement, intensification and diversification, to adaptively select the most suitable meta-heuristic at any particular time. Our results are promising as HHH manages to outperform existing t-way strategies on many of the benchmarks.     

A ‘greedy’ channel router

A ‘greedy’ channel-router is presented. It is quick, simple and effective. It always suceeds, usually using no more than one track more than required by channel density. It may be forced in rare cases to make a few connections ‘off the end’ of the channel, in order to succeed. It assumes that all pins and wirling lie on a common grid, and that vertical wires are on one layer, horizontal on another. The greedy router wires the channel left-to-right, column-by-column, wiring each column completely before starting the next. Within each column the router tries to maximize the utility of the wiring produced, using simple, ‘greedy’ heuristics. It may place a net on more than one track for a few columns, and collapse the net to a single track later on, using a vertical jog. It may also use a jog to move a net to a track closer to its pin in some future column. The router may occasionally add a new track to the channel, to avoid getting stuck.     

A greedy Delaunay-based surface reconstruction algorithm

In this paper, we present a new greedy algorithm for surface reconstruction from unorganized point sets. Starting from a seed facet, a piecewise linear surface is grown by adding Delaunay triangles one by one. The most plausible triangles are added first and in such a way as to prevent the appearance of topological singularities. The output is thus guaranteed to be a piecewise linear orientable manifold, possibly with boundary. Experiments show that this method is very fast and achieves topologically correct reconstruction in most cases. Moreover, it can handle surfaces with complex topology, boundaries, and nonuniform sampling.     

基于模拟退火遗传算法的服务选择

为了解决面向服务体系结构服务组合中服务选择问题,提出了一种将模拟退火算法与遗传算法相结合的融合算法。将服务流程等效成AOV图,对AOV图进行拓扑排序,并将生成的拓扑序列作为遗传算法的编码,使用QoS参数作为适应度,在遗传算法生成每一代子代后,利用模拟退火算法对其进行局部优化调整。仿真实验结果表明,模拟退火遗传算法在减少服务流程资源消耗上能取得理想的效果。     

A greedy approximation algorithm for minimum-gap scheduling

We consider scheduling of unit-length jobs with release times and deadlines, where the objective is to minimize the number of gaps in the schedule. Polynomial-time algorithms for this problem are known, yet they are rather inefficient, with the best algorithm running in time \(O(n^4)\) and requiring \(O(n^3)\) memory. We present a greedy algorithm that approximates the optimum solution within a factor of 2 and show that our analysis is tight. Our algorithm runs in time \(O(n^2 \log n)\) and needs only O(n) memory. In fact, the running time is \(O(n (g^*+1)\log n)\), where \(g^*\) is the minimum number of gaps.     

A hyper-heuristic approach to automated generation of mutation operators for evolutionary programming

Evolutionary programming can solve black-box function optimisation problems by evolving a population of numerical vectors. The variation component in the evolutionary process is supplied by a mutation operator, which is typically a Gaussian, Cauchy, or Lévy probability distribution. In this paper, we use genetic programming to automatically generate mutation operators for an evolutionary programming system, testing the proposed approach over a set of function classes, which represent a source of functions. The empirical results over a set of benchmark function classes illustrate that genetic programming can evolve mutation operators which generalise well from the training set to the test set on each function class. The proposed method is able to outperform existing human designed mutation operators with statistical significance in most cases, with competitive results observed for the rest.     

一种新的贪婪回溯子空间追踪算法研究

针对目前的贪婪类算法在实际应用中出现的重构遮挡和虚假等问题,本文在分析该问题产生的原因基础上,提出了一种新的贪婪回溯子空间追踪(greedy backtracking subspace pursuit, GBSP)算法。该算法基本思想是在每次的迭代过程中,采用回溯反馈和贪婪精选的思路进行支撑集选择。具体而言,在原子识别阶段,从残差投影中挑选出绝对值最大的 ( 是信号稀疏度)个投影值位置,添加到候选支撑集中,为降低在此步骤中产生的错误概率,每次只将候选支撑集中的前s（ ）个最大值对应的位置添加到真实支撑集中进行更新;此后再进行投影计算和残差更新,直到完成支撑集的选择。由于新算法结合了正交匹配追踪算法和子空间追踪算法二者的优势,因此可较好的解决重构遮挡与虚假问题,使得压缩感知重构算法更具实用性。     

PMC模型下的一个贪婪诊断算法

提出了一种PMC模型下基于矩阵运算的贪婪诊断算法——MGFD算法。算法结合作者曾经提出的"绝对故障基"思想,首先剔除绝对故障基,得到一个维度减小的矩阵,之后根据该矩阵求得集团。在文献[10]提出的四个贪婪诊断算法的基础上,提出集团的内贪婪因子、外贪婪因子、综合贪婪因子等概念,设计了新的贪婪准则。论证了MGFD算法的正确性,并对算法进行了实验仿真。实验结果表明,MGFD算法相比文献[10]提出的贪婪诊断算法,具有较高的诊断正确率。