车辆路径问题的水波算法

水波算法(Water Wave Optimization WWO)是郑宇军于2014年基于浅水波理论提出的一种新颖的元启发式算法,用于全局优化问题.通过水波的传播、折射和碎浪操作,可以用来导出在高维解决方案空间中搜索的有效机制.算法WWO的框架简单,易于实现,并且只需要少量的控制参数.本文应用WWO求解车辆路径问题(the Capacitated Vehicle Routing Problem CVRP),算法采用0-1矩阵编码方式,通过传播操作进行全局搜索,反射操作实现进化,碎浪操作防止陷入局部最优.利用构建的算法求解64个benchmark算例,求解的结果中有65%的算例获得已知最优解,有6个算例更新了已知最好解,验证水波算法求解车辆路径问题的可行性,为水波算法应用于其他优化问题提供参考.     

一种基于混沌和单纯形法的水波优化算法

水波优化(Water Wave Optimization,WWO)算法是一种基于浅水波理论的新兴元启发式优化算法,通过模拟水波的传播、碎浪、折射操作在解空间中进行全局搜索。为提高算法的收敛速度和精度,提出了一种基于混沌(Ch-aotic)优化和单纯形法(Simplex Method,SM)的水波优化算法,简称为CSMWWO。在CSMWWO算法中,引入了混沌优化策略来降低随机初始化的种群对收敛速度和求解精度的影响,在混沌优化策略的基础上又引入了局部搜索能力较强的单纯形法来提高WWO算法的收敛速度。将CSMWWO与包括WWO在内的4个启发式算法在12个基本测试函数上进行了测试,结果表明改进后的算法在计算精度和收敛速度上都有一定程度的提高,所提出的混合水波优化算法能改进水波优化算法的整体性能。     

水波优化算法收敛性分析

水波优化(Water Wave Optimization,WWO)算法是一种受浅水波现象启发的新兴进化算法,它通过模拟水波的传播、折射、碎浪等运动机制来在高维解空间中进行高效搜索。该算法已被证明在大量基准测试问题和工程实际问题上优于其它许多前沿的启发式优化算法。从理论上分析了WWO算法的收敛性条件。通过对目标问题和算法参数设置的简化,证明了WWO中任何个体在两种特殊情况下都是收敛的:(1)只执行传播操作;(2)只执行折射操作。这两种情况分别对应两种特殊的适应度变化状态。进行了数值仿真实验,验证了上述两种收敛性条件。     

基于模拟退火的自适应水波优化算法

水波优化算法(Water Wave Optimization,WWO)是一种基于浅水波理论的新兴智能优化算法。在简化水波优化算法(Simplified Water Wave Optimization,SimWWO)的基础上,提出水波优化算法的一个改进版本。针对WWO算法在寻优过程中未能有效利用水波历史状态和经验的问题,提出一种自适应的参数调整策略:根据水波进化过程中的性能改善指标自适应调整算法的波长系数,提高搜索效率;同时,针对算法后期容易陷入局部最优的情况,加入模拟退火的思想,以一定的概率接受劣质解,避免算法陷入局部最优。通过以上两个操作可以更好地平衡全局搜索和局部搜索。在CEC 2015函数测试集上进行比较,结果证明改进后的算法有效地提高了综合性能。     

基于自适应控制参数的改进水波优化算法

水波优化算法(Water Wave Optimization,WWO)是最近被提出的一种新型的群智能优化算法。它尽管具有控制参数少、操作简单、容易实现等优点,但是也存在收敛较慢、搜索精度低等不足。针对水波优化算法的不足,首先,从理论上分析并揭示算法收敛时控制参数应满足的条件;然后,提出满足上述条件的改进水波优化算法,改进算法采取自适应机制来调节算法参数,进一步增强了全局探索和局部开发的平衡能力;最后,对4种算法(ApWWO,WWO,FA,MVO)在10个标准测试函数上的寻优性能进行仿真实验和统计比较。结果表明,ApWWO在搜索精度、速度和鲁棒性等方面均显著优于WWO和FA,在5个测试函数上优于MVO;与PSO和GA的对比结果表明,ApWWO具有较好的寻优性能。进一步分析了维数和种群规模对ApWWO的影响,并使用ApWWO来求解置换流水线调度问题,结果表明ApWWO能够取得较好的求解效果。     

基于傅里叶变换的粒子群优化算法

针对标准粒子群算法容易陷入局部收敛的问题,提出了新的优化粒子群方法,从两个方面对其进行优化.为了改进学习因子,利用傅里叶级数的特性定义了一个傅里叶级数进行分析判断;加入随机速度,辅助粒子扩大搜索区域并避免早熟.该算法遵循启发式规则,可根据粒子搜索结果动态调整参数,具有较好的全局搜索性能和搜索精度.最后,采用4种经典测试函数进行测试并比较,选取一个单峰函数和多峰函数进行仿真,仿真结果表明了该算法的可行性.     

一种批优化调度策略的实时异构系统的集成动态调度算法

针对实时异构多任务调度的特点,提出了软、硬实时任务形式化描述非精确计算的统一任务模型,在此基础上,提出了一种基于批优化调度策略的实时异构系统的集成动态调度算法.该算法以启发式搜索为基础,引入软实时任务服务质量降级策略,在每次扩充当前局部调度时,按制定的规则选取一批任务,计算其在各处理器上运行的目标函数,采用指派问题解法对任务优化分配.模拟实验表明,该算法与同类算法相比,提高了调度成功率.     

一种面向测试需求部分覆盖的测试用例集约简技术

软件系统开发中频繁面对局部更新和部分缺陷修改,此时需要选择性回归测试;为降低其测试工作量需要解决部分覆盖用例集约简问题.文中基于选择性回归测试形式化定义多目标用例集约简,并设计HATS算法解决该问题.HATS算法遵循启发式贪婪搜索框架,定义权重因子a平衡两方面目标:其一是减少用例集规模;其二是避免对无关需求的覆盖.实验...     

基于多标签k近邻方法实现元启发式算法的排名推荐

设计并研究一种基于多标签k近邻方法(multi-label k-nearest neighbor, ML-k NN)推荐元启发式算法的实现框架.应用多标签k近邻分类学习技术,实现最佳元启发式算法的排名推荐.为了验证效果,以多模式资源约束项目调度问题(MRCPSP)为优化对象,选取不同规模的数百个算例分别提取问题基本特征和地标特征;选用遗传、粒子群、禁忌搜索、蜂群和蚁群5种元启发式算法,使用ML-k NN建立元推荐模型;利用海明损失、单错误率、覆盖率、排位损失和平均准确率5个指标对推荐效果做出分析和评价.实验结果表明,基于ML-k NN方法推荐元启发式算法效果突出,其中基于地标特征的单错误率指标为18.4%,平均准确率达到88.9%.相对于k NN方法, MLk NN取得了更好的推荐结果.此外, ML-k NN方法可以实现对所有备选算法的排名推荐,该研究结论有望推广应用于其他组合优化问题的优化算法推荐.     

一种基于景观特征的浮点数编码遗传算法研究

遗传算法作为一种适应性搜索技术得到了普遍的应用,但其搜索效率不如启发式搜索.已有研究者将启发式知识用于二进制编码遗传算法,但浮点数编码在函数优化和约束优化领域明显有效于其它编码.本文基于算法运行时的景观特征作为启发式知识,用于浮点数编码遗传算法,力求提高其搜索效率、增强其局部搜索能力、拓展其应用领域.本文的理论研究和实验结果表明,将景观特征用于浮点数编码遗传算法,理论是可靠的,方法是可行的.     

Water wave optimization: A new nature-inspired metaheuristic

Nature-inspired computing has been a hot topic in scientific and engineering fields in recent years. Inspired by the shallow water wave theory, the paper presents a novel metaheuristic method, named water wave optimization (WWO), for global optimization problems. We show how the beautiful phenomena of water waves, such as propagation, refraction, and breaking, can be used to derive effective mechanisms for searching in a high-dimensional solution space. In general, the algorithmic framework of WWO is simple, and easy to implement with a small-size population and only a few control parameters. We have tested WWO on a diverse set of benchmark problems, and applied WWO to a real-world high-speed train scheduling problem in China. The computational results demonstrate that WWO is very competitive with state-of-the-art evolutionary algorithms including invasive weed optimization (IWO), biogeography-based optimization (BBO), bat algorithm (BA), etc. The new metaheuristic is expected to have wide applications in real-world engineering optimization problems.     

Band selection for hyperspectral images using probabilistic memetic algorithm

Band selection plays an important role in identifying the most useful and valuable information contained in the hyperspectral images for further data analysis such as classification, clustering, etc. Memetic algorithm (MA), among other metaheuristic search methods, has been shown to achieve competitive performances in solving the NP-hard band selection problem. In this paper, we propose a formal probabilistic memetic algorithm for band selection, which is able to adaptively control the degree of global exploration against local exploitation as the search progresses. To verify the effectiveness of the proposed probabilistic mechanism, empirical studies conducted on five well-known hyperspectral images against two recently proposed state-of-the-art MAs for band selection are presented.     

Exporting water wave optimization concepts to modified simulated annealing algorithm for size optimization of truss structures with natural frequency constraints

This paper proposes an improved version of a recently proposed modified simulated annealing algorithm (MSAA) named as an improved MSAA (I-MSAA) to tackle the size optimization of truss structures with frequency constraint. This kind of problem is problematic because its feasible region is non-convex while the boundaries are highly non-linear. The main motivation is to improve the exploitative behavior of MSAA, taking concept from water wave optimization metaheuristic (WWO). An interesting concept of WWO is its breaking operation. Thirty functions extracted from the CEC2014 test suite and four benchmark truss optimization problems with frequency constraints are explored for the validity of the proposed algorithm. Numerical results indicate that I-MSAA is more reliable, stable and efficient than those found by other existing metaheuristics in the literature.

     

An effective method for service components selection based on micro-canonical annealing considering dependability assurance

Distributed virtualization changes the pattern of building software systems. However, it brings some problems on dependability assurance owing to the complex social relationships and interactions between service components. The best way to solve the problems in a distributed virtualized environment is dependable service components selection. Dependable service components selection can be modeled as finding a dependable service path, which is a multiconstrained optimal path problem. In this paper, a service components selection method that searches for the dependable service path in a distributed virtualized environment is proposed from the perspective of dependability assurance. The concept of Quality of Dependability is introduced to describe and constrain software system dependability during dynamic composition. Then, we model the dependable service components selection as a multiconstrained optimal path problem, and apply the Adaptive Bonus-Penalty Microcanonical Annealing algorithm to find the optimal dependable service path. The experimental results show that the proposed algorithm has high search success rate and quick converges.     

A systematic review of search-based testing for non-functional system properties

Search-based software testing is the application of metaheuristic search techniques to generate software tests. The test adequacy criterion is transformed into a fitness function and a set of solutions in the search space are evaluated with respect to the fitness function using a metaheuristic search technique. The application of metaheuristic search techniques for testing is promising due to the fact that exhaustive testing is infeasible considering the size and complexity of software under test. Search-based software testing has been applied across the spectrum of test case design methods; this includes white-box (structural), black-box (functional) and grey-box (combination of structural and functional) testing. In addition, metaheuristic search techniques have also been applied to test non-functional properties. The overall objective of undertaking this systematic review is to examine existing work into non-functional search-based software testing (NFSBST). We are interested in types of non-functional testing targeted using metaheuristic search techniques, different fitness functions used in different types of search-based non-functional testing and challenges in the application of these techniques. The systematic review is based on a comprehensive set of 35 articles obtained after a multi-stage selection process and have been published in the time span 1996–2007. The results of the review show that metaheuristic search techniques have been applied for non-functional testing of execution time, quality of service, security, usability and safety. A variety of metaheuristic search techniques are found to be applicable for non-functional testing including simulated annealing, tabu search, genetic algorithms, ant colony methods, grammatical evolution, genetic programming (and its variants including linear genetic programming) and swarm intelligence methods. The review reports on different fitness functions used to guide the search for each of the categories of execution time, safety, usability, quality of service and security; along with a discussion of possible challenges in the application of metaheuristic search techniques.     

A hybrid evolutionary algorithm for the resource-constrained project scheduling problem

The resource-constrained project scheduling problem (RCPSP) is an NP-hard optimization problem. RCPSP is one of the most important and challenging problems in the project management field. In the past few years, many researches have been proposed for solving the RCPSP. The objective of this problem is to schedule the activities under limited resources so that the project makespan is minimized. This paper proposes a new algorithm for solving RCPSP that combines the concepts of negative selection mechanism of the biologic immune system, simulated annealing algorithm (SA), tabu search algorithm (TS) and genetic algorithm (GA) together. The performance of the proposed algorithm is evaluated and compared to current state-of-the-art metaheuristic algorithms. In this study, the benchmark data sets used in testing the performance of the proposed algorithm are obtained from the project scheduling problem library. The performance is measured in terms of the average percentage deviation from the critical path lower bound. The experimental results show that the proposed algorithm outperforms the state-of-the-art metaheuristic algorithms on all standard benchmark data sets.     

A memetic algorithm for the travelling salesperson problem with hotel selection

In this paper, a metaheuristic solution procedure for the travelling salesperson problem with hotel selection (TSPHS) is presented. The metaheuristic consists of a memetic algorithm with an embedded tabu search, using a combination of well-known and problem-specific neighbourhoods. This solution procedure clearly outperforms the only other existing metaheuristic in the literature. For smaller instances, whose optimal solution is known, it is able to consistently find the optimal solution. For the other instances, it obtains several new best known solutions.     

通过遗传算法进行系统级软硬件划分

介绍采用遗传算法解决软硬件划分问题，具体讨论在遗传算法实现过程中的编码和解码，适应值函数的选取，选择，交叉，变异算子的实现、收敛准则的决定等问题的处理，与已发表文献的处理方法进行比较，最后通过随机实验取得好的结果。