1,721,054 research outputs found
Interactive evolutionary multiobjective optimization with modular physical user interface
No full text© 2022 Copyright held by the owner/author(s).Incorporating the preferences of a domain expert, a decision-maker (DM), in solving multiobjective optimization problems increased in popularity in recent years. The DM can choose to use different types of preferences depending on his/her comfort, requirements, or the problem being solved. Most papers, where preference-based and interactive algorithms have been proposed, do not pay attention to the user interfaces and input devices. If they do, they use character or graphics-based preference input methods. We propose the option of using a physical or tactile input device that gives the DM a better sense of control over providing his/her preferences. However, off the shelf hardware devices are not tailored to solve multiobjective optimization problems and provide many controls that may increase the cognitive load on the DM. In this paper, we propose a fully modular physical user interface to input preference information for solving multiobjective optimization problems. The modularity allows to arrange each input module in various ways depending on the algorithm, DM’s requirements, or the problem being solved. The device can be used with any computer and uses web-based visualizations. We demonstrate the potential of the physical interface by solving a real-world problem with an interactive decomposition-based multiobjective evolutionary algorithm.peerReviewe
Survivor selection in a crossoverless evolutionary algorithm
Full text linkThe plant propagation algorithm is a crossoverless population based evolutionary algorithm, defaultly deploying the plus-selection method for survivor selection - combining parents and offspring population and then selecting the best popSize individuals. In this study, we explore eight different survivor selection methods (plus and comma selection, tournament selection with and without replacement, elitist tournament selection, linear ranking selection and (elitist) roulette wheel selection) on 59 continuous benchmark test function instances and compare the results. In the results, the tournament selection methods outperform PPA's default selection method on 83% to 88% of the 59 benchmark functions. Results show that the performance of all selection methods diminish as dimensions of benchmark function instances increase. Analysis indicates that the tournament selection methods employ more exploitation by decreasing population diversity. Future research should establish if this also benefits performance on other benchmark functions and industrial problems.</p
What makes the dynamic capacitated arc routing problem hard to solve:insights from fitness landscape analysis
Full text linkThe Capacitated Arc Routing Problem (CARP) aims at assigning vehicles to serve tasks which are located at different arcs in a graph. However, the originally planned routes are easily affected by different dynamic events like newly added tasks. This gives rise to Dynamic CARP (DCARP) instances, which need to be efficiently optimized for new high-quality service plans in a short time. However, it is unknown which dynamic events make DCARP instances especially hard to solve. Therefore, in this paper, we provide an investigation of the influence of different dynamic events on DCARP instances from the perspective of fitness landscape analysis based on a recently proposed hybrid local search (HyLS) algorithm. We generate a large set of DCARP instances based on a variety of dynamic events and analyze the fitness landscape of these instances using several different measures such as fitness correlation length. From the empirical results we conclude that cost-related events have no significant impact on the difficulty of DCARP instances, but instances which require more new vehicles to serve the remaining tasks are harder to solve. These insights improve our understanding of the DCARP instances and pave the way for future work on improving the performance of DCARP algorithms
The intersection of evolutionary computation and explainable AI.
Full text linkIn the past decade, Explainable Artificial Intelligence (XAI) has attracted a great interest in the research community, motivated by the need for explanations in critical AI applications. Some recent advances in XAI are based on Evolutionary Computation (EC) techniques, such as Genetic Programming. We call this trend EC for XAI. We argue that the full potential of EC methods has not been fully exploited yet in XAI, and call the community for future efforts in this field. Likewise, we find that there is a growing concern in EC regarding the explanation of population-based methods, i.e., their search process and outcomes. While some attempts have been done in this direction (although, in most cases, those are not explicitly put in the context of XAI), we believe that there are still several research opportunities and open research questions that, in principle, may promote a safer and broader adoption of EC in real-world applications. We call this trend XAI within EC. In this position paper, we briefly overview the main results in the two above trends, and suggest that the EC community may play a major role in the achievement of XAI
Facility location problem and permutation flow shop scheduling problem: a linked optimisation problem.
Full text linkThere is a growing literature spanning several research communities that studies multiple optimisation problems whose solutions interact, thereby leading researchers to consider suitable approaches to joint solution. Real-world problems, like supply chain, are systems characterised by such interactions. A decision made at one point of the supply chain could have significant consequence that ripples through linked production and transportation systems. Such interactions would require complex algorithmic designs. This paper, therefore, investigates the linkages between a facility location and permutation flow shop scheduling problems of a distributed manufacturing system with identical factory (FLPPFSP). We formulate a novel mathematical model from a linked optimisation perspective with objectives of minimising facility cost and makespan. We present three algorithmic approaches in tackling FLPPFSP; Non-dominated Sorting Genetic Algorithm for Linked Problem (NSGALP), Multi-Criteria Ranking Genetic Algorithm for Linked Problem (MCRGALP), and Sequential approach. To understand FLPPFSP linkages, we conduct a pre-assessment by randomly generating 10000 solution pairs on all combined problem instances and compute their respective correlation coefficients. Finally, we conduct experiments to compare results obtained by the selected algorithmic methods on 620 combined problem instances. Empirical results demonstrate that NSGALP outperforms the other two methods based on relative hypervolume, hypervolume and epsilon metrics
Fast non-elitist evolutionary algorithms with power-law ranking selection
Full text linkTheoretical evidence suggests that non-elitist evolutionary algorithms (EAs) with non-linear selection mechanisms can efficiently overcome broad classes of local optima where elitist EAs fail. However, the analysis assumes a weak selective pressure and mutation rates carefully chosen close to the "error threshold", above which they cease to be efficient. On problems easier for hill-climbing, the populations may slow down these algorithms, leading to worse runtime compared with variants of the elitist (1+1) EA. Here, we show that a non-elitist EA with power-law ranking selection leads to fast runtime on easy benchmark problems, while maintaining the capability of escaping certain local optima where the elitist EAs spend exponential time in the expectation. We derive a variant of the level-based theorem which accounts for power-law distributions. For classical theoretical benchmarks, the expected runtime is stated with small leading constants. For complex, multi-modal fitness landscapes, we provide sufficient conditions for polynomial optimisation, formulated in terms of deceptive regions sparsity and fitness valleys density. We derive the error threshold and show extreme tolerance to high mutation rates. Experiments on NK-Landscape functions, generated according to the Kauffman's model, show that the algorithm outperforms the (1+1) EA and the univariate marginal distribution algorithm (UMDA).</p
Evolving parsimonious circuits through Shapley value-based genetic programming
Full text linkEvolutionary analog circuit design is a challenging task due to the large search space incurred by the circuit topology and device values. Applying genetic operators on randomly selected genes may make it difficult to identify which part of sub-circuit is beneficial to the evolution and even destroy useful sub-circuits, potentially incurring stagnation of the evolutionary process and bloat on the evolved circuits. In this paper, we propose a tree-based approach called Shapley Circuit Tree that incorporates Shapley values for quantifying the contribution of each function node of the circuit tree to the performance of the whole tree, to guide the evolutionary process. Our experiments on three benchmarks show that the proposed approach is able to evolve analog circuits with smaller area while converging faster than existing approaches
Hard problems are easier for success-based parameter control
No full textRecent works showed that simple success-based rules for self-adjusting parameters in evolutionary algorithms (EAs) can match or outperform the best fixed parameters on discrete problems. Non-elitism in a (1, λ) EA combined with a self-adjusting of spring population size λ outperforms common EAs on the multimodal Cliff problem. However, it was shown that this only holds if the success rate λ that governs self-adjustment is small enough. Otherwise, even on OneMax, the self-adjusting (1, λ) EA stagnates on an easy slope, where frequent successes drive down the of spring population size.We show that self-adjustment works as intended in the absence of easy slopes. We define everywhere hard functions, for which successes are never easy to find and show that the self-adjusting (1, λ) EA is robust with respect to the choice of success rates λ. We give a general fitness-level upper bound on the number of evaluations and show that the expected number of generations is at most [EQUATION] where d is the number of non-optimal fitness values and [EQUATION] is the smallest probability of finding an improvement from a non-optimal search point. We discuss implications for the everywhere hard function LeadingOnes and a new class OneMaxBlocks of everywhere hard functions with tunable difficulty
Reproducibility and baseline reporting for dynamic multi-objective benchmark problems
No full textDynamic multi-objective optimization problems (DMOPs) are widely accepted to be more challenging than stationary problems due to the time-dependent nature of the objective functions and/or constraints. Evaluation of purpose-built algorithms for DMOPs is often performed on narrow selections of dynamic instances with differing change magnitude and frequency or a limited selection of problems. In this paper, we focus on the reproducibility of simulation experiments for parameters of DMOPs. Our framework is based on an extension of PlatEMO, allowing for the reproduction of results and performance measurements across a range of dynamic settings and problems. A baseline schema for dynamic algorithm evaluation is introduced, which provides a mechanism to interrogate performance and optimization behaviours of well-known evolutionary algorithms that were not designed specifically for DMOPs. Importantly, by determining the maximum capability of non-dynamic multi-objective evolutionary algorithms, we can establish the minimum capability required of purpose-built dynamic algorithms to be useful. The simplest modifications to manage dynamic changes introduce diversity. Allowing non-dynamic algorithms to incorporate mutated/random solutions after change events determines the improvement possible with minor algorithm modifications. Future expansion to include current dynamic algorithms will enable reproduction of their results and verification of their abilities and performance across DMOP benchmark space
- …
