Metaheuristics have yielded very promising results for the frequency assignment problem (FAP). However, the results obtainable using currently published methods are far from ideal in complex, large-scale instances. This paper applies and extends some of the most recent advances in evolutionary algorithms to two common variants of the FAP, and shows how, in traditional techniques, two common issues affect their performance: 1) premature convergence and 2) the way in which neutral networks are handled. A recent replacement-based diversity management strategy is successfully applied to alleviate the premature convergence drawback. Additionally, by properly defining a distance metric, the performance in the presence of neutrality can also be greatly improved. The replacement strategy combines the principle of transforming a single-objective problem into a multiobjective one by considering diversity as an additional objective, with the idea of adapting the balance induced between exploration and exploitation to the requirements of the different optimization stages. Tests with 44 publicly available instances yield very competitive results. New best-known frequency plans were generated for 11 instances, whereas in the remaining ones the best-known solutions were replicated. Comparisons with a large number of strategies designed to delay convergence of the population clearly show the advantages of our novel proposals.
Multimodal optimization (MMO) aiming to locate multiple optimal (or near-optimal) solutions in a single simulation run has practical relevance to problem solving across many fields. Population-based meta-heuristics have been shown particularly effective in solving MMO problems, if equipped with specifically-designed diversity-preserving mechanisms, commonly known as niching methods. This paper provides an updated survey on niching methods. This paper first revisits the fundamental concepts about niching and its most representative schemes, then reviews the most recent development of niching methods, including novel and hybrid methods, performance measures, and benchmarks for their assessment. Furthermore, this paper surveys previous attempts at leveraging the capabilities of niching to facilitate various optimization tasks (e.g., multiobjective and dynamic optimization) and machine learning tasks (e.g., clustering, feature selection, and learning ensembles). A list of successful applications of niching methods to real-world problems is presented to demonstrate the capabilities of niching methods in providing solutions that are difficult for other optimization methods to offer. The significant practical value of niching methods is clearly exemplified through these applications. Finally, this paper poses challenges and research questions on niching that are yet to be appropriately addressed. Providing answers to these questions is crucial before we can bring more fruitful benefits of niching to real-world problem solving.
We present a model of changing the intensity of interaction based on the individual behavior to study the iterated prisoner’s dilemma game in social networks. In this model, each individual has an assessed score of reputation which is obtained by considering the evaluation level of interactive partners for its present behavior. We focus on the effect of evaluation level on the changing intensity of interaction between individuals. For an individual with good behavior, the higher the evaluation level of its partners for its good behavior, the better its reputation, and the higher the probability of surrounding partners interaction with it. On the contrary, for an individual with bad behavior, the lower the evaluation level of its partners for its bad behavior, the worse its reputation, and the less the probability of surrounding neighbors interaction with it. Simulation results show that this effective mechanism can drastically facilitate the emergence and maintenance of cooperation in the population under a treacherous chip. Interestingly, for a small or moderate treacherous chip, the cooperation level monotonously ascends as the evaluation level increases; however, for a higher treacherous chip, existing an optimal evaluation level, which can result in the best promotion of cooperation. Furthermore, we find better agreement between simulation results and theoretical predictions obtained from an extended pair-approximation method, although there are some tiny deviations. We also show some typical snapshots of the system and investigate the reason for appearance and persistence of cooperation. The results further show the importance of evaluation level of individual behavior in coevolutionary relationships.
Cooperative co-evolution (CC) is an explicit means of problem decomposition in multipopulation evolutionary algorithms for solving large-scale optimization problems. For CC, subpopulations representing subcomponents of a large-scale optimization problem co-evolve, and are likely to have different contributions to the improvement of the best overall solution to the problem. Hence, it makes sense that more computational resources should be allocated to the subpopulations with greater contributions. In this paper, we study how to allocate computational resources in this context and subsequently propose a new CC framework named CCFR to efficiently allocate computational resources among the subpopulations according to their dynamic contributions to the improvement of the objective value of the best overall solution. Our experimental results suggest that CCFR can make efficient use of computational resources and is a highly competitive CCFR for solving large-scale optimization problems.
A steady state analysis of the optimization quality of a classical self-adaptive evolution strategy (ES) on a class of robust optimization problems is presented. A novel technique for calculating progress rates for nonquadratic noisy fitness landscapes is presented. This technique yields asymptotically exact results in the infinite population size limit. This technique is applied to a class of functions with noise-induced multimodality. The resulting progress rate formulas are compared with high-precision experiments. The influence of fitness resampling is considered and the steady state behavior of the ES is derived and compared with simulations. The questions whether one should sample and average fitness values and how to choose the truncation ratio are discussed giving rise to further research perspectives.