The notion and characterisation of fitness landscapes has helped us understand the performance of heuristic algorithms on complex optimisation problems. Many practical problems, however, are constrained, and when significant areas of the search space are infeasible, researchers have intuitively resorted to a variety of constraint-handling techniques intended to help the algorithm manoeuvre through infeasible areas and toward feasible regions of better fitness. It is clear that providing constraint-related feedback to the algorithm to influence its choice of solutions overlays the violation landscape with the fitness landscape in unpredictable ways whose effects on the algorithm cannot be directly measured. In this work, we apply metrics of violation landscapes to continuous and combinatorial problems to characterise them. We relate this information to the relative performance of six well-known constraint-handling techniques to demonstrate how some properties of constrained landscapes favour particular constraint-handling approaches. For the problems with sampled feasible solutions, a bi-objective approach was the best performing approach overall, but other techniques performed better on problems with the most disjoint feasible areas. For the problems with no measurable feasibility, a feasibility ranking approach was the best performing approach overall, but other techniques performed better when the correlation between fitness values and the level of constraint violation was high.

Finding communities in networks has become very important because various social and physical complex systems are represented as networks. Because of their ability to address large networks, local community detection methods that start from a seed node have become the focus of many research endeavours in recent times. In this paper, a derivative-based local community detection method, inspired by active contours, is proposed for finding a community surrounding an initial seed. The method is based on the concepts of curvature and gradient of the current communitys boundary. Curvature and gradient comprise the velocity function used to determine whether the boundary should move to include a candidate node in its vicinity. Unlike Euclidean space, networks have non-uniform space with fluctuations of dimensionality, given by the fluctuation in degrees of nodes, which complicates the calculation of derivatives used to define the curvature and gradient of boundary nodes. In this research, with some intuitive imagination, a framework for approximating derivatives in network space is proposed. Benchmarking this community detection method against three contemporary methods shows that it is capable of building communities with equal or better conductance.

Recommender systems play an important role in today's electronic markets due to the large benefits they bring by helping businesses understand their customers' needs and preferences. The major preference components modelled by current recommender systems include user and item biases, feature value preferences, conditional dependencies, temporal preference drifts, and social influence on preferences. In this paper, we introduce a new hybrid latent factor model that achieves great accuracy by integrating all these preference components in a unified model efficiently. The proposed model employs gradient descent to optimise the model parameters, and an evolutionary algorithm to optimise the hyper-parameters and gradient descent learning rates. Using two popular datasets, we investigate the interaction effects of the preference components with each other.We conclude that depending on the dataset, different interactions exist between the preference components. Therefore, understanding these interaction effects is crucial in designing an accurate preference model in every preference dataset and domain.Our results show that on both datasets, different combinations of components result in different accuracies of recommendation, suggesting that some parts of the model interact strongly. Moreover, these effects are highly dataset-dependent, suggesting the need for exploring these effects before choosing the appropriate combination of components.

Summary Private Cloud provides Cloud services with its relatively limited resources compared to public Clouds. Resources in private Clouds should be used energy efficiently. The resource utilization is determined by the assignment of virtual machines (VMs) to hosts. Because of the frequent changes in the resource requests on VMs, the system might become imbalanced, some hosts are overloaded/underloaded. Virtual machine migration is a solution to ease the imbalance problem. Virtual machine migration includes the selection of a VM for migration and decision upon where it should be taken to (mapped). In this work, VM selection and VM mapping are integrated and aimed to ease the imbalance problem for energy efficiency. Moreover, selection and mapping have become adaptive to ease imbalance, while optimizing energy consumption and adaptively responding to changes in the system. Our proposed adaptive mechanism applies Bayesian inference to estimate the likelihood of a VM migration decision, both VM selection for migration and VM mapping, optimizing energy consumption. The proposed mechanism is evaluated on CloudSim using PlanetLab workload on a heterogeneous Cloud. It is demonstrated to reduce energy consumption significantly, (on average) by 116%, while its total execution time is also, (on average) 5.39 times, shorter than the competing state‐of‐the‐art policies.

Complex combinatorial problems are most often optimised with heuristic solvers, which usually deliver acceptable results without any indication of the quality obtained. Recently, predictive diagnostic optimisation was proposed as a means of characterising the fitness landscape while optimising a combinatorial problem. The scalars produced by predictive diagnostic optimisation appear to describe the difficulty of the problem with relative reliability. In this study, we record more scalars that may be helpful in determining problem difficulty during the optimisation process and analyse these in combination with other well-known landscape descriptors by using exploratory factor analysis on four landscapes that arise from different search operators, applied to a varied set of quadratic assignment problem instances. Factors are designed to capture properties by combining the collinear variances of several variables. The extracted factors can be interpreted as the features of landscapes detected by the variables, but disappoint in their weak correlations with the result quality achieved by the optimiser, which we regard as the most reliable indicator of difficulty available. It appears that only the prediction error of predictive diagnostic optimisation has a strong correlation with the quality of the results produced, followed by a medium correlation of the fitness distance correlation of the local optima.

The automation of software architecture design is an important goal in software engineering. A plethora of automated design exploration techniques have been devised in the last decades to handle the complexity of making design decision in large scale, complex software systems. The common aim of these methods is the optimisation of quality attributes, such as reliability and safety. The majority of approaches use heuristic methods, such as local search or genetic algorithms, which use gradients in the fitness space to guide the search to the local optimum. When problems are constrained, search gradients are disrupted by infeasible regions, which may have a great impact on the difficulty of solving optimisation problems. Discovering the conditions under which a search heuristic will succeed or fail is critical for understanding the strengths and weaknesses of different software architecture optimisation methods. This paper investigates how to adequately characterize the features of constrained problem instances that have impact on difficulty in terms of algorithmic performance, and how such features can be defined and measured for the component deployment optimisation problem. We employ fitness landscape characterisation metrics that measure uniformity of the gradients in the search space, and investigate how two different constraints shape the search space, and as a result affect the performance of software architecture optimisation approaches.

All commonly used stochastic optimisation algorithms have to be parameterised to perform effectively. Adaptive parameter control (APC) is an effective method used for this purpose. APC repeatedly adjusts parameter values during the optimisation process for optimal algorithm performance. The assignment of parameter values for a given iteration is based on previously measured performance. In recent research, time series prediction has been proposed as a method of projecting the probabilities to use for parameter value selection. In this work, we examine the suitability of a variety of prediction methods for the projection of future parameter performance based on previous data. All considered prediction methods have assumptions the time series data has to conform to for the prediction method to provide accurate projections. Looking specifically at parameters of evolutionary algorithms (EAs), we find that all standard EA parameters with the exception of population size conform largely to the assumptions made by the considered prediction methods. Evaluating the performance of these prediction methods, we find that linear regression provides the best results by a very small and statistically insignificant margin. Regardless of the prediction method, predictive parameter control outperforms state of the art parameter control methods when the performance data adheres to the assumptions made by the prediction method. When a parameter's performance data does not adhere to the assumptions made by the forecasting method, the use of prediction does not have a notable adverse impact on the algorithm's performance.

The performance of an Evolutionary Algorithm (EA) is greatly affected by the settings of its strategy parameters. An effective solution to the parameterisation problem is adaptive parameter control, which applies learning methods that use feedback from the optimisation process to evaluate the effect of parameter value choices and adjust the parameter values over the iterations. At every iteration of an EA, the performance of an EA is reported and employed by the feedback mechanism as an indication of the success of the parameterisation of the algorithm instance. Many approaches to collect information about the algorithm's performance exist in single objective optimisation. In this work, we review the most recent and prominent approaches. In multiobjective optimisation, establishing a single scalar which can report the algorithm's performance as feedback for adaptive parameter control is a complex task. Existing performance measures of multiobjective optimisation are generally used as feedback for the optimisation process. We discuss the properties of these measures and present an empirical evaluation of the binary hypervolume and ϵ+-indicators as feedback for adaptive parameter control.

Stochastic optimisers such as Evolutionary Algorithms, Estimation of Distribution Algorithm are suitable methods when problems are highly complex and deterministic algorithms cannot be expected to produce acceptable results. Generally, when the search process produces the optimised solutions, there is no indication how successful the search has been. In previous work, we introduced Predictive Diagnostic Optimisation (PDO), a local-search-based solver which can predict with certain accuracy the quality of local optima and that can help decide which of the initial solutions is appropriate to optimise. The neighbourhood created by the swap operator was used in exploration of the search space and the number of predictors created is a metric for the homogeneity of the landscape. The advantage of PDO is that it provides information regarding the difficulty of the search landscape alongside the optimisation results. In this work we extend PDO by employing three more neighbourhood operators to allow a comparison between the performances of different types of local search. Each neighbourhood operator has its own group of predictors and the difficulty in predicting the local optima is quantified by a new metric, the prediction error. To provide an assessment of the characterisation ability for the algorithm, a set of landscapes with various degrees of difficulty has been designed by manipulating the matrices of the test problems instances. We show that the metric is able to identify the degree of difficulty that we expect the landscapes to pose for the employed local search operators.

Evolutionary Algorithms are equipped with a range of adjustable parameters, such as crossover and mutation rates which significantly influence the performance of the algorithm. Practitioners usually do not have the knowledge and time to investigate the ideal parameter values before the optimisation process. Furthermore, different parameter values may be optimal for different problems, and even problem instances. In this work, we present a parameter control method which adjusts parameter values during the optimisation process using the algorithm's performance as feedback. The approach is particularly effective with continuous parameter intervals, which are adapted dynamically. Successful parameter ranges are identified using an entropy-based clusterer, a method which outperforms state-of-the-art parameter control algorithms.

Particle Swarm Optimization (PSO) is a popular algorithm used extensively in continuous optimization. One of its well-known drawbacks is its propensity for premature convergence. Many techniques have been proposed for alleviating this problem. One of the alternative approaches is hybridization. Genetic Algorithms (GA) are one of the possible techniques used for hybridization. Most often, a mutation scheme is added to the PSO, but some applications of crossover have been added more recently. Some of these schemes use adaptive parameterization when applying the GA operators. In this work, adaptively parameterized mutation and crossover operators are combined with a PSO implementation individually and in combination to test the effectiveness of these additions. The results indicate that an adaptive approach with position factor is more effective for the proposed PSO hybrids. Compared to single PSO with adaptive inertia weight, all the PSO hybrids with adaptive probability have shown satisfactory performance in generating near-optimal solutions for all tested functions.

All existing stochastic optimisers such as Evolutionary Algorithms require parameterisation which has a significant influence on the algorithm's performance. In most cases, practitioners assign static values to variables after an initial tuning phase. This parameter tuning method requires experience the practitioner may not have and, when done conscientiously, is rather time-consuming. Also, the use of parameter values that remain constant over the optimisation process has been observed to achieve suboptimal results. This work presents a parameter control method which redefines variables repeatedly based on a separate optimisation process which receives its feedback from the primary optimisation algorithm. The feedback is used for a projection of the value performing well in the future. The parameter values are sampled from intervals which are adapted dynamically, a method which has proved particularly effective and outperforms all existing adaptive parameter controls significantly.

Stochastic optimisers such as Evolutionary Algorithms outperform random search due to their ability to exploit gradients in the search landscape, formed by the algorithm's search operators in combination with the objective function. Research into the suitability of algorithmic approaches to problems has been made more tangible by the direct study and characterisation of the underlying fitness landscapes. Authors have devised metrics, such as the autocorrelation length, to help define these landscapes. In this work, we contribute the Predictive Diagnostic Optimisation method, a new local-search-based algorithm which provides knowledge about the search space while it searches for the global optimum of a problem. It is a contribution to a less researched area which may be named Diagnostic Optimisation.

Realistic negotiation settings in socio-economic contexts are distributed multi-attribute scenarios in which negotiators act largely selfishly but make concessions in the interests of long-term gains. These semi-competitive environments have increasingly complex goal structures in which a single negotiator has difficulty identifying his own ideal goals. In combination with the conflicting goals of other parties to the negotiations, the situation presents itself as a complex multi-objective scenario with incomplete information. Most existing approaches to this problem either assume linear or monotonic functions or they employ an unbiased mediator to select a single proposal as the basis of an agreement. Existing approaches also assume that each negotiating party can identify her own acceptance limit or reservation utility. The current work overcomes these limitations by introducing a distributed approach which integrates another party's proposals into the local optimisation process. It employs a dynamic coceding strategy which is not dependent on the identification of a reservation utility.

In stochastic optimisation, all currently employed algorithms have to be parameterised to perform effectively. Users have to rely on approximate guidelines or, alternatively, undertake extensive prior tuning. This study introduces a novel method of parameter control, i.e. the dynamic and automated variation of values for parameters used in approximate algorithms. The method uses an evaluation of the recent performance of previously applied parameter values and predicts how likely each of the parameter values is to produce optimal outcomes in the next cycle of the algorithm. The resulting probability distribution is used to determine the parameter values for the following cycle. The results of our experiments show a consistently superior performance of two very different EA algorithms when they are parameterised using the predictive parameter control method.

The automotive deployment problem is a real-world constrained multiobjective assignment problem in which software components must be allocated to processing units distributed around a car's chassis. Prior work has shown that evolutionary algorithms such as NSGA-II can produce good quality solutions to this problem. This paper presents a population-based ant colony optimisation (PACO) approach that uses a single pheromone memory structure and a range of local search operators. The PACO and prior NSGA-II are compared on two realistic problem instances. Results indicate that the PACO is generally competitive with NSGA-II and performs more effectively as problem complexity---size and number of objectives---is increased.

State-of-the art constrained multiobjective optimisation methods are often explored and demonstrated with the help of function optimisation problems from these accounts. It is sometimes hard for practitioners to extract good approaches for practical problems. In this paper we apply an evolutionary algorithm to a factual problem with realistic constraints and compare the effects of different operators and constraint handling methods. We observe that in spite of an apparently very insular search space, we consistently obtain the best results when using a repair mechanism, effectively eliminating infeasible solutions. This runs contrary to some recommendations in the optimisation literature which propose penalty functions for search spaces where feasible solutions are sparse.

The Hooke-Jeeves (HJ) Pattern Search, which seems to be the most popular choice among the local search algorithms, was used as an alternative to the dimensional local search (DLS), which has provided excellent results in previous work. In this paper, the question whether the well-known Hooke-Jeeves pattern search could outperform the DLS algorithm that was devised somewhat ad-hoc, is to be investigated. The Moving Peaks (MP) function is used as a benchmark. In our experiments, the algorithms performed almost identically well on the problem instances used. However, it was observed that the pattern move, an intrinsic part of the HJ algorithm, hardly contributed to the quality of the outcome, in fact less than the number sequence used as step sizes for both local searches. We provide some investigations into why the pattern move is less successful than most authors - including the original inventors of the Hooke-Jeeves search - seem to anticipate.

Decisions regarding the mapping of software components to hardware nodes affect the quality of the resulting system. Making these decisions is hard when considering the ever-growing complexity of the search space, as well as conflicting objectives and constraints. An automation of the solution space exploration would help not only to make better decisions but also to reduce the time of this process. In this paper, we propose to employ Ant Colony Optmisation (ACO) as a multi-objective optimisation strategy. The constructive approach is compared to an iterative optimisation procedure - a Genetic Algorithm (GA) adaptation - and was observed to perform suprisingly similar, although not quite on a par with the GA, when validated based on a series of experiments.

A new multi-phase multi-individual version of the extremal optimisation algorithm was devised for dynamic function optimisation. The algorithm was tested on the three standardised benchmark scenarios of the publicly available moving peaks (MP) problem and observed to outperform all numerical results of other algorithmic approaches currently available in the literature. Parts of the algorithm were subsequently tested on variations of the scenarios to establish the role of each algorithm component in solving the problem as well as its contribution to the overall result The reasons for the algorithm's impressive performance on the particular problem instance are discussed and possible limitations to its wider applicability are identified.

Solving dynamic combinatorial problems poses a particular challenge to optimisation algorithms. Optimising a dynamic problem that does not notify the solver when a change has been made is very difficult for most well-known algorithms. Extremal optimisation is a recent addition to the group of biologically inspired optimisation algorithms, while ant colony system has been used to solve a large variety of problem types in static and dynamic contexts. Both algorithms seem well suited to solving problems with hidden dynamics. We present a performance comparison of the two algorithms and endeavour to highlight particular strengths and weaknesses observed with different types of dynamic problem changes.

Biological systems are, by their very nature, adaptive. However, the meta-heuristic search algorithms inspired by them have mainly been applied to static problems (i.e., problems that do not change while they are being solved). Recently, a greater body of work has been completed on the newer meta-heuristics, particularly ant colony optimisation, particle swarm optimisation and extremal optimisation. This survey paper examines representative works and methodologies of these techniques on this class of problems. Beyond this we outline the limitations of these methods.