车辆路径问题的轻鲁棒优化模型与算法

针对不确定旅行时间下的车辆路径问题,以总变动成本最小为优化目标,建立了一种轻鲁棒优化模型,提出了一种针对问题特征的超启发式粒子群算法.在算法中,利用基于图论中深度优先搜索的初始化策略加快算法的早期收敛速度,引入基于均衡策略的启发式规则变换方式来提高算法的寻优能力,重新设计的粒子更新公式确保生成低层构造算法的有效性.实验结果表明:所提算法能有效地求解不确定旅行时间下的车辆路径问题.     

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

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

A Hyper-Heuristic Framework for Lifetime Maximization in Wireless Sensor Networks With A Mobile Sink

Maximizing the lifetime of wireless sensor networks(WSNs) is an important and challenging research problem. Properly scheduling the movements of mobile sinks to balance the energy consumption of wireless sensor network is one of the most effective approaches to prolong the lifetime of wireless sensor networks. However, the existing mobile sink scheduling methods either require a great amount of computational time or lack effectiveness in finding high-quality scheduling solutions. To address the above issues, this paper proposes a novel hyperheuristic framework, which can automatically construct high-level heuristics to schedule the sink movements and prolong the network lifetime. In the proposed framework, a set of low-level heuristics are defined as building blocks to construct high-level heuristics and a set of random networks with different features are designed for training. Further, a genetic programming algorithm is adopted to automatically evolve promising high-level heuristics based on the building blocks and the training networks. By using the genetic programming to evolve more effective heuristics and applying these heuristics in a greedy scheme, our proposed hyper-heuristic framework can prolong the network lifetime competitively with other methods, with small time consumption. A series of comprehensive experiments, including both static and dynamic networks,are designed. The simulation results have demonstrated that the proposed method can offer a very promising performance in terms of network lifetime and response time.     

An urban transportation problem solved by parallel programming with hyper-heuristics

An innovative optimization strategy by means of hyper-heuristics is proposed. It consists of a parallel combination of three metaheuristics. In view of the need both to escape from local optima and to achieve high diversity, the algorithm cooperatively combines simulated annealing with genetic algorithms and ant colony optimization. A location routing problem (LRP), which aims at the design of transport networks, was adopted for the performance evaluation of the proposed algorithm. Information exchanges took place effectively between the metaheuristics and speeded up the search process. Moreover, the parallel implementation was useful since it allowed several metaheuristics to run simultaneously, thus achieving a significant reduction in the computational time. The algorithmic efficiency and effectiveness were ratified for a medium-sized city. The proposed optimization algorithm not only accelerated computations, but also helped to improve solution quality.     

基于自组织映射的遗传聚类算法

遗传聚类算法往往需要较大的种群规模才能得到最优解,导致收敛速度慢,针对这一问题,本文提出一种基于自组织映射的超启发遗传聚类算法。首先利用自组织映射把数据空间转换到特征空间,再在特征空间里利用遗传算法进行搜索,然后进行反映射,即把聚类结果在数据空间里表现,从而得到一组解,同时利用K-means算法在数据空间里进行粗聚类,获得另一组解,最后比较2组解的聚类结果,相同的样本保留,不同的再次聚类,进而有效地保证了最优解的获得。计算机仿真实验验证了所提算法在种群规模较小的情况下,可以获得较高的准确率。      

Generation of Particle Swarm Optimization algorithms: An experimental study using Grammar-Guided Genetic Programming

Particle Swarm Optimization (PSO) is largely used to solve optimization problems effectively. Nonetheless, the PSO performance depends on the fine tuning of different parameters. To make the algorithm design process more independent from human intervention, some researchers have treated this task as an optimization problem. Grammar-Guided Genetic Programming (GGGP) algorithms, in particular, have been widely studied and applied in the context of algorithm optimization. GGGP algorithms produce customized designs based on a set of production rules defined in the grammar, differently from methods that simply select designs in a pre-defined limited search space. Although GGGP algorithms have been largely used in other contexts, they have not been deeply investigated in the generation of PSO algorithms. Thus, this work applies GGGP algorithms in the context of PSO algorithm design problem. Herein, we performed an experimental study comparing different GGGP approaches for the generation of PSO algorithms. The main goal is to perform a deep investigation aiming to identify pros and cons of each approach in the current task. In the experiments, a comparison between a tree-based GGGP approach and commonly used linear GGGP approaches for the generation of PSO algorithms was performed. The results showed that the tree-based GGGP produced better algorithms than the counterparts. We also compared the algorithms generated by the tree-based technique to state-of-the-art optimization algorithms, and it achieved competitive results.     

云环境下超启发式能耗感知调度算法

能耗感知调度的研究对云计算数据中心的可持续发展有着重要意义。能耗感知调度是一个NP难的多目标优化问题,目前云环境下的任务调度算法较少考虑能耗问题,且不能实现对能耗的灵活管理,随机搜索算法是一种解决该问题的有效途径,但其计算开销大,收敛速度慢。将异构云环境下的能耗感知调度问题定义为一个带约束的问题,即在一定的完成时间下优化系统能耗,以实现对能耗的灵活管理。此外,提出了基于在线学习的超启发式算法（OLHH）,该算法结合电压调节技术,在设计了简单高效的启发式策略集的基础上,引进超启发式算法,并采用在线学习的方式跟踪启发式策略的表现,实现对启发式策略的合理管理,从而达到提高算法的收敛性能的目的。模拟实验表明,该算法能够实现系统能耗的灵活管理,且比传统的随机搜索算法有着更好的收敛性能。     

超启发算法研究进展综述

超启发算法是一类新兴的优化方法,通过机器学习、算法选择、算法生成等技术求解组合优化等问题,具备跨问题领域求解的能力。针对超启发算法研究进展进行综述和讨论。首先,梳理超启发算法的定义、结构、特点和分类;其次,归纳选择式超启发算法和生成式超启发算法的研究进展及相关技术,包括选择低层启发式算法采用的学习方法,迭代计算中的移动接受策略,低层启发式算法的生成方法;最后,讨论现有超启发算法研究中存在的不足及未来的研究方向。