Dual-Tree Genetic Programming with Adaptive Mutation for Dynamic Workflow Scheduling in Cloud Computing
针对云计算中截止时间约束的动态工作流调度问题，提出一种带两级自适应变异机制的双树遗传规划算法，自动演化虚拟机选择规则和任务选择规则，以最小化租赁费用和违反截止时间的惩罚。
Dynamic workflow scheduling (DWS) is a challenging and important optimization problem in cloud computing, aiming to execute multiple heterogeneous workflows on dynamically leased virtual machine resources to satisfy user-defined Quality of Service requirements. For the popular deadline-constrained DWS in cloud problem, a virtual machine selection rule (VMSR) and a task selection rule (TSR) need to be designed simultaneously to minimize the rental fee and deadline violation penalty. For this purpose, Dual-Tree Genetic Programming (DTGP) has been previously developed to automatically evolve effective VMSRs and TSRs. However, existing DTGP approaches assume that VMSR and TSR, as well as terminals used by VMSRs and TSRs are equally important and evolve both VMSRs and TSRs in a black box manner, i.e., without using any knowledge about different impacts of trees and terminals. Several recent studies clearly indicate that different trees or terminals have varied performance impacts, making it critical to develop adaptive mutation mechanisms for effective DTGP. Driven by this motivation, this paper proposes two new levels of adaptive mutation mechanisms, contributing to the development of a new DTGP algorithm, which features the use of three new probability vectors for adaptive tree selection of VMSR and TSR at the first level and adaptive terminal selection at the second level while mutating any existing dual-tree individuals. Extensive experimental results demonstrate that the proposed two adaptive mechanisms can improve the effectiveness of DTGP compared to four baseline algorithms.