318 results on '"010201 computation theory & mathematics"'
Search Results
2. Quality-diversity optimisation
- Author
-
Antoine Cully, Stéphane Doncieux, and Jean-Baptiste Mouret
- Subjects
0106 biological sciences ,business.industry ,Computer science ,media_common.quotation_subject ,Environmental resource management ,0102 computer and information sciences ,02 engineering and technology ,021001 nanoscience & nanotechnology ,010603 evolutionary biology ,01 natural sciences ,010201 computation theory & mathematics ,0202 electrical engineering, electronic engineering, information engineering ,020201 artificial intelligence & image processing ,Quality (business) ,0210 nano-technology ,business ,media_common ,Diversity (business) - Published
- 2022
3. Bridging kriging believer and expected improvement using bump hunting for expensive black-box optimization
- Author
-
Tapabrata Ray, Hemant Kumar Singh, and Bing Wang
- Subjects
Mathematical optimization ,Bridging (networking) ,Optimization problem ,Computer science ,Sampling (statistics) ,0102 computer and information sciences ,02 engineering and technology ,01 natural sciences ,Range (mathematics) ,010201 computation theory & mathematics ,Kriging ,Black box ,0202 electrical engineering, electronic engineering, information engineering ,Infill ,020201 artificial intelligence & image processing ,Bump hunting - Abstract
For several real-world optimization problems, the evaluation of response functions may be expensive, computationally or otherwise. The number of design evaluations one can afford for such problems are therefore severely limited. Surrogate models are commonly used to guide the search for such computationally expensive optimization problems (CEOP). The surrogate models built using a limited number of true evaluations are used to identify the next infill/sampling location. Expected improvement (EI) is a well known infill criteria which balances exploration and exploitation by accounting for both mean and uncertainties in the current model. However, recent studies have shown that, somewhat counter-intuitively, a greedy ("believer") strategy can compete well with EI in solving CEOPs. In this study, we are interested in examining the relative performance of the two infill methods across a range of problems, and identify the influencing factors affecting their performance. Based on the empirical analysis, we further propose an algorithm incorporating the strengths of the two strategies. The numerical experiments demonstrate that the proposed algorithm is able to achieve a competitive performance across a range of problems with diverse characteristics; making it a strong candidate for solving black-box CEOPs.
- Published
- 2021
4. Runtime analysis of population-based evolutionary algorithms
- Author
-
Pietro S. Oliveto and Per Kristian Lehre
- Subjects
Theoretical computer science ,Computer science ,Evolutionary algorithm ,Interactive evolutionary computation ,0102 computer and information sciences ,02 engineering and technology ,Population based ,01 natural sciences ,Evolutionary computation ,Human-based evolutionary computation ,010201 computation theory & mathematics ,0202 electrical engineering, electronic engineering, information engineering ,020201 artificial intelligence & image processing ,Algorithm ,Evolutionary programming - Published
- 2021
5. Decomposition multi-objective optimisation
- Author
-
Ke Li and Qingfu Zhang
- Subjects
010201 computation theory & mathematics ,Computer science ,business.industry ,0202 electrical engineering, electronic engineering, information engineering ,Decomposition (computer science) ,020201 artificial intelligence & image processing ,0102 computer and information sciences ,02 engineering and technology ,Current (fluid) ,Process engineering ,business ,01 natural sciences - Published
- 2021
6. Theoretical analyses of multi-objective evolutionary algorithms on multi-modal objectives
- Author
-
Weijie Zheng and Benjamin Doerr
- Subjects
Mathematical optimization ,Computer science ,Evolutionary algorithm ,Contrast (statistics) ,0102 computer and information sciences ,02 engineering and technology ,Track (rail transport) ,01 natural sciences ,Multi-objective optimization ,Modal ,010201 computation theory & mathematics ,Simple (abstract algebra) ,0202 electrical engineering, electronic engineering, information engineering ,Benchmark (computing) ,Jump ,020201 artificial intelligence & image processing - Abstract
Previous theory work on multi-objective evolutionary algorithms considers mostly easy problems that are composed of unimodal objectives. This paper takes a first step towards a deeper understanding of how evolutionary algorithms solve multi-modal multi-objective problems. We propose the OneJumpZeroJump problem, a bi-objective problem with single objectives isomorphic to the classic jump function benchmark. We prove that the simple evolutionary multi-objective optimizer (SEMO) cannot compute the full Pareto front. In contrast, for all problem sizes n and all jump sizes [EQUATION], the global SEMO (GSEMO) covers the Pareto front in Θ((n-2k)nk) iterations in expectation. To improve the performance, we combine the GSEMO with two approaches, a heavy-tailed mutation operator and a stagnation detection strategy, that showed advantages in single-objective multi-modal problems. Runtime improvements of asymptotic order at least kΩ(k) are shown for both strategies. Our experiments verify the substantial runtime gains already for moderate problem sizes. Overall, these results show that the ideas recently developed for single-objective evolutionary algorithms can be effectively employed also in multi-objective optimization. This Hot-off-the-Press paper summarizes "Theoretical Analyses of Multi-Objective Evolutionary Algorithms on Multi-Modal Objectives" by B. Doerr and W. Zheng, which has been accepted for publication in AAAI 2021 [9].
- Published
- 2021
7. Towards a novel NSGA-II-based approach for multi-objective scientific workflow scheduling on hybrid clouds
- Author
-
Sadok Bouamama, Hamza Gharsellaoui, and Haithem Hafsi
- Subjects
Computer science ,business.industry ,Distributed computing ,media_common.quotation_subject ,Big data ,Cloud computing ,0102 computer and information sciences ,02 engineering and technology ,Supercomputer ,Grid ,01 natural sciences ,Multi-objective optimization ,Scheduling (computing) ,Interdependence ,Workflow ,010201 computation theory & mathematics ,Genetic algorithm ,0202 electrical engineering, electronic engineering, information engineering ,020201 artificial intelligence & image processing ,business ,media_common - Abstract
In the era of the big data and e-science revolution, the execution of such applications known as High Performance Computing (HPC) is becoming a challenging issue. In order to face these challenges, a new promising Large Scale Distributed Systems (LSDS) has emerged suchlike Grid and Cloud Computing. As a matter of fact, these HPC applications are commonly arranged as a form of interdependent tasks named workflows. Nevertheless, the new challenging topic is that the scheduling of these scientific workflows in the LSDS is a well-known NP-hard problem. The goal of this work is to design an Non-dominated Sorting Genetic Algorithm Version II (NSGA-II)-based approach for optimizing a multi objective scheduling of scientific workflows in hybrid distributed systems. This paper work deals with the proposition of two execution models: i) A Cumulative one aiming to improve the Pareto front quality in term of Makespan-Cost trade-off; ii) An Incremental execution fashion, what kind of Cost-driven approach leading to a solution diversity of the Pareto front in the objective space. Experiments conducted with multiple common scientific workflows point out significant improvement against the classic NSGA-II algorithm.
- Published
- 2019
8. Evolutionary many-objective optimization
- Author
-
Hisao Ishibuchi and Hiroyuki Sato
- Subjects
Mathematical optimization ,Fuzzy rule ,Computer science ,Evolutionary algorithm ,Pareto principle ,0102 computer and information sciences ,02 engineering and technology ,01 natural sciences ,Multi-objective optimization ,010201 computation theory & mathematics ,Knapsack problem ,Genetic algorithm ,Genetic fuzzy systems ,0202 electrical engineering, electronic engineering, information engineering ,020201 artificial intelligence & image processing ,ComputingMethodologies_GENERAL - Abstract
In this paper, we first explain why many-objective problems are difficult for Pareto dominance-based evolutionary multiobjective optimization algorithms such as NSGA-II and SPEA. Then we explain recent proposals for the handling of many-objective problems by evolutionary algorithms. Some proposals are examined through computational experiments on multiobjective knapsack problems with two, four and six objectives. Finally we discuss the viability of many-objective genetic fuzzy systems (i.e., the use of many-objective genetic algorithms for the design of fuzzy rule-based systems).
- Published
- 2019
9. Evolution and self-teaching in neural networks
- Author
-
Nam Le
- Subjects
Neuroevolution ,Artificial neural network ,Computer science ,business.industry ,Foraging ,Evolutionary algorithm ,0102 computer and information sciences ,02 engineering and technology ,01 natural sciences ,010201 computation theory & mathematics ,0202 electrical engineering, electronic engineering, information engineering ,020201 artificial intelligence & image processing ,Artificial intelligence ,Set (psychology) ,business - Abstract
Previous work presented a technique called evolving self-taught neural networks - neural networks that can teach themselves, intrinsically motivated, without external supervision or reward [3]. In an autonomous multi-agent setting in which the agent is primitively set to know little or nothing about its environment, self-teaching was shown to give rise to intelligence, whereas an evolutionary algorithm alone fails since it has no way to search without gradient information. In this paper, we conduct another comparative experiment in which the foraging agent is built more conscious of its environment beforehand. Experimental results show that the more conscious primitive design can let evolution alone be able to search. Yet the combination of evolution and self-teaching still outperforms the alternative. Indications for future work on evolving intelligence are also presented.
- Published
- 2019
10. Inferring structure and parameters of dynamic systems using particle swarm optimization
- Author
-
Muhammad Usman, George M. Coghill, Abubakr Awad, and Wei Pang
- Subjects
Structure (mathematical logic) ,Computer science ,Computer Science::Neural and Evolutionary Computation ,MathematicsofComputing_NUMERICALANALYSIS ,Particle swarm optimization ,Sampling (statistics) ,0102 computer and information sciences ,02 engineering and technology ,ComputingMethodologies_ARTIFICIALINTELLIGENCE ,01 natural sciences ,Latin hypercube sampling ,010201 computation theory & mathematics ,Simple (abstract algebra) ,Genetic algorithm ,0202 electrical engineering, electronic engineering, information engineering ,020201 artificial intelligence & image processing ,Hypercube ,Time series ,Algorithm - Abstract
Inferring models of dynamic systems from their time series data is a challenging task for optimization algorithms due to its potentially expensive computational cost and underlying large search space. In this study we aim to infer both the structure and parameters of a dynamic system model simultaneously by Particle Swarm Optimization (PSO), enhanced by effective stratified sampling strategies. More specifically we apply Latin Hyper Cube Sampling (LHS) with PSO. This leads to two novel swarm-inspired algorithms, LHS-PSO which can be used efficiently to learn the structure and parameters of simple and complex dynamic system models. We used a complex biological cancer model called Kinetochores, for assessing the performance of PSO and LHS-PSO. The experimental results demonstrate that LHS-PSO can find promising solutions with corresponding structure and parameters, and it outperforms PSO during our experiments.
- Published
- 2019
11. Enhanced optimization with composite objectives and novelty pulsation
- Author
-
Hormoz Shahrzad, Simon Lau, Babak Hodjat, Donn Goodhew, Risto Miikkulainen, Justin Dyer, Andrei Denissov, and Camille Dollé
- Subjects
Computer science ,Mechanism (biology) ,business.industry ,Novelty ,0102 computer and information sciences ,02 engineering and technology ,Machine learning ,computer.software_genre ,01 natural sciences ,Multi-objective optimization ,Transformation (function) ,010201 computation theory & mathematics ,0202 electrical engineering, electronic engineering, information engineering ,020201 artificial intelligence & image processing ,Artificial intelligence ,business ,computer ,Selection (genetic algorithm) - Abstract
An important benefit of multi-objective search is that it maintains a diverse population of candidates, which helps in deceptive problems in particular. Not all diversity is useful, however: candidates that optimize only one objective while ignoring others are rarely helpful. A recent solution is to replace the original objectives by their linear combinations, thus focusing the search on the most useful tradeoffs between objectives. To compensate for the loss of diversity, this transformation is accompanied by a selection mechanism that favors novelty. This paper improves this approach further by introducing novelty pulsation, i.e. a systematic method to alternate between novelty selection and local optimization. In the highly deceptive problem of discovering minimal sorting networks, it finds state-of-the-art solutions significantly faster than before. In fact, our method so far has established a new world record for the 20-lines sorting network with 91comparators. In the real-world problem of stock trading, it discovers solutions that generalize significantly better on unseen data. Composite Novelty Pulsation is therefore a promising approach to solving deceptive real-world problems through multi-objective optimization.
- Published
- 2019
12. Modularity metrics for genetic programming
- Author
-
Lee Spector and Anil Kumar Saini
- Subjects
Modularity (networks) ,Theoretical computer science ,Computer science ,business.industry ,Process (engineering) ,media_common.quotation_subject ,Genetic programming ,0102 computer and information sciences ,02 engineering and technology ,Reuse ,01 natural sciences ,Modularity ,Software ,010201 computation theory & mathematics ,0202 electrical engineering, electronic engineering, information engineering ,020201 artificial intelligence & image processing ,Fraction (mathematics) ,Quality (business) ,business ,media_common - Abstract
With improvements in selection methods and genetic operators, Genetic Programming (GP) has been able to solve many software synthesis problems. However, so far, the primary focus of GP has been on improving success rates (fraction of the runs that succeeds in finding a solution). Less attention has been paid to other important characteristics and quality measures of human-written programs. One such quality measure is modularity. Since the introduction of Automatically Defined Functions (ADFs) by John Koza, most of efforts involving modularity in GP have been directed towards pre-programming modularity into the GP system, rather than measuring it for evolved programs. Modularity has played a central role in evolutionary biology. To study its effects on the evolution of software, however, we need a quantitative formulation of modularity. In this paper, we present two platform-independent modularity metrics, namely, reuse and repetition, that make use of the information contained in the execution traces of the programs. We describe the process of calculating these metrics for any evolved program, using problems that have been solved with the PushGP system as examples. We also discuss some mechanisms for integrating these metrics into the evolution framework itself.
- Published
- 2019
13. A bi-level hybrid PSO
- Author
-
Inês Soares, Carlos Henggeier Antunes, and Maria João Alves
- Subjects
Mathematical optimization ,Computer science ,business.industry ,Computation ,Tariff ,Particle swarm optimization ,0102 computer and information sciences ,02 engineering and technology ,Solver ,01 natural sciences ,Profit (economics) ,Demand response ,010201 computation theory & mathematics ,0202 electrical engineering, electronic engineering, information engineering ,020201 artificial intelligence & image processing ,Electricity ,business - Abstract
1With the implementation of dynamic tariffs, the electricity retailer may define distinct energy prices along the day. These tariff schemes encourage consumers to adopt different patterns of consumption with potential savings and enable the retailer to manage the interplay between wholesale and retail prices. In this work, the interaction between retailer and consumers is hierarchically modelled as a bi-level (BL) programming problem. However, if the lower level (LL) problem, which deals with the optimal operation of the consumer's appliances, is difficult to solve, it may not be possible to obtain its optimal solution, and therefore the solution to the BL problem is not feasible. Considering a computation budget to solve LL problems, a hybrid particle swarm optimization (PSO) - mixed-integer programming (MLP) approach is proposed to estimate good quality bounds for the upper level (UL) objective function. This work is based on [4].
- Published
- 2019
14. Collaborative diversity control strategy for random drift particle swarm optimization
- Author
-
Vasile Palade, Qidong Chen, Wei Fang, Li Chao, and Jun Sun
- Subjects
Mathematical optimization ,Optimization problem ,Computer science ,Control (management) ,Random drift ,Process (computing) ,Particle swarm optimization ,0102 computer and information sciences ,02 engineering and technology ,01 natural sciences ,Swarm intelligence ,010201 computation theory & mathematics ,0202 electrical engineering, electronic engineering, information engineering ,020201 artificial intelligence & image processing ,Premature convergence ,Diversity (business) - Abstract
Random drift particle swarm optimization (RDPSO) is a swarm intelligence algorithm inspired by the trajectory analysis of the canonical particle swarm optimization (PSO) and the free electron model in metal conductors placed in an external electric field. However, the RDPSO algorithm may easily encounter premature convergence when solving multimodal optimization problems. In order to deal with this issue, a new collaborative diversity control strategy for RDPSO is presented in this paper. Within this strategy, two kinds of diversity measures are used and changed in a collaborative manner to make the evolving process of the RDPSO controllable, so that premature convergence can be avoided and a final good solution can be found. Experimental results, when comparing with the canonical RDPSO and the canonical RDPSO using ring neighborhood topology, show that the proposed collaborative diversity control strategy can significantly improve the performance of the RDPSO algorithm for multimodal optimization problems in most cases.
- Published
- 2019
15. Bond strength prediction of FRP-bar reinforced concrete
- Author
-
Nizar Lajnef, Hamed Bolandi, Kaveh Barri, Wolfgang Banzhaf, and Amir H. Alavi
- Subjects
chemistry.chemical_classification ,Bar (music) ,Computer science ,business.industry ,Bond strength ,Genetic programming ,0102 computer and information sciences ,02 engineering and technology ,Polymer ,Structural engineering ,Fibre-reinforced plastic ,Reinforced concrete ,01 natural sciences ,Multi gene ,chemistry ,010201 computation theory & mathematics ,0202 electrical engineering, electronic engineering, information engineering ,020201 artificial intelligence & image processing ,business ,Test data - Abstract
This paper presents a new multi-gene genetic programming (MGGP) approach for prediction of bond strength of Fiber Reinforced Polymers (FRP) bars to concrete. The MGGP technique models the bond behavior of FRP bars by integrating the capabilities of standard genetic programming and classical regression. The factors that affect the bond strength of FRP bars were identified from the test data of 223 beam-test specimens in the literature and fed into the GP system to produce a model. Our study concludes that the proposed MGGP model predicts bond strength of FRP bars in concrete quite accurately. Indeed, the proposed MGGP model equation has better performance than the code equation currently used by the American Concrete Institute (ACI).
- Published
- 2019
16. A mixed framework to support heterogeneous collection asset scheduling
- Author
-
Rami Abielmona, Alexander Tekse, Ibrahim Abualhaol, Jean Berger, Moufid Harb, and Emil M. Petriu
- Subjects
Artificial neural network ,Job shop scheduling ,Computer science ,0102 computer and information sciences ,02 engineering and technology ,computer.software_genre ,01 natural sciences ,Scheduling (computing) ,010201 computation theory & mathematics ,Genetic algorithm ,0202 electrical engineering, electronic engineering, information engineering ,Resource allocation ,Graph (abstract data type) ,020201 artificial intelligence & image processing ,Data mining ,computer ,Decision model - Abstract
A new framework1 mixing evolutionary approach, discrete-event simulation and deep neural networks is proposed to achieve multi-asset collection/image acquisition scheduling in a surveillance context. It combines an extended graph-based hybrid genetic algorithm (GA) used for satellite image acquisition scheduling, with a predictive simulation-based deep neural network and knowledge-based capabilities to solve an heterogeneous collection asset scheduling problem. Plan execution simulation and neural networks predict track trajectories target behaviors. In contrast, a knowledge-based approach is used to estimate target identification. Both assessments are exploited to instantiate key solution quality parameters of a generalized decision model aimed at maximizing task collection value subject to a variety of collector capacity constraints. The mixed framework departs from basic point target/area coverage task modeling, introducing tracking and identification tasks while expanding resource allocation to various space, air and ground-based deployable image acquisition/collection asset types.
- Published
- 2019
17. Improving classification performance of support vector machines via guided custom kernel search
- Author
-
Kumar Ayush and Abhishek Sinha
- Subjects
business.industry ,Computer science ,0102 computer and information sciences ,02 engineering and technology ,Machine learning ,computer.software_genre ,01 natural sciences ,Support vector machine ,Task (computing) ,Kernel (linear algebra) ,010201 computation theory & mathematics ,Kernel (statistics) ,0202 electrical engineering, electronic engineering, information engineering ,Key (cryptography) ,Reinforcement learning ,020201 artificial intelligence & image processing ,Artificial intelligence ,business ,computer ,MNIST database - Abstract
Support Vector Machines (SVMs) deliver state-of-the-art performance in real-world applications and are established as one of the standard tools for machine learning and data mining. A key problem of these methods is how to choose an optimal kernel function. The real-world applications have also emphasized the need to adapt the kernel to the characteristics of heterogeneous data in order to boost the classification accuracy. Therefore, our goal is to automatically search a task specific kernel function. We use reinforcement learning based search mechanisms to discover custom kernel functions and verify the effectiveness of our approach by conducting an empirical evaluation with the discovered kernel function on MNIST classification. Our experiments show that the discovered kernel function shows significantly better classification performance than well-known classic kernels. Our solution will be very effective for resource constrained systems with low memory footprint which rely on traditional machine learning algorithms like SVMs for classification tasks.
- Published
- 2019
18. Hot off the press in expert systems on underwater robotic missions
- Author
-
José Daniel Hernández Sosa and Aleš Zamuda
- Subjects
Underwater glider ,Computer science ,Real-time computing ,Ocean current ,Evolutionary algorithm ,0102 computer and information sciences ,02 engineering and technology ,Numerical weather prediction ,computer.software_genre ,01 natural sciences ,Expert system ,010201 computation theory & mathematics ,Differential evolution ,0202 electrical engineering, electronic engineering, information engineering ,Benchmark (computing) ,020201 artificial intelligence & image processing ,Motion planning ,Underwater ,computer - Abstract
The real-world implementation of Underwater Glider Path Planning (UGPP) over the dynamic and changing environment in deep ocean waters requires complex mission planning under very high uncertainties. Such a mission is also influenced to a large extent by remote sensing for forecasting weather models outcomes used to predict spatial currents in deep sea, further limiting the available time for accurate run-time decisions by the pilot, who needs to re-test several possible mission scenarios in a short time, usually a few minutes. Hence, this paper presents the recently proposed UGPP mission scenarios' optimization with a recently well performing algorithm for continuous numerical optimization, Success-History Based Adaptive Differential Evolution Algorithm (SHADE) including Linear population size reduction (L-SHADE). An algorithm for path optimization considering the ocean currents' model predictions, vessel dynamics, and limited communication, yields potential way-points for the vessel based on the most probable scenario; this is especially useful for short-term opportunistic missions where no reactive control is possible. The newly obtained results with L-SHADE outperformed existing literature results for the UGPP benchmark scenarios. Thereby, this new application of Evolutionary Algorithms to UGPP contributes significantly to the capacity of the decision-makers when they use the improved UGPP expert system yielding better trajectories.
- Published
- 2019
19. Exploitation of multiple surrogate models in multi-point infill sampling strategies
- Author
-
C. Sainvitu, P. Beaucaire, and Charlotte Beauthier
- Subjects
Mathematical optimization ,Computer science ,Sampling (statistics) ,0102 computer and information sciences ,02 engineering and technology ,01 natural sciences ,Identification (information) ,Surrogate model ,010201 computation theory & mathematics ,Search algorithm ,0202 electrical engineering, electronic engineering, information engineering ,Benchmark (computing) ,020201 artificial intelligence & image processing ,Representation (mathematics) - Abstract
This work presents interesting multi-point search algorithms exploiting several surrogate models, implemented in Minamo, the multi-disciplinary optimization platform of Cenaero. Many types of surrogate models are used in the literature with their own forces and weaknesses. More generally, each one models differently a given problem and provides its own representation of the reality. The idea of this paper is to exploit simultaneously different types of surrogate models in order to catch automatically their forces and to outshine some of their weaknesses. This strategy is based on a multi-point enrichment at each iteration, each candidate point being provided by one kind of surrogate model and/or criterion. This strategy can be tuned by selecting different infill criteria, based on different surrogate models, in order to improve more specifically different aspects such as feasibility, exploration and/or exploitation. The performance of this surrogate-based optimization framework is illustrated on well-known constrained benchmark problems available in the literature (such as GX-functions and MOPTA08 test cases). Good performance both in terms of identification of feasible regions and objective gains is demonstrated.
- Published
- 2019
20. A classification-based selection for evolutionary optimization
- Author
-
Jimmy Xiangji Huang, Jinyuan Zhang, and Qinmin Vivian Hu
- Subjects
business.industry ,Computer science ,media_common.quotation_subject ,Evolutionary algorithm ,0102 computer and information sciences ,02 engineering and technology ,Machine learning ,computer.software_genre ,01 natural sciences ,Class (biology) ,010201 computation theory & mathematics ,0202 electrical engineering, electronic engineering, information engineering ,Test suite ,020201 artificial intelligence & image processing ,Quality (business) ,Artificial intelligence ,business ,computer ,Selection (genetic algorithm) ,media_common - Abstract
For evolutionary algorithms (EAs), selection is one of the main components which decides solutions for the new population. Most selection strategies are fitness-based and prodigal in fitness evaluations, since many evaluated solutions are discarded immediately due to their worse values. It is desirable to predict the quality of new solutions without the evaluations before selection, thus the efficiency of EAs can be improved. Naturally selection can be considered as a classification problem: selected solutions belong to the 'good' class and the discarded ones belong to the 'bad' class. This paper demonstrates this idea by introducing a classification-based selection (CBS) strategy for EAs. The CBS is integrated into a state-of-the-art algorithm and studied on a test suite. The experimental results evidence the efficiency of CBS on saving the number of fitness evaluations when compared with the original algorithm.
- Published
- 2019
21. Solving legends of the three kingdoms based on hierarchical macro strategy model
- Author
-
Youjie Zhang, Xiang Ding, and Zhi Chen
- Subjects
Computer science ,ComputingMilieux_PERSONALCOMPUTING ,Perfect information ,0102 computer and information sciences ,02 engineering and technology ,01 natural sciences ,GeneralLiterature_MISCELLANEOUS ,symbols.namesake ,Kingdom ,010201 computation theory & mathematics ,Nash equilibrium ,0202 electrical engineering, electronic engineering, information engineering ,symbols ,020201 artificial intelligence & image processing ,Game based ,Macro ,Mathematical economics - Abstract
Legends of the Three Kingdoms is a Chinese card game based on the novel Romance of the Three Kingdoms. As a turn-based strategy game, Legends of the Three Kingdoms is an imperfect information game where agents interact with one another to deduce the unknown information. The most famous solution for an imperfect information game is to find a Nash equilibrium where no agent can benefit from changing strategies. Tencent AI Lab has recently developed a novel learning-based Hierarchical Macro Strategy model for AI to master MOBA games, a sub-genre of RTS games. In this paper, we adopt this method on our AI to solve Legends of the Three Kingdoms in a shrunken size of 4 players.
- Published
- 2019
22. Genetic programming hyper-heuristic with knowledge transfer for uncertain capacitated arc routing problem
- Author
-
Mazhar Ansari Ardeh, Yi Mei, and Mengjie Zhang
- Subjects
Mathematical optimization ,Computer science ,Process (engineering) ,Genetic programming ,0102 computer and information sciences ,02 engineering and technology ,01 natural sciences ,010201 computation theory & mathematics ,0202 electrical engineering, electronic engineering, information engineering ,020201 artificial intelligence & image processing ,Routing (electronic design automation) ,Hyper-heuristic ,Transfer of learning ,Knowledge transfer ,Arc routing - Abstract
The Uncertain Capacitated Arc Routing Problem (UCARP) is an important combinatorial optimisation problem. Genetic Programming (GP) has shown effectiveness in automatically evolving routing policies to handle the uncertain environment in UCARP. However, when the scenario changes, the current routing policy can no longer work effectively, and one has to retrain a new policy for the new scenario which is time consuming. On the other hand, knowledge from solving the previous similar scenarios may be helpful in improving the efficiency of the retraining process. In this paper, we propose different knowledge transfer methods from a source scenario to a similar target scenario and examine them in different settings. The experimental results showed that by knowledge transfer, the retraining process is made more efficient and the same performance can be obtained within a much shorter time without having any negative transfer.
- Published
- 2019
23. On the use of context sensitive grammars in grammatical evolution for legal non-compliance detection
- Author
-
Erik Hemberg and Carl Im
- Subjects
Grammar ,business.industry ,Computer science ,media_common.quotation_subject ,Context (language use) ,Genetic programming ,0102 computer and information sciences ,02 engineering and technology ,Context-free grammar ,Filter (higher-order function) ,computer.software_genre ,01 natural sciences ,TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES ,Rule-based machine translation ,010201 computation theory & mathematics ,Grammatical evolution ,0202 electrical engineering, electronic engineering, information engineering ,020201 artificial intelligence & image processing ,Artificial intelligence ,business ,computer ,Natural language processing ,media_common - Abstract
We extend the context-free grammar mapping method in the Grammatical Evolution search heuristic. Grammatical Evolution guarantees the generation of transparent and syntactically correct sentences(phenotypes), but not necessarily semantically correct or feasible ones. Generating syntactically valid phenotypes with postprocessing to filter out semantically invalid ones suffers from some issues, e.g. introduction of bias toward short phenotypes and loss in search efficiency. These issues become significant in legal application domains. We first demonstrate that applying Grammatical Evolution with a context free grammar to legal non-compliance detection problems might not be a tenable solution. Then we demonstrate how the addition of context sensitivity improves both the search efficiency and achieves a greater diversity in the case of the iBoB problem regarding legal non-compliance.
- Published
- 2019
24. Identifying solutions of interest for practical many-objective problems using recursive expected marginal utility
- Author
-
Tobias Rodemann, Tapabrata Ray, Markus Olhofer, and Hemant Kumar Singh
- Subjects
Mathematical optimization ,Optimization problem ,Computer science ,Evolutionary algorithm ,0102 computer and information sciences ,02 engineering and technology ,01 natural sciences ,Multi-objective optimization ,010201 computation theory & mathematics ,0202 electrical engineering, electronic engineering, information engineering ,Domain knowledge ,020201 artificial intelligence & image processing ,Marginal utility ,Set (psychology) ,Preference (economics) - Abstract
Real-world problems often involve optimization of multiple conflicting objectives. Significant research has been directed recently towards development of multi-objective evolutionary algorithms that are scalable, i.e., able to deal with problems involving more than 3 objectives, commonly referred to as many-objective optimization problems. This has led to the emergence several new techniques that can deliver a set of trade-off solutions to approximate the Pareto optimal front of the problem. However, means to select solution(s) from this large trade-off set for final implementation/decision making has received relatively scarce attention. This paper aims to study and demonstrate the performance of recursive expected marginal utility (EMUr) approach for informed decisionmaking. Towards this goal, we apply the EMUr approach to identify solutions of interest for two practical examples and analyze the obtained set of solutions. The study highlights the desirable trade-off characteristics that the chosen solutions have over the rest of the trade-off set, highlighting its potential as a decision-making tool, especially in cases where other preference information or domain knowledge is unavailable.
- Published
- 2019
25. Automated design of random dynamic graph models
- Author
-
Chris Rawlings, Aaron Scott Pope, and Daniel R. Tauritz
- Subjects
Random graph ,Theoretical computer science ,010201 computation theory & mathematics ,Computer science ,0202 electrical engineering, electronic engineering, information engineering ,020201 artificial intelligence & image processing ,Genetic programming ,0102 computer and information sciences ,02 engineering and technology ,Heuristics ,01 natural sciences ,Graph - Abstract
Dynamic graphs are an essential tool for representing a wide variety of concepts that change over time. Examples include modeling the evolution of relationships and communities in a social network or tracking the activity of users within an enterprise computer network. In the case of static graph representations, random graph models are often useful for analyzing and predicting the characteristics of a given network. Even though random dynamic graph models are a trending research topic, the field is still relatively unexplored. The selection of available models is limited and manually developing a model for a new application can be difficult and time-consuming. This work leverages hyper-heuristic techniques to automate the design of novel random dynamic graph models. A genetic programming approach is used to evolve custom heuristics that emulate the behavior of a variety of target models with high accuracy. Results are presented that illustrate the potential for the automated design of custom random dynamic graph models.
- Published
- 2019
26. Security testing of web applications
- Author
-
Tao Chen, Ke Li, and Muyang Liu
- Subjects
SQL ,Database ,business.industry ,Computer science ,Search-based software engineering ,0102 computer and information sciences ,02 engineering and technology ,Web application security ,computer.software_genre ,01 natural sciences ,Security testing ,Test case ,System under test ,010201 computation theory & mathematics ,SQL injection ,0202 electrical engineering, electronic engineering, information engineering ,Web application ,020201 artificial intelligence & image processing ,business ,computer ,computer.programming_language - Abstract
Web applications have become increasingly essential in many domains that operate on confidential data related to business. SQL injection attack is one of the most significant web application security risks. Detecting SQL injection vulnerabilities is essential for protecting the underlying web application. However, manually enumerating test cases is extremely challenging, if not impossible, given the potentially infinite number of user inputs and the likely nonexistence of one-to-one mapping between user inputs and malicious SQL statements. This paper proposes an automatic security test case generation approach to detect SQL injection vulnerabilities for web applications, following a search-based software engineering (SBSE) paradigm. Particularly, we propose a novel fitness function that evaluates the similarity between the SQL statements produced by feeding user inputs in the system under test and a known malicious SQL statement. For the search algorithm, we exploit differential evolution, which is robust in continuous optimization but it is under-investigated in SBSE. Based on three real-world web applications, we conduct experiments on 19 configurations that are of diverse forms of SQL statements and types of attacks. Results demonstrate that our approach is more effective, with statistical significance and high effect sizes, than the state-of-the-art.
- Published
- 2019
27. Towards better estimation of statistical significance when comparing evolutionary algorithms
- Author
-
Maxim Buzdalov
- Subjects
Estimation ,business.industry ,Computer science ,Computation ,Evolutionary algorithm ,0102 computer and information sciences ,02 engineering and technology ,Machine learning ,computer.software_genre ,01 natural sciences ,010201 computation theory & mathematics ,0202 electrical engineering, electronic engineering, information engineering ,020201 artificial intelligence & image processing ,Artificial intelligence ,business ,computer - Abstract
The use of well-established statistical testing procedures to compare the performance of evolutionary algorithms often yields pessimistic results. This requires increasing the number of independent samples, and thus the computation time, in order to get results with the necessary precision. We aim at improving this situation by developing statistical tests that are good in answering typical questions coming from benchmarking of evolutionary algorithms. Our first step, presented in this paper, is a procedure that determines whether the performance distributions of two given algorithms are identical for each of the benchmarks. Our experimental study shows that this procedure is able to spot very small differences in the performance of algorithms while requiring computational budgets which are by an order of magnitude smaller (e.g. 15x) compared to the existing approaches.
- Published
- 2019
28. On adaptive specialisation in genetic improvement
- Author
-
Aymeric Blot and Justyna Petke
- Subjects
Focus (computing) ,Class (computer programming) ,Process (engineering) ,business.industry ,Mechanism (biology) ,Computer science ,Search-based software engineering ,0102 computer and information sciences ,02 engineering and technology ,Machine learning ,computer.software_genre ,01 natural sciences ,Software ,010201 computation theory & mathematics ,0202 electrical engineering, electronic engineering, information engineering ,020201 artificial intelligence & image processing ,Artificial intelligence ,business ,computer - Abstract
Genetic improvement uses automated search to find improved versions of existing software. Software can either be evolved with general-purpose intentions or with a focus on a specific application (e.g., to improve it's efficiency for a particular class of problems). Unfortunately, software specialisation to each problem application is generally performed independently, fragmenting and slowing down an already very time-consuming search process. We propose to incorporate specialisation as an online mechanism of the general search process, in an attempt to automatically devise application classes, by benefiting from past execution history.
- Published
- 2019
29. ECJ at 20
- Author
-
Sean Luke and Eric O. Scott
- Subjects
business.industry ,Computer science ,Ant colony optimization algorithms ,Evolutionary algorithm ,Genetic programming ,0102 computer and information sciences ,02 engineering and technology ,01 natural sciences ,Evolutionary computation ,Estimation of distribution algorithm ,010201 computation theory & mathematics ,0202 electrical engineering, electronic engineering, information engineering ,020201 artificial intelligence & image processing ,Software engineering ,business ,Metaheuristic - Abstract
ECJ is now 20 years old. Begun as a genetic programming and evolutionary computation library in Java, it has since established itself as historically one of the most popular EC toolkits worldwide. In 2016 we received a National Science Foundation grant to improve ECJ in many ways with an eye toward making it a useful toolkit not just for EC but for the broader metaheuristics community. This paper is a report on our efforts to this end. We discuss new metaheuristics frameworks and representations added to ECJ and the design challenges that they raise for a general-purpose framework, as well as testing facilities and other support tools. We conclude with our future directions for the library.
- Published
- 2019
30. A memetic algorithm to optimize bus timetable with unequal time intervals
- Author
-
Xinchao Zhao, Pengfei Gao, Xingquan Zuo, and Qiang Bian
- Subjects
Constraint (information theory) ,Matching (statistics) ,Operations research ,010201 computation theory & mathematics ,Computer science ,Metric (mathematics) ,0202 electrical engineering, electronic engineering, information engineering ,Memetic algorithm ,020201 artificial intelligence & image processing ,0102 computer and information sciences ,02 engineering and technology ,Interval (mathematics) ,01 natural sciences - Abstract
An appropriate bus timetable is vital for bus enterprises to improve service quality and save operational cost. Most existing literature on bus timetable optimization divide a whole day into several periods and assume that departure time intervals are the same for each period. As passengers' flow varies over time in a period, giving the same time interval for each period cannot really meet the demand of passengers. In this paper, we study the optimization of bus timetable with unequal time intervals. Aiming at characteristics of this problem, a memetic algorithm is devised that combines a genetic algorithm with elite strategy and a local search. To handle infeasible solutions, a repair method is proposed to repair solutions that do not meet the constraint. A new metric reflecting the degree of bus carrying capability matching passengers' need is introduced. The metric together with passengers' waiting time is used to evaluate a bus timetable. Experiments show that compared to the actually used timetables, timetables optimized by the proposed approach are able to save about 4.54-12.84% cost and 11.87-37.76% passengers' waiting time.
- Published
- 2019
31. A new approach for malware detection based on evolutionary algorithm
- Author
-
Farnoush Manavi and Ali Hamzeh
- Subjects
Class (computer programming) ,Software_OPERATINGSYSTEMS ,Computer science ,Evolutionary algorithm ,0102 computer and information sciences ,02 engineering and technology ,computer.file_format ,computer.software_genre ,01 natural sciences ,010201 computation theory & mathematics ,0202 electrical engineering, electronic engineering, information engineering ,Code (cryptography) ,Malware ,Graph (abstract data type) ,020201 artificial intelligence & image processing ,Data mining ,Executable ,computer - Abstract
Malware is a malicious code which intends to harm computers and networks. Each year, a huge number of malicious programs are released. Therefore, detecting malware has become one of the most important challenges for the security of computer systems. Various methods have been defined for detecting and classifying malware, such as signature-based and heuristic-based techniques. This paper proposes a new malware detection method based on the operational codes (OpCodes) within an executable file by using the evolutionary algorithm. There are several steps in the proposed method, which includes disassembling the executable files, generating a graph of OpCodes and using the evolutionary algorithm to find the most similar graph to each suspicious instance. Finally, the label of each suspicious instance is detected based on the most similar graph obtained from the evolutionary algorithm with each class (family of malware and benign). The results show that, the proposed method can be used as a method for malware detection and malware category.
- Published
- 2019
32. Gaussian process surrogate models for the CMA-ES
- Author
-
Jakub Repický, Lukas Bajer, Zbyněk Pitra, and Martin Holeňa
- Subjects
Continuous optimization ,Computer science ,0102 computer and information sciences ,02 engineering and technology ,01 natural sciences ,symbols.namesake ,Surrogate model ,010201 computation theory & mathematics ,0202 electrical engineering, electronic engineering, information engineering ,symbols ,020201 artificial intelligence & image processing ,CMA-ES ,Evolution strategy ,Gaussian process ,Algorithm ,Selection (genetic algorithm) - Abstract
This extended abstract previews the usage of Gaussian processes in a surrogate-model version of the CMA-ES, a state-of-the-art black-box continuous optimization algorithm. The proposed algorithm DTS-CMA-ES exploits the benefits of Gaussian process uncertainty prediction, especially during the selection of points for the evaluation with the surrogate model. Very brief results are presented here, while much more elaborate description of the methods, parameter settings and detailed experimental results can be found in the original article Gaussian Process Surrogate Models for the CMA Evolution Strategy [2], to appear in the Evolutionary Computation1.
- Published
- 2019
33. Immune and genetic hybrid optimization algorithm for data relay satellite with microwave and laser links
- Author
-
Yinghui Xue, Cheng Dong, Wei Li, Weihu Zhao, Shuwen Chen, Guijin Xia, Xiya Chen, and Shuai Ren
- Subjects
Computer science ,Distributed computing ,0102 computer and information sciences ,02 engineering and technology ,01 natural sciences ,Tabu search ,law.invention ,Scheduling (computing) ,010201 computation theory & mathematics ,Relay ,law ,Genetic algorithm ,0202 electrical engineering, electronic engineering, information engineering ,Programming paradigm ,Information system ,020201 artificial intelligence & image processing ,Global optimization ,Constraint satisfaction problem - Abstract
Aiming at the problem of oversubscription of data relay access request of user stars in future Space-Based Information System, the problem of resource scheduling optimization for data relay satellite system with microwave and laser hybrid links is studied. The characteristics of the hybrid links are analyzed. A multi-objective programming model on static resource scheduling constraint satisfaction problem is established, and a hybrid optimization algorithm integration of artificial immune strategies, niche ideas and improved genetic algorithm is put forward to solve the scheduling model. Simulation results show that the hybrid optimization algorithm optimizes the model quickly, and performs well in the ability of global optimization and convergence. The results validate that the static resource scheduling model could accurately describe the microwave and laser hybrid links relay satellite system resource scheduling problem with multi-tasking and multi-type antenna1.
- Published
- 2019
34. CE+EPSO
- Author
-
Leonel M. Carvalho, Carlos E. Pedreira, Vladimiro Miranda, Armando M. Leite da Silva, Carolina G. Marcelino, and Elizabeth F. Wanner
- Subjects
Mathematical optimization ,Computer science ,Particle swarm optimization ,0102 computer and information sciences ,02 engineering and technology ,01 natural sciences ,Power flow ,Cross entropy ,010201 computation theory & mathematics ,0202 electrical engineering, electronic engineering, information engineering ,020201 artificial intelligence & image processing ,CMA-ES ,Evolution strategy ,Global optimization problem - Abstract
This work discusses the solution of a Large-scale global optimization problem named Security Constrained Optimal Power Flow (SCOPF) using a method based on Cross Entropy (CE) and Evolutionary Particle Swarm Optimization (EPSO). The obtained solution is compared to the Entropy Enhanced Covariance Matrix Adaptation Evolution Strategy (EE-CMAES) and Shrinking Net Algorithm (SNA). Experiments show the approach reaches competitive results.
- Published
- 2019
35. A new neighborhood topology for QUAntum particle swarm optimization (QUAPSO)
- Author
-
Hamouche Oulhadj, Patrick Siarry, and Arnaud Flori
- Subjects
business.industry ,Computer science ,Gaussian ,Computer Science::Neural and Evolutionary Computation ,Quantum superposition ,MathematicsofComputing_NUMERICALANALYSIS ,Particle swarm optimization ,Swarm behaviour ,0102 computer and information sciences ,02 engineering and technology ,01 natural sciences ,Swarm intelligence ,symbols.namesake ,010201 computation theory & mathematics ,Simulated annealing ,0202 electrical engineering, electronic engineering, information engineering ,symbols ,020201 artificial intelligence & image processing ,Local search (optimization) ,business ,Algorithm ,Bat algorithm - Abstract
Swarm Intelligence (SI) is a behavior, used first by Beni and Wang, corresponding to a system working with single and self-organized agents, interacting the ones with each other. This operating concept is implemented in many algorithms. Developed by Kennedy, Eberhart and Shi, Particle Swarm Optimization (PSO) is one of them. Its behavior is based on the movements of birds swarm, and its effectiveness, for looking for the optimal solution of a given problem, is well established. Nevertheless, PSO is known for its weakness in local search. Moreover, the behavior of PSO strongly depends on internal parameters settings. In order to address these problems, we propose a new type of self-adaptive Quantum PSO (QPSO), called QUAntum Particle Swarm Optimization (QUAPSO), based on quantum superposition to set the velocity parameters and hybridized with a Kangaroo Algorithm in order to optimize its efficiency in local search. QUAPSO was compared with five known algorithms from the literature (classical PSO, Kangaroo Algorithm, Simulated Annealing Particle Swarm Optimization, Bat Algorithm and Simulated Annealing Gaussian Bat Algorithm) on a set of 19 test functions. The results show that QUAPSO outperforms the competing algorithms.
- Published
- 2019
36. Toward self-learning model-based EAs
- Author
-
Erik A. Meulman, Peter A. N. Bosman, and Radiotherapy
- Subjects
Class (computer programming) ,Optimization problem ,business.industry ,Computer science ,Evolutionary algorithm ,0102 computer and information sciences ,02 engineering and technology ,01 natural sciences ,Field (computer science) ,Estimation of distribution algorithm ,010201 computation theory & mathematics ,Black-box optimization ,Machine learning ,Reinforcement learning ,Specialization (logic) ,0202 electrical engineering, electronic engineering, information engineering ,020201 artificial intelligence & image processing ,Artificial intelligence ,business ,Estimation of distribution algorithms - Abstract
Model-based evolutionary algorithms (MBEAs) are praised for their broad applicability to black-box optimization problems. In practical applications however, they are mostly used to repeatedly optimize different instances of a single problem class, a setting in which specialized algorithms generally perform better. In this paper, we introduce the concept of a new type of MBEA that can automatically specialize its behavior to a given problem class using tabula rasa self-learning. For this, reinforcement learning is a naturally fitting paradigm. A proof-of-principle framework, called SL-ENDA, based on estimation of normal distribution algorithms in combination with reinforcement learning is defined. SL-ENDA uses an RL-agent to decide upon the next population mean while approaching the rest of the algorithm as the environment. A comparison of SL-ENDA to AMaLGaM and CMA-ES on unimodal noiseless functions shows mostly comparable performance and scalability to the broadly used and carefully manually crafted algorithms. This result, in combination with the inherent potential of self-learning model-based evolutionary algorithms with regard to specialization, opens the door to a new research direction with great potential impact on the field of model-based evolutionary algorithms.
- Published
- 2019
37. Stochastic program synthesis via recursion schemes
- Author
-
Krzysztof Krawiec, Jerry Swan, and Zoltan A. Kocsis
- Subjects
Recursion ,Theoretical computer science ,Computer science ,Structure (category theory) ,0102 computer and information sciences ,02 engineering and technology ,01 natural sciences ,Random search ,010201 computation theory & mathematics ,0202 electrical engineering, electronic engineering, information engineering ,Benchmark (computing) ,Algebraic data type ,020201 artificial intelligence & image processing ,Pattern matching ,Program synthesis - Abstract
Stochastic synthesis of recursive functions has historically proved difficult, not least due to issues of non-termination and the often ad hoc methods for addressing this. We propose a general method of implicit recursion which operates via an automatically-derivable decomposition of datatype structure by cases, thereby ensuring well-foundedness. The method is applied to recursive functions of long-standing interest and the results outperform recent work which combines two leading approaches and employs 'human in the loop' to define the recursion structure. We show that stochastic synthesis with the proposed method on benchmark functions is effective even with random search, motivating a need for more difficult recursive benchmarks in future. This paper summarizes work that appeared in [1].
- Published
- 2019
38. Towards solving neural networks with optimization trajectory search
- Author
-
Lia T. Parsenadze, Danilo Vasconcellos Vargas, and Toshiyuki Fujita
- Subjects
Mathematical optimization ,Artificial neural network ,Contextual image classification ,Computer science ,Work (physics) ,Evolutionary algorithm ,0102 computer and information sciences ,02 engineering and technology ,Parameter space ,01 natural sciences ,Evolutionary computation ,010201 computation theory & mathematics ,Path (graph theory) ,0202 electrical engineering, electronic engineering, information engineering ,Trajectory ,020201 artificial intelligence & image processing - Abstract
Modern gradient based optimization methods for deep neural networks demonstrate outstanding results on image classification tasks. However, methods that do not rely on gradient feedback fail to tackle deep network optimization. In the held of evolutionary computation, applying evolutionary algorithms directly to network weights remains to be an unresolved challenge. In this paper we examine a new framework for the evolution of deep nets. Based on the empirical analysis, we propose the use of linear sub-spaces of problems to search for promising optimization trajectories in parameter space, opposed to weight evolution. We show that linear sub-spaces of loss functions are sufficiently well-behaved to allow trajectory evaluation. Furthermore, we introduce fitness measure to show that it is possible to correctly categorize trajectories according to their distance from the optimal path. As such, this work introduces an alternative approach to evolutionary optimization of deep networks.
- Published
- 2019
39. A tabu search-based memetic algorithm for the multi-objective flexible job shop scheduling problem
- Author
-
Michael Emmerich, Steffen Limmer, Asteris Apostolidis, Markus Olhofer, Thomas Bäck, and Marios Kefalas
- Subjects
Mathematical optimization ,Job shop scheduling ,Computer science ,business.industry ,Pareto principle ,Novelty ,Workload ,0102 computer and information sciences ,02 engineering and technology ,01 natural sciences ,Multi-objective optimization ,Tabu search ,Scheduling (computing) ,010201 computation theory & mathematics ,Genetic algorithm ,0202 electrical engineering, electronic engineering, information engineering ,Memetic algorithm ,020201 artificial intelligence & image processing ,Local search (optimization) ,business - Abstract
In this paper we propose a tabu search-based memetic algorithm (TSM) for the multi-objective flexible job shop scheduling problem (FJSSP), with the objectives to minimize the makespan, the total workload and the critical workload. The problem is addressed in a Pareto manner, which targets a set of Pareto optimal solutions. The novelty of our method lies in the use of tabu search (TS) as the local search method as well as a mutation operator and the use of the hypervolume indicator to avoid stagnation by increasing the flow of individuals in the local search. To the best of our knowledge, the use of TS in the context of multi-objective FJSSP has not been reported so far. We apply our algorithm on well known test instances and compare our results to state-of-the art algorithms. The results show that our approach yields competitive solutions in 6 of the 10 instances against two of their algorithms proving that the use of TS as a local search method can provide competitive results.
- Published
- 2019
40. A parametric investigation of PBI and AASF scalarizations
- Author
-
Kalyanmoy Deb and Hemant Kumar Singh
- Subjects
Mathematical optimization ,Computer science ,Intersection (set theory) ,Boundary (topology) ,0102 computer and information sciences ,02 engineering and technology ,Function (mathematics) ,Multiple-criteria decision analysis ,01 natural sciences ,Field (computer science) ,Range (mathematics) ,010201 computation theory & mathematics ,0202 electrical engineering, electronic engineering, information engineering ,020201 artificial intelligence & image processing ,Equivalence (measure theory) ,Parametric statistics - Abstract
Multi-objective problems (MOP) are of significant interest to both multi-criteria decision making (MCDM) and evolutionary multi-objective (EMO) research communities. A core technique common in both is scalarization, which combines multiple objectives into one in a way that solving it provides a solution to the original MOP. In this paper, we look closely at two scalarization methods --- augmented achievement scalarization function (AASF) and penalty boundary intersection (PBI). While the former has its roots in MCDM literature, the latter was developed in EMO field with focus on decomposition-based algorithms. We observe the conventional limits of the parameters involved in these methods and then demonstrate that by relaxing those limits one could be made to behave like the other. The aim is to gain a deeper understanding of both these measures, as well as expand their parametric range to provide more control over the search behavior of EMO algorithms. It also lays groundwork for further development of complete analytical derivations of equivalence conditions between the two metrics.
- Published
- 2019
41. Multidimensional time series feature engineering by hybrid evolutionary approach
- Author
-
Krzysztof Michalak and Piotr Lipinski
- Subjects
Feature engineering ,Series (mathematics) ,Computer science ,Evolutionary algorithm ,0102 computer and information sciences ,02 engineering and technology ,computer.software_genre ,01 natural sciences ,010201 computation theory & mathematics ,Stock exchange ,0202 electrical engineering, electronic engineering, information engineering ,020201 artificial intelligence & image processing ,Data mining ,computer - Abstract
This paper proposes a hybrid evolutionary approach to feature engineering for mining frequent patterns from multidimensional financial ultra-high frequency time series. Experiments performed on real-world data from the London Stock Exchange Rebuilt Order Book database confirms that the evolutionary algorithm is capable of improving significantly the results of classification.
- Published
- 2019
42. Genetic improvement of data gives binary logarithm from sqrt
- Author
-
William B. Langdon and Justyna Petke
- Subjects
Floating point ,Computer science ,MathematicsofComputing_NUMERICALANALYSIS ,Double-precision floating-point format ,0102 computer and information sciences ,02 engineering and technology ,Binary logarithm ,01 natural sciences ,Square root ,010201 computation theory & mathematics ,0202 electrical engineering, electronic engineering, information engineering ,Code (cryptography) ,020201 artificial intelligence & image processing ,Algorithm - Abstract
Automated search in the form of the Covariance Matrix Adaptation Evolution Strategy (CMA-ES), plus manual code changes, transforms 512 Newton-Raphson floating point start numbers from an open source GNU C library, glibc, table driven square root function to create a new bespoke custom mathematical implementation of double precision binary logarithm log2 for C in seconds.
- Published
- 2019
43. Openly revisiting derivative-free optimization
- Author
-
Camille Couprie, Jeremy Rapin, Pauline Dorval, Olivier Teytaud, Jules Pondard, Nicolas Vasilache, and Marie-Liesse Cauwet
- Subjects
Mathematical optimization ,Computer science ,Crossover ,Context (language use) ,0102 computer and information sciences ,02 engineering and technology ,01 natural sciences ,Separable space ,Range (mathematics) ,010201 computation theory & mathematics ,Differential evolution ,Derivative-free optimization ,0202 electrical engineering, electronic engineering, information engineering ,Test functions for optimization ,020201 artificial intelligence & image processing ,State (computer science) - Abstract
This paper surveys and compares a wide range of derivative-free optimization algorithms in an open source context. We also propose a genetic variant of differential evolution, an adaptation of population control for the multimodal noise-free case, new multiscale deceptive functions, and as a contribution to the debate on genetic crossovers, a test function with useless variables on which 2-points crossover achieves great performance. We include discrete and continuous and mixed settings; sequential and parallel optimization; rotated, separable and partially rotated settings; noisy and noise-free setting. We include real world applications and compare with recent optimizers which have not yet been extensively compared to the state of the art.
- Published
- 2019
44. Impact of subcircuit selection on the efficiency of CGP-based optimization of gate-level circuits
- Author
-
Jitka Kocnova and Zdenek Vasicek
- Subjects
Combinational logic ,Computer science ,Computation ,0102 computer and information sciences ,02 engineering and technology ,Formal methods ,01 natural sciences ,Reduction (complexity) ,Logic synthesis ,Computer engineering ,010201 computation theory & mathematics ,Logic gate ,Scalability ,0202 electrical engineering, electronic engineering, information engineering ,020201 artificial intelligence & image processing ,Circuit complexity ,Hardware_LOGICDESIGN ,Electronic circuit - Abstract
Various EA-based methods have been applied to design and optimize logic circuits since the early nineties. The unconventional methods, however, typically suffer from various scalability issues preventing them to be adopted in practice. Recent improvement in the fitness computation procedure connected with the introduction of formal methods in the fitness evaluation such as SAT solvers or BDDs enabled pushing of the limits forward and approaching the complexity of industrial problems. It was demonstrated that EAs can be applied to optimize gate-level circuits consisting of thousands of gates without introducing any decomposition technique. Despite that, the efficiency decreases with increasing the circuit complexity. This problem can be managed by adopting the concept of the so-called iterative resynthesis based on the extraction of smaller sub-circuits from a complex circuit, their local optimization followed by the implantation back to the original circuit. Recently, a method based on the computation of so-called cuts was proposed. In this paper, we propose an alternative approach which is able to select more complex sub-graphs consisting of more nodes and more inputs. Compared to the previous method, the proposed approach allows to improve the efficiency of the optimization. More than 9% and 20% reduction was observed on the highly optimized logic and arithmetic circuits, respectively.
- Published
- 2019
45. Benchmarking the region learning-based JADE on noiseless functions
- Author
-
Guangming Dai, Mingcheng Zuo, Lei Peng, Maocai Wang, Pan Peng, and Changchun Chen
- Subjects
education.field_of_study ,Optimization problem ,business.industry ,Computer science ,Population ,0102 computer and information sciences ,02 engineering and technology ,Benchmarking ,Machine learning ,computer.software_genre ,01 natural sciences ,JADE (particle detector) ,010201 computation theory & mathematics ,0202 electrical engineering, electronic engineering, information engineering ,020201 artificial intelligence & image processing ,Learning based ,Artificial intelligence ,business ,education ,computer - Abstract
This paper proposes a region-learning based JADE algorithm, namely RL-JADE, to solve numerical optimization problems. To exploit as much as possible the most promising areas known by the current population, the worst parts of population are eliminated, and some new individuals are regenerated in the area where the best parts of population locate. RL-JADE is tested based on COCO benchmarks, and compared with other DE-variants. Experimental results show that RL-JADE has a better performance than JADE on the tested 5-D problems.
- Published
- 2019
46. Feature selection for surrogate model-based optimization
- Author
-
Frederik Rehbach, Thomas Bartz-Beielstein, and Lorenzo Gentile
- Subjects
Mathematical optimization ,Computer science ,Dimensionality reduction ,Feature selection ,0102 computer and information sciences ,02 engineering and technology ,01 natural sciences ,Regularization (mathematics) ,Surrogate model ,Lasso (statistics) ,010201 computation theory & mathematics ,Kriging ,0202 electrical engineering, electronic engineering, information engineering ,020201 artificial intelligence & image processing ,ddc:004 ,Fakultät für Informatik und Ingenieurwissenschaften (F10) ,Shrinkage - Abstract
We propose a hybridization approach called Regularized-Surrogate- Optimization (RSO) aimed at overcoming difficulties related to high- dimensionality. It combines standard Kriging-based SMBO with regularization techniques. The employed regularization methods use the least absolute shrinkage and selection operator (LASSO). An extensive study is performed on a set of artificial test functions and two real-world applications: the electrostatic precipitator problem and a multilayered composite design problem. Experiments reveal that RSO requires significantly less time than Kriging to obtain comparable results. The pros and cons of the RSO approach are discussed and recommendations for practitioners are presented.
- Published
- 2019
47. Transfer learning
- Author
-
Brandon Muller, Mengjie Zhang, Harith Al-Sahaf, and Bing Xue
- Subjects
education.field_of_study ,Computer science ,business.industry ,Population ,Genetic programming ,0102 computer and information sciences ,02 engineering and technology ,Machine learning ,computer.software_genre ,01 natural sciences ,Domain (software engineering) ,010201 computation theory & mathematics ,Block (programming) ,0202 electrical engineering, electronic engineering, information engineering ,020201 artificial intelligence & image processing ,Artificial intelligence ,Symbolic regression ,education ,business ,Transfer of learning ,computer ,Selection (genetic algorithm) - Abstract
In machine learning, transfer learning is concerned with utilising prior knowledge as a way to improve the process of training a new model in a different, but related, domain. Transfer learning has been shown to be beneficial across a large set of problems. One of the main questions any transfer learning approach must address is "What to transfer?". This paper proposes a new transfer learning method in genetic programming (GP) to improve solving symbolic regression problems by extracting all potentially good and unique building blocks from a source problem. The proposed method is compared against standard GP and a state-of-the-art GP method on ten regression datasets. The experimental results show that the proposed method has achieved significantly better or comparable performance to that of the competitive methods. Furthermore, the proposed method shows better initial population and convergence compared to the other methods.
- Published
- 2019
48. A parallel multi-population biased random-key genetic algorithm for electric distribution network reconfiguration
- Author
-
Holger Voos, Willian Tessaro Lunardi, and Haroldo de Faria
- Subjects
Computer science [C05] [Engineering, computing & technology] ,Genetic Algorithm ,Optimization problem ,Uniform distribution (continuous) ,Computer science ,Parallel algorithm ,Control reconfiguration ,Graph theory ,Metaheuristics ,0102 computer and information sciences ,02 engineering and technology ,Load balancing (computing) ,Sciences informatiques [C05] [Ingénierie, informatique & technologie] ,01 natural sciences ,Electric distribution network ,Network planning and design ,Parallel Computing ,010201 computation theory & mathematics ,Combinatorial Optimization ,Genetic algorithm ,0202 electrical engineering, electronic engineering, information engineering ,Combinatorial optimization ,020201 artificial intelligence & image processing ,Algorithm ,Metaheuristic - Abstract
This work presents a multi-population biased random-key genetic algorithm (BRKGA) for the electric distribution network reconfiguration problem (DNR). DNR belongs to the class of network design problems which include transportation problems, computer network restoration and telecommunication network design and can be used for loss minimization and load balancing, being an important tool for distribution network operators. A BRKGA is a class of genetic algorithms in which solutions are encoded as vectors of random keys, i.e. randomly generated real numbers from a uniform distribution in the interval [0, 1). A vector of random keys is translated into a solution of the optimization problem by a decoder. The decoder used generates only feasible solutions by using an efficient codification based upon the fundamentals of graph theory, restricting the search space. The parallelization is based on the single program multiple data paradigm and is executed on the cores of a multi-core processor. Time to target plots, which characterize the running times of stochastic algorithms for combinatorial optimization, are used to compare the performance of the serial and parallel algorithms. The proposed method has been tested on two standard distribution systems and the results show the effectiveness and performance of the parallel algorithm.
- Published
- 2019
49. Performance of dynamic algorithms on the dynamic distance minimization problem
- Author
-
Sanaz Mostaghim, Mahrokh Javadi, Heiner Zille, and Mardé Heibig
- Subjects
Optimization problem ,Computer science ,Work (physics) ,Pareto principle ,0102 computer and information sciences ,02 engineering and technology ,01 natural sciences ,Multi-objective optimization ,Euclidean distance ,Dynamic problem ,010201 computation theory & mathematics ,Metaheuristic algorithms ,Euclidean geometry ,Metric (mathematics) ,0202 electrical engineering, electronic engineering, information engineering ,Benchmark (computing) ,020201 artificial intelligence & image processing ,Algorithm - Abstract
In the area of multi-objective optimization, a special challenge is dynamic optimization problems. These problems change their optimal values or optimal configurations of input variables over time, making it harder for metaheuristic algorithms to track these changes and find the new optima. To test the search ability of such dynamic multi-objective algorithms, a dynamic benchmark called the Dynamic Distance Minimization Problem (dDMP) was proposed in the literature. The dDMP implements multiple changes, not only in location and fitness values of the Pareto-optimal sets, but also in the complexity of the problem. This work aims to test the performance of two well-known dynamic multi-objective algorithms on different instances of the dDMP with varying complexity. This involves changes in the number of objectives and changes of the distance metric at runtime, which has not been done before with this problem in the literature. The results show that both algorithms struggled to recover after the number of objectives was reduced and then increased again. When the distance metric was changed over time both algorithms performed reasonable well. However, there were gaps in the found Pareto fronts when switching between the Euclidean and the Manhattan distance metrics.
- Published
- 2019
50. Graph-based multi-objective generation of customised wiring harnesses
- Author
-
Steven Benkhardt, Sanaz Mostaghim, and Jens Weise
- Subjects
Structure (mathematical logic) ,Computer science ,Crossover ,Evolutionary algorithm ,0102 computer and information sciences ,02 engineering and technology ,Object (computer science) ,01 natural sciences ,Graph ,Computer engineering ,010201 computation theory & mathematics ,Path (graph theory) ,0202 electrical engineering, electronic engineering, information engineering ,Graph (abstract data type) ,020201 artificial intelligence & image processing ,Motion planning - Abstract
Electrical wires are a very important part of a vehicle as well of many other objects with electrical functions. These wires are summed up to harnesses. Engineers often manually create the virtual paths for wires by considering their expert knowledge. More variants of a product often require different wires and the criteria for cables do vary. Criteria, e.g. heat or the length, define the wire path and configuration and have to be taken into account. Engineers may not be able to consider all criteria, notably when there is an extensive amount of product variants, or when the object configuration is changing. This paper will evaluate if a multi-objective evolutionary algorithm can compute feasible wire paths where two of these criteria are optimised. We are showing that discretised free-space in a graph structure enables an evolutionary algorithm to compute wire suggestions by using customised reproduction operators for path planning. The developed crossover and mutation operators are suitable for multi-objective path finding, may be used in other fields as well and will be extended in future research.
- Published
- 2019
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.