查看更多>>摘要：Memetic algorithms are known for their enhanced solution refinement capabilities. These capabilities are a result of incorporating local-search methods into population-based metaheuristics such as swarm and evolutionary algorithms. However, designing a memetic algorithm is not a trivial task. The inclusion of local-search procedures must consider the exploitation-exploration balance and its interplay with other algorithm operators. Due to these variables, there is no universal methodology to design a memetic algorithm. Although previous works have investigated the impact of local search procedures on genetic and ant colony algorithms, we have limited knowledge about the impact of these procedures on other types of swarm-based algorithms. For swarm-based algorithms, the interactions within the population are vital to the emergence of collective intelligence and shape the algorithm's behaviour. Here, we model these interactions into a network and analyse the impact of local search in swarm-based algorithms. We selected the Particle Swarm Optimization (PSO), the Artificial Bee Colony (ABC), and one memetic version of each algorithm as a case study. We examined the effects of the modifications proposed in the memetic variants. The results obtained indicate that the networks of interactions capture several characteristics of the algorithms and the impact of the local search strategies. The impact of local search operators can be gauged by the temporal analysis of the changes in the structural properties of the algorithm's network (e.g. study of the weight and distribution of the network's connections). These changes are linked to the algorithms' convergence signature and can be used as a proxy to assess the differences between the algorithms studied and their memetic versions.
查看更多>>摘要：The environments of the dynamic multiobjective optimization problems (DMOPs), such as Pareto optimal front (POF) or Pareto optimal set (POS), usually frequently change with the evolution process. This kind of problem poses a higher challenge for evolutionary algorithms because it requires the population to quickly track (i.e., con -verge) to the position of a new environment and be widely distributed in the search space. The prediction-based response mechanism is a commonly used method to deal with environmental changes, but it's only suitable for predictable changes. Moreover, the imbalance of population diversity and convergence in the process of tracking the dynamically changing POF has aggravated. In this paper, we proposed a new change response mechanism that combines a hybrid prediction strategy and a precision controllable mutation strategy (HPPCM) to solve the DMOPs. Specifically, the hybrid prediction strategy coordinates the center point-based prediction and the guiding individual-based prediction to make accurate predictions. Thus, the population can quickly adapt to the predictable environmental changes. Additionally, the precision controllable mutation strategy handles un-predictable environmental changes. It improves the diversity exploration of the population by controlling the variation degree of solutions. In this way, our change response mechanism can adapt to various environmental changes of DMOPs, such as predictable and unpredictable changes. This paper integrates the HPPCM mecha-nism into a prevalent regularity model-based multiobjective estimation of distribution algorithm (RM-MEDA) to optimize DMOPs. The results of comparative experiments with some state-of-the-art algorithms on various test instances have demonstrated the effectiveness and competitiveness of the change response mechanism proposed in this paper.
查看更多>>摘要：A B S T R A C T Internet of Things (IoT) assisted robotic applications are becoming prominent in smart cities for granting autonomous services for end-users. The IoT-enabled edge-computing paradigm provides ubiquitous computing and resource access for the robots for robust services. The interactive sessions and partial computations of the robots result in unnecessary exploitation of real-time resources. This paper introduces a swarm intelligence-based modular interactive computation scheme (MICS) for IoT-assisted robots to address the incompleteness in resource utilization and reduce computational complexity. In this scheme, particle swarm optimization (PSO) is incorporated with intelligent decision-making. The role of swarm intelligence is to improve interactive computations using different agents that provide offloading support. The flexible sharing of swarm agents provides shared resource utilization and comprehensive calculations for robot-based assistance. The proposed scheme performs computing and interaction decisions based on the robot inputs and its parallel processing feature. The proposed scheme's performance is verified using the metrics interaction span, decision complexity, offloading ratio, computing time, and outages. The proposed scheme achieves a 12.74% high interaction span, 6.68% less decision complexity, 11.69% less offloading ratio, and 19.41% less computing time under different intervals. Based on the resource availability analysis, MICS achieves 62.1% compared to IoT-IF 25.6%, SF-EM 32.9, and 25.61%. Further MICS offloading ratio achieves up to 8.5% following IoT-IF 11.9%, SF-EM 10.1%, and SDF 9.1%.
Guijt, ArthurNgoc Hoang LuongBosman, Peter A. N.de Weerdt, Mathijs...
13页
查看更多>>摘要：Gene-pool Optimal Mixing Evolutionary Algorithms (GOMEAs) have been shown to achieve state-of-the-art results on various types of optimization problems with various types of problem variables. Recently, a GOMEA for permutation spaces was introduced by leveraging the random keys encoding, obtaining promising first results on permutation flow shop instances. A key cited strength of GOMEAs is linkage learning, i.e., the ability to determine and leverage, during optimization, key dependencies between problem variables. However, the added value of linkage learning was not tested in depth for permutation GOMEA. Here, we introduce a new version of permutation GOMEA, called qGOMEA, that works directly in permutation space, removing the redundancy of using random keys. We additionally consider various linkage information sources, including random noise, in both GOMEA variants, and compare performance with various classic genetic algorithms on a wider range of problems than considered before. We find that, although the benefits of linkage learning are clearly visible for various artificial benchmark problems, this is far less the case for various real-world inspired problems. Finally, we find that qGOMEA performs best, and is more applicable to a wider range of permutation problems.
查看更多>>摘要：A method based on decision variable partition is often utilized for large-scale optimization problems, but it only considers the convergence and diversity of decision variables. However, decision variables in the same group may still have different (strong or weak) correlations with objectives, even if they are only related to conver-gence or diversity. This situation not only reduces the accuracy of the grouping of decision variables, but also affects the allocation of computational resources. To address this issue, an algorithm based on dual analysis of objective space and decision space to group decision variables more accurately for solving large-scale many-objective optimization problems is proposed; this algorithm is called LM-DAS. It first divides decision variables into two categories: convergence-related variables and the diversity-related variables. Then, the correlation be-tween convergence-related variables and objective functions is analyzed. The decision space is divided into several subspaces according to the objective importance. Next, the decision variables are grouped using the method of interaction analysis between two level variables. Under the premise of ensuring the correctness of the grouping as much as possible, the algorithm can allocate more search resources to decision variables that are related to more important objective functions. The performance of LM-DAS is compared with four representative algorithms for 71 test instances. These instances involved 5-10 objectives and 200-1000 decision variables. The experimental results demonstrate that the proposed algorithm is competitive and effective.
查看更多>>摘要：The design of Ant Colony Optimization (ACO) has been inspired by the foraging behavior of ant colonies. ACO is one of the most widely used metaheuristic algorithms applicable to various optimization problems. Nevertheless, the deficiency of ACO is early maturity and slow convergence, usually leading to dissatisfactory performance. In this research, a new type of ACO is proposed with innovative adaptive learning mechanism is devised (the algorithm is called ADACO). In the paper, first, the ACO algorithm for Traveling Salesman Problem (TSP) is modeled in the framework of reinforcement learning (RL) and learns a best policy by stochastic gradient descent (SGD). Then, an adaptive gradient descent strategy, which can exploit the update history of per-dimensional pheromones to achieve intelligent convergence, is integrated into the ACO algorithm as ADACO. A parallel computation process is implemented in the process to expedite computational efficiency. Finally, through case studies in TSP and Capacitated Vehicle Routing Problem (CVRP), ADACO is validated. ADACO is trialed on various sizes of TSP and CVRP instances and compared with other state-of-the-art algorithms. Results show that ADACO is competitive in terms of accuracy (better in most cases), stability (statistically significant) and adaptability (support various types of problems). The results also elucidate that the algorithm maintains good computational efficiency owing to its parallel implementation. It can be concluded that ADACO is effectively applicable to routing problems with good performance.
查看更多>>摘要：Memetic Algorithms and, in general, approaches underneath the wider Memetic Computing paradigm, have been at the core of a frantic research activity since the very inception of this research area in the late eighties. The community working in this area has so far showcased the benefits of hybridizing population-based algorithms with trajectory-based methods or any other specialized procedures that encompass problem-specific knowledge in a variety of real-world scenarios. From the perspective of the algorithms themselves, this hybridization can be realized in many different ways: it is this upsurge of manifold algorithmic approaches what has maintained a vigorous and intense activity around Memetic Computing over the years, progressively adapting the paradigm to newly emerging problem formulations and characteristics. This editorial introduces the readership of Swarm and Evolutionary Computation to the contributions finally included in the Special Issue on Memetic Computing: Accelerating Optimization Heuristics with Problem-Dependent Local Search Methods . The high quality of the works presented in this editorial unquestionably proves the excellent health of this vibrant research area, as well as its continued success at tackling challenging real-world optimization problems.
Kulkarni, Divya D.Semwal, TusharNair, Shivashankar B.
17页
查看更多>>摘要：Evolutionary robotics employs unconventional techniques to continuously evolve controllers for robots, based on their fitness values. In most cases, a parent controller is subjected to mutation to evolve its offspring. If the offspring performs better than the parent, the former is made to replace the latter. This essentially results in a major loss in information learned by the parents over generations. One simple workaround to circumvent this problem is to maintain a Hall of Fame (HoF) comprising the best parent controllers for use in future generations. In embodied evolutionary robotic scenarios, caching a large number of controllers in an HoF would result in increased computational overheads while selecting the best out of them, resulting in a drastic reduction in performance. With no means to find an upper limit to the number of controllers that can populate an HoF a priori , devising a technique to dynamically regulate this population is imperative. In this work, a novel method to evict the non-performing controllers within an HoF based on the dynamics of the system, is proposed. We describe the evolution of such controllers using genetic operators that eventually form an Idiotypic Network. A constantly varying Resource , associated with each controller together with its concentration in the Idiotypic Network, helps decide its eviction from the HoF. Experiments performed using simulations and also a real robot indicate a marked improvement in the learning process due to the dynamic eviction policy.
查看更多>>摘要：Balancing between the optimization of objective functions and constraint satisfaction is essential to handle constrained multi-objective optimization problems (CMOPs). Recently, various methods have been presented to enhance the performance for the constrained multi-objective optimization evolutionary algorithms (CMOEAs). However, most of them encounter difficulties when dealing with the CMOPs with complex feasible regions. To overcome this drawback, this paper proposes a tri-population based co-evolutionary framework (TriP): i) the first and second populations are evolved through a weak co-evolutionary relation for the original and unconstrained problems respectively to handle CMOPs with relatively simple constraints; and ii) the third population is evolved solely for the constraint relaxed problem with constraint relaxation technique. The cooperation of three populations preserve the advantages of weak co-evolution and constraint relaxation. Experiments on six benchmark CMOPs with 65 instances and diverse features are performed. Compared to 9 state-of-the-art CMOEAs, the proposed framework yields highly competitive performance and the best versatility. In addition, the effectiveness of the proposed framework on handling real-world CMOPs is also verified.
查看更多>>摘要：This article presents the Ant Colony Optimization algorithm to solve the Travelling Salesman Problem. The pro-posed algorithm implements three novel techniques to enhance the overall performance, lower the execution time and reduce the negative effects particularly connected with ACO-based methods such as falling into a local optimum and issues with settings of control parameters for different instances. These techniques include (a) the node clustering concept where transition nodes are organised in a set of clusters, (b) adaptive pheromone evapo-ration controlled dynamically based on the information entropy and (c) the formulation of the new termination condition based on the diversity of solutions in population. To verify the effectiveness of the proposed principles, a number of experiments were conducted using 30 benchmark instances (ranging from 51 to 2,392 nodes with various nodes topologies) taken from the well-known TSPLIB benchmarks and the results are compared with sev-eral state-of-the-art ACO-based methods; the proposed algorithm outperforms these rival methods in most cases. The impact of the novel techniques on the behaviour of the algorithm is thoroughly analysed and discussed in respect to the overall performance, execution time and convergence.
NSTL
Elsevier