Previous work proposed to unify an algebraic theory of fitness landscapes and a geometric framework of evolutionary algorithms (EAs). One of the main goals behind this unification is to develop an analytical method th...
详细信息
ISBN:
(数字)9783030167110
ISBN:
(纸本)9783030167103;9783030167110
Previous work proposed to unify an algebraic theory of fitness landscapes and a geometric framework of evolutionary algorithms (EAs). One of the main goals behind this unification is to develop an analytical method that verifies if a problem's landscape belongs to certain abstract convex landscape classes, where certain recombination-based EAs (without mutation) have polynomial runtime performance. this paper advances such unification by showing that: (a) crossovers can be formally classified according to geometric or algebraic axiomatic properties;and (b) the population behaviour induced by certain crossovers in recombination-based EAs can be formalised in the geometric and algebraic theories. these results make a significant contribution to the basis of an integrated geometric-algebraic framework with which analyse recombination spaces and recombination based EAs.
We investigate a variant of the facility location problem concerning the optimal distribution of service points with incomplete information within a certain geographical area. the application scenario is generic in pr...
详细信息
ISBN:
(数字)9783030167110
ISBN:
(纸本)9783030167103;9783030167110
We investigate a variant of the facility location problem concerning the optimal distribution of service points with incomplete information within a certain geographical area. the application scenario is generic in principle, but we have the setup of charging stations for electric vehicles or rental stations for bicycles or cars in mind. When planning such systems, estimating under which conditions which customer demand can be fulfilled is fundamental in order to evaluate and optimize possible solutions. In this paper we present a cooperative optimization approach for distributing service points that incorporates potential customers not only in the data acquisition but also during the optimization process. A surrogate objective function is used to evaluate intermediate solutions during the optimization. the quality of this surrogate objective function is iteratively improved by learning from the feedback of potential users given to candidate solutions. For the actual optimization we consider a population based iterated greedy algorithm. Experiments on artificial benchmark scenarios with idealized simulated user behavior show the learning capabilities of the surrogate objective function and the effectiveness of the optimization.
We conduct the first ever statistical comparison between two Local Optima Network (LON) sampling algorithms. these methodologies attempt to capture the connectivity in the local optima space of a fitness landscape. On...
详细信息
ISBN:
(数字)9783030167110
ISBN:
(纸本)9783030167103;9783030167110
We conduct the first ever statistical comparison between two Local Optima Network (LON) sampling algorithms. these methodologies attempt to capture the connectivity in the local optima space of a fitness landscape. One sampling algorithm is based on a random-walk snowballing procedure, while the other is centred around multiple traced runs of an Iterated Local Search. Both of these are proposed for the Quadratic Assignment Problem (QAP), making this the focus of our study. It is important to note the sampling algorithm frameworks could easily be modified for other domains. In our study descriptive statistics for the obtained search space samples are contrasted and commented on. the LON features are also used in linear mixed models and random forest regression for predicting heuristic optimisation performance of two prominent heuristics for the QAP on the underlying combinatorial problems. the model results are then used to make deductions about the sampling algorithms' utility. We also propose a specific set of LON metrics for use in future predictive models alongside previously-proposed network metrics, demonstrating the payoff in doing so.
the output of an optimal recombination operator for two parent solutions is a solution withthe best possible value for the objective function among all the solutions fulfilling the gene transmission property: the val...
详细信息
ISBN:
(数字)9783030167110
ISBN:
(纸本)9783030167103;9783030167110
the output of an optimal recombination operator for two parent solutions is a solution withthe best possible value for the objective function among all the solutions fulfilling the gene transmission property: the value of any variable in the offspring must be inherited from one of the parents. this set of solutions coincides withthe largest dynastic potential for the two parent solutions of any recombination operator withthe gene transmission property. In general, exploring the full dynastic potential is computationally costly, but if the variables of the objective function have a low number of non-linear interactions among them, the exploration can be done in O(4(ss) (n + m) + n(2)) time, for problems with n variables, m subfunctions and ss a constant. In this paper, we propose a quasi-optimal recombination operator, called Dynastic Potential Crossover (DPX), that runs in O(4(ss) (n+ m)+ n(2)) time in any case and is able to explore the full dynastic potential for low-epistasis combinatorial problems. We compare this operator, boththeoretically and experimentally, with two recently defined efficient recombination operators: Partition Crossover (PX) and Articulation Points Partition Crossover (APX). the empirical comparison uses NKQ Landscapes and MAX-SAT instances.
Algebraic evolutionary algorithms are an emerging class of meta-heuristics for combinatorialoptimization based on strong mathematical foundations. In this paper we introduce a decomposition-based algebraic evolutiona...
详细信息
ISBN:
(数字)9783319774497
ISBN:
(纸本)9783319774497;9783319774480
Algebraic evolutionary algorithms are an emerging class of meta-heuristics for combinatorialoptimization based on strong mathematical foundations. In this paper we introduce a decomposition-based algebraic evolutionary algorithm, namely MOEA/DEP, in order to deal with multiobjective permutation-based optimization problems. As a case of study, MOEA/DEP has been experimentally validated on a multiobjective permutation flowshop scheduling problem (MoPFSP). In particular, the makespan and total flowtime objectives have been investigated. Experiments have been held on a widely used benchmark suite, and the obtained results have been compared with respect to the state-of-the-art Pareto fronts for MoPFSP. the experimental results have been analyzed by means of two commonly used performance metrics for multiobjective optimization. the analysis clearly shows that MOEA/DEP reaches new state-of-the-art results for the considered benchmark.
To solve combinatorialoptimization problems, many metaheuristics use first or best improvement hill-climbing as intensification mechanism in order to find local optima. In particular, first improvement offers a good ...
详细信息
ISBN:
(数字)9783319774497
ISBN:
(纸本)9783319774497;9783319774480
To solve combinatorialoptimization problems, many metaheuristics use first or best improvement hill-climbing as intensification mechanism in order to find local optima. In particular, first improvement offers a good tradeoff between computation cost and quality of reached local optima. In this paper, we investigate a worst improvement-based moving strategy, never considered in the literature. Such a strategy is able to reach good local optima despite requiring a significant additional computation cost. Here, we investigate if such a pivoting rule can be efficient when considered within metaheuristics, and especially within iterated local search (ILS). In our experiments, we compare an ILS using a first improvement pivoting rule to an ILS using an approximated version of worst improvement pivoting rule. Both methods are launched withthe same number of evaluations on bit-string based fitness landscapes. Results are analyzed using some landscapes' features in order to determine if the worst improvement principle should be considered as a moving strategy in some cases.
the proceedings contain 17 papers. the special focus in this conference is on evolutionarycomputation in combinatorialoptimization. the topics include: A hybrid constructive mat-heuristic algorithm for the heterogen...
ISBN:
(纸本)9783319306971
the proceedings contain 17 papers. the special focus in this conference is on evolutionarycomputation in combinatorialoptimization. the topics include: A hybrid constructive mat-heuristic algorithm for the heterogeneous vehicle routing problem with simultaneous pick-up and delivery;a property preserving method for extending a single-objective problem instance to multiple objectives with specific correlations;an evolutionary approach to the full optimization of the traveling thief problem;application to the repetition-free longest common subsequence problem;deconstructing the big valley search space hypothesis;determining the difficulty of landscapes by pagerank centrality in local optima networks;efficient hill climber for multi-objective pseudo-Boolean optimization;evaluating hyperheuristics and local search operators for periodic routing problems;evolutionary algorithms for finding short addition chains;experimental evaluation of two approaches to optimal recombination for permutation problems;hyperplane elimination for quickly enumerating local optima;limits to learning in reinforcement learning hyper-heuristics;modifying colourings between time-steps to tackle changes in dynamic random graphs;particle swarm optimisation with sequence-like indirect representation for web service composition;particle swarm optimization for multi-objective web service location allocation;a multipopulation estimation of distribution algorithm based on problem similarity and solving the quadratic assignment problem with cooperative parallel extremal optimization.
this paper concerns the Inventory Routing Problem (IRP) which is an optimization problem addressing the optimization of transportation routes and the inventory levels at the same time. the IRP is notable for its diffi...
详细信息
ISBN:
(数字)9783319774497
ISBN:
(纸本)9783319774497;9783319774480
this paper concerns the Inventory Routing Problem (IRP) which is an optimization problem addressing the optimization of transportation routes and the inventory levels at the same time. the IRP is notable for its difficulty - even finding feasible initial solutions poses a significant problem. In this paper an evolutionary algorithm is proposed that uses approaches to solution construction and modification utilized by practitioners in the field. the population for the EA is initialized starting from a base solution which in this paper is generated by a heuristic, but can as well be a solution provided by a domain expert. Subsequently, feasibility-preserving moves are used to generate the initial population. In the paper dedicated recombination and mutation operators are proposed which aim at generating new solutions without loosing feasibility. In order to reduce the search space, solutions in the presented EA are encoded as lists of routes withthe quantities to be delivered determined by a supplying policy. the presented work is a step towards utilizing domain knowledge in evolutionarycomputation. the EA presented in this paper employs mechanisms of solution initialization capable of generating a set of feasible initial solutions of the IRP in a reasonable time. Presented operators generate new feasible solutions effectively without requiring a repair mechanism.
Local optima networks are a valuable tool used to analyse and visualise the global structure of combinatorial search spaces;in particular, the existence and distribution of multiple funnels in the landscape. We extrac...
详细信息
ISBN:
(数字)9783319774497
ISBN:
(纸本)9783319774497;9783319774480
Local optima networks are a valuable tool used to analyse and visualise the global structure of combinatorial search spaces;in particular, the existence and distribution of multiple funnels in the landscape. We extract and analyse the networks induced by Chained-LK, a powerful iterated local search for the TSP, on a large set of randomly generated (Uniform and Clustered) instances. Results indicate that increasing the perturbation strength employed by Chained-LK modifies the landscape's global structure, withthe effect being markedly different for the two classes of instances. Our quantitative analysis shows that several funnel metrics have stronger correlations with Chained-LK success rate than the number of local optima, indicating that global structure clearly impacts search performance.
暂无评论