ABSTRACT
The control of virus spreading over complex networks with a limited budget has attracted much attention but remains challenging. This article aims at addressing the combinatorial, discrete resource allocation problems (RAPs) in virus spreading control. To meet the challenges of increasing network scales and improve the solving efficiency, an evolutionary divide-and-conquer algorithm is proposed, namely, a coevolutionary algorithm with network-community-based decomposition (NCD-CEA). It is characterized by the community-based dividing technique and cooperative coevolution conquering thought. First, to reduce the time complexity, NCD-CEA divides a network into multiple communities by a modified community detection method such that the most relevant variables in the solution space are clustered together. The problem and the global swarm are subsequently decomposed into subproblems and subswarms with low-dimensional embeddings. Second, to obtain high-quality solutions, an alternative evolutionary approach is designed by promoting the evolution of subswarms and the global swarm, in turn, with subsolutions evaluated by local fitness functions and global solutions evaluated by a global fitness function. Extensive experiments on different networks show that NCD-CEA has a competitive performance in solving RAPs. This article advances toward controlling virus spreading over large-scale networks.
ABSTRACT
Evacuation path optimization (EPO) is a crucial problem in crowd and disaster management. With the consideration of dynamic evacuee velocity, the EPO problem becomes nondeterministic polynomial-time hard (NP-Hard). Furthermore, since not only one single evacuation path but multiple mutually restricted paths should be found, the crowd evacuation problem becomes even challenging in both solution spatial encoding and optimal solution searching. To address the above challenges, this article puts forward an ant colony evacuation planner (ACEP) with a novel solution construction strategy and an incremental flow assignment (IFA) method. First, different from the traditional ant algorithms, where each ant builds a complete solution independently, ACEP uses the entire colony of ants to simulate the behavior of the crowd during evacuation. In this way, the colony of ants works cooperatively to find a set of evacuation paths simultaneously and thus multiple evacuation paths can be found effectively. Second, in order to reduce the execution time of ACEP, an IFA method is introduced, in which fractions of evacuees are assigned step by step, to imitate the group-based evacuation process in the real world so that the efficiency of ACEP can be further improved. Numerical experiments are conducted on a set of networks with different sizes. The experimental results demonstrate that ACEP is promising.
Subject(s)
Algorithms , CrowdingABSTRACT
This paper develops a decomposition-based coevolutionary algorithm for many-objective optimization, which evolves a number of subpopulations in parallel for approaching the set of Pareto optimal solutions. The many-objective problem is decomposed into a number of subproblems using a set of well-distributed weight vectors. Accordingly, each subpopulation of the algorithm is associated with a weight vector and is responsible for solving the corresponding subproblem. The exploration ability of the algorithm is improved by using a mating pool that collects elite individuals from the cooperative subpopulations for breeding the offspring. In the subsequent environmental selection, the top-ranked individuals in each subpopulation, which are appraised by aggregation functions, survive for the next iteration. Two new aggregation functions with distinct characteristics are designed in this paper to enhance the population diversity and accelerate the convergence speed. The proposed algorithm is compared with several state-of-the-art many-objective evolutionary algorithms on a large number of benchmark instances, as well as on a real-world design problem. Experimental results show that the proposed algorithm is very competitive.
ABSTRACT
Cloud workflow scheduling is significantly challenging due to not only the large scale of workflow but also the elasticity and heterogeneity of cloud resources. Moreover, the pricing model of clouds makes the execution time and execution cost two critical issues in the scheduling. This paper models the cloud workflow scheduling as a multiobjective optimization problem that optimizes both execution time and execution cost. A novel multiobjective ant colony system based on a co-evolutionary multiple populations for multiple objectives framework is proposed, which adopts two colonies to deal with these two objectives, respectively. Moreover, the proposed approach incorporates with the following three novel designs to efficiently deal with the multiobjective challenges: 1) a new pheromone update rule based on a set of nondominated solutions from a global archive to guide each colony to search its optimization objective sufficiently; 2) a complementary heuristic strategy to avoid a colony only focusing on its corresponding single optimization objective, cooperating with the pheromone update rule to balance the search of both objectives; and 3) an elite study strategy to improve the solution quality of the global archive to help further approach the global Pareto front. Experimental simulations are conducted on five types of real-world scientific workflows and consider the properties of Amazon EC2 cloud platform. The experimental results show that the proposed algorithm performs better than both some state-of-the-art multiobjective optimization approaches and the constrained optimization approaches.