The development of electric vehicle (EV) techniques has led to a new vehicle routing problem (VRP) called the capacitated EV routing problem (CEVRP). Because of the limited number of charging stations and the limited cruising range of EVs, not only the service order of customers but also the recharging schedules of EVs should be considered. However, solving these two aspects of the problem together is very difficult. To address the above issue, we treat CEVRP as a bilevel optimization problem and propose a novel bilevel ant colony optimization algorithm in this article, which divides CEVRP into two levels of subproblem: 1) capacitated VRP and 2) fixed route vehicle charging problem. For the upper level subproblem, the electricity constraint is ignored and an order-first split-second max–min ant system algorithm is designed to generate routes that fulfill the demands of customers. For the lower level subproblem, a new effective heuristic is designed to decide the charging schedule in the generated routes to satisfy the electricity constraint. The objective values of the resultant solutions are used to update the pheromone information for the ant system algorithm in the upper level. Through good orchestration of the two components, the proposed algorithm can significantly outperform state-of-the-art algorithms on a wide range of benchmark instances.

Through introducing the divide-and-conquer strategy, cooperative co-evolution has been successfully employed by many evolutionary algorithms to solve large-scale optimization problems. In practice, it is common that different subcomponents of a large-scale problem have imbalanced contributions to the global fitness. Thus how to utilize such imbalance and concentrate efforts on optimizing important subcomponents becomes an important issue for improving performance of cooperative co-evolutionary algorithm, especially in distributed computing environment. In this paper, we propose a two-layer distributed cooperative co-evolution architecture with adaptive computing resource allocation for large-scale optimization. The first layer is the distributed cooperative co-evolution model which takes charge of calculating the importance of subcomponents and accordingly allocating resources. An effective allocating algorithm is designed which can adaptively allocate computing resources based on a periodic contribution calculating method. The second layer is the pool model which takes charge of making fully utilization of imbalanced resource allocation. Within this layer, two different conformance policies are designed to help optimizers use the assigned computing resources efficiently. Empirical studies show that the two conformance policies and the computing resource allocation algorithm are effective, and the proposed distributed architecture possesses high scalability and efficiency.

The blossoming of electric vehicles gives rise to a new vehicle routing problem called capacitated electric vehicle routing problem. Since charging is not as convenient as refueling, both the service of customers and the recharging of vehicles should be considered. In this paper, we propose a confidence-based bi-level ant colony optimization algorithm to solve the problem. It divides the whole problem into the upper-level sub-problem capacitated vehicle routing problem and the lower-level sub-problem fixed routing vehicle charging problem. For the upper-level sub-problem, an ant colony optimization algorithm is used to generate customer service sequence. Both the direct encoding scheme and the order-first split-second encoding scheme are implemented to make a guideline of their applicable scenes. For the lower-level sub-problem, a new heuristic called simple enumeration is proposed to generate recharging schedules for vehicles. Between the two sub-problems, a confidence-based selection method is proposed to select promising customer service sequence to conduct local search and lower-level optimization. By setting adaptive confidence thresholds, the inferior service sequences that have little chance to become the iteration best are eliminated during the execution. Experiments show that the proposed algorithm has reached the state-of-the-art level and updated eight best known solutions of the benchmark.

Potable water distribution networks are important infrastructures of modern cities. A good design of the network can not only reduce the construction expenditure but also provide reliable service. Nowadays, the scale of the water distribution network of a city grows dramatically along with the city expansion, which brings heavy pressure to its optimal design. In order to solve the large-scale water distribution network optimization problem, a cooperative co-evolutionary algorithm is proposed in this paper. First, an iterative trace-based decomposition method is specially designed by utilizing the information of water tracing to divide a large-scale network into small sub-networks. Since little domain knowledge is required, the decomposition method has great adaptability to multiform networks. Meanwhile, during optimization, the proposed algorithm can gradually refine the decomposition to make it more accurate. Second, a new fitness function is devised to handle the pressure constraint of the problem. The function transforms the constraint into a part of the objective to punish the infeasible solutions. Finally, a new suite of benchmark networks are created with both balanced and imbalanced cases. Experimental results on a widely-used real network and the benchmark networks show that the proposed algorithm is promising.

The introduction of workflow in cloud computing has afforded a new and efficient way to tackle large-scale applications. As an NP-hard problem, how to schedule cloud workflows effectively and economically with deadline constraints and different kinds of tasks and resources is extraordinarily challenging. To solve this constrained problem, this paper intends to develop an intelligent scheduling system from the perspective of users to reduce expenditure of workflow, subject to the deadline and other execution constraints. A new estimation model of the task execution time is designed according to virtual machine settings in real public clouds and execution data from practical workflows. Based on the new model, an adaptive ant colony optimization algorithm is proposed to meet the quality of service and orchestrate tasks. The adaptiveness of the algorithm is embodied in two aspects. First, an adaptive solution construction method is designed that each solution is built with a dynamically changing resource pool, thus the search space of the algorithm is narrowed down and the execution time is decreased. Second, two heuristics with self-adaptive weight are introduced to adaptively meet different deadline settings. Simulating results on four types of workflows show that the proposed approach is effective and competitive.

In high dimensional environment, the interaction among particles significantly affects their movements in searching the vast solution space and thus plays a vital role in assisting particle swarm optimization (PSO) to attain good performance. To this end, this paper designs a random contrastive interaction (RCI) strategy for PSO, resulting in RCI-PSO, to tackle large-scale optimization problems (LSOPs) effectively and efficiently. Unlike existing interaction mechanisms for low-dimensional problems, RCI randomly chooses several different peers from the current swarm to construct a random interaction topology for each particle. Then, it lets the particle interact with the selected peers based on their current evolutionary information instead of their historical evolutionary information. Within the topology, RCI only propagates the evolutionary information of two contrastive dominators with the largest difference in fitness to direct the evolution of the particle. Therefore, particles with no more than two dominators in their topologies are not updated. Furthermore, a dynamic topology size adjustment scheme is devised to gradually enlarge the interaction topology. In this way, the swarm gradually switches from exploring the immense search space dispersedly to exploiting the found optimal regions intensively as the evolution continues. With these two strategies, RCI-PSO expectedly compromises search diversity and search convergence well at the swarm level and the particle level. At last, extensive experiments executed on two public LSOP suites verify that RCI-PSO performs competitively with or even much better than totally 40 state-of-theart large-scale approaches and preserves a good capability and scalability in tackling complex LSOPs.