Many important problems can be regarded as maximizing submodular functions under some constraints. A simple multi-objective evolutionary algorithm called GSEMO has been shown to achieve good approximation for submodul...
详细信息
ISBN:
(纸本)9783030581145;9783030581152
Many important problems can be regarded as maximizing submodular functions under some constraints. A simple multi-objective evolutionary algorithm called GSEMO has been shown to achieve good approximation for submodular functions efficiently. While there have been many studies on the subject, most of existing run-time analyses for GSEMO assume a single cardinality constraint. In this work, we extend the theoretical results to partition matroid constraints which generalize cardinality constraints, and show that GSEMO can generally guarantee good approximation performance within polynomial expected run time. Furthermore, we conducted experimental comparison against a baseline GREEDY algorithm in maximizing undirected graph cuts on random graphs, under various partition matroid constraints. The results show GSEMO tends to outperform GREEDY in quadratic run time.
This paper attempts to employ evolutionary Algorithm(EA) techniques to evolve variants of a computer virus(Timid) that successfully evades popular antivirus scanners. Generating authentic variants of a specific malwar...
详细信息
This paper attempts to employ evolutionary Algorithm(EA) techniques to evolve variants of a computer virus(Timid) that successfully evades popular antivirus scanners. Generating authentic variants of a specific malware results in a valid database of malware variants, which is sought by anti-malware scanners, so as to identify the variants before they are released by malware developers. This preliminary investigation applies EAs to mutate the Timid virus with a simple code evasion strategy, i.e., insertion and deletion(if available) of a specific assembly code instruction directly into the virus source code. Starting with a database of over 60 popular antivirus scanners, this EA based approach for malware variant generation successfully evolves Timid variants that evade more than 97% of the antivirus scanners. The results from these preliminary investigations demonstrate the potential for EA based malware generation and also opens up avenues for further analysis.
The chance-constrained knapsack problem is a variant of the classical knapsack problem where each item has a weight distribution instead of a deterministic weight. The objective is to maximize the total profit of the ...
详细信息
ISBN:
(纸本)9781450371285
The chance-constrained knapsack problem is a variant of the classical knapsack problem where each item has a weight distribution instead of a deterministic weight. The objective is to maximize the total profit of the selected items under the condition that the weight of the selected items only exceeds the given weight bound with a small probability of alpha. In this paper, we consider problem-specific single-objective and multi-objective approaches for the problem. We examine the use of heavy-tail mutations and introduce a problem-specific crossover operator to deal with the chance-constrained knapsack problem. Empirical results for single-objective evolutionary algorithms show the effectiveness of our operators compared to the use of classical operators. Moreover, we introduce a new effective multi-objective model for the chance-constrained knapsack problem. We use this model in combination with the problem-specific crossover operator in multi-objective evolutionary algorithms to solve the problem. Our experimental results show that this leads to significant performance improvements when using the approach in evolutionary multi-objective algorithms such as GSEMO and NSGA-II.
Solving single objective constrained real-parameter optimization problems via population-based algorithms has attracted much attention. In this paper, a new self-tuning meta-heuristic approach called Fuzzy Controlled ...
详细信息
ISBN:
(纸本)9781728169293
Solving single objective constrained real-parameter optimization problems via population-based algorithms has attracted much attention. In this paper, a new self-tuning meta-heuristic approach called Fuzzy Controlled Cooperative Heterogeneous Algorithm (FCHA), which was proposed for constrained optimization, is introduced. The developed approach combines competition and cooperation between biology-inspired and evolutionary algorithms, regulated by fuzzy controller. It should be noted, that the epsilon-constrained method is utilized to handle the constraints for the solved optimization problems. The performance of the proposed FCHA algorithm is evaluated on 57 real-world constrained problems submitted for CEC 2020 special session. Its workability and usefulness are demonstrated;also ways of algorithm improvement are discussed.
evolutionary algorithms have been widely used for a range of stochastic optimization problems. In most studies, the goal is to optimize the expected quality of the solution. Motivated by real-world problems where cons...
详细信息
ISBN:
(纸本)9781450361118
evolutionary algorithms have been widely used for a range of stochastic optimization problems. In most studies, the goal is to optimize the expected quality of the solution. Motivated by real-world problems where constraint violations have extremely disruptive effects, we consider a variant of the knapsack problem where the profit is maximized under the constraint that the knapsack capacity bound is violated with a small probability of at most a. This problem is known as chance-constrained knapsack problem and chance-constrained optimization problems have so far gained little attention in the evolutionary computation literature. We show how to use popular deviation inequalities such as Chebyshev's inequality and Chernoff bounds as part of the solution evaluation when tackling these problems by evolutionary algorithms and compare the effectiveness of our algorithms on a wide range of chance-constrained knapsack instances.
Recently, it has repeatedly been reported that the search ability of Pareto dominance-based multi-objective evolutionary algorithms severely deteriorates with the increase in the number of objectives. In this paper, w...
详细信息
ISBN:
(纸本)9781643681016;9781643681009
Recently, it has repeatedly been reported that the search ability of Pareto dominance-based multi-objective evolutionary algorithms severely deteriorates with the increase in the number of objectives. In this paper, we examine the generality of the reported observations through computational experiments on a wide variety of test problems. First, we generate 18 types of test problems by combining various properties of Pareto fronts and feasible regions. Next, we examine the performance of a frequently-used Pareto dominance-based evolutionary algorithm called NSGA-II on the generated test problems in comparison with four decomposition-based algorithms. We observe that the performance of NSGA-II severely degrades for three types of many-objective test problems which are similar to frequently-used DTLZ1-4 test problems with triangular Pareto fronts. However, better results are obtained by NSGA-II than all the examined decomposition-based algorithms for nine types of test problems even when they have ten objectives. Then, we discuss why NSGA-II does not work well on DTLZ type test problems whereas it works well on other test problems.
This article explores the application of evolutionary algorithms and agent-oriented programming to solve the problem of searching and monitoring objectives through a fleet of unmanned aerial vehicles. The subproblem o...
详细信息
ISBN:
(纸本)9783030410056;9783030410049
This article explores the application of evolutionary algorithms and agent-oriented programming to solve the problem of searching and monitoring objectives through a fleet of unmanned aerial vehicles. The subproblem of static off-line planning is studied to find initial flight plans for each vehicle in the fleet, using evolutionary algorithms to achieve compromise values between the size of the explored area, the proximity of the vehicles, and the monitoring of points of interest defined in the area. The results obtained in the experimental analysis on representative instances of the surveillance problem indicate that the proposed techniques are capable of computing effective flight plans.
One of the possible ways to increase the end-to-end power transfer efficiency in a radiative Wireless Power Transfer (WPT) system is by transmitting multi-tone signals optimized according to the receiver rectenna'...
详细信息
ISBN:
(纸本)9781728166872
One of the possible ways to increase the end-to-end power transfer efficiency in a radiative Wireless Power Transfer (WPT) system is by transmitting multi-tone signals optimized according to the receiver rectenna's nonlinear behavior and the Channel State Information (CSI). This optimization problem is a non-convex problem that has been tackled in the past with Sequential Convex Programming (SCP) algorithms. Since SCP algorithms do not guarantee to track the globally optimal solutions, there is interest in applying some other optimization methods to this problem. Here we apply various evolutionary algorithms (EAs) with different characteristics. The performance of the designed waveforms is evaluated in Matlab, using a simplified Single Input Single Output (SISO) system model. EAs are successfully applied to waveform design for WPT and seem to track the optimal solutions in the tested cases. Moreover, the effectiveness of the SCP-QCLP method is verified.
evolutionary algorithms (EAs) are general-purpose problem solvers that usually perform an unbiased search. This is reasonable and desirable in a black-box scenario. For combinatorial optimization problems, often more ...
详细信息
ISBN:
(纸本)9781450371285
evolutionary algorithms (EAs) are general-purpose problem solvers that usually perform an unbiased search. This is reasonable and desirable in a black-box scenario. For combinatorial optimization problems, often more knowledge about the structure of optimal solutions is given, which can be leveraged by means of biased search operators. We consider the Minimum Spanning Tree (MST) problem in a single- and multi-objective version, and introduce a biased mutation, which puts more emphasis on the selection of edges of low rank in terms of low domination number. We present example graphs where the biased mutation can significantly speed up the expected runtime until (Pareto-)optimal solutions are found. On the other hand, we demonstrate that bias can lead to exponential runtime if "heavy" edges are necessarily part of an optimal solution. However, on general graphs in the single-objective setting, we show that a combined mutation operator which decides for unbiased or biased edge selection in each step with equal probability exhibits a polynomial upper bound - as unbiased mutation - in the worst case and benefits from bias if the circumstances are favorable.
It has been shown before that some results from the theory of evolutionary algorithms (EAs) may be used for the analysis of population dynamics in biology. In the present paper, we study the EAs without elite individu...
详细信息
暂无评论